SQL hierarchy - allow full path for all ancestors of a given node

Question

I have a hierarchy described by an adjacency list. There is not necessarily one root element, but I have data to identify the elements of a sheet (terminal) in hiearchy. So, the hierarchy that looked like this ...

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

... will be described by a table like this. NOTE I have no way 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 an example of a table and data definition:

 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 

From this, I must provide any identifier and get a list of all ancestors, including all descendants of each of them. So, if I imagined the input id = 6 , I would expect the following:

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

• id 6 just has
• its parent id id 3 would have deflectors of 3 and 6
• its parent id id 1 would have deflectors 1, 3, and 6

I will use this data to provide convolution calculations at each level of the hierarchy. This works well, assuming I can get the dataset above.

I did this using two recusive ctes - one to get a “terminal” for each node in hiearchy. Then, the second, where I get the full ancestors of my selected node (so 6 resolves to 6, 3, 1) to go up and get a complete set. I hope that I missed something and that it can be done in one round. Here is an example of 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 

Additional detail : the "real" hierarchy will be much more than an example. It may technically have infinite depth, but realistically, it has rarely been to more than 10 levels.

In conclusion, my question is, can I do this with a single recursive cte instead of rewriting the hierarchy twice.

Answer 1

Well, that bothered me since I read the question, and I just came back to think about it again ... Anyway, why would you come back to get all the descendants? You asked for ancestors, not descendants, and your result set does not try to get other brothers and sisters, grandchildren, etc. In this case, he receives a parent and a great parent. Your first cte gives you everything you need to know, except when the ancestor id is also a parent. So, with the union of all, a little magic to set up the parent-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 

Your result set from your first cte gives you 2 ancestors and itself associated with their ancestor , with the exception of the original ancestors, which parentid is null . This null is a special case that I'll talk to in a minute.

Remember, at this moment your request produces ancestors not descendants , but what it does not give you is self-promotion, meaning grandparent = grandparent , parent = parent , self = self . But all you have to do is add lines for each id and make parentid equal to their id . hence union . Now your result set is almost completely formed:

A special case of null parentid . So the null parentid identifies the originating ancestor , which means that ancestor does not have another ancestor in your dataset. And here is how you will use it to your advantage. Since you started your initial recursion at the leaf level , there is no direct link to the id you started with originating ancestor , but at every other level just remove that null parent id and flip the values ​​around and you now have an ancestor for your leaf.

Then, at the end, if you want it to be a descendant table, switch the columns and you are done. The last note of DISTINCT is in the case of repeating id with an additional parentid . For instance. 6 | 3 6 | 3 and another entry for 6 | 4 6 | 4

Answer 2

I'm not sure if this works better or even gives the correct results in all cases, but you can grab the node list and then use the xml functionality to parse it and cross-reference the list of identifiers:

 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 3

Since your data is a tree structure, we can use the data type of the hierarchy to meet your needs (even though you say you cannot comment). First, the simple part is generating a hierarchy with recursive cte

 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; 

Next, a small table function that I wrote:

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

Armed with this, getting the desired set of results is not so bad:

 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 ah = h.[path] order by h.id, c.id; 

Of course, you are missing out on the many benefits of using a hierarchy without saving it (you will have to either update it in the side table or generate it each time). But there you go.