基于结构化联接的多版本XML文档查询处理

结构连接是XML查询处理的核心操作,受到了研究界的关注。高效的算法是高效查询处理的关键。目前已经提出了许多结构连接的算法,但都不支持多版本的XML文档。文章对经典结构连接算法进行了扩充,使之支持多版本的XML文档。     

Native XML数据库的结构连接算法研究

Native XML数据库的快速查询,可以通过基于XML文档编码的结构连接算法实现。在对现有结构连接算法进行综述的前提下,提出一种新的Native XML数据库的结构连接算法——基于深度均匀划分的结构连接算法(DRIAM)。该算法不要求输入数据AList和DList有序或在其节点编码上建有索引,避免了排序和索引所增加的额外开销;不需要输入数据AList和Dlist全部加载到内存中,可以适应不同内存大小限制的情况,并且该算法时间复杂度非常低。     

以目标节点为导向的XML路径查询处理

XML查询语言将复杂路径表达式作为核心内容.为了加速路径表达式处理,基于路径分解和结构连接操作的处理策略需要更深入的研究.以目标节点为导向的XML路径查询处理框架被提了出来.该方法利用了扩展基本操作来减少连接操作的数目.在路径分解和查询计划选择的过程中,利用查询树中的目标节点来避免中间结果的传递.除了分解规则和策略以外,提出了一组扩展的基本操作和实现算法.初步的实验结果显示,该方法具有良好的性能.它为路径查询处理提供了更多的选择.     

XML数据库结构连接算法之分析

结构连接是XML查询处理的核心操作,受到了计算机研究界的高度关注.高效的算法是高效查询处理的关键,目前已经提出许多结构连接的算法.本文介绍了几种典型的算法,并分析了这几种算法的优缺点.     

XML查询的结构连接算法

针对目前多数XML结构连接方法在输入元素集合不存在索引或者无序的情况下,对输入数据临时排序或建立索引代价过高的问题,分析经典的Stack-Tree-Desc算法以及B 树索引的优化算法,提出不局限于外部索引结构的XML查询优化策略并给出算法实现.实验结果表明该算法较Stack-Tree-Desc算法查询效率更高.     

一种适用于顺序XML树的前缀编码方法

在对XML数据模型和XML查询语言中的顺序性进行分析的基础上,提出了一种用于顺序XML树的前缀编码方法,并从唯一性、确定性、动态性、灵活性和简洁性五个方面论证了这种编码的正确性和有效性;同时,运用分层编码的思想解决当XML文档规模增大时编码长度增加的问题。     

一种新的基于划分的结构连接算法

有效的结构连接是XML查询处理的关键。目前,大部分结构连接算法由于需要临时排序、建立索引或存在数据复制及I/O问题,大大降低了执行效率。该文在分析比较现有结构连接算法的基础上,提出了一种新的基于划分的结构连接算法。该算法不需要排序或建立索引,通过栈的机制解决了数据复制问题,并充分考虑内存缓冲提高了I/O性能。实验分析表明该算法具有良好的查询性能。     

利用自动机高效处理XML路径表达式查询

在XML查询处理中,应用于绝大多数XML查询语言中的路径表达式在定位和查询XML数据和数据的结构关系方面具有极强的表达能力,并且由于XML数据的半结构化性,使得XML路径表达式查询的查询处理技术的研究与传统的数据库查询处理技术相比有着全新的特点和挑战.一些目前已有的查询处理技术可以用来处理路径表达式,但是查询处理中产生的大量中间结果导致了这些方法应用在大规模XML文档和复杂的路径表达式查询中时查询效率急剧下降.文中利用自动机技术设计了一个处理XML路径表达式查询的高效方法--SAM.SAM的基本思想是将路径表达式查询转化成一个与之完全等价的自动机,然后将其与从XML文档中抽象出来的模式路径相匹配.文中同时也给出了基于SAM方法的针对路径表达式中"//"操作符计算的有效解决方案.实验证明:SAM是一种非常有效的查询方法,在计算大数据量复杂路径表达式查询时具有非常高的效率,是一种实用的XML路径表达式查询方法.     

基于分片的XML快速结构连接算法

结构连接作为XML查询的重要部分,对查询性能来说起着非常重要的作用.目前有几种结构连接算法已经被提出,例如Stack-Tree、XR-tree.这些算法主要集中在节点之间关系的确定上.与之不同,作者从分片的角度去解决结构连接问题,首先把节点间的关系引申到分片之间的关系,从而得出各分片之间的一些性质,再利用分片间的性质来提高结构连接操作的性能.文中提出了一种基于分片的结构连接算法和两种优化方法,实验表明该算法在性能上要优于Stack-Tree算法和XR-tree算法.设计了一个简单而又高效的索引结构来存储分片结果,实验结果表明该索引结构的维护代价要小于XR-tree的维护代价.     

