RPE Query Processing and Optimization Techniques for XML Databases

An extent join to compute path expressions containing parent-children andancestor-descendent operations and two path expression optimization rules, path-shortening andpath-complementing, are presented in this paper. Path-shortening reduces the number of joins byshortening the path while path-complementing optimizes the path execution by using an equivalentcomplementary path expression to compute the original one. Experimental results show that thealgorithms proposed are more efficient than traditional algorithms.

XML查询语言XQuery的研究与实现

XQuery是一种对XML结构的文档和数据进行查询的语言。在对该查询语言规范体系分析、理解和研究的基础上,提出了支持W3C的XQuery语言的查询处理引擎的体系结构。针对各个输入输出和处理模块按数据流的方式逐一进行分析,对整个系统的运行状态做了一个总体的介绍。按照这个体系结构,一个XQuery查询处理引擎已经被实现。

XML更新流的XQuery查询

针对在XML流上执行XQuery查询处理,精确输出查询结果的问题,给出了一种基于XML更新流的解决方案.在XML流中动态地插入更新事件,得到XML更新流,以达到获取连续精确的结果.XQuery查询语言在XPath路径查询的基础上使用FLWOR表达式实现XML数据流的复杂查询.将主Xpath式进行提取,分出绝对路径和相对路径,把有依赖关系的路径进行合并,重写FLWOR表达式,提高XQuery的查询效率.实验结果表明,提出的方法能够提高执行效率,得到精确的查询结果.

一种基于扩展XQuery的XML文档更新方法

在W3C关于XML查询语言的推荐标准XQuery的基础上扩展出一系列更新操作 ,并且设计了XML文档更新过程中的有效性检查机制。

一种基于Schema的XML索引结构

XMLSchema作为一种描述XML文档模式信息即结构信息的标准,对于XML索引的建立及查询效率的提高有着重要的作用。现有的大部分XML索引结构着重研究XML文档的结构查询,而对于XML文档的更新支持却不多,对无效查询也不能作出快速的判断。该文基于已有的XML文档的编码方式,提出了一种基于Schema的XML索引结构,不仅能支持基于有效性验证的动态更新,使得XML文档和XMLSchema保持一致,而且对用户提出的无效的路径查询也能在较短时间内作出判断。

基于XML的工艺信息表达方法研究与实践

XML标准技术的发展和应用,使其成为信息交换与数据共享事实上的标准.分析了CAPP中的信息组成与逻辑关联关系,建立了CAPP系统中工艺信息的通用数据模型.研究了基于XML的工艺信息表达技术,包括DTD语法定义、XML工艺信息查询、XML工艺信息浏览等,并给出了异构工艺信息的XML转换与集成的实现框架.

基于DOM的XML数据库的索引技术研究

XML作为一种数据交换的国际标准 ,已经贯穿于Internet应用的各个领域之中 ,如何快速准确地存储和查询XML数据的数据库技术是一个重要的研究课题 XML索引技术对XML数据库查询处理起着至关重要的作用 提出了基于DOM的XML数据库的索引技术 (路径连接索引、值索引和引用索引 ) ,解决了传统的基于树的遍历的XML数据查询方法性能上的不足 ,并着重对处理含有谓词和引用关系等较复杂的查询路径的不同处理方法进行了对比和分析 还给出了索引空间利用率、查询性能和索引维护代价 3个方面的标准测试结果 。

时态XML索引技术

首先通过讨论时态XML查询数据模型TXQDM,提出了基于结点有效时间的前缀编码方案．以此为基础,引入TXQDM结点间的基于时态连通的等价关系和基于时态包含的拟序关系,建立了时态XML索引数据模型TXIDM,该模型的基本特征足具有二重嵌套的索引框架,适合于TXQDM这种不规则的具有较大随意性的树形结构情形．其次,在TXIDM框架内,讨论了相应时态查询算法,其中包括基于时态的路径查询和值查询,同时,还讨论了时态索引更新算法,其中包括插入和修改算法．最后,对于文中提出的模型TXIDM和时态索引操作算法进行了性能分析且设计了相应模拟实验．实验结果表明,基于TXIDM的时态查询与更新算法是可行的和有效的．

基于时态编码和线序划分的时态XML索引

研究了一种基于时态编码和线序划分的时态XML索引机制.首先,提出一种基于扩展先序编码的时态编码方案,通过该编码可确定结点间的结构关系;其次,在深入分析时间区间关系的基础上引入线序划分的概念,并讨论了获取线序划分的算法;然后,建立了整合路径结构信息和时态约束信息的时态结构摘要,并在此基础上建立了时态XML索引结构——TempSumIndex,同时研究了基于TempSumIndex的时态XML查询和增量式更新算法;最后,对TempSumIndex和现有时态XML索引技术的基本性能进行了详细的实验评估.实验结果表明,TempSumIndex具有更为优越的性能.

基于O-D的XML编码及对信息查询与更新的支持

提出了一种基于区间表示的XML编码方式,设计了相应的关系存储模式,研究了该编码方式对信息查询和信息更新的支持。鉴于XML关系存储下信息更新的困难性,采用基于order-descendan(O-D)的XML编码方式,不仅可以完全支持XPath查询语言的13个查询轴的查询功能,而且通过简单的计算即可有效地支持XML数据的增加和删除,这种简单计算可以在关系存储模式下通过SQL语句方便地实现。

