开发人员：SQL
   下载
Oracle Database 11g 第 2 版或更高版本
   标签
sql, database, 全部

递归：

在 Oracle Database 11g 第 2 版中查询层次结构数据的快速入门

作者：Tim Hartley

2010 年 2 月发表

递归数据库处理，也称为材料清单 或零件分解问题，适用于包括人力资源、制造业、金融市场和教育在内的多种应用领域。这类处理中所涉及的数据称为 树状结构 数据或 层次结构 数据。Oracle 数据库长期以来一直通过专用语法（CONNECT BY 子句）支持递归。Oracle Database 11g 第 2 版通过子查询分解来支持递归，这就为解决下面的老问题提供了一个更好的新方法：查询层次结构数据。

表表达式

首先，我们回顾一下针对第 2 版的新功能建立的 SQL 语法。这里我们选择教育作为说明递归处理的领域。我们的原始示例使用下面的 Course 表：

                                 
CNO CNAME                  CRED CLABFEE CDEPT
--- ---------------------- ---- ------- -----
C11 INTRO TO CS               3     100 CIS
C22 DATA STRUCTURES           3      50 CIS
C33 DISCRETE MATHEMATICS      3       0 CIS
C44 DIGITAL CIRCUITS          3       0 CIS
C55 COMPUTER ARCH.            3     100 CIS
C66 RELATIONAL DATABASE       3     500 CIS
C77 COMPUTER PROGRAMMING 1    3     100 CIS
P11 EMPIRICISM                3     100 PHIL
P22 RATIONALISM               3      50 PHIL
P33 EXISTENTIALISM            3     200 PHIL
P44 SOLIPSISM                 6       0 PHIL
该表中的每行描述一门课程，由 CNO 列唯一标识。每门课程由一个系 (CDEPT) 开设，每门课程分配了学生修完该课程应取得的学分 (CRED)，还包含了注册选修该课程的学生需要支付的课程学费 (CRED)。以下查询显示了对哲学系开设的课程按学分-课程学费组合进行查询的结果： 
                                 
SELECT CRED, CLABFEE
FROM COURSE
WHERE CDEPT = 'PHIL';

CRED CLABFEE
---- -------
   3     100
   3      50
   3     200
   6       0

观察结果：查询的输入是一个表。查询的输出还是一个表 — 结果表。通过将查询括在圆括号内然后包括在另一个 SELECT 的 FROM 子句中，结果表本身可以是查询的目标。这样的查询也可以称为表表达式，因为它产生一个表。也可以将它称为 子查询，因为它是另一个查询之内的查询。

对子查询的支持使得针对同一个问题可用多种方式创建查询。如果另一个系也开设了一门学分-课程学费组合与哲学系开设的某门课程的学分-课程学费组合（即第一个查询的输出）相同的课程，考虑一下如何确定。查询 1、2 和 3（在本文结尾处给出）提供了三个解决方案。执行这三个查询都将产生以下结果集： 

                                 
CNO CNAME                  CRED CLABFEE CDEPT
--- ---------------------- ---- ------- -----
C77 COMPUTER PROGRAMMING 1    3     100 CIS
C55 COMPUTER ARCH.            3     100 CIS
C11 INTRO TO CS               3     100 CIS
C22 DATA STRUCTURES           3      50 CIS

子查询分解

子查询的使用可以进入另一个层面。考虑对视图的查询。从概念上而言，一个视图定义一个可对其执行查询的结果表。假设可以编写一个表达式，从而允许一个名称与结果表相关联。则使用该名称的查询将是一个对该结果表的查询。子查询分解（也称为公用表表达式）正是这一思想的体现。WITH 子句为子查询块指派一个名称。之后可以使用指派的名称在某个查询中引用该查询块。

