基于分数的动态前缀XML 编码方案

姚保峰，马程，谢娜，戚晓明，郭有强

(蚌埠学院 计算机科学与技术系，安徽 蚌埠 233000)

0 引言

随着越来越多的网络数据采用XML 格式进行表示，XML 已经成为网络上数据存储和交换的事实标准，同时也是Web 的基本组成部分和未来技术发展的基础.如何快速实现XML 文档的数据查询是当前XML 相关研究的热点，而XML 的数据查询依赖于XML 的文档树编码，因此，对XML 文档树的编码机制进行研究具有重要意义.XML 文档树的编码机制是指对XML 文档中的每个节点赋予唯一的编码，以通过这个编码快速地确定任意两个节点之间的关系(如父子关系、祖先后裔关系、兄弟关系等)［1］.目前已经提出了一些XML 的编码方案，但是当对XML 数据进行插入、删除等更新操作时，现有的编码方案往往需要大幅调整相应结点的编码甚至对整棵树进行重新编码，造成数据更新的代价很大.本文提出一种基于分数的动态前缀编码DPEF(Dynamic prefix encoding with fraction).

1 相关工作

目前比较常见的编码方式有区间编码［2－3］和前缀编码［4－5］.区间编码为XML 文档树的每一个节点赋予一个区间编码［start，end］，并要求满足:一个节点的区间编码包含它的后裔节点的区间编码［6］.文献［2］和文献［3］提出的区间编码方法都能够有效地支持包含关系和文档位置关系的计算，且编码长度小，查询效率也较高.但是，它们都没有完全实现编码的动态更新，在预留空间不足的情况下需要二次编码，从而产生巨大的时间和空间开销.前缀编码将文档树中父节点的编码作为其子节点编码的前缀.Dewey 编码［7］是最常用的一种前缀编码，但是Dewey 编码本身并不直接支持更新操作.文献［8］提出的ORDPATH 编码与Dewey 编码类似，但采用二进制形式表示编码，初始编码都用正奇数表示，插入新节点时以偶数作为占位符结合预留的负数实现了节点的动态更新，但是ORDPATH 编码插入节点后的位置关系判断复杂且编码规模较大.文献［9］提出的TDE 算法将实数映射为二维元组，利用任意两个实数间存在无限个实数的特点，避免了更新时的二次编码，但TDE 编码的节点长度过大，浪费了存储空间.

本文在Dewey 编码的基础上提出一种基于分数的动态前缀编码DPEF(Dynamic prefix encoding with fraction)，该编码保留了Dewey 编码的良好特性，实现了XML 数据的动态更新.

2 DPEF 编码

定义1数符对应表NCCT(Numeric－Character Corresponding Table).设有数字集合N={0，1，2，3，4，5，6，7，8，9}，字符集合C={’A’，’B’，’C’，’D’，’E’，’F’，’G’，’H’，’I’，’J’}，对任一n∈N 有唯一的c∈C 与之一一对应.对应规则函数f={＜0，A＞，＜1，B＞，＜2，C＞，＜3，D＞，＜4，E＞，＜5，F＞，＜6，G＞，＜7，H＞，＜8，I＞，＜9，J＞}.

定义2分数编码FC(Fraction Coding).任何一个分数都可以表示为hy 的形式，其中h={a0a1…an|ai∈C，i，n∈N}，C 是定义1 中的字符集合.即表示分数时将分子x 用定义1 的规则表示为字符形式，分母y 保持不变.如可以表示为BFH13.

定义3静态DPEF 编码.静态DPEF 编码是指在初始化XML 文档时为XML 文档树中的每个节点赋予一个唯一的编码，其编码规则由下列规则确定:

(1)根节点的编码为1;

(2)在对文档树进行宽度优先遍历的过程中，如果节点v 是节点u 的第i 个子节点，那么，节点v 的DPEF 编码为c(u).i，其中的c(u)表示节点u 的编码.

