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

发布时间：2021-01-24 23:53:55 所属栏目：MsSql教程来源：网络整理

导读：我需要您关于访问存储在数据库中的有向图的帮助. 请考虑以下有向图 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)

副标题[/!--empirenews.page--]

我需要您关于访问存储在数据库中的有向图的帮助.

请考虑以下有向图

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,3);
insert into ownership (parent,child) values (3,1);

我想提取从节点可到达的图形的所有半连接边缘(即忽略方向的连接边缘).即,如果我从parent = 1开始,我想得到以下输出

1,2
2,1
2,3
3,1

我正在使用postgresql.

我已经修改了example on Postgres’ manual,它解释了递归查询,并且我已经调整了连接条件以“向上”和“向下”(这样做我忽略了方向).我的查询如下：

c test

WITH RECURSIVE graph(parent,child,path,depth,cycle) AS (
SELECT o.parent,o.child,ARRAY[ROW(o.parent,o.child)],false
    from ownership o
    where o.parent = 1
UNION ALL
SELECT 
    o.parent,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,3)"}                 | f
      3 |     1 | {"(1,"(3,1)"}                 | f
      1 |     2 | {"(1,1)","(1,2)"}         | t
      1 |     2 | {"(1,3)",2)"}         | t
      3 |     1 | {"(1,1)"}         | f
      1 |     2 | {"(1,2)"}         | t
      2 |     3 | {"(1,3)"}         | f
      1 |     2 | {"(1,2)"} | t
      2 |     3 | {"(1,3)"} | t
      1 |     2 | {"(1,2)"} | t
      3 |     1 | {"(1,1)"} | t
(13 rows)

我有一个问题：查询多次提取相同的边,因为它们通过不同的路径到达,我想避免这种情况.如果我将外部查询修改为

select  distinct g.parent,g.child from graph

我有所需的结果,但在WITH查询中仍然存在效率低下,因为不需要的连接已完成.
那么,有没有一种解决方案可以从一个给定的数据库中提取数据库中可到达的边缘,而不使用不同的？

我还有另一个问题(这个问题已解决,请查看底部)：正如您从输出中看到的那样,循环仅在第二次到达节点时停止.即我有(1,2)(2,3)(1,2).
我想在再次循环最后一个节点之前停止循环,即具有(1,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)<>任何(路径))应该避免循环再次进入循环边缘但是不起作用).如何在关闭循环的节点之前停止循环一次？

编辑：正如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,但我仍然有重复,所以提取所有边缘而没有重复且没有明显的主要(第一个)问题仍然存在.当前输出有和不是ROW

parent | child |           path            | cycle 
--------+-------+---------------------------+-------
      1 |     2 | {"(1,2)"}                 | f
      2 |     1 | {"(1,1)"}         | f
      2 |     3 | {"(1,3)"}         | f
      3 |     1 | {"(1,1)"}         | f
      3 |     1 | {"(1,1)"} | f
      2 |     3 | {"(1,3)"} | f
(6 rows)

编辑#2 ::遵循Erwin Brandstetter的建议,我修改了我的查询,但是如果我没有错,建议的查询会提供比我更多的行(ROW比较仍然存在,因为它对我来说似乎更清楚,即使我理解字符串比较会更有效率).
使用新查询,我获得20行,而我的获得6行

WITH RECURSIVE graph(parent,depth) AS (
SELECT o.parent,0
    from ownership o
    where 1 in (o.child,o.parent)
UNION ALL
SELECT 
    o.parent,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,1),从而缺少应包含在其中的行(2,1).结果在概念上算法意味着((2,1)是“接近”(3,1))

当我尝试在Postgresql手册中修改示例时,我正好尝试加入所有权的父母和孩子,但我错了没有保存必须在每个步骤中加入的图的值.

这些类型的查询似乎根据起始节点生成不同的行集(即,取决于在基本步骤中选择的行集).因此,我认为在基本步骤中只选择包含起始节点的一行可能很有用,因为无论如何您将获得任何其他“相邻”节点.

解决方法

可以像这样工作：

WITH RECURSIVE graph AS (
    SELECT parent,',' || parent::text || ',' || child::text || ',' AS path,0 AS depth
    FROM   ownership
    WHERE  parent = 1

    UNION ALL
    SELECT o.parent,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

你提到了性能,所以我在这个方向上进行了优化.

主要观点：

>仅在定义的方向上遍历图形.
>不需要列循环,而是将其作为排除条件.少走一步.这也是直接答案：

How can I do to stop cycles one step before the node that closes the
cycle?

（编辑：东莞站长网）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!

1/3

尾页