使用此方法，查询 4 找到了课程学费总额最高的系。该查询包含两级聚合。首先，通过 GROUP BY 子句对每个系应用 SUM 函数来确定每个系的总费用。其次，根据每个系的总费用额确定总费用额最高的系。DTOTAL 是一个命名查询，为其设计了多个引用。没有子查询分解时，必须在两个后续的 FROM 子句中针对 Course 表对 SELECT 进行编码。因为 SUM(CLABFEE) 的结果是一个导出值，所以在子查询中使用 TOTFEE 的列别名。对 DTOTAL 的后续引用将使用这个别名。在 Oracle Database 11g 第 2 版中，可以在查询表达式声明中对列重命名（也就是说使用列别名），而不是在子查询中对列重命名： 

                                 
WITH DTOTAL  
                                  
(CDEPT, TOTFEE) AS
第 2 版进一步扩展了 WITH 子句，通过一个叫“递归的 WITH 子句”的特性支持递归查询。首先，我们来快速回顾一下 Oracle 的专用递归语法。

递归的“旧”方法

从树状结构检索数据的过程被称作递归处理。传统上，Oracle 数据库通过两个专门的子句 CONNECT BY 和 START WITH 支持递归处理。CONNECT BY 指明要在树状结构序列中检索行。该子句中指定的条件指明了父-子关系。如果 PRIOR 出现在父列前面，则表示要进行向下遍历。如果 PRIOR 位于子列前面，则表示向上遍历。START WITH 指定了遍历的起始点，称为种源。可以从任何节点进入树，通过 START WITH 子句确定进入的节点。

为了说明递归，我们使用 Course 表的修改版本，其中每门课程都有另一门课程作为修课的前提条件。一门课程的直接前提课程绝不会多余一门；但是，一门课程可以是多门课程的前提条件。这种关系是递归的，因为它将一个实体与另一个同类型实体相关联。Coursex 表中表示了这种关系，如下所示。

                                 
CNO PCNO CNAME                  CRED CLABFEE CDEPT
--- ---- ---------------------- ---- ------- -----
C11      INTRO TO CS               3     100 CIS
C33 C11  DISCRETE MATHEMATICS      3       0 CIS
C22 C33  DATA STRUCTURES           3      50 CIS
C44 C33  DIGITAL CIRCUITS          3       0 CIS
C55 C44  COMPUTER ARCH.            3     100 CIS
C66 C22  RELATIONAL DATABASE       3     500 CIS
C77 C33  INTRO TO PROGRAMMING 1    3     100 CIS
P11      EMPIRICISM                3     100 PHIL
P22 P11  RATIONALISM               3      50 PHIL
P33 P11  EXISTENTIALISM            3     200 PHIL
P44      SOLIPSISM                 6       0 PHIL
PCNO 是建立该关系的外键。如果某门课程没有前提条件，则外键值为 NULL。

递归关系的一个主要特征是可以将它表示为树状结构。使用该结构时，使用术语“父”和“子”来描述树上节点之间的关系。图 1 中，C11 是 C33 的父节点，而 C33 是 C11 的子节点。没有父节点的节点（如 C11、P11）对应于没有前提条件的课程。这些节点位于树的顶端，充当根节点。没有子节点的节点（如 C66、C55）出现在树的底部，称作叶节点。

图 1 以树状结构表示的递归关系


查询 5 使用递归处理方法识别作为课程 C22 的前提条件的所有课程的课程代号和课程名称。运行该查询将产生以下输出： 
                                 
CNO PCNO CNAME
--- ---- --------------------
C22 C33  DATA STRUCTURES
C33 C11  DISCRETE MATHEMATICS
C11 -    INTRO TO CS
使用 CONNECT BY 的 SELECT 语句可以引用 LEVEL 伪列。始终从层次 1 进入树。随着从种源开始向各个节点遍历，层次逐渐增加。再遍历回种源则减少层次。

递归的“新”方法

通过子查询分解进行递归，需要使用 WITH 子句定义一个命名子查询，还需要一个针对这个命名子查询的查询。查询 6 使用新的递归的 WITH 子句特性实现了与查询 5 中显示的 CONNECT BY 查询相同的结果。命名子查询包含两个通过 UNION ALL 操作组合的查询块。第一个查询块是一个初始化子查询（也称定位点），其编码是非递归的，包括确定调查起始点的种源。系统将首先处理这个子查询。第二个查询块是递归子查询，它根据与结果中已有行的关系向结果添加行。此处的技巧是定义新行与旧行的关联方式。新行是通过将命名查询与定位点确定的原始表进行联接而识别的。UNION ALL 将定位点与递归子查询进行组合，确保不从结果中清除重复记录。这两个查询块必须是可兼容合并的；也就是说，两个查询块中必须选择相同的列数。

列表中紧跟着查询名称的别名构成了该命名查询的结果表的各列。在递归子查询以及对命名查询的后续查询中可以引用这些别名。

递归需要一个终止条件。每次执行递归子查询时，因为它要读取由公用表表达式建立的临时视图，所以它只能看到由该递归查询的上一次迭代添加到该视图中的行。系统不断评估递归查询，直到不再向临时视图添加新行为止。

我们现在从概念上来了解此过程是如何针对查询 6 工作的。首先，执行初始话子查询来生成临时视图。这个子查询的执行向临时视图（此处命名为 C）添加以下行： 

                                 
C22 C33  DATA STRUCTURES
执行完初始化查询后，通过合并临时视图的内容来执行递归子查询。因此，执行以下查询： 
                                 
SELECT X.CNO, X.PCNO, X.CNAME
FROM  
                                  
(SELECT CNO, PCNO, CNAME
      FROM COURSEX
      WHERE CNO = 'C22') C, COURSEX X
WHERE C.PCNO = X.CNO;
执行该查询将向临时视图添加以下行： 
                                 
C33 C11  DISCRETE MATHEMATICS
再次执行递归子查询，合并临时视图中新添加的行。因此，执行以下查询： 
                                 
SELECT X.CNO, X.PCNO, X.CNAME
FROM  
                                  
(SELECT X.CNO, X.PCNO, X.CNAME
      FROM (SELECT CNO, PCNO, CNAME
            FROM COURSEX 
            WHERE CNO = 'C22') C, COURSEX X
      WHERE C.PCNO = X.CNO) C, COURSEX X
WHERE C.PCNO = X.CNO;
执行该查询将向临时视图添加以下行： 
                                 
C11 -    INTRO TO CS
通过合并临时视图中新添加的行，再次执行递归子查询。这次，该查询不生成结果。因为之前没有向临时视图添加任何行，该操作完成。这个事件是终止条件。

遍历方向

递归子查询中指定的条件指明了父子关系。使用命名查询 (C) 限定父列 (CNO)，从而指示遍历方向向下。遍历的起始点由初始子查询中的种源确定。也可以向上遍历树来访问存储在父节点和祖先节点中的信息。使用命名查询限定子列 (PCNO)，从而指示遍历方向向上。

LEVEL 伪列只能与 CONNECT BY 子句一起使用。但是，通过在查询中另外引入别名也能达到同样的效果。这一方法将在查询 7 中演示，查询 7 中使用一个名为 LVL 的别名来标识距种源的层次或距离。执行该查询将产生以下结果： 

                                 
LVL CNO PCNO CNAME
--- --- ---- --------------------
  1 C22 C33  DATA STRUCTURES
  2 C33 C11  DISCRETE MATHEMATICS
  3 C11      INTRO TO CS
该查询的种源为 C22，因此结果表中对应行的 LVL 值为 1。如上面的图 1 中所示，课程 C33 是 C22 的父节点，因此对该行来说 LVL 的值为 2。课程 C11 是 C33 的父节点，因此我们已经从种源向上移动了一层，结果表最后一行的 LVL 值反映了这点。

递归与循环

层次结构数据会引发的一个特殊情况是循环，当后代也是祖先时会出现这一情况。如果检测到存在循环，则 CONNECT BY 会报告在递归查询中存在一个错误。在 Oracle Database 10g 中，通过指定 NOCYCLE 可以使系统返回查询的结果。如果不指定这个参数，由于数据中存在循环，查询将失败。CONNECT_BY_ISCYCLE 伪列指示当前行是否包含本身也是自己的祖先的子节点。

下面的 HAS_A_CYCLE 表包含一个循环：C33 和 C22 互为前提条件，并且每个都是另一个的父节点。 
                                 
CNO PCNO
--- ----
C11
C22 C11
C33 C22
C22 C33
执行没有 NOCYCLE 参数的递归查询将导致以下错误： 
                                 
