SQL Server 2008 Recursive query

Question

FromID               ToID     
--------------    ----------    
   1              2               
   2              3                 
   3              4                 
   5              6                
   6              7                
   9              10

I would like to use recursive query in SQL Server 2008 to create an output as

FromID                Path
1                     1,2,3,4
5                     5,6,7                                          
9                     9,10

I have been trying to construct a SQL statement using referring to online examples as below

;WITH items AS (
  SELECT FromID
  , CAST(FromID AS VARCHAR(255)) AS Path
  FROM tablex
  UNION ALL
  SELECT i.FromID
  , CAST(Path + '.' + CAST(i.FromID AS VARCHAR(255)) AS VARCHAR(255)) AS Path
  FROM tablex i
  INNER JOIN items itms ON itms.FromID = i.ToID
)
SELECT * 
FROM items 
ORDER BY Path

However above doesn't work. Any ideas?

Answer 1

It's not entirely clear to me why your expected output is what it is. The path from 6-10 isn't the complete path to 10: that path starts at ID 5. I've written an example that outputs the full path to illustrate how you'd go about doing that. If you really do want it to start at 6 for some reason, then please clearly state the rule that determines which nodes should appear as starting points in the result set.

I noticed that every ID in your sample data has exactly one predecessor but potentially multiple successors. For that reason, I've chosen to start by identifying the nodes that are endpoints, then work backwards to the starting points. Hopefully the code comments below suffice to explain the rest of what's going on.

declare @TableX table (FromID int, ToID int);
insert @TableX values (1, 2), (2, 3), (3, 4), (5, 6), (6, 7), (6, 9), (9, 10);

with PathCTE as
(
    -- BASE CASE
    -- Any ID that appears as a "to" but not a "from" is the endpoint of a path. This
    -- query captures the ID that leads directly to that endpoint, plus the path
    -- represented by that one row in the table.
    select
        X1.FromID,
        [Path] = convert(varchar(max), X1.FromID) + ',' + convert(varchar(max), X1.ToID)
    from
        @TableX X1
    where
        not exists (select 1 from @TableX X2 where X2.FromID = X1.ToID)

    union all

    -- RECURSIVE CASE
    -- For every path previously identified, look for another record in @TableX that
    -- leads to its starting point and prepend that record's from ID to the overall path.
    select
        X.FromID,
        [Path] = convert(varchar(max), X.FromID) + ',' + PathCTE.[Path]
    from
        PathCTE
        inner join @TableX X on PathCTE.FromID = X.ToID
)

-- Any ID that appears as a "from" but not a "to" is the starting point of one or more
-- paths, so we get all results beginning at one of those points. All other output from
-- PathCTE is partial paths, which we can ignore.
select * 
from 
    PathCTE 
where
    not exists (select 1 from @TableX X where PathCTE.FromID = X.ToID)
order by
    FromID, [Path];

Output:

FromID   Path
1        1,2,3,4
5        5,6,7
5        5,6,9,10