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

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

处理XML文档查询的高效结构连接方法

结构索引和倒排表在处理XML文档查询时，有不足之处。该文提出了一种结合结构索引、倒排表的策略、连接路径表达式的查询算法，有效地降低了实际执行的代价，提高了查询速度。     

D（k，l）-索引：一种自适应的XML数据索引

XML已成为网络上数据表示和交换的一种实际标准。为促进XML的数据和半结构化数据的查询，几种结构概要被提出。它们可以直接从数据中得出，并以索引的方式来估计在XML数据上的路径表达式。在本文中，综合几种索引提出新型数据结构D(k，l)索引。其参数k，l刻画了节点向上和向下的相似度。它考虑各个节点向上路径和向下路径的相似关系，因此它可以有效地支持路径表达式，尤其支持带分支路径表达式的查询，同时，它也可以根据查询情况的变化来动态地改变索引结构，使索引结构更适合当前的查询要求，实验表明我们的方法具有很好的效率和效果。     

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

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

XML数据库的索引技术研究

目前XML已经成为Internet以及电子商务中进行数据表示和数据交换事实上的标准.本文研究了XML的两种索引技术即结点记录类索引、结构摘要索引.深入分析了XML数据的区间编码技术,利用编码技术使孩子与双亲节点,兄弟节点可以通过编码值获取,降低节点对树型结构的依赖程度,使得查询在执行表达式时不必遍历整个结构树;同时引入基于后缀树的索引构造技术,尽可能地合并相同标签路径的节点.所以,周游一条路径即可得到该标签路径下的所有节点,避免了相同标签路径的重复访问的缺陷.     

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

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

一种基于完整性约束的路径表达式的查询优化策略

利用路径表达式导航 XML 查询是 XML 查询语言的共同特点。目前对 XML 路径表达式的计算有两种方法:一种是基于树遍历的方法,一种是路径连接方法。在路径连接方法中路径表达式的计算效率很大程度上依赖于路径表达式的长度。在对 XML 模式反映的完整性约束研究的基础上,本文提出了排他性包含约束的概念;给出了利用排他性包含约束缩短路径表达式的策略和算法,从而降低了路径连接的代价。通过分析比较,这种路径缩短策略是有效可行的。     

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

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

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

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

XQuery在XML流上查询的结构化连接

通过分析XQuery查询与XPath查询的区别与联系,定义了扩展的基本XSIEQ机E-XSIEQ,它是一种被索引化、基于栈的自动机。提出用变量表来收集XPath查询结果,并将这些中间结果组织成原子表集合,结果构造时能够根据原子表元组之间的上下文关系,对原子表集合快速地进行连接。描述了XQuery查询过程中的结构化连接算法,给出了结果构造的时间性能分析。     

基于模式的XML路径表达式查询处理技术

为了有效地利用文档类型定义(DTD)中的路径信息、减少结构连接次数,使用二元前缀码对DTD的元素或属性编码,并将DTD编码引入到XML节点编码中.在此基础上,将路径表达式查询分解成若干查询片段,利用二元前缀码的"位"操作高效地计算每个查询片段的结果,最后使用结构连接将这些查询结果组合起来.实验结果表明该方法是正确的和高效的.     

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

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

基于路径索引的密集邻域图数据查询方法研究

随着社交网络、生物信息以及web挖掘等应用的不断发展,图结构数据的存储和查询处理越来越得到重视。但是,针对顶点邻域非常密集的场合,如何提高此类顶点的查询效率,现有的研究相对较少。论文在分析了顶点密集领域数据的特点后,提出了一种对顶点密集邻域建立路径索引的策略,有效地解决了此类查询的效率。首先分析顶点密集的邻域的查询模式,并在这些模式上建立路径索引,然后采用B 树方法,对路径索引的存储、更新和查找方法进行了设计实现,最后,采用图数据库NEO4J为基础,对路径索引存储空间和查询性能进行了测试,测试表明,虽然路径索引会占用存储空间,但是能够提高特定的查询处理的性能。     

一种支持高效检索的双重索引策略*

从信息检索角度出发,提出一种高效的索引,在结构索引中集成了倒排文档,可同时查询XML结构部分和关键词.双重索引策略很好地解决了基于路径表达查询效率低的问题.     

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

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

A multiple-depth structural index for branching query

XML structural index, which acts as a schema, plays an important role in XML query optimization and formulation. To provide a reasonable structural index for branching path query under space constraint, we propose an adaptive index of multiple local branching depths and multiple local bisimilarities, which is constructed by maximizing marginal gain for given query load. It cannot only give good support to branching path queries but also have much smaller size compared with that of same sort of index. Detailed experiments have shown that the index is effective and efficient for XML branching path query.     

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

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

Index structures for matching XML twigs using relational query processors

Various index structures have been proposed to speed up the evaluation of XML path expressions. However, existing XML path indices suffer from at least one of three limitations: they focus only on indexing the structure (relying on a separate index for node content), they are useful only for simple path expressions such as root-to-leaf paths, or they cannot be tightly integrated with a relational query processor. Moreover, there is no unified framework to compare these index structures. In this paper, we present a framework defining a family of index structures that includes most existing XML path indices. We also propose two novel index structures in this family, with different space–time tradeoffs, that are effective for the evaluation of XML branching path expressions (i.e., twigs) with value conditions. We also show how this family of index structures can be implemented using the access methods of the underlying relational database system. Finally, we present an experimental evaluation that shows the performance tradeoff between index space and matching time. The experimental results show that our novel indices achieve orders of magnitude improvement in performance for evaluating twig queries, albeit at a higher space cost, over the use of previously proposed XML path indices that can be tightly integrated with a relational query processor.