一種基于同心圓切割的XML編碼方案

郭麗紅，王 箭，杜 賀

(1.南京航空航天大學(xué)計算機(jī)科學(xué)與技術(shù)學(xué)院，南京 210016；2.南京工程學(xué)院通信工程學(xué)院，南京 211167)

1 概述

隨著(eXtensible Markup Language,XML)文檔被廣泛應(yīng)用，Internet上出現(xiàn)了大量用可擴(kuò)展標(biāo)記語言XML文檔來描述的信息，如何有效地管理和查詢這些網(wǎng)上海量的XML信息，已經(jīng)成為學(xué)者們近年來研究的課題[1-2]。在 XML眾多研究問題中，XML文檔節(jié)點編碼在XML研究中有著基礎(chǔ)性的重要作用。

為 XML文檔樹中的節(jié)點分配唯一編號的具體策略稱為XML節(jié)點編碼方案。為高效地支持XML數(shù)據(jù)的查詢，一個高效的編碼方案應(yīng)能快速高效地判定任意 2個節(jié)點間的結(jié)構(gòu)關(guān)系，包括父子關(guān)系、兄弟關(guān)系、祖先后代關(guān)系等，而且也能快速定位某一具體節(jié)點所在位置。本文側(cè)重于XML數(shù)據(jù)編碼中區(qū)間編碼方案的研究，針對目前XML區(qū)間編碼方案中的主要問題進(jìn)行分析，在現(xiàn)有的區(qū)間編碼方法的基礎(chǔ)上，提出一種新的高效的編碼方法。

2 相關(guān)研究

目前，對XML文檔樹的編碼已有很多研究，如位向量編碼[3]、前綴編碼[4]、區(qū)間編碼[5]、素數(shù)編碼等[6]。本文主要針對幾種常見的區(qū)間編碼方法進(jìn)行研究與分析，為新編碼方案的提出打下基礎(chǔ)。

2.1 常見的區(qū)間編碼方法

區(qū)域編碼方法是為每個節(jié)點分配一對隱含該節(jié)點包含區(qū)域的數(shù)字。給定任意2個區(qū)域z1和z2，如果稱z1包含z2，則z1節(jié)點是z2節(jié)點的祖先。目前常見的區(qū)域編碼分為基本區(qū)域編碼和擴(kuò)展區(qū)域編碼。為描述方便，本文以下部分用L(u)表示節(jié)點u的編碼。

(1)Dietz區(qū)間編碼

Dietz區(qū)間編碼[7]的編碼規(guī)則是樹T的每一個節(jié)點都被賦予一個含有先序遍歷序號和后序遍歷序號的二元組節(jié)點，可以表示為(preorder,postorder)。前序遍歷XML樹時節(jié)點對應(yīng)的前序遍歷值用preorder表示，后序遍歷XML樹時節(jié)點對應(yīng)的后序遍歷值用postorder表示。

(2)起止區(qū)間編碼

節(jié)點的起止區(qū)間編碼[8]可以用一個三元組來表示：(start,end,level)。該節(jié)點在文檔結(jié)構(gòu)樹中的起始位置用start表示，結(jié)束位置用end表示，節(jié)點所處的層次用level表示，start和end可以看作是深度優(yōu)先遍歷該節(jié)點所在的XML樹，進(jìn)入該節(jié)點用start表示，離開該節(jié)點用end表示，每次訪問一個節(jié)點時，依次分配一個整數(shù)。

(3)擴(kuò)展的區(qū)域編碼

節(jié)點的擴(kuò)展區(qū)域編碼[9]是一個三元組，可以表示為(order,size,level)，order和size分別表示該節(jié)點的前序遍歷順序和該節(jié)點的大小，level表示節(jié)點所處的層次。用該方法對節(jié)點進(jìn)行編碼的時候可使 size適當(dāng)大于該節(jié)點的實際大小，這樣可以為插入新節(jié)點預(yù)留空間，減少更新的代價。

2.2 區(qū)間編碼方法舉例

圖1是一棵具體的XML文檔樹，對于樹的層數(shù)的定義，這里規(guī)定，樹根所在的層數(shù)為0，它的孩子節(jié)點所在層數(shù)1，依次向下遞增。具體的相對于這棵XML樹的Dietz區(qū)間編碼、起止區(qū)間編碼和擴(kuò)展區(qū)間編碼的信息如表1所示。

