XML数据流中祖先-后裔关系匹配算法

在祖先-后裔关系匹配算法中,多数都是首先利用XML解析器将XML文档解析分裂为元素(或属性) 列表进行存储,然后在这些分裂得到的元素(或属性) 列表之间进行祖先-后裔关系的结构连接.该文的算法SSD不需要事先将源XML文档分裂为元素(或属性) 列表进行存储,而是直接将源XML文档作为输入,采用SAX来产生XML数据流,然后基于XML数据流实现祖先-后裔关系匹配.通过分析可知,该算法适用面广,仅需要对源XML文档进行一次扫描,占用系统资源少,且具有很高的匹配效率.     

Native XML数据库的文档编码机制研究

Native XML数据库快速查询的实现,可以采用基于XML文档编码的结构连接算法。而结构连接算法的实现需要对XML文档进行编码,以便于快速判断XML文档树结点之间的祖先后裔关系。在对现有编码机制进行综述的前提下,提出一种新的XML文档编码机制——前缀整除编码（PDIV）机制。该机制编码形式简单,只需要一个正整数即可充分表示结点在XML文档树中的位置信息;可以实现祖先后裔关系的快速查询;支持XML文档的更新操作;编码长度较短,编码长度约为o（ln（n））。     

基于区间编码的XML索引结构的有效结构连接

该文给出了一个XML树数据模型的形式化定义．将编码方案、逆序列表和路径索引的思想相结合，提出了一种改进的XML数据的索引结构；给出了两个实现双亲／孩子关系和拥有关系的结构连接算法，它们最多只需要对参与连接的两个列表分别进行一次扫描，并且能够根据双亲结构信息等利用Bt树索引尽可能多地跳过不需要参与连接的元素结点．实验结果表明，该文给出的基于XML索引结构实现双亲／孩子关系和拥有关系的结构连接算法是高效的、健壮的．     

sTwig——一种基于流的XML小枝匹配算法

结构连接是处理XML查询的主要方法,目前已经有一系列有效的结构连接算法被提出.但是已经存在的结构连接算法,在处理仅含有祖先后裔边的小枝模式查询方面,会访问不必要的元素节点,提出了一种新的小枝匹配算法sTwig.sTwig算法基于"流"的思想,实现简单,不需要归并操作,且避免了对不必要元素节点的访问,TwigNME算法是目前在处理仅含有祖先后裔边的小枝查询方面表现最优的结构连接算法,通过实验,将sTwig算法与TwigNME算法进行了比较,实验结果表明sTwig算法在时间和空间上都存在优势.     

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

为有效实现XML文档查询,减少查询时结构连接的扫描代价,分析了基于归并思想的结构连接算法查询效率低的原因,充分利用XML数据的结构特点,提出了能够直接判断结点间结构关系的扩展Dewey编码,基于该编码的改进的Stack-Tree-Desc结构连接算法.应用扩展的Dewey编码,缩短了编码长度,降低了空间成本.改进的Stack-Tree-Desc算法引入二分查找快速跳过不需要参与连接的结点,减少了AList和DList列表中被扫描的结点数量,提高了查询效率.理论分析和实验结果表明了该编码方案以及结构连接算法的准确性和有效性.     

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

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

一种高效的XMLQuery基本模式匹配算法

有效的支持结构连接是实现数据库系统XML文件查询的关键。结构连接是用来查找所有满足基本的结构关系的元素对,即指定XML树型结构文件元素对的关系(父亲-孩子和祖先-子孙的关系)。文中在分析常见的XMLQuery模式匹配算法(Stack-Tree连接算法)的基础上,提出一种改进的Stack-Tree连接算法将Stack-Tree-Desc算法和Stack-Tree-Anc算法统一;并且采用动态分配存储空间方法,比Stack-Tree-Anc大大节省了存储空间。最后给出了改进的Stack-Tree连接算法分析和试验结果。     

eXist数据库结构连接算法的改进和实现

为了进一步提高eXist数据库的查询效率,针对数据库现有的数据存储特点和查询策略,提出一种快速定位的结构连接算法FL-Stack。算法采用栈缓存已遍历过的但仍可能与尚未遍历的后代结点匹配的祖先结点,并对能预先判断不可能满足结构连接匹配的祖先或后代结点,提出相应方法实现快速定位,以批量跳过这类结点。与现有算法必须逐个扫描祖先后代结点序列相比,这种快速定位的结构连接算法避免了逐个扫描带来的多次重复无意义的比较,可大大提高结构连接效率。     

对双亲／孩子结构连接算法的研究与改进

结合区间编码和结点模型映射方法提出一种用于关系数据库的扩展存储模式.通过按广度优先遍历XML树实现对双亲/孩子关系结构连接算法的改进.改进后的算法降低了内存空间的开销,缩小了列表的扫描范围,明显提高了查找匹配速度,达到了查询优化的目的.     

一种基于有序对的小枝模式匹配算法

