Мне нужна ваша помощь о посещении ориентированного графа, хранящегося в базе данных.
Рассмотрим следующий ориентированный граф
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)) следует избегать зацикливания, прежде чем снова перейти на зацикленное ребро, но это не работает). Как я могу остановить цикл за один шаг до того, как узел закроет цикл?
Редактировать : как предложил Данихп, решитьВторая проблема, которую я использовал
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)
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
Редактировать 3 : так, как указал Эрвин Брандштеттер, последний запросвсе еще был неправ, а правильного можно найти в его ответе.
Когда я отправил свой первый запрос, я не понял, что пропустил некоторые объединения, как это происходит в следующем случае: если я начинаю с узла 3, БД выбирает строки (2,3) и(3,1).Затем на первом индуктивном шаге запроса выбираются из этих строк строки (1,2), (2,3) и (3,1), пропущенные строки (2,1), которые должны быть включены в результат, как концептуально алгоритмбудет означать ((2,1) "рядом" (3,1))
Когда я пытался адаптировать пример в руководстве к Postgresql, я был прав, пытаясь соединить родителя и потомка ownership, но я ошибалсяне сохраняйте значение graph, которое нужно было объединять на каждом шаге.
Похоже, что эти типы запросов генерируют различный набор строк в зависимости от начального узла (т.е. в зависимости от набора строк, выбранного вбазовый шаг).Поэтому я думаю, что было бы полезно выбрать только одну строку, содержащую начальный узел в базовом шаге, поскольку в любом случае вы получите любой другой «соседний» узел.