一种基于扩展区间编码的结构连接算法TwigELM

1、一种基于扩展区间编码的结构连接算法TwigELM 摘要：由于XML具有格式良好，自描述，可扩展等优点，使得XML成为网络上信息表达和数据交换事实上的标准。随着XML格式数据的广泛应用，如何有效地存储和查询XML格式数据成为当前研究的热点。为了有效支持XML结构查询，研究者已经提出了XML数据的各种编码方案。通过编码的方式将XML结构查询的计算转化为结构连接的计算。该文提出了一种新的XML文档树编码方案，并基于该编码方案给出了一种新的小枝模式查询算法TwigELM，实验表明，该算法可有效提高结构连接操作的效率。 关键词：XML；结构连接；小枝模式；编码方案 中图分类号：TP311文献标识码：A文

2、章编号：1009-3044(2011)11-2495-03 A Structural Join Algorithm TwigELM Based on Extended Interval Coding SUN Qing-tao, LU Yan (College of Information Science and Engineering, SUST, Qingdao 266510, China) Abstract: Because XML has a well-formed, self-describing, extensible, etc., make the XML information

3、into the network expression and the de facto standard data exchange. With the extensive use of XML formatted data, how to store and query data in XML format to become a research focus. In order to effectively support the XML structure of inquiry, researchers have proposed a variety of XML data encod

4、ing scheme. By way of coding the query XML structure into a structure of connected computing calculations. This paper presents a new XML document tree coding scheme and coding scheme based on the given model, a new Twig query algorithm TwigELM, experiments show that the algorithm can effectively imp

5、rove the efficiency of structural join operation. Key words: XML; structural join; twig pattern; coding scheme XML文档树的编码方案可以分为两大类：基于区间的编码和基于路径的编码。前者是利用XML文档的有序特点，根据每一个元素结点在原XML文档树中字典顺序的位置给每一个元素结点赋予一个编码；后者则是利用XML文档的嵌套的特点，根据XML文档的嵌套结构，给从文档根节点开始所能到达的每一条路径和元素结点赋予一个编码1。 到目前为止，国内外已经提出的编码方案主要包括：前缀编码、区间编码和二

6、叉树编码等。本文主要研究的是区间编码，提出了一种新的XML扩展区间编码Extended Li-Moon。 1 相关研究 XML文档树中的每一个结点被赋予一个区间编码start，end，并且满足：一个结点的区间编码包含它的后裔结点的区间编码，即如果结点x是结点y的祖先，当且仅当start（x） end(x)。 文献3给出了第一种区间编码方案，称为Dietz编码。编码规则是：XML文档树中的每一个结点被赋予一个先序遍历序号和后序遍历序号的二元组。pre和post分别是结点的先序和后序遍历序号。 Li和Moon在文献4中提出了第二种区间编码方案，称为Li-Moon编码。编码规则为对XML文档树的每一

7、个结点赋予一个三元组。Order是结点的扩展先序遍历序号，取值是非连续的；size是结点的后裔范围；depth表示该结点在文档树中所在的层数。该编码方案中，判断结点x是结点y的双亲的充要条件是：order（x）为了实现在关系数据库中存储的XML文档的快速查找，文献5给出了第三种编码方案，称为Zhang编码。编码规则为XML文档树中的每一个结点被赋予一个三元组。begin和end的产生规则：对树中的所有结点进行先序遍历，每一个结点在遍历时被访问两次。一次是在遍历该结点的所有后裔结点之前访问该结点，产生该结点的序号begin;另一次是在遍历该结点的所有后裔结点后再访问一次该结点，产生结点序号end

8、。每一个结点还被赋予一个值level，表示该结点在文档树中所处的层数。类似的，该编码方案中，判断结点x是结点y的双亲的充要条件是：begin(x)begin(y)begin(y)基于区间的编码优点是能够快速确定XML文档树中任意两个结点对之间的结构关系，编码简单。缺点是始终不能完全支持XML文档的动态更新。本文考虑了结点在文档树的位置关系，给出了一种新的编码方法: 对XML文档树上不同位置的结点，预留不同的编码空间。这样，当XML文档树中的结点更新时，可以减少重新编码结点的数量。 2 一种新的XML扩展区间编码Extended Li-Moon 本研究所提出的扩展区间编码的编码规则是：以三元组标

