Trees in SQL: Nested Sets and Materizlized Path

by Vadim Tropashko   翻译: Janwer Zhang

原文链接： Trees in SQL:Nested Sets and Materizlized Path

关系数据库通常被认为是在其先辈网络和分层模型上的进步发展。在每个层级查询方面，当模型转换成依赖关系时，他们结果是惊人地不完整。几乎每两三个月总有关于如何在数据库中建立树模型的问题弹出在comp.database.theory新闻组。在本文中我将探讨两者用四个众所周知的方法的实现，并展示它们之间的关联。我们将找到一个可以被看作是具体路径(materialized path)和嵌套集合(nested sets)“混合式”的新方法。

链接表(Adjacency List)

---

树结构是有向无环图(Directed Acyclic Graph, 简称DAG)的一个特殊案例。描绘DAG结构的方式之一：

create table emp (
  ename varchar2(100),
  mgrname varchar2(100
);

emp 表的每条记录通过指向上级mgrname的ename来标识。例如，假如JONES向KING报告，于是emp表中含有<ename='JONES', mgrname='KING'>的记录。假设，emp表也包含<ename='SCOTT', mgrname='JONES'>。此外，假如emp表不含有<ename='SCOTT',mgrname='KING'>记录，对于其它每对毗连的记录也是如此，那么它就是所谓的邻接表(Adjacency List)。如果正好相反，那emp表是可传递的闭包关系。

一个典型的层次查询可能会询问SCOTT是否间接向KING报告。由于我们不知道两者间的层级数字，因此我们不能告诉emp表要进行多少次自连接，以至于这个任务不能用传统的SQL解决。假如知道emp表是传递闭包tcemp，那么这个查询是小事一桩：

select 'TRUE' from tcemp where ename='SCOTT' and mgrname='KING'

这个简便查询的牺牲代价 transitive closure maintenance .

此外，SQL扩展：SQL3/DB2递归查询，能执行层次查询：

with tcemp as （select ename,mgrname from tcemp 
union select tcemp.ename,emp.mgrname from tcemp, emp where tcemp.mgrname = emp.ename) 
select 'TRUE' from tcempwhere ename = 'SCOTT' and mgrname = 'KING';

这个tcemp计算作为中间关联，或采用Oracle专有连接的语法：

select 'TRUE' from (  select ename from emp  connect by prior mgrname = ename  
start with ename = 'SCOTT') where ename = 'KING';

其中内查询"chases the pointers"从SCOTT节点到树的根节点，而外查询检查KING节点是否在路径上。

链接表可以说是最直观的树模型。这是我们的主要焦点，不过，接下来还有两种方法。

