父子 SQL 递归 [英] Parent Child SQL Recursion
问题描述
我见过类似但不完全相同的请求.
I have seen similar but not Exactly the same requests.
如果我有下表
Parent Child
1 2
1 3
4 3
5 1
6 1
5 7
8 9
我选择了1"我希望返回所有记录,其中一个是父级或子级,但也包括所有相关的父级和子级,例如行5、7",因为 5 是1"的父级
I selected "1" I would expect back all records where one is the parent or child but also all related parents and children for instance row "5 , 7" because 5 is the parent of "1"
所以 1 的结果集将是
so the result set for 1 would be
Parent Child
1 2
1 3
4 3
5 1
6 1
5 7
所以它会不包括行
So it would NOT include the row
Parent Child
8 9
这是我目前所能达到的最接近的
This is as close as I can get so far
;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
但这有以下输出,远非所需
But this has the following output which is far from whats needed
Parent Child
1 2
1 3
1 2
1 3
5 1
6 1
推荐答案
这里有两种方法.第一种使用效率很低的 CTE.问题是在递归期间您无法检查结果集中的所有其他行.虽然您可以构建对给定行有贡献的行的列表,但您无法检查是否已经通过另一条路径到达该行.第二种方法使用循环一步一步地用关系填充表.这是一种比 CTE 更好的方法.
Here are two approaches. The first uses a CTE that is quite inefficient. The problem is that during recursion you cannot examine all of the other rows in the result set. While you can build a list of the rows that have contributed to a given row, you cannot check to see if you already reached that row via another path. The second approach uses a loop to populate a table with relations one step at a time. It is a much better method than the CTE.
留给读者练习:这两种方法是否会在树"中存在循环时终止,例如1 > 2 > 3 > 1?
Left as an exercise for the reader: Will the two methods terminate in the presence of a cycle in the "tree", e.g. 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;
这篇关于父子 SQL 递归的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!