SQL 确认叶子节点、分支节点和根节点|极客教程

SQL 确认叶子节点、分支节点和根节点，你想确定给定的一行数据是哪种类型的节点：叶子节点、分支节点还是根节点。对于本实例而言，叶子节点代表不是管理者的员工。分支节点表示管理者的员工，同时他也拥有自己的上级管理者。根节点表示没有上级管理者的员工。

SQL 确认叶子节点、分支节点和根节点问题描述

你想确定给定的一行数据是哪种类型的节点：叶子节点、分支节点还是根节点。对于本实例而言，叶子节点代表不是管理者的员工。分支节点表示管理者的员工，同时他也拥有自己的上级管理者。根节点表示没有上级管理者的员工。你希望通过返回 1（TRUE）或 0（FALSE）来反映每一行在层次关系中的状态。你希望返回如下所示的结果集。

ENAME         IS_LEAF  IS_BRANCH    IS_ROOT
---------- ---------- ---------- ----------
KING                 0         0          1
JONES                0         1          0
SCOTT                0         1          0
FORD                 0         1          0
CLARK                0         1          0
BLAKE                0         1          0
ADAMS                1         0          0
MILLER               1         0          0
JAMES                1         0          0
TURNER               1         0          0
ALLEN                1         0          0
WARD                 1         0          0
MARTIN               1         0          0
SMITH                1         0          0

SQL 确认叶子节点、分支节点和根节点解决方案

EMP 表是树形结构，而不是递归层次结构（recursive hierarchy），因为根节点的 MGR 值是 Null。认识到这一点很重要。如果 EMP 表是递归层次结构，那么根节点将会指向自身（即员工 KING的 MGR 值将等于他的 EMPNO）。我认为这是违反常理的，因而指定根节点的 MGR 值为 Null。对于 Oracle 的 CONNECT BY 子句和 DB2/SQL Server 的 WITH 子句而言，树形结构处理起来更容易，甚至可能比递归层次结构的处理效率更高。如果必须要处理递归层次结构，并且要使用 CONNECT BY 或 WITH 子句，那么就要小心了：我们可能会掉进死循环里。为防止陷入递归层次结构设置的陷阱，需要编写额外的代码小心地避开它。
DB2、PostgreSQL、MySQL 和 SQL Server
使用 3 个标量子查询，针对每一种节点类型分别计算出正确的“布尔”值（1 或 0）。

 1  select e.ename,
 2         (select sign(count(*)) from emp d
 3           where 0 =
 4             (select count(*) from emp f
 5               where f.mgr = e.empno)) as is_leaf,
 6         (select sign(count(*)) from emp d
 7           where d.mgr = e.empno
 8             and e.mgr is not null) as is_branch,
 9         (select sign(count(*)) from emp d
10           where d.empno = e.empno
11             and d.mgr is null) as is_root
12     from emp e
13   order by 4 desc,3 desc

Oracle
对于 Oracle Database 10g 之前的版本，上述标量子查询方案也适用。下面的解决方案利用（Oracle Database 10g 新增的）内置函数来帮助我们识别根节点和叶子节点。这些函数分别是 CONNECT_BY_ROOT 和 CONNECT_BY_ISLEAF。

 1  select ename,
 2         connect_by_isleaf is_leaf,
 3         (select count(*) from emp e
 4           where e.mgr = emp.empno
 5             and emp.mgr is not null
 6             and rownum = 1) is_branch,
 7         decode(ename,connect_by_root(ename),1,0) is_root
 8    from emp
 9   start with mgr is null
10 connect by prior empno = mgr
11 order by 4 desc, 3 desc

SQL 确认叶子节点、分支节点和根节点扩展知识

DB2、PostgreSQL、MySQL 和 SQL Server
本解决方案按照“问题”部分提出的规则确认叶子节点、分支节点和根节点。首先确认一个员工是否是叶子节点。如果当前员工不是管理者（没有下属），那么他就是一个叶子节点。第一个标量子查询 IS_LEAF 如下所示。

select e.ename,
       (select sign(count(*)) from emp d
         where 0 =
           (select count(*) from emp f
             where f.mgr = e.empno)) as is_leaf
  from emp e
