基于擴展Dewey編碼的XML結(jié)構(gòu)連接算法

楊 揚，李海歌

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

0 引 言

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

1 相關(guān)研究

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

2 IPE編碼方案

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

2.1 IPE編碼（improved prefix encoding）

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

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

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

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

圖1 IPE編碼片段

2.2 IPE編碼的XPath查詢

本文給出的基于IPE編碼的結(jié)構(gòu)連接算法在進行結(jié)構(gòu)關(guān)系判斷時，需要比較結(jié)點的編碼大小，比較規(guī)則為：父小于子，前驅(qū)兄弟小于后繼兄弟，后裔大于前驅(qū)兄弟且小于后繼兄弟。

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

利用IPE編碼直接判斷結(jié)點之間的結(jié)構(gòu)關(guān)系，加速了結(jié)構(gòu)連接，表1給出了基于IPE編碼的XPath查詢的判別方法。

表1 IPE編碼的XPath查詢

3 B－S算法（binary－stack）

3.1 B－S算法思想

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

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

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 算法分析

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

4 實 驗

4.1 實驗環(huán)境

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

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

圖2 實驗測試所用DTD

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

表2 查詢用例

4.2 實驗分析

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

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

表3 STD算法與B－S算法掃描元素結(jié)點數(shù)量的對比

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

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

5 結(jié)束語

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

［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數(shù)據(jù)的查詢技術(shù)［J］.軟件學(xué)報，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查詢的結(jié)構(gòu)連接算法［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）.［王仕福，郝忠孝.基于區(qū)間編碼的有效XML結(jié)構(gòu)連接［J］.哈爾濱理工大學(xué)學(xué)報，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數(shù)據(jù)庫技術(shù)［M］.2版.北京：清華大學(xué)出版社，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）.［覃遵躍，蔡國民，黃云.基于擴展區(qū)間編碼的XML兄弟關(guān)系結(jié)構(gòu)連接［J］.南通大學(xué)學(xué)報（自然科學(xué)版），2009，8（1）：26－28.］

［6］XU Juan，LI Zhan－h(huán)uai，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）.［徐娟，李戰(zhàn)懷，婁穎.基于節(jié)點位置信息的降低更新代價前綴編碼方案研究［J］.計算機科學(xué)，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－h(huán)ong，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關(guān)鍵詞檢索算法［J］.軟件學(xué)報，2009，20（4）：910－917.］

［9］ZHANG Bo，GENG Zhi－h(huán)ua，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路徑查詢的 自 適 應(yīng) 結(jié) 構(gòu) 索 引［J］.軟 件 學(xué) 報，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）.［覃遵躍，黃云.一種基于擴展區(qū)間編碼的XML結(jié)構(gòu)連接算法［J］.計算機系統(tǒng)應(yīng)用，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結(jié)構(gòu)連接算法［J］.山東科技大學(xué)學(xué)報（自然科學(xué)版），2009，28（2）：92－96.］

［12］WEN Si，WEN Gui－h(huán)ua.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）.［文思，文貴華.基于擴展前綴編碼的左孩子右兄弟結(jié)構(gòu)連接算法［J］.計算機工程與設(shè)計，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）.［朱曉娟.基于擴展區(qū)間編碼的XML結(jié)構(gòu)連接算法［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］.河南大學(xué)學(xué)報（自然科學(xué)版），2010，40（1）：85－89.］

［15］ZHENG Hong－h(huán)ui，GUO Hong.XML keyword search algorithm based on efficient LCA［J］.Journal of Computer Applications，2010，37（12）：120－124（in Chinese）.［鄭弘暉，郭紅.基于有效最低公共祖先的XML關(guān)鍵字查詢算法［J］.計算機應(yīng)用，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］.小型微型計算機系統(tǒng)，2011，32（5）：837－839.］