DVBB：基于Dewey向量的B＋树索引结构连接算法

为解决XML数据库中的结构关系查询问题，本文以Dewey向量为基础，提出了基于Dewey向量的矿树（Dewey Vector Based矿Tree，简称为DVBB）双栈结构连接算法。该算法利用了两个栈，Public Stack和Privat-eStaek，在这两个栈的基础上，利用DVBB索引，能够最大限度地避免那些不能产生连接结果的元素参加连接运算。一系列的实验结果表明，基于DVBB的双栈结构连接算法，无论是对于有效的跳过“祖先”还是“后代”节点，都具有很高的性能。     

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

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

基于扩展前缀编码的左孩子右兄弟结构连接算法

为了更加有效实现XML文档的结构查询,加强结构连接操作的效率,提出一种新结构连接算法.该算法采用扩展的前缀编码方案,在编码中增加了type、index等字段以利于定位树中结点在祖先结点列表或者后裔结点列表中的位置.该算法通过将XML文档树转换成左孩子右兄弟树,并定位树中一个祖先元素的起始点下标和终结点下标来找到该祖先元素的后裔结点列表.算法时间复杂度分析表明了该算法比现有算法的性能更好.     

基于改进B+树索引的结构连接算法

基本的结构连接是XML数据库查询处理的一个核心操作。Stack_Tree_Desc_B＋算法能够有效地跳过不参加连接的后代，但跳过祖先的能力不强。通过对B＋树叶子结点的每一项增加了parent和nextNeighbour指针，该文提出了一种改进算法Stack_Tree_Desc_B＋_pn。改进算法不但具有较强的跳过后代的能力，而且具有较强的跳过祖先的能力。实验表明Stack_Tree_Desc_B＋_pn算法可以有效地减少I/O次数，具有更高的性能。     

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

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

路径分区编码优化小枝查询

有效地存储查询XML文档已经成为当今数据库领域的研究热点。从XML文档的路径统计出发,提出了路径分区存储编码方案,并依此消除了小枝查询的后裔边和通配符。针对这类不含//和*的小枝查询,利用路径分区编码的特性,给出了基于结构约束节点的Twig查询算法,极大地减少了结构连接次数。实验表明,该算法能有效滤除无关元素,提高小枝查询效率。     

一种新的基于索引的多版本XML文件的结构查询法

主要讨论如何突破版本恢复的限制直接对任意版本的XMI、文件进行复杂的结构查询,围绕这个主题,首先介绍了目前XML文档版本管理的一般办法,然后在多版本XML文档的编码方式的基础上提出并实现了一种新的索引机制,进而将结构化连接的查询方法引入XML版本管理的领域,改进了3个经典的结构连接算法,这些算法均能在不恢复版本的前提下直接进行任意版本的结构查询。实验分析比较了它们的查询效能并证明了基于索引的算法能最大程度地避免查询中的冗余。     

基于压缩叶子流的XML Twig查询

在XML数据库中的XML Twig查询是最近查询所关注的焦点,特别是基于整体的算法.很大部分查询算法是通过对XML文档进行编码来实现的,但是,这些算法忽略了文档中双生节点的共有特性.提出了用路径标记来代替已有的编码策略,通过路径标记策略,实现了一种新的基于压缩叶子流的Twig查询算法--CPJoin.不同于先前的算法,CPJoin不需要扫描文档中每一个节点,而是通过把具有相同特征的节点进行压缩来得到一个压缩流,只需要扫描对应查询叶子的压缩流,同时对于已有的两阶段算法,进行重组来减少中间结果的存储.最后,通过真实数据与合成数据上的实验结果来证明基于压缩叶子流的CPJoin算法,提高了Twig查询的性能.     

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

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

一种复杂XML Twig查询处理算法

根据复杂Twig查询的特点,充分利用DTD资源,建立一种基于DTD的索引结构,采用Dewey编码方法对XML文档进行统一编码,并提出一种基于DTD的复杂Twig查询处理算法STwigScan;查询时,通过扫描DTD索引,将复杂Twig查询定位在条件节点以及目标节点上,有效的减少查询处理算法的处理规模;实验证明,STwigScan算法处理规模比较小,查询效率比较高.     

Dynamic interval-based labeling scheme for efficient XML query and update processing

XML data can be represented by a tree or graph structure and XML query processing requires the information of structural relationships among nodes. The basic structural relationships are parent-child and ancestor-descendant, and finding all occurrences of these basic structural relationships in an XML data is clearly a core operation in XML query processing. Several node labeling schemes have been suggested to support the determination of ancestor-descendant or parent-child structural relationships simply by comparing the labels of nodes. However, the previous node labeling schemes have some disadvantages, such as a large number of nodes that need to be relabeled in the case of an insertion of XML data, huge space requirements for node labels, and inefficient processing of structural joins. In this paper, we propose the nested tree structure that eliminates the disadvantages and takes advantage of the previous node labeling schemes. The nested tree structure makes it possible to use the dynamic interval-based labeling scheme, which supports XML data updates with almost no node relabeling as well as efficient structural join processing. Experimental results show that our approach is efficient in handling updates with the interval-based labeling scheme and also significantly improves the performance of the structural join processing compared with recent methods.     

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

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