基于二分法的XML结构连接

在XML数据的查询处理过程中,基于区域划分的连接算法在处理XML数据无序和不存在索引时,是一个效率较高的算法。该文利用区域编码的特点对输入集合进行穷尽的递归划分,在划分的代价下,逐步定位祖先-后代的结构关系。使用二分法进行划分后,再完成结构连接,提高了结构连接的效率,实验表明该算法在XML数据的查询处理上是一个有效的方法。     

基于路径索引与编码模式的路径连接

在各种XML查询语言中普遍采用路径表达式来表示对象间的嵌套和引用关系，路径表达式的求解是查询处理中的一个关键问题．本文提出一种基于路径索引与编码模式的路径连接方法，利用路径索引能够以与路径长度成比例的时间求出对象的后代或祖先的目标集，利用编码模式则可以用常数时间确定对象之间的祖先一后代关系．实验结果表明，本文提出的方法具有较高的效率，当对大量对象进行连接以及当路径的长度、路径上结点的出度或入度较大时，本文提出的方法明显优干自顶向下或自底向上遍历的方法。     

Coding-based Join Algorithms for Structural Queries on Graph-Structured XML Document

In many applications, XML documents need to be modelled as graphs. The query processing of graph-structured XML documents brings new challenges. In this paper, we design a method based on labelling scheme for structural queries processing on graph-structured XML documents. We give each node some labels, the reachability labelling scheme. By extending an interval-based reachability labelling scheme for DAG by Rakesh et al., we design labelling schemes to support the judgements of reachability relationships for general graphs. Based on the labelling schemes, we design graph structural join algorithms to answer the structural queries with only ancestor-descendant relationship efficiently. For the processing of subgraph query, we design a subgraph join algorithm. With efficient data structure, the subgraph join algorithm can process subgraph queries with various structures efficiently. Experimental results show that our algorithms have good performance and scalability. Support by the Key Program of the National Natural Science Foundation of China under Grant No.60533110; the National Grand Fundamental Research 973 Program of China under Grant No. 2006CB303000; the National Natural Science Foundation of China under Grant No. 60773068 and No. 60773063.     

基于扩展区间编码的XML结构连接算法

结构连接的效率直接影响XML查询的性能。经典的Anc-Des-B+算法在判断双亲/孩子关系时跳过双亲节点的后裔(非孩子)节点的能力不强。为此,基于区间编码的思想提出一种改进的编码方法,把每个节点译码为六元组,并增加双亲节点的信息。给出的ZParent算法可以跳过孩子列表中所有不参与连接的元素节点,只需要扫描一次列表P和列表C,即可实现基于该编码的结构连接计算。实验结果表明,该方法具有较好的时间性能。     

Structural Join and Staircase Join Algorithms of Sibling Relationship

The processing of XML queries can result in evaluation of various structural relationships. Efficient algorithms for evaluating ancestor-descendant and parent-child relationships have been proposed. Whereas the problems of evaluating preceding-sibling-following-sibling and preceding-following relationships are still open. In this paper, we studied the structural join and staircase join for sibling relationship. First, the idea of how to filter out and minimize unnecessary reads of elements using parent＇s structural information is introduced, which can be used to accelerate structural joins of parent-child and preceding-sibling-following-sibling relationships. Second, two efficient structural join algorithms of sibling relationship are proposed. These algorithms lead to optimal join performance： nodes that do not participate in the join can be judged beforehand and then skipped using B^＋-tree index. Besides, each element list joined is scanned sequentially once at most. Furthermore, output of join results is sorted in document order. We also discussed the staircase join algorithm for sibling axes. Studies show that, staircase join for sibling axes is close to the structural join for sibling axes and shares the same characteristic of high efficiency. Our experimental results not only demonstrate the effectiveness of our optimizing techniques for sibling axes, but also validate the efficiency of our algorithms. As far as we know, this is the first work addressing this problem specially.     

XML查询结构连接顺序选择算法分析与优化

如今对XML查询的优化是对XML的热点研究方向。其中的结构连接操作是XML数据库查询的主要操作。和关系数据库中的连接运算一样,结构连接顺序的选择是XML数据库查询优化的核心。文中主要通过对XML查询优化中各种选择连接顺序算法的研究,提出了一种优化的算法,在规模较大的XML查询中能够有效缩减搜索空间,提高效率。