基于分數的動態前綴XML 編碼方案

姚保峰，馬程，謝娜，戚曉明，郭有強

(蚌埠學院 計算機科學與技術系，安徽 蚌埠 233000)

0 引言

隨著越來越多的網絡數據采用XML 格式進行表示，XML 已經成為網絡上數據存儲和交換的事實標準，同時也是Web 的基本組成部分和未來技術發展的基礎.如何快速實現XML 文檔的數據查詢是當前XML 相關研究的熱點，而XML 的數據查詢依賴于XML 的文檔樹編碼，因此，對XML 文檔樹的編碼機制進行研究具有重要意義.XML 文檔樹的編碼機制是指對XML 文檔中的每個節點賦予唯一的編碼，以通過這個編碼快速地確定任意兩個節點之間的關系(如父子關系、祖先后裔關系、兄弟關系等)［1］.目前已經提出了一些XML 的編碼方案，但是當對XML 數據進行插入、刪除等更新操作時，現有的編碼方案往往需要大幅調整相應結點的編碼甚至對整棵樹進行重新編碼，造成數據更新的代價很大.本文提出一種基于分數的動態前綴編碼DPEF(Dynamic prefix encoding with fraction).

1 相關工作

目前比較常見的編碼方式有區間編碼［2－3］和前綴編碼［4－5］.區間編碼為XML 文檔樹的每一個節點賦予一個區間編碼［start，end］，并要求滿足:一個節點的區間編碼包含它的后裔節點的區間編碼［6］.文獻［2］和文獻［3］提出的區間編碼方法都能夠有效地支持包含關系和文檔位置關系的計算，且編碼長度小，查詢效率也較高.但是，它們都沒有完全實現編碼的動態更新，在預留空間不足的情況下需要二次編碼，從而產生巨大的時間和空間開銷.前綴編碼將文檔樹中父節點的編碼作為其子節點編碼的前綴.Dewey 編碼［7］是最常用的一種前綴編碼，但是Dewey 編碼本身并不直接支持更新操作.文獻［8］提出的ORDPATH 編碼與Dewey 編碼類似，但采用二進制形式表示編碼，初始編碼都用正奇數表示，插入新節點時以偶數作為占位符結合預留的負數實現了節點的動態更新，但是ORDPATH 編碼插入節點后的位置關系判斷復雜且編碼規模較大.文獻［9］提出的TDE 算法將實數映射為二維元組，利用任意兩個實數間存在無限個實數的特點，避免了更新時的二次編碼，但TDE 編碼的節點長度過大，浪費了存儲空間.

本文在Dewey 編碼的基礎上提出一種基于分數的動態前綴編碼DPEF(Dynamic prefix encoding with fraction)，該編碼保留了Dewey 編碼的良好特性，實現了XML 數據的動態更新.

2 DPEF 編碼

定義1數符對應表NCCT(Numeric－Character Corresponding Table).設有數字集合N={0，1，2，3，4，5，6，7，8，9}，字符集合C={’A’，’B’，’C’，’D’，’E’，’F’，’G’，’H’，’I’，’J’}，對任一n∈N 有唯一的c∈C 與之一一對應.對應規則函數f={＜0，A＞，＜1，B＞，＜2，C＞，＜3，D＞，＜4，E＞，＜5，F＞，＜6，G＞，＜7，H＞，＜8，I＞，＜9，J＞}.

定義2分數編碼FC(Fraction Coding).任何一個分數都可以表示為hy 的形式，其中h={a0a1…an|ai∈C，i，n∈N}，C 是定義1 中的字符集合.即表示分數時將分子x 用定義1 的規則表示為字符形式，分母y 保持不變.如可以表示為BFH13.

定義3靜態DPEF 編碼.靜態DPEF 編碼是指在初始化XML 文檔時為XML 文檔樹中的每個節點賦予一個唯一的編碼，其編碼規則由下列規則確定:

(1)根節點的編碼為1;

(2)在對文檔樹進行寬度優先遍歷的過程中，如果節點v 是節點u 的第i 個子節點，那么，節點v 的DPEF 編碼為c(u).i，其中的c(u)表示節點u 的編碼.

