递归的 CTE 向上和向后？如何从任何节点获取整棵树？

Question

给出一个非常简单的 table 比如：

-- SQLite3
CREATE TABLE tst (
    id INTEGER PRIMARY KEY AUTOINCREMENT, 
    parent_id INTEGER CHECK (parent_id <> id),
    tag STRING NOT NULL, 
    FOREIGN KEY (parent_id) REFERENCES tst(id)
    )

我可以使用 WITH RECURSIVE（常见的 table 表达式）从任何节点到该树的 "root" 或从一个节点向下遍历到它的所有子节点（沿所有分支机构）。以下是似乎适用于这两种情况的查询（分别）：

    WITH RECURSIVE t(id, parent_id, tag) AS (
        SELECT id, parent_id, tag FROM tst WHERE id=:mynode
      UNION ALL
        SELECT t2.id, t2.parent_id, t2.tag FROM tst AS t2
        JOIN t ON t.parent_id = t2.id
    ) SELECT * FROM t

...和：

    WITH RECURSIVE t(id, parent_id, tag) AS (
        SELECT id, parent_id, tag FROM tst WHERE id=?
      UNION ALL
        SELECT t2.id, t2.parent_id, t2.tag FROM tst AS t2
        JOIN t ON t.id = t2.parent_id
    ) SELECT * FROM t

（我所做的只是将 t.parent_id 和 t2.id 从第一个示例反转到另一个）。

这很有魅力。但我正在努力思考如何从任何节点开始并获取整组行。

明显的解决方法是执行第一个查询，找到 parent_id IS NULL 所在的行，然后对其执行第二个查询。但我想一定有更优雅的解决方案。

这是什么？

Answer 1

好的，我已经花了一些时间在 SQLFiddle: PostgreSQL: CTE 上，这似乎有效：

-- SQL: Fetch whole tree
WITH RECURSIVE t (id, parent_id, tag) AS
 (
  SELECT id, parent_id, tag FROM tst WHERE id =
   (
    WITH RECURSIVE t3 (id, parent_id) AS
     (
      SELECT id, parent_id FROM tst WHERE id = :mynode
      UNION ALL
      SELECT t2.id, t2.parent_id FROM tst AS t2
      JOIN t3 ON t3.parent_id=t2.id 
     ) SELECT id FROM t3 WHERE parent_id IS NULL
   ) UNION ALL
     SELECT t2.id, t2.parent_id, t2.tag FROM tst AS t2
     JOIN t ON t.id = t2.parent_id
 ) SELECT * FROM t ORDER BY id;

... 其中 :mynode 是给定行树中任何节点的 ID。

我所做的就是进行第一个查询（沿着树向上走），添加 WHERE parent_id IS NULL 以获取整棵树的父级，然后将其粘贴到 IN (...) 表达式中。（在这种情况下，我也可以只使用 = 而不是 IN）。

这看起来还是有点，嗯，...涉及。但它似乎确实有效。

有没有更好的方法？

Answer 2

我发现我之前的 RCTE 查询有效，但我的应用程序有两个主要缺陷。

我没有捕捉每一行的深度；所以我不能轻易缩进我的条目来反映线程嵌套级别
我的 ORDER BY 子句完全偏离基础...所以即使我根据其嵌套深度缩进每一行，结果 "outline summary" 也会完全错误。

这个稍微复杂的查询似乎可以解决这两个问题：

WITH RECURSIVE tree (id, parent_id, tag, depth, path) AS (
  SELECT id, parent_id, tag, 1 AS depth, '' AS path FROM tst WHERE id = (
    WITH RECURSIVE t3 (id, parent_id) AS (
      SELECT id, parent_id FROM tst WHERE id = :mynode
      UNION ALL
      SELECT t2.id, t2.parent_id FROM tst AS t2
      JOIN t3 ON t3.parent_id=t2.id
     ) SELECT id FROM t3 WHERE parent_id IS NULL
   ) UNION ALL
     SELECT t2.id, t2.parent_id, t2.tag, tree.depth+1,
        path || '/' || CAST(t2.id AS VARCHAR) FROM tst AS t2
     JOIN tree ON tree.id = t2.parent_id
 ) SELECT * FROM tree ORDER by path;

...所以似乎不允许我在此处标记代码的内容...但我将 depth 和 path 列添加到 "tree"（CTE 虚拟）table，为我的第一个 SELECT 中的那些（虚拟）列提供初始值（使用 1 AS depth, '' AS path（这对我来说是一个新技巧），并且然后通过 tree.depth+1, path || '/' || CAST(t2.id AS VARCHAR) 在递归的每一步修改它们；然后，最后我可以将 path 用于我的 ORDER BY 并使用我的应用程序中的深度为每一行添加适当级别的前缀缩进。

为了使它适用于我的应用程序，我可以执行以下操作：

#!python
for each in db.execute("SELECT id FROM tst WHERE parent_id IS NULL").fetchall():
    for row in db.execute(qry, each):
        print("%s\t%s%s" % (row[0], '  ' * row[3], row[2]))

... 其中 qry 是我在上面描述的查询（实际上已调整为仅获取感兴趣的列，但此示例即使在 * 下也能正常工作）。在实践中，我可能会使用 LIMIT 和 OFFSET 来翻阅这些结果（就像我已经对 table 的不支持任何消息线程的结果的平面列表所做的那样）。

我还知道，我为此在 table 模式上设置的 CHECK 只是阻止了最简单的循环树形式。似乎 parent_id INTEGER CHECK (parent_id IS NULL or parent_id < id) 应该更好用。（parent_id -> id 链接的每个链必须单调递减......所以不可能有循环。FOREIGN KEY 强制属性 for INSERT 语句已经......但此检查实施也适用于 UPDATE。（从技术上讲，我想我应该在实际应用程序中使用 "date" 字段，但我希望代理键就足够了）。

顺便说一句：为这篇文章向 a_horse_with_no_name 大声疾呼：https://dba.stackexchange.com/a/7150 ... 这帮助我弄清楚了如何构建路径。

递归的 CTE 向上和向后？如何从任何节点获取整棵树？

CTE WITH RECURSIVE Up and back? How do I get the whole tree from any node?

sql

sqlite

common-table-expression

recursive-query