王維盛,賈向東

(西北師范大學(xué)計算機科學(xué)與工程學(xué)院,蘭州730070)

左兒子右兄弟鏈式相關(guān)的XML動態(tài)編碼方案

王維盛,賈向東

(西北師范大學(xué)計算機科學(xué)與工程學(xué)院,蘭州730070)

針對可擴展標記語言(XML)數(shù)據(jù)的查詢與更新問題,提出一種基于左兒子右兄弟節(jié)點鏈式關(guān)聯(lián)的XML動態(tài)編碼方案。通過左兒子右兄弟節(jié)點的鏈式相關(guān)信息,僅需在局部做簡單的若干改動,就可實現(xiàn)XML數(shù)據(jù)的更新,并能方便快速地實現(xiàn)祖先后裔關(guān)系、父子關(guān)系和兄弟關(guān)系等各種軸操作。研究結(jié)果表明,該編碼方案不僅能高效地支持結(jié)構(gòu)查詢,而且編碼時間與插入節(jié)點的時間也較少,可快速準確地判斷XML文檔結(jié)構(gòu)樹中任意兩節(jié)點之間的關(guān)系,從而避免更新操作帶來的編碼大量調(diào)整問題,且支持XML文檔的查詢與更新。

可擴展標記語言;文檔樹;編碼方案;軸操作;數(shù)據(jù)查詢;數(shù)據(jù)更新

1 概述

可擴展標記語言(eXtensible Markup Language, XML)是由萬維網(wǎng)聯(lián)盟(World Wide Web Consortium,W3C)推出的新一代網(wǎng)絡(luò)數(shù)據(jù)表示、傳遞和交換的標準,是Internet環(huán)境中跨平臺的、依賴于內(nèi)容的技術(shù)［1-2］。如今越來越多的數(shù)據(jù)采用XML格式存儲,已經(jīng)成為互聯(lián)網(wǎng)上信息表示和信息交換的實際標準,有效地存儲XML數(shù)據(jù)并提供合理高效的XML數(shù)據(jù)編碼,從而實現(xiàn)其數(shù)據(jù)的更新、查詢等操作,成為當今研究的熱點問題。為了有效地管理和利用急劇增長的XML數(shù)據(jù),人們提出了各種針對XML數(shù)據(jù)特征的編碼方法。為XML文檔樹中的每個節(jié)點分配唯一的編碼,可以快速地確定節(jié)點之間的結(jié)構(gòu)關(guān)系,因此,XML文檔的節(jié)點編碼機制是實現(xiàn)XML數(shù)據(jù)高效查詢的重要條件,對它的研究具有重要的現(xiàn)實意義。

為了有效地適應(yīng)XML數(shù)據(jù)的查詢和更新,文獻［3］總結(jié)了一個高效的編碼機制應(yīng)具有確定性、動態(tài)性、壓縮性3個方面的特征。為了不降低編碼性能和查詢性能,同時降低編碼長度,本文在對已有各種XML數(shù)據(jù)編碼機制深入研究的基礎(chǔ)上,提出了一種基于左兒子右兄弟節(jié)點鏈式相關(guān)的XML文檔動態(tài)編碼機制(Node Chain Related XML Dynamic Coding Scheme,NCCS),僅需修改局部若干個相關(guān)節(jié)點的編碼,就可以支持任意節(jié)點間的無限更新。

2 研究背景

目前,對于XML數(shù)據(jù)的編碼已有很多研究,常見的方法有前綴編碼［4］、區(qū)間編碼［5］、位向量編碼［6-7］等。一種良好的支持動態(tài)更新的XML編碼是指當頻繁地發(fā)生節(jié)點的插入、刪除等更新操作時,應(yīng)當不修改或者極少修改已有的節(jié)點編碼。在常見的編碼方法中,前綴編碼是主流的編碼方式之一,該方法保存了元素在文檔中的路徑信息,使得元素之間祖先后裔關(guān)系的判定相當于字符串之間包含關(guān)系的判斷,并能有效地支持對XML數(shù)據(jù)的各種更新操作,相比其他編碼的更新代價要小得多［8］。因此,對如何降低編碼存儲空間、提高查詢效率的前綴編碼的研究,對于解決XML應(yīng)用領(lǐng)域的許多問題都很有意義。

