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

Question

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

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

... 将由 table 描述，如下所示。注意：我无法更改此格式。

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

这里是示例 table 定义和数据：

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 只有它自己
它的 parent，id 3 将有 3 和 6 的后代
它的 parent，id 1 将有 1、3 和 6 的后代

我将使用此数据在层次结构的每个级别提供 roll-up 计算。这很好用，假设我可以得到上面的数据集。

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

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

其他详细信息："real" 层次结构将比示例大得多。它在技术上可以有无限的深度，但实际上它很少超过 10 级深度。

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

Answer 1

我不确定这是否表现更好，甚至在所有情况下都能产生正确的结果，但您可以捕获一个节点列表，然后使用 xml 功能来解析它并交叉应用于ID 列表：

declare @test int = 6;

;WITH cte AS (SELECT id, parentid, CAST(id AS VARCHAR(MAX)) as IDlist
              FROM HiearchyTest
              WHERE isleaf = 1
              UNION ALL
              SELECT h.id, h.parentid , CAST(CONCAT(c.IDlist,',',h.id) AS VARCHAR(MAX))
              FROM HiearchyTest as h
              JOIN cte as c 
                ON  h.id = c.parentid
            )
    ,cte2 AS (SELECT *, CAST ('<M>' + REPLACE(IDlist, ',', '</M><M>') + '</M>' AS XML) AS Data 
              FROM cte
              WHERE IDlist LIKE '%'+CAST(@test AS VARCHAR(50))+'%'
              )
SELECT id,Split.a.value('.', 'VARCHAR(100)') AS descendentid
FROM cte2 a
CROSS APPLY Data.nodes ('/M') AS Split(a);

Answer 2

好吧，这一直困扰着我，因为我已经阅读了这个问题，我只是回过头来再次思考它......不管怎样，你为什么需要递归回去得到所有的后代？您要求的是祖先而不是后代，并且您的结果集没有尝试获取其他兄弟姐妹、grand children 等。在这种情况下，它得到的是 parent 和 grand parent。您的第一个 cte 为您提供了您需要知道的一切，除非祖先 ID 也是 parentid。因此，使用 union all，设置原始祖先的小魔法，您无需第二次递归即可获得所需的一切。

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

)

, cteAncestors AS (

    SELECT DISTINCT
       id = IIF(parentid IS NULL, @Test, id)
       ,parentid = IIF(parentid IS NULL,id,parentid)
    FROM
       cte
    WHERE
       terminalid = @test

    UNION

    SELECT DISTINCT
       id
       ,parentid = id
    FROM
       cte
    WHERE
       terminalid = @test
) 

SELECT
    id = parentid
    ,DecendentId = id
FROM
    cteAncestors
ORDER BY
    id
    ,DecendentId

你的第一个 cte 的结果集给你你的 2 ancestors 和与他们 ancestor 相关的自我，除了 parentid is null。 null 是一个特例，我会在一分钟内处理。

请记住，此时您的查询生成的是 Ancestors 而不是 descendants，但它没有给您的是自我引用，意思是 grandparent = grandparent、parent = parent、self = self。但是你要做的就是为每个 id 添加行并使 parentid 等于它们的 id。因此 union。现在您的结果集几乎完全成形了：

null parentid的特例。因此 null parentid 标识 originating ancestor 意味着 ancestor 在您的数据集中没有其他 ancestor。以下是您将如何利用它来发挥自己的优势。因为您在 leaf level 开始了初始递归，所以与您开始与 originating ancestor 的 id 没有直接联系，但在其他所有级别都有，只需劫持 null parent id 并翻转值，你现在有了你的叶子的祖先。

最后，如果您希望它成为后代，table 切换列，您就完成了。最后一个音符 DISTINCT 是为了防止 id 与额外的 parentid 重复。例如。 6 | 3 和 6 | 4

的另一条记录

Answer 3

因为你的数据是树状结构，我们可以使用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;

接下来，我写了一个 table 值函数：

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 的很多好处（您要么必须在 table 旁边保持最新状态，要么生成它每次）。但是你去吧。

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

SQL Hierarchy - Resolve full path for all ancestors of a given node

sql

sql-server

common-table-expression

hierarchical-data

sql-server-2014