具体化路径(Materialized Path）

---

在这种做法中每条记录存储到根部为止的整个路径。在我们前面的例子中，让我们假定KING为根节点，然后，记录ename="SCOTT" 通过路径 SCOTT->JONES->KING 连接到根部。现代数据库允许描绘一个节点清单作为一个单一的值，但由于具体路径在被发明之前的长时间里，约定停留在经由一些分隔符连接的普通字符串节点，最常见的'.'或'/。在后一种情况下，尤其明显一个类似UNIX文件系统的路径名。

应用更紧凑的变量方法，是在字符路径里我们使用兄弟分子代替节点的主键。扩展我们的例子：

ENAME	PATH
KING	1
JONES	1.1
SCOTT	1.1.1
ADAMS	1.1.1.1
FORD	1.1.2
SMITH	1.1.2.1
BLAKE	1.2
ALLEN	1.2.1
WARD	1.2.2
CLARK	1.3
MILLER	1.3.1

Path 1.1.2 指示FORD是父节点JONES的第二个孩子节点

让我们写一些查询。

1. 雇员FORD和它的一系列上级节点：

select e1.ename from emp e1, emp e2 where e2.path like e1.path || '%' and e2.ename='FORD'

 

2. 雇员JONES及它的所有间接子节点：

select e1.ename from emp e1, emp e2 where e1.path like e2.path || '%' and e2.ename='JONES'

 

尽管两个查询看起来是对称的，但在它们的各自的执行中有根本性的差别。如果一颗子树的下级节点相比整体层次大小而言是较小的，那么在数据库中通过执行主键抓取e2记录，然后执行e1.path范围的扫描，这是快速的保证。

在另一方面，上级节点的查询大体上是相同的

select e1.ename from emp e1, emp e2 where e2.path > e1.path and e2.path < e1.path || 'Z' 
and e2.ename='FORD'

 

或者，本来知道e2.path，请注意，它可以进一小减少到：

select e1.ename from emp e1 where e2.path>e1.path and e2.path<e1.path || 'Z'

 

这里，很显然path上的索引不会起作用(除了e2.path恰好是靠近域边界的意外情况下，以便有选择性的判定e2.path>e1.path)。明显的解决方法是，我们并没有利用数据库去计算出所有的上级路径！例如，1.1.2的上级是1.1和1。一个简单的递归字符串解析函数可以提取这些路径，那么回答上层的名称通过：

select e1.ename from emp where e1.path in ('1.1','1')

这应该是个快速级联的执行方案。

嵌套集合(Nested Sets)

---

具体路径和 Joe Celko的嵌套集合 均具有标准SQL语法层次查询的回应能力。在两种模型中，节点的全局位置在层次中是“编码”的，相反链接表的每个连接仅是一个近邻间的局部连接。类似于具体路径，嵌套集合模型也遭遇上层节点查询的性能问题。

select p2.emp from Personnel p1, Personnel p2where p1.lft between p2.lft and 
p2.rgtand p1.emp = 'Chuck'

（注意：这个查询借自previously cited Celko article ）

此处，这问题变得比具体路径情况下更明确：我们需要找出特定点的所有间隔。这个问题很难解决。尽管有像R-Tree的专门索引表，但它们中没有一个能像B- Tree一样被普遍接受。例如，如果顶层路径仅包含10个节点，而整棵树的大小为1000000，那么没有一种索引技术能够提供 1000000/10=100000倍的性能提升。（这样的性能改进因素通常与索引扫描范围类似，非常有选择性，以数据卷为条件的典型关联。）

不像一个具体路径，这边的技巧是我们 计算所有节点而不须为查询数据库做不必要的工作。
另一个--较根本性的--嵌套集合的缺点是嵌套集编码是暂时性的。如果我们在分层结构中间插入一个 节点，插入点边界以上的所有间隔必须重新计算。换句话说，当我们插入一条记录到数据库中，大概有一半左右的其它记录需要被更新。这也是为什么嵌套集合模型仅能接收有限的静态层次。

嵌套集合间的区间为整数。为尝试使嵌套集合模型对插入更有耐性。Celko建议我们放弃每个节点总是有(rgt-lft+1)/2个孩子的特性。依我之见，这是一个朝前了半步的解决方案：在一个 带有大 区间 和扩展编号的嵌套集合模型 中的任何 区间 仍然可以覆盖为增加更多的孩子而没空间留下的 区间 。假如这些 区间 都允许仅在分散点有边界（e.g.整数）。那么其中需要使用一个密集的域来代替，像有理数或实数。

嵌套区间（Nested Intervals)

---

嵌套区间归纳为嵌套集合。一个节点[clft,crgt]是一个[plft,prgt]的(间接)后代,假如：
plft <= clft and crgt >= prgt
该域名的区间范围不再仅限于整数：如果需要，我们准许有理数甚至实数。现在，一个合理的规则是，增加一个孩子节点不再是问题。一个类似规则的例子在父区间 [plft,prgt]里将找到一个空段[lft1,rgt1]并插入一个孩子节点[(2*lft1+rgt1)/3, (rgt1+2*lft)/3]:

插入之后，我们仍旧有两有空段[lft1,(2*lft1+rgt1)/3]和[(rgt1+2*lft)/3,rgt1]来增加更多的孩子到父节点。

在接下来的章节我们将改进这一固有规则。

偏序（Partial Order）

---

让我们看一下嵌套集合的二维图。我们假定rgt为水平x轴，lft为垂直y轴。那么嵌套 区间 树看起来像这样：

每个节点[lft,rgt]在二维圆锥形里有它的子节点边界y>=lft&x<=rgt。且右区间边界总是小于左区间，所有节点均不允许超过对角线y=x。

另一种方式看这幅图片应注意父节点的子类中的一个孩子节点，无论何时一系列定义在圆锥形孩子y>=clft&x<=crgt的所有点是父节点y>=plft&x<=prgt的一个子集。这个子集与平面上的圆锥形的关系是一个偏序。

现在我们知道遵照树节点的两个制约因素，我将确切地描述如何在xy平面上放置他们。

映射(The Mapping)

---

