基于代价的XML路径索引构建

处理路径表达式是XML查询技术中的难点和热点．在本实验室提出的XML路径表达式索引-结构化映射的基础上．为了降低构建索引所需的空间开销，本文提出了构建路径索引的代价模型，并设计了基于给定查询负载，有选择地构建路径索引的相应算法，为给定查询负载自动选择近最优索引模式（NOIS）．本文还提出了当查询效率发生变化时，系统对索引模式进行自适应调整的策略．实验研究表明：使用本文方法，系统可在不影响路径表达式处理效率的前提下，大大降低路径索引的空间开销，取得查询收益和空间开销的较佳权衡．     

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

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

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

针对XML文档查询,提出了一种基于素数编码Schema的XML索引技术.该索引是对XML模式采用素数编码,对XML文档采用Li-Moon编码,这样在建立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能够缩短路径查询的响应时间．     

基于优化过滤策略的XML数据查询处理

如何高效地处理XML查询，是目前研究的热点。由于当前方法存在过多扫描无用节点引起效率下降的问题，本文设计了一种XML数据的二级索引结构，基于该结构给出路径查询处理算法。首先，本文对XML模式中每个节点按路径类型进行分类编码，然后把每个节点按该编码进行聚类存储。在查询时，就可以先根据模式信息和查询信息得到目标节点的编码，然后只需将二级索引中这些编码对应的部分载入内存，进行过滤操作。这样就不必扫描整个索引，提高CPU和IO效率。本文还对二级索引结构进行扩展，使本文的过滤索引能方便应用在有分支结构的查询上。实验结果表明，本文的XML数据过滤算法效率优于基于Bit vector的过滤算法，并且索引结构所需要的存储空间也小于Bitvector索引。     

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

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

一种基于结构特征的XML数据查询方法

针对XML数据特有的树型结构模式，提出了一种将树型结构的XML数据和查询语句转化为特定格式的字符串，基于串匹配原理对结构复杂的XML数据进行查询的方法，避免了传统的基于路径的查询方式所必需的路径之间的连接（join）操作，从而提高查询效率。利用本文提出的编码方式，可以建立关于XML数据结构和数据内容舍为一体的索引。实验显示，本文使用的针对XML数据查询的方法比传统的基于连接操作的数据查询方式高效，且本方法具有良好的扩展性。     

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

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

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

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

一种基于路径分块索引的XML查询方法

针对XML的相对路径查询及引用路径查询问题，提出了一种面向XML数据的路径分块索引KI。探讨了KI索引构造方法、索引节点分裂算法和相关查询处理的算法，并用VC++实现，利用Shakespeare和Xorder数据集进行了XML查询测试，实验结果表明，提出的KI索引能有效地提高XML查询效率。     

基于XML索引技术的有效外延连接

首先给出了XML文档树、元素外延和名字路径等的形式化定义.接着,将编码方案、路径索引和名字外延的思想相结合,提出了一种改进的XML数据的索引结构(类型索引集、名字索引集和外延索引),解决了基于传统索引技术的XML数据查询方法性能上的不足,它既可以有效地支持结构连接的计算以快速地判断任意结点之间的子孙后代关系,也可以有效地支持基于名字外延的路径连接算法以快速地判断任意结点之间的父子关系,然后还可以快速地支持对包含拥有关系的小枝查询;进而给出了基于该索引结构的外延连接算法,并着重对其处理含有父子关系和拥有关系等较复杂的XPath查询路径的不同处理过程进行了对比和分析,使得对于一条长度为n的XPath绝对路径查询,最多只需要n/z-1次外延连接,且能够根据双亲结构信息等利用外延索引尽可能跳过不需要参与连接的结点,实验结果表明,提出的新的索引结构可以有效地提高查询处理的性能.     

优化索引XML数据研究

介绍了文档树中嵌入编码机制的思想和扩展编码方法，提出了采用改进的扩展编码方式来对XML文档进行编码，并使用改进的B 树构造算法构建索引树，以期提高存储空间利用率并减少B 树节点分裂次数；最后，在理论和实验的基础上分析了数据查询的执行效率。     

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.     

面向XML文档检索的索引技术

XML文档的查询索引是当前研究的热点.该文探讨XML文档的索引技术,包括索引结构的设计等问题,给出了一个高效的XML索引方法,采用独特的编码方法,对XML文档及其遵循的DTD同时建立索引,有效支持内容和结构的双重检索;该方法结合了区间编码、倒排表和路径索引的思想,利用DTD结构信息来提高查询的效率.实验结果表明,本文提出的方法可以有效地降低建立XML数据索引的代价,能够缩短查询的响应时间.     

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

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

基于DTD的XML索引查询技术

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

基于互关联后继树的XML索引技术

提出了一种新的根树节点编码方法——基于叶序区间的节点编码(LOINS)．编码方法只需对根树后序遍历一次即可完成,能实现常数时间内对任意两个树节点间前后代关系的判断．同时,结合互关联后继树模型(IRST)的标引性、可压缩性等特点,提出基于IRST的根树索引模型Ist3aRTI-Ⅰ,及对该模型空间优化的索引模型IstBaRTI-Ⅱ．IsBaRTI-Ⅰ,Ⅱ采用树节点名称(标签)及其在根树(XML文档树)中的出现计数索引节点间的父子关系和节点叶序区间编码,实现索引结构和节点编码的相互统一,IsBaRTI-Ⅰ,Ⅱ索引建立时间、空间代价小,可快速查询满足XPath表达式在XML文档树中的节点序列和路径．     

基于XPath的XML查询优化

随着XML作为Internet上数据表示和交换的标准,如何高效地进行XML数据的查询己经变得越来越重要,许多XML查询语言也随之出现。这些查询语言虽然种类繁多,但都有个共同特征:使用基于XPath数据模型下规则路径表示来查询XML数据。研究表明,当前的关系数据库技术在处理规则路径表示的查询时通常效率不高。文章在介绍了传统的基于遍历树的方法的基础上重点讨论了基于路径分解的查询处理算法,并对选择连接顺序算法提出了基于动态规划思想的改进。     

基于XPath的XML查询优化

随着XML作为Internet上数据表示和交换的标准,如何高效地进行XML数据的查询己经变得越来越重要,许多XML查询语言也随之出现。这些查询语言虽然种类繁多,但都有个共同特征：使用基于XPath数据模型下规则路径表示来查询XML数据。研究表明,当前的关系数据库技术在处理规则路径表示的查询时通常效率不高。 文章在介绍了传统的基于遍历树的方法的基础上重点讨论了基于路径分解的查询处理算法,并对选择连接顺序算法提出了基于动态规划思想的改进,     

XML数据扩展前序编码的更新方法

大部分XML查询技术都是基于某种对XML树的编码方法.对XML树的编码,是指按照某种规则对XML树的每一个结点分配唯一的编码,目的是通过任意两个结点的编码,能够直接判断两个结点之间是否具有祖先后代关系.最常用的编码方法是区域编码方法(region based numbering scheme).然而,XML数据也会面临插入删除等更新问题.数据一旦更新,区域编码也要作相应的调整,才能保证基于这个编码的各种索引和查询算法的正确性.在编码的更新方面,目前研究得还不多.主要研究区域编码的更新问题,采用预留编码空间的方法,针对不同特征的XML数据和应用环境提出了一整套预留算法和编码更新算法,并做了大量的实验,检验这些算法的有效性.