SQL 层次结构 - 解析给定节点的所有祖先的完整路径

我有一个由邻接列表描述的层次结构。不一定有单个根元素，但我确实有数据来识别层次结构中的叶（终端）项。所以，一个看起来像这样的层次结构......

1
- 2
- - 4
- - - 7
- 3
- - 5
- - 6 
8
- 9

...将通过表格来描述，就像这样。NOTE: 我没有能力改变这种格式。

id  parentid isleaf
--- -------- ------
1   null     0
2   1        0
3   1        0
4   2        0
5   3        1
6   3        1
7   4        1
8   null     0
9   8        1

这是示例表定义和数据：

CREATE TABLE [dbo].[HiearchyTest](
    [id] [int] NOT NULL,
    [parentid] [int] NULL,
    [isleaf] [bit] NOT NULL
)
GO

INSERT [dbo].[HiearchyTest] ([id], [parentid], [isleaf]) VALUES (1, NULL, 0)
INSERT [dbo].[HiearchyTest] ([id], [parentid], [isleaf]) VALUES (2, 1, 0)
INSERT [dbo].[HiearchyTest] ([id], [parentid], [isleaf]) VALUES (3, 1, 0)
INSERT [dbo].[HiearchyTest] ([id], [parentid], [isleaf]) VALUES (4, 2, 0)
INSERT [dbo].[HiearchyTest] ([id], [parentid], [isleaf]) VALUES (5, 3, 1)
INSERT [dbo].[HiearchyTest] ([id], [parentid], [isleaf]) VALUES (6, 3, 1)
INSERT [dbo].[HiearchyTest] ([id], [parentid], [isleaf]) VALUES (7, 4, 1)
INSERT [dbo].[HiearchyTest] ([id], [parentid], [isleaf]) VALUES (8, NULL, 0)
INSERT [dbo].[HiearchyTest] ([id], [parentid], [isleaf]) VALUES (9, 8, 1)
GO

由此，我需要提供任何 id 并获取所有祖先的列表，包括每个祖先的所有后代。所以，如果我提供的输入id = 6，我期望以下内容：

id descendentid
-- ------------
1  1
1  3
1  6
3  3
3  6
6  6

• id 6 只有它自己
• 它的父代 id 3 将有 3 和 6 的后代
• 它的父代 id 1 将有 1、3 和 6 的后代

我将使用这些数据来提供层次结构中每个级别的汇总计算。假设我可以获得上面的数据集，这效果很好。

我使用两个递归 ctes 完成了这一任务 - 一个用于获取层次结构中每个节点的“终端”项。然后，在第二个步骤中，我获得所选节点的完整祖先（因此，6 解析为 6、3、1），然后向上走并获得完整的集合。我希望我遗漏了一些东西，并且这可以在一轮内完成。这是双递归代码示例：

declare @test int = 6;

with cte as (

    -- leaf nodes
    select id, parentid, id as terminalid
    from HiearchyTest
    where isleaf = 1

    union all

    -- walk up - preserve "terminal" item for all levels
    select h.id, h.parentid, c.terminalid
    from HiearchyTest as h
    inner join
    cte as c on h.id = c.parentid

)

, cte2 as (

    -- get all ancestors of our test value
    select id, parentid, id as descendentid
    from cte
    where terminalid = @test 

    union all

    -- and walkup from each to complete the set
    select h.id, h.parentid, c.descendentid
    from HiearchyTest h
    inner join cte2 as c on h.id = c.parentid

)

-- final selection - order by is just for readability of this example
select id, descendentid 
from cte2
order by id, descendentid

附加细节：“真实”层次结构将比示例大得多。从技术上讲，它可以具有无限深度，但实际上它很少会超过 10 层深度。

总之，我的问题是我是否可以使用单个递归 cte 来完成此任务，而不必在层次结构上递归两次。

因为你的数据是树形结构，所以我们可以使用hierarchyid数据类型来满足你的需求（尽管你在评论中说不能）。首先，简单的部分 - 使用递归 cte 生成 Hierarchyid

with cte as (

    select id, parentid, 
       cast(concat('/', id, '/') as varchar(max)) as [path]
    from [dbo].[HiearchyTest]
    where ParentID is null

    union all

    select child.id, child.parentid, 
       cast(concat(parent.[path], child.id, '/') as varchar(max))
    from [dbo].[HiearchyTest] as child
    join cte as parent
        on child.parentid = parent.id
)
select id, parentid, cast([path] as hierarchyid) as [path] 
into h
from cte;

接下来，我编写了一个小表值函数：

create function dbo.GetAllAncestors(@h hierarchyid, @ReturnSelf bit)
returns table
as return
   select @h.GetAncestor(n.n) as h
   from dbo.Numbers as n
   where n.n <= @h.GetLevel()
      or (@ReturnSelf = 1 and n.n = 0)

   union all

   select @h
   where @ReturnSelf = 1;

有了这些，获得你想要的结果集也不算太糟糕：

declare @h hierarchyid;

set @h = (
    select path
    from h
    where id = 6
);

with cte as (
    select * 
    from h
    where [path].IsDescendantOf(@h) = 1
        or @h.IsDescendantOf([path]) = 1
)
select h.id as parent, c.id as descendentid
from cte as c
cross apply dbo.GetAllAncestors([path], 1) as a
join h
    on a.h = h.[path]
order by h.id, c.id;

当然，如果不保留它，您就会错过使用 hierarchyid 的很多好处（您要么必须在边表中保持它最新，要么每次都生成它）。但就这样吧。