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

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: :下列哪些欧文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数字改变.

• 使用LIKEoperator(~~)检查循环,应该快得多.

• 如果您不希望在一段时间内有更多的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