SQL层次结构-解析给定节点的所有祖先的完整路径 [英] SQL Hierarchy - Resolve full path for all ancestors of a given node

问题描述

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

I have a hierarchy described by an adjacency list. There is not necessarily a single root element, but I do have data to identify the leaf (terminal) items in the hiearchy. So, a hierachy that looked like this ...

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

...会像这样用表格来描述。 注意：我无法更改此格式。

... would be described by a table, like this. NOTE: I don't have the ability to change this format.

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

这是示例表定义和数据：

here is the sample table definition and data:

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 的输入，我会期望以下内容：

From this, I need to provide any id and get a list of all ancestors including all descendents of each. So, if I provided the input of id = 6, I would expect the following:

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

• id 6本身就是


• 其父代，id 3将有3和6的后代


• 其父代，id 3将具有1、3和6的后代。 b $ b
  • id 6 just has itself
  • its parent, id 3 would have decendents of 3 and 6
  • its parent, id 1 would have decendents of 1, 3, and 6

  我将使用此数据在层次结构的每个级别上提供汇总计算。

  I will be using this data to provide roll-up calculations at each level in the hierarchy. This works well, assuming I can get the dataset above.

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

  I have accomplished this using two recusive ctes - one to get the "terminal" item for each node in the hiearchy. Then, a second one where I get the full ancestory of my selected node (so, 6 resolves to 6, 3, 1) to walk up and get the full set. I'm hoping that I'm missing something and that this can be accomplished in one round. Here is the example double-recursion code:

  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个级别。

  Additional detail: the "real" hierarchy will be much larger than the example. It can technically have infinite depth, but realistically it would rarely go more than 10 levels deep.

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

  In summary, my question is if I can accomplish this with a single recursive cte instead of having to recurse over the hierarchy twice.

  推荐答案

  好吧，这是困扰我的原因，因为我已经阅读了这个问题，然后我又重新考虑了一下... ..无论如何，为什么您需要递归向下才能获得所有后代？您要求的是祖先而不是后代，并且您的结果集没有尝试获取其他兄弟姐妹，孙子女等。在这种情况下，它获取的是父母和祖父母。您的第一个cte会为您提供所有您需要了解的信息，但当祖先ID也是父代ID时。因此，有了所有的并集，就可以设置原始祖先，这有点不可思议，并且您无需进行第二次递归即可拥有所需的一切。

  Okay this has been bothering me since I have read the question and I just came back to think of it again..... Anyway, why do you need to recurse back down to get all of the descendants? You have asked for ancestors not descendants and your result set is not trying to get other siblings, grand children, etc.. It is getting a parent and a grand parent in this case. Your First cte gives you everything you need to know except when an ancestor id is also the parentid. So with a union all, a little magic to setup the originating ancestor, and you have everything you need without a second 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
  
  )
  
  , 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个祖先，并且与他们的祖先，但对于祖父母 c> 为空的始祖祖先而言。 null 是我将在一分钟内处理的特例。

  Your result set from your first cte gives you your 2 ancestors and self related to their ancestor except in the case of the originating ancestors who's parentid is null. That null is a special case I will deal with in a minute.

  此时请记住，您的查询正在生成祖先而不是后代，但是它没有给您的是自我参考，意思是 grandparent =祖父母， parent =父母， self = self 。但是，您要做的就是为每个 id 添加行，并使 parentid 等于其 id 。因此，工会。现在您的结果集几乎完全成形了：

  Remember at this point your query is producing Ancestors not descendants, but what it doesn't give you is self references meaning grandparent = grandparent, parent = parent, self = self. But all you have to do to get that is to add rows for every id and make the parentid equal to their id. hence the union. Now your result set is almost totally shaped up:

  空父级的特殊情况。因此空父代标识了起源 祖先，这意味着祖先在数据集中没有其他祖先。这就是您将如何利用它来发挥自己的优势。由于您是从叶级别开始初始递归的，因此与您开始的 id 没有直接关系。 起源祖先，但在其他每个级别上，只需劫持空的父代id并将其值翻转即可，您现在有了叶子的祖先。

  The special case of the null parentid. So the null parentid identifies the originating ancestor meaning that ancestor has no other ancestor in your dataset. And here is how you will use that to your advantage. Because you started your initial recursion at the leaf level there is no direct tie to the id that you started with to the originating ancestor, but there is at every other level, simply hijack that null parent id and flip the values around and you now have an ancestor for your leaf.

  然后如果希望它成为后代表，则最后切换列即可完成。最后一个注释 DISTINCT 是在重复 id 和附加的 parentid <的情况下使用的/ code>。例如。 6 | 3 和 6的另一条记录| 4

  Then in the end if you want it to be a descendants table switch the columns and you are finished. One last note DISTINCTs are there in case the id is repeated with an additional parentid. E.g. 6 | 3 and another record for 6 | 4

  这篇关于SQL层次结构-解析给定节点的所有祖先的完整路径的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！