多次阻止递归CTE访问节点

6 回答

• 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
  

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

  您可以将访问的值记录在临时表中，每个值都带有temptable，并且如果找到它则不遵循此值，但 SQL Server 不支持这些内容 .

  所以你只需使用 SELECT DISTINCT .

  回复于 2024-04-27T06:31:52+08:00
• 4

  这是我使用的方法 . 它已针对几种方法进行了测试，性能最佳 . 它结合了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
  

  回复于 2024-04-27T06:31:52+08:00
• 0

  你碰巧知道这两个边缘中哪一个在树的更深层次上？因为在这种情况下，你可以使边缘 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
  

  回复于 2024-04-27T06:31:52+08:00
• 7

  这是你想要做的吗？

  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_id，您可以很容易地将此谓词与原始查询一起使用：

  where foo.child_id not in (1,3)
  

  回复于 2024-04-27T06:31:52+08:00
• 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
  

  或类似的 . 对不起，现在已经很晚了，我无法测试 . 我会在星期一早上检查 . 对此必须归功于Peter Larsson（比索）

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

  回复于 2024-04-27T06:31:52+08:00
• 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'
  

  回复于 2024-04-27T06:31:52+08:00