T-sql – Recursively get ids of tree

cterecursivet-sql

I have a table foo.

enter image description here

So we have a hiearchical object structure where on foo has one parent (or none) and a list of children.

What I want is a sql statement that lists all id:s that can be found either traversing upwards and downwards in that hierarchy.

How?

My current attempt is

CREATE PROCEDURE [dbo].[GetChain]
    @starting_id int
AS
BEGIN
    WITH chainIDsUpwards AS
    (
        SELECT id, parent_id FROM foo
        WHERE parent_id IS NULL

        UNION ALL

        SELECT foo.id, foo.parent_id FROM foo
        JOIN chainIDsUpwards p ON foo.parent_id = p.id
    ),
    chainIDsDownwards AS
    (
        SELECT id, parent_id FROM foo

        UNION ALL

        SELECT foo.id, foo.parent_id FROM foo
        JOIN chainIDsDownwards c ON foo.id = c.parent_id
    )

    SELECT * FROM chainIDsUpwards WHERE id = @starting_id
    UNION
    SELECT * FROM chainIDsDownwards WHERE id = @starting_id
END

but it does only give me a single row.

edit

Sample data:

sample data

EXEC [GetChain] @starting_id = 5

returns

only one row as result

but I expect:

  • 5, 2
  • 2, 1
  • 1, null
  • 11, 5

Fiddle at https://dbfiddle.uk/?rdbms=sqlserver_2019&fiddle=aeaf40c57b3940ce725dccf553a8d9e2

edit 2

I thought I had found the correct sql being

CREATE PROCEDURE [dbo].[GetChain]
    @starting_id int
AS
BEGIN
    WITH chainIDsUpwards AS
    (
        SELECT id, parent_id FROM foo WHERE id = @starting_id

        UNION ALL

        SELECT foo.id, foo.parent_id FROM foo
        JOIN chainIDsUpwards p ON p.id = foo.parent_id
    ),
    chainIDsDownwards AS
    (
        SELECT id, parent_id FROM foo WHERE parent_id = @starting_id

        UNION ALL

        SELECT foo.id, foo.parent_id FROM foo
        JOIN chainIDsDownwards c ON foo.id = c.parent_id
    ),
    chainIDs AS
    (
        SELECT id FROM chainIDsUpwards
        UNION
        SELECT id FROM chainIDsDownwards
    )

    SELECT id FROM chainIDs
END

but that will not find any parents for 9. It only finds 9 itself, but not 3 or 1.

Fiddle at https://dbfiddle.uk/?rdbms=sqlserver_2019&fiddle=10041653e78b52bc8ec0e3c40cfff7a0

Best Answer

Basically, you need to move your @starting_id predicate to the base case of the recursive part:

WITH chainIDsUpwards AS
(
    SELECT id, parent_id FROM foo
    WHERE id = @starting_id

    UNION ALL

    SELECT foo.id, foo.parent_id FROM foo
    JOIN chainIDsUpwards p ON foo.id = p.parent_id
)
SELECT * FROM chainIDsUpwards;

If you put the predicate as:

SELECT * FROM chainIDsUpwards WHERE ...;

it will filter all rows that do not satisfy the predicate.

I also believe that you need to change the join clause in both cte:s if you want the behavior to correspond with the name. I find it easier mentally to start with the cte in the join like:

SELECT foo.id, foo.parent_id 
FROM chainIDsUpwards p
JOIN foo 
    ON p.parent_id = foo.id

Fiddle

Related Question