May 2, 2012 at 6:48 am
I have a table with a tree structure (IdIndividual, IdMother, IdFather).
Is there a way to find if the tree contains infinite cycles?
An infinite cycle in our case, could be if at some point, at a certain depth, an ancestor of IdIndividual has IdFather/IdMother one of its descendants.
I was trying to use a recursive CTE, but I get the error 'The maximum recursion 100 has been exhausted before statement completion.' If I try to increase 'maxrecursion' it executes for a lot of time and it does not seem to work. Also, I have checked that for my tree the maximum depth is of 95.
I would really apreciate any help!
Thank you!
May 2, 2012 at 8:37 am
This is one of the challenges of recursion and the adjacency list. How can you know if there is an endless loop until you get into it? You could put your code inside a try-catch, it would at least prevent your code from crashing.
_______________________________________________________________
Need help? Help us help you.
Read the article at http://www.sqlservercentral.com/articles/Best+Practices/61537/ for best practices on asking questions.
Need to split a string? Try Jeff Modens splitter http://www.sqlservercentral.com/articles/Tally+Table/72993/.
Cross Tabs and Pivots, Part 1 – Converting Rows to Columns - http://www.sqlservercentral.com/articles/T-SQL/63681/
Cross Tabs and Pivots, Part 2 - Dynamic Cross Tabs - http://www.sqlservercentral.com/articles/Crosstab/65048/
Understanding and Using APPLY (Part 1) - http://www.sqlservercentral.com/articles/APPLY/69953/
Understanding and Using APPLY (Part 2) - http://www.sqlservercentral.com/articles/APPLY/69954/
May 2, 2012 at 8:42 am
You have to build your own loop for that, instead of using a recursive CTE.
At each iteration of the loop, check if any values already exist in the result-set. Handle per whatever your rules are.
But recursive CTEs don't allow for real error-checking inside them.
- Gus "GSquared", RSVP, OODA, MAP, NMVP, FAQ, SAT, SQL, DNA, RNA, UOI, IOU, AM, PM, AD, BC, BCE, USA, UN, CF, ROFL, LOL, ETC
Property of The Thread
"Nobody knows the age of the human race, but everyone agrees it's old enough to know better." - Anon
May 3, 2012 at 12:37 am
I have also tried this approach (building my own loop).
The steps were:
Create a table (IdIndividual, IdMother, IdFather, Depth).
Create a sp with the parameters @IdIndividual, @Depth -> whithe the following steps:
-> inserts into the table @idIndividual, @depth and @idMother, @IdFather (which I can recover if a have an IdIndividual)
-> checks if my @IdMother or @IdFather isn't the same as IdIndividual(from table) and @Depth < Depth (from table)
-> if the conditions are true I have a @bool (bit) = 0 and return @IdIndidual, @idMother and @idFather
-> executes the same sp (recursive) for @IdMother and @IdFather.
Execute the sp starting from one @IdIndividual and initiate a variable @depth with one.
My problem is that I get the error : 'Maximum stored procedure nesting level exceeded (limit 32).' and I cannot run again starting with depth = 1 and also I cannot get the last depth value from the table, because the depth could by different, maybe it's on another branch of the tree, etc.
Is there something different I could do? Maybe use this approach? Or a different one?
What I need to do is to identify the cycle. I cannot do it visually because my trees are very big. (~200.000 individuals)
May 3, 2012 at 1:43 am
We had this as a forum question a while back where the OP had an unintentional loop and needed to find it:
http://www.sqlservercentral.com/Forums/Topic1283710-392-1.aspx
Fitz
May 3, 2012 at 8:22 am
I've resolved hierarchies of this nature, with this kind of error handling, in the past, simply by using a While loop and a temp table.
Insert your seed value (usually either a "top" row or a "bottom" row that you want to resolve a path up or down from). Then use While @@Rowcount > 0, and keep inserting, with a Where clause that includes Not In the temp table.
SELECT *
INTO #MyHierarchy
FROM dbo.MyTable
WHERE ID = <seed ID value>;
WHILE @@Rowcount > 0
INSERT INTO #MyHierarchy
SELECT MyTable.*
FROM dbo.MyTable
INNER JOIN #MyHierarchy
ON MyTable.ID IN (#MyHierarchy.FatherID, #MyHierarchy.MotherID)
WHERE ID NOT IN (SELECT ID FROM #MyHierarchy);
Something like that. You can add an iterative variable for depth if you want to. Makes the query a little more complex, since you have to change the While clause and add a Begin and End break so you can add an iteration counter increase to the loop. But it's not very complex to do so.
- Gus "GSquared", RSVP, OODA, MAP, NMVP, FAQ, SAT, SQL, DNA, RNA, UOI, IOU, AM, PM, AD, BC, BCE, USA, UN, CF, ROFL, LOL, ETC
Property of The Thread
"Nobody knows the age of the human race, but everyone agrees it's old enough to know better." - Anon
Viewing 6 posts - 1 through 5 (of 5 total)
You must be logged in to reply to this topic. Login to reply