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

《一种基于扩展区间编码的结构连接算法twigelm》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、一种基于扩展区间编码的结构连接算法TwigELM：由于XML具有格式良好，自描述，可扩展等优点，使得XML成为X络上信息表达和数据交换事实上的标准。随着XML格式数据的广泛应用，如何有效地存储和查询XML格式数据成为当前研究的热点。为了有效支持XML结构查询，研究者已经提出了XML数据的各种编码方案。通过编码的方式将XML结构查询的计算转化为结构连接的计算。该文提出了一种新的XML文档树编码方案，并基于该编码方案给出了一种新的小枝模式查询算法TTationScienceandEngineering,SUST,Qingdao266510,China

2、)　　Abstract:BecauseXMLhasaed,self-describing,extensible,etc.,maketheXMLinformationintotheatteddata,hoattobeearesearchfocus.InordertoeffectivelysupporttheXMLstructureofinquiry,researchershaveproposedavarietyofXMLdataencodingscheme.Byenttreecodingschemeandcodingschemebasedonthe

3、givenmodel,aneTentsshocaneffectivelyimprovetheefficiencyofstructuraljoinoperation.　　Keye　　XML文档树的编码方案可以分为两大类：基于区间的编码和基于路径的编码。前者是利用XML文档的有序特点，根据每一个元素结点在原XML文档树中字典顺序的位置给每一个元素结点赋予一个编码；后者则是利用XML文档的嵌套的特点，根据XML文档的嵌套结构，给从文档根节点开始所能到达的每一条路径和元素结点赋予一个编码[1]。　　到目前为止，国内外已经提出的编码方案主要包括：前缀编码、

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

5、是结点的后裔范围；depth表示该结点在文档树中所在的层数。该编码方案中，判断结点x是结点y的双亲的充要条件是：order（x）。begin和end的产生规则：对树中的所有结点进行先序遍历，每一个结点在遍历时被访问两次。一次是在遍历该结点的所有后裔结点之前访问该结点，产生该结点的序号begin;另一次是在遍历该结点的所有后裔结点后再访问一次该结点，产生结点序号end。每一个结点还被赋予一个值level，表示该结点在文档树中所处的层数。类似的，该编码方案中，判断结点x是结点y的双亲的充要条件是：begin(x)标识XML文档树中的每一个结点。pre

6、是结点的扩展先序遍历序号，取值非连续，为结点的插入预留空间，Size是结点的后裔范围，level表示结点在文档树中的层数。该编码方案中，结点pre和size必须满足：1）对于XML文档树中的结点y和它的双亲结点x，有pre（x）pre(y)。2）XML文档树中的兄弟结点x和y，如果在先序遍历中y是x的右兄弟，则pre(x)+size（x），不需要重新编码其余结点。　　3一种新的T)对输入的结点流中的结点进行判断，如果满足小枝模式条件将其入栈，否则将结点流向前推进；当出现叶结点时，判断其父节点栈是否为空，若不为空表明满足小枝模式的结点已经生成，把相

7、应的栈中结点出栈，最后归并所有线性路径结果，得到最终满足小枝模式查询的匹配结果。　　在Tpty(Sqt)andtopSize(Sqt)

8、foreachmiinchildren(m)//遍历查询结点m的所有后裔结点　　④ni=getNext(mi);　　⑤nmin=mina