ORA-01436: CONNECT BY loop in user data
通过子查询分解进行的递归使用 CYCLE 子句标记处理过程中的循环。在这个子句中可以引用命名查询的各列，系统也可以使用命名查询的各列来检测循环。使用递归子查询分解时，循环的概念也更加广泛。如果某一行的祖先的循环列的值与当前行中循环列的值相同，则存在循环。用于检测循环的列并不仅限于定义递归关系的列。

SET 子句在结果中生成了一个称作循环标记的列，设置该列的值来指示是否针对当前行检测到了循环。如果检测到循环，将停止对该行的子行的搜索。如果未检测到循环，则将循环标记设置为指定的默认值。循环标记的值必须是单个字符。与 CONNECT BY 子句一样，如果未在查询中包括循环检测，也就是说，没有 CYCLE 子句，一旦发现循环就会出现错误。查询 8 包括了 CYCLE 子句，用于检测循环并继续处理过程。在下面的结果表中可以看到，循环标记作为一列是可访问的，但是它不在该命名查询的范围内。 

                                 
CNO PCNO CYCLEMARKER
--- ---- -----------
C11      N
C22 C11  N
C33 C22  N
C22 C33  Y

搜索顺序

对递归处理的另一个增强是可以指定遍历顺序。既可指定 DEPTH FIRST，也可指定 BREADTH FIRST，二者都是层序遍历。在 DEPTH FIRST 遍历中，先返回一个节点的子节点，然后再返回该节点的同级节点（即具有相同父节点的节点）。在 BREADTH FIRST 遍历中，先返回该层次中的所有行，然后再下行至下个层次。因此，某节点的同级节点在其子节点之前返回。根据 BY 关键字后面列出的列中的值对同级节点进行排序。可以是升序 (ASC)，也可以是降序 (DESC)。

使用 SET 子句显示搜索过程中访问节点的顺序。还引进了一个列别名，可在在最终查询中用来显示结果或对结果排序。虽然 Oracle 递归处理过程中 LEVEL 概念的增加或减少反映了离开种源或接近种源，但 SET 子句中的别名值在整个遍历中还是不断增加。查询 9 说明了按同级节点的课程学费值进行的 DEPTH FIRST 搜索和对同级节点的排序。执行该查询将产生以下结果。 

                                 
CNO          PCNO CLABFEE XX
------------ ---- ------- --
C11                   100  1
   C33       C11        0  2
      C77    C33      100  3
      C22    C33       50  4
         C66 C22      500  5
      C44    C33        0  6
         C55 C44      100  7
观察同级节点 C77、C22 和 C44 的顺序。它们依据各自课程学费的值出现在输出中。在这三门课程中，课程 C77 的课程学费最高，因此在指定的降序序列中它首先出现。

为了建议使用 BREADTH FIRST 遍历，我们做了下列假设：

  • 没有前提条件的课程为一年级课程。
  • 有一个前提条件的课程为二年级课程。
  • 有多个前提条件的课程为三年级/四年级的课程。
课程表的 BREADTH FIRST 遍历将生成课程的排序，可以反映该学校的学士项目大学排名。将查询 9 中的搜索修改为 BREADTH FIRST 将产生以下输出： 
                                 
CNO          PCNO CLABFEE XX
------------ ---- ------- --
C11                   100  1
   C33       C11        0  2
      C77    C33      100  3
      C22    C33       50  4
      C44    C33        0  5
         C66 C22      500  6
         C55 C44      100  7

遍历网络

用于遍历树状结构的方法同样可用于遍历网络。网络结构是由多对多关系构成的。例如，如果允许某门课程有多个必备前提条件，同时允许一门课程作为多门课程的前提条件，则需要一个单独的表来表示这种关系。可以使用以前的 CONNECT BY 语法或新的子查询分解语法遍历这样的表。

总结

Oracle Database 11g 第 2 版新增的递归的 WITH 子句特性为处理层次结构数据提供了新方法。还提供了更加强大的循环检测功能，可以选择使用 DEPTH FIRST 或 BREADTH FIRST 遍历来处理数据。

