一种XML文档索引及查询处理方式

本文首先论述了传统XML路径模式索引方式，在此基础上提出面向元素的XML文档索引方式和相关算法，以及使用扩展的后序遍历序号进行元素节点标识的方案，并给出了该索引方式和元素节点标识方案下规则路径表达式查询和树型模式查询处理的方法，最后说明该方式在效率上优于传统索引方式下规则路径表达式查询和树型模式查询处理。     

一种新的基于Dewey编码的XML路径索引

建立高效的索引来快速定位满足要求的节点是提高XML数据查询效率的一个必要手段.文中以降低复杂度和提高查询效率为目标,以基于路径的XML索引原理为基础,提出了一种新型的基于Dewey编码的索引结构RTL-Index.RTL-Index通过对文档节点编码来表示结构信息,利用前缀路径匹配操作完成结构查询,支持含通配符" 和后代轴"//"的查询以及兄弟节点无序的模式树的查询.仿真实验结果表明RTL-Index索引具有较低的时间和空间复杂度,解决了XML文档分支路径查找问题,是一种较为有效的XML索引结构.     

一种高效的XML路径查询索引

XML文档的查询索引是当前研究的热点。提出一种高效的XML路径查询索引KDXI,首先对XML文档进行编码,然后建立结构索引并对结构索引进行编码。研究了基于KDXI索引结构的半结构连接算法和路径查询处理过程。通过KDXI索引机制,可以有效执行一般的路径查询语句,并避免冗余的结构连接操作。实验证明了KDXI索引机制的优越性。     

基于DTD的XML索引查询技术

针对XML文档索引查询中非法路径查询响应时问过长的问题,提出一种利用DTD模式进行预处理的索引方法。建立索引DWBI,采用新的基十区域编码方式,有效地支持祖先一后代判断。查询时利用DTD模式对查询进行预处理,再查询带有DTD信息的XML索引树,从而提高查询的效率。     

基于素数编码Schema的XML索引结构的研究

针对XML文档查询,提出了一种基于素数编码Schema的XML索引技术.该索引是对XML模式采用素数编码,对XML文档采用Li-Moon编码,这样在建立XML文档的节点索引时,也可对该节点的路径信息进行记录.在节点类索引的基础上,记录路径信息,既可以很好地支持正则路径表达式,同时又避免了节点类索引在处理长路径表达式时可能造成高昂的连接操作代价.实验结果表明,该索引的性能总体上要好于传统的节点类索引.     

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

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

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

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

改进XISS索引技术的仿真研究

研究了数据库查询优化问题,而XISS索引是XML数据库索引中支持正则路径表达式的典型代表。XISS索引对于长查询路径表达式,要产生大量中间结果,连接操作代价十分高,加大了查询的时间和空间复杂度,导致查询的效率和准确率低。为了提高XML数据库查询效率和准确率,提出一种改进的XISS索引技术。首先引入DTD模式信息,简化编码方式;然后对节点索引结构进行改进,减少中间结果的连接次数,使得查询时间与路径长度无关,提高了查询效率和准确率。最后通过实验对改进前后的XISS索引进行仿真。结果表明,改进的XISS索引缩短了建立索引的时间,加快了查询响应的速度,提高了XML数据库查询的效率和准确率。     

一种改进XML模式树查询最小化算法

对XML模式树查询进行最小化查询优化,是左右XML数据查询处理性能的关键因素。对模式树查询最小化技术进行了研究,结合XML结构索引提出了一种改进的XML模式树查询最小化算法。该算法有效地解决了普遍意义上的语法层次优化中不能有效删除冗余节点的缺陷,从而提高了查询效率。实验结果表明该算法是正确的和有效的。     

一种基于DTD的XML索引方法

路径查询是XML查询的一个主要特征,现已提出了多种XML索引方法．DTD的结构信息对于XML索引的建立及查询效率的提高很重要,但现有的大部分索引方法没有利用DTD这一有效资源,提出一种利用DTD的XML索引方法——DBXI(DTD-based XML indexing),该方法采用了新的编码方法,可使路径查询具备如下特征：对于由N个元素／属性组成的具有1个谓词约束的路径表达式,DBXI处理每个XML文档仅需0次或1次元素／属性结点集的结构连接操作;对于在XML文档中不存在匹配结构的路径查询,DBXI能够在比现有的XML索引方法较短的时间内给出无查询结果的判断．实验表明,与Lore,SphinX和XISS等索引方法相比,DBXI能够缩短路径查询的响应时间．     

