支持更新的XML編碼方案

楊 揚，申石磊

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

0 引 言

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

1 相關研究

1.1 區間編碼

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

1.2 路徑編碼

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

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

2 IPEU編碼方案

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

圖1為IPEU編碼片斷。

圖1 IPEU編碼片段

定義2 IPEU編碼比較：設結點u的IPEU編碼c（u），結點u的祖先結點a的IPEU編碼c（a），結點u的雙親結點p的IPEU編碼c（p），結點u的孩子結點c的IPEU編碼c（c），結點u的后裔結點d的IPEU編碼c（d），結點u的前驅兄弟結點ps的IPEU編碼c（ps），結點u的后繼兄弟結點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）。

依據定義2中的編碼符號，表1給出了基于IPEU編碼，在進行XPath查詢時，XML結點間結構關系的判定方法。

表1 基于IPEU編碼的XPath查詢

3 IPEU編碼的更新

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

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

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

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

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

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

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

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

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

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

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

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

4 實 驗

4.1 實驗環境

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

圖2 IPEU編碼的更新操作

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

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個測試數據集。實驗中將IPEU編碼與目前普遍使用的Dewey前綴編碼和Zhang區間編碼作比較，這3種編碼方案在對文檔進行編碼時的代價相差不大，如圖3所示。

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

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

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

5 結束語

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

［1］WAN Changxun，LIU Xiping.The XML database technology［M］.2nd ed.Beijing：Tsinghua University Press，2008：106（in Chinese）.［萬常選，劉喜平.XML數據庫技術 ［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］.計算機應用，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）.［劉先鋒，朱清華，陳鳳英.支持數據更新的XML編碼方案研究 ［J］.計算機工程與應用，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］.計算機工程與設計，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）.［徐娟，李戰懷，婁穎.基于節點位置信息的降低更新代價前綴編碼方案研究 ［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）.［文思，文貴華.基于擴展前綴編碼的左孩子右兄弟結構連接算法 ［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）.［周軍鋒，魏蕊，郭景峰.面向更新的擴展Dewey編碼 ［J］.計算機科學與探索，2010，4 （10）：918－926.］