左儿子右兄弟链式相关的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.