基于擴展Dewey編碼的XML結構連接算法

楊 揚，李海歌

（1.河南大學 計算中心，河南 開封475004；2.開封市建筑設計院有限公司，河南 開封475004）

0 引 言

XML作為互聯網中一種數據表示與交換的標準，具有高效結構連接算法的查詢方法成為XML數據庫的研究熱點。當前，為優化XML數據查詢和更新，AList和DList列表之間的結構連接操作構成了結構查詢的核心，為了加速結構連接，研究人員首先對XML文檔樹結點編碼來判斷結點之間的結構關系，而無需遍歷整棵XML文檔樹。再者通過高效的結構連接算法提高查詢效率。高效的XML查詢重在優化的結構連接算法，與之相關的有益算法大多基于歸并思想，根據XML文件格式的特點和編碼規則減少或避免了無效的結構連接。為了能夠規避不參與結構連接的結點，一些算法思想采用索引結構進一步減少連接的掃描代價，但索引的維護又需要額外的時間和空間開銷。為解決上述問題，本文給出的擴展的Dewey編碼，加速了結點的結構關系判斷，在此基礎上，論文改進了Stack－Tree－Desc（STD）算法，提出了一種不依賴于索引結構的優化算法，利用棧進行緩存來減少連接次數，在查找下一個需要參與連接的結點時引入二分查找，有效地跳過了不必要的結構連接，無需順序掃描，最壞情況下AList和DList列表只需各遍歷一次。實驗結果表明，論文所用編碼方案和改進算法具有較好的查詢效果。

1 相關研究

當前，多數結構連接算法基于歸并結構，根據XML文件格式的特點和編碼規則減少或避免了無效的結構連接。C.Zhang和J.Naughton等提出了一種執行性能優于關系查詢引擎的結構連接算法MPMGJN，該算法能有效地實現包含連接，但多次重復地掃描內表會影響算法性能。為了避免對內表重復掃描，S.Al－Khalifa和 H.V.Jagadish等提出了STD算法，該算法維護了一個用于存放可能需要連接的祖先結點棧，需對AList和DList列表分別順序掃描一次即可實現包含關系的結構連接。Shu－Yao Chien、Z.Vagena和Donghui Zhang等提出的Anc－Desc－B＋算法，根據兩個列表中有些結點能夠事先判斷出不必參與結構連接，為減少掃描代價，算法中的B＋樹索引成功地跳過了不必要的結點，優化了Stack－Tree算法。而B＋樹索引維護時需要額外的時間和空間開銷，本文從另一角度，不建立索引，在查找下一個需要參與結構連接的AList列表中的a結點與DList列表中的d結點時，采取了二分查找來跳過不需參與連接的結點，最壞情況下AList和DList列表僅需掃描一次即可實現結構連接。

2 IPE編碼方案

XML結構查詢，通常先將XML文檔中的結點按照某種編碼方案編碼，利用結點間的編碼規律來判定AList和DList列表結點對（a，d）的結構關系。

2.1 IPE編碼（improved prefix encoding）

IPE編碼，本質上是一種擴展的Dewey編碼，由字母、整數、點（.）組成，雙親結點的編碼作為該結點編碼的前綴。

定義1 編碼映射：集合N＝｛1，2，3，4，5，6，7，8，9｝與集合C＝｛A，B，C，D，E，F，G，H，I｝，規定f＝｛＜1，A＞，＜2，B＞，＜3，C＞，＜4，D＞，＜5，E＞，＜6，F＞，＜7，G＞，＜8，H＞，＜9，I＞｝，f：N→C，對唯一n∈N，有唯一的c∈C與之對應。

定義2 IPE編碼：設XML文檔樹中結點u的IPE編碼為p（u），則結點u的孩子結點v的IPE編碼c（v）＝p（u）Nv，其中c（v）編碼的層次數稱為層級L；每一層的區別編碼Nv代表了結點v在結點u的所有孩子結點中位置關系，各層的結點編碼之間用數字唯一表示，Nv是個位數，以Nv原數值表示，若Nv大于10，除個位數不變，其它位的轉換均使用定義1的編碼映射來實現。

圖1為IPE編碼片段。例如，Dewey編碼“2.31.3.2”，取消原 Dewey編碼中各層之間的“.”分隔符，改進為IPE編碼“2C132”，節省了存儲空間，也可清晰地判斷各層編碼的分隔。