定義4動態DPEF 編碼.動態DPEF 編碼是指在靜態DPEF 編碼的基礎上，使其支持節點的插入、刪除和更新操作.考慮到節點的刪除和更新操作不會影響其他節點編碼，因此這里的動態性主要指插入操作.DPEF 編碼在插入新節點時通過分數表示新節點的編碼，考慮分數在編碼中難以表示，對分數進行了FC 編碼.插入節點主要包含以下3 種情況:

(1)在兩相鄰節點u1 和u2 之間插入.設u1 的節點編碼為p(u).a，u2 的節點編碼為p(u).b(p(u)為u1 和u2 的父節點編碼)，則新插入節點的編碼為p(u).((a+b)/2).如圖1(a)中，在原有節點u1 和u2 之間依次插入新節點u3、u4 和u5，則u3的編碼為1.2.1.((1+2)/2)，根據定義2 的分數編碼表示法定義，最終編碼可表示為1.2.1.D2，采用同樣的方法，u4 的編碼為1.2.1.((3/2+2)/2)，最終編碼表示為1.2.1.H4，u5 的編碼為1.2.1.((3/2+7/4)/2)，最終編碼表示為1.2.1.BD8.

圖1 DPEF 編碼的插入操作

(2)在最左節點u1 左邊插入.設u1 的節點編碼為p(u).a，則新插入節點的編碼為p(u).a/2).如圖1(b)中，在節點u1的左邊依次插入u2 和u3，則u2 的編碼為1.2.1.1/2)，根據定義2 的表示方法，最終可表示為1.2.1.B2，同樣的，u3 的編碼為1.2.1.(1/2)/2)，最左編碼為1.2.1.B4.

(3)在最右節點u1 右邊插入.設u1 的節點編碼為p(u).a，則新插入節點的編碼為p(u).(a+1).如圖1(b)中，在節點u1 的左邊依次插入u4 和u5，則u4 的編碼為1.2.1.2，u5 的編碼為1.2.1.3.

3 相關算法

可以看出，DPEF 編碼在形式上類似于Dewey 碼，因此仍然具有Dewey 碼的良好特性，如算法實現簡單、編碼本身包含節點間的位置關系等.但是由于更新時采用了分數形式表示節點編碼，因此實現了節點的動態更新.下面是插入節點和節點位置關系判定的算法描述.

算法1 中得到左右節點DPEF 編碼的時間復雜度為O(n)，求父節點編碼和插入一個節點的時間復雜度均為O(1)，因而算法1 的時間復雜度為O(n).算法2 中得到節點DPEF 編碼和計算節點所在層的時間復雜度為O(n)，判斷兩節點位置關系需對兩節點的編碼串作模式匹配，采用KMP 算法該過程也可在O(n)時間內完成，因而算法2 的時間復雜度也為O(n).

4 實驗及性能分析

4.1 實驗環境

本實驗硬件環境為:AMD Athlon 7750 雙核2.7GHz 處理器，2G 內存，160G 硬盤，軟件環境為Windows 7 Ultimate 版32 位操作系統，開發平臺為Eclipse 3.6.2，對XML 文檔采用Java DOM4J 包進行解析，并存儲于MySQL 5.5 中.選用的測試數據集情況如表1 所示.

表1 測試數據集

表1 給出了實驗用到的5 個測試數據集.其中數據集D1 是文獻［12］提供的，D2 和D3 是文獻［13］提供的，D4 和D5 由XML 自動生成工具XMARK［14］生成，生成D4 采用的生成因子f 為0.04，生成D5 采用的生成因子f 為0.08.

4.2 實驗結果分析

圖2 顯示了三種編碼方案在編碼的空間占用上的比較情況.由于TDE 編碼采用二維編碼，即每個節點均由若干二維元組組成，而DPEF 編碼和ORDPATH 編碼的每個節點均由若干單值組成，因而在空間占用上TDE 明顯較大，DPEF 編碼和ORDPATH 編碼占用空間相差不大，但ORDPATH 在編碼時空出了偶數，因此當節點較多時產生的編碼最后一位平均值會逐漸大于DPEF 編碼，可以看出，在空間占用方面DPEF 相對較小.

圖2 三種編碼占用存儲空間比較

圖3 三種編碼的靜態編碼時間比較

