SQL : How to get full hierarchy paths avoiding self & back relations?

Question

I have the following table (StatusTransitions) :: SQL Fiddle

I use the below queries to get all full hierarchy paths ::

;WITH Paths  AS
 (
    SELECT 
        ID, FromID, ToID,
        CAST(FromID + ',' + CAST(ToID AS VARCHAR(100)) AS varchar(100)) AS [Path]
        , 1 as LevelID
    FROM    StatusTransitions
    WHERE   FromID = 'A'

    UNION ALL

    SELECT   
        NextTransition.ID, NextTransition.FromID, NextTransition.ToID,
        CAST(PreviousTransition.[Path] + ',' + CAST( NextTransition.ToID AS VARCHAR(100)) AS varchar(100)) AS [Path]
        ,(PreviousTransition.LevelID + 1) as LevelID
    FROM    
        StatusTransitions AS NextTransition 
            join Paths AS PreviousTransition ON NextTransition.FromID = PreviousTransition.ToID 
)

SELECT  ID, FromID, ToID, [Path], LevelID
FROM    Paths
WHERE   ToID NOT IN 
    ( 
        SELECT  FromID
        FROM    StatusTransitions
        WHERE   FromID <> 'A'
    )

Order By ID
OPTION (MAXRECURSION 20)

Query work perfectly in case we don't have any self relation between the same item or any back relation ( example :: items with id 12,13 ) ..

previous relations go into infinite loops ..

How can change this queries in which be able to avoid these relations ??

Answer 1

You prevent cycles by being sure that the new element in the path is not already in the path. The following where statement does this:

WHERE ','+PreviousTransition.[Path]+',' not like '%,'+NextTransition.ToID+',%'

The complete query is:

;WITH Paths  AS
 (
    SELECT
        ID, FromID, ToID,
        CAST(FromID + ',' + CAST(ToID AS VARCHAR(100)) AS varchar(100)) AS [Path]
        , 1 AS LevelID
    FROM    StatusTransitions
    WHERE   FromID = 'A'

    UNION ALL

    SELECT
        NextTransition.ID, NextTransition.FromID, NextTransition.ToID,
        CAST(PreviousTransition.[Path] + ',' + CAST( NextTransition.ToID AS VARCHAR(100)) AS varchar(100)) AS [Path],
        (PreviousTransition.LevelID + 1) AS LevelID
    FROM StatusTransitions NextTransition JOIN
         Paths PreviousTransition
         ON NextTransition.FromID = PreviousTransition.ToID
    WHERE ','+PreviousTransition.[Path]+',' not like '%,'+NextTransition.ToID+',%'
)
SELECT  ID, FromID, ToID, [Path], LevelID
FROM    Paths
WHERE   ToID NOT IN
    (
        SELECT  FromID
        FROM    StatusTransitions
        WHERE   FromID <> 'A'
    )
ORDER BY ID
OPTION (MAXRECURSION 20);

Because of the not in filtering, the result is not the same as the query on the original data, but I believe it is working correctly. The SQL Fiddle is here.