sql - 检测递归 CTE 中的重复项目

Question

我的数据库中存储了一组依赖项。我正在寻找直接或间接依赖于当前对象的所有对象。由于对象可以依赖零个或多个其他对象，因此对象 1 被对象 9 依赖两次是完全合理的(9 依赖于 4 和 5，两者都依赖于 1)。我想获取依赖于当前对象的所有对象的列表而不重复。

如果有循环，这会变得更复杂。如果没有循环，可以使用 DISTINCT，尽管不止一次地通过长链只是为了在最后剔除它们仍然是一个问题。然而，对于循环，递归 CTE 不与它已经看到的东西联合变得很重要。

到目前为止，我所拥有的是这样的:

WITH RECURSIVE __dependents AS (
  SELECT object, array[object.id] AS seen_objects
  FROM immediate_object_dependents(_objectid) object
  UNION ALL
  SELECT object, d.seen_objects || object.id
  FROM __dependents d
  JOIN immediate_object_dependents((d.object).id) object
    ON object.id <> ALL (d.seen_objects)
) SELECT (object).* FROM __dependents;

(它在存储过程中，所以我可以传入 _objectid )

不幸的是，当我之前在当前链中看到它时，这只是省略了一个给定的对象，如果递归 CTE 是深度优先的，这会很好，但当它是广度优先时，它就会出现问题。

理想情况下，解决方案应使用 SQL 而不是 PLPGSQL，但两者都可行。

例如，我在 postgres 中设置了它:

create table objectdependencies (
  id int,
  dependson int
);

create index on objectdependencies (dependson);

insert into objectdependencies values (1, 2), (1, 4), (2, 3), (2, 4), (3, 4);

然后我试着运行这个:

with recursive rdeps as (
  select dep
  from objectdependencies dep
  where dep.dependson = 4 -- starting point
  union all
  select dep
  from objectdependencies dep
  join rdeps r
    on (r.dep).id = dep.dependson
) select (dep).id from rdeps;

我期望输出“1、2、3”。

但是，这种情况不知何故会永远持续下去(我也不明白)。如果我添加 level检查( select dep, 0 as level , ... select dep, level + 1 , on ... and level < 3 )，我看到 2 和 3 重复。相反，如果我添加一个可见支票:

with recursive rdeps as (
  select dep, array[id] as seen
  from objectdependencies dep
  where dep.dependson = 4 -- starting point
  union all
  select dep, r.seen || dep.id
  from objectdependencies dep
  join rdeps r
    on (r.dep).id = dep.dependson and dep.id <> ALL (r.seen)
) select (dep).id from rdeps;

然后我得到 1、2、3、2、3，它停止了。我可以使用 DISTINCT在外部选择中，但这只能合理地处理此数据，因为没有循环。有了更大的数据集和更多的循环，我们将继续增加 CTE 的输出，只是为了让 DISTINCT 削减它。我希望 CTE 在已经在其他地方看到该特定值时简单地停止该分支。

编辑:这不仅仅是关于循环检测(尽管可能存在循环)。它是关于直接和间接地揭示该对象引用的所有内容。所以如果我们有 1->2->3->5->6->7 和 2->4->5，我们可以从 1 开始，到 2，从那里我们可以到 3 和 4，两者这些分支中的一个将转到 5，但我不需要两个分支都这样做 - 第一个可以转到 5，另一个可以简单地停在那里。然后我们继续进行 6 和 7。大多数循环检测将找不到循环并返回 5、6、7 两次。考虑到我希望我的大部分生产数据有 0-3 个直接引用，而且其中大部分也是如此，从一个对象到另一个对象有多个分支是很常见的，并且沿着这些分支向下不会这不仅是多余的，而且是对时间和资源的巨大浪费。

Answer 1

第二个查询(在 union 之后)中的单词 dep 有歧义。实际上它被解释为 rdeps 的列，而不是 objectdependencies.

的别名

with recursive rdeps as (
  select dep
  from objectdependencies dep
  where dep.dependson = 4 -- starting point
  union all
  select dep -- this means r.dep
  from objectdependencies dep
  join rdeps r
    on (r.dep).id = dep.dependson
) select (dep).id from rdeps;

这就是查询创建无限循环的原因。您可以通过更改别名来纠正此问题:

with recursive rdeps as (
  select dep
  from objectdependencies dep
  where dep.dependson = 4 -- starting point
  union all
  select objectdep
  from objectdependencies objectdep
  join rdeps r
    on (r.dep).id = objectdep.dependson
) select (dep).id from rdeps;

 id 
----
  1
  2
  3
  1
  2
  1
(6 rows)    

或者更好，只是使用列，就像上帝的意图一样:

with recursive rdeps as (
    select id, dependson
    from objectdependencies
    where dependson = 4
union all
    select d.id, d.dependson
    from objectdependencies d
    join rdeps r
    on r.id = d.dependson
) 
select *
from rdeps;

问题中的第一个查询是您可以在普通 sql 中执行的所有操作，因为递归查询生成的不同(并行)分支之间没有通信。在功能方法中，您可以使用临时表作为所有分支机构通用的存储。该函数可能如下所示:

create or replace function rec_function(int)
returns void language plpgsql as $$
declare
    i int;
begin
    for i in
        select id
        from objectdependencies
        where dependson = $1
    loop
        if not exists(
            select from temp_table 
            where id = i)
        then
            insert into temp_table values(i);
            perform rec_function(i);
        end if;
    end loop;
end $$;

用法:

create temp table temp_table(id int);

select rec_function(4);

select *
from temp_table;