定义4动态DPEF 编码.动态DPEF 编码是指在静态DPEF 编码的基础上，使其支持节点的插入、删除和更新操作.考虑到节点的删除和更新操作不会影响其他节点编码，因此这里的动态性主要指插入操作.DPEF 编码在插入新节点时通过分数表示新节点的编码，考虑分数在编码中难以表示，对分数进行了FC 编码.插入节点主要包含以下3 种情况:

(1)在两相邻节点u1 和u2 之间插入.设u1 的节点编码为p(u).a，u2 的节点编码为p(u).b(p(u)为u1 和u2 的父节点编码)，则新插入节点的编码为p(u).((a+b)/2).如图1(a)中，在原有节点u1 和u2 之间依次插入新节点u3、u4 和u5，则u3的编码为1.2.1.((1+2)/2)，根据定义2 的分数编码表示法定义，最终编码可表示为1.2.1.D2，采用同样的方法，u4 的编码为1.2.1.((3/2+2)/2)，最终编码表示为1.2.1.H4，u5 的编码为1.2.1.((3/2+7/4)/2)，最终编码表示为1.2.1.BD8.

图1 DPEF 编码的插入操作

(2)在最左节点u1 左边插入.设u1 的节点编码为p(u).a，则新插入节点的编码为p(u).a/2).如图1(b)中，在节点u1的左边依次插入u2 和u3，则u2 的编码为1.2.1.1/2)，根据定义2 的表示方法，最终可表示为1.2.1.B2，同样的，u3 的编码为1.2.1.(1/2)/2)，最左编码为1.2.1.B4.

(3)在最右节点u1 右边插入.设u1 的节点编码为p(u).a，则新插入节点的编码为p(u).(a+1).如图1(b)中，在节点u1 的左边依次插入u4 和u5，则u4 的编码为1.2.1.2，u5 的编码为1.2.1.3.

3 相关算法

可以看出，DPEF 编码在形式上类似于Dewey 码，因此仍然具有Dewey 码的良好特性，如算法实现简单、编码本身包含节点间的位置关系等.但是由于更新时采用了分数形式表示节点编码，因此实现了节点的动态更新.下面是插入节点和节点位置关系判定的算法描述.

算法1 中得到左右节点DPEF 编码的时间复杂度为O(n)，求父节点编码和插入一个节点的时间复杂度均为O(1)，因而算法1 的时间复杂度为O(n).算法2 中得到节点DPEF 编码和计算节点所在层的时间复杂度为O(n)，判断两节点位置关系需对两节点的编码串作模式匹配，采用KMP 算法该过程也可在O(n)时间内完成，因而算法2 的时间复杂度也为O(n).

4 实验及性能分析

4.1 实验环境

本实验硬件环境为:AMD Athlon 7750 双核2.7GHz 处理器，2G 内存，160G 硬盘，软件环境为Windows 7 Ultimate 版32 位操作系统，开发平台为Eclipse 3.6.2，对XML 文档采用Java DOM4J 包进行解析，并存储于MySQL 5.5 中.选用的测试数据集情况如表1 所示.

表1 测试数据集

表1 给出了实验用到的5 个测试数据集.其中数据集D1 是文献［12］提供的，D2 和D3 是文献［13］提供的，D4 和D5 由XML 自动生成工具XMARK［14］生成，生成D4 采用的生成因子f 为0.04，生成D5 采用的生成因子f 为0.08.

4.2 实验结果分析

图2 显示了三种编码方案在编码的空间占用上的比较情况.由于TDE 编码采用二维编码，即每个节点均由若干二维元组组成，而DPEF 编码和ORDPATH 编码的每个节点均由若干单值组成，因而在空间占用上TDE 明显较大，DPEF 编码和ORDPATH 编码占用空间相差不大，但ORDPATH 在编码时空出了偶数，因此当节点较多时产生的编码最后一位平均值会逐渐大于DPEF 编码，可以看出，在空间占用方面DPEF 相对较小.

图2 三种编码占用存储空间比较

图3 三种编码的静态编码时间比较