Dewey編碼［9］是最早提出的一種前綴編碼方案,其優(yōu)點是查詢效率較高,缺點是不支持節(jié)點更新［10］。文獻［11］提出了一種分數(shù)前綴的XML編碼方案(Fraction and Prefix Encoding Scheme,FPES),支持任意節(jié)點間的無限更新,無需二次編碼,但節(jié)點查詢效率和更新都不高。本文主要針對幾種常見基于路徑的前綴編碼方法進行研究與分析,根據(jù)XML文檔嵌套結(jié)構(gòu)的特點,從文檔根節(jié)點開始對依次到達的每條路徑的每一個節(jié)點都賦予一個基于路徑前綴的編碼。本文提出的節(jié)點鏈式相關(guān)的NCCS編碼方案提高了查詢效率,支持節(jié)點之間的無限更新,與分數(shù)前綴的FPES編碼方案相比,NCCS方案的節(jié)點查詢時間及節(jié)點更新時間都更少。

3 左兒子右兄弟節(jié)點鏈式相關(guān)的動態(tài)編碼

3.1 NCCS編碼方案

對于XML文檔而言,其本身是一棵節(jié)點標簽樹,記為T(V,E);V(T)代表以樹中節(jié)點為元素的節(jié)點集,E(T)代表的是連接父子關(guān)系節(jié)點之間邊的集合。XML文檔樹中的每個節(jié)點可以用一個四元組來表示:V(Ti)={〈Pi,Si,Li,Ri〉},其中:

Pi為樹中節(jié)點Ti的路徑前綴,根節(jié)點的路徑前綴為1,子節(jié)點的路徑前綴是其父節(jié)點路徑前綴與父節(jié)點編號之間用“.”分割的字符組合;

Si為樹中節(jié)點Ti的編號,Si的取值從1開始;

Li為樹中節(jié)點Ti最左兒子節(jié)點的編號,當Li= 0時,表示節(jié)點Ti為葉節(jié)點,沒有子節(jié)點;

Ri為樹中節(jié)點Ti相鄰右兄弟節(jié)點的編號;若用Max(Ti)表示節(jié)點Ti同級節(jié)點中最大的節(jié)點編號,則當Ri=Max(Ti)時,表示節(jié)點Ti是兄弟節(jié)點中從左向右起的最后一個節(jié)點,這時Ri將不再表示其右兄弟節(jié)點的編號,而是表示下一個新增兄弟節(jié)點將分配的編號為Ri。

節(jié)點的Key值由Pi.Si唯一標識,Li和Ri是為了優(yōu)化查詢及更新操作而設(shè)置的。

左兒子右兄弟節(jié)點鏈式相關(guān)的動態(tài)編碼示意圖如圖1所示。圖中虛線分別標注了指向最左兒子節(jié)點的編號及指向相鄰右兄弟節(jié)點的編號的指針鏈。

圖1 左兒子右兄弟節(jié)點鏈式相關(guān)的動態(tài)編碼示意圖

3.2 NCCS編碼節(jié)點關(guān)系的判斷

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

(1)兄弟關(guān)系判斷

設(shè)A＜P1,S1,L1,R1＞,B＜P2,S2,L2,R2＞是XML文檔樹T中的2個節(jié)點,如果P1=P2,則A節(jié)點和B節(jié)點是同級兄弟節(jié)點。進一步的,如果R1=S2或者R2=S1,則A節(jié)點和B節(jié)點為相鄰的兄弟節(jié)點。例如:節(jié)點A＜1.1,1,0,2＞和節(jié)點B＜1.1,2,1,3＞是同級兄弟節(jié)點。

(2)父子關(guān)系判斷

設(shè)A＜P1,S1,L1,R1＞,B＜P2,S2,L2,R2＞是XML文檔樹T中的2個節(jié)點,如果P1.S1=P2,則A節(jié)點是B節(jié)點的父節(jié)點,B節(jié)點是A節(jié)點的子節(jié)點。如:節(jié)點A＜1.1,2,1,3＞是節(jié)點B＜1.1.2, 1,0,2＞的父節(jié)點。

(3)祖先/后裔關(guān)系判斷

