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章。