图3 是三种编码的静态编码时间比较，DPEF 编码和ORDPATH 编码的静态编码都和Dewey 码类似，因此在编码时间上也基本一致，而TDE 编码的计算方法较为复杂，因而耗费时间较多.图4 是分别采用三种编码方案在五种不同数据集上动态插入1000 个新节点时的平均性能比较情况，由于DPEF 编码和TDE 编码的插入操作都需进行一次数值计算才能得到新的编码，因而它们的更新效率比较接近，而ORDPATH 需要先引入占位符再插入新节点，因而更新效率较差.

图4 三种编码的动态编码时间比较

5 结束语

本文在分析现有区间编码和前缀编码的基础上，提出一种基于分数的动态前缀编码DPEF，该编码方案保留了Dewey 编码的特性，编码简单易用，支持节点间的位置关系判定操作，且在不预留空间的前提下实现了对编码的动态更新.实验结果表明，DPEF 编码在空间占用和编码的时间效率上都表现出了较好的性能.下一步考虑研究在DPEF 编码的基础上设计和实现支持动态更新的Native XML 数据库的索引结构.

［1］胡江明，李建华，杜章华，魏锋.一种高效的动态XML 文档树编码机制［J］.计算机工程，2010，19(36);75－77.

［2］Li Quanzhong，Moon B.Indexing and Querying XML Data for Regular Path Expressions［C］.Proc.of the 27th International Conference on Very Large Data Bases.Roma.Italy:［S.n.］，2001.36l－370.

［3］Zhang Chun，Naughton J，David D，et a1.On Supporting Contain－ment Queries in Relational Database Management Systems［C］.Proc.of SIGMOD’01.Santa Barbara，California，USA:［S.n.］，2001.425－436.

［4］Cohen E，Kaplan H.Milo Labeling Dynamic XML Trees［C］.Proc.of P0DS’02.Madison Wisconsin，SA:［S.n.］，2002.271－281.

［5］Harder L Haustein M，Mathis C，et a1.Node Labeling Schemes for Dynamic XML Documents Reconsidered［J］.Data＆Knowledge Engineering，2007，60(1):126－149.

［6］Wan Changxuan，Liu Xiping.The XML database technology 2nd ed［M］.Beijing Tsinghua University Press，2008.106 in Chinese.

［7］ITatarinov SD，Viglas K，Beyer J，Shanmugasundaram，E，et al.Storing and querying ordered xml using a relational database system［C］.Proc.of the 2002 ACM SIGMOD.hlt’1 Conf.on Managementof Data(SIGMOD).Madison:ACM Press，2002.204－215.

［8］O’Neil P，O’Neil E，Pal S，Cseri I，et al.ORDPATHs:Insert－Friendly XML node labels.In:Weikum G，König AC，Deöloch S，eds［C］.Proc.of the 2004 ACM SIGMOD Int’l Conf.on Management of Data(SIGMOD 2004).Paris:ACM Press，2004.903－908.

［9］覃遵跃，卓月明，徐洪智，张彬连.一种支持XML 文档更新的编码方案［J］.计算机工程，2011，37(5):47－49.

［10］汪陈应，袁晓洁，王鑫，刘众奇.BSC:一种高效的动态XML 树编码方案［J］.计算机科学，2008，35(3):76－78.

［11］Ko Hye－Kyeong，Lee Sang－Keun.A Binary String Approach for Updates in Dynamic Ordered XML Data［J］.IEEE Transactions on Knowledge and Data Engeneering，2008，99(1):602－607.

［12］Dong Chan An，Seog Park.Efficient labeling scheme of XML data considering update operations［C］.8th IEEE International Conference on Computer and Information Technology，CIT 2008.Sydney，Australia:NSW，2008.438－443.

［13］NIAGARA Experimental Data［EB/OL］.Available at http://www.cs.wisc.edu/niagara/data.html.

［14］University of Washington XML Repository［EB/OL］.Available at:http:www.cs.washington.edu/research/xmldatasets/.

［15］Xmark－An XML Benchmark Project［EB/OL］.Available at http://monetdb.ewi.nl/xml/downloads.htm1.