sql - 防止递归 CTE 多次访问节点

Question

考虑以下简单的 DAG:

  1->2->3->4

还有一个表#bar，描述了这一点(我使用的是 SQL Server 2005):

parent_id   child_id
1           2
2           3
3           4
//... other edges, not connected to the subgraph above

现在想象我有一些其他任意标准来选择第一个和最后一个边缘，即 1->2 和 3->4。我想用它们来查找图表的其余部分。

我可以按如下方式编写递归 CTE(我使用 MSDN 中的术语):

with foo(parent_id,child_id) as (
// anchor member that happens to select first and last edges:
select parent_id,child_id from #bar where parent_id in (1,3)
union all
// recursive member:
select #bar.* from #bar
join foo on #bar.parent_id = foo.child_id
)
select parent_id,child_id from foo

但是，这会导致边 3->4 被选择两次:

parent_id  child_id
1          2
3          4
2          3
3          4    // 2nd appearance!

如何防止查询递归到已经描述过的子图中？如果在查询的“递归成员”部分中，我可以引用到目前为止递归 CTE 检索到的所有数据(并提供一个谓词，指示递归成员中不包括已访问过的节点)。但是，我认为我只能访问递归成员的最后一次迭代返回的数据。

当存在大量此类重复时，这将无法很好地扩展。有没有办法防止这种不必要的额外递归？

请注意，我可以在语句的最后一行使用“select unique”来实现所需的结果，但这似乎是在所有(重复)递归完成之后应用的，所以我我认为这不是一个理想的解决方案。

编辑 - hainstech 建议通过添加谓词来排除显式在起始集中的递归向下路径来停止递归，即仅递归其中 foo.child_id 不在 (1,3) 中。这适用于上述情况，只是因为它很简单 - 所有重复部分都从 anchor 节点集开始。它不能解决通常情况下可能无法解决的问题。例如，考虑将边 1->4 和 4->5 添加到上述集合中。即使使用建议的谓词，边 4->5 将被捕获两次。 :(

Answer 1

CTE 是递归的。

当您的 CTE 具有多个初始条件时，这意味着它们也具有不同的递归堆栈，并且无法在另一个堆栈中使用一个堆栈中的信息。

在您的示例中，递归堆栈将如下所示:

(1) - first IN condition
(1, 2)
(1, 2, 3)
(1, 2, 3, 4)
(1, 2, 3) - no more children
(1, 2) - no more children
(1) - no more children, going to second IN condition

(3) - second condition
(3, 4)
(3) - no more children, returning

如您所见，这些递归堆栈不相交。

您可能可以将访问过的值记录在临时表中，将每个值与临时表JOIN，并且如果找到该值，则不遵循该值，但是SQL Server会这样做不支持这些东西。

所以你只需使用SELECT DISTINCT。