使用递归查询访问有向图，就好像它是无向图一样

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手册中解释递归查询的示例，并将联接条件调整为"向上"one_answers"向下"（这样做我忽略了指示）。我的问题如下：

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查询仍然效率低下，因为完成了不必要的联接。那么，有没有一种解决方案可以从给定的边开始提取数据库中图的可达边，而不使用distinct

我还有另一个问题（这个问题已经解决了，看看底部）：正如你从输出中看到的，只有当第二次到达节点时，循环才会停止。即我有(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)）在再次访问已循环的边缘之前应该避免循环，但不起作用）如何在关闭循环的节点前一步停止循环

编辑：正如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：：按照Erwin Brandstetter的建议，我修改了我的查询，但如果我没有错的话，建议的查询给出的行数比我的多（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：因此，正如Erwin Brandstetter所指出的，上一个查询仍然是错误的，而在他的回答中可以找到正确的查询。

当我发布第一个查询时，我还没有意识到我缺少了一些联接，就像下面的情况一样：如果我从节点3开始，db会选择行(2,3)和(3,1)。然后，查询的第一个归纳步骤将从这些行中选择(1,2)、(2,3)和(3,1)行，忽略应该包括在结果中的行（2,1），这在概念上是算法所暗示的（(2,1)"接近"(3,1)）

当我尝试调整Postgresql手册中的示例时，我尝试连接ownership的父级和子级是正确的，但我没有保存每个步骤中必须连接的graph的值是错误的。

这些类型的查询似乎会根据起始节点生成不同的行集（即，根据在基本步骤中选择的行集）。因此，我认为在基本步骤中只选择一行包含起始节点可能很有用，因为无论如何都会得到任何其他"相邻"节点。

Answer 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，而是将其作为排除条件。少走一步。这也是的直接答案

如何在关闭的节点前一步停止循环周期

• 使用字符串来记录路径。比行数组更小、更快。仍然包含所有必要的信息。不过，可能会随着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)

并且两行CCD_ 22和CCD_。。。

---

评论后的其他解决方案

• 忽略方向
• 仍然每条路只走一次边
• 使用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