With (SQL)

在SQL数据库中，处理组织架构、家族树、文件系统等层次模型数据的主要手段有两种：递归公用表表达式（Recursive CTE）与 `CONNECT BY`子语句。

层级查询（Hierarchical Query）是一种处理层次模型数据的SQL查询，本质上是更通用的“递归不动点查询（Recursive Fixpoint Queries）”的特殊形式，主要用于计算数据的传递闭包（Transitive Closures）。

自SQL:1999标准发布以来，层级查询正式确立了以递归公用表表达式（recursive CTE）为核心的实现方式。与Oracle早期的connect-by子句不同，递归CTE从设计之初就包含了不动点语义（Fixpoint Semantics）。这一标准实现很大程度上借鉴了IBM DB2版本2中的实现。

目前，递归 CTE 已获得业界主流数据库的广泛支持，包括Microsoft SQL Server（自 SQL Server 2008 R2 起）、 Firebird 2.1、 PostgreSQL 8.4+、 SQLite 3.8.3+、 IBM Informix 11.50+ 版本、CUBRID、MariaDB 10.2+以及MySQL 8.0.1+的支持。此外，BI工具如 Tableau已提供相关应用文档。但TIBCO Spotfir仍未支持CTE。而Oracle 11g Release 2的实现仍缺乏不动点语义。

如果没有公用表表达式或`connect-by`子句，可以通过用户定义的递归函数来实现层级查询。

## 公用表表达式

在SQL中，公用表表达式（Common table expression, CTE），是一个临时命名的结果集，它派生自简单的查询，并在`SELECT`、`INSERT`、`UPDATE` 或 `DELETE` 语句的执行范围内定义。

CTE可视为派生表（子查询）、视图或内联用户自定义函数的替代方案。

CTE的实现支持：Teradata（从版本14开始）、IBM DB2、IBM Informix（从版本14.1开始）、Firebird（从版本2.1开始）、 Microsoft SQL Server（从2005版本开始）、Oracle（从11g release 2开始支持递归）、PostgreSQL（自8.4版本起）、MariaDB（自10.2版本起）、MySQL（自8.0版本起）、SQLite（自3.8.3版本起）、HyperSQL、IBM Informix（自 14.10 版本起）、 Google BigQuery、Sybase（从版本 9 开始）、Vertica、H2（实验性支持）、以及许多其他数据库的支持。Oracle将CTE称为“子查询分解”（subquery factoring）。

CTE（可以是递归的，也可以不是）的语法如下：

```sql
 
WITH [RECURSIVE] with_query [, ...]  -- 这里可以依次定义多个CTE，数据库引擎会逐个依次生成结果集，后面的CTE可以引用前面定义的CTE
SELECT ...                           -- 在查询中使用CTE
```

其中 `with_query` 的语法为：

```sql
 
query_name [ (column_name [,...]) ]  -- 可定义列名
AS (SELECT ...) 
```

`WITH RECURSIVE`是SQL:1999标准提供的递归公共表表达式（Recursive CTE）实现机制，用来在一条SQL内完成“循环/递归”类计算（树遍历、层级展开、生成序列、图遍历等）。其核心结构是：锚点查询（anchor）+ 递归查询（recursive）用`UNION [ALL]`连接，递归部分引用CTE自身，直到不再产生新行即终止。由于不会自动创建伪列（如下文提到的`LEVEL`），其语法更加复杂。如果需要这些伪列，必须在代码中自行创建。有关教程示例，请参阅 MSDN 文档或 IBM 文档。

除了PostgreSQL，其他数据库系统中`WITH`之后通常不需要`RECURSIVE`关键字。

在SQL:1999标准中，递归CTE查询可以出现在任何允许查询的地方。例如，可以使用 `CREATE` `RECURSIVE` `VIEW` 为结果命名。在 `INSERT INTO` 中使用 CTE，可以用递归查询生成的数据填充表；利用这种技术可以实现随机数据生成，而无需使用任何过程化语句。

一些数据库（如 PostgreSQL）支持较短的 CREATE RECURSIVE VIEW 格式，该格式在内部被转换为 WITH RECURSIVE 编码。

递归CTE的语法框架：

```sql
 
WITH RECURSIVE cte_name (col1, col2, ...) AS (
  -- 1) anchor member（锚点/基线查询）：初始行集（递归的起点，生成第0层/第1层数据，不引用 cte_name）
  SELECT ...

  UNION ALL   --  UNION ALL：保留重复，通常更快；需自己保证不会无限递归/爆炸重复。
              -- 或者UNION：自动去重，常用于防止图遍历重复节点，但代价更高。

  -- 2) recursive member（递归成员查询）：递归行集（必须引用cte_name自身，基于上一轮结果生成下一轮结果）
  SELECT ...
  FROM cte_name
  WHERE ...   -- 终止条件（termination）写在这里：不再产生新行。例如层级上限、剩余字符串非空、未访问过等。
)
SELECT ...
FROM cte_name;
```

计算从0到9的阶乘的递归查询示例：

```sql
 
WITH recursive temp (n, fact) AS (
    SELECT 0, 1                           -- 初始子查询
  UNION ALL
    SELECT n+1, (n+1)*fact FROM temp      -- 递归子查询
    WHERE n < 9
)
SELECT * FROM temp;
```

SQL标准的递归CTE语义中，数据库引擎的递归执行模型只用上一轮新增行(称工作集或增量delta)去`JOIN`基表生成下一批 delta，以避免指数级重复计算。最终结果是各轮delta的累积。绝大多数实现（PostgreSQL、SQL Server、DB2 等）都会用一个“工作表（working table）/队列”保存上一轮新增的行（delta），递归成员每轮只读取这批增量数据去`JOIN`基表。即使把递归成员写成`JOIN cte_name`，引擎在递归上下文里读取的就是“上一轮的工作集”，而不是“最终累计结果集”。SQL标准语义强调“递归直到不再产生新行”。

以下为树/层级数据遍历（组织结构）的例子。假设基表为：`org(emp_id, manager_id, emp_name)`，自顶向下展开（从某个经理开始找下属）：

```sql
 
WITH RECURSIVE sub_tree(emp_id, manager_id, emp_name, lvl, path) AS (
  -- anchor：根节点（起点经理）
  SELECT emp_id, manager_id, emp_name, 1 AS lvl,
         CAST(emp_id AS VARCHAR(200)) AS path
  FROM org
  WHERE emp_id = 100

  UNION ALL

  -- recursive：找当前节点的直接下属
  SELECT o.emp_id, o.manager_id, o.emp_name, st.lvl + 1,
         st.path || '>' || o.emp_id
  FROM org o
  JOIN sub_tree st ON o.manager_id = st.emp_id -- 语义是用 每轮迭代的新增的行（delta）JOIN基表
)
SELECT * FROM sub_tree;

-- 防止环（脏数据或者图结构）导致A管理B、B又管理A。标准做法是用“路径”判断当前行是否访问过：
--  在递归成员加条件：WHERE (path不包含o.emp_id)
```

以下为图遍历与去重策略的示例。假设边表为`edge(src, dst)`，要找从A出发可达的点：

```sql
 
WITH RECURSIVE reach(node) AS (
  SELECT 'A'
  UNION     -- UNION（去重）很常见：避免图中回路导致无限扩展。每轮迭代的新增的行（delta）都会与当前累计结果集比较去重。实现可能用 hash/sort
  SELECT e.dst
  FROM edge e
  JOIN reach r ON e.src = r.node
)
SELECT * FROM reach;
```

## CONNECT BY

另一种可选语法是Oracle在20世纪80年代引入的非标准的 `CONNECT BY` 结构。在Oracle 10g之前，该结构仅对遍历无环图有用，因为探测到任何循环时它都会返回错误。在Oracle 10g版本中，引入了NOCYCLE特性（及关键字），使其能处理带环的数据。

`CONNECT BY`的实现支持有：Snowflake、EnterpriseDB、 Oracle数据库、 CUBRID、 IBM Informix 以及 IBM DB2（仅在启用兼容模式时）的支持。

语法如下：

```sql
START WITH：指定层次结构的根节点。

CONNECT BY PRIOR：定义父子之间的关联。

ORDER SIBLINGS BY：在保持层次结构的同时，对同一层级的“兄弟”进行排序。

SELECT select_list FROM table_expression [ WHERE ... ] [ START WITH start_expression ] CONNECT BY [NOCYCLE] { PRIOR child_expr = parent_expr | parent_expr = PRIOR child_expr } [ ORDER SIBLINGS BY column1 [ ASC | DESC ] [, column2 [ ASC | DESC ] ] ... ] [ GROUP BY ... ] [ HAVING ... ] ... 
```

查询示例：

```sql
SELECT LEVEL, LPAD (' ', 2 * (LEVEL - 1)) || ename "employee", empno, mgr "manager"
FROM emp 
START WITH mgr IS NULL
CONNECT BY PRIOR empno = mgr;
```

上述查询的输出如下所示：

```
 level |  employee   | empno | manager
     1 | KING        |  7839 |
     2 |   JONES     |  7566 |    7839
     3 |     SCOTT   |  7788 |    7566
     4 |       ADAMS |  7876 |    7788
     3 |     FORD    |  7902 |    7566
     4 |       SMITH |  7369 |    7902
     2 |   BLAKE     |  7698 |    7839
     3 |     ALLEN   |  7499 |    7698
     3 |     WARD    |  7521 |    7698
     3 |     MARTIN  |  7654 |    7698
     3 |     TURNER  |  7844 |    7698
     3 |     JAMES   |  7900 |    7698
     2 |   CLARK     |  7782 |    7839
     3 |     MILLER  |  7934 |    7782
(14 rows)
```

### 伪列

- LEVEL
- CONNECT_BY_ISLEAF
- CONNECT_BY_ISCYCLE
- CONNECT_BY_ROOT

### 一元运算符

以下示例返回部门 10 中每个员工的姓氏、层级结构中该员工之上的每个经理、经理与员工之间的层级数，以及两者之间的路径：

```sql
SELECT
  ename                           "Employee",
  CONNECT_BY_ROOT ename           "Manager",
  LEVEL-1                         "Pathlen",
  SYS_CONNECT_BY_PATH(ename, '/') "Path"
FROM emp
WHERE LEVEL > 1 AND deptno = 10
CONNECT BY PRIOR empno = mgr
ORDER BY "Employee", "Manager", "Pathlen", "Path";
```

### 函数

`SYS_CONNECT_BY_PATH`

## 延伸阅读

- 学术教科书。请注意，这些仅涵盖 SQL:1999 标准（和 Datalog），不包括 Oracle 扩展。
- 第24章。