一种基于层次栈的XML数据小枝查询算法研究-层次树.docx

一种基于层次栈的XML数据小枝查询算法研究层次树论文导读:：针对XML数据存储和查询的研究正方兴未艾。研究者已经由XML数据简单路径查询转移到复杂小枝查询的研究。基于层次树的小枝查询方法。关键词：XML数据，小枝查询，层次树1引言XML作为基于WEB应用的一种电子数据交换标准，是Internet共通的语言与沟通的媒介。针对XML数据存储和查询的研究正方兴未艾。当前，研究者已经由XML数据简单路径查询转移到复杂小枝查询的研究。目前小枝查询方法中最有代表性的是Bruno等提出的基于整枝连接技术的TwigStack[1]算法，其思想是利用相互连接的多栈结构一次性生成查询结果文档。然而TwigStack算法对于含父亲-孩子边的查询不够有效[6]。本文在发现文档树中与查询树中的同一个查询结点对应的结点间自然地形成树型结构关系的基础上，提出把文档树中与相同的查询结点匹配的元素组织成层次栈结构，从而得出了一种基于层次栈的新的XML数据小枝查询算法。2XML小枝查询XML查询一般分为通过对限定在元素内容和属性值上的取值而进行选择的值查询和通过对文档中标记的元素之间的结构关系进行的结构查询。一般情况下，结构关系查询可以分为两种不同的类型：（1）路径表达式查询；（2）小枝查询。在结构查询中，单斜线和双斜线边符号分别用来表示结点间的父亲-孩子关系和祖先-后代关系。例如查询Q1＝/dblp//inproceedings[/author=’Jon’]是用来匹配所有满足以下条件的路径表达式查询：1）由作者Jon写的；2）二元结构成分（inproceedings/author）是父亲-孩子关系，而（dblp//inproceedings）元素对是祖先-后代关系。小枝查询Q2=/article[./author=’Jon’AND/title=’XML’]是查找由Jon所写的在他们的题目中有’XML’词的文章。前人的许多工作已经对XML小枝查询做了大量研究，文献[1]中的TwigStack算法可以将整棵模式树一起匹配处理层次树，避免保存无用的中间结果，它对于只有祖先-后代边的模式树匹配是最优的。文献[2]在TwigStack算法的基础上使用了XR-Tree索引，可以快速跳过输入序列中的无用结点，但这种索引不能减少连接次数。BLAS[3]中提出的P-label可以直接找出满足连续父亲-孩子边路径的XML结点，从而避免了一部分父亲-孩子边的连接，并减少需处理的结点数。它的缺点是没有利用更多的结构信息。总之，以上算法没有从根本上改进小枝查询的效率。3基于层次树的小枝查询方法3.1XML数据结点编码XML文档具有丰富的内容和灵活的半结构化特征，它能有效的支持复杂查询。XML文档可以表示为每个结点对应相应的元素，每条边表示父亲-孩子关系或祖先-子孙关系的树型结构。图3.1（a）给出了一个简单的XML文档树的实例，图3.1（b）给出了一个简单的树模式查询的实例。数据结点编码对于树模式的查询效率起着非常关键的作用[3,4]，本节后面提出的小枝查询方法所使用的编码方案为EDiezt-P编码。EDiezt-P编码每个结点看作是一个三元组(DocId，StartPos:EndPos，Parent)，为了对问题进行适当的简化从而便于说明，这里我们先讨论单文档查询。图3.1（a）中的结点编码即为EDiezt-P编码。（a）基于EDiezt-P编码的文档树实例（b）小枝查询实例图3.1XML数据结点编码和小枝查询3.2PathStack和TwigStack算法处理小枝查询的不足PathStack算法，考虑路径查询//B/T//S和图3.1中的数据路径B1，B2，T2，B4，T3，S2层次树，S3。整个路径查询的处理是自顶向下遍历文档。首先每个查询结点E关联到对应的栈S[E]，如果一个元素和其父亲栈栈顶中的元素的关系满足查询的轴需要，那么这个元素就被压入栈中。一旦被压入栈的数据结点对应于路径模式查询q的叶结点，则栈链中应该包含了路径模式查询q的整体匹配结果。虽然Bruno等人之后进一步提出了处理整枝查询的TwigStack算法，但对于父亲-孩子关系却不能达到最优[5]。我们需要一种有效的机制来对部分/整体的小枝结果进行编码，从而使得中间结果和查询处理代价达到最小化。一种较好的改进方法，不仅记录下不同的查询结点在文档元素中对应结果的祖先-后代关系，也同时记录下同一个查询结点对应到文档元素中的解的祖先－后代关系，从而使得中间结果最小化。整枝查询时，对于不同的查询结点在文档元素中的解可以像PathStack一样通过明显的边来标识祖先-后代关系。但是对于对应于同一个查询结点的元素，如果通过分解为不同的路径进行查询，那么在文档树中的同一路径上那还可以像PathStack算法一样通过在同一栈中的前后