结构化查询语言(Structured Query Language): 递归

递归查询概述

在某些情况下，一张表中的行以层级结构或网络结构形式表示，典型的用例包括管理层级、物料清单（如机器由多个部件组成）或网络结构（如航班计划）。为了检索特定行及其所有相关行，可以结合子查询和集合操作将这些行合并到一个结果集中。然而，这种方法存在以下局限性：

必须明确知道层级的数量。
层级数量在不同场景下可能变化，且每一级的查询语法会有所不同。

为解决这些限制，SQL 提供了一种递归查询语法，能够以递归的方式表达查询，从而自动检索所有相关层级的行，而无需明确层级数量。

语法

SQL 标准使用 WITH 子句 的特殊形式来定义递归查询。WITH 子句出现在 SELECT、INSERT、UPDATE 或 DELETE 关键字之前，是这些语句的一部分。

WITH [RECURSIVE] intermediate_table (temp_column_name [,...]) AS 
  (
    SELECT ... FROM real_table          -- 初始查询，获取起点行 (1)
      UNION ALL
    SELECT ... FROM intermediate_table  -- 递归查询，定义如何到达下一层 (2)
  )
SELECT ... FROM intermediate_table;     -- 最终查询，作用于递归结果集 (3)

执行步骤：

初始查询：对实际表或视图执行查询，获取递归的起点。
递归查询：基于中间结果集，执行递归查询。通常是中间表和实际表的连接操作，直到没有新行生成。
合并结果：将初始查询和递归查询的结果合并为一个结果集。
最终查询：对合并结果执行主查询。

示例表

以下是一张表示家庭关系的示例表，用于演示递归查询：

CREATE TABLE family_tree (
  id             DECIMAL      NOT NULL,
  firstname      VARCHAR(50)  NOT NULL,
  lastname       VARCHAR(50)  NOT NULL,
  year_of_birth  DECIMAL      NOT NULL,
  year_of_death  DECIMAL,
  father_id      DECIMAL,
  mother_id      DECIMAL,
  CONSTRAINT family_tree_pk   PRIMARY KEY (id),
  CONSTRAINT family_tree_uniq UNIQUE (father_id, mother_id, firstname),
  CONSTRAINT family_tree_fk1  FOREIGN KEY (father_id) REFERENCES family_tree(id),
  CONSTRAINT family_tree_fk2  FOREIGN KEY (mother_id) REFERENCES family_tree(id),
  CONSTRAINT family_tree_check1 CHECK ( year_of_birth >= 1800 AND year_of_birth < 2100),
  CONSTRAINT family_tree_check2 CHECK ((year_of_death >= 1800 AND year_of_death < 2100) OR year_of_death IS NULL)
);

-- 插入示例数据
INSERT INTO family_tree VALUES ( 1, 'Karl',   'Miller', 1855, 1905, null, null);
INSERT INTO family_tree VALUES ( 2, 'Lisa',   'Miller', 1851, 1912, null, null);
INSERT INTO family_tree VALUES ( 3, 'Ruth',   'Miller', 1878, 1888, 1,    2);
INSERT INTO family_tree VALUES ( 4, 'Helen',  'Miller', 1880, 1884, 1,    2);
INSERT INTO family_tree VALUES ( 5, 'Carl',   'Miller', 1882, 1935, 1,    2);
INSERT INTO family_tree VALUES ( 6, 'John',   'Miller', 1883, 1900, 1,    2);
INSERT INTO family_tree VALUES ( 7, 'Emily',  'Newton', 1880, 1940, null, null);
INSERT INTO family_tree VALUES ( 8, 'Charly', 'Miller', 1908, 1978, 5,    7);
INSERT INTO family_tree VALUES ( 9, 'Deborah','Brown',  1910, 1980, null, null);
INSERT INTO family_tree VALUES (10, 'Chess',  'Miller', 1948, null, 8,    9);
COMMIT;

递归查询示例

示例 1：查询特定人物及其所有后代

以下查询以 "Karl Miller" 为起点，递归查询其所有后代。

WITH intermediate_table (id, firstname, lastname) AS
(
  -- 初始查询：检索起始行
  SELECT id, firstname, lastname
  FROM   family_tree
  WHERE  firstname = 'Karl'
  AND    lastname  = 'Miller'
    UNION ALL
  -- 递归查询：定义如何获取下一层
  SELECT f.id, f.firstname, f.lastname
  FROM   intermediate_table i
  JOIN   family_tree f 
  ON f.father_id = i.id OR f.mother_id = i.id
)
-- 最终查询：输出递归结果
SELECT * FROM intermediate_table;

结果：

ID   FIRSTNAME  LASTNAME
1    Karl       Miller
3    Ruth       Miller
4    Helen      Miller
5    Carl       Miller
6    John       Miller
8    Charly     Miller
10   Chess      Miller

解析：

起始查询：找到 firstname = 'Karl' AND lastname = 'Miller' 的记录。
递归查询：通过 father_id 或 mother_id 与当前中间表 i 中的记录关联，找到下一层后代。
结果合并：递归查询结束后合并所有结果。

递归查询的应用场景

树形结构：如公司管理层级、家谱关系。
物料清单：如复杂机器的部件层级。
网络结构：如航班路线或社交网络关系。

通过递归查询，SQL 能够灵活、高效地处理层级数据，减少复杂查询中的重复逻辑。

SQL递归查询的进一步应用

中间表的进一步处理

SQL允许使用所有语言特性进一步处理递归查询中的中间表（尽管它只是一个具有表结构的中间结果，并不是真实的表）。例如，可以统计后代的数量：