9、识XML文档树中的每一个结点。pre是结点的扩展先序遍历序号，取值非连续，为结点的插入预留空间，Size是结点的后裔范围，level表示结点在文档树中的层数。该编码方案中，结点pre和size必须满足：1）对于XML文档树中的结点y和它的双亲结点x，有pre（x） pre(y)。2）XML文档树中的兄弟结点x和y，如果在先序遍历中y是x的右兄弟，则pre(x)+size（x）假设对深度为n的满k叉树，若在该k叉树第i层第j个结点Ni,j左侧插入一个兄弟结点，则需要对先序遍历序号大于结点Ni,j的后继结点进行重新编码。并且满足先序遍历序号越小的位置，对应的更新代价越大，即插入时引起的重新编码结点

10、数目越多6。在本文提出的编码方案中，结点的扩展先序遍历序号pre取值非连续，根据xml文档树结点的位置的不同，预留不同的编码空间。对于更新代价大的结点，预留较大的空间，而对于更新代价小的结点，预留较少的空间。因此减少了更新操作引起的重新编码的结点数量。如在图1中，删除结点，不需要重新编码其余结点。 3 一种新的Twig模式查询算法TwigELM 3.1 算法描述 目前流行的XML查询语言是XPath和XQuery，而处理XPath/XQuery表达式的核心操作是从XML数据源中查找与查询相匹配的数据片段，即Twig查询处理。一个XPath路径表达式查询可以通过小枝模式进行建模，称为小枝模式查询

11、。目前，研究者已经提出了一系列有效的小枝模式匹配算法。根据算法是否需要执行归并操作，可以将该类算法分为两种。 1）基于归并的小枝模式匹配算法：TwigStack算法、PathStack算法、TSGenetic+算法等。 2）非归并的小枝模式匹配算法：Twig2Stack算法和TwigList算法。 本文提出的是一种基于扩展区间编码的归并小枝模式匹配算法，是对TwigStack算法8的改进。该算法的优点是基于支持XML更新的扩展区间编码提出的，考虑了分枝路径查询的普遍现象，可以有效处理包含“/”边的小枝模式查询，减少了对查询匹配过程中中间匹配结果的存取。 3.2 算法思想 TwigELM（Twi

