Посещение ориентированного графа, как если бы оно было неориентированным, используя рекурсивный запрос
Мне нужна ваша помощь о посещении ориентированного графика, хранящегося в базе данных.
Рассмотрим следующий направленный граф
1->2
2->1,3
3->1
В таблице хранятся эти отношения:
create database test;
\c test;
create table ownership (
parent bigint,
child bigint,
primary key (parent, child)
);
insert into ownership (parent, child) values (1, 2);
insert into ownership (parent, child) values (2, 1);
insert into ownership (parent, child) values (2, 3);
insert into ownership (parent, child) values (3, 1);
Я хотел бы извлечь все полусвязанные ребра (т.е. связанные ребра, игнорирующие направление) графика, достижимого из node. I.e., если я начинаю с parent = 1, я хотел бы иметь следующий вывод
1,2
2,1
2,3
3,1
Я использую postgresql.
Я изменил пример в руководстве Postgres, в котором объясняются рекурсивные запросы, и я адаптировал условие соединения для перехода вверх и вниз ( делая это, я игнорирую указания). Мой запрос следующий:
\c test
WITH RECURSIVE graph(parent, child, path, depth, cycle) AS (
SELECT o.parent, o.child, ARRAY[ROW(o.parent, o.child)], 0, false
from ownership o
where o.parent = 1
UNION ALL
SELECT
o.parent, o.child,
path||ROW(o.parent, o.child),
depth+1,
ROW(o.parent, o.child) = ANY(path)
from
ownership o, graph g
where
(g.parent = o.child or g.child = o.parent)
and not cycle
)
select g.parent, g.child, g.path, g.cycle
from
graph g
его вывод следует:
parent | child | path | cycle
--------+-------+-----------------------------------+-------
1 | 2 | {"(1,2)"} | f
2 | 1 | {"(1,2)","(2,1)"} | f
2 | 3 | {"(1,2)","(2,3)"} | f
3 | 1 | {"(1,2)","(3,1)"} | f
1 | 2 | {"(1,2)","(2,1)","(1,2)"} | t
1 | 2 | {"(1,2)","(2,3)","(1,2)"} | t
3 | 1 | {"(1,2)","(2,3)","(3,1)"} | f
1 | 2 | {"(1,2)","(3,1)","(1,2)"} | t
2 | 3 | {"(1,2)","(3,1)","(2,3)"} | f
1 | 2 | {"(1,2)","(2,3)","(3,1)","(1,2)"} | t
2 | 3 | {"(1,2)","(2,3)","(3,1)","(2,3)"} | t
1 | 2 | {"(1,2)","(3,1)","(2,3)","(1,2)"} | t
3 | 1 | {"(1,2)","(3,1)","(2,3)","(3,1)"} | t
(13 rows)
У меня проблема : запрос извлекает одни и те же ребра много раз, поскольку они достигаются с помощью разных путей, и я хотел бы избежать этого. Если я изменяю внешний запрос в
select distinct g.parent, g.child from graph
У меня есть желаемый результат, но неэффективность остается в запросе WITH, поскольку выполняются ненужные объединения.
Итак, есть ли решение для извлечения достижимых ребер графа в db, начиная с заданного, без использования отдельных?
У меня также есть другая проблема (эта проблема решена, посмотрите внизу): как вы можете видеть на выходе, циклы останавливаются только тогда, когда во второй раз node достигается. То есть У меня (1,2) (2,3) (1,2).
Я хотел бы остановить цикл перед повторением велосипеда по этому последнему node, т.е. иметь (1,2) (2,3).
Я попытался изменить условия where следующим образом
where
(g.parent = o.child or g.child = o.parent)
and (ROW(o.parent, o.child) <> any(path))
and not cycle
чтобы избежать посещений уже посещенных краев, но он не работает, и я не могу понять, почему ((ROW(o.parent, o.child) <> any(path)) следует избегать циклирования, прежде чем снова переходить к циклическому краю, но не работает). Как я могу сделать, чтобы остановить циклы на один шаг до node, который закрывает цикл?
Изменить: как предложил danihp, чтобы решить вторую проблему, которую я использовал
where
(g.parent = o.child or g.child = o.parent)
and not (ROW(o.parent, o.child) = any(path))
and not cycle
и теперь вывод не содержит циклов. Строки изменились с 13 до 6, но у меня все еще есть дубликаты, поэтому основная (первая) проблема извлечения всех краев без дубликатов и без четкости все еще жива. Токовый выход с and not ROW
parent | child | path | cycle
--------+-------+---------------------------+-------
1 | 2 | {"(1,2)"} | f
2 | 1 | {"(1,2)","(2,1)"} | f
2 | 3 | {"(1,2)","(2,3)"} | f
3 | 1 | {"(1,2)","(3,1)"} | f
3 | 1 | {"(1,2)","(2,3)","(3,1)"} | f
2 | 3 | {"(1,2)","(3,1)","(2,3)"} | f
(6 rows)
Изменить №2:: следуя предложенному Эрвином Брандстетером, я изменил свой запрос, но если я не ошибаюсь, предлагаемый запрос дает больше строк, чем мой (сравнение ROW все еще существует кажется мне более понятным, даже я понял, что сравнение строк будет более эффективным).
Используя новый запрос, я получаю 20 строк, а my дает 6 строк
WITH RECURSIVE graph(parent, child, path, depth) AS (
SELECT o.parent, o.child, ARRAY[ROW(o.parent, o.child)], 0
from ownership o
where 1 in (o.child, o.parent)
UNION ALL
SELECT
o.parent, o.child,
path||ROW(o.parent, o.child),
depth+1
from
ownership o, graph g
where
g.child in (o.parent, o.child)
and ROW(o.parent, o.child) <> ALL(path)
)
select g.parent, g.child from graph g
Изменить 3: так, как указал Эрвин Брандштеттер, последний запрос по-прежнему был неправильным, а правильный - в его ответе.
Когда я отправил свой первый запрос, я не понял, что мне не хватает некоторых подключений, как это происходит в следующем случае: если я начинаю с node 3, db выбирает строки (2,3) и (3,1). Затем первый индуктивный шаг запроса будет выбирать, присоединяясь из этих строк, строки (1,2), (2,3) и (3,1), пропуская строку (2,1), которая должна быть включена в результат, как концептуально алгоритм ((2,1) находится "рядом" (3,1))
Когда я попытался адаптировать пример в руководстве Postgresql, я был прав, пытаясь присоединиться к родительскому и дочернему объектам ownership, но я ошибся, не сохраняя значение graph, которое должно было быть соединено на каждом шаге.
Кажется, что эти типы запросов генерируют другой набор строк в зависимости от начального node (т.е. в зависимости от набора строк, выбранного на базовом этапе). Итак, я думаю, было бы полезно выбрать только одну строку, содержащую начальный node на базовом этапе, так как вы все равно получите любой другой "соседний" node.
Ответы
Ответ 1
Может работать следующим образом:
WITH RECURSIVE graph AS (
SELECT parent
,child
,',' || parent::text || ',' || child::text || ',' AS path
,0 AS depth
FROM ownership
WHERE parent = 1
UNION ALL
SELECT o.parent
,o.child
,g.path || o.child || ','
,g.depth + 1
FROM graph g
JOIN ownership o ON o.parent = g.child
WHERE g.path !~~ ('%,' || o.parent::text || ',' || o.child::text || ',%')
)
SELECT *
FROM graph
Вы упомянули производительность, поэтому я оптимизирован в этом направлении.
Основные моменты:
-
Поверните график только в определенном направлении .
-
Нет необходимости в столбце cycle, вместо этого сделайте это условие исключения. Еще один шаг. Это также прямой ответ на:
Как сделать, чтобы остановить циклы на один шаг до node, который закрывает цикл?
-
Используйте строку для записи пути. Меньше и быстрее, чем массив строк. Все еще содержит всю необходимую информацию. Могу меняться с очень большими номерами bigint.
-
Проверка циклов с помощью оператора LIKE (~~) должна быть намного быстрее.
-
Если вы не ожидаете больше 2147483647 строк с течением времени, используйте обычные столбцы integer вместо bigint. Меньше и быстрее.
-
Обязательно иметь индекс на parent. Индекс на child не имеет значения для моего запроса. (За исключением оригинала, где вы пересекаете края в обоих направлениях.)
-
Для огромных графов я бы переключился на процедуру plpgsql, где вы можете поддерживать путь как временную таблицу с одной строкой за шаг и соответствующий индекс. Немного накладных расходов, которые будут окупаться огромными графиками.
Проблемы в исходном запросе:
WHERE (g.parent = o.child or g.child = o.parent)
В любой момент процесса существует только одна конечная точка вашего обхода. Когда вы вставляете ориентированный график в обоих направлениях, конечная точка может быть либо родительской, либо дочерней, но не обоим. Вы должны сохранить конечную точку каждого шага, а затем:
WHERE g.child IN (o.parent, o.child)
Нарушение направления также делает ваше начальное условие сомнительным:
WHERE parent = 1
Должно быть
WHERE 1 IN (parent, child)
И две строки (1,2) и (2,1) эффективно дублируются таким образом...
Дополнительное решение после комментария
- Игнорировать направление
- Продолжайте движение по любому ребру только один раз на каждый путь.
- Используйте ARRAY для пути
- Сохранить исходное направление в пути, а не в фактическом направлении.
Обратите внимание, что таким образом (2,1) и (1,2) являются эффективными дубликатами, но оба могут использоваться по одному и тому же пути.
Вводя столбец leaf, который сохраняет фактическую конечную точку каждого шага.
WITH RECURSIVE graph AS (
SELECT CASE WHEN parent = 1 THEN child ELSE parent END AS leaf
,ARRAY[ROW(parent, child)] AS path
,0 AS depth
FROM ownership
WHERE 1 in (child, parent)
UNION ALL
SELECT CASE WHEN o.parent = g.leaf THEN o.child ELSE o.parent END -- AS leaf
,path || ROW(o.parent, o.child) -- AS path
,depth + 1 -- AS depth
FROM graph g
JOIN ownership o ON g.leaf in (o.parent, o.child)
AND ROW(o.parent, o.child) <> ALL(path)
)
SELECT *
FROM graph
