CODEWITHSUNDEEP
sqlitecommon-table-expressionrecursive-query
Chris
Chris

Reputation: 1353

finding ultimate parents with recursive CTE

I have an SQLite table of child IDs and their parent ID. Where a given parent may also appear in the child column. For example:

child    parent
-----    ------
3        4
2        3
1        2
5        4
7        8
6        7

I would like to transform this from the recursive structure to a table where the child is listed in one column and its ultimate parent (the parent that remains after all recusing is done) is listed in the other. For example, the above table would result in:

child    ultimate_parent
-----    ---------------
3        4
2        4
1        4
5        4
7        8
6        8

I understand that this should be possible using SQLites Recursive CTEs, but I am having trouble developing the query. Below is what I have so far, but it is obviously incomplete.

WITH RECURSIVE rel(child, parent) AS (
        SELECT child, parent FROM relationships
        UNION ALL
        SELECT child, parent FROM rel
    )
    SELECT * FROM rel;

Any help would be much appreciated.

A dump for the example table above

PRAGMA foreign_keys=OFF;
BEGIN TRANSACTION;
CREATE TABLE `relationships` (
    `child` INTEGER,
    `parent`    INTEGER
);
INSERT INTO relationships VALUES(3,4);
INSERT INTO relationships VALUES(2,3);
INSERT INTO relationships VALUES(1,2);
INSERT INTO relationships VALUES(5,4);
INSERT INTO relationships VALUES(7,8);
INSERT INTO relationships VALUES(6,7);
COMMIT;

Upvotes: 3

Views: 1441

Answers (1)

CL.
CL.

Reputation: 180080

The recursion step must use the data from the previous step and the original table to compute the data for the next step:

WITH RECURSIVE ...
    ...
    UNION ALL
    SELECT rel.child,
           relationships.parent
    FROM relationships
    JOIN rel ON rel.parent = relationships.child
)

And the CTE generates all possible direct and indirect parents; you have to filter out the ultimate parents, i.e., those parents that aren't children:

WITH ...
SELECT *
FROM rel
WHERE parent NOT IN (SELECT child
                     FROM relationships);

Upvotes: 2

Related Questions