20

考虑以下简单的 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 将被捕获两次，即使使用建议的谓词。:(

4

6 回答 6

8

CTE's 是递归的。

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

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

(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.

于 2009-05-06T13:26:16.153 回答
7

这是我使用的方法。它已针对多种方法进行了测试，并且性能最高。它结合了 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
于 2010-03-18T07:27:07.187 回答
1

您是否碰巧知道两条边中的哪一条在树的更深层次上？因为在这种情况下，您可以将 edge3->4设为锚成员并开始沿着树向上走，直到找到 edge 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
于 2009-05-06T13:27:07.620 回答
1

（我不是图表专家，只是探索了一下）

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'
于 2009-05-06T14:24:31.600 回答
1

这是你想做的吗？

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 中不受支持）。支持我的方法，对原始方法的唯一更改是在递归成员中的谓词中，以排除在您的起始集中明确存在的递归向下路径。我只添加了 table 变量，以便您在一个位置定义起始 parent_ids，您可以轻松地将此谓词与原始查询一起使用：

where foo.child_id not in (1,3)
于 2009-05-06T14:25:10.413 回答
1

编辑——这根本不起作用。这是一种停止追逐三角形路线的方法。它没有做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

或类似的。抱歉，太晚了，我无法测试它。我会在星期一早上检查。这必须归功于彼得拉尔森（比索）

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

于 2011-03-11T23:48:36.987 回答