sql - 父子 SQL 递归

Question

我见过类似但不完全相同的请求。

如果我有下表

Parent  Child
1       2
1       3
4       3
5       1
6       1
5       7
8       9

我选择了“1”我希望返回所有记录，其中一个是父项或子项，还有所有相关的父项和子项，例如行“5、7”，因为 5 是“1”的父项

因此 1 的结果集将是

Parent  Child
1       2
1       3
4       3
5       1
6       1
5       7

所以它会不包含行

Parent  Child
8       9

这是我能做到的最接近的了

;WITH LinksDown AS (
   SELECT *
   FROM RecursiveTable
   WHERE Parent = 1
   UNION ALL
   SELECT rt.*
   FROM RecursiveTable rt
   JOIN LinksDown ld on ld.Child = rt.Parent
),

LinksUp AS (
   SELECT *
   FROM RecursiveTable
   WHERE Child = 1
   UNION ALL
   SELECT rt.*
   FROM RecursiveTable rt
   JOIN LinksUp lu on lu.Child = rt.Parent
) 

select distinct *
from LinksDown

Union All 
select distinct * from LinksUp

但这有以下输出，远非所需

Parent  Child
1       2
1       3
1       2
1       3
5       1
6       1

Answer 1

这里有两种方法。第一个使用效率很低的 CTE。问题是在递归期间，您无法检查结果集中的所有其他行。虽然您可以构建对给定行有贡献的行的列表，但您无法检查是否已通过另一条路径到达该行。第二种方法使用循环一次一步地用关系填充表。这是一种比 CTE 更好的方法。

留给读者练习:这两种方法是否会在“树”中存在循环时终止，例如1 > 2 > 3 > 1？

-- Sample data.
declare @RecursiveTable as Table ( Parent Int, Child Int );
insert into @RecursiveTable ( Parent, Child ) values
  ( 1, 2 ), ( 1, 3 ),
  ( 4, 3 ),
  ( 5, 1 ),
  ( 6, 1 ),
  ( 5, 7 ),
  ( 8, 9 );
select * from @RecursiveTable;

-- Walk the tree with a recursive CTE.
--   NB: This is woefully inefficient since we cannot promptly detect
--   rows that have already been processed.
declare @Start as Int = 1;
with Pairs as (
  select Parent, Child, Cast( Parent as VarChar(10) ) + '/' + Cast( Child as VarChar(10) ) as Pair
    from @RecursiveTable ),
 Relations as (
  select Parent, Child, Cast( '|' + Pair + '|' as VarChar(1024) ) as Path
    from Pairs
    where Parent = @Start or Child = @Start
  union all
  select P.Parent, P.Child, Cast( R.Path + P.Pair + '|' as VarChar(1024) )
    from Relations as R inner join
      Pairs as P on P.Child = R.Parent or P.Parent = R.Child or
        P.Child = R.Child or P.Parent = R.Parent
    where CharIndex( '|' + P.Pair + '|', R.Path ) = 0
  )
  -- To see how terrible this is, try: select * from Relations
  select distinct Parent, Child
    from Relations
    order by Parent, Child;

-- Try again a loop to add relations to a working table.
declare @Relations as Table ( Parent Int, Child Int );
insert into @Relations
  select Parent, Child
    from @RecursiveTable
    where Parent = @Start or Child = @Start;
while @@RowCount > 0
  insert into @Relations
    select RT.Parent, RT.Child
      from @Relations as R inner join
        @RecursiveTable as RT on RT.Child = R.Child or RT.Parent = R.Parent or
          RT.Child = R.Parent or RT.Parent = R.Child
    except
    select Parent, Child
      from @Relations;
select Parent, Child
  from @Relations
  order by Parent, Child;