Trees in SQL: Nested Sets and Materizlized P

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

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

        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';
      

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

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

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

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

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

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

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

每个节点[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;
      

      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;
    

      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
    

      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;
    

      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;
    

      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
    

      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 
    

      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

    

      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