sqlite - 使用递归 CTE 寻找最终 parent

Question

我有一个包含子 ID 及其父 ID 的 SQLite 表。给定父项也可能出现在子列中的位置。例如:

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

我想将其从递归结构转换为一个表，其中子项列在一列中，其最终父项(在所有回溯完成后仍然存在的父项)列在另一列中。例如，上表将导致:

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

我知道这应该可以使用 SQLites 递归 CTE，但我在开发查询时遇到了问题。以下是我目前所拥有的，但显然是不完整的。

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

如有任何帮助，我们将不胜感激。

上面示例表的转储

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;

Answer 1

递归步骤必须使用上一步的数据和原始表来计算下一步的数据:

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

并且 CTE 生成所有可能的直接和间接 parent ；你必须过滤掉最终的 parent ，即那些不是 child 的 parent :

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