左兒子右兄弟鏈式相關的XML動態編碼方案

王維盛,賈向東

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

左兒子右兄弟鏈式相關的XML動態編碼方案

王維盛,賈向東

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

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

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

1 概述

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

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

2 研究背景

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

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

3 左兒子右兄弟節點鏈式相關的動態編碼

3.1 NCCS編碼方案

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

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

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

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

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

節點的Key值由Pi.Si唯一標識,Li和Ri是為了優化查詢及更新操作而設置的。

左兒子右兄弟節點鏈式相關的動態編碼示意圖如圖1所示。圖中虛線分別標注了指向最左兒子節點的編號及指向相鄰右兄弟節點的編號的指針鏈。

圖1 左兒子右兄弟節點鏈式相關的動態編碼示意圖

3.2 NCCS編碼節點關系的判斷

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

(1)兄弟關系判斷

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

(2)父子關系判斷

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

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

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

(4)節點所在層次判斷

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

3.3 NCCS編碼更新數據

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

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

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

圖2 無兄弟節點的情況

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

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

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

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

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

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

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

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

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

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

(5)節點的刪除

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

圖6 刪除節點的情況

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

4 實驗結果與分析

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

為了簡單起見,實驗中做了以下相關處理:

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

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

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

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

表1 測試通用數據集

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

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

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

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

5 結束語

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

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

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

［3］ 胡江明,李建華,杜章華,等.一種高效的動態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］ 馮少榮,陳天爍.基于向量的動態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文檔樹節點編碼的動態調整算法的研究［J］.佳木斯大學學報:自然科學版, 2010,28(3):360-362.

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

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

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

［12］ 孫更新,肖 冰,彭玉忠.XML編程與應用教程［M］.北京:清華大學出版社,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

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

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

2013-12-23

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

中文引用格式:王維盛,賈向東.左兒子右兄弟鏈式相關的XML動態編碼方案［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.