sql – 使用递归查询访问有向图,就好像它是一个无向图
|
副标题[/!--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). 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比较仍然存在,因为它对我来说似乎更清楚,即使我理解字符串比较会更有效率). 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
你提到了性能,所以我在这个方向上进行了优化. 主要观点： >仅在定义的方向上遍历图形.
（编辑：威海站长网） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |
