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

Question

我有一个由邻接列表描述的层次结构.没有一个根元素,但我确实有数据来识别层次结构中的叶子(终端)项目.所以,一个看起来像这样的层次......

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

......将用表格来描述,就像这样. 注意:我无法更改此格式.

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就是它自己
• 它的父母,身份3将具有3和6的后代
• 它的父,id 1将具有1,3和6的后瞻

我将使用此数据在层次结构中的每个级别提供汇总计算.假设我可以获得上面的数据集,这很有效.

我已经使用两个recusive ctes完成了这个 - 一个用于获取hiearchy中每个节点的"terminal"项.然后,第二个我获得所选节点的完整祖先(因此,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来完成这个,而不是必须两次递归层次结构.

Answer 1

好吧，自从我读过这个问题以来，这一直困扰着我，我刚刚回来再次想到它......无论如何，为什么你需要递归回去才能得到所有的后代？您要求的是祖先而不是后代，并且您的结果集并不是试图获取其他兄弟姐妹、孙子等。在这种情况下，它是获取父母和祖父母。您的第一个 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您提供了您的 2ancestors和与他们相关的自我，ancestor但原始祖先的情况除外parentid is null。这null是一个特殊情况，我稍后会处理。

请记住，此时您的查询生成Ancestorsnot descendants，但它没有给您提供自我引用，意思是grandparent = grandparent, parent = parent, self = self。但要实现这一点，您所要做的就是为每个添加行id并使parentid它们等于它们id。因此union. 现在你的结果集几乎已经完全成型：

的特殊情况null parentid。因此，它null parentid标识了数据集中没有其他originating ancestor含义的含义。以下是您将如何利用它来发挥自己的优势。因为您在 处开始了初始递归，所以与您开始时的 与 处没有直接联系，但在所有其他级别都有，只需劫持该空父级 id 并翻转值，您现在就拥有了叶子的祖先。ancestorancestorleaf levelidoriginating ancestor

最后，如果您希望它成为后代表，请切换列，您就完成了。最后一个注释DISTINCT是为了防止id与附加的重复parentid。例如6 | 3，还有另一条记录6 | 4