检测递归CTE中的重复项

Question

我有一组存储在我的数据库中的依赖项.我希望找到所有依赖于当前对象的对象,无论是直接还是间接.由于对象可以依赖于零个或多个其他对象,因此对象1依赖于对象9两次(9取决于4和5,两者都取决于1)是完全合理的.我想得到所有依赖于当前对象的对象的列表而不重复.

如果有循环,这会变得更复杂.没有循环,可以使用DISTINCT,虽然不止一次只通过长链来剔除它们仍然是一个问题.然而,对于循环,RECURSIVE 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

dep第二个查询(之后union)中的单词不明确.实际上它被解释为列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;

Answer 2

您可以使用 tablefunc 模块中存在的 connectby 函数。

首先您需要启用该模块

CREATE EXTENSION tablefunc;

然后您可以使用 connectby 函数（根据您在问题中提供的示例表，如下所示）：

SELECT distinct id
FROM connectby('objectdependencies', 'id', 'dependson', '4', 0)
AS t(id int, dependson int, level int)
where id != 4;

这将返回：1 2 3

以下是文档中参数的解释：

connectby(text relname, text keyid_fld, text parent_keyid_fld
          [, text orderby_fld ], text start_with, int max_depth
          [, text branch_delim ])

• relname 源关系的名称
• keyid_fld 关键字段的名称
• Parent_keyid_fld 父键字段的名称
• orderby_fld 用于对兄弟排序的字段名称（可选）
• start_with 开始行的键值
• max_depth 下降到的最大深度，或为零表示无限深度
• branch_delim 用于分隔分支输出中的键的字符串（可选）

请查阅文档以获取更多信息。 https://www.postgresql.org/docs/9.5/static/tablefunc.html