圖1 IPE編碼片段

2.2 IPE編碼的XPath查詢

本文給出的基于IPE編碼的結構連接算法在進行結構關系判斷時，需要比較結點的編碼大小，比較規則為：父小于子，前驅兄弟小于后繼兄弟，后裔大于前驅兄弟且小于后繼兄弟。

例如，圖1中所示的編碼，“2C1”＜“2C11”＜“2C12”＜“2C122”＜“2C13”＜“2C131”。

利用IPE編碼直接判斷結點之間的結構關系，加速了結構連接，表1給出了基于IPE編碼的XPath查詢的判別方法。

表1 IPE編碼的XPath查詢

3 B－S算法（binary－stack）

3.1 B－S算法思想

基于棧的結構連接算法在效率上高于直接歸并算法，IPE編碼支持基于棧的連接算法，因此提出的基于IPE編碼的B－S算法也是基于棧的。B－S算法中輸入列表是對XML文檔樹前序遍歷有序，輸出結果按后裔有序。STD算法的I/O代價是對AList和DList列表各順序掃描一遍，BS算法改進了STD算法，采取了二分查找來跳過不需參與連接的結點，有效地減少了掃描結點的數量。

B－S算法的基本思想是：設參加結構連接的兩個列表AList和DList，如果a和d均不是棧頂元素的后裔，則將棧頂元素出棧。若a是d的祖先，將a入棧，同時將a指向AList列表中下一個參與結構連接的結點。若上述兩個條件均不滿足，則將棧內所有與當前d形成祖先/后裔關系的結點對輸出，并將d指向DList列表中下一個參與結構連接的結點。AList和DList列表為靜態有序表，按IPE編碼升序排列。在靜態有序表AList和DList中查詢符合結構連接條件的結點，采用了查找效率很高的二分查找方法，避開了AList與DList列表中結點的逐個掃描。B－S算法中的第（7）到（18）步是在AList列表中查找下一個參與結構連接的a結點，第（23）步與第（7）到（18）步相似，調用BinarySearch（d，first，last，a），在 DList列表中查找下一個參與結構連接的d結點。

3.2 B－S算法

（1）a ＝AList.firstNode ＆＆ d ＝DList.firstNode＆＆stack s is empty；

（2）while（AList and DList are not empty or stack s is not empty）｛

（3） if（neither a or d is the descendant of the s.top）｛

（4） s.pop（s.top）；｝

（5） else if（the IPE of a is the substring of the IPE of d）｛//a is the ancestor of d

（6） s.push（a）；

（7） BinarySearch（a，first，last，d）｛//to search next a which participates in structural join

（8） mid＝（first＋last）/2；

（9） if（first＞last）

（10） return false；

（11） else if（d＜a［mid］）

（12） return BinarySearch（a，first，mid－1，d）

（13） else if（d＞a［mid］）//a is the ancestor of d

（14） return BinarySearch（a，mid＋1，last，d）

（15） else if（d＞a［mid］＆＆the IPE of a is the substring of the IPE of d）

（16） return a［mid］；//a［mid］is the target

（17） ｝//to search next a which participates in structural join using BinarySearch

（18） ｝

（19） else｛

（20） for（t＝s.bottom；t！＝null；t－－）｛

（21） append（a，d）to output；

（22） ｝

（23） BinarySearch（d，first，last，a）//to search next d which participates in structural join

（24） ｝

（25）｝

3.3 算法分析

在查找下一個進行結構連接的結點時，STD算法為有序表的順序查找，平均查找長度較大，特別是當列表中結點很多時，查找效率較低，時間復雜度為O（n）。B－S算法在查找下一個有效結構連接的結點時，采用了有序表的二分查找，時間復雜度最好情況O（1），最壞情況O（logn），平均情況O（logn）。并且當結點分布緊湊且嵌套較多時，引入的二分查找效率較高。可見B－S算法在處理下一個能夠參與結構連接問題上優于STD算法。

4 實 驗

4.1 實驗環境

本文實驗環境為：英特爾酷睿2雙核T5870@2.00GHz筆記本處理器，2GB內存，160GB硬盤，Windows XP 專 業 版（32 位/SP2/DirectX 9.0c） 操 作 系 統，NetBeans IDE 6.8for Java。

