使用递归 CTE 找到最终 parents

Question

我有一个 SQLite table 的 child 个 ID 及其 parent 个 ID。其中给定的 parent 也可能出现在 child 列中。例如：

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

我想将其从递归结构转换为 table，其中 child 列在一列中，其最终 parent（parent在所有回收完成后仍然存在）列在另一个中。例如，上面的 table 将导致：

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;

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

上述示例table的转储

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

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

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

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

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

使用递归 CTE 找到最终 parents

finding ultimate parents with recursive CTE

sqlite

recursive-query

common-table-expression