楊 揚，申石磊

（河南大學 計算中心，河南 開封475004）

0 引 言

XML作為互聯(lián)網(wǎng)上一種功能強大的標記語言，已經(jīng)成為數(shù)據(jù)表示和交換的一個主要標準，受到越來越多的業(yè)內(nèi)人士的關(guān)注，如何高效的索引和查詢XML數(shù)據(jù)是目前XML研究領(lǐng)域的重要課題。為了加速結(jié)構(gòu)連接，提高查詢和文檔更新維護的效率，目前主流方法是通過對XML文檔樹編碼，依靠編碼快速判斷結(jié)點間的結(jié)構(gòu)關(guān)系。研究人員提出了很多編碼方案來加速結(jié)構(gòu)連接，但是大多沒有考慮編碼更新問題。當XML文檔更新時，更多的編碼方法不能很好地支持更新操作。當XML數(shù)據(jù)頻繁地發(fā)生刪除、插入等更新XML數(shù)據(jù)時，需要調(diào)整相應(yīng)結(jié)點的編碼，以維持結(jié)點間的結(jié)構(gòu)關(guān)系。但重新建立索引或重新編碼的代價是非常高的，有時甚至需要給整棵樹重新編碼。若采用預(yù)留空間的編碼方案，在一定程度上解決了動態(tài)更新問題，但當插入結(jié)點過多，超出預(yù)留空間時，仍然需要重新遍歷XML文檔樹，造成二次編碼。因此，本文提出了一種新的支持XML數(shù)據(jù)更新的編碼方案IPEU （improved prefix encoding of supporting updates），該編碼方案可快速判斷結(jié)點間的結(jié)構(gòu)關(guān)系，當XML文檔樹中插入或刪除結(jié)點時，已有結(jié)點不存在二次編碼問題，降低了更新代價，查詢性能得以提高。

1 相關(guān)研究

1.1 區(qū)間編碼

區(qū)間編碼是樹T中的每一個結(jié)點被賦予一個編碼區(qū)間［start，end］，并且滿足：一個結(jié)點的區(qū)間編碼包含它的后裔結(jié)點的區(qū)間編碼［1］。區(qū)間編碼能有效地支持XML查詢，但它不能適應(yīng)XML文檔動態(tài)更新，當在XML文檔中插入和刪除結(jié)點時，有時甚至會導致整個文檔樹的重新編碼。ZHANG編碼將對結(jié)點先序遍歷時兩次訪問生成的序號作為編碼，這種采用全局標識的編碼更新缺乏靈活性，一個或多個結(jié)點的插入或刪除操作，會引起多個甚至所有結(jié)點的二次編碼。為保證能夠XML文檔更新，Li－Moon編碼的order序號采用非連續(xù)的取值，預(yù)留了一定的空間，Li－Moon編碼與Dietz編碼相比，能夠更好地支持文檔的修改，但當插入的結(jié)點過多超出了預(yù)留空間時，就需要重新編碼。

1.2 路徑編碼

路徑編碼保存了元素的路徑信息，每個結(jié)點編碼都繼承其父結(jié)點的編碼，作為其編碼的前綴。文獻 ［2］提出了一種適用于順序XML文檔樹的前綴編碼方案。這種編碼方案支持順序XML文檔的XPath查詢，并且編碼具有動態(tài)性，可以適應(yīng)XML文檔的插入、刪除操作，但是編碼過長卻是需要改進的。采用二進制表示的SP編碼，編碼長度過長，且在執(zhí)行插入或刪除操作后有大量的結(jié)點需要二次編碼。同樣采用二進制標記的ORDPATH編碼機制類似于Dewey編碼，引入了局部標識，支持XML文檔更新，不需要對結(jié)點重新編碼，但是預(yù)留的空間，造成了浪費，使得編碼規(guī)模很大。

因此，基于以上問題的考慮，本文提出一種支持XML數(shù)據(jù)更新的IPEU編碼方案，并且該編碼是對文獻 ［3］中IPE編碼的改進，彌補了不支持編碼更新的不足。IPEU編碼支持XPath查詢軸的計算，可表示祖先／后裔、雙親／孩子、之前、之后等關(guān)系，當執(zhí)行插入或刪除操作時，XML文檔樹中已有結(jié)點的編碼不需改變，實現(xiàn)了結(jié)點編碼動態(tài)更新，從而提高了更新和查詢效率。

2 IPEU編碼方案

