防止多次递归CTE访问节点

Question

考虑以下简单的DAG：

  1->2->3->4

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检索到的所有数据
（并在递归成员中提供一个谓词，表示已访问的节点除外），则可以实现此目的。但是，我认为我只能访问递归成员 的最后一次迭代 返回的数据。

当有很多这样的重复时，这将无法很好地扩展。有没有办法防止这种不必要的额外递归？

请注意，我可以在语句的最后一行使用“选择不同”来实现所需的结果，但这似乎在 完成 所有（重复）递归 之后 才应用，因此我认为这不是理想的解决方案。

Edit -hainstech建议通过添加谓词来排除递归在起始集中明确存在的路径（即仅递归）的方式来停止递归where foo.child_id not in (1,3)。这仅对简单情况有效，因为它很简单-所有重复的部分都在节点的锚点集合内开始。它不能解决可能不存在的一般情况。例如，考虑将边线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。