XML压缩方法的比较分析

搜集近几年提出的各种XML压缩方法,比较、分析具有代表性的XML压缩技术。实验表明,XMill拥有出色的压缩率、较少的压缩与解压时间、较低的内存消耗,以及最优的平均压缩性能,但不支持对压缩文档的直接查询。XGRIND与XPRESS的压缩性能不如XMill,却能较好地支持对压缩文档的直接查询。总结XML压缩方法各自的优点和不足,并探讨未来努力的方向。

XCluster:基于聚类支持查询的XML多文档压缩方法

XML已成为各种网络应用中数据存储和数据交换的标准.XML数据管理面临的最大困难在于结构与数据混合存储导致大量数据冗余,这极大地增加了XML数据存储、交换和处理的代价.对XML文档进行压缩可以在一定程度上解决这个问题.但现有XML压缩方法大都仅压缩单文档中的冗余信息.利用XML文档间的相似性,提出一种支持查询的多XML文档压缩存储方法XCluster.XCluster先利用XML有根有序标签树上改进的pq-gram近似距离对XML文档集进行层次聚类;然后合并每个聚类结果子集中文档的结构得到结构代表并进行字典编码压缩;同时合并不同文档内同一标签下的值内容,并根据其数据类型进行相应编码压缩.实验结果表明,在真实和生成的XML多文档数据集上,XCluster比XGrind和XQilla具有更好的压缩效果和查询效率.

利用自动机高效处理XML路径表达式查询

在XML查询处理中,应用于绝大多数XML查询语言中的路径表达式在定位和查询XML数据和数据的结构关系方面具有极强的表达能力,并且由于XML数据的半结构化性,使得XML路径表达式查询的查询处理技术的研究与传统的数据库查询处理技术相比有着全新的特点和挑战.一些目前已有的查询处理技术可以用来处理路径表达式,但是查询处理中产生的大量中间结果导致了这些方法应用在大规模XML文档和复杂的路径表达式查询中时查询效率急剧下降.文中利用自动机技术设计了一个处理XML路径表达式查询的高效方法——SAM.SAM的基本思想是将路径表达式查询转化成一个与之完全等价的自动机,然后将其与从XML文档中抽象出来的模式路径相匹配.文中同时也给出了基于SAM方法的针对路径表达式中"//"操作符计算的有效解决方案.实验证明:SAM是一种非常有效的查询方法,在计算大数据量复杂路径表达式查询时具有非常高的效率,是一种实用的XML路径表达式查询方法.

对XML数据索引的回顾

随着Internet的迅速发展,XML已成为Internet网上数据表示与交换的事实标准,大量应用采纳了XML,例如Web Service中的数据表示和交换、MPEG7中定义的多媒体特征描述子等。日前,查询XML数据需要用XPath,由于查询语句的复杂性,很难找到一种通用的索引结构能有效支持任意查询。因此,在近十年的研究历程中,为了实现XML数据的快速查询,人们提出了大量索引结构。本文就是对已经提出的一些代表性的索引结构进行分类和总结,并指出其优缺点和所能支持的查询。

基于XML的异构数据集成系统的查询处理

讨论了基于XML的Web异构数据源集成系统中的查询处理,并提出了针对全局视图的语义缓存的实现方法,包括查询与缓存入口的匹配算法,网络环境下缓存建立和淘汰算法;最后描述了Gav模式集成方式下的查询分解和优化方法。

面向对象XML数据索引技术

提出了一种面向对象XML数据的索引模式路径仓,路径仓是紧凑地、准确地表示面向对象的XML数据的一棵树,是两级双向树:组级和元素级.在组级上,路径仓提供路径信息、类层次信息,类层次信息存储以索引类为根的类层次子树上特有的元素和属性的对象标识符,而继承的元素和属性的对象标识符存在较高的层次中,可以在查询早期阶段减少大量存储空间;在元素级,它保存从孩子元素到父亲元素的信息,快速存取元素的父亲,提高查询处理效率.不使用全局标志符而是用基于组的引用,可以按组区分不同类型的元素值聚簇相同类型元素值并且索引它们.

基于自动机XML正则路径表达式查询研究

基于自动机正则路径表达式查询技术是半结构化数据模式下XML查询研究领域颇有价值的方法。许多研究方法对含有"//"操作符和"*"通配符复杂正则路径重写都会产生大量中间路径。设计了处理XML正则路径查询高效方法———CSAS,利用对象交换模型(OEM)作为XML数据模型,有限自动机作为查询模型,提出裁剪XMLSchema转化的自动机片断作为重写自动机来重写"//"和"*"符号的重写技术;利用剪枝技术、谓词处理后移策略实现查询优化。实验证明,CSAS方法是一种高效的XML正则路径表达式查询方法。

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

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

基于关系数据库的实时XML数据查询处理

力图用成熟的关系数据库查询机制处理符合DTD的XML文档。提出了一整套数据模型、转换规则和算法描述,可以将XML文档转换为关系元组,从而达到用XML实现基于关系数据库的实时数据一致性查询处理的目的。

有效支持数据更新的XML索引研究

高效的索引是提高XML数据查询效率的关键,目前已经提出了许多XML索引算法,它们大多数都不支持XML数据更新。对CSSU编码进行了改进,提出了一种新的有效支持数据更新的路径索引算法,该索引算法有效支持单支查询和多支查询。