PostgreSQL을 사용하여 네트워크의 노드 결정
모든 항목이 노드이고 테이블에 각 노드와 다른 노드의 직접 연결이 포함 된 테이블이 있습니다. 노드 자체가 연결된 노드뿐만 아니라 체인의 모든 노드를 포함하는 각 노드에 대한 열이있는 뷰를 만들려고합니다.
예를 들어 다음 표의 처음 두 열에서 체인의 노드 열을 생성 할 수 있습니다.
CREATE TABLE example
(
node text,
connections text[],
nodes_in_chain text[]
)
INSERT INTO example VALUES
('a', ARRAY['a','b'], null),
('b', ARRAY['a','b','c','d'], null),
('c', ARRAY['b','c'], null),
('d', ARRAY['b','d'], null),
('e', ARRAY['e','f'], null),
('f', ARRAY['e','f'], null);
Node Connections Nodes in Chain
"a" "{a,b}" "{a,b,c,d}"
"b" "{a,b,c,d}" "{a,b,c,d}"
"c" "{b,c}" "{a,b,c,d}"
"d" "{b,d}" "{a,b,c,d}"
"e" "{e,f}" "{e,f}"
"f" "{e,f}" "{e,f}"
이것은 실제 문제의 작은 단순화 된 버전입니다. 예제를 풀 수 있다면 전체 테이블은 문제가되지 않습니다.
이 테이블의 데이터는 다음과 같은 방식으로 시각화 할 수 있습니다.
이 문제를 해결하기 위해 여러 가지 방법을 살펴 보았습니다. 재귀 CTE를 조사했지만 제대로 작동하도록 만들지 못했습니다.
각 노드는 현재 데이터베이스에있는 자체에 연결됩니다. 필요한 경우 데이터베이스에서 자체 연결을 제거하는 데 문제가 없습니다.
아마도 문제에 대한 불필요한 배경 :
이 문제의 원인은 교통 체증에서 차량을 식별하려는 시도에서 비롯됩니다. 원래 데이터베이스에는 주어진 영역에서 모든 시간 단계 t의 차량 위치와 속도가 포함됩니다. 목표는 신호등에서 보내는 시간을 결정하는 것입니다. 이 문제를 해결하기 위해 신호등의 정지 영역을 식별했습니다. 속도가 특정 임계 값 미만인이 지역의 각 차량은 신호등을 기다리는 것으로 간주됩니다. 줄이 길기 때문에 차량이이 구역 밖에서 대기 할 수 있습니다. 따라서 교통 선 ( "노드 체인")은 서로 특정 거리 내에 있고 속도가 낮은 모든 차량으로 만들어집니다. 식별 된 대기열 영역 내의 차량에서 시작합니다. 문제는 항공기 택시 시간에 대한 과학적 연구의 일부입니다. 따라서 차량은 항공기이고 신호등은 활주로 임계 값입니다.
먼저 Python과 pandas가있는 지역에서 차량을 식별하는 계산을 수행했습니다. 그러나 코드를 실행하는 데 10 배 더 오래 걸렸기 때문에 프로젝트에 방해가되었습니다. 코드는 수동으로 루프를 도입하지 않고 매우 간단했기 때문에 가속화 할 수 없었습니다. 또한 Python과 PostgreSQL에서 대기열 알고리즘을 수행하는 속도를 비교할 것입니다.
답변
접근법 1 :
샘플 데이터에 따르면 각 단일 연결이 다른 연결에 포함되어 있기 때문에 처음에는 기본 솔루션을 적용 할 수있는 것 같습니다.
SELECT
e1.node,
e1.connections,
COALESCE(e2.connections, e1.connections) nodes_in_chain
FROM
example e1
LEFT JOIN
example e2
ON e2.node <> e1.node
AND e1.connections <@ e2.connections;
노드 | 연결 | nodes_in_chain
: --- | : ---------- | : -------------
a | {a, b} | {a, b, c, d}
b | {a, b, c, d} | {a, b, c, d}
c | {b, c} | {a, b, c, d}
d | {b, d} | {a, b, c, d}
e | {e, f} | {e, f}
f | {e, f} | {e, f}
접근법 2 :
그러나 @ypercube가 지적 했듯이이 솔루션은 행에 3 개 이상의 선형 점이있는 경우 작동하지 않습니다.
예 : e-> f-> g-> h
이 질문을 해결하기 위해 다른 관련 질문에서 답변을 사용했습니다.
- Postgres의 여러 열 중 하나에 그룹화
전 이적 폐쇄 라는 방법을 사용 하여 문제를 해결합니다.
일시적인 폐쇄
수학에서 집합 X에 대한 이진 관계 R의 전 이적 종결은 R을 포함하고 전 이적 인 X에서 가장 작은 관계입니다.
예를 들어, X가 공항 집합이고 xRy가 "공항 x에서 공항 y까지의 직항 항공편이 있습니다"(X의 x 및 y에 대해)를 의미하는 경우 X에서 R의 전 이적 폐쇄는 관계 R +가됩니다. R + y는 "하나 이상의 비행에서 x에서 y로 날아갈 수 있음"을 의미합니다. 비공식적으로 전 이적 폐쇄는 모든 시작 위치에서 이동할 수있는 모든 장소의 집합을 제공합니다.
먼저 4 개 노드의 선형 연결을 추가하여 샘플 데이터를 변경하겠습니다.
DELETE FROM example WHERE node = 'f';
INSERT INTO example VALUES
('f', ARRAY['e','f','g'], null),
('g', ARRAY['f','g','h'], null),
('h', ARRAY['g','h'], null);
이제 수학을 적용합니다.
WITH RECURSIVE al (dst, src) AS --adjacent list or list of all related nodes
(
SELECT e1.node, e2.node
FROM example e1
JOIN example e2
ON e1.node = any(e2.connections)
), tc (dst, src) AS
(
SELECT dst, src FROM al -- transitive closure
UNION
SELECT a1.dst, a2.src
FROM al as a1
JOIN tc as a2
ON a1.src = a2.dst
)
SELECT src, array_agg(DISTINCT dst ORDER BY dst) AS nodes_in_chain
FROM tc
GROUP BY src;
이 결과를 제공하십시오.
src | nodes_in_chain
:-- | :-------------
a | {a,b,c,d}
b | {a,b,c,d}
c | {a,b,c,d}
d | {a,b,c,d}
e | {e,f,g,h}
f | {e,f,g,h}
g | {e,f,g,h}
h | {e,f,g,h}
db <> 여기에 바이올린
참고 : 원래 관계에는 길이 1 (각 노드 2 개)의 경로로 볼 수있는 즉시 연결 만 있습니다. 접근 방식 1은 한 번 연결하는 방법을 적용하므로 길이 2 (노드 3 개)의 모든 경로를 찾습니다. 길이가 N 인 경로를 찾으려면 방법을 N-1 번 적용해야합니다. 임의 길이의 모든 경로 (전 이적 클로저)를 찾으려면 재귀 솔루션 또는 while 루프가 필요합니다. 간단한 SQL로는 불가능합니다. (예 : CTE가없는 하나의 쿼리)
뿡뿡