在本文中，我们通过一些非常简单的用例简要介绍了这些特性。更多详细信息，请参阅“参考资料”部分。

查询 1：使用存在性测试的关联子查询 
SELECT *
FROM COURSE C1
WHERE CDEPT <> 'PHIL'
AND EXISTS
(SELECT *
 FROM COURSE C2
 WHERE C2.CLABFEE = C1.CLABFEE
   AND C2.CRED = C1.CRED
   AND C2.CDEPT = 'PHIL')
查询 2：返回多列的子查询 
SELECT *
FROM COURSE
WHERE CDEPT <> 'PHIL'
AND (CRED, CLABFEE) IN
(SELECT CRED, CLABFEE
 FROM COURSE
 WHERE CDEPT = 'PHIL');
查询 3：使用表表达式联接 
SELECT C1.*
FROM COURSE C1, (SELECT CRED, CLABFEE
                 FROM COURSE
                 WHERE CDEPT = 'PHIL') C2
WHERE C1.CLABFEE = C2.CLABFEE
  AND C1.CRED = C2.CRED
  AND C1.CDEPT <> 'PHIL';
查询 4：子查询分解示例 
WITH DTOTAL AS
(SELECT CDEPT, SUM(CLABFEE) AS "TOTFEE"
 FROM COURSE
 GROUP BY CDEPT)
SELECT CDEPT
FROM DTOTAL
WHERE TOTFEE =
 (SELECT MAX(TOTFEE)
  FROM DTOTAL);
查询 5：使用 CONNECT BY 的递归处理 
SELECT CNO, PCNO, CNAME
FROM COURSEX
CONNECT BY CNO = PRIOR PCNO
START WITH CNO = 'C22';
查询 6：使用递归的 WITH 子句 
WITH C (CNO, PCNO, CNAME) AS
(SELECT CNO, PCNO, CNAME -- initialization subquery
 FROM COURSEX
 WHERE CNO = 'C22' -- seed
 UNION ALL
 SELECT X.CNO, X.PCNO, X.CNAME -- recursive subquery
 FROM C, COURSEX X
 WHERE C.PCNO = X.CNO)
SELECT CNO, PCNO, CNAME
FROM C;
查询 7：在递归性子查询中报告层次 
WITH C (LVL, CNO, PCNO, CNAME) AS
((SELECT 1, CNO, PCNO, CNAME
  FROM COURSEX
  WHERE CNO = 'C22')
 UNION ALL
 (SELECT C.LVL+1, X.CNO, X.PCNO, X.CNAME
  FROM C, COURSEX X
  WHERE C.PCNO = X.CNO))
SELECT LVL, CNO, PCNO, CNAME
FROM C;
查询 8：在递归性子查询中处理循环 
WITH C (CNO, PCNO) AS
(SELECT CNO, PCNO -- initialization subquery
 FROM HAS_A_CYCLE
 WHERE CNO = 'C11' -- seed
 UNION ALL
 SELECT X.CNO, X.PCNO -- recursive subquery
 FROM C, HAS_A_CYCLE X
 WHERE X.PCNO = C.CNO)                                       
CYCLE CNO SET CYCLEMARKER TO 'Y' DEFAULT 'N'
SELECT CNO, PCNO, CYCLEMARKER
FROM C;
查询 9：使用 search 子句的递归 
WITH C (LVL, CNO, PCNO, CLABFEE) AS
(SELECT 0, CNO, PCNO, CLABFEE
 FROM COURSEX
 WHERE CNO = 'C11'
 UNION ALL
 SELECT C.LVL+1, X.CNO, X.PCNO, X.CLABFEE
 FROM C, COURSEX X
 WHERE C.CNO = X.PCNO)                                       
SEARCH DEPTH FIRST BY CLABFEE DESC SET XX
SELECT LPAD(' ', LVL*3) || CNO AS "CNO", PCNO, CLABFEE, XX
FROM C
ORDER BY XX;

参考资料

Tim Hartley ( www.timhartley.com) 是 Tim Hartley and Associates, LLC 的负责人。他从 1989 年开始使用 Oracle 产品，并且完成了三本著书。