楊 揚(yáng)，李海歌

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

0 引 言

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

1 相關(guān)研究

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

2 IPE編碼方案

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

2.1 IPE編碼（improved prefix encoding）

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

定義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，對(duì)唯一n∈N，有唯一的c∈C與之對(duì)應(yīng)。

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

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

圖1 IPE編碼片段

2.2 IPE編碼的XPath查詢

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

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

利用IPE編碼直接判斷結(jié)點(diǎn)之間的結(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算法中輸入列表是對(duì)XML文檔樹(shù)前序遍歷有序，輸出結(jié)果按后裔有序。STD算法的I/O代價(jià)是對(duì)AList和DList列表各順序掃描一遍，BS算法改進(jìn)了STD算法，采取了二分查找來(lái)跳過(guò)不需參與連接的結(jié)點(diǎn)，有效地減少了掃描結(jié)點(diǎn)的數(shù)量。

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

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?。絥ull；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 算法分析

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

4 實(shí) 驗(yàn)

4.1 實(shí)驗(yàn)環(huán)境

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

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

圖2 實(shí)驗(yàn)測(cè)試所用DTD

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

表2 查詢用例

4.2 實(shí)驗(yàn)分析

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

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

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

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

圖3 兩種算法運(yùn)行時(shí)間比較

5 結(jié)束語(yǔ)

本文基于Dewey編碼給出了IPE編碼方案，它加速了XPath查詢軸的結(jié)構(gòu)關(guān)系的判斷，有效地輔助了B－S算法的執(zhí)行。為跳過(guò)無(wú)益的結(jié)點(diǎn)掃描，B－S算法對(duì)STD算法進(jìn)行了改進(jìn)，通過(guò)二分查找，每次將查找折半處理，縮小了查找范圍，從而提高了結(jié)構(gòu)連接的效率。實(shí)驗(yàn)結(jié)果表明改進(jìn)后的B－S算法比STD算法具有較好的查詢效率。結(jié)構(gòu)連接作為XML查詢中的關(guān)鍵，因此，下一步的研究工作是在此基礎(chǔ)上研究如何進(jìn)一步優(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é)報(bào)，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］.計(jì)算機(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é)報(bào)，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）.［萬(wàn)常選，劉喜平.XML數(shù)據(jù)庫(kù)技術(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）.［覃遵躍，蔡國(guó)民，黃云.基于擴(kuò)展區(qū)間編碼的XML兄弟關(guān)系結(jié)構(gòu)連接［J］.南通大學(xué)學(xué)報(bào)（自然科學(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é)點(diǎn)位置信息的降低更新代價(jià)前綴編碼方案研究［J］.計(jì)算機(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é)報(bào)，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é) 報(bào)，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）.［覃遵躍，黃云.一種基于擴(kuò)展區(qū)間編碼的XML結(jié)構(gòu)連接算法［J］.計(jì)算機(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é)報(bào)（自然科學(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）.［文思，文貴華.基于擴(kuò)展前綴編碼的左孩子右兄弟結(jié)構(gòu)連接算法［J］.計(jì)算機(jī)工程與設(shè)計(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）.［朱曉娟.基于擴(kuò)展區(qū)間編碼的XML結(jié)構(gòu)連接算法［J］.計(jì)算機(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）.［楊揚(yáng)，尹柯.一種基于XML前綴編碼的路徑查詢［J］.河南大學(xué)學(xué)報(bào)（自然科學(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］.計(jì)算機(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）.［趙圣猛，趙雷.一種采用擴(kuò)展Dewey編碼非歸并的小枝模式查詢算法［J］.小型微型計(jì)算機(jī)系統(tǒng)，2011，32（5）：837－839.］