경로#
고정된 패턴은 모양을 이미 아는 질문을 합니다. (a)-[]->(b)-[]->(c)는 언제나 두 홉입니다. 그래프가
있는 이유가 되는 질문은 모양을 모르는 질문입니다. 이 두 사람은 어떻게 연결되는가, 여기서 무엇에
도달할 수 있는가, 가장 값싼 경로는 무엇인가 같은 것입니다.
세 가지 도구가 그 질문에 답하며, 서로 다릅니다. 가변 길이 간선은 어떤 길이 범위 안의 모든 경로를
열거합니다. shortestpath는 길이가 최소인 경로 하나를 찾습니다. dijkstra는 가중치가 최소인
경로 하나를 찾는데, 그것은 흔히 같은 경로가 아닙니다.
여기 있는 것은 모두 예제 데이터셋에서 실행되며, 그 데이터셋의
related_to 간선에는 weight가 있습니다. 아래 두 절은 정류장 네 개로 된 작은 그래프도 필요하므로
지금 만들어 둡니다. 이 그래프에는 비용 10인 A → B 직행 구간, 각각 비용 1인 세 구간의 우회로, 그리고
A → B → A를 순환으로 만드는 복귀 구간이 있습니다:
CREATE GRAPH routelab;
SET graph_path = routelab;
CREATE VLABEL stop;
CREATE ELABEL leg;
CREATE (:stop {name: 'A'}), (:stop {name: 'B'}), (:stop {name: 'C'}), (:stop {name: 'D'});
MATCH (a:stop {name:'A'}), (b:stop {name:'B'}) CREATE (a)-[:leg {cost: 10}]->(b);
MATCH (a:stop {name:'A'}), (c:stop {name:'C'}) CREATE (a)-[:leg {cost: 1}]->(c);
MATCH (c:stop {name:'C'}), (d:stop {name:'D'}) CREATE (c)-[:leg {cost: 1}]->(d);
MATCH (d:stop {name:'D'}), (b:stop {name:'B'}) CREATE (d)-[:leg {cost: 1}]->(b);
MATCH (b:stop {name:'B'}), (a:stop {name:'A'}) CREATE (b)-[:leg {cost: 1}]->(a);
아래의 각 블록은 두 그래프 중 필요한 쪽으로 graph_path를 설정합니다.
홉 수가 정해지지 않은 경우#
간선 레이블 뒤의 *가 그 길이를 범위로 만듭니다. 경계는 별표 뒤에 씁니다:
표기 |
뜻 |
|---|---|
|
정확히 간선 두 개 |
|
간선 한 개, 두 개, 또는 세 개 |
|
두 개 이상 |
|
최대 세 개, 최소 한 개 |
|
한 개 이상, 상한 없음 |
|
그 정점 자신, 또는 간선 하나 거리 |
길이를 고정하면 패턴을 길게 늘여 쓴 것과 같이 동작합니다:
SET graph_path = moviekb;
MATCH (a:movie {title: 'The Matrix'})-[:related_to*2]->(b:movie) RETURN b.title AS reached ORDER BY reached;
reached
------------------------------
"Inception"
"Terminator 2: Judgment Day"
"The Matrix Revolutions"
범위는 그 안의 길이들을 합집합으로 묶으므로, 더 짧은 도달 결과도 함께 돌아옵니다:
MATCH (a:movie {title: 'The Matrix'})-[:related_to*1..2]->(b:movie) RETURN b.title AS reached ORDER BY reached;
reached
------------------------------
"Inception"
"Terminator 2: Judgment Day"
"The Matrix Reloaded"
"The Matrix Revolutions"
"The Terminator"
"Total Recall"
하한이 0이면 시작 정점 자신이 포함되며, 이때는 아무것과도 일치시키지 않습니다:
MATCH (a:movie {title: 'The Matrix'})-[:related_to*0..1]->(b:movie) RETURN b.title AS reached ORDER BY reached;
reached
-----------------------
"The Matrix"
"The Matrix Reloaded"
"The Terminator"
"Total Recall"
상한을 생략하면 “간선이 이어지는 곳까지”를 뜻합니다:
MATCH (a:movie {title: 'The Matrix'})-[:related_to*]->(b:movie) RETURN count(*) AS reachable;
reachable
-----------
7
영원히 돌지는 않는다#
순환이 있는 그래프에서 상한 없는 순회도 끝납니다. 어떤 경로도 같은 간선을 두 번 쓸 수 없기
때문입니다. routelab에는 A → B → A 순환이 있습니다. A에서 A로 돌아오는, 간선 여덟 개까지의
경로를 물어봅니다:
SET graph_path = routelab;
MATCH p = (a:stop {name: 'A'})-[:leg*..8]->(a)
RETURN length(p) AS hops, [x IN nodes(p) | x.name] AS route ORDER BY hops;
hops | route
------+---------------------------
2 | ["A", "B", "A"]
4 | ["A", "C", "D", "B", "A"]
무한이 아니라 경로 두 개입니다. 각각 어떤 간선도 다시 쓰지 않는 보행입니다. 정점은 반복될 수
있으며, 여기서 A가 양쪽 끝에 나타나는 것이 그렇습니다.
이 보장은 비용이 아니라 정확성에 관한 것입니다. 밀도가 높은 그래프에서 상한 없는 탐색은 간선이 바닥나기 전까지 엄청난 수의 경로를 열거할 수 있습니다. 상한이 얼마쯤이어야 할지 짐작이 가는 경우라면 언제든 범위에 상한을 주십시오.
경로를 바인딩하기#
패턴 앞의 p = 는 경로 전체를 바인딩하고, 세 함수가 그것을 분해합니다. length(p)는 간선 개수,
nodes(p)는 순서대로의 정점, relationships(p)는 간선입니다.
SET graph_path = moviekb;
MATCH p = (a:movie {title: 'The Matrix'})-[:related_to*2]->(b:movie)
RETURN length(p) AS hops,
[x IN nodes(p) | x.title] AS route,
[r IN relationships(p) | r.weight] AS weights
ORDER BY route;
hops | route | weights
------+-----------------------------------------------------------------+---------
2 | ["The Matrix", "The Matrix Reloaded", "The Matrix Revolutions"] | [1, 1]
2 | ["The Matrix", "The Terminator", "Terminator 2: Judgment Day"] | [3, 1]
2 | ["The Matrix", "Total Recall", "Inception"] | [4, 2]
[x IN list | expression] 형태는 리스트 컴프리헨션이며, 경로를 읽기 좋게 표현하는 방법입니다.
edges(p)는 relationships(p)와 같은 뜻입니다.
레이블 두 종류를 지나는 경로는 속성마다 컴프리헨션이 하나씩 필요합니다. person에는 title이
없고 movie에는 name이 없기 때문입니다:
MATCH p = shortestpath((a:person {name: 'Keanu Reeves'})-[e:acted_in*..6]-(b:person {name: 'Carrie-Anne Moss'}))
RETURN length(p) AS hops, [x IN nodes(p) | x.name] AS people, [x IN nodes(p) | x.title] AS films;
hops | people | films
------+--------------------------------------------+----------------------------
2 | ["Keanu Reeves", null, "Carrie-Anne Moss"] | [null, "The Matrix", null]
경로 자체를 반환하면 모든 요소가 전부 출력됩니다. 탐색할 때는 유용하지만 그 밖의 경우에는
과합니다. 경로의 모양을 간결하게 보는 방법은 label(x)입니다.
최단 경로#
shortestpath는 가변 길이 간선이 하나 있는 패턴을 받아 길이가 최소인 경로 하나를 반환하고, 그런
경로가 없으면 아무 행도 반환하지 않습니다. 이것은 “경로들을 길이로 정렬해 하나만 취하는 것”이
아닙니다. 양쪽 탐색 전선이 만나는 순간 멈추는 양방향 탐색이므로, 버릴 경로를 열거하지 않습니다.
MATCH p = shortestpath((a:person {name: 'Keanu Reeves'})-[e*..6]-(b:person {name: 'Arnold Schwarzenegger'}))
RETURN length(p) AS hops,
[x IN nodes(p) | label(x)] AS labels,
[r IN relationships(p) | label(r)] AS via;
hops | labels | via
------+----------------------------------------+----------------------------------------
3 | ["person", "movie", "movie", "person"] | ["acted_in", "related_to", "acted_in"]
위 쿼리에서 세 가지는 의도한 것입니다. 간선에 타입이 없고 방향도 주지 않았습니다. 경로가 서로 다른 간선 레이블 두 종류를 지나며, 한쪽은 정방향으로 다른 쪽은 역방향으로 따라가기 때문입니다.
상한 6이 붙어 있는 것은, 레이블 없는 간선에 대한 상한 없는 최단 경로 탐색이 이 매뉴얼에서 가장 비싼 쿼리이기 때문입니다. 그리고 양 끝점이 변수에 바인딩돼 있습니다.
마지막 것은 반드시 지켜야 합니다:
MATCH p = shortestpath((:person {name: 'Keanu Reeves'})-[e*..6]-(:person {name: 'Arnold Schwarzenegger'}))
RETURN length(p);
ERROR: node must be a reference to a specific node
이름을 쓰지 않을 때에도 양 끝에 이름을 붙이십시오. 변수를 생략하는 것이 낭비에 그치지 않고 아예 거부되는 곳은 여기 하나입니다.
allshortestpaths는 같은 탐색이지만 최소 길이인 경로 중 하나가 아니라 전부를 반환합니다:
MATCH p = allshortestpaths((a:movie {title: 'The Matrix'})-[:related_to*..4]->(b:movie {title: 'Inception'}))
RETURN length(p) AS hops, [x IN nodes(p) | x.title] AS route;
hops | route
------+---------------------------------------------
2 | ["The Matrix", "Total Recall", "Inception"]
여기서는 경로가 하나입니다. 이 데이터셋의 related_to 간선이 트리를 이루기 때문입니다. 똑같이
짧은 경로가 여러 개인 그래프에서는 각각 한 행씩 나옵니다. 그 동률 자체가 관심사일 때 원하는
것입니다.
두 함수 모두 간선 레이블의 택일 표기를 받지 않습니다. [:acted_in|directed*..4]는
ERROR: multiple types for relationship not supported를 냅니다. 간선에 타입을 주지 않고 나중에
걸러 내십시오. 그래프 읽기를 참고하십시오.
가장 값싼 경로#
shortestpath는 간선을 셉니다. 간선이 항상 서로 바꿔 놓을 수 있는 것은 아닙니다. 거리, 지연,
가격, 유사도를 담고 있을 수 있습니다. 그럴 때 간선을 세는 것은 틀린 질문에 답하는 것입니다.
dijkstra는 가중치 표현식을 받아 그 합을 최소화합니다.
차이는 routelab에서 가장 잘 보입니다. A에서 B로 가는 쓸 만한 경로가 두 개 있습니다:
SET graph_path = routelab;
MATCH p = (a:stop {name: 'A'})-[:leg*..3]->(b:stop {name: 'B'})
RETURN length(p) AS hops, [x IN nodes(p) | x.name] AS route, [r IN relationships(p) | r.cost] AS costs
ORDER BY hops;
hops | route | costs
------+----------------------+-----------
1 | ["A", "B"] | [10]
3 | ["A", "C", "D", "B"] | [1, 1, 1]
shortestpath는 한 홉 경로를 고릅니다:
MATCH p = shortestpath((a:stop {name: 'A'})-[:leg*..5]->(b:stop {name: 'B'}))
RETURN length(p) AS hops, [x IN nodes(p) | x.name] AS route;
hops | route
------+------------
1 | ["A", "B"]
dijkstra는 세 홉 경로를 고릅니다. 비용이 10이 아니라 3이기 때문입니다:
MATCH (a:stop {name: 'A'}), (b:stop {name: 'B'})
MATCH (p, total) = dijkstra((a)-[e:leg]->(b), e.cost)
RETURN total AS cost, length(p) AS hops, [x IN nodes(p) | x.name] AS route;
cost | hops | route
------+------+----------------------
3 | 3 | ["A", "C", "D", "B"]
구문에서 틀리기 쉬운 것이 두 가지 있습니다.
패턴에는 가변 길이 간선이 아니라 간선 하나를 씁니다. dijkstra는 확장을 스스로 하므로, 한 홉만
쓰면 필요한 만큼 알아서 따라갑니다. 거기에 *를 쓰면
ERROR: variable length relationship is not supported로 거부되고, 간선을 둘 이상 쓰면
ERROR: only one relationship is allowed로 거부됩니다.
가중치 표현식은 간선 변수를 이름으로 부릅니다. e.cost는 패턴 안에서 바인딩된 e를 가리키며,
탐색이 확장될 때마다 간선별로 평가됩니다.
(p, total) = dijkstra(...)는 두 가지를 바인딩합니다. 경로와, 그 경로의 총 가중치입니다. 변수 하나
형태인 p = dijkstra(...)는 경로만 줍니다.
이 매뉴얼의 데이터셋에서는 가중치가 related_to에 있습니다:
SET graph_path = moviekb;
MATCH (a:movie {title: 'The Matrix'}), (b:movie {title: 'Inception'})
MATCH (p, total) = dijkstra((a)-[e:related_to]->(b), e.weight)
RETURN total AS weight, [x IN nodes(p) | x.title] AS route, [r IN relationships(p) | r.weight] AS legs;
weight | route | legs
--------+---------------------------------------------+--------
6 | ["The Matrix", "Total Recall", "Inception"] | [4, 2]
세 번째 인자는 한정자입니다. 탐색이 후보 간선마다 적용하는 불리언이며, 그래프를 미리 걸러 내는 대신 간선을 제외할 수 있습니다. 아래에서는 아무것도 살아남지 않습니다. The Matrix에서 Inception 쪽으로 나가는 유일한 경로가 가중치 4인 간선을 지나기 때문입니다:
MATCH (a:movie {title: 'The Matrix'}), (b:movie {title: 'Inception'})
MATCH (p, total) = dijkstra((a)-[e:related_to]->(b), e.weight, e.weight < 3)
RETURN total AS weight, [x IN nodes(p) | x.title] AS route;
weight | route
--------+-------
(0 rows)
모든 조건이 그래야 하듯 한정자도 불리언이어야 합니다. 괄호 안의 LIMIT n은 반환되는 경로 수의
상한을 정합니다. 둘 다 dijkstra에 설명돼 있습니다.
경로 쿼리의 비용#
가변 길이 간선의 실행 계획에는 그것만의 노드가 있고, 그 노드는 따라가는 레이블과 따라가는 범위를 이름으로 보여 줍니다:
EXPLAIN (COSTS OFF) MATCH (a:movie {title: 'The Matrix'})-[r:related_to*1..3]->(b:movie) RETURN b.title;
QUERY PLAN
--------------------------------------------------------------
Nested Loop
-> Seq Scan on movie a
Filter: (properties.'title' = '"The Matrix"'::jsonb)
-> Hash Join
Hash Cond: (r."end" = b.id)
-> Subquery Scan on r
-> Graph VLE on related_to [1..3]
-> Result
-> Hash
-> Seq Scan on movie b
읽어야 할 것은 Graph VLE on related_to [1..3]입니다. 레이블을 생략하면 이것이
Graph VLE on ag_edge가 되며, 매 홉마다 그래프의 모든 간선 레이블을 훑습니다:
EXPLAIN (COSTS OFF) MATCH (a:movie {title: 'The Matrix'})-[r*1..2]->(b:movie) RETURN b.title;
QUERY PLAN
--------------------------------------------------------------
Nested Loop
-> Seq Scan on movie a
Filter: (properties.'title' = '"The Matrix"'::jsonb)
-> Hash Join
Hash Cond: (r."end" = b.id)
-> Subquery Scan on r
-> Graph VLE on ag_edge [1..2]
-> Result
-> Hash
-> Seq Scan on movie b
shortestpath는 Hash2Side 노드 한 쌍 위의 Shortestpath VLE [min..max]로 나타납니다. 그 두
노드가 양방향 탐색의 두 전선입니다. dijkstra는 Dijkstra 노드로 나타납니다. 세 경우 모두 홉마다
하는 일은 간선 레이블의 (start, "end") 또는 ("end", start) 인덱스를 찾아보는 것입니다. 그래서
경로 쿼리의 비용은 전선이 닿는 간선의 개수입니다. 그것을 줄이는 것이 네 가지 있고, 효과가 큰
순서대로 적으면 이렇습니다:
한쪽 끝을 고정하십시오. 선택도가 높고 인덱스가 걸린 속성에 고정합니다. 알고 있는 정점 하나에서 출발하는 순회는 전부에서 출발하는 순회와 다른 쿼리입니다.
간선 레이블을 이름으로 부르십시오. 홉마다 테이블 하나를 보는 것과 전부를 보는 것의 차이입니다.
길이에 상한을 두십시오. 상한은 실행기가 쓸 수 있는 약속입니다.
간선 레이블에
ANALYZE를 돌리십시오. 순회 비용 산정은 차수 추정이고, 분석하지 않은 간선 레이블에는 추정에 쓸 차수가 없습니다. 쿼리 튜닝을 참고하십시오.
정리#
DROP GRAPH routelab CASCADE;