Parent-Child Hierarchy - Finding the root
-
Hello, what I am trying to do is to find the root for every id.
declare @tab table
(id nvarchar(3),
Father_id nvarchar(3),
Flag_Root bit
)
insert into @tab values ('A1','A1',1)
insert into @tab values ('A2','A1',0)
insert into @tab values ('A3','A2',0)
insert into @tab values ('B1','B1',1)
insert into @tab values ('B2','B4',0)
insert into @tab values ('B3','B1',0)
insert into @tab values ('B4','B3',0)
insert into @tab values ('C1','C2',0)
insert into @tab values ('C2','C3',0)
insert into @tab values ('C4','C4',1)
I need to write a CTE recursive query but I don't know how...
It's a hierarchy A3-A2-A1, so for every row that begins with 'A' I need to put in the new column Root_result the value 'A1' which is the root (because flag_root=1).
The same for B2->B4->B3->B1
C1 and C2 will not have anything in the new column Root_result, they don't have a relationship with an Id having flag_root=1.
I don't know how many levels I have in the table.
Is it possible to write a CTE recursive query for this?
I appreciate any help
Thank you
-
How does this look:
WITH cte AS (
SELECT [id]
, [Father_id]
, [Flag_Root]
, root = [id]
, 0 AS N
FROM @tab
WHERE [Flag_Root] = 1
UNION ALL
SELECT [t].[id], [t].[father_id], [t].flag_root, root = [cte].[father_id]
, N+1 AS N
FROM @tab t
JOIN cte ON [cte].id = [t].father_id
WHERE [t].flag_root = 0
)
SELECT DISTINCT [cte].[id]
, [cte].[Father_id]
, [cte].[Flag_Root]
, LAG(root, N) OVER (ORDER BY root) AS root
FROM cte
UNION ALL
SELECT [id]
, [Father_id]
, [Flag_Root]
, '' AS root
FROM @tab
WHERE id NOT IN (SELECT ID FROM cte)
ORDER BY IDAs per your request, it uses a recursive CTE. Not entirely sure it is the most efficient way to solve this or the easiest to follow, but recursive CTE and gives you the results you had in your screenshot.
The above is all just my opinion on what you should do.
As with all advice you find on a random internet forum - you shouldn't blindly follow it. Always test on a test server to see if there is negative side effects before making changes to live!
I recommend you NEVER run "random code" you found online on any system you care about UNLESS you understand and can verify the code OR you don't care if the code trashes your system. -
It can be done in using a single recursive cte. You just need to pass the first found roots to the rest of the hierarchy. We might as well sort it in the expected order, as well. Comment out what you don't want but it's there if you need it.
WITH cteTraverse AS
(
SELECT id
,Father_ID
,Flag_Root = 1
,Root_Result = id
,HLevel = 1 --Because I don''t trust other people to mark this for me
,SortPath = CONVERT(VARCHAR(8000),'|'+id+'|')
FROM @tab
WHERE ID = Father_ID
UNION ALL
SELECT t.id
,t.Father_ID
,Flag_Root = 0 --Because I don''t trust other people to mark this for me
,Root_Result = h.Root_Result
,Hlevel = h.HLevel + 1
,SortPath = CONVERT(VARCHAR(8000),h.SortPath+t.id+'|')
FROM @tab t
JOIN cteTraverse h
ON h.id = t.Father_id
WHERE --These criteria prevent cyclic errors
h.SortPath NOT LIKE '%|' + t.ID + '|%'
AND t.id <> t.Father_ID
)
SELECT *
FROM cteTraverse
ORDER BY SortPath
;Here's the output...
--Jeff Moden
RBAR is pronounced "ree-bar" and is a "Modenism" for Row-By-Agonizing-Row.
First step towards the paradigm shift of writing Set Based code:
________Stop thinking about what you want to do to a ROW... think, instead, of what you want to do to a COLUMN.
"Change is inevitable... change for the better is not".
Helpful Links:
How to post code problems
How to Post Performance Problems
Create a Tally Function (fnTally)
Intro to Tally Tables and Functions -
p.s.
If you want to seem some "Black Arts" magic with these kinds of Adjacency List hierarchies and learn about Nested Sets and other cool things, check out the following two articles on hierarchies. I can vouch for the author. 😀
--Jeff Moden
RBAR is pronounced "ree-bar" and is a "Modenism" for Row-By-Agonizing-Row.
First step towards the paradigm shift of writing Set Based code:
________Stop thinking about what you want to do to a ROW... think, instead, of what you want to do to a COLUMN.
"Change is inevitable... change for the better is not".
Helpful Links:
How to post code problems
How to Post Performance Problems
Create a Tally Function (fnTally)
Intro to Tally Tables and Functions -
I've written an entire book on various methods for modeling treason hierarchies and SQL. Get a copy and see which technique is most appropriate for your particular situation.
Please post DDL and follow ANSI/ISO standards when asking for help.
-
Imo expressing the recursive "downlines" or "sort path" as nested json makes the information much more usefully accessible. You can check out an example at:
Aus dem Paradies, das Cantor uns geschaffen, soll uns niemand vertreiben können
-
Steve Collins wrote:
Imo expressing the recursive "downlines" or "sort path" as nested json makes the information much more usefully accessible. You can check out an example at:
Can you use the "Sort Path" in JSON to create the nested sets? (I've not looked at your article yet).
--Jeff Moden
RBAR is pronounced "ree-bar" and is a "Modenism" for Row-By-Agonizing-Row.
First step towards the paradigm shift of writing Set Based code:
________Stop thinking about what you want to do to a ROW... think, instead, of what you want to do to a COLUMN.
"Change is inevitable... change for the better is not".
Helpful Links:
How to post code problems
How to Post Performance Problems
Create a Tally Function (fnTally)
Intro to Tally Tables and Functions -
Jeff Moden wrote:Steve Collins wrote:
Imo expressing the recursive "downlines" or "sort path" as nested json makes the information much more usefully accessible. You can check out an example at:
Can you use the "Sort Path" in JSON to create the nested sets? (I've not looked at your article yet).
Pretty sure the answer is yes. The nested json arrays in the script are nested sets yes? I posted an example using your test data in the forum of one of your articles. The major reason I know how to do any of this, btw, is because I've studied your articles. My advice to the OP as a first step is definitely read those articles 🙂
Aus dem Paradies, das Cantor uns geschaffen, soll uns niemand vertreiben können
-
jcelko212 32090 wrote:
I've written an entire book on various methods for modeling treason hierarchies and SQL. Get a copy and see which technique is most appropriate for your particular situation.
I'll add that it's a good great book (although I've not read the latest one). When you get to the part about converting an Adjacency List to Nested Sets, though, you might want to consider the newer and much faster method that's taught in the following article. It also means that, rather than abandoning the ease of of modification the Adjacency List offers, you can actually keep it because the conversions to Nested Sets are now so incredibly fast. For example, the original "push stack" method in the book will take literally a couple of days (although I've not measured it on newer machines) to do the conversion to Nested Sets on a million row hierarchy (and a surprising number of people have such things). On an old laptop running SQL Server 2008 with dual i5 CPU's (threaded to 4) and only 4GB of RAM allocated to SQL Server, the new method takes that down to 54 seconds. On my current laptop running SQL Server 2017 with a 6 core i7 (threaded to 12) and 24GB of RAM allocated to SQL Server, it only takes 19 seconds.
Here's the link to the article that explains the "new" method, which is now almost 8 years old...
There's also a method you might want to consider. I wouldn't go so far as to call it a new type of Hierarchical structure but it's close. It "pre-aggregates" most of what you'd ever need to ask of a hierarchy as a single kind-of data warehouse table and it also takes the same amount of time to create from an Adjacency List. Here's the article on that.
Both articles come with code to create a small "Employee" table and a monster 1 million row (actually, it's programmable for size) that only takes a short amount of time to execute so that you can test all sorts of things with a properly formed Adjacency List.
--Jeff Moden
RBAR is pronounced "ree-bar" and is a "Modenism" for Row-By-Agonizing-Row.
First step towards the paradigm shift of writing Set Based code:
________Stop thinking about what you want to do to a ROW... think, instead, of what you want to do to a COLUMN.
"Change is inevitable... change for the better is not".
Helpful Links:
How to post code problems
How to Post Performance Problems
Create a Tally Function (fnTally)
Intro to Tally Tables and Functions -
Steve Collins wrote:Jeff Moden wrote:Steve Collins wrote:
Imo expressing the recursive "downlines" or "sort path" as nested json makes the information much more usefully accessible. You can check out an example at:
Can you use the "Sort Path" in JSON to create the nested sets? (I've not looked at your article yet).
Pretty sure the answer is yes. The nested json arrays in the script are nested sets yes? I posted an example using your test data in the forum of one of your articles. The major reason I know how to do any of this, btw, is because I've studied your articles. My advice to the OP as a first step is definitely read those articles 🙂
My apologies... I AM remiss in not devoting some time to giving your code a run. Things are slowing up a bit for me lately and I should be able to allocate some good time to studying and running your code. And thank you for the very kind words.
--Jeff Moden
RBAR is pronounced "ree-bar" and is a "Modenism" for Row-By-Agonizing-Row.
First step towards the paradigm shift of writing Set Based code:
________Stop thinking about what you want to do to a ROW... think, instead, of what you want to do to a COLUMN.
"Change is inevitable... change for the better is not".
Helpful Links:
How to post code problems
How to Post Performance Problems
Create a Tally Function (fnTally)
Intro to Tally Tables and Functions -
>> I'll add that it's a good great book (although I've not read the latest one). <<
Unfortunately, there's only been one edition. Oh well, it still sells and I get royalties so I can pay my mortgage. 🙂
>> When you get to the part about converting an Adjacency List to Nested Sets, though, you might want to consider the newer and much faster method that's taught in the following article. <<
Definitely! I posted a SQL/PSM version of the standard traversal programs from freshman data structures courses. It is, at best, weak, and, at worst, very inefficient. I'd like to sit down and I get the time and rewrite those parts of the manuscript. But I have no idea if my publisher wants to do another edition.
Please post DDL and follow ANSI/ISO standards when asking for help.
Viewing 11 posts - 1 through 10 (of 10 total)
You must be logged in to reply to this topic. Login to reply