Indexing and querying XML using extended Dewey labeling scheme

Finding all the occurrences of a tree pattern in an XML database is a core operation for efficient evaluation of XML queries. The Dewey labeling scheme is commonly used to label an XML document to facilitate XML query processing by recording information on the path of an element. In order to improve the efficiency of XML tree pattern matching, we introduce a novel labeling scheme, called extended Dewey, which effectively extends the existing Dewey labeling scheme to combine the types and identifiers of elements in a label, and to avoid the scan of labels for internal query nodes to accelerate query processing (in I/O cost). Based on extended Dewey, we propose a series of holistic XML tree pattern matching algorithms. We first present TJFast to answer an XML twig pattern query. To efficiently answer a generalized XML tree pattern, we then propose GTJFast, an optimization that exploits the non-output nodes. In addition, we propose TJFastTL and GTJFastTL based on the tag + level data partition scheme to further reduce I/O costs by level pruning. Finally, we report our comprehensive experimental results to show that our set of XML tree pattern matching algorithms are superior to existing approaches in terms of the number of elements scanned, the size of intermediate results and query performance.     

Matching twigs in fuzzy XML

A considerable amount of twig pattern matching algorithms have been proposed to holistically process a twig query. Those algorithms mainly focus on twig pattern query with the AND-logic. However, there is often a need to process a twig query with the OR-predicates. Furthermore, the existing algorithms fall short in their ability to support twig query with OR-logic in fuzzy XML. To overcome this limitation, in this paper, we first introduce a novel encoding scheme to represent node information in fuzzy XML. Based on the encoding scheme, we then propose an effective algorithm for matching a twig pattern query with the AND/OR-logic in fuzzy XML. Our approach adopts a compact stack technique to process the complicated twig query consisting of both AND-logic and OR-logic. More importantly, our method eliminates re-scanning unnecessary portions of XML documents and redundant intermediate results. Finally, the experimental results demonstrate the performance advantages of our approach.     

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

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

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

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

Compact Labeling Scheme for XML Ancestor Queries

XML documents are often viewed as trees (basically the parse tree of the document), and queries over such documents typically test for ancestor relationships among tree nodes. Search engines process such queries using an index structure summarizing the ancestor relations. In the index, each document item (tree node) is identified using some logical id (node label), such that, given two labels, the engine can determine the ancestor relationship between the corresponding nodes. The length of the labels is a main factor of the index size. Therefore, reducing this length, even by a constant factor, is a critical issue. In this work we consider the following problem. Given a rooted XML tree T, label the nodes of T in the most compact way such that given the labels of two nodes, one can determine in constant time, by looking at the labels only, whether one node is an ancestor of the other. Labelings currently being used are all variants of the following interval scheme. Number the leaves say from left to right and label each node with a pair consisting of the numbers of its smallest and largest leaf descendants. An ancestor query then amounts to an interval containment test on the labels. The maximum label length using this scheme is 2 log n, where n is the number of nodes in the tree. (All logarithms in this paper are to base 2.) The focus of this work is finding a scheme that works best in practice on real XML data. We suggest an orthogonal prefix-based approach, where the labeling is such that an ancestor query roughly amounts to testing whether one label is a prefix of the other. We present several new labeling schemes based on this approach and analyze their performance both theoretically and empirically.     

RRSi: indexing XML data for proximity twig queries

Twig query pattern matching is a core operation in XML query processing. Indexing XML documents for twig query processing is of fundamental importance to supporting effective information retrieval. In practice, many XML documents on the web are heterogeneous and have their own formats; documents describing relevant information can possess different structures. Therefore some “user-interesting” documents having similar but non-exact structures against a user query are often missed out. In this paper, we propose the RRSi, a novel structural index designed for structure-based query lookup on heterogeneous sources of XML documents supporting proximate query answers. The index avoids the unnecessary processing of structurally irrelevant candidates that might show good content relevance. An optimized version of the index, oRRSi, is also developed to further reduce both space requirements and computational complexity. To our knowledge, these structural indexes are the first to support proximity twig queries on XML documents. The results of our preliminary experiments show that RRSi and oRRSi based query processing significantly outperform previously proposed techniques in XML repositories with structural heterogeneity.

一种采用扩展Dewey编码非归并的小枝模式查询算法

小枝模式查询是XML查询中重要的操作,已经有许多种算法提出,如TwigStack和TJFast算法等,但是他们都是基于归并思想的,不能避免大量的不必要的路径归并.本文提出的TwigWM(Twig Without Merging)算法使用部分栈与链表的结构来实现非归并查询,由于从扩展Dewey编码中能够直接得到祖先元素结点的编码,所以TwigWM算法采用扩展Dewey编码.实验结果表明,TwigWM算法要优于TJFast、Twig2Stack等算法.