代码之家 › 专栏 › 技术社区 › Tanktalus

检测递归CTE中的重复项

common-table-expression postgresql sql

Tanktalus · 技术社区 · 7 年前

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

如果存在循环,这会变得更复杂。如果没有循环,人们可以使用不同的方法,尽管只通过一次以上的长链在最后剔除它们仍然是一个问题。然而,对于循环,递归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是重复的。相反,如果我添加了一个Seen检查:

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的输出,只会使其明显减少。我希望CTE在其他地方看到这个特定的值时简单地停止这个分支。

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

4 回复 | 直到 7 年前

Developer84ios 7 年前

您可以使用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;

这将返回: 一二三

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

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

源关系的relname名称
关键字字段的关键字名称
父关键字字段的父关键字名称
order by_fld用于对同级排序的字段的名称(可选)
以要开始的行的键值开始
最大深度下降到的最大深度,或无限深度为零
使用分支输出(可选)来分隔键的分支delim字符串

有关更多信息,请参阅文档。 https://www.postgresql.org/docs/9.5/static/tablefunc.html

klin 7 年前

这个词 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中所能做的全部工作,因为递归查询生成的不同(paralel)分支之间没有通信。在函数方法中,可以将临时表用作所有分支的公共存储。函数可能如下所示:

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;

Ivan UstûÅ¾anin 6 年前

我知道这不是一个很古老的问题,但我有点惊讶没有人建议移除 all 来自 union 尽早消除重复。这是一种防止递归CTE结果重复的相当简单的方法,但它确实有自己的警告,这样的结果必须只包括实数字段,也就是说,在执行时不计算。 depth , path 或者别的什么。

将问题中的示例数据与此查询一起使用(从原始数据重新格式化了一点):

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

我明白了 1 , 2 和 3 .

此外,此解决方案还可以防止依赖关系中出现循环时出现无休止的循环。然而,它没有检测到它,因为它没有也不能显示出有一个循环,它只是阻止了一个无休止的循环。

Erfan Mohammadi 7 年前

您可以从此处查找重复值

WITH cte AS (
SELECT ROW_NUMBER()OVER(PARTITION BY [FieldName] ORDER BY [FieldName])[Rank],* 
FROM TableName)
SELECT * 
FROM  cte 
WHERE cte.[Rank]>1