在递归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，但我不需要两个分支都可以-
第一个分支可以转到5，而另一个可以停在该位置。然后我们继续进行6和7。大多数循环检测将找不到任何循环，并两次返回5、6、7。考虑到我希望我的大多数生产数据都具有0-3个立即引用，并且大多数情况类似，因此从一个对象到另一个对象有多个分支是很普遍的，而向下跳转这些分支将不会只是多余的，但是浪费大量的时间和资源。

Answer 1

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