SQL递归查询方法简介及示例

计算机技术
作者

zenggyu

发布日期

2020-08-30

摘要
介绍SQL递归查询的写法，并提供一些例子。

引言

假设有这么一家机构，它拥有华东和华南两大区域级分支，该两大分支下又拥有若干省（或直辖市）级、市级、区级分支，且这些分支的关系如下所示。

.
├── 华东
│   ├── 江苏省
│   │   └── 南京市
│   │       ├── 鼓楼区
│   │       └── 秦淮区
│   ├── 上海市
│   │   └── 浦东新区
│   └── 台湾省
└── 华南
    └── 广东省
        └── 广州市
            ├── 海珠区
            └── 黄埔区

如果为每个分支指定一个标识，并构建一个表用以表示上述关系，那么结果将如branch表所示；其中，branch_id属性记录了的是分支的标识，branch_name属性记录了分支名称，而parent_branch属性记录的则是上一级别分支的标识。

              branch
+---------+-----------+-------------+
|branch_id|branch_name|parent_branch|
+---------+-----------+-------------+
|1        |华东       |NULL         |
|2        |华南       |NULL         |
|11       |上海市     |1            |
|111      |浦东新区   |11           |
|12       |江苏省     |1            |
|121      |南京市     |12           |
|1211     |鼓楼区     |121          |
|1212     |秦淮区     |121          |
|13       |台湾省     |1            |
|21       |广东省     |2            |
|211      |广州市     |21           |
|2111     |海珠区     |211          |
|2112     |黄埔区     |211          |
+---------+-----------+-------------+

现在，请考虑如何使用SQL实现以下查询：

  • 找出华东分支及其所有下级分支；
  • 找出华东分支的所有下二级分支；
  • 找出华东分支的所有最下级分支；
  • 找出黄埔区分支的所有上级分支；
  • 找出黄埔区分支的最上级分支；
  • 为每个分支列出其自身及所有下级分支；
  • …

经常与关系型数据库打交道的人往往都遇到过类似上面描述的问题。这类问题带有递归性质，使用一般的查询难以解决；但幸运的是，SQL标准定义了递归查询方法，并且现在许多关系型数据库管理系统均提供了相应的实现，可以帮助我们解决该类问题。本文的目的在于介绍SQL递归查询的一般形式和执行过程，并在PostgreSQL中以branch表所示数据（本文附录提供了生成该表所需的SQL语句）为例介绍前面提到的各种查询的具体写法。

注：由于SQL标准中定义的递归查询是基于公共表表达式（common table expression, CTE）实现的，所以在阅读下文之前请先确保你已经了解CTE的基本概念和用法。

递归查询的一般形式

递归查询是通过在CTE中添加RECURSIVE关键字实现的，其一般形式如下：

WITH RECURSIVE cte_name AS (
  non_recursive_term
  UNION [ALL]
  recursive_term
)
invocation_statement

其中，cte_name是用于实现递归查询的一个公共表表达式的名称；non_recursive_term和recursive_term分别被称为非递归项和递归项，它们返回的结果需要以UNION或UNION ALL取并集；而invocation_statement则是公共表表达式的调用语句。一般来说，non_recursive_term、recursive_term和invocation_statement都是SELECT语句。

以下是一个简单的递归查询示例，其作用是求数列\([1, 2, ..., 99, 100]\)的和：

WITH RECURSIVE t AS (
  SELECT 1 AS n
  UNION ALL
  SELECT n + 1 AS n
  FROM t
  WHERE n < 100
)
SELECT sum(n) AS sum
FROM t;

其输出结果为：

+----+
|sum |
+----+
|5050|
+----+

在这个例子中，t中的递归项存在着对t的递归自引用（recursive self-reference），这正是我们将其称为递归项的原因。

递归查询的执行过程

递归查询的执行过程如下(The PostgreSQL Global Development Group 2020)1：

1 本文对递归查询执行过程的描述主要参考了PostgreSQL官方文档中的相关描述，并在此基础上根据个人见解做了改动，希望能使之更容易被理解。

  1. 执行非递归项，将返回的结果记为\(R_i\)（此时\(i = 0\)）。
  2. 重复以下步骤，直至满足递归终止条件：
    1. 检查\(R_i\)是否为空，如果为空则终止递归，直接跳到步骤3。
    2. 将\(R_i\)替换递归项中的递归自引用，然后执行递归项，并将其返回的结果记为\(R_{i+1}\)。
    3. 记\(i = i + 1\)。
  3. 取各个结果集（\(R_0, ..., R_i\)）的并集（如果使用了UNION而非UNION ALL，则需去除重复记录），作为最终结果。

递归查询写法示例

找出华东分支（branch_id = 1）及其所有下级分支

