Посещение ориентированного графа, как если бы он был неориентированным, с использованием рекурсивного запроса
Мне нужна ваша помощь по поводу посещения ориентированного графа, хранящегося в базе данных.
Рассмотрим следующий ориентированный граф
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);
Я хотел бы извлечь все полусвязные ребра (т.е. соединенные ребра, игнорирующие направление) графа, достижимые из узла . То есть, если я начну с 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, поскольку будут выполнены ненужные соединения. Итак, есть ли решение для извлечения достижимых ребер графа в базе данных, начиная с заданного, без использования различных?
У меня также есть другая проблема (эта решена, посмотрите на внизу): как видно из выходных данных, циклы останавливаются только при достижении узла во второй раз . Т.е.У меня есть (1,2) (2,3) (1,2) .
Я хотел бы остановить цикл перед повторным циклом по этому последнему узлу, т.е. имеющему (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) ) следует избегать зацикливания перед повторным переходом на зацикленный край, но это не работает). Как я могу сделать, чтобы остановить циклы за один шаг до узла, который закрывает цикл?
Edit : как предложил 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, но у меня все еще есть дубликаты, поэтому основная (первая) проблема извлечения всех ребер без дубликатов и без отличий все еще жива. Текущий вывод с , а не 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)
Edit # 2: : следуя предложению Эрвина Брандштеттера, я изменил свой запрос, но если я не ошибаюсь, предложенный запрос дает БОЛЬШЕ строк, чем мой (сравнение ROW все еще там, как мне кажется более понятным, даже я понимал, что сравнение строк будет более эффективным). Используя новый запрос, я получаю 20 строк, в то время как мой дает 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
Edit 3 : так, как указал Эрвин Брандштеттер, последний запрос все еще был неправильным, а правильный можно найти в его ответе.
Когда я отправил свой первый запрос, я не понял, что мне не хватает некоторых объединений, как это происходит в следующем случае: если я начинаю с узла 3, база данных выбирает строки (2,3 ) и (3,1) .Затем первый индуктивный шаг запроса выберет, объединяя из этих строк, строки (1,2) , (2,3) и (3,1 ) , пропущена строка (2,1), которая должна быть включена в результат, поскольку концептуально алгоритм будет подразумевать ( (2,1) находится «близко» (3,1) )
Когда я пытался адаптировать пример из руководства Postgresql, я был прав, пытаясь объединить родительский и дочерний элемент владельца , но я был неправ, не сохранив значение графика , которые нужно было объединять на каждом шаге.
Этот тип запросов, похоже, генерирует другой набор строк в зависимости от начального узла (т.е. в зависимости от набора строк, выбранных на базовом шаге). Итак, я думаю, что было бы полезно выбрать только одну строку, содержащую начальный узел на базовом шаге, так как вы все равно получите любой другой «соседний» узел.