Cypher - How is denial handled?
I am trying to understand how Cypher fits with graph database theory. In particular, I was referring to Peter T. Wood's Query Languages for Graphics Databases ( http://users.dcc.uchile.cl/~pbarcelo/wood.pdf ). I suppose it matches conjunctive regular path queries with additional operations like aggregation, but I can't find information on this anywhere.
Two questions:
- Where can I find information on the theory behind Cypher? In particular, with the spin of a conjunctive query.
- How does Cypher handle denial? for example is this "safe denial"?
Reference Information. I started using Neo4j with Cypher for the paper I'm working on. I did this because they were both well established and well maintained. However, I want to take my mind off my query implementation by answering the more general graph query formalism, but I don't know how Cypher fits this.
source to share
I got an answer to this question on LinkedIn which can be found here: https://www.linkedin.com/groups/Does-anybody-know-similarities-differences-2623939.S.5939804856381382658
Below is the answer:
MATCH (n: Asteroid) WHERE NOT n.name = 'Ceres' RETURN n LIMIT 25
The answer is:
There are two answers to your question regarding denial:
(i) Negation of property value
This refers to the consideration above that is essentially true; I will use the given example. Internally, all nodes labeled Asteroid are retrieved using the index of the label. This is followed by a select operator (from relational algebra), which is used to select only those tuples that have no name, or where the name property is not Ceres. This is then followed by a statement called "up", which limits the results returned to 25. As you can see, this is no different from how SQL is done in relational databases.
(ii) Negation of a template predicate
This is where the full power of pattern matching is used.
Let's say we have the following toy query where I want to find all the events I haven't attended:
MATCH (me: Person {name: "me"}), (e: Event) WHERE NOT ((me) - [: ATTENDED] → (e)) RETURN e
Our query plan is a tree of statements, each with up to 2 children.
At the root of the tree, we have the "Anti Semi Apply" operator (equivalent to the anti-semioin operator in relational theory). The left child is the Cartesian product of two sets of tuples: (1) the set of nodes corresponding to (me: Person {name: "me"}) obtained by the label and property index, and (2) the set of nodes corresponding to (e: Event) is retrieved using the index of the label. Note that the Cartesian product will consist of all combinations of "me" nodes with each (e: Event) in the database.
The Cartesian product releases one line at a time, and that R line is redirected up to the Anti Semi Apply statement. Anti Semi Apply then feeds R as an argument to its right branch, so that R appears as the final child on the right side. R is passed up to an Expand statement, which returns all (me) - [: ATTENDED] - (some_e) lines (note that "me" here matches one in R). Immediately, each such line of S has a select operation applied to it to match "some_e" in "e" in R. Thus, any line of S is effectively an "event" ATTEND "me". S is then piped to Anti Semi-Apply. If row R is not found for R, the result is R (since these will be all "Events", not "I")
Thus, negation in a query is not seen as a simple filter — it essentially affects the entire query plan.
More information on Cyphers execution plans can be found at http://neo4j.com/docs/snapshot/execution-plans.html .
source to share