WITH ... -- 与之前相同的递归查询
SELECT count(*) FROM intermediate_table;

递归查询的传统替代方法

如果没有递归查询支持，可以使用子查询和集合操作。以下查询通过子查询手动检索 "Karl Miller" 和他的子女：

-- 检索 Karl Miller 本人
SELECT * 
FROM   family_tree
WHERE  firstname = 'Karl'
AND    lastname  = 'Miller'
  UNION ALL
-- 检索 Karl 的子女
SELECT * 
FROM   family_tree
WHERE  father_id IN (
  SELECT id
  FROM   family_tree
  WHERE  firstname = 'Karl'
  AND    lastname  = 'Miller'
);

问题：如果需要检索孙辈，就需要嵌套更多的子查询，从而导致语法复杂且难以维护。

逆向遍历层级

以下示例从指定人物（如 "Chess Miller"）开始，逆向追溯其父系祖先。

WITH intermediate_table (id, father_id, firstname, lastname) AS
(
  -- 起始查询
  SELECT id, father_id, firstname, lastname
  FROM   family_tree
  WHERE  firstname = 'Chess'
  AND    lastname  = 'Miller'
    UNION ALL
  -- 递归查询，定义逆向层级关系
  SELECT f.id, f.father_id, f.firstname, f.lastname
  FROM   intermediate_table i
  JOIN   family_tree f ON f.id = i.father_id
)
SELECT * FROM intermediate_table;

显示层级（Hierarchy Level）

有时需要知道每一行属于层级中的第几层，可以通过在递归查询中引入一个伪列 hier_level 来表示。

WITH intermediate_table (id, firstname, lastname, hier_level) AS
(
  -- 设置起始层级为 0
  SELECT id, firstname, lastname, 0 AS hier_level
  FROM   family_tree
  WHERE  firstname = 'Karl'
  AND    lastname  = 'Miller'
    UNION ALL
  -- 每次递归层级加 1
  SELECT f.id, f.firstname, f.lastname, i.hier_level + 1
  FROM   intermediate_table i
  JOIN   family_tree f ON f.father_id = i.id OR f.mother_id = i.id
)
SELECT * FROM intermediate_table;

通过 hier_level 列可以对结果进行筛选，例如仅显示前两层的结果：

SELECT * FROM intermediate_table WHERE hier_level < 2;

或者在递归查询中直接限制层级：

WITH intermediate_table (id, firstname, lastname, hier_level) AS
(
  SELECT id, firstname, lastname, 0 AS hier_level
  FROM   family_tree
  WHERE  firstname = 'Karl'
  AND    lastname  = 'Miller'
    UNION ALL
  SELECT f.id, f.firstname, f.lastname, i.hier_level + 1
  FROM   intermediate_table i
  JOIN   family_tree f ON f.father_id = i.id OR f.mother_id = i.id
  WHERE  hier_level < 1 -- 限制递归层级
)
SELECT * FROM intermediate_table;

生成路径

有时需要从层级起点到当前行的路径。例如，可以为每一行生成类似 1.5.3 的分面分类路径。

WITH intermediate_table (id, firstname, lastname, hier_level, hier_path) AS
(
  -- 起始路径为当前姓名
  SELECT id, firstname, lastname, 0 AS hier_level, firstname AS hier_path
  FROM   family_tree
  WHERE  firstname = 'Karl'
  AND    lastname  = 'Miller'
    UNION ALL
  -- 每次递归在路径后追加当前姓名
  SELECT f.id, f.firstname, f.lastname, i.hier_level + 1, 
         CONCAT(CONCAT(i.hier_path, ' / '), f.firstname)
  FROM   intermediate_table i
  JOIN   family_tree f ON f.father_id = i.id OR f.mother_id = i.id
)
SELECT * FROM intermediate_table;

示例输出：

ID   FIRSTNAME   LASTNAME   HIER_LEVEL   HIER_PATH
1    Karl        Miller     0            Karl
5    Carl        Miller     1            Karl / Carl
8    Charly      Miller     2            Karl / Carl / Charly
10   Chess       Miller     3            Karl / Carl / Charly / Chess

深度优先与广度优先

在层级或网络中有两种遍历方式：

深度优先（Depth First）：优先处理子节点（下一层级的节点）。
广度优先（Breadth First）：优先处理同一层级的节点（默认）。

SQL允许通过关键字 DEPTH FIRST 或 BREADTH FIRST 来选择遍历方式：

WITH intermediate_table (id, firstname, lastname, hier_level) AS
(
  SELECT id, firstname, lastname, 0 AS hier_level
  FROM   family_tree
  WHERE  firstname = 'Karl'
  AND    lastname  = 'Miller'
    UNION ALL
  SELECT f.id, f.firstname, f.lastname, i.hier_level + 1
  FROM   intermediate_table i
  JOIN   family_tree f ON f.father_id = i.id OR f.mother_id = i.id
)
SEARCH DEPTH FIRST BY firstname SET sequence_number -- 深度优先
SELECT * FROM intermediate_table;

备注：

遍历顺序：深度优先会优先处理当前节点的子节点；广度优先会优先处理同一层级的所有节点。
排序依据：使用 BY <column_name> 指定排序规则，例如按 firstname 排序。
序列号：通过 SET <sequence_number> 为所有行生成一个全局序列号。

递归查询是处理复杂层级结构的强大工具，能够在不明确层级深度的情况下灵活地检索和操作数据。

Last modified: Tuesday, 28 January 2025, 2:28 PM