Michael J. Swart

I want to write (for posterity) a solution to a problem I encountered last week. I was asked a question about the following error message:

The statement terminated. The maximum recursion 100 has
been exhausted before statement completion.

I was dealing with a table that represented a (0..*) to (0..*) relationship between objects I’ll call THINGS¹:

CREATE TABLE PARENTS
(
   ParentId INT NOT NULL REFERENCES THING(Id),
   ChildId INT NOT NULL REFERENCES THING(Id),
   PRIMARY KEY (ParentId, ChildId)
)

We were attempting to populate a similar table called ANCESTORS using a recursive CTE. I suspected that the recursive CTE was not terminating because of a loop in the PARENTS table. That is to say, the data in the PARENTS table implied that some THING was its own ancestor. (Think of it this way, if you are your own parent, that also means you’re your own grandparent, great-grandparent etc…)

To help fix the data I needed to write a query that returned a list of all THINGs that were (somehow) their own ancestor. This is what I came up with. It’s inefficient, but it did the trick.

;WITH ANCESTORS_CTE
AS (
     SELECT ParentId AS AncestorId, ChildId AS DescendantId, 1  AS Depth
     FROM PARENTS
     UNION ALL
     SELECT ANCESTORS_CTE.AncestorId, PARENTS.ChildId, ANCESTORS_CTE.Depth + 1 AS Depth
     FROM ANCESTORS_CTE
     JOIN PARENTS
          ON ANCESTORS_CTE.DescendantId = PARENTS.ParentId
     WHERE ANCESTORS_CTE.Depth < 10
)
SELECT DISTINCT AncestorId
FROM ANCESTORS_CTE
WHERE AncestorId = DescendantId

¹ Mathematically speaking, the PARENTS table represents the adjacency matrix of a directed acyclic graph.