Search code examples
mysqlrecursioncommon-table-expressionrecursive-query

MySQL8 query whole bloodline (ancestors + descendants) of a hierarchy


MySQL8 allows using with syntax to query hierarchical structures. For instance, querying all ancestors of an item. Conversely, all descendants also can be queried recursively.

enter image description here

I'm looking for a query that combines these two aspects: a query of all descendants, ancestors, and optimally the item self (see at the included graphic, all colorized items). Actually, you also could say, all items without the siblings of all ancestors. I think we could say "bloodline". It's possible just to union the two results but I need a solution without union.

Is that possible at all? I would welcome any approach.

For an overview, my union attempt. Note, that there's currently an error, some parent_id are wrong; I'm working on that)

(with recursive cte as (
    SELECT id, parent_id
    from categories
    where id = 'C2'
    union all
    select t.parent_id, cte.id
    from cte
             inner join categories t on t.id = cte.parent_id
    where cte.id is not null
)
 select id, parent_id
 from cte
 where cte.id is not null)

union

(with recursive cte as (
    SELECT id, parent_id
    from categories
    where id = 'C2'
    union all
    select t.id, cte.parent_id
    from cte
             inner join categories t on t.parent_id = cte.id
)
 select id, parent_id
 from cte);

and the data for the given diagram.

INSERT INTO categories (id, parent_id) VALUES ('A1', null);
INSERT INTO categories (id, parent_id) VALUES ('B1', 'A1');
INSERT INTO categories (id, parent_id) VALUES ('B2', 'A1');
INSERT INTO categories (id, parent_id) VALUES ('B3', 'A1');
INSERT INTO categories (id, parent_id) VALUES ('C1', 'B2');
INSERT INTO categories (id, parent_id) VALUES ('C2', 'B2');
INSERT INTO categories (id, parent_id) VALUES ('D1', 'C1');
INSERT INTO categories (id, parent_id) VALUES ('D2', 'C1');
INSERT INTO categories (id, parent_id) VALUES ('D3', 'C2');
INSERT INTO categories (id, parent_id) VALUES ('D4', 'C2');
INSERT INTO categories (id, parent_id) VALUES ('D5', 'C2');
INSERT INTO categories (id, parent_id) VALUES ('E1', 'D5');

Expected output

id,parent_id
C2,B2
A1,null
B2,A1
D3,C2
D4,C2
D5,C2
E1,D5

Solution

  • You can do it with 1 recursive CTE, if you include both conditions for the ancestors and descendants in the ON clause.
    You will need another column type which indicates whether each row is for an ancestor or descendant:

    WITH RECURSIVE cte AS (
        SELECT id, parent_id, 0 type
        FROM categories
        WHERE id = 'C2'
        UNION ALL
        SELECT t.id, t.parent_id,
               CASE WHEN c.parent_id = t.id THEN -1 ELSE 1 END
        FROM categories t INNER JOIN cte c
        ON c.parent_id = t.id OR c.id = t.parent_id
        WHERE (type = 0) 
           OR (c.parent_id = t.id AND type = -1) 
           OR (c.id = t.parent_id AND type = 1)
    )
    SELECT id, parent_id FROM cte
    

    See the demo.