設(shè)A＜P1,S1,L1,R1＞,B＜P2,S2,L2,R2＞是XML文檔樹T中的2個節(jié)點,如果P1.S1為P2的子串,則A節(jié)點是B節(jié)點的祖先節(jié)點,B節(jié)點是A節(jié)點的后裔節(jié)點。如:節(jié)點A＜1.1,3,2,4＞是節(jié)點B＜1.1.3.1,2,1,3＞的祖先節(jié)點。

(4)節(jié)點所在層次判斷

設(shè)A＜P1,S1,L1,R1＞是XML文檔樹T中的一個節(jié)點,其所在層次可通過路徑前綴P1中分隔符“.”的個數(shù)來判斷。例如:節(jié)點A＜1.1.3.1,2,1,3＞所在的層次為第4層。

3.3 NCCS編碼更新數(shù)據(jù)

下面先討論新增節(jié)點的插入,設(shè)A＜X,Y,L,R＞是XML文檔樹T中的一個節(jié)點,以A節(jié)點為父節(jié)點,在其下陸續(xù)插入新節(jié)點后的節(jié)點編碼變化情況如下:

(1)無兄弟節(jié)點的新節(jié)點插入

在節(jié)點A下面插入一個新節(jié)點B,如圖2所示。A節(jié)點的編碼變?yōu)锳＜X,Y,1,R＞,新增節(jié)點B的編碼為＜X.Y,1,0,2＞,因為節(jié)點A的編碼中L修改成了1,表示A的最左兒子節(jié)點的編號是1,同時RB=Max(B)=2,表示B是最右面的唯一的節(jié)點,下一個插入的新節(jié)點將分配的編號是2。

圖2 無兄弟節(jié)點的情況

(2)有左兄弟但無右兄弟的新節(jié)點插入

在節(jié)點B的右面插入一個新節(jié)點C,如圖3所示。A節(jié)點的編碼不變,仍然是A＜X,Y,1,R＞,新增節(jié)點C的編碼為＜X.Y,2,0,3＞,B節(jié)點的編碼保持＜X.Y,1,0,2＞不變。

圖3 有左兄弟但無右兄弟的情況

(3)既有左兄弟也有右兄弟的新節(jié)點插入

在節(jié)點B和節(jié)點C之間插入一個新的節(jié)點D,如圖4所示。A節(jié)點的編碼不變,仍然是＜X,Y,1,R＞,新增節(jié)點D的編碼為＜X.Y,3,0,2＞,同時B節(jié)點的編碼調(diào)整為＜X.Y,1,0,3＞,節(jié)點C的編碼調(diào)整為＜X.Y,2,0,4＞。

圖4 既有左兄弟又有右兄弟的情況

(4)有右兄弟但無左兄弟的新節(jié)點插入

在節(jié)點B的左面插入一個新的節(jié)點E,如圖5所示。A節(jié)點的編碼修改為＜X,Y,4,R＞,新增節(jié)點E的編碼為＜X.Y,4,0,1＞,同時B節(jié)點、D節(jié)點的編碼保持不變,節(jié)點C的編碼修改為＜X.Y,2, 0,5＞。

圖5 有右兄弟但無左兄弟的情況

在插入新節(jié)點時,對于上文4種情況中的任何一種,只要找到同級兄弟節(jié)點中最右邊的節(jié)點,該節(jié)點的右兄弟編號就是新插入節(jié)點的編號,同時僅需要修改新插入節(jié)點周圍幾個相關(guān)節(jié)點的編碼以及最右邊的節(jié)點編號,其他節(jié)點的編碼都保持不變。

(5)節(jié)點的刪除

對于節(jié)點的刪除操作,如果被刪節(jié)點是最左的兒子節(jié)點,則需修改它父節(jié)點編碼中L的值;如果被刪節(jié)點是最右的兒子節(jié)點,僅需刪除該節(jié)點即可;如果被刪節(jié)點是子節(jié)點中間的某個節(jié)點,則需修改與它相鄰的左節(jié)點編碼中R的值。如刪除圖6中的B節(jié)點,只需要修改B節(jié)點左兄弟節(jié)點E的編碼,其他節(jié)點的編碼都保持不變。

圖6 刪除節(jié)點的情況