order by 2 desc
　
ENAME         IS_LEAF
---------- ----------
SMITH               1
ALLEN               1
WARD                1
ADAMS               1
TURNER              1
MARTIN              1
JAMES               1
MILLER              1
JONES               0
BLAKE               0
CLARK               0
FORD                0
SCOTT               0
KING                0

IS_LEAF 的输出结果要么是 0，要么是 1，因此要对 COUNT(*) 查询的结果调用 SIGN 函数。否则的话，对于叶子节点而言，我们将得到 14 而不是 1。作为一种替代方案，因为只希望返回 0 或者 1，我们也可以对一个只有一行数据的表做 COUNT(*) 查询。例如：

select e.ename,
       (select count(*) from t1 d
         where not exists
           (select null from emp f
             where f.mgr = e.empno)) as is_leaf
  from emp e
order by 2 desc
　
ENAME         IS_LEAF
---------- ----------
SMITH               1
ALLEN               1
WARD                1
ADAMS               1
TURNER              1
MARTIN              1
JAMES               1
MILLER              1
JONES               0
BLAKE               0
CLARK               0
FORD                0
SCOTT               0
KING                0

下一步要找出分支节点。如果一个员工是管理者（有下属），并且他们也碰巧有上级管理者，那么该员工就是一个分支节点。标量子查询 IS_BRANCH 的结果集如下所示。

select e.ename,
       (select sign(count(*)) from emp d
         where d.mgr = e.empno
          and e.mgr is not null) as is_branch
  from emp e
 order by 2 desc
　
ENAME       IS_BRANCH
---------- ----------
JONES               1
BLAKE               1
SCOTT               1
CLARK               1
FORD                1
SMITH               0
TURNER              0
MILLER              0
JAMES               0
ADAMS               0
KING                0
ALLEN               0
MARTIN              0
WARD                0

类似地，有必要对 COUNT(*) 查询的结果调用 SIGN 函数。否则，当一个节点是分支节点时，我们有可能得到比 1 大的值。就像标量子查询 IS_LEAF 一样，我们也可以借助一个只有一行数据的表来避免使用 SIGN 函数。下面的解决方案用到了一个只有一行数据的表 T1。

select e.ename,
       (select count(*) from t1 t
         where exists (
           select null from emp f
             where f.mgr = e.empno
               and e.mgr is not null)) as is_branch
  from emp e
order by 2 desc
　
ENAME       IS_BRANCH
---------- ----------
JONES               1
BLAKE               1
SCOTT               1
CLARK               1
FORD                1
SMITH               0
TURNER              0
MILLER              0
JAMES               0
ADAMS               0
KING                0
ALLEN               0
MARTIN              0
WARD                0

最后要找到根节点。根节点的员工是一个管理者，但他没有上级管理者。在 EMP 表里，只有 KING 是根节点。标量子查询 IS_ROOT 如下所示。

select e.ename,
       (select sign(count(*)) from emp d
         where d.empno = e.empno
          and d.mgr is null) as is_root
  from emp e
 order by 2 desc
　
ENAME         IS_ROOT
---------- ----------
KING                1
SMITH               0
ALLEN               0
WARD                0
JONES               0
TURNER              0
JAMES               0
MILLER              0
FORD                0
ADAMS               0
MARTIN              0
BLAKE               0
CLARK               0
SCOTT               0

EMP 表只有 14 行数据，很容易就能看出来 KING 是唯一的根节点，因此严格地说，上述对 COUNT(*) 查询结果调用 SIGN 函数的操作并不是必须的。如果可能存在多个根节点，那么就有必要使用 SIGN 函数。当然，也可以像前面的 IS_BRANCH 和 IS_LEAF 一样，借助一个只有一行数据的表来避免使用 SIGN 函数。
Oracle
对于 Oracle Database 10g 之前的版本，可以参考其他数据库的讨论内容，它们的解决方案也适用于 Oracle（无须任何改动）。对于 Oracle 10g 和后续的版本，我们可以利用两个更便于识别根节点和叶子节点的函数，它们分别是 CONNECT_BY_ROOT 和 CONNECT_BY_ISLEAF。在写作本书时，若要使用 CONNECT_BY_ROOT 和 CONNECT_BY_ISLEAF 函数，则 SQL 语句中也要同时用到 CONNECT BY 子句。首先，调用 CONNECT_BY_ISLEAF 找出叶子节点，如下所示。

