TSQL CTE: How to avoid circular traversal?

Question

I have written a very simple CTE expression that retrieves a list of all groups of which a user is a member.

The rules goes like this, a user can be in multiple groups, and groups can be nested so that a group can be a member of another group, and furthermore, groups can be mutual member of another, so Group A is a member of Group B and Group B is also a member of Group A.

My CTE goes like this and obviously it yields infinite recursion:

            ;WITH GetMembershipInfo(entityId) AS( -- entity can be a user or group
                SELECT k.ID as entityId FROM entities k WHERE k.id = @userId
                UNION ALL
                SELECT k.id FROM entities k 
                JOIN Xrelationships kc on kc.entityId = k.entityId
                JOIN GetMembershipInfo m on m.entityId = kc.ChildID
            )

I can't find an easy solution to back-track those groups that I have already recorded.

I was thinking of using an additional varchar parameter in the CTE to record a list of all groups that I have visited, but using varchar is just too crude, isn't it?

Is there a better way?

Answer 1

You need to accumulate a sentinel string within your recursion. In the following example I have a circular relationship from A,B,C,D, and then back to A, and I avoid a loop with the sentinel string:

DECLARE @MyTable TABLE(Parent CHAR(1), Child CHAR(1));

INSERT @MyTable VALUES('A', 'B');
INSERT @MyTable VALUES('B', 'C');
INSERT @MyTable VALUES('C', 'D');
INSERT @MyTable VALUES('D', 'A');

; WITH CTE (Parent, Child, Sentinel) AS (
    SELECT  Parent, Child, Sentinel = CAST(Parent AS VARCHAR(MAX))
    FROM    @MyTable
    WHERE   Parent = 'A'
    UNION ALL
    SELECT  CTE.Child, t.Child, Sentinel + '|' + CTE.Child
    FROM    CTE
    JOIN    @MyTable t ON t.Parent = CTE.Child
    WHERE   CHARINDEX(CTE.Child,Sentinel)=0
)
SELECT * FROM CTE;

Result:

Parent Child Sentinel
------ ----- --------
A      B     A
B      C     A|B
C      D     A|B|C
D      A     A|B|C|D

Answer 2

Instead of a sentinel string, use a sentinel table variable. Function will catch circular reference no matter how many hops the circle is, no issues with maximum length of nvarchar(max), easily modified for different data types or even multipart keys, and you can assign the function to a check constraint.

CREATE FUNCTION [dbo].[AccountsCircular] (@AccountID UNIQUEIDENTIFIER)
RETURNS BIT 
AS
BEGIN
    DECLARE @NextAccountID UNIQUEIDENTIFIER = NULL;
    DECLARE @Sentinel TABLE
    (
        ID UNIQUEIDENTIFIER
    )
    INSERT INTO     @Sentinel
                ( [ID] )
    VALUES          ( @AccountID )
    SET @NextAccountID = @AccountID;

    WHILE @NextAccountID IS NOT NULL
    BEGIN
        SELECT  @NextAccountID = [ParentAccountID]
        FROM    [dbo].[Accounts]
        WHERE   [AccountID] = @NextAccountID;
        IF  EXISTS(SELECT 1 FROM @Sentinel WHERE ID = @NextAccountID)
            RETURN 1;
        INSERT INTO @Sentinel
                ( [ID] )
        VALUES      ( @NextAccountID )
    END
    RETURN 0;
END