TSQL: Handle infinite loop in data

Question

I have a table FolderXDoc:

CREATE TABLE [dbo].[FolderXDoc](
[fldid] [int] NOT NULL,
[Xorder] [int] NOT NULL,
[docid] [int] NOT NULL,
CONSTRAINT [FolderXDoc$pk] PRIMARY KEY CLUSTERED 
(
[fldid] ASC,
[Xorder] ASC,
[docid] ASC
)WITH (PAD_INDEX  = OFF, STATISTICS_NORECOMPUTE  = OFF, IGNORE_DUP_KEY = OFF, ALLOW_ROW_LOCKS  = ON, ALLOW_PAGE_LOCKS  = ON) ON [PRIMARY]
) ON [PRIMARY]

My application allows cyclic references in this table, so the following data is allowed:

fldid|Xorder|docid
1|1|2
2|1|3
3|1|4
4|1|2

So folder 1 contains folder 2 which contains folder 3. Folder 3 contains folder 4. Folder 4 contains folder 2 so that we have a cycle (1/2/3/4/2/3/4/2/3/4/...)

Now I want to retrieve all contained elements of a folder recursively. I tried this with CTE, but because of the cycle of the data this does not work. I would like to stop the recursion when the loop is detected. So when I retrieve the contained elements of 1 I'd expect the result set (2,3,4).

I tried this with a user defined function:

CREATE FUNCTION [dbo].[DocChildren](@fldid int)
RETURNS TABLE
AS
RETURN
(
     WITH n AS 
           (SELECT f.fldid, f.docid
            FROM folderxdoc f where f.fldid = @fldid
           UNION ALL

           SELECT n.fldid, nplus1.docid  
            FROM folderxdoc as nplus1, n
                WHERE n.docid = nplus1.fldid and n.docid != @fldid)

     SELECT docid FROM n
  )

The function handles a cyclic loop of the starting id, but not when the cycle occurs in a contained element. What can I do to solve this problem?

Thanks for your help!

What output would you want when you run into one of these infinite loops? Would you want it to display the first complete chain? In your above example, would you want 1/2/3/4, or 1/2/3/4/2/3/4, or something else? — Registered User, Apr 18 '13 at 19:22
You can find an example of detecting a loop in a CTE [here](http://stackoverflow.com/questions/15080922/infinite-loop-cte-with-option-maxrecursion-0/15081353#15081353). It involves assembling the path during recursion and testing for a duplicate entry. — HABO, Apr 18 '13 at 19:48
@Registered User: Thanks for your feedback. I have edited the question. My expected result set is (2,3,4) for all elements contained in 1. — carlptr, Apr 19 '13 at 06:55
@Habo: Thanks for the hint! I managed to solve this based on the example you provided: http://sqlfiddle.com/#!3/cc8b3/1 — carlptr, Apr 19 '13 at 06:56

score 1 · Answer 1 · answered Apr 18 '13 at 19:15

Perhaps a temp table to mark when a node has been visited may help.

Basically as you visit each node, push it into the temp table and check each node against the temp table. Stop when you find an existing node.

Might need cursors to implement this though, as bad as that may be.

score 1 · Accepted Answer · answered Apr 19 '13 at 07:14

I solved the issue using the hint of @HaBo.

I assembled the path during recursion and checked for duplicate entries. You can find the resulting query here: http://sqlfiddle.com/#!3/cc8b3/1

 WITH n AS 
       (SELECT f.fldid, f.docid, ',' + cast(f.fldid as varchar(max)) + ',' levels
        FROM folderxdoc f where f.fldid = 1
       UNION ALL

       SELECT n.fldid, nplus1.docid,n.levels+ cast(n.docid as varchar(max)) + ',' levels
        FROM folderxdoc as nplus1, n
            WHERE n.docid = nplus1.fldid AND
            n.levels not like ('%,' + cast(nplus1.docid as varchar(max)) + ',%')
       )

 SELECT fldid, docid, levels FROM n

TSQL: Handle infinite loop in data

2 Answers2