database - Cypher - 如何处理否定？

Question

我一直在努力理解Cypher是如何对应图数据库理论的。我特别想到了“Peter T.Wood 的图形数据库查询语言”(http://users.dcc.uchile.cl/~pbarcelo/wood.pdf)。我想它对应于具有聚合等附加操作的联合常规路径查询，但我无法在任何地方找到有关此的信息。

两个问题:

1. 有什么地方可以找到有关 Cypher 背后理论的信息吗？特别是结合查询自旋。
2. Cypher 如何处理否定？例如是“安全否定”吗？

背景:我开始使用 Neo4j 和 Cypher 来撰写我正在撰写的论文。我这样做是因为这些似乎都已经建立并且得到了很好的支持。但是，我想从我的查询回答抽象到更一般的图形查询形式主义，但我不知道 Cypher 是如何对应于此的。

Answer 1

我在 LinkedIn 上找到了这个问题的答案，可以在这里找到: https://www.linkedin.com/groups/Does-anybody-know-similarities-differences-2623939.S.5939804856381382658

下面的答案是指这个查询:

MATCH (n:Asteroid) WHERE NOT n.name = 'Ceres' RETURN n LIMIT 25

答案如下:

There are two answers to your question regarding negation:

(i) The negation of a property value

This is the case covered in the comment above, which is essentially correct; I will re-use the provided example. Internally, all nodes having the label 'Asteroid' are retrieved using the label index. This is followed by a “selection” operator (from relational algebra), which is used to select only those tuples containing either no 'name' property or where the 'name' property is not 'Ceres'.This is then followed by an operator called “top”, limiting the results returned to 25. As you can see, this does not differ from how SQL is executed on relational databases.

(ii) The negation of a pattern predicate

This is where the full power of graph pattern matching is utilised.

Say we have the following toy query, in which I want to find all events I have not attended:

MATCH (me:Person {name: “me”}), (e:Event) WHERE NOT ( (me) - [:ATTENDED] -> (e) ) RETURN e

Our query execution plan is a tree of operators, each of which has up to 2 children.

At root of the tree, we have an 'Anti Semi Apply' operator (equivalent to an anti-semijoin operator in relational theory). The left-hand child is a Cartesian Product of two sets of tuples: (1) a set of nodes corresponding to (me:Person {name: "me"}) retrieved using the label and property index, and (2) a set of nodes corresponding to (e:Event), retrieved using the label index. We note that the Cartesian Product will consist of all combinations of "me" nodes with every (e:Event) in the database.

The Cartesian Product emits a single row at a time, and this row, R, is piped upwards to the Anti Semi Apply operator. The Anti Semi Apply then feeds R as an argument to its right-hand branch, so that R appears as the ultimate descendant on the right-hand side. R is passed upwards to an Expand operator, which returns all (me)-[:ATTENDED]-(some_e) rows (note that the "me" here matches the one in R). Immediately, each such row, S, has a Selection operation applied to it, in order to match "some_e" to the "e" in R. Thus, any row S is in effect an "Event" ATTEND by "me". S is then piped to Anti Semi Apply. If no row S was found for R, R is returned as a result (as these will be all “Events” not ATTENDED by "me")

Thus, having negation in a query is not treated as a simple filter - it intrinsically affects the entire query plan.

More details on Cypher’s execution plans can be found at http://neo4j.com/docs/snapshot/execution-plans.html.