亚洲免费在线-亚洲免费在线播放-亚洲免费在线观看-亚洲免费在线观看视频-亚洲免费在线看-亚洲免费在线视频

Trees in SQL: Nested Sets and Materizlized P

系統 1656 0
by Vadim Tropashko ? 翻譯: Janwer Zhang

關系數據庫通常被認為是在其先輩網絡和分層模型上的進步發展。在每個層級查詢方面，當模型轉換成依賴關系時，他們結果是驚人地不完整。幾乎每兩三個月總有關于如何在數據庫中建立樹模型的問題彈出在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優化，數據庫約束和計算機代數學系統。


Trees in SQL: Nested Sets and Materizlized Path


更多文章、技術交流、商務合作、聯系博主

微信掃碼或搜索：z360901061

微信掃一掃加我為好友

QQ號聯系： 360901061

您的支持是博主寫作最大的動力，如果您喜歡我的文章，感覺我的文章對您有幫助，請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧，狠狠點擊下面給點支持吧，站長非常感激您！手機微信長按不能支付解決辦法：請將微信支付二維碼保存到相冊，切換到微信，然后點擊微信右上角掃一掃功能，選擇支付二維碼完成支付。

【本文對您有幫助就好】元

您的支持是博主寫作最大的動力，如果您喜歡我的文章，感覺我的文章對您有幫助，請用微信掃描上面二維碼支持博主2元、5元、10元、自定義金額等您想捐的金額吧，站長會非常 感謝您的哦！！！

發表我的評論
最新評論 總共0條評論
主站蜘蛛池模板： 亚洲国产成人久久综合区 | 免费黄色a | 国产一区日韩二区欧美三 | 亚洲va欧美va人人爽夜夜嗨 | 综合久久国产对白 | 久久免费看| 亚洲国产激情一区二区三区 | 国产亚洲精品久久 | 亚洲欧美日韩人成 | 91精品视频在线看 | 高清一级做a爱过程免费视频 | xo欧美性另类 | 国产伦乱 | 亚洲综合色婷婷在线观看 | 国产一区二区三区视频在线观看 | 久久99精品九九九久久婷婷 | 亚洲 欧洲 另类 综合 自拍 | 亚洲午夜片子大全精品 | 国产福利视频一区二区微拍 | 亚洲欧美色鬼久久综合 | 亚洲第一页色 | 久精品视频村上里沙 | 最新中文字幕在线观看 | 99精品视频在线视频免费观看 | 国产精品分类视频分类一区 | 精品国产91| 日韩精品欧美亚洲高清有无 | 亚洲男女在线 | 四虎国产在线观看 | 亚洲 欧洲 另类 综合 自拍 | 天天插天天干天天射 | 在线观看久草视频 | 日韩射吧| 中文字幕一区久久久久 | 久久成人国产精品二三区 | 久青草网站 | 四虎永久在线精品 | 97婷婷狠狠成人免费视频 | 2022国产91精品久久久久久 | 国产极品福利 | 日本免费一二三区 |