Определите узлы в сети с помощью 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, b} | {а, б, в, г}
б | {a, b, c, d} | {а, б, в, г}
c | {b, c} | {а, б, в, г}
d | {b, d} | {а, б, в, г}
е | {e, f} | {e, f}
f | {e, f} | {e, f}
Подход 2:
Но, как указал @ypercube , это решение не работает, если в строке есть 3 или более линейных точки.
Пример: e -> f -> g -> h
В качестве ссылки для решения этого вопроса я использовал ответы на другой связанный вопрос:
- Группировка по любому из нескольких столбцов в Postgres
Для решения проблемы он использует метод, называемый транзитивным замыканием .
Переходное закрытие
В математике транзитивное замыкание бинарного отношения R на множестве X - это наименьшее отношение на X, которое содержит R и является транзитивным.
Например, если X - это набор аэропортов, а xRy означает «есть прямой рейс из аэропорта x в аэропорт y» (для x и y в X), то транзитивное замыкание R на X - это отношение R + такое, что x 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.)
@ypercube