防止递归CTE多次访问节点

Question

考虑以下简单的有向无环图：

  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也将被捕获两次。:(

- bacar

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。

- Quassnoi

---

我只有一个初始条件，但它可以选择多行。你有没有任何文件链接说明每一行都是独立堆栈处理的？（我认为我可以使用自己的临时表来模拟所需的效果-尚未尝试过）我没有足够的“声望”来投票支持你的答案 >:( - bacar

啊哈，我在评论时你修改了答案，建议使用临时表 :) - bacar

Answer 2

这是我使用的方法。它已经被测试过多种方法，并且是最高效的。它结合了Quassnoi建议的临时表思想和使用distinct和left join来消除递归中冗余路径。递归的级别也包括在内。

我将失败的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

- Laramie

---

太棒了，易于理解，运行速度快！谢谢！ - BD.

使用此查询可以实现超快速执行。帮助我将存储过程的时间从2分钟缩短到不到1秒。我知道这不是“如何使用CTE”这个问题的答案，但如果您愿意放弃CTE递归，这是一个非常高效的解决方案。 - Smitty

Answer 3

编辑——这根本不起作用。这是一种停止追踪三角形路线的方法。它不符合OP的要求。

或者，您可以使用递归令牌分隔字符串。

我在家里用笔记本电脑（没有SQL服务器），所以可能不完全正确，但是我尝试了一下.....

; WITH NodeNetwork AS (
  -- Anchor Definition
  SELECT
     b.[parent_Id] AS [Parent_ID]
     , b.[child_Id] AS [Child_ID]
     , CAST(b.[Parent_Id] AS VARCHAR(MAX)) AS [NodePath]
  FROM
     #bar AS b

  -- Recursive Definition
  UNION ALL SELECT
     b.[Parent_Id]
     , b.[child_Id]
     , CAST(nn.[NodePath] + '-' + CAST(b.[Parent_Id] AS VARCHAR(MAX)) AS VARCHAR(MAX))
  FROM
     NodeNetwork AS nn
     JOIN #bar AS b ON b.[Parent_Id] = nn.[Child_ID]
  WHERE
     nn.[NodePath] NOT LIKE '%[-]' + CAST(b.[Parent_Id] AS VARCHAR(MAX)) + '%'
  )
  SELECT * FROM NodeNetwork

或类似的。抱歉太晚了，我无法测试它。我会在周一早上检查。这个想法要归功于Peter Larsson（Peso）。

这个想法是在这里产生的： http://www.sqlteam.com/forums/topic.asp?TOPIC_ID=115290

- Transact Charlie

---

我不确定这是什么意思。实际上，它选择了边缘3->4三次，而不是两次！（我只想要一次）。它还选择了2->3两次。它也没有应用原始的“任意标准”（其中parent_id在（1,3）中）。如果我添加它，它会给出与我在最初的问题陈述中得到的相同结果。 - bacar

就编程而言，以下内容翻译成中文。仅返回翻译后的文本：（FWIW-考虑到@Quassnoi的答案/评论是正确的，我不认为仅使用递归CTE的任何解决方案都能解决问题，无论你如何在其中操作数据。） - bacar

是的，你说得对。这将阻止你追踪三角形路线（如果你有某个条目，其中一个子项指向自己的父项或祖父项）。但它并没有真正回答你的问题。 - Transact Charlie

Answer 4

你知道这两条边在树中哪一条更深吗？如果是这样，你可以将边3->4作为锚定成员，并开始沿着树向上走，直到找到边1->2。

就像这样：

with foo(parent_id, child_id)
as
(
    select parent_id, child_id
    from #bar
    where parent_id = 3

    union all

    select parent_id, child_id
    from #bar b
    inner join foo f on b.child_id = f.parent_id
    where b.parent_id <> 1
)
select *
from foo

- Ronald Wildenberg

---

很抱歉，我不知道。通常我甚至不知道初始查询中选择的边缘是否属于同一个整体图形，:( 谢谢！ - bacar

Answer 5

（我不是图表方面的专家，只是在探索一下）

DISTINCT 保证每行都是唯一的，但它不会消除不以您的最后一个边缘结束的图形路线。看这个图：

insert into #bar (parent_id,child_id) values (1,2)
insert into #bar (parent_id,child_id) values (1,5)
insert into #bar (parent_id,child_id) values (2,3)
insert into #bar (parent_id,child_id) values (2,6)
insert into #bar (parent_id,child_id) values (6,4)

查询结果中包括(1,5)，但该点并非从第一条边(1,2)到最后一条边(6,4)的路径。

你可以尝试类似以下的方法，只查找以(1,2)开头以及以(6,4)结尾的路径：

with foo(parent_id, child_id, route) as (
    select parent_id, child_id, 
        cast(cast(parent_id as varchar) + 
        cast(child_id as varchar) as varchar(128))
    from #bar
    union all
    select #bar.parent_id, #bar.child_id, 
        cast(route + cast(#bar.child_id as varchar) as varchar(128)) 
    from #bar
    join foo on #bar.parent_id = foo.child_id
)
select * from foo where route like '12%64'

- Andomar

---

我不想排除那些没有以我的“最后”边缘结束的路由（我想要与锚点指定的任何边缘相连的所有内容）- 但我同意这是一个有趣的（单独的）问题 :) - bacar

如果你添加(6,1)，那算作连接吗？ - Andomar

是的，但是那样会变得循环，你就需要担心一系列其他问题了 :) - bacar

（请注意，能够跟踪您已经访问过的节点实际上有助于避免在循环图中无限循环！） - bacar

哦，对了！抱歉。那么不，我不想选择那个。抱歉，我的术语有些松散 - 我只想选择初始节点集“下游”的子图。 - bacar

Answer 6

这是你想要做的吗？

create table #bar (parent_id int, child_id int)
insert #bar values (1,2)
insert #bar values (2,3)
insert #bar values (3,4)

declare @start_node table (parent_id int)
insert @start_node values (1)
insert @start_node values (3)

;with foo(parent_id,child_id) as (
    select
        parent_id
        ,child_id
    from #bar where parent_id in (select parent_id from @start_node)

    union all

    select
        #bar.*
    from #bar
        join foo on #bar.parent_id = foo.child_id
    where foo.child_id not in (select parent_id from @start_node)
)
select parent_id,child_id from foo

编辑 - @bacar - 我认为这不是Quasnoi提出的临时表解决方案。我相信他们建议在每次递归期间基本上复制整个递归成员内容，并将其用作连接以防止重新处理（并且这在ss2k5中不受支持）。我的方法得到了支持，对您原始查询的唯一更改在于递归成员中的谓词，以排除明确包含在起始集中的路径。我只添加了表变量，以便您可以在一个位置定义起始parent_ids，您也可以轻松地使用此谓词与原始查询：

where foo.child_id not in (1,3)

- ahains

---

是的 - 这是Quassnoi建议的“临时表”解决方案的实现。谢谢！ - bacar

好的，我现在明白了 - 这对于所有重复部分都包含在初始集合中的简单情况有效，但它不能防止反复递归到由初始集合共享但不直接包含在其中的其他子图中。例如，请考虑以下图形： insert #bar values (1,2) insert #bar values (2,3) insert #bar values (1,3) insert #bar values (3,4)并且仅有一个初始起始节点为1。您的查询仍将两次选择出边3->4，因为我无法在递归成员部分中将已访问的节点插入表变量（正如您所提到的）。 :( - bacar

@bacar - 感谢您提供的有用示例，您可能希望编辑您的问题以加入它。您无法使用CTE保存任何类型的状态，因此我认为您可能需要采用迭代T-SQL方法或具有CLR的某些方法。 - ahains

完成 - 尽量简单明了，感谢！ - bacar