随着半结构化的数据在信息交换中越来越重要,近年来,在XML数据库中,研究工作者提出了很多匹配小枝查询的算法.这些算法对仅含祖先后裔边的查询是很有效的,但是当查询中同时含祖先后裔和父子边时,以前算法仍可能产生大量中间结果,尤其是输入和输出的规模很大时.为避免中间结果的产生,提出了一种新的算法OPTwig,它是基于有序对的,通过查询树和文档树中结点有序对的匹配来进行查询,且不需要进行归并操作.结果表明,该算法优于以前算法.     

有效支持XML结构化连接的索引——CATI

结构化连接的效率直接影响着XML查询的性能,目前对XML的结构化连接大多都是基于编码的方法.介绍了一种全新的有效支持XML结构化连接的树索引CATI(compact ancestor tree index)CATI的基本思想是,对于给定的一个祖先后代查询(A-D查询)或Twig查询,遍历XML文档,找出所有的祖先A的实例,用以建立CATI的主干;对于每个A实例,找出它的直接后代D的实例链接在它的后面.因为经典的结构连接算法Stack-Tree算法效率较高且使用较广,因此应用基于CATI的结构连接算法和基于Stack-Tree的结构连接算法就A-D查询和Twig查询做了大量实验.实验结果表明,基于CATI的结构化连接在一般查询情况下性能明显优于基于Stack-Tree的结构化连接.     

一种具有多模态索引结构的XML查询算法

将编码方案、路径索引和名字外延思想相结合,提出一种针对XML数据检索的多模态索引结构.它既可支持结构连接计算,用以判断任意结点之间的子孙后代关系,也可支持基于名字外延的路径连接算法,用以判断任意结点之间的父子关系,同时可支持包含拥有关系的小枝查询;进而给出基于该结构的外延连接算法,使得对于长度为n的Xpath绝对路径查询,最多只需n/2-1次外延连接.实验结果表明,本文提出的索引结构可有效提高查询处理性能.     

一种基于结构索引的XML模式匹配方法

XML文档采用了树型的数据模型,对其查询通常是用带有选择谓词的模式树在XML数据中进行匹配.因此,找出XML文档中所有符合模式树结构的元素集,是XML查询处理的核心操作.本文提出了结构索引JoinGuide,并在此基础上提出了一种新的XML模式匹配方法.它使用JoinGuide来对模式树进行预匹配,这样在XML文档上查询时可以利用索引上的匹配结果来忽略部分连接谓词和不必要的候选XML元素序列.本文还提出了三种具体算法来利用索引匹配结果进行进一步的查询.实验结果表明本文中的模式树匹配方法优于以往的匹配方法,并且索引所需的空间很小.     

一种基于XML文档关键字检索的结构索引

XML数据索引对其检索效率有较大的影响。在深入分析现有XMI、结构索引之后,结合XML文档特点,提出了一种基于关键字检索的结构索引--LSS(Level Structure Summary) . LSS采用了把具有相同标签路径的结点进行合并的策略,具有高效判断结点之间同构异构关系的能力。实现了LSS索引生成算法CSCAN,并在LSS索引的基础上设计了XML关键字检索算法LSSearch。该算法依据LSS索引,将各个关键字的原始倒排表集合分拆成不同类型的子集合,最后在所有子集合上进行查询。实验结果表明,LSS可以帮助减少XML文档中关键字倒排表的规模,提高检索效率。     

一种新的XML文档编码机制

XML查询中正则路径表达式的实现，需要快速判断元素间父子关系或祖先一后代关系。目前，基于树遍历的XML文档编码是一种主流的方法，但父子关系的判断需要在编码之外附加辅助的措施，部分实现不支持文档更新，提出一种新的编码方法，能够在常数复杂度的时间内实现两个元素间父子关系、祖先一后代关系的判断，计算祖先一后代结点间的辈数差异，并支持文档更新功能。     

Indexing graph-structured XML data for efficient structural join operation

Structural join has been established as a primitive technique for matching the binary containment pattern, specifically the parent–child and ancestor–descendant relationship, on the tree XML data. While current indexing approaches and evaluation algorithms proposed for the structural join operation assume the tree-structured data model, the presence of reference links in XML documents may render the underlying model a graph instead. In the more general category of semi-structured data, of which XML is an example, the data model is also usually supposed to be of graph structure. In this paper, we present an indexing approach and corresponding evaluation algorithms for efficiently performing the structural join operation on graph-structured data. Our approach encodes the structural containment relationship of a graph on multiple nested tree-structured layers, probably with the exception of the last one. With each tree-structured layer indexed with the inverted technique, the structural join operation on a graph can therefore be accomplished through recursively performing structural joins on nested layer trees. Our extensive experiments on both benchmark and synthetic XML data indicate that our proposed approach has good potential to perform significantly better than existing ones in term of both the I/O and CPU cost.     

基于复杂模式索引的XML查询优化*

分析了XML模式与XML文档之间的关系以及XML查询的特点,提出了一种基于复杂模式索引的XML查询优化方法.该方法对XML模式中的节点建立索引,查询时考虑XML模式中带有环的情况.首先对查询树进行去除重复元素的预处理,并将查询树分解成主路径和分支路径;然后利用索引查找潜在目标节点的XML模式编号;最后在XML文档中对对应节点进行筛选,找到目标节点.该方法可以减少连接操作的次数,提高查询操作的效率,能处理较复杂的XML模式.     

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.