由于本文編碼方案是建立在節(jié)點路徑的基礎(chǔ)上,在直接子節(jié)點的所有兄弟節(jié)點中進行,在被刪除的節(jié)點有子孫后代時,將刪除以該節(jié)點為祖先的一顆子樹,因此刪除節(jié)點的操作對文檔樹的編碼不會產(chǎn)生任何影響。

4 實驗結(jié)果與分析

主要針對編碼方案在查詢、更新性能等方面進行性能評估,并將其與分數(shù)前綴FPES編碼進行比較。實驗用計算機CPU是Intel(R)Core(TM)2 Duo,主頻3.00 GHz,內(nèi)存2 GB,操作系統(tǒng)為Windows XP Professional,軟件環(huán)境是Netbeans 7.4+JDK 1.7。

為了簡單起見,實驗中做了以下相關(guān)處理:

(1)在進行XML文檔的初始化編碼時,由于DOM解析當XML文件很大時或者結(jié)構(gòu)比較復(fù)雜時,對內(nèi)存的要求很高。而SAX比DOM需要更少的內(nèi)存,具有更高的效率［12］。因此,采用SAX解析方法對XML文檔實現(xiàn)初始化編碼操作,由于SAX解析是基于事件處理的,因此采用棧結(jié)構(gòu)以深度優(yōu)先搜索算法建立節(jié)點編碼。

(2)在實驗中只是針對XML文檔中的元素節(jié)點進行了編碼處理,忽略了處理指令節(jié)點、屬性節(jié)點、文本節(jié)點、注釋節(jié)點等。

(3)對于分數(shù)前綴FPES編碼方案,由于其節(jié)點編碼采用英文字母,當XML文檔樹的度很高時,顯然不利于文檔節(jié)點的編碼,因此在對比實驗中將節(jié)點編碼都修改成了整數(shù)類型。

實驗用 XML數(shù)據(jù)來自 UWXMLData Repository通用數(shù)據(jù)集中的 Florid-Mondial Case Study 2002(FMCS)、Transaction Processing Performance Council 2002(TPPC)和GSFC/NASA XML Project 2001(GNXP),相關(guān)參數(shù)如表1所示。

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

實驗檢測本文提出的節(jié)點鏈式相關(guān)的NCCS編碼方案和分數(shù)前綴FPES編碼方案對文檔編碼、插入10 000個節(jié)點(新插入節(jié)點的度都以平均數(shù)為5的取值進行處理)、查詢1 000 000個節(jié)點(在文檔中隨機選取)的平均處理時間如表2所示。

表2 文檔處理時間的對比 ms

從實驗結(jié)果可以看出,對于相同大小的XML文檔,NCCS編碼與FPES編碼對文檔編碼所花的時間大致相當。FPES編碼由于采用分數(shù)前綴的表示方法,雖然支持無限更新,但是在查詢及更新數(shù)據(jù)時由于節(jié)點間的相關(guān)信息少,在插入節(jié)點時需要花費大部分時間找到插入位置,因此對文檔處理所花的時間明顯較NCCS編碼多。

因為節(jié)點鏈式相關(guān)的NCCS編碼在結(jié)點關(guān)系判斷時只需要通過節(jié)點編碼就可以簡單快捷地判斷出節(jié)點間的關(guān)系,尤其是對于實現(xiàn)節(jié)點的多種軸操作運算時,采用節(jié)點鏈式相關(guān)的NCCS編碼要比其他編碼具有查詢效益突出的優(yōu)點;而分數(shù)前綴編碼在編碼比較時,由于涉及到分數(shù)編碼的結(jié)點判斷,可能需要進行多次數(shù)值比較,因此在實現(xiàn)節(jié)點的軸操作運算時相應(yīng)的查詢響應(yīng)時間較長。

5 結(jié)束語

本文提出的鏈式相關(guān)NCCS編碼方案,由于基于路徑的編碼具有不定長的特性,在簡短性和可擴充性優(yōu)化方面,與分數(shù)前綴的FPES編碼方案相比,本文編碼方案的節(jié)點查詢時間及節(jié)點插入時間更少,支持節(jié)點間的無限更新,并且保持了節(jié)點間豐富的相關(guān)信息,提高了文檔的處理效率。今后將針對編碼壓縮存儲情況和提高大數(shù)據(jù)的查詢效率進行更深入的研究。