圖1 原始XML樹

表1 原始XML樹的區(qū)間編碼

3 基于同心圓切割的XML編碼

XML文檔是由樹型結(jié)構(gòu)來表示的，對n層樹，如果把樹根看作成圓心，樹的每一層節(jié)點各自分布不同半徑的多個同心圓上，那么這棵倒置的樹更像一個以根節(jié)點為圓心由多個半徑不同的同心圓組成的一個同心圓集合，而這些分布在若干個同心圓上的節(jié)點，像是在這些同心圓上進(jìn)行區(qū)域分割，基于該設(shè)想，本文提出一種同心圓切割的XML編碼方案。

3.1 編碼的構(gòu)建

基于上述同心圓切割的理論，把XML樹中每個節(jié)點編碼成兩部分組成(RX,agl)。

(1)組合標(biāo)識RX

R代表節(jié)點所在的同心圓集合中所在圓的半徑，也代表該節(jié)點在樹中所處的層數(shù)，從樹根開始層數(shù)逐漸上升，其中根節(jié)點所在半徑為0，其兒子節(jié)點所在半徑為1，依次以1為步長遞增。X代表組標(biāo)識，規(guī)定兄弟節(jié)點分在同一組內(nèi)，具有相同的組標(biāo)識。這里組標(biāo)識選用字母來標(biāo)識，依次可以為 a,b,c,…,z,aa,ab,…,az,ba,bb,bc,…,ca,…。

(2)角度agl

由于采用同心圓平均切割理論，任意節(jié)點的孩子節(jié)點是平分該節(jié)點所占有區(qū)域的，因此每個節(jié)點都占據(jù)圓中的一個區(qū)域，這里選用起始角度 agl代表該節(jié)點。針對圖 1原始XML樹的同心圓切割編碼如圖2所示，其中，A為根節(jié)點即圓心節(jié)點，編碼為(0,0)，A的3個孩子節(jié)點，屬于同一組，組編碼采用字母編碼，因此，其組編碼為a，三節(jié)點平分半徑為1的圓，其中第1個孩子從0°開始(水平方向)，每個節(jié)點占據(jù) 360°/3=120°的區(qū)域，B 占據(jù)[0,120°)，C 占據(jù)[120°,240°)，D 占據(jù)[240°,360°)的半開半閉區(qū)間。節(jié)點編碼以起始角度為準(zhǔn)，因此，B的編碼為(1a,0)，C的編碼為(1a,120°)。同理，對于C的孩子節(jié)點E、F、G，這3個節(jié)點安置于C的[120°,240°)范圍內(nèi)，但其位于半徑為2的圓內(nèi)，每點主要占據(jù)40((240°,120°)/3)的區(qū)域，因此，E的編碼為(2a,120°)，F(xiàn) 的編碼為(2a,160°)，G 編碼為(2a,200°)，依次繼續(xù)編碼，圖2的具體編碼如表2所示。XML文檔樹的分布連接關(guān)系如圖3所示。

圖2 同心圓切割編碼后節(jié)點分布位置

表2 同心圓切割編碼

圖3 XML文檔樹在同心圓中的分布連接關(guān)系

3.2 節(jié)點關(guān)系判定法則

節(jié)點關(guān)系的判定法則如下：

(1)父子關(guān)系的判定

對于節(jié)點u和v，如果節(jié)點u存在右兄弟節(jié)點u’，當(dāng)且僅當(dāng) L(u).agl

(2)兄弟關(guān)系的判定

對于節(jié)點u和v，當(dāng)且僅當(dāng)L(v).RX=L(u).RX，u和v是兄弟節(jié)點。

(3)祖先后代關(guān)系的判定

對于節(jié)點u和v，如果節(jié)點u存在右兄弟節(jié)點u’，當(dāng)且僅當(dāng) L(u).agl

4 實驗分析與比較

為測試新編碼方案的時空效率，本文主要比較Dietz區(qū)間編碼、起止區(qū)間編碼(Start End，簡稱StartE)和本文的同心圓切割的編碼方案(Concentric Circular Cutting，簡稱3C)。本文實驗是在處理器為Intel Pentium 43.02 GHz，內(nèi)存為1 GB，操作系統(tǒng)為Windows XP環(huán)境下采用Visual C++6.0，基于 DOM 技術(shù)編程實現(xiàn)的。實驗所采用的測試文檔由 XML自動生成工具 XMark[10]生成，文檔樹的最大深度和平均深度等信息如表3所示。

