4

I have the following schema (names changed), which I cannot change:

CREATE TABLE MyTable (
    Id INT NOT NULL PRIMARY KEY,
    ParentId INT NOT NULL
);

ALTER TABLE MyTable ADD FOREIGN KEY (ParentId) REFERENCES MyTable(Id);

That is, each record is a child of another record.

The root node is the record with Id equal to 0.

I want to run query which will find all circular references. For example, with the data

INSERT INTO MyTable (Id, ParentId) VALUES
    (0, 0),
    (1, 0),
    (2, 4),
    (3, 2),
    (4, 3),
    (5, 6),
    (6, 5),
    (7, 5),
    (8, 8);

the query should return

Id | Cycle
2  | 2 > 4 > 3 > 2
3  | 3 > 2 > 4 > 3
4  | 4 > 3 > 2 > 4
5  | 5 > 6 > 5
6  | 6 > 5 > 6
7  | 7 > 5 > 6 > 5
8  | 8

This is similar to my question How to write a query which finds all circular references when a table references itself? from last year, except for the following differences:

  • The root node is hard-coded to have an Id of 0.
  • Any self-cycle (8 in the example above) except for the root should be considered a cycle
  • The accepted answer runs into infinite recursion on the case 7 > 5 > 6 > 5 in the example above

I am having trouble coming up with a query to account for these. Suggestions?

1
  • Recursive CTE's are straightforward to code, but don't always scale well. Do you have more than a few hundred rows in this table? Do you need to specify the cycles or only need to identify the nodes that are orphaned from root? The latter may be more efficiently answered as a set difference between the entire tree and the non-orphaned nodes (which obviously can be accessed from root). Aug 4, 2014 at 17:07

2 Answers 2

3

I think you're looking for a recursive common table expression.

WITH rcte (Id, ParentId, [Path])
AS ( --- Anchor:
     SELECT Id, ParentId,
            CAST(CAST(Id AS varchar(10))+' > '+
         CAST(ParentID AS varchar(10)) AS varchar(max))
     FROM MyTable

     UNION ALL

     --- Recursion:
     SELECT t.Id, rcte.ParentId,
        CAST(CAST(t.Id AS varchar(10))+' > '+
         rcte.[Path] AS varchar(max))
     FROM rcte
     INNER JOIN MyTable AS t ON rcte.Id=t.ParentId
     WHERE rcte.ParentID!=rcte.Id)

--- Returns rows where parent is child, i.e. self-recursion:
SELECT ISNULL(b.Id, a.Id) AS Id, ISNULL(b.[Path]+SUBSTRING(a.[Path], LEN(CAST(a.Id AS varchar(10)))+1, LEN(a.[Path])), a.[Path])
FROM rcte AS a
LEFT JOIN rcte AS b ON b.ParentId=a.Id AND b.Id NOT IN (SELECT ParentId FROM MyTable)
WHERE a.Id=a.ParentId
ORDER BY a.Id
OPTION (MAXRECURSION 0);

First off, every relation is a potential anchor in the tree. Then union those anchors to their respective relations (working your way down the tree for each recursion). The recursion stops when Id is ParentId, i.e. when you've come "full circle", or when there is nothing left to recurse.

Finally, the returned resultset is filtered for only those records where Id=ParentID. You might want to add a filter to exclude the 0-member as well, not sure how you wanted it.

Edit: I've LEFT JOIN'ed rcte again (as "b") to catch any branches leading up to a self-recursion. The query still doesn't precisely return the data in the question, but perhaps it's close enough. :)

A quick intro to recursive CTEs from a blog post of mine.

2
  • 2
    Wouldn't 7 still slip by?
    – JNK
    Aug 4, 2014 at 16:40
  • Yep, I just realised. :) I've revised the query to try to fix it. Aug 4, 2014 at 16:56
1

I've used a recursive CTE that works from each node back towards the root, child to parent. If at any stage the path loops onto itself it will set a flag to stop the recursion.
Each node other than the root node is considered as a start (anchor) point for the recursion.

WITH rcte AS (
-- Child Nodes
    SELECT  
        a.ID BaseID,
        a.ParentID, 
        a.ID,
        '> ' + CAST(a.ID AS VARCHAR(8000)) + ' > ' Cycle,
        0 rFlag
    FROM MyTable a
    WHERE a.ID <> 0 and parentID <> 0            -- Ignore root node and imediate children

    UNION ALL
    -- Parent Nodes
    SELECT  
        r.BaseID, 
        m.ParentID, 
        m.ID,
        r.Cycle + CAST(m.ID AS VARCHAR(10)) + ' > ' Cycle,
        CASE 
            WHEN r.Cycle like '% ' + CAST(m.ID AS VARCHAR(10)) + ' %' 
            THEN 1                               -- Flag if node already hit
            ELSE 0 
        END rFlag       
    FROM MyTable m
        INNER JOIN rcte r ON r.ParentID = m.ID   -- Work back towards root
    WHERE r.rFlag = 0                            -- Avoid recursing forever
        and m.ParentID <> 0                      -- Avoid recursing to root node
    )
SELECT 
    BaseID ID, 
    STUFF(SUBSTRING(Cycle,1,LEN(Cycle)-2),1,2,'') Cycle
FROM rcte r
WHERE rFlag = 1                                  -- Filter to records that loop back on themselves
ORDER BY BaseID
OPTION (MAXRECURSION 1000)                       -- Have it error out if it recurses too much

;

1
  • Actually, I think MickyT's script is more accurate. I just list one example here (besides others) In MickyT's soultion, I can see a returned record of 6>5>6, which is correct and expected, while you cannot find it in Daniel Hutmacher's solution.
    – jyao
    May 3, 2016 at 18:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.