定義1 IPEU編碼：本質(zhì)上是一種擴展的Dewey編碼，由字母、整數(shù)、點 （.）組成，XML文檔樹的層次用L表示，令c（u）為結(jié)點u的IPEU編碼，對于結(jié)點u的孩子結(jié)點v的IPEU編碼c（v）＝c（u）Nv，其中Nv代表了結(jié)點v在結(jié)點u的所有孩子結(jié)點中的從左到右的位置關(guān)系。原Dewey編碼中各層的 “.”分隔符取消，表示各層的分隔僅用數(shù)字標識。若Nv小于10，Nv仍以數(shù)字表示；若Nv大于10，除個位數(shù)字不變，其余位均做轉(zhuǎn)換，其中，1轉(zhuǎn)換為A，2轉(zhuǎn)換為B，依次轉(zhuǎn)換，直至9轉(zhuǎn)為I。

圖1為IPEU編碼片斷。

圖1 IPEU編碼片段

定義2 IPEU編碼比較：設(shè)結(jié)點u的IPEU編碼c（u），結(jié)點u的祖先結(jié)點a的IPEU編碼c（a），結(jié)點u的雙親結(jié)點p的IPEU編碼c（p），結(jié)點u的孩子結(jié)點c的IPEU編碼c（c），結(jié)點u的后裔結(jié)點d的IPEU編碼c（d），結(jié)點u的前驅(qū)兄弟結(jié)點ps的IPEU編碼c（ps），結(jié)點u的后繼兄弟結(jié)點fs的IPEU編碼c（fs），則c（a）＜c（u），c （p）＜c （u）＜c （c），c （ps）＜c （u）＜c （fs），c （ps）＜c （d）＜c（fs）。

依據(jù)定義2中的編碼符號，表1給出了基于IPEU編碼，在進行XPath查詢時，XML結(jié)點間結(jié)構(gòu)關(guān)系的判定方法。

表1 基于IPEU編碼的XPath查詢

3 IPEU編碼的更新

IPEU編碼支持4種插入操作：①在兩個相鄰位置的兄弟結(jié)點之間插入新結(jié)點；②在結(jié)點的最左孩子結(jié)點之前插入新結(jié)點；③在結(jié)點的最右孩子結(jié)點之后插入新結(jié)點；④為葉子結(jié)點的孩子插入新結(jié)點。如圖2所示，圖中實線表示已有結(jié)點，虛線表示插入情況。插入多個結(jié)點的操作，可分解為以上4種插入操作通過多次插入來完成。以下4種插入操作IPEU編碼規(guī)則如下：

（1）在兩個相鄰位置的兄弟結(jié)點u和v之間插入新結(jié)點t，Nu與Nv是兩個相鄰的整數(shù)，結(jié)點t在兩兄弟結(jié)點u和v之間的位置關(guān)系Nt前加符號 “.”加以標識，結(jié)點t的IPEU編碼c（t）＝c（u）.Nt，Nt取值從整數(shù)1開始。若結(jié)點t與v之間再插入新結(jié)點m，則結(jié)點m的IPEU編碼c（m）＝c（t）.Nm，Nm－Nt＝1，即Nt與Nm以1為步長遞增。

例如：圖2（a）中兩個位置連續(xù)的兄弟結(jié)點b1與b2之間插入結(jié)點b3，c（b1）＝2C11，c（b2）＝2C12，那么c（b3）＝2C11.1。b3與b2之間再插入結(jié)點b4，c（b4）＝2C11.2。

特例，若結(jié)點u與插入的結(jié)點t之間，再插入結(jié)點p，在反映結(jié)點p在u和t之間的位置關(guān)系Np前加符號 “.”標識，結(jié)點p的IPEU編碼c（p）＝c（u）.Np，Np取值從0開始。若結(jié)點u與p之間再插入新結(jié)點q，則結(jié)點q的IPEU編碼c（q）＝c （t）.Nq，Nq－Np＝－1，Nq與 Np以－1為步長遞減。

例如：如圖2（a）所示，兩個位置連續(xù)的兄弟結(jié)點b1與b2之間已插入結(jié)點b3，若在b1與b3之間再插入結(jié)點b5，c（b1）＝2C11，c （b2）＝2C12，c （b3）＝2C11.1，那么c（b5）＝2C11.0。b1與b5之間再插入結(jié)點b6，c（b6）＝2C11.－1。