SXBP：基于Pri—order编码的XML文档存储方法

随着XML技术的发展，如何利用现有的数据库技术存储和查询XML文档已成为XML数据管理领域研究的热点问题。本文介绍了一种新的文档编码方法，以及基于这种编码方式提出了一种新的XML文档存储方法。方法按照文档中结点类型将XML文档树型结构分解为结点，分别存储到对应的关系表中，这种方法能够将任意结构的文档存储到一个固定的关系模式中。同时为了便于实现数据的查询，将文档中出现的简单路径模式也存储为一个表。这种新的文档存储方法能够有效地支持文档的查询操作，并能根据结点的编码信息实现原XML文档的正确恢复。最后，对本文提出的存储方法和恢复算法进行了实验验证。     

概率XML文件树结点概率的查询算法

概率XML文件是概率数据的网络数据交换和表示标准,元素取值及其概率的查询与计算是概率XML文件的重要研究内容.概率XML文件树是一种有效的概率XML文件的数据模型,定义了概率XML文件树的基本路径和扩展路径,提出了根据可能世界原理将概率XML文件树分解为普通子XML树的集合的算法,根据路径分析原理将概率XML文件树分解为子概率XML树的集合的算法和相应的查询与计算结点及结点集合概率的算法,并通过实验进行了比较分析.实验结果表明:这两种方法是有效的;与前一种方法比较,后一种方法适合较大的概率XML文件树、结点及结点集合的概率的查询,计算过程较简单.     

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.     

An encoding scheme based on fractional number for querying and updating XML data

In order to facilitate the XML query processing, several labeling schemes have been proposed to directly determine the structural relationships between two arbitrary XML nodes without accessing the original XML documents. However, the existing XML labeling schemes have to re-label the pre-existing nodes or re-calculate the label values when a new node is inserted into the XML document during an update process. In this paper, we devise a novel encoding scheme based on the fractional number to encode the labels of the XML nodes. Moreover, we propose a mapping method to convert our proposed fractional number based encoding scheme to bit string based encoding scheme with the intention to minimize the label size and save the storage space. By applying our proposed bit string encoding scheme to the range-based labeling scheme and the prefix labeling scheme, the process of re-labeling the pre-existing nodes can be avoided when nodes are inserted as leaf nodes and sibling nodes without affecting the order of XML nodes. In addition, we propose an algorithm to control the increment of label size when new nodes are inserted frequently at a fix place of an XML tree. Experimental results show that our proposed bit string encoding scheme provides efficient support to the process of XML updating without sacrificing the query performance when it is applied to the range-based labeling schemes.     

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.     

CSBTT:一种基于二叉树遍历的XML文档编码模式

XML文档数据编码模式是XML文档查询处理的基础, 好的文档编码模式有利于提高文档的查询效率. 为了解决XML数据查询效率低、支持动态更新等问题. 本文在二叉树遍历的编码基础上, 引入二叉树的三叉链表存储结构对XML文档结点进行编码. 该编码利用自然数作为编码序号, 因此编码长度较短; 引入结点双亲指针, 方便结点之间结构关系的判定, 结点采用三叉树链式存储, 方便文档的更新操作.     

用后缀树构造XML路径字典加快路径查询评价速度

后缀树的重要性可以为多年来学术界对它总是有新的发现而印证．它的结构简单，但可以在线性的时间里解决许多复杂的问题，被大量的使用在字符串及树的模式匹配中，对于XML标准，有很多基于关系库和对象库的索引技术和查询方案被提出来，我们试图给出一种基于后缀树进行路径导航的查询机制：用后缀树构造XML路径字典加速路径查询评价速度，我们提出可以在线地建立一个trie树的后缀树，讨论了XML路径字典中的后缀树建树算法，阐述了整个索引方案和查询机制，并探讨了包括RPE在内的它所支持的各种查询操作，XML路径字典被用于加快路径查询的评价速度．     

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

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

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.