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

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)）在再次进入循环的边缘之前应避免循环，但不起作用）。 如何在关闭循环的节点之前一步停止循环？

编辑 ：作为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的建议，我修改了查询，但是如果我没看错，建议的查询提供的行比我的要多（行比较仍然存在，因为对我来说似乎更清楚，即使我明白了字符串比较会更有效）。使用新查询，我获得了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开始，则数据库选择行(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)

而且这两行(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