多次阻止递归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 distinct"来获得所需的结果,但这似乎在所有(重复)递归完成后应用,因此我认为这不是一个理想的解决方案.

编辑 - 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每个值都包含temptable,如果找到它则不遵循此值,但SQL Server不支持这些值.

所以你只需使用SELECT DISTINCT.

Answer 2

这是我使用的方法.它已针对几种方法进行了测试,性能最佳.它结合了Quassnoi建议的临时表概念以及使用distinct和left连接来消除递归的冗余路径.递归的级别也包括在内.

我在代码中留下了失败的CTE方法,因此您可以比较结果.

如果有人有更好的想法,我很想知道.

create table #bar (unique_id int identity(10,10), parent_id int, child_id int)
insert #bar  (parent_id, child_id)
SELECT 1,2 UNION ALL
SELECT 2,3 UNION ALL
SELECT 3,4 UNION ALL
SELECT 2,5 UNION ALL
SELECT 2,5 UNION ALL
SELECT 5,6

SET NOCOUNT ON

;with foo(unique_id, parent_id,child_id, ord, lvl) as (
    -- anchor member that happens to select first and last edges:
    select unique_id, parent_id, child_id, row_number() over(order by unique_id), 0
    from #bar where parent_id in (1,3)
union all
-- recursive member:
select b.unique_id, b.parent_id, b.child_id, row_number() over(order by b.unique_id), foo.lvl+1
    from #bar b
    join foo on b.parent_id = foo.child_id
)
select unique_id, parent_id,child_id, ord, lvl from foo

/***********************************
    Manual Recursion
***********************************/
Declare @lvl as int
Declare @rows as int
DECLARE @foo as Table(
    unique_id int,
    parent_id int,
    child_id int,
    ord int,
    lvl int)

--Get anchor condition
INSERT @foo (unique_id, parent_id, child_id, ord, lvl)
select unique_id, parent_id, child_id, row_number() over(order by unique_id), 0
    from #bar where parent_id in (1,3)

set @rows=@@ROWCOUNT
set @lvl=0

--Do recursion
WHILE @rows > 0
BEGIN
    set @lvl = @lvl + 1

    INSERT @foo (unique_id, parent_id, child_id, ord, lvl)
    SELECT DISTINCT b.unique_id, b.parent_id, b.child_id, row_number() over(order by b.unique_id), @lvl
    FROM #bar b
     inner join @foo f on b.parent_id = f.child_id
     --might be multiple paths to this recursion so eliminate duplicates
     left join @foo dup on dup.unique_id = b.unique_id
    WHERE f.lvl = @lvl-1 and dup.child_id is null

    set @rows=@@ROWCOUNT 
END

SELECT * from @foo

DROP TABLE #bar