（2）在結(jié)點u的最左孩子結(jié)點v之前插入新結(jié)點p，結(jié)點u的IPEU編碼c（u），結(jié)點v的IPEU編碼c（v）＝c（u）Nv，結(jié)點v是結(jié)點u的最左孩子，Nv＝1，新結(jié)點p插入已有結(jié)點v之前，p即為u最左孩子結(jié)點，c（p）＝c（u）Np，Np＝Nv－1＝0，Np取值以－1為公差遞減。

例如：在圖2（b）中，在結(jié)點a的最左孩子結(jié)點b1之前插入結(jié)點b7，c（a）＝2C1，c（b1）＝2C11，Nb1＝1，c（b7）＝2C10，Nb7＝1－1＝0。若在已成為最左結(jié)點的b7之前再插入新結(jié)點b8，則c（b8）＝2C1－1，Nb8＝0－1＝－1。

（3）在結(jié)點u的最右孩子w結(jié)點之后插入新結(jié)點q，結(jié)點u的IPEU編碼c（u），結(jié)點w的IPEU編碼c（w）＝c（u）Nw，結(jié)點w是結(jié)點u的最右孩子，新結(jié)點q插入u之后，q變成u最右孩子結(jié)點，c（q）＝c（u）Nq，Nq＝Nw＋1，Nq取值以1為公差遞增。

例如：在結(jié)點a的最右孩子結(jié)點b2之后插入結(jié)點b9，c（a）＝2C1，c（b2）＝2C12，Nb2＝2，c（b9）＝2C13，Nb7＝2＋1＝3。結(jié)點b9之后若再插入新結(jié)點b10，則c（b10）＝2C14，Nb10＝3＋1＝4。如圖2 （b）所示。

（4）作為葉子結(jié)點u的孩子插入新結(jié)點v，結(jié)點u的IPEU編碼c（u），結(jié)點v的IPEU編碼為其雙親結(jié)點u的編碼連接上結(jié)點v在其雙親結(jié)點孩子中的位次Nv，Nv取值從1開始以1為公差遞增，則c（v）＝c（u）Nv。

例如：圖2（c）中已插入存在的結(jié)點b8，c（b8）＝2C11－1，為b8添加孩子結(jié)點c1，c （c1）＝2C11－11。為已插入存在的結(jié)點b3先后添加孩子結(jié)點c2和c3，c（b3）＝2C11.1，則c （c2）＝2C11.11，c （c3）＝2C11.12。

其他更新操作，如刪除和修改，無需改動已有的IPEU編碼，這里不再贅述。

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。

圖2 IPEU編碼的更新操作

實驗所用數(shù)據(jù)集為XMark，其中原始XMark數(shù)據(jù)集為115MB，包含1 666 315元素，最大扇出為25 500，平均扇出為3242，最大深度12，平均深度6。實驗中采用不同的生成因子生成不同大小的XMark數(shù)據(jù)集，對IPEU編碼的編碼時間、插入結(jié)點進行性能分析。

4.2 實驗分析

（1）初始編碼所用時間：采用生成因子為0.01、0.1、0.2、0.3、0.4 和 0.5 分 別 生 成 1.12MB、11.3MB，22.8MB、34MB、45.3MB和56.2MB這5個測試數(shù)據(jù)集。實驗中將IPEU編碼與目前普遍使用的Dewey前綴編碼和Zhang區(qū)間編碼作比較，這3種編碼方案在對文檔進行編碼時的代價相差不大，如圖3所示。

圖3 不同編碼方案所用編碼時間比較

（2）編碼更新所用時間：以生成因子為0.5生成的56.2MB的XMark數(shù)據(jù)集為例， （單位：千結(jié)點，1、3、5、8、10）進行了插入結(jié)點測試。Dewey前綴編碼和Zhang編碼不能很好地支持編碼更新。當XML文檔樹中插入結(jié)點時，作為更新代價，為保持編碼的連續(xù)性，Dewey編碼將插入點之后的結(jié)點重新編碼。而Zhang編碼采用全局標識作為編碼，這種編碼查詢效率較高，但XML文檔更新時效率低，一旦插入或刪除新的結(jié)點，整個XML文檔樹的所有結(jié)點均需要二次編碼。而當插入新結(jié)點時，IPEU編碼不需要重新編碼，IPEU編碼在更新數(shù)據(jù)操作時明顯優(yōu)于Zhang編碼和Dewey前綴編碼。測試結(jié)果如圖4所示。實驗證明，IPEU編碼方案在對需要頻繁進行更新的XML文檔是非常有效的。

圖4 不同編碼方案更新操作所用時間比較

5 結(jié)束語

