Common Table Expressions to retrieve path

Question

I'm trying to use a recursive query to find a path through a table structured like this:

RelatedEntities

FromKey TINYINT
ToKey TINYINT
...more....

I thought I could do something like this:

DECLARE @startKey UNIQUEIDENTIFIER, @endKey UNIQUEIDENTIFIER;
SET @startKey = 0;
SET @endKey = 3;

;With findPath
AS
(
    SELECT FromKey, ToKey
    FROM RelatedEntities
    WHERE FromKey = @startKey

    UNION ALL

    SELECT FromKey, ToKey
    FROM RelatedEntities r
    JOIN findPath b
    ON r.FromKey = b.ToKey
    AND r.FromKey NOT IN (SELECT FromKey FROM b)
)
SELECT * FROM findPath;

This code fails because I cannot use a subquery within a CTE. It also seems to be a rule that the recursive query can only contain one reference to the CTE. (true?) Maybe this is a job for a cursor, or procedural code, but I thought I would put it out here in case I'm missing a way to find a path through a table with a CTE?

The parameters are:

Start with a beginning and ending key
Base query uses the beginning key
Recursive query should stop when it contains the ending key, (have not been able to figure that one out) and should not repeat start keys.
A MAXRECURSION option could be used to stop after a certain number of iterations.

Thanks to all of you CTE gurus out there. Set me straight.

Changing this from UNIQUEIDENTIFIERS to TINYINT for readability. The SQL constructs are the same. Here's some code to test it.

CREATE TABLE RelatedEntities(FromKey TINYINT, ToKey TINYINT);

INSERT RelatedEntities(FromKey, ToKey)
VALUES
(1, 0),
(0, 1), 
(1, 7),
(7, 1),
(3, 4),
(4, 3)

;With FindPath 
AS
(
    SELECT FromKey, ToKey, 0 AS recursionLevel
    FROM RelatedEntities
    WHERE FromKey = 1

    UNION ALL

    SELECT r.FromKey, r.ToKey, recursionLevel = recursionLevel + 1
    FROM RelatedEntities r
    INNER JOIN FindPath b ON r.FromKey = b.ToKey
    WHERE b.ToKey <> 3 AND RecursionLevel < 10
)
SELECT * FROM FindPath
ORDER BY recursionLevel

Note that this returns from 1, to 0, then from 0, to 1, and repeats until I run out of recursion levels.

Giorgos Betsos Giorgos Betsos · Accepted Answer · 2015-03-30T19:12:03

You need to modify your query like this:

DECLARE @startKey UNIQUEIDENTIFIER, @endKey UNIQUEIDENTIFIER;
DECLARE @maxRecursion INT = 100
SET @startKey = '00000000-0000-0000-0000-000000000000';
SET @endKey = 'F7801327-C037-AA93-67D1-B7892F6093A7';

;With FindPath
AS
(
    SELECT FromKey, ToKey, 0 AS recursionLevel
    FROM RelatedEntities
    WHERE FromKey = @startKey

    UNION ALL

    SELECT r.FromKey, r.ToKey, recursionLevel = recursionLevel +1
    FROM RelatedEntities r
    INNER JOIN FindPath b ON r.FromKey = b.ToKey
    WHERE b.ToKey <> @endKey AND recursionLevel < @maxRecursion
)
SELECT * FROM FindPath;

The anchor member of the above CTE:

SELECT FromKey, ToKey, 0 AS recursionLevel
FROM RelatedEntities
WHERE FromKey = @startKey

will select the starting record, T0, of the (From, To) chain of records.

The recursive member of the CTE:

SELECT r.FromKey, r.ToKey, recursionLevel = recursionLevel +1
FROM RelatedEntities r
INNER JOIN FindPath b ON r.FromKey = b.ToKey
WHERE b.ToKey <> @endKey AND recursionLevel < @maxRecursion

will be executed with T0, T1, ... as an input and T1, T2, ... respectively as an output.

This process will continue adding records to the final result set until an empty set is returned from the recursive member, i.e. until a record with ToKey=@endKey has been added to the result set, or @maxRecursion level has been reached.

EDIT:

You can use the following query in order the effectively handle any circular paths:

;With FindPath 
AS
(
    SELECT FromKey, ToKey, 
           0 AS recursionLevel,
           CAST(FromKey AS VARCHAR(MAX)) AS FromKeys
    FROM RelatedEntities
    WHERE FromKey = 1

    UNION ALL

    SELECT r.FromKey, r.ToKey, 
           recursionLevel = recursionLevel + 1,
           FromKeys = FromKeys + ',' + CAST(r.FromKey AS VARCHAR(MAX))
    FROM RelatedEntities r
    INNER JOIN FindPath b ON r.FromKey = b.ToKey
    WHERE (b.ToKey <> 3) 
          AND (RecursionLevel < 10) 
          AND PATINDEX('%,' + CAST(r.ToKey AS VARCHAR(MAX)) + ',%', ',' + FromKeys + ',') = 0  
)
SELECT * FROM FindPath
ORDER BY recursionLevel

Calculated field FromKeys is used to carry on FromKey on to the next recursion level. This way any keys from previous recursion levels are accumulated from level to level using string concatenation. PATINDEX is then used to check whether a circular path has been met.

SQL Fiddle Demo here

Common Table Expressions to retrieve path

1 Answers