［1］ 蔡體健.XML網(wǎng)頁設(shè)計實用教程［M］.北京:人民郵電出版社,2009.

［2］ 孫更新,肖 冰,彭玉忠.XML編程與應(yīng)用教程［M］.北京:清華大學(xué)出版社.2010.

［3］ 胡江明,李建華,杜章華,等.一種高效的動態(tài)XML文檔樹編碼機制［J］.計算機工程,2010,36(19):75-77.

［4］ Tatarnov I,Viglas S D,Beyer K,et al.Storing and Quering Ordered XML Using a Relational Database System［C］//Proceedings of SIGMOD'02.Madison, USA:IEEE Press,2002:204-215.

［5］ Han Y T,Park H S.Distinctive Traffic Characteristics of Pure and Game P2P Applications［C］//Proceedings of the 10th International Conference on Advanced Communication Technology.Daejeon,Korea:［s.n.］, 2008:405-408.

［6］ 馮少榮,陳天爍.基于向量的動態(tài)XML編碼方法研究［J］.計算機工程,2012.38(13):64-66.

［7］ Tatarinov I,Viglas S D,Beyer K,et al.Storing and Querying Ordered XML Using a Relational Database System［C］//Proceedings of the 21st ACM SIGMOD InternationalConference on ManagementofData.Madison,USA:［s.n.］,2002:204-215.

［8］ 閆文剛,李 晶.一種XML文檔樹節(jié)點編碼的動態(tài)調(diào)整算法的研究［J］.佳木斯大學(xué)學(xué)報:自然科學(xué)版, 2010,28(3):360-362.

［9］ 姚保峰,朱洪浩,王 磊,等.包含Dewey碼的XML文檔映射關(guān)系數(shù)據(jù)庫策略［J］.計算機工程與應(yīng)用, 2012,48(27):128-131.

［10］ 魏東平,賈 楠,徐瑞敏.一種支持數(shù)據(jù)更新的前綴編碼方案［J］.計算機系統(tǒng)應(yīng)用,2011,20(3):189-192.

［11］ 劉先鋒,周 舟,劉 萍,等.一種分數(shù)前綴XML編碼方案［J］.計算機工程,2012,38(12):29-31.

［12］ 孫更新,肖 冰,彭玉忠.XML編程與應(yīng)用教程［M］.北京:清華大學(xué)出版社,2010.

編輯 任吉慧

XML Dynamic Coding Scheme of Left Son and Right Sibling Chain Association

WANG Weisheng,JIA Xiangdong
(College of Computer Science and Engineering,Northwest Normal University,Lanzhou 730070,China)

Aiming at the problem of eXtensible Markup Language(XML)data query and update,this paper proposes a dynamic XML coding scheme based on left son and right sibling node chain association.According to the chain related information about brother node,only by doing some simple changes in local,it can realize unlimited updates of XML data and the ancestor descendant relationships,parent-child relationship and sibling relationships and other axis operation.The results show that the proposed coding scheme not only efficiently supports structure query,but also has less coding time and insert node time.It can fast and accurately determine the relationship between any XML document structure tree nodes,so as to avoid a lot of code adjustment problems the update brings,and it efficiently supports the query and update of XML documents.

eXtensible Markup Language(XML);document tree;coding scheme;axis operation;data query; data update

1000-3428(2014)11-0056-04

A

TP311

10.3969/j.issn.1000-3428.2014.11.011

國家自然科學(xué)基金資助項目(61261015);甘肅省杰出青年基金資助項目(1308RJDA007)。

王維盛(1974-),男,講師、碩士,主研方向:網(wǎng)絡(luò)計算;賈向東,副教授、博士。

2013-12-23

2014-02-20E-mail:wangws@nwnu.edu.cn

中文引用格式:王維盛,賈向東.左兒子右兄弟鏈式相關(guān)的XML動態(tài)編碼方案［J］.計算機工程,2014,40(11):56-59.

英文引用格式:Wang Weisheng,Jia Xiangdong.XML Dynamic Coding Scheme of Left Son and Right Sibling Chain Association［J］.Computer Engineering,2014,40(11):56-59.