WITH RECURSIVE
  t1 AS (
    SELECT branch_id, branch_name
    FROM branch
    WHERE branch_id = 1
    UNION
    SELECT branch.branch_id, branch.branch_name
    FROM
      t1
      INNER JOIN
        branch ON t1.branch_id = branch.parent_branch
  )
SELECT branch_id, branch_name
FROM t1;

上述语句的输出结果为：

+---------+-----------+
|branch_id|branch_name|
+---------+-----------+
|1        |华东       |
|11       |上海市     |
|12       |江苏省     |
|13       |台湾省     |
|111      |浦东新区   |
|121      |南京市     |
|1211     |鼓楼区     |
|1212     |秦淮区     |
+---------+-----------+

找出华东分支（branch_id = 1）的所有下二级分支

WITH RECURSIVE t1 AS (
  SELECT branch_id, branch_name, 0 AS rel_level
  FROM branch
  WHERE branch_id = 1
  UNION
  SELECT branch.branch_id, branch.branch_name, rel_level + 1 AS rel_level
  FROM
    t1
    INNER JOIN branch ON t1.branch_id = branch.parent_branch
)
SELECT branch_id, branch_name
FROM t1
WHERE
  rel_level = 2;

上述语句的输出结果为：

+---------+-----------+
|branch_id|branch_name|
+---------+-----------+
|111      |浦东新区   |
|121      |南京市     |
+---------+-----------+

找出华东分支（branch_id = 1）的所有最下级分支

WITH RECURSIVE t1 AS (
  SELECT branch_id, branch_name, parent_branch
  FROM branch
  WHERE branch_id = 1
  UNION
  SELECT branch.branch_id, branch.branch_name, branch.parent_branch
  FROM
    t1
    INNER JOIN branch ON t1.branch_id = branch.parent_branch
)
SELECT branch_id, branch_name
FROM t1 AS ta
WHERE
  NOT exists(SELECT 1 FROM t1 AS tb WHERE ta.branch_id = tb.parent_branch);

上述语句的输出结果为：

+---------+-----------+
|branch_id|branch_name|
+---------+-----------+
|13       |台湾省     |
|111      |浦东新区   |
|1211     |鼓楼区     |
|1212     |秦淮区     |
+---------+-----------+

找出黄埔区分支（branch_id = 2112）的所有上级分支

WITH RECURSIVE t1 AS (
  SELECT branch_id, branch_name, parent_branch
  FROM branch
  WHERE branch_id = 2112
  UNION
  SELECT branch.branch_id, branch.branch_name, branch.parent_branch
  FROM
    t1
    INNER JOIN branch ON t1.parent_branch = branch.branch_id
)
SELECT branch_id, branch_name
FROM t1
WHERE branch_id != 2112;

上述语句的输出结果为：

+---------+-----------+
|branch_id|branch_name|
+---------+-----------+
|211      |广州市     |
|21       |广东省     |
|2        |华南       |
+---------+-----------+

找出黄埔区分支（branch_id = 2112）的最上级分支

WITH RECURSIVE t1 AS (
  SELECT branch_id, branch_name, parent_branch
  FROM branch
  WHERE branch_id = 2112
  UNION
  SELECT branch.branch_id, branch.branch_name, branch.parent_branch
  FROM
    t1
    INNER JOIN branch ON t1.parent_branch = branch.branch_id
)
SELECT branch_id, branch_name
FROM t1
WHERE
  parent_branch IS NULL;

上述语句的输出结果为：

+---------+-----------+
|branch_id|branch_name|
+---------+-----------+
|2        |华南       |
+---------+-----------+

为每个分支列出其自身及所有下级分支

WITH RECURSIVE t1 AS (
  SELECT branch_id AS anchor_id, branch_name AS anchor_name, branch_id, branch_name
  FROM branch
  UNION
  SELECT t1.anchor_id, t1.anchor_name, branch.branch_id, branch.branch_name
  FROM
    t1
    INNER JOIN branch ON t1.branch_id = branch.parent_branch
)
SELECT anchor_id, anchor_name, branch_id, branch_name
FROM t1
ORDER BY
  anchor_id, branch_id;

上述语句的输出结果为：