树根的选择完全是随意的：我们假定根节点为区间[0,1]。在我们几何图案的解释中，所有树节点属于xy平面上的正方形单元下部的三角形。

我们会通过归纳来进一步详细的描述映射 。对于每个树节点，让我们首先在xy平面定义两个重要的点。深度优先会聚点是对角线与通过节点的垂直线之间的一个交叉点。例如，节点<x=1,y=1/2>的深度优先会聚点为<x=1,y=1>。广度优先会聚点是对角线与通过这点的水平线之间的交叉点。例如， 点<x=1,y=1/2>的广度优先点为<x=1/2,y=1/2>。

现在，为每个父节点，我们定义首个孩子的位置为一个父亲点和深度优先会聚点之间中点的一半。那么，每个兄弟节点被定义为一个前兄弟点和广度优先会聚点中点的一半：

例如，节点2.1的位置在x=1/2, y=3/8。

现在映射定义了，很显然我们正使用密集型域：它既不是有理数，也不是实数，而是一对分数(当然，尽管两个前者已足够)。

有趣的是，父节点"1.2"的子树后代是节点"1.1"子树的一个向下缩小的复制品。 同样的，节点1.1的子树是节点"1."树的一个向下缩小的复制品，一个带自相似性的结构被称为分形图。

规范化(Normalization)

---

接着，我们注意到x和y并没有完全独立。假如知道他们的和，就能知道x和y两者是什么？给出有理数的分子和分母代表节点坐标的和，我们能计算x和y坐标追溯到：

function x_numer( numer integer, denom integer )
RETURN integer IS
ret_num integer;
ret_den integer;
BEGIN
ret_num := numer+1;
ret_den := denom*2;
while floor(ret_num/2) = ret_num/2 loop
ret_num := ret_num/2;
ret_den := ret_den/2;
end loop;
RETURN ret_num;
END;

function x_denom( numer integer, denom integer )
...
RETURN ret_den;
END;

 

在这边函数x_denom主体与x_numer的不同仅在返回变量。通俗地说，number+1的递增将ret_num/ret_den点垂直地向对角线方向移动，且x的坐标是这个值的一半，所以我们仅能让分母乘2。接着，分子和分母我们均减少相同的二次幂。

当然，y坐标被定义为和的一个补数:

function y_numer( numer integer, denom integer )
RETURN integer IS
num integer;
den integer;
BEGIN
num := x_numer(numer, denom);
den := x_denom(numer, denom);
while den < denom loop
num := num*2;
den := den*2;
end loop;
num := numer - num;
while floor(num/2) = num/2 loop
num := num/2;
den := den/2;
end loop;
RETURN num;
END;

function y_denom( numer integer, denom integer )
...
RETURN den;
END;

 
现在测试（这里39/32的节点是1.3.1):

select x_number(39,32)||'/'||x_denom(39,32),
y_number(39,32)||'/'||y_denom(39,32) from dual
5/8  19/32

select 5/8+19/32,39/32 from dual
1.21875 1.21875

 
我不用一个浮数点来代表一个实数，而所有函数用整数计算来替代。说穿了，是浮点数的一般概念，和IEEE标准，尤其是仅对渲染3D游戏有益。在最后的测试中，尽管我们使用一个浮点来验证5/8和19/32，通过前查询的返回，证明确实增加到了39/32。

我们将存储这两个整数--分子和分母的x和y坐标和--做为一个编码节点路径。碰巧，Celko的嵌套集合也是是两个整数。不像嵌套集合，我们的映射是稳定的：每个节点在xy平面有一个预定义的位置，在涉及节点位置的层次查询时不需引用数据库便能回应。在这方面，我们的分层模型本质上是一个有理数编码的原型路径。

查找父编码和兄弟编号

---

给一个 numer/denom编码的孩子节点，我们可以这样找它的父节点：

function parent_numer( numer integer, denom integer )
RETURN integer IS
ret_num integer;
ret_den integer;
BEGIN
if numer=3 then
return NULL;
end if;
ret_num := (numer-1)/2;
ret_den := denom/2;
while floor((ret_num-1)/4) = (ret_num-1)/4 loop
ret_num := (ret_num+1)/2;
ret_den := ret_den/2;
end loop;
RETURN ret_num;
END;

function parent_denom( numer integer, denom integer )
...
RETURN ret_den;
END;

 
背后的算法如下：假如节点已是最顶层--则所有这些节点有一个分子等于3--且节点没有父亲。否则，我们须垂直下移xy平面到跟深度优先会聚点相等的距离。如果节点正好是第一个孩子，那么这就是回应。否则我们须平移到跟广度优先会聚点相等的距离直到见到父节点。

