基于分數(shù)的動態(tài)前綴XML 編碼方案

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

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

0 引言

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

1 相關(guān)工作

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

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

2 DPEF 編碼

定義1數(shù)符對應(yīng)表NCCT(Numeric－Character Corresponding Table).設(shè)有數(shù)字集合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 與之一一對應(yīng).對應(yīng)規(guī)則函數(shù)f={＜0，A＞，＜1，B＞，＜2，C＞，＜3，D＞，＜4，E＞，＜5，F(xiàn)＞，＜6，G＞，＜7，H＞，＜8，I＞，＜9，J＞}.

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

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

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

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

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

(1)在兩相鄰節(jié)點u1 和u2 之間插入.設(shè)u1 的節(jié)點編碼為p(u).a，u2 的節(jié)點編碼為p(u).b(p(u)為u1 和u2 的父節(jié)點編碼)，則新插入節(jié)點的編碼為p(u).((a+b)/2).如圖1(a)中，在原有節(jié)點u1 和u2 之間依次插入新節(jié)點u3、u4 和u5，則u3的編碼為1.2.1.((1+2)/2)，根據(jù)定義2 的分數(shù)編碼表示法定義，最終編碼可表示為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)在最左節(jié)點u1 左邊插入.設(shè)u1 的節(jié)點編碼為p(u).a，則新插入節(jié)點的編碼為p(u).a/2).如圖1(b)中，在節(jié)點u1的左邊依次插入u2 和u3，則u2 的編碼為1.2.1.1/2)，根據(jù)定義2 的表示方法，最終可表示為1.2.1.B2，同樣的，u3 的編碼為1.2.1.(1/2)/2)，最左編碼為1.2.1.B4.

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

3 相關(guān)算法

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

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

4 實驗及性能分析

4.1 實驗環(huán)境

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

表1 測試數(shù)據(jù)集

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

4.2 實驗結(jié)果分析

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

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

圖3 三種編碼的靜態(tài)編碼時間比較

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

圖4 三種編碼的動態(tài)編碼時間比較

5 結(jié)束語

本文在分析現(xiàn)有區(qū)間編碼和前綴編碼的基礎(chǔ)上，提出一種基于分數(shù)的動態(tài)前綴編碼DPEF，該編碼方案保留了Dewey 編碼的特性，編碼簡單易用，支持節(jié)點間的位置關(guān)系判定操作，且在不預(yù)留空間的前提下實現(xiàn)了對編碼的動態(tài)更新.實驗結(jié)果表明，DPEF 編碼在空間占用和編碼的時間效率上都表現(xiàn)出了較好的性能.下一步考慮研究在DPEF 編碼的基礎(chǔ)上設(shè)計和實現(xiàn)支持動態(tài)更新的Native XML 數(shù)據(jù)庫的索引結(jié)構(gòu).

［1］胡江明，李建華，杜章華，魏鋒.一種高效的動態(tài)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］汪陳應(yīng)，袁曉潔，王鑫，劉眾奇.BSC:一種高效的動態(tài)XML 樹編碼方案［J］.計算機科學(xué)，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.