sql - CTE WITH RECURSIVE Up and back？如何从任何节点获取整棵树？

Question

给定一个非常简单的表格，例如:

-- 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 (公共(public)表表达式)从任何节点向上到该树的“根”，或者从一个节点向下遍历到它的所有子节点(沿着所有分支)。以下是似乎适用于这两种情况的查询(分别):

    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

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

我没有捕捉每一行的深度；所以我不能轻易缩进我的条目以反射(reflect)线程嵌套级别

我的 ORDER BY子句完全偏离了基础......所以即使我根据嵌套深度缩进每一行，生成的“大纲摘要”也是完全错误的。

这个稍微复杂的查询似乎解决了这两个问题:

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 “树”(CTE 虚拟)表的列，为我的第一个 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 对这些结果进行分页(正如我已经对不支持任何消息线程的表中的结果的平面列表所做的那样)。

我也知道 CHECK我放置表模式只是为了防止最简单的循环树形式。好像是 parent_id INTEGER CHECK (parent_id IS NULL or parent_id < id)应该工作得更好。 (每条 parent_id -> id 链接链都必须单调递减......所以不可能有循环。 FOREIGN KEY 已经为 INSERT 语句强制执行该属性......但此检查强制执行也适用于 UPDATE。 (技术上我想我应该在我的实际应用程序中使用“日期”字段，但我希望代理键就足够了)。

顺便说一句:大喊:a_horse_with_no_name 这篇帖子: https://dba.stackexchange.com/a/7150 ...这帮助我弄清楚了如何构建路径。