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

郭麗紅，王 箭，杜 賀

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

1 概述

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

為 XML文檔樹中的節點分配唯一編號的具體策略稱為XML節點編碼方案。為高效地支持XML數據的查詢，一個高效的編碼方案應能快速高效地判定任意 2個節點間的結構關系，包括父子關系、兄弟關系、祖先后代關系等，而且也能快速定位某一具體節點所在位置。本文側重于XML數據編碼中區間編碼方案的研究，針對目前XML區間編碼方案中的主要問題進行分析，在現有的區間編碼方法的基礎上，提出一種新的高效的編碼方法。

2 相關研究

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

2.1 常見的區間編碼方法

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

(1)Dietz區間編碼

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

(2)起止區間編碼

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

(3)擴展的區域編碼

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

2.2 區間編碼方法舉例

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

圖1 原始XML樹

表1 原始XML樹的區間編碼

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

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

3.1 編碼的構建

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

(1)組合標識RX

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

(2)角度agl

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

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

表2 同心圓切割編碼

圖3 XML文檔樹在同心圓中的分布連接關系

3.2 節點關系判定法則

節點關系的判定法則如下：

(1)父子關系的判定

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

(2)兄弟關系的判定

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

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

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

4 實驗分析與比較

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

表3 XML測試數據集

4.1 編碼空間對比

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

圖4 編碼空間

4.2 編碼時間對比

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

圖5 編碼時間

5 結束語

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

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

[2]孟小峰,王 宇,王小鋒.XML查詢優化研究[J].軟件學報,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.