XML文檔使用過程中，不可避免地會有修改，當增減數(shù)據(jù)元素時，若每次都得調(diào)整插入或刪除結(jié)點后的結(jié)點編碼，以維系在進行XPath查詢時結(jié)點間的結(jié)構(gòu)關(guān)系判定，這樣勢必會影響查詢效率。為避免XML文檔樹中結(jié)點的二次編碼，減少更新代價，本文提出了一種支持XML數(shù)據(jù)更新的IPEU編碼方案，它支持祖先／后裔和兄弟等多種結(jié)構(gòu)關(guān)系的判定，且編碼不需要預(yù)留編碼空間，這樣就不必考慮當插入結(jié)點或子樹時，編碼預(yù)留空間不足時 “溢出”問題以及二次編碼效率，不必改變已有編碼，可以有效地解決更新操作所造成的結(jié)點重新編碼的問題，是一種較好的前綴編碼。

［1］WAN Changxun，LIU Xiping.The XML database technology［M］.2nd ed.Beijing：Tsinghua University Press，2008：106（in Chinese）.［萬常選，劉喜平.XML數(shù)據(jù)庫技術(shù) ［M］.2版.北京：清華大學出版社，2008：106.］

［2］ZHANG Jianmei，TAO Shiqun.Prefix encoding scheme for ordered XML trees ［J］.Computer Applications，2005，25（12）：2879－2881 （in Chinese）. ［張劍妹，陶世群.一種適用于順序XML樹的前綴編碼方法 ［J］.計算機應(yīng)用，2005，25（12）：2879－2881.］

［3］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.］

［4］LI C Q，LING T W，HU M.Efficient processing of updates in dynamic XML data［C］.Proceedings of the 22nd International Conference on Data Engineering.Washington，DC：IEEE Computer Society，2006：13－22.

［5］Harder T，Haustein M P，Mathis C，et al.Node labeling schemes for dynamic XML documents reconsidered［J］.Data and Knowledge Engineering，2007，60 （1）：126－149.

［6］LIU Zhenhua，Muralidhar Krishnaprasad.Effective and efficient update of XML in RDBMS ［C］.SIGMOD Conference，2007：925－936.

［7］LIU Xianfeng，ZHU Qinghua，CHEN Fengying.Research coding scheme of supporting for updating XML data ［J］.Computer Engineering and Applications，2008，44 （33）：151－154 （in Chinese）.［劉先鋒，朱清華，陳鳳英.支持數(shù)據(jù)更新的XML編碼方案研究 ［J］.計算機工程與應(yīng)用，2008，44 （33）：151－154.］

［8］MIN Junki，LEE Jihyun，CHUNG Chinwan.An efficient XML encoding and labeling method for query processing and updating on dynamic XML data［J］.Journal of Systems and Software，2009，82 （3）：503－515.

［9］KO Hye Kyeong，LEE Sang Keun.A binary string approach for updates in dynamic ordered XML data［J］.IEEE Transactions on Knowledge and Data Engineering，2008，99 （1）：602－607.

［10］WANG Chenying，YUAN Xiaojie，WANG Xin，et al.An efficient numbering scheme for dynamic XML trees ［C］.Wuhan：Proc of International Conference on Computer Science and Software Engineering，2008：704－707.

［11］LI C Q，LING T W，HU M.Efficient updates in dynamic XML data：From binary string to quaternary string ［J］.The VLDB Journal，2008，17 （3）：573－601.

［12］Fegaras，Leonidas.Efficient processing of XML update streams ［C］.Cancun，Mexico：24th IEEE International Conference on Data Engineering，2008：616－625.

［13］QIN Zunyue，TANG Yong，XU Hongzhi.Updating computing for XML document based on extended Dewey coding ［J］.Computer Engineering and Design，2009，30 （10）：2583－2589 （in Chinese）.［覃遵躍，湯庸，徐洪智.基于擴展Dewey編碼的XML文檔更新計算 ［J］.計算機工程與設(shè)計，2009，30 （10）：2583－2589.］

［14］XU Juan，LI Zhanhuai，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］.計算機科學，2009，36 （2）：167－171.］

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

［16］WEN Si，WEN Guihua.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.］

［17］ZHOU Junfeng，WEI Rui，GUO Jingfeng.Update－oriented extending Dewey labeling scheme［J］.Journal of Frontiers of Computer Science ＆ Technology，2010，4 （10）：918－926 （in Chinese）.［周軍鋒，魏蕊，郭景峰.面向更新的擴展Dewey編碼 ［J］.計算機科學與探索，2010，4 （10）：918－926.］