Посещение ориентированного графа, как если бы оно было ненаправленным, с использованием рекурсивного запроса

Question

Посещение ориентированного графа, как если бы оно было ненаправленным, с использованием рекурсивного запроса

Мне нужна ваша помощь о посещении ориентированного графа, хранящегося в базе данных.

Рассмотрим следующий ориентированный граф

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)

Изменить # 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 это должно было быть объединено в каждом шаге.

Эти типы запросов, кажется, генерируют различный набор строк в зависимости от начального узла (то есть в зависимости от набора строк, выбранных на базовом шаге). Поэтому я думаю, что было бы полезно выбрать только одну строку, содержащую начальный узел в базовом шаге, так как в любом случае вы получите любой другой "соседний" узел.

12

sql postgresql recursion graph common-table-expression

Источник

user472317 06 янв '12 в 21:22

1 ответ

Решение

Другие вопросы по тегам sql postgresql recursion graph common-table-expression

user939860 06 янв '12 в 22:58 2012-01-06 22:58 · Accepted Answer · 2012-01-06 22:58

Может работать так:

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 вместо этого сделайте это условием исключения. Еще один шаг впереди. Это также прямой ответ на:

Как я могу сделать, чтобы остановить цикл за один шаг до узла, который закрывает цикл?

Используйте строку для записи пути. Меньше и быстрее, чем массив строк. Все еще содержит всю необходимую информацию. Может измениться с очень большой 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