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
最后,标出 ROOT
列为 Null
的行,它就是我们要寻找的根节点行。