我需要你关于数据库中存储的有向图的访问方面的帮助。
考虑以下有向图：
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查询中仍存在低效率，因为进行了不必要的连接。 那么，是否有一种方法可以从给定的起始点开始，在数据库中提取图的可达边缘，而不使用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))应该在再次进入环之前避免循环，但实际上并没有起作用)。如何在到达关闭循环的节点之前停止循环一步？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
第三次编辑: 正如Erwin Brandstetter所指出的那样，最后一个查询仍然是错误的，而正确的查询可以在他的回答中找到。
当我发布我的第一个查询时，我没有意识到我缺少一些连接，就像在以下情况下发生的那样：如果我从节点3开始，数据库会选择行(2,3)和(3,1)。然后，查询的第一个归纳步骤将选择连接这些行的行(1,2)、(2,3)和(3,1)，错过了应该作为概念上算法暗示的结果包含的行(2,1)（ (2,1)“接近”(3,1)）。
当我试图调整Postgresql手册中的示例时，我尝试连接ownership的父级和子级，但我没有保存必须在每个步骤中连接的graph的值。
这些类型的查询似乎会生成不同的行集，具体取决于起始节点（即基本步骤中选择的行集）。因此，我认为在基本步骤中选择只包含起始节点的一行可能很有用，因为无论如何都会得到任何其他“相邻”的节点。
and NOT (ROW(o.parent, o.child) = any(path))吗？这难道不足以满足需求了吗：select distinct g.parent, g.child from graph g where cycle = f？ - dani herrera(ROW(o.parent, o.child) <> ALL(path))而不是NOT (ROW(o.parent, o.child) = ANY(path))。 - Erwin Brandstetter