Поиск корня дерева в ориентированном графе

Question

У меня есть древовидная структура, такая как node (1) -> node (2) -> node (3). У меня есть имя как свойство, используемое для извлечения узла.

Учитывая, что узел сказал узел (3), я хочу получить узел (1).

Запрос пытался:

MATCH (р: Node) - [: HAS *] -> (с: Node) где c.name = "Узел 3" ВОЗВРАТ р LIMIT 5

Но, не способный получить узел 1.

Answer 1

Ваш запрос не только вернет «узел 1», но должен содержать хотя бы один путь, содержащий его. Можно фильтровать путь только получить один пересекающие весь путь к корню, однако:

MATCH (c:Node {name: "node 3"})<-[:HAS*0..]-(p:Node) 
// The root does not have any incoming relationship 
WHERE NOT (p)<-[:HAS]-() 
RETURN p 

Обратите внимание на использовании 0 длины, которая соответствует всем случаям, в том числе тот, где узел запуска является корень.

Удовлетворительный факт: даже если у вас есть индекс в Node: name, он не будет использоваться (если вы не используете Neo4j 3.1, где он, по-видимому, исправлен с 3.1 Beta2, по крайней мере), и вы должны явно укажите его.

MATCH (c:Node {name: "node 3"})<-[:HAS*0..]-(p:Node) 
USING INDEX c:Node(name) 
WHERE NOT (p)<-[:HAS]-() 
RETURN p 

Использование PROFILE на первый запрос (с числовым id собственности вместо name):

+-----------------------+----------------+------+---------+-------------------------+----------------------+ 
| Operator    | Estimated Rows | Rows | DB Hits | Variables    | Other    | 
+-----------------------+----------------+------+---------+-------------------------+----------------------+ 
| +ProduceResults  |    0 | 1 |  0 | p      | p     | 
| |      +----------------+------+---------+-------------------------+----------------------+ 
| +AntiSemiApply  |    0 | 1 |  0 | anon[23], c -- p  |      | 
| |\     +----------------+------+---------+-------------------------+----------------------+ 
| | +Expand(All)  |    1 | 0 |  3 | anon[58], anon[67] -- p | (p)<-[:HAS]-()  | 
| | |     +----------------+------+---------+-------------------------+----------------------+ 
| | +Argument   |    1 | 3 |  0 | p      |      | 
| |      +----------------+------+---------+-------------------------+----------------------+ 
| +Filter    |    1 | 3 |  3 | anon[23], c, p   | p:Node    | 
| |      +----------------+------+---------+-------------------------+----------------------+ 
| +VarLengthExpand(All) |    1 | 3 |  5 | anon[23], p -- c  | (c)<-[:HAS*]-(p)  | 
| |      +----------------+------+---------+-------------------------+----------------------+ 
| +Filter    |    1 | 1 |  3 | c      | c.id == { AUTOINT0} | 
| |      +----------------+------+---------+-------------------------+----------------------+ 
| +NodeByLabelScan  |    3 | 3 |  4 | c      | :Node    | 
+-----------------------+----------------+------+---------+-------------------------+----------------------+ 

Total database accesses: 18 

и на второй:

+-----------------------+----------------+------+---------+-------------------------+------------------+ 
| Operator    | Estimated Rows | Rows | DB Hits | Variables    | Other   | 
+-----------------------+----------------+------+---------+-------------------------+------------------+ 
| +ProduceResults  |    0 | 1 |  0 | p      | p    | 
| |      +----------------+------+---------+-------------------------+------------------+ 
| +AntiSemiApply  |    0 | 1 |  0 | anon[23], c -- p  |     | 
| |\     +----------------+------+---------+-------------------------+------------------+ 
| | +Expand(All)  |    1 | 0 |  3 | anon[81], anon[90] -- p | (p)<-[:HAS]-() | 
| | |     +----------------+------+---------+-------------------------+------------------+ 
| | +Argument   |    1 | 3 |  0 | p      |     | 
| |      +----------------+------+---------+-------------------------+------------------+ 
| +Filter    |    1 | 3 |  3 | anon[23], c, p   | p:Node   | 
| |      +----------------+------+---------+-------------------------+------------------+ 
| +VarLengthExpand(All) |    1 | 3 |  5 | anon[23], p -- c  | (c)<-[:HAS*]-(p) | 
| |      +----------------+------+---------+-------------------------+------------------+ 
| +NodeUniqueIndexSeek |    1 | 1 |  2 | c      | :Node(id)  | 
+-----------------------+----------------+------+---------+-------------------------+------------------+ 

Total database accesses: 13