表3 XML測試數(shù)據(jù)集

4.1 編碼空間對比

從圖4中數(shù)據(jù)和表1信息可以看出，Dietz方案在文檔的節(jié)點數(shù)比較少時，所占據(jù)的存儲空間比較小，而隨著文檔節(jié)點數(shù)的增加，編碼空間越來越大，這是因為節(jié)點數(shù)小于65535時，每個節(jié)點占用4 Byte空間，而超過65535，則需要8 Byte編碼；StartE編碼方法在節(jié)點數(shù)小于32767時，每個節(jié)點占用5 Byte空間，而超過32767，則需要9 Byte編碼；3C編碼與節(jié)點的分布及其扇出度相關(guān)，在多數(shù)情況下每個節(jié)點占用 6 Byte空間，具體信息如圖 4所示。

圖4 編碼空間

4.2 編碼時間對比

圖5是上述3種方案在編碼時間上的對比，從測試數(shù)據(jù)可以看出，Dietz區(qū)間編碼時需要2次遍歷XML文檔，很明顯地，這2種方法在編碼時間上比較耗時，StartE方法除了遍歷上費(fèi)時之外，時間主要耗費(fèi)在第 2次訪問編碼節(jié)點時的判斷上，但是整體編碼時間略低于Dietz方法；而 3C方法整體遍歷一次，標(biāo)識簡單，因此，編碼時間最小。

圖5 編碼時間

5 結(jié)束語

本文對目前典型的區(qū)間編碼方法進(jìn)行分析，提出一種基于同心圓切割的節(jié)點編碼方案。該方案在文檔較大、節(jié)點個數(shù)比較多的情況下，可改善查詢效率和編碼時空效率，為XML其他處理做基礎(chǔ)性的準(zhǔn)備，因此，該方案對于較大文檔的查詢有一定的使用及借鑒價值，此外，把XML樹中節(jié)點布局到同心圓中，可以利用數(shù)學(xué)的理論和方法來求各節(jié)點之間的關(guān)系，包括對節(jié)點的具體定位、求某節(jié)點的子孫后代等，這是下一步的研究方向。

[1]荊旦建.基于XML的數(shù)據(jù)管理技術(shù)的研究[D].南京: 南京理工大學(xué),2009.

[2]孟小峰,王 宇,王小鋒.XML查詢優(yōu)化研究[J].軟件學(xué)報,2006,17(10): 2069-2086.

[3]Mohammad S,Martin P.LLS: Level-based Labeling Scheme for XML Databases[C]//Proceedings of 2010 Conference of the Center for Advanced Studies on Collaborative Research.New York,USA: [s.n.],2010.

[4]An D,Park S.Efficient Access Control Labeling Scheme for Secure XML Query Processing[J].Computer Standards &Interfaces,2011,33(5): 439-447.

[5]Niu Na,Dong Guoqing.A New Labeling Scheme for XML Trees Based on Mesh Partition[C]//Proceedings of the 2nd International Conference on Future Computer and Communication.New York,USA: [s.n.],2010.

[6]Lu Jiaheng,Meng Xiaofeng,Tok W L.Indexing and Query XML Using Extended Dewey Labeling Scheme[J].Data &Knowledge Engineering,2011,70(1): 35-59.

[7]Dietz P F.Maintaining Order in a Linked List[C]//Proceedings of the 14th Annual ACM Symposium on Theory of Computing.San Francisco,USA: ACM Press,1982.

[8]Zhang Chun,Naughton J F,DeWitt D J,et al.On Supporting Containment Queries in Relational Database Management Systems[C]//Proceedings of the 27th ACM SIGMOD.Santa Barbara,USA: ACM Press,2001.

[9]Yun J H,Chung C W.Dynamic Interval-based Labeling Scheme for Efficient XML Query and Update Processing[J].Journal of Systems and Software,2008,81(1): 56-70.

[10]Schmidt A R.XMark——An XML Benchmark Project[EB/OL].[2012-06-03].http://monetdb.cwi.nl/xml/index.html.