圖3 是三種編碼的靜態編碼時間比較，DPEF 編碼和ORDPATH 編碼的靜態編碼都和Dewey 碼類似，因此在編碼時間上也基本一致，而TDE 編碼的計算方法較為復雜，因而耗費時間較多.圖4 是分別采用三種編碼方案在五種不同數據集上動態插入1000 個新節點時的平均性能比較情況，由于DPEF 編碼和TDE 編碼的插入操作都需進行一次數值計算才能得到新的編碼，因而它們的更新效率比較接近，而ORDPATH 需要先引入占位符再插入新節點，因而更新效率較差.

圖4 三種編碼的動態編碼時間比較

5 結束語

本文在分析現有區間編碼和前綴編碼的基礎上，提出一種基于分數的動態前綴編碼DPEF，該編碼方案保留了Dewey 編碼的特性，編碼簡單易用，支持節點間的位置關系判定操作，且在不預留空間的前提下實現了對編碼的動態更新.實驗結果表明，DPEF 編碼在空間占用和編碼的時間效率上都表現出了較好的性能.下一步考慮研究在DPEF 編碼的基礎上設計和實現支持動態更新的Native XML 數據庫的索引結構.

［1］胡江明，李建華，杜章華，魏鋒.一種高效的動態XML 文檔樹編碼機制［J］.計算機工程，2010，19(36);75－77.

［2］Li Quanzhong，Moon B.Indexing and Querying XML Data for Regular Path Expressions［C］.Proc.of the 27th International Conference on Very Large Data Bases.Roma.Italy:［S.n.］，2001.36l－370.

［3］Zhang Chun，Naughton J，David D，et a1.On Supporting Contain－ment Queries in Relational Database Management Systems［C］.Proc.of SIGMOD’01.Santa Barbara，California，USA:［S.n.］，2001.425－436.

［4］Cohen E，Kaplan H.Milo Labeling Dynamic XML Trees［C］.Proc.of P0DS’02.Madison Wisconsin，SA:［S.n.］，2002.271－281.

［5］Harder L Haustein M，Mathis C，et a1.Node Labeling Schemes for Dynamic XML Documents Reconsidered［J］.Data＆Knowledge Engineering，2007，60(1):126－149.

［6］Wan Changxuan，Liu Xiping.The XML database technology 2nd ed［M］.Beijing Tsinghua University Press，2008.106 in Chinese.

［7］ITatarinov SD，Viglas K，Beyer J，Shanmugasundaram，E，et al.Storing and querying ordered xml using a relational database system［C］.Proc.of the 2002 ACM SIGMOD.hlt’1 Conf.on Managementof Data(SIGMOD).Madison:ACM Press，2002.204－215.

［8］O’Neil P，O’Neil E，Pal S，Cseri I，et al.ORDPATHs:Insert－Friendly XML node labels.In:Weikum G，K?nig AC，De?loch S，eds［C］.Proc.of the 2004 ACM SIGMOD Int’l Conf.on Management of Data(SIGMOD 2004).Paris:ACM Press，2004.903－908.

［9］覃遵躍，卓月明，徐洪智，張彬連.一種支持XML 文檔更新的編碼方案［J］.計算機工程，2011，37(5):47－49.

［10］汪陳應，袁曉潔，王鑫，劉眾奇.BSC:一種高效的動態XML 樹編碼方案［J］.計算機科學，2008，35(3):76－78.

［11］Ko Hye－Kyeong，Lee Sang－Keun.A Binary String Approach for Updates in Dynamic Ordered XML Data［J］.IEEE Transactions on Knowledge and Data Engeneering，2008，99(1):602－607.

［12］Dong Chan An，Seog Park.Efficient labeling scheme of XML data considering update operations［C］.8th IEEE International Conference on Computer and Information Technology，CIT 2008.Sydney，Australia:NSW，2008.438－443.

［13］NIAGARA Experimental Data［EB/OL］.Available at http://www.cs.wisc.edu/niagara/data.html.

［14］University of Washington XML Repository［EB/OL］.Available at:http:www.cs.washington.edu/research/xmldatasets/.

［15］Xmark－An XML Benchmark Project［EB/OL］.Available at http://monetdb.ewi.nl/xml/downloads.htm1.