结构化查询语言(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>
为所有行生成一个全局序列号。
递归查询是处理复杂层级结构的强大工具,能够在不明确层级深度的情况下灵活地检索和操作数据。