12、g based on Extended Li-Moon）算法的思想是：对于一个路径模式查询，将每个小枝的路径查询作为一个整体考虑，采用自顶向下的匹配方法，通过调用递归函数getnext(m)对输入的结点流中的结点进行判断，如果满足小枝模式条件将其入栈，否则将结点流向前推进；当出现叶结点时，判断其父节点栈是否为空，若不为空表明满足小枝模式的结点已经生成，把相应的栈中结点出栈，最后归并所有线性路径结果，得到最终满足小枝模式查询的匹配结果。 在TwigELM算法中，对XML文档中的结点流Tqi的操作函数有： nextPre(Tq):返回流Tq中下一数据结点的pre区间编码值； nextSize(Tq

13、):返回流Tq中下一数据结点的size区间编码值。 在TwigELM算法中，对XML文档中的结点流Tqi的操作函数有： topPre:返回栈顶元素的pre区间编码值； topSize: 返回栈顶元素的size区间编码值。 3.3 小枝模式查询算法TwigELM： 输入：小枝模式查询q，n个查询结点的流Ti 输出：模式查询q的匹配结果 TwigELM（q,T1,T2,，Tn） while (!end(q) qt=getNext(q); while (not empty(Sqt)and topSize(Sqt) pop(Sqt) ; moveStreamToStack(Tqt,Sqt,pointe

14、r to top(Sparent(qt),q)/流Tqt的下一数据结点进栈，链栈指针pointer指向双亲栈的栈顶结点 endwhile endwhile mergeAllPathSolutions()/归并多个路径模式查询的局部匹配结果 getNext(m) if(isLeaf(m) return m; foreach mi in children(m) /遍历查询结点m的所有后裔结点 ni=getNext(mi); nmin=minargninextPre(Tni); return nmin;/返回流Tni中下一数据结点的pre区间编码值最小的结点 moveStreamToStack(Tn

15、,Sn,p,m) while(Tm isAncestorof(Tn) ) foreach mi in children(m) ni=getNext(mi); nmax=maxargninextPre(Tni); while(nextSize(Tm)advance(Tm); /流Tm的指针指向下一个数据结点，指针下移 push(Sn,next(Tn),p); if(isLeaf(n) output result of path solution /输出可能满足小枝模式查询的局部匹配结果 pop(Sn); /出栈 advance(Tn); 对于仅仅包含“/”边的小枝模式查询q，在最坏情况下Twig

16、ELM算法的I/O和CPU时间复杂度与q的从根到叶的路径查询的局部匹配结果的大小无关;对于包含“/”边的小枝模式查询q，TwigELM算法不能保证它的I/O和CPU时间是最优的。 4 实验分析 实验的目的是将本文提出的小枝模式算法同PathStack和TwigStack算法进行路径查询效率的比较。测试的硬件配置为： Intel(R) Pentium(R) D CPU 3.00 GHz 2.99 GHz,1GB内存, DDR RAM ；软件平台为： Microsoft Windows XP sp3操作系统,集成开发环境 Microsoft Visual Studio 2005 ,以及 SQL S

17、erver 2005，开发语言:C#； 数据集：为了验证本文所提出的小枝模式查询算法的有效性，在XMark数据集上进行了大量的实验。在XMark数据集是有XMark文档生成器自动生成的一个数据集，它的深度是12，包含80多万个元素结点。选择XMark数据集的原因是XMark的规模相对较小，结点类型也较少。 四个小枝模式匹配查询在TwigELM算法所找到的匹配结果的数目如图2所示。 TwigELM同PathStack算法的效率比较如图3所示。由图3可以看出，TwigELM算法要优于PathStack算法，这是因为PathStack算法在小枝模式查询中，产生了大量的中间结果，需要多次对中间匹配结果

18、进行存取，因此算法执行效率较低。而TwigELM在对包含“/”边的小枝模式查询中，对不满足局部匹配结果的元素结点不进行入栈操作，减少了对中间结果的存取，提高了算法执行效率。 TwigELM（采用的是本文提出的Extended Li-Moon）算法同TwigStack（采用的是区间编码的Zhang编码）算法在4个小枝模式查询树上的执行时间如图4所示。TwigStack算法时间性能要略好于TwigELM，这是因为：TwigStack采用的是不能支持XML动态更新的Zhang编码，数据结点间祖先/后裔的结构关系判断是通过简单的加减运算; 而TwigELM采用的是一种支持XML动态更新的Extende

19、d Li-Moon编码，数据结点间祖先/后裔的结构关系判断相对复杂，这是支持更新的代价。虽然效率稍微降低了一些，但是也是可以接受的。 5 结论 为了提高XML路径查询的效率，本文在分析已有各种XML小枝模式查询匹配算法的基础上，提出了一种新的XML小枝模式查询匹配算法TwigELM。同时，本文提出了一种支持文档树中结点更新的区间编码方案，它可以更好地解决更新操作造成的结点重新编码问题，并给出了明确的节点编码的计算表达式。实验证明，基于此编码的TwigELM算法对提高XML文档树的查询效率很有帮助。 参考文献： 1 万常选.XML数据库技术M.北京:清华大学出版社,2005. 2 万常选,刘云生

20、,徐升华,等.基于区间编码的XML索引结构的有效结构连接J.计算机学报,2005,28(1):113-127. 3 DIETZ P F,SLEATOR D.Two Algorithms for Maintaining Order in a ListC/Retal L H.Proceedings of the 19th Annual ACM Symposium on Theory of Computing,New York City,1987:365-372. 4 LI Q,MOON B.Indexing and querying XML data for regular path expres

21、sionsC/Proceedings of the 21th VLDB Conference,Roma,Italy,2001:361-370. 5 ZHANG C,NAUGHTON J,DEWITT D,et al.On Supporting Containment Queries in Relational Databases Management SystemsC/Proceedings of the 20th ACM SIGMOD International Conference on Management of Data.New York:ACM Press,2001:426-437. 6 徐娟,李战怀,王彦龙.基于更新代价的XML文档区间编码方案研究J.计算机科学,2006,33(11):342-346. 7 Bruno N,Koudasn N,Srivastava.Holistic Twig joins:optimal XML Pattern MatchingC/Proceedings ofthe 21th ACM SIGMOD International Conferenc