这里是测试方法(在这27/32的节点是2.1.2，当7/8是2.1时)；

select parent_numer(27,32)||'/'||parent_denom(27,32) from dual
7/8

 
在前面的方法，当横向导航时节将得到兄弟编号的计算步骤：

function sibling_number( numer integer, denom integer )
RETURN integer IS
  ret_num integer;
  ret_den integer;
  ret integer;
BEGIN
  if numer=3 then
    return NULL;
  end if;
  ret_num := (numer-1)/2;
  ret_den := denom/2;
  ret := 1;
while floor((ret_num-1)/4) = (ret_num-1)/4 loop
  if ret_num=1 and ret_den=1 then
  return ret;
end if;
ret_num := (ret_num+1)/2;
ret_den := ret_den/2;
ret := ret+1;
end loop;
RETURN ret;
END;

 
一个节点在最近的一级的一个特殊停止条件，ret_num=1和ret_den=1是必须的。
那测试：

select sibling_number(7,8) from dual;
             1

 
计算具体路径和节点间的距离

---

严格来讲，我们没有使用具体路径，由于我们的编码是可选择的。另一方面，一个具体路径在 层次结构上能提供 一个更直觉的节点位置，这样我们能使用具体路径为数据输入/出，假如我们提供映射到我们的模型。

从上节来看实现是一个简单的方法应用。我们打印兄弟编号，跳到父节点，然后重复以上两步直到根部为止。

function path( numer integer, denom integer )
RETURN varchar2 IS
BEGIN
if numer is NULL then
return '';
end if;
RETURN path(parent_numer(numer, denom),
parent_denom(numer, denom))
|| '.' || sibling_number(numer, denom);
END;

select path(15,16) from dual

.2.1.1

 
现在我们准备来写主要的查询：给2个节点，P和C，何时节P是C的父节点? 如果从P可达C, 一个很普通的查询将返回P和C之间的居次编号和一些异常提示；反之：

function distance( num1 integer, den1 integer, num2 integer, den2 integer )
RETURN integer IS
BEGIN
 if num1 is NULL then
 return -999999;
end if;
 if num1=num2 and den1=den2 then
  return 0;
end if;
 RETURN 1+distance(parent_numer(num1, den1), parent_denom(num1, den1), num2,den2);
END;

select distance(27,32,3,4) from dual
 2 

负数字都作为异常来处理。假如节点num1/den1从num2/den2不可达，那么将导向回根部，且将返回层次(num1/den1)-999999（读者建议找个更得体的解释）。

可选择方式来回答是否通过简单计算x和y坐标来连接两个节点，然后检查是否父节点闭区间于孩子。尽管没有涉及磁盘方法，检查是否偏序的节点间存在似乎更小代价。另一方面，它仅是一个比较两个整数是否为原子操作的人工打造的计算机体系结构。该方法的更完美的实现将包含一个无限区间的整数域（这些类型的数字是计算机系统所支持的），那么一个比较操作也将得循环。

我们的系统不会完全没有一个路径的反向函数，一当提供路径时，它会返回一个节点numer/denom的值。让我们介绍两个辅助函数，首先：

function child_numer
( num integer, den integer, child integer )
RETURN integer IS
BEGIN
RETURN num*power(2, child)+3-power(2, child);
END;

function child_denom
( num integer, den integer, child integer )
RETURN integer IS
BEGIN
RETURN den*power(2, child);
END;

select child_numer(3,2,3) || '/' ||
child_denom(3,2,3) from dual

19/16

 
例如，节点1(编码为3/2)的第三个孩子节点节点是1.3(编码为19/16)。
路径编码函数是：

function path_numer( path varchar2 )
RETURN integer IS
 num integer;
 den integer;
 postfix varchar2(1000);
 sibling varchar2(100);
BEGIN
   num := 1;
   den := 1;
   postfix := '.' || path || '.';
while length(postfix) > 1 loop
  sibling := substr(postfix, 2, instr(postfix,'.',2)-2);
  postfix := substr(postfix, instr(postfix,'.',2), length(postfix) -instr(postfix,'.',2)+1);
  num := child_numer(num,den,to_number(sibling));
  den := child_denom(num,den,to_number(sibling));
  end loop;
 RETURN num;
END;

 function path_denom( path varchar2 ) ...
  RETURN den;
 END;

select path_numer('2.1.3') || '/' || path_denom('2.1.3') from dual
 51/64 

最后测试

---

现在基础架构已完成，我们可以测试它，让我们创建一个层次结构

create table emps (
name varchar2(30),
numer integer,
denom integer
)

alter table emps
ADD CONSTRAINT uk_name UNIQUE (name) USING INDEX
(CREATE UNIQUE INDEX name_idx on emps(name))
ADD CONSTRAINT UK_node
UNIQUE (numer, denom) USING INDEX
(CREATE UNIQUE INDEX node_idx on emps(numer, denom))

然后填入一些数据：

insert into emps values ('KING',
path_numer('1'),path_denom('1'));
insert into emps values ('JONES',
path_numer('1.1'),path_denom('1.1'));
insert into emps values ('SCOTT',
path_numer('1.1.1'),path_denom('1.1.1'));
insert into emps values ('ADAMS',
path_numer('1.1.1.1'),path_denom('1.1.1.1'));
insert into emps values ('FORD',
path_numer('1.1.2'),path_denom('1.1.2'));
insert into emps values ('SMITH',
path_numer('1.1.2.1'),path_denom('1.1.2.1'));
insert into emps values ('BLAKE',
path_numer('1.2'),path_denom('1.2'));
insert into emps values ('ALLEN',
path_numer('1.2.1'),path_denom('1.2.1'));
insert into emps values ('WARD',
path_numer('1.2.2'),path_denom('1.2.2'));
insert into emps values ('MARTIN',
path_numer('1.2.3'),path_denom('1.2.3'));
insert into emps values ('TURNER',
path_numer('1.2.4'),path_denom('1.2.4'));
insert into emps values ('CLARK',
path_numer('1.3'),path_denom('1.3'));
insert into emps values ('MILLER',
path_numer('1.3.1'),path_denom('1.3.1'));
commit;

 
所有函数在前节已编写可方便地连接到一个单独的视图中:

create or replace
view hierarchy as
select name, numer, denom,
y_numer(numer,denom) numer_left,
y_denom(numer,denom) denom_left,
x_numer(numer,denom) numer_right,
x_denom(numer,denom) denom_right,
path (numer,denom) path,
distance(numer,denom,3,2) depth
from emps

 

最后，我们创建一个分层报告

• 深度优先枚举，按左区间排序

select lpad(' ',3*depth)||name
from hierarchy order by numer_left/denom_left

LPAD('',3*DEPTH)||NAME
-----------------------------------------------
KING
   CLARK
      MILLER
   BLAKE
      TURNER
      MARTIN
      WARD
      ALLEN
   JONES
      FORD
         SMITH

 

• 广度优先枚举，按右区间排序

select lpad(' ',3*depth)||name
from hierarchy order by numer_right/denom_right desc

LPAD('',3*DEPTH)||NAME
-----------------------------------------------------
KING
   JONES
      SCOTT
         ADAMS
      FORD
         SMITH
   BLAKE
      ALLEN
      WARD
      MARTIN
      TURNER
   CLARK
      MILLER

 

• 深度优先枚举，按路径排序（输出同#2)

select lpad(' ',3*depth)||name
from hierarchy order by path

LPAD('',3*DEPTH)||NAME
-----------------------------------------------------
KING
   JONES
      SCOTT
         ADAMS
      FORD
         SMITH
   BLAKE
      ALLEN
      WARD
      MARTIN
      TURNER
   CLARK
      MILLER

 

• JONES的所有孩子， 不 包括自己

select h1.name from hierarchy h1, hierarchy h2
where h2.name = 'JONES'
and distance(h1.numer, h1.denom,
             h2.numer, h2.denom)>0;

NAME
------------------------------
SCOTT
ADAMS
FORD
SMITH

 

• FORD的所有祖先，不包含自己

select h2.name from hierarchy h1, hierarchy h2
where h1.name = 'FORD'
and distance(h1.numer, h1.denom,
             h2.numer, h2.denom)>0;

NAME
------------------------------
KING
JONES

 

关于本文作者
Vadim Tropashko 工作于Orace公司的Real World Performance组。在以往的生活，他是应用程序员，并曾把B.Stroustrup的《C++编程语言》第二版译成俄文。他当前兴趣包括SQL优化，数据库约束和计算机代数学系统。