支持更新的XML編碼方案

楊 揚(yáng)，申石磊

（河南大學(xué) 計(jì)算中心，河南 開封475004）

0 引 言

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

1 相關(guān)研究

1.1 區(qū)間編碼

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

1.2 路徑編碼

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

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

2 IPEU編碼方案

定義1 IPEU編碼：本質(zhì)上是一種擴(kuò)展的Dewey編碼，由字母、整數(shù)、點(diǎn) （.）組成，XML文檔樹的層次用L表示，令c（u）為結(jié)點(diǎn)u的IPEU編碼，對(duì)于結(jié)點(diǎn)u的孩子結(jié)點(diǎn)v的IPEU編碼c（v）＝c（u）Nv，其中Nv代表了結(jié)點(diǎn)v在結(jié)點(diǎn)u的所有孩子結(jié)點(diǎn)中的從左到右的位置關(guān)系。原Dewey編碼中各層的 “.”分隔符取消，表示各層的分隔僅用數(shù)字標(biāo)識(shí)。若Nv小于10，Nv仍以數(shù)字表示；若Nv大于10，除個(gè)位數(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é)點(diǎn)u的IPEU編碼c（u），結(jié)點(diǎn)u的祖先結(jié)點(diǎn)a的IPEU編碼c（a），結(jié)點(diǎn)u的雙親結(jié)點(diǎn)p的IPEU編碼c（p），結(jié)點(diǎn)u的孩子結(jié)點(diǎn)c的IPEU編碼c（c），結(jié)點(diǎn)u的后裔結(jié)點(diǎn)d的IPEU編碼c（d），結(jié)點(diǎn)u的前驅(qū)兄弟結(jié)點(diǎn)ps的IPEU編碼c（ps），結(jié)點(diǎn)u的后繼兄弟結(jié)點(diǎn)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中的編碼符號(hào)，表1給出了基于IPEU編碼，在進(jìn)行XPath查詢時(shí)，XML結(jié)點(diǎn)間結(jié)構(gòu)關(guān)系的判定方法。

表1 基于IPEU編碼的XPath查詢

3 IPEU編碼的更新

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

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

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

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

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

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

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

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

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

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

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

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

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

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

本文實(shí)驗(yà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í)驗(yàn)所用數(shù)據(jù)集為XMark，其中原始XMark數(shù)據(jù)集為115MB，包含1 666 315元素，最大扇出為25 500，平均扇出為3242，最大深度12，平均深度6。實(shí)驗(yàn)中采用不同的生成因子生成不同大小的XMark數(shù)據(jù)集，對(duì)IPEU編碼的編碼時(shí)間、插入結(jié)點(diǎn)進(jìn)行性能分析。

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

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

圖3 不同編碼方案所用編碼時(shí)間比較

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

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

5 結(jié)束語

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

［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版.北京：清華大學(xué)出版社，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］.計(jì)算機(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）. ［楊揚(yáng)，尹柯.一種基于XML前綴編碼的路徑查詢 ［J］.河南大學(xué)學(xué)報(bào) （自然科學(xué)版），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）.［劉先鋒，朱清華，陳鳳英.支持?jǐn)?shù)據(jù)更新的XML編碼方案研究 ［J］.計(jì)算機(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）.［覃遵躍，湯庸，徐洪智.基于擴(kuò)展Dewey編碼的XML文檔更新計(jì)算 ［J］.計(jì)算機(jī)工程與設(shè)計(jì)，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é)點(diǎn)位置信息的降低更新代價(jià)前綴編碼方案研究 ［J］.計(jì)算機(jī)科學(xué)，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）.［文思，文貴華.基于擴(kuò)展前綴編碼的左孩子右兄弟結(jié)構(gòu)連接算法 ［J］.計(jì)算機(jī)工程與設(shè)計(jì)，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）.［周軍鋒，魏蕊，郭景峰.面向更新的擴(kuò)展Dewey編碼 ［J］.計(jì)算機(jī)科學(xué)與探索，2010，4 （10）：918－926.］