select ename,
        connect_by_isleaf is_leaf
  from emp
 start with mgr is null
connect by prior empno = mgr
order by 2 desc
　
ENAME         IS_LEAF
---------- ----------
ADAMS               1
SMITH               1
ALLEN               1
TURNER              1
MARTIN              1
WARD                1
JAMES               1
MILLER              1
KING                0
JONES               0
BLAKE               0
CLARK               0
FORD                0
SCOTT               0

下一步要使用标量子查询找出分支节点。分支节点的员工既是一个管理者，同时也有上级管理者。

select ename,
        (select count(*) from emp e
          where e.mgr = emp.empno
            and emp.mgr is not null
            and rownum = 1) is_branch
  from emp
 start with mgr is null
connect by prior empno = mgr
order by 2 desc
　
ENAME       IS_BRANCH
---------- ----------
JONES               1
SCOTT               1
BLAKE               1
FORD                1
CLARK               1
KING                0
MARTIN              0
MILLER              0
JAMES               0
TURNER              0
WARD                0
ADAMS               0
ALLEN               0
SMITH               0

上述 ROWNUM 过滤条件是必要的，这是为了确保返回值是 1 或 0，而不是其他值。
最后，使用函数 CONNECT_BY_ROOT 识别出根节点。本解决方案找出根节点的 ENAME，并逐一地比较 ENAME 和下面查询返回的行数据。如果两个 ENAME 相等，则那一行即为根节点。

select ename,
       decode(ename,connect_by_root(ename),1,0) is_root
  from emp
 start with mgr is null
connect by prior empno = mgr
order by 2 desc
　
ENAME         IS_ROOT
---------- ----------
KING                1
JONES               0
SCOTT               0
ADAMS               0
FORD                0
SMITH               0
BLAKE               0
ALLEN               0
WARD                0
MARTIN              0
TURNER              0
JAMES               0
CLARK               0
MILLER              0

对于 Oracle 9i 及其后续版本，也可以使用 SYS_CONNECT_BY_PATH 函数替代 CONNECT_BY_ROOT。Oracle 9i 版本的解决方案如下所示。

select ename,
       decode(substr(root,1,instr(root,',')-1),NULL,1,0) root
  from (
select ename,
       ltrim(sys_connect_by_path(ename,','),',') root
  from emp
start with mgr is null
connect by prior empno=mgr
       )
　
ENAME       ROOT
---------- ----
KING          1
JONES         0
SCOTT         0
ADAMS         0
FORD          0
SMITH         0
BLAKE         0
ALLEN         0
WARD          0
MARTIN        0
TURNER        0
JAMES         0
CLARK         0
MILLER        0

SYS_CONNECT_BY_PATH 函数从根节点开始逐一遍历树形结构，如下所示。

select ename,
       ltrim(sys_connect_by_path(ename,','),',') path
  from emp
start with mgr is null
connect by prior empno=mgr
　
ENAME      PATH
---------- ----------------------------
KING       KING
JONES      KING,JONES
SCOTT      KING,JONES,SCOTT
ADAMS      KING,JONES,SCOTT,ADAMS
FORD       KING,JONES,FORD
SMITH      KING,JONES,FORD,SMITH
BLAKE      KING,BLAKE
ALLEN      KING,BLAKE,ALLEN
WARD       KING,BLAKE,WARD
MARTIN     KING,BLAKE,MARTIN
TURNER     KING,BLAKE,TURNER
JAMES      KING,BLAKE,JAMES
CLARK      KING,CLARK
MILLER     KING,CLARK,MILLER

为了得到根节点，只要提取出 PATH 里第一个 ENAME 即可。

select ename,
       substr(root,1,instr(root,',')-1) root
  from (
select ename,
       ltrim(sys_connect_by_path(ename,','),',') root
  from emp
start with mgr is null
connect by prior empno=mgr
       )
　
ENAME      ROOT
---------- ---------
KING
JONES      KING
SCOTT      KING
ADAMS      KING
FORD       KING
SMITH      KING
BLAKE      KING
ALLEN      KING
WARD       KING
MARTIN     KING
TURNER     KING
JAMES      KING
CLARK      KING
MILLER     KING