두 노드 간의 모든 경로에 대한 Cypher

Question

나는 수백만 개의 노드와 관계가있는 그래프를 가지고 있습니다. 두 노드 사이에 모든 경로를 가져와야합니다. 내 경우에 관계 경로의 모든 노드는 같은 레이블이어야합니다.

내 쿼리는 다음과 같습니다.

match (n:Label) match (m:Label) where n.NAME='foo' and m.NAME='foo2' 
match p=(n)-[r*..20]-(m) where all(x in nodes(p) where (x:Label)) 
with p 
return p, EXTRACT(x IN nodes(p) | x.NAME), EXTRACT(r IN relationships(p) | type(r)) 

노드 레이블 "라벨"을 수는 약 20 만 모든 그래프에서이 쿼리 트래버스와 경로를 줄이는 노력하고 두 개의 노드 사이의 모든 가능한 경로를 찾아 내 "여기서 모든"절. 그런 다음 내 데이터베이스가 손상됩니다.

레이블 이름이 "Label"인 모든 노드와 그 관계를 구해야하므로 비용을 줄이기 위해 하위 그래프 간 경로를 쿼리해야합니다.

Answer 1

많은 수의 경로를 생성 할 때 레이블 필터를 지정할 수 있으므로 많은 도움이 될 Path Expander APOC 절차가 있습니다. 예를 들어

:

MATCH (n:Label {NAME: 'foo'}) 
WITH COLLECT(n) AS ns1 
MATCH (m:Label {NAME: 'foo2'}) 
WITH ns1 + COLLECT(m) AS startNodes 
CALL apoc.path.expandConfig(
    startNodes, 
    {labelFilter: '+Label', minLevel: 1, maxLevel: 20} 
) YIELD path 
RETURN 
    path, 
    [x IN nodes(path) | x.NAME] AS names, 
    [r IN relationships(path) | TYPE(r)] AS types; 

Answer 2

노드의 수백만의 그래프 (20의 길이까지의 경우에도) 메모리 오버 플로우를 일으킬 수있는 모든 가능한 경로를 찾으려고.

작은 작업으로 나누면됩니다. 쿼리는 우아하지 않지만 작동해야합니다. 우리는 한 번에 5의 경로 길이를하고 있다면

예를 들어, 두 개의 세그먼트 쿼리는 다음과 같이 표시됩니다

MATCH p1 = (n1:Label)-[r1*..5]-(n2:Label), p2 = (n2:Label)-[r2*..5]-(n3:Label) 
WHERE all(x1 in nodes(p1) WHERE (x1:Label)) 
AND all(x2 in nodes(p2) WHERE (x2:Label)) 
RETURN r1, r2 

이 쿼리에 대한 비용 계획은 같은 같습니다

+-----------------------+----------------------+---------------------+ 
| Operator    | Variables   | Other    | 
+-----------------------+----------------------+---------------------+ 
| +ProduceResults  | r1     | r1     | 
| |      +----------------------+---------------------+ 
| +Filter    | n1, n2, n3, r1, r2 | [see below]   | 
| |      +----------------------+---------------------+ 
| +VarLengthExpand(All) | n1, r1 -- n2, n3, r2 | (n2)-[r1:*..5]-(n1) | 
| |      +----------------------+---------------------+ 
| +Filter    | n2, n3, r2   | n3:Label   | 
| |      +----------------------+---------------------+ 
| +VarLengthExpand(All) | n3, r2 -- n2   | (n2)-[r2:*..5]-(n3) | 
| |      +----------------------+---------------------+ 
| +NodeByLabelScan  | n2     | :Label    | 
+-----------------------+----------------------+---------------------+ 

첫 번째 확장 후에 필터는 :Label으로 시작하고 끝나지 않는 경로를 필터링하고 두 번째 확장 만 발생한다는 것을 알 수 있습니다.

네오 버전이 2.2 이상인 경우 p1 및 p2will not include the same relationships입니다.

할 수 있습니다 실제로 필터링이 ProduceResults 연산자 (두 번째 줄) 앞의 필터에서 수행 참조 : 당신은 또한 우리는 마지막 필터에 경로에있는 모든 노드에 대해 확인하는 것이 나타납니다 이제

all(x1 in NodesFunction(ProjectedPath(Set(r1, n1),)) where x1:Label) 
AND none(r1 in r1 where any(r2 in r2 where r1 == r2)) 
AND n1:Label 

을 . 그러므로 (a : Label) - (b : Blah) - (c : Label)과 같은 경로는 여전히 첫 번째 세그먼트를 지나고 결과 생성 전에 필터링됩니다.

따라서 모든 세그먼트 노드에 :Label이 있는지 확인하고 더 유사한 방법으로 과거 관계가 비슷한 관계를 수동으로 확인하여 최적화 할 수 있습니다.

WITH n2, r1 
MATCH p2 = (n2:Label)-[r2*..5]-(n3:Label) 
WHERE all(x2 in nodes(p2) WHERE (x2:Label)) 
AND none(r1 in r1 where any(r2 in r2 where r1 == r2)) 

내가 언급하지만, 같은 쿼리 게으른 방식으로 실행된다는 점을 기억하는 것을 잊었다 : 만 두 번째 단계를 보여주는.