實驗所用數據集的DTD如圖2所示，根據該DTD利用XML文檔生成器自動生成一個XML文檔。該測試文檔大小為67.3MB，共有元素和屬性結點1648372個，其中toy元素2498個、grade元素402113個、production元素6243個、assembling元素393370個、instruction元素157641個。實驗對基于IPE編碼的B－S算法進行性能分析。

圖2 實驗測試所用DTD

實驗測試查詢用例，見表2。查詢Q1為最常見的查詢，父結點僅有一個孩子結點，且孩子結點又為葉子結點；查詢Q2較為復雜，可多次出現的父結點擁有多個孩子結點，孩子結點可零次或多次出現，而且孩子結點又存在嵌套關系；查詢Q3反映雙親結點嵌套；查詢Q4是一個常見查詢，它沒有明確指定連接的孩子結點的標記名。

表2 查詢用例

4.2 實驗分析

實驗通過保持孩子結點數量不變而雙親結點的百分比改變的方法，對STD算法與B－S算法的性能進行測試，分別驗證算法結構連接時掃描結點的數量和算法所耗用的時間。

（1）算法連接結點數：即符合某種結構關系的結點配對時掃描的元素結點的數量，這是算法跳過不參加結構連接結點的優越性的體現。表3表現了維持原有孩子結點的百分比，隨機按比例刪除父結點的情況，將STD算法與BS算法依據論文中DTD生成的XML文件進行實際掃描結點數比較。由表3可知，在相同的百分比下，B－S算法掃描的結點數量少于STD算法；當按比例減少XML文件中父結點的百分比時，兩種算法實際參與掃描、形成相應結構關系結點對的數量均有所降低，但B－S算法掃描結點數量少于STD算法。在跳過不相關結點的能力上，B－S算法優于STD算法。

表3 STD算法與B－S算法掃描元素結點數量的對比

（2）結構連接耗用時間：反映了算法的性能優劣。圖3中，兩種算法的查詢耗用時間均隨雙親結點百分比的降低而減少，但B－S算法耗用的時間要少于STD算法。B－S算法的優點在于不必將結點逐一比較、全部訪問，AList和DList中的元素利用二分查找方法每次進行折半查找處理，提高了查詢效率。當雙親結點的數量減少時，B－S算法由于能夠減少被掃描元素結點，因此它的性能優于順序掃描的STD算法，這在圖3（a）、（b）、（d）中均可體現。

圖3 兩種算法運行時間比較

5 結束語

本文基于Dewey編碼給出了IPE編碼方案，它加速了XPath查詢軸的結構關系的判斷，有效地輔助了B－S算法的執行。為跳過無益的結點掃描，B－S算法對STD算法進行了改進，通過二分查找，每次將查找折半處理，縮小了查找范圍，從而提高了結構連接的效率。實驗結果表明改進后的B－S算法比STD算法具有較好的查詢效率。結構連接作為XML查詢中的關鍵，因此，下一步的研究工作是在此基礎上研究如何進一步優化查詢操作。

［1］KONG Ling－bo，TANG Shi－wei，YANG Dong－qing，et al.Querying techniques for XML data［J］.Journal of Software，2007，18（6）：1400－1418（in Chinese）.［孔令波，唐世渭，楊冬青，等.XML數據的查詢技術［J］.軟件學報，2007，18（6）：1400－1418.］

［2］HUANG Yuan，YANG Wei－wei.Structural join algorithm in XML query［J］.Computer Aided Engineering，2007，16（1）：74－75（in Chinese）.［黃淵，楊薇薇.XML查詢的結構連接算法［J］.計算機輔助工程，2007，16（1）：74－75.］

［3］WANG Shi－fu，HAO Zhong－xiao.Efficient structural join for XML based on region encoding［J］.Journal of Harbin University of Science and Technology，2008，13（2）：53－56（in Chinese）.［王仕福，郝忠孝.基于區間編碼的有效XML結構連接［J］.哈爾濱理工大學學報，2008，13（2）：53－56.］

［4］ WAN Chang－xuan，LIU Xi－ping.XML database technology［M］.2nd ed.Beijing：Tsinghua University Press，2008（in Chinese）.［萬常選，劉喜平.XML數據庫技術［M］.2版.北京：清華大學出版社，2008.］

