Databases
StackOverflow2013
Postsdbo
POSQL Server: How to limit CTE recursion to rows just recursivly added?
 

Note that there are some explanatory texts on larger screens.

plurals
  1. POSQL Server: How to limit CTE recursion to rows just recursivly added?
    primarykey
    data
    text
    <h2>Simpler Example</h2> <p>Let's try a simpler example, so people can wrap their heads around the concepts, and have a practical example that you can copy&amp;paste into SQL Query Analizer:</p> <p>Imagine a <strong>Nodes</strong> table, with a heirarchy:</p> <pre><code>A - B - C </code></pre> <p>We can start testing in Query Analizer:</p> <pre><code>CREATE TABLE ##Nodes ( NodeID varchar(50) PRIMARY KEY NOT NULL, ParentNodeID varchar(50) NULL ) INSERT INTO ##Nodes (NodeID, ParentNodeID) VALUES ('A', null) INSERT INTO ##Nodes (NodeID, ParentNodeID) VALUES ('B', 'A') INSERT INTO ##Nodes (NodeID, ParentNodeID) VALUES ('C', 'B') </code></pre> <p><strong>Desired output:</strong></p> <pre><code>ParentNodeID NodeID GenerationsRemoved ============ ====== ================== NULL A 1 NULL B 2 NULL C 3 A B 1 A C 2 B C 1 </code></pre> <p>Now the suggested CTE expression, with it's incorrect output:</p> <pre><code>WITH NodeChildren AS ( --initialization SELECT ParentNodeID, NodeID, 1 AS GenerationsRemoved FROM ##Nodes WHERE ParentNodeID IS NULL UNION ALL --recursive execution SELECT P.ParentNodeID, N.NodeID, P.GenerationsRemoved + 1 FROM NodeChildren AS P INNER JOIN ##Nodes AS N ON P.NodeID = N.ParentNodeID ) SELECT ParentNodeID, NodeID, GenerationsRemoved FROM NodeChildren </code></pre> <p><strong>Actual output</strong>:</p> <pre><code>ParentNodeID NodeID GenerationsRemoved ============ ====== ================== NULL A 1 NULL B 2 NULL C 3 </code></pre> <p><strong>Note:</strong> If SQL Server 2005† CTE cannot do what i was doing before in 2000‡, that's fine, and that's the answer. And whoever gives "it's not possible" as the answer will win the bounty. But i will wait a few days to make sure everyone concur's that it's not possible before i irrecovably give 250 reputation for a non-solution to my problem.</p> <p><strong>Nitpickers Corner</strong></p> <p>†not 2008</p> <p>‡without resorting to a UDF*, which is the solution already have</p> <p>*unless you can see a way to improve the performance of the UDF in the original question</p> <hr> <h2>Original Question</h2> <p>i have a table of Nodes, each with a parent that points to another Node (or to null).</p> <p>For illustration:</p> <pre><code>1 My Computer 2 Drive C 4 Users 5 Program Files 7 Windows 8 System32 3 Drive D 6 mp3 </code></pre> <p>i want a table that returns all the parent-child relationships, and the number of generations between them</p> <p>For for all direct parent relationships:</p> <pre><code>ParentNodeID ChildNodeID GenerationsRemoved ============ =========== =================== (null) 1 1 1 2 1 2 4 1 2 5 1 2 7 1 1 3 1 3 6 1 7 8 1 </code></pre> <p>But then there's the grandparent relationships:</p> <pre><code>ParentNodeID ChildNodeID GenerationsRemoved ============ =========== =================== (null) 2 2 (null) 3 2 1 4 2 1 5 2 1 7 2 1 6 2 2 8 2 </code></pre> <p>And the there's the great-grand-grandparent relationships:</p> <pre><code>ParentNodeID ChildNodeID GenerationsRemoved ============ =========== =================== (null) 4 3 (null) 5 3 (null) 7 3 (null) 6 3 1 8 3 </code></pre> <p>So i can figure out the basic CTE initialization:</p> <pre><code>WITH (NodeChildren) AS { --initialization SELECT ParentNodeID, NodeID AS ChildNodeID, 1 AS GenerationsRemoved FROM Nodes } </code></pre> <p>The problem now is the recursive part. The obvious answer, of course, doesn't work:</p> <pre><code>WITH (NodeChildren) AS { --initialization SELECT ParentNodeID, ChildNodeID, 1 AS GenerationsRemoved FROM Nodes UNION ALL --recursive execution SELECT parents.ParentNodeID, children.NodeID, parents.Generations+1 FROM NodeChildren parents INNER JOIN NodeParents children ON parents.NodeID = children.ParentNodeID } Msg 253, Level 16, State 1, Line 1 Recursive member of a common table expression 'NodeChildren' has multiple recursive references. </code></pre> <p>All the information needed to generate the entire recursive list is present in the inital CTE table. But if that's not allowed i'll try:</p> <pre><code>WITH (NodeChildren) AS { --initialization SELECT ParentNodeID, NodeID, 1 AS GenerationsRemoved FROM Nodes UNION ALL --recursive execution SELECT parents.ParentNodeID, Nodes.NodeID, parents.Generations+1 FROM NodeChildren parents INNER JOIN Nodes ON parents.NodeID = nodes.ParentNodeID } </code></pre> <p>But that fails because it's not only joining on the recursive elements, but keeps recursivly adding the same rows over and over:</p> <pre><code>Msg 530, Level 16, State 1, Line 1 The statement terminated. The maximum recursion 100 has been exhausted before statement completion. </code></pre> <p>In SQL Server 2000 i simulated a CTE by using a User Defined Function (UDF):</p> <pre><code>CREATE FUNCTION [dbo].[fn_NodeChildren] () RETURNS @Result TABLE ( ParentNodeID int NULL, ChildNodeID int NULL, Generations int NOT NULL) AS /*This UDF returns all "ParentNode" - "Child Node" combinations ...even multiple levels separated BEGIN DECLARE @Generations int SET @Generations = 1 --Insert into the Return table all "Self" entries INSERT INTO @Result SELECT ParentNodeID, NodeID, @Generations FROM Nodes WHILE @@rowcount &gt; 0 BEGIN SET @Generations = @Generations + 1 --Add to the Children table: -- children of all nodes just added -- (i.e. Where @Result.Generation = CurrentGeneration-1) INSERT @Result SELECT CurrentParents.ParentNodeID, Nodes.NodeID, @Generations FROM Nodes INNER JOIN @Result CurrentParents ON Nodes.ParentNodeID = CurrentParents.ChildNodeID WHERE CurrentParents.Generations = @Generations - 1 END RETURN END </code></pre> <p>And the magic to keep it from blowing up was the limiting where clause: WHERE CurrentParents.Generations - @Generations-1</p> <p>How do you prevent a recursive CTE from recursing forever? </p>
    singulars
    1. PO
      singulars
      1. PTAnswer
    1. This table or related slice is empty.
    1. PTQuestion
    1. USIan Boyd
    1. USIan Boyd
    plurals
    1. This table or related slice is empty.
    1. PL
      singulars
      1. LTLinked
    2. PL
      singulars
      1. LTLinked
    3. PL
      singulars
      1. LTLinked
    1. This table or related slice is empty.
    1. PO
      singulars
      1. PTAnswer
    2. PO
      singulars
      1. PTAnswer
    3. PO
      singulars
      1. PTAnswer
    1. VO
      singulars
      1. POSQL Server: How to limit CTE recursion to rows just recursivly added?
      1. USIan Boyd
      1. VTBountyStart
    2. VO
      singulars
      1. POSQL Server: How to limit CTE recursion to rows just recursivly added?
      1. USMattK
      1. VTFavorite
    3. VO
      singulars
      1. POSQL Server: How to limit CTE recursion to rows just recursivly added?
      1. This table or related slice is empty.
      1. VTUpMod
    1. COQuite honestly - I do not think you can do this in a simple, one-step process. What you're trying to achieve is not "normal" hierarchical display from level to level, but a mix between several levels. This can't be handled by CTE or other methods....
      singulars
      1. POSQL Server: How to limit CTE recursion to rows just recursivly added?
      1. USmarc_s
 

Querying!

 
Guidance
A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload