2

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

4
2

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

1

Just for funsies.

Rather than having two subqueries (one for ancestors and one for descendants), my preference is to map the entire hierarchy in a single statement and search above and below in the node in question based on that.

Given an additional computed column marking parentless (or self-parent) entities as "is_root = 1", for a hierarchy of the form...

 1
 |\
 2 3
  / \
 7   4

 5
  \
   6

...my example code would be...

CREATE PROCEDURE [dbo].[GetChain]
    @starting_id int
AS
BEGIN
-- https://dba.stackexchange.com/q/273695/68127
    WITH cte AS (
        SELECT 
            id, 
            parent_id,
            depth = 0,
            '/'+convert(varchar(max),id) as _path
        FROM foo
        WHERE is_root = 1
        UNION ALL
        SELECT 
            foo.id, 
            foo.parent_id,
            depth + 1,
            _path + '/'+convert(varchar(max),foo.id)
        FROM cte
        JOIN foo ON foo.parent_id = cte.id
        where cte.depth < 100 -- i can never remember the maxrecursion hint syntax
            and foo.is_root = 0
    )
    SELECT * 
    FROM cte 
    where exists ( -- children (and self)
        select 1
        from string_split(_path,'/') ss
        where ss.value = @starting_id
    ) or cte.id in ( -- parents (and self)
        select ss.[value]
        from cte b
        cross apply string_split(b._path,'/') ss
        where b.id = @starting_id
    )
    order by _path
END

... which gives us...

exec getChain 3;
/*
we expect the following nodes

 1
  \
   3
  / \
 7   4
 
2 is excluded because it is a sibling of 3, 
but not an ancestor or descendant
*/

Full db<>fiddle

5
  • Too bad I cannot freely add the column is_root! – Anders Lindén Aug 13 '20 at 13:57
  • That is a bummer; but you can drop-in replace it with the expression given in the computed column in the fiddle iif(id=parent_id,1,0)), although you may need to be sensible about scoping issues. Probably makes more sense (and is definitely more human readable) to just use the original expression id=parent_id, really – Peter Vandivier Aug 13 '20 at 14:00
  • What's the difference between is_root = 1 and parent_id is null? – Lennart Aug 13 '20 at 15:10
  • @Lennart none really. i just prefer marking root entities as own-parent rather than null-parent in these scenarios. It allows for the parent_id column to be set not null as well. – Peter Vandivier Aug 13 '20 at 15:20
  • You dont need an extra attribute in that case either, id = parent_id is sufficient. – Lennart Aug 13 '20 at 15:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.