［5］QIN Zun－yue，CAI Guo－min，HUANG Yun.Sibling structural join for XML document based on extensible region coding［J］.Journal of Nantong University（Natural Science Edition），2009，8（1）：26－28（in Chinese）.［覃遵躍，蔡國民，黃云.基于擴展區間編碼的XML兄弟關系結構連接［J］.南通大學學報（自然科學版），2009，8（1）：26－28.］

［6］XU Juan，LI Zhan－huai，LOU Ying.Novel position－based prefix encoding approach to reduce update cost for dynamic XML data［J］.Computer Science，2009，36（2）：167－171（in Chinese）.［徐娟，李戰懷，婁穎.基于節點位置信息的降低更新代價前綴編碼方案研究［J］.計算機科學，2009，36（2）：167－171.］

［7］XU Liang，LING T W，WU Hua－yu，et al.DDE：From Dewey to a fully dynamic XML labeling scheme［C］.Proceedings of the ACM Conference on SIGMOD，2009：719－730.

［8］JI Cong－rui，DENG Zhi－hong，TANG Shi－wei.An XML keyword retrieval algorithm based on nearest pair［J］.Journal of Software，2009，20（4）：910－917（in Chinese）.［吉聰睿，鄧志鴻，唐世渭.基于Nearest Pair的XML關鍵詞檢索算法［J］.軟件學報，2009，20（4）：910－917.］

［9］ZHANG Bo，GENG Zhi－hua，ZHOU Ao－ying.Adaptive structural index for efficient processing of XML path queries［J］.Journal of Software，2009，20（7）：1812－1824（in Chinese）.［張博，耿志華，周傲英.一種支持高效XML路徑查詢的 自 適 應 結 構 索 引［J］.軟 件 學 報，2009，20（7）：1812－1824.］

［10］QIN Zun－yue，HUANG Yun.A structural joins algorithm based on extended region coding［J］.Computer Systems ＆Applications，2009，19（4）：61－64（in Chinese）.［覃遵躍，黃云.一種基于擴展區間編碼的XML結構連接算法［J］.計算機系統應用，2009，19（4）：61－64.］

［11］JIANG Mei－xian，LU Yan.A new encoding－based XML structural join algorithm［J］.Journal of Shandong University of Science and Technology（Natural Science），2009，28（2）：92－96（in Chinese）.［蔣美仙，路燕.一種新的基于編碼的XML結構連接算法［J］.山東科技大學學報（自然科學版），2009，28（2）：92－96.］

［12］WEN Si，WEN Gui－hua.Left child and right sibling structural join algorithm based on extended prefix－coding［J］.Computer Engineering and Design，2010，31（10）：2312－2319（in Chinese）.［文思，文貴華.基于擴展前綴編碼的左孩子右兄弟結構連接算法［J］.計算機工程與設計，2010，31（10）：2312－2319.］

［13］ZHU Xiao－juan.XML structural join algorithm based on extended region coding［J］.Computer Engineering，2010，36（22）：49－51（in Chinese）.［朱曉娟.基于擴展區間編碼的XML結構連接算法［J］.計算機工程，2010，36（22）：49－51.］

［14］YANG Yang，YIN Ke.A path query based on XML prefix encoding［J］.Journal of Henan University（Natural Science），2010，40（1）：85－89（in Chinese）.［楊揚，尹柯.一種基于XML前綴編碼的路徑查詢［J］.河南大學學報（自然科學版），2010，40（1）：85－89.］

［15］ZHENG Hong－hui，GUO Hong.XML keyword search algorithm based on efficient LCA［J］.Journal of Computer Applications，2010，37（12）：120－124（in Chinese）.［鄭弘暉，郭紅.基于有效最低公共祖先的XML關鍵字查詢算法［J］.計算機應用，2010，37（12）：120－124.］

［16］ZHAO Sheng－meng，ZHAO Lei.Extended Dewey encoding algorithm of Twig pattern query without merging［J］.Journal of Chinese Computer Systems，2011，32（5）：837－839（in Chinese）.［趙圣猛，趙雷.一種采用擴展Dewey編碼非歸并的小枝模式查詢算法［J］.小型微型計算機系統，2011，32（5）：837－839.］