Kodokon kodokon.com

递归查询（WITH RECURSIVE）：层级与图

用 WITH RECURSIVE 遍历树和图，掌握深度与环的检测。

11 分钟 · 3 题

在 Kodokon 中打开本课

递归 CTE 由 UNION ALL 连接的两部分组成：一个提供起始行的锚点项，以及一个引用 CTE 自身的递归项。SQLite 先运行一次锚点，然后在新产生的行上循环应用递归项，直到不再产生任何行为止。让我们创建一个经理的层级结构来说明它。

SQL
CREATE TABLE employees (
  id INTEGER PRIMARY KEY,
  name TEXT NOT NULL,
  manager_id INTEGER
);

INSERT INTO employees (id, name, manager_id)
VALUES
  (1, 'Ada',    NULL),
  (2, 'Grace',  1),
  (3, 'Alan',   2),
  (4, 'Edsger', 2);
Ada 管理 Grace，Grace 管理 Alan 和 Edsger。

为了展开 Ada 之下的组织架构图，锚点选出根节点，深度为 0，而递归项则把每位员工与已经存在于 CTE 中的经理连接起来，并把深度加一。你自己计算的 depth 列，是衡量层级深浅的最简单方式。

SQL
WITH RECURSIVE chain(id, name, depth) AS (
  SELECT id, name, 0
  FROM employees
  WHERE id = 1
  UNION ALL
  SELECT e.id, e.name, c.depth + 1
  FROM employees e
  JOIN chain c ON e.manager_id = c.id
)
SELECT id, name, depth FROM chain;
Ada 0，Grace 1，Alan 2，Edsger 2。

图由一张边表 (src, dst) 来建模。遍历遵循同样的机制，但一个图可能包含环：沿着 1 -> 2 -> 3 -> 1 会永远循环下去。补救办法是在一个文本列里记住已经走过的路径，并拒绝任何已经访问过的节点。instr 函数会在这条路径中，在两个点之间查找某个节点。

SQL
CREATE TABLE edges (
  src INTEGER NOT NULL,
  dst INTEGER NOT NULL
);

INSERT INTO edges (src, dst) VALUES
  (1, 2), (2, 3), (3, 1), (2, 4);

WITH RECURSIVE walk(node, path) AS (
  SELECT 1, '.1.'
  UNION ALL
  SELECT e.dst,
         w.path || e.dst || '.'
  FROM edges e
  JOIN walk w ON e.src = w.node
  WHERE instr(w.path, '.' || e.dst || '.') = 0
)
SELECT node, path FROM walk;
路径 '.1.2.3.' 阻止了返回到 1。

知识检测

确认你已牢记本课的重点内容。

  1. 在一个递归 CTE 中，哪个运算符把锚点项和递归项连接起来？
    • UNION ALL（或 UNION）
    • JOIN
    • INTERSECT
    • CROSS APPLY
  2. 为什么一个有环的图在使用 UNION ALL 时有无限递归的风险？
    • 因为 UNION ALL 会系统性地对结果排序
    • 因为相同的节点会被反复访问而不去重
    • 因为 SQLite 在递归期间禁用了索引
    • 因为锚点在每一轮都被重新求值
  3. 在 SQLite 中遍历一个有环的图时，如何避免无限循环？
    • 在递归项里加一个 ORDER BY
    • 记住走过的路径并排除已访问过的节点
    • 使用标准的 CYCLE 子句
    • 增大内存缓存的大小