+---------+-----------+---------+-----------+
|anchor_id|anchor_name|branch_id|branch_name|
+---------+-----------+---------+-----------+
|1        |华东       |1        |华东       |
|1        |华东       |11       |上海市     |
|1        |华东       |12       |江苏省     |
|1        |华东       |13       |台湾省     |
|1        |华东       |111      |浦东新区   |
|1        |华东       |121      |南京市     |
|1        |华东       |1211     |鼓楼区     |
|1        |华东       |1212     |秦淮区     |
|2        |华南       |2        |华南       |
|2        |华南       |21       |广东省     |
|2        |华南       |211      |广州市     |
|2        |华南       |2111     |海珠区     |
|2        |华南       |2112     |黄埔区     |
|11       |上海市     |11       |上海市     |
|11       |上海市     |111      |浦东新区   |
|12       |江苏省     |12       |江苏省     |
|12       |江苏省     |121      |南京市     |
|12       |江苏省     |1211     |鼓楼区     |
|12       |江苏省     |1212     |秦淮区     |
|13       |台湾省     |13       |台湾省     |
|21       |广东省     |21       |广东省     |
|21       |广东省     |211      |广州市     |
|21       |广东省     |2111     |海珠区     |
|21       |广东省     |2112     |黄埔区     |
|111      |浦东新区   |111      |浦东新区   |
|121      |南京市     |121      |南京市     |
|121      |南京市     |1211     |鼓楼区     |
|121      |南京市     |1212     |秦淮区     |
|211      |广州市     |211      |广州市     |
|211      |广州市     |2111     |海珠区     |
|211      |广州市     |2112     |黄埔区     |
|1211     |鼓楼区     |1211     |鼓楼区     |
|1212     |秦淮区     |1212     |秦淮区     |
|2111     |海珠区     |2111     |海珠区     |
|2112     |黄埔区     |2112     |黄埔区     |
+---------+-----------+---------+-----------+

小结

本文介绍了SQL递归查询的一般形式及执行过程，并且结合示例数据给出了一些基本的递归查询的写法；如果仔细研究并灵活运用这些基本查询中所涉及的技巧，还可以写出更多满足其他需要的递归查询。

最后，这里再对递归查询进行几点补充说明。

回顾“找出华东分支的所有下二级分支”这一例子，该查询的SQL语句中引入了一个变量rel_level用于表示查询结果中的分支相对于华东分支的相对位置。但有时候查询条件可能需要判断分支在层次结构中的绝对位置，这时仅靠递归查询是无法得到所需结果的。此时，解决方案是在原始表中引入一个新属性用于记录各分支的绝对位置，以便在查询中利用。例如，我们可以在branch表的基础上增加一个新属性abs_level，得到branch_with_level（见下表）；这样，我们就可以实现涉及绝对位置的查询了：例如，“找出华东分支下的所有2级分支”（注意与“找出华东分支的所有下二级分支”的描述相区别），结果应是上海市、江苏省和台湾省分支。通过这种方式，我们还可以更加轻易地确定最上级分支（abs_level = 1）2。

2 细心的读者可能会发现上海市分支和浦东新区分支之间缺少了一个3级分支。但这并不是一处错误，因为从业务角度考虑，我们可能会将直辖市分支置于与省分支同样的位置。

              branch_with_level
+---------+-----------+-------------+---------+
|branch_id|branch_name|parent_branch|abs_level|
+---------+-----------+-------------+---------+
|1        |华东       |NULL         |1        |
|2        |华南       |NULL         |1        |
|11       |上海市     |1            |2        |
|111      |浦东新区   |11           |4        |
|12       |江苏省     |1            |2        |
|121      |南京市     |12           |3        |
|1211     |鼓楼区     |121          |4        |
|1212     |秦淮区     |121          |4        |
|13       |台湾省     |1            |2        |
|21       |广东省     |2            |2        |
|211      |广州市     |21           |3        |
|2111     |海珠区     |211          |4        |
|2112     |黄埔区     |211          |4        |
+---------+-----------+-------------+---------+

在本文提供的示例中，递归查询中的非递归项和递归项之间使用UNION或UNION ALL取并集的结果均没有差异。但在实际工作中，应考虑到两者的区别3，并根据具体目的决定是否需要去重。

3 举个例子，对“找出华东分支及上海市分支的所有下级分支”这个查询来说，使用UNION或UNION ALL取并集得到的结果就会不一样，读者可以自行研究一下为什么。

使用递归查询时需要特别注意的一点是必须确保递归项最终会返回空集，否则查询会不断循环下去，无法终止。PostgreSQL的官方文档(The PostgreSQL Global Development Group 2020)提供了一些检查策略，有兴趣的读者可以在有关章节找到该内容，这里就不再展开了。

附录

以下是在PostgreSQL中生成branch表所示数据的SQL语句：

CREATE TABLE branch (
  branch_id     INT,
  branch_name   VARCHAR(10),
  parent_branch INT,
  PRIMARY KEY (branch_id),
  FOREIGN KEY (parent_branch) REFERENCES branch (branch_id)
);

INSERT INTO branch
VALUES
  (1, '华东', NULL),
  (2, '华南', NULL),
  (11, '上海市', 1),
  (111, '浦东新区', 11),
  (12, '江苏省', 1),
  (121, '南京市', 12),
  (1211, '鼓楼区', 121),
  (1212, '秦淮区', 121),
  (13, '台湾省', 1),
  (21, '广东省', 2),
  (211, '广州市', 21),
  (2111, '海珠区', 211),
  (2112, '黄埔区', 211);

参考文献

The PostgreSQL Global Development Group. 2020. 《PostgreSQL 12.4 Documentation》.