XML正则路径表达式的优化技术研究

为提高XML数据的查询效率,本文基于XML数据模型和路径表达式提出一种新的优化方法,方法通过定义及解析一种XML树节点的编码,消除正则路径表达式中的闭包运算和通配符,将正则路径表达式简化为简单路径表达式,确定节点的查询路径,最终改善了闭包运算和通配符的不确定性而引起的查询效率低下问题,并验证了方法的优化性能。

基于XML数据的通用路径表达式的查询

查询重写是数据库研究的一个基本问题,它和查询优化、数据仓库、数据集成、语义缓存等数据库问题密切相关。同时,查询重写也是在关系数据库中存储和查询XML数据的关键问题。由于XML数据是元素嵌套和元素引用的,嵌套层数可以任意,并且模式和数据混合,因此XML的查询会涉及到广义路径表达式(GPE)。文中着重研究了如何解决XML数据的查询重写的方案,把含有广义路径表达式的XML查询语句重写为含有简单路径表达式(SPE)的XML查询语句,再转化为基于关系数据库的SQL语句。

XML数据的路径表达式查询优化技术

路径表达式作为XML数据查询语言的核心部分,关于它的计算方法的研究成果已有很多,然而针对路径表达式本身进行优化的研究却相对较少.提出了两种针对路径表达式的优化策略:路径缩短策略和补路径策略,从而提高了XML路径查询效率.路径缩短策略根据XML文档模式信息,将路径表达式查询长度缩短,从而简化查询本身以降低需要的查询代价;而补路径策略则试图使用代价更小的等价路径表达式来替换原始查询.经过对实验数据的分析,这两种优化策略对于绝大多数路径表达式查询可以应用,并可大幅度地改进路径表达式的查询性能.

路径表达式的并行算法研究

在面向对象数据库系统中，路径表达式是用于定位复杂对象的必要查询设施，因此，优化和并行化路径表达式的执行是实现高性能面向对象数据库系统的关键因素之一．由于ＯＱＬ语言的正交性，在ＳＥＬＥＣＴ，ＦＲＯＭ和（或）ＷＨＥＲＥ子句中均可嵌套路径表达式，而我们将着重讨论ＷＨＥＲＥ子句中路径表达式的并行计算，这种路径表达式也称之为复杂谓词．本文在分析了现有路径表达式的计算方法后，提出了两种新的路径表达式并行计算算法：并行级联式半连接算法（ＰＣＳＪ）和并行正向指针跟踪算法（ＰＦＰＣ）．为了达到一个路径表达式的并行化计算，该表达式可以转换为一个等价的连接表达式，但是我们研究发现，一个路径表达式只要转换为一个级联式半连接表达式即可，该表达式产生与路径表达式等价的结果．由于一个半连接的代价总是少于一个连接操作的代价，因此ＰＣＳＪ算法总是要优于基于连接的并行算法．ＰＦＰＣ算法是集中式正向指针跟踪算法的并行实现，它能充分利用管道并行性和Ｉ／Ｏ并行性．

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

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

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

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

XML结构完整性约束下的路径表达式的最小化

引入了一个XML结构完整性约束体系.这个体系描述了XML文档中节点或路径之间的5种结构关系,包括路径蕴涵、路径同现、路径互斥、必需性包含和排他性包含.给出了这些结构完整性约束的语法和语义定义,并研究了它们在XML查询优化中的作用.基于子路径的概念,提出了有结构完整性约束的路径表达式的最小化算法.该算法以路径蕴涵闭包为工具,不仅可以删除路径表达式的冗余,还可以识别无效路径表达式.实验结果表明了该算法的正确性和有效性.

基于正则路径表达式的XML查询优化技术研究

支持正则路径表达式的查询技术,被认为是半结构化数据模式下的XML查询研究领域中一种颇具有研究价值的XML查询计算方法。本文对基于正则路径表达式的XML查询计算方法及其特点进行了分析,在此基础上详尽地介绍了目前所提出的各种查询优化技术,最后讨论了XML查询优化技术研究中存在的问题以及今后的研究方向。

基于匹配的最小化路径表达式的优化方法

路径表达式的最小化问题,是快速有效地从XML数据源中查询所需信息的重要因素。为了加速路径表达式的处理,在深入分析Chase方法的基础上,提出一种基于匹配的最小化策略。该方法利用了匹配的基本操作来删除冗余分支以便达到优化的目的,在匹配的过程中,按照自上而下的顺序对树中的结点对进行匹配来减少计算的工作量。初步的分析表明,该方法比普遍意义上的消除路径表达式的冗余条件的方法更能有效地提高查询效率。

XML路径表达式中公共子查询的优化技术

研究了XML路径表达式的相关查询算法,提出了基于标注后缀树的XML路径表达式公共子查询的优化算法,通过冗余消除技术来提高路径表达式的查询效率·在REOA测试集上,通过对设计的查询进行测试,分析了基于标注后缀树的XML路径表达式公共子查询的优化算法的性能·实验结果表明,基于标注后缀树的XML路径表达式冗余消除技术可以极大地提高路径表达式的查询效率·

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

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

基于XML路径表达式优化及其查询和过滤计算方法研究

主要对XML路径表达式的优化、查询和过滤算法三个方面进行了研究.运用补路径和缩短路径方法对路径表达式进行优化.通过对路径表达式进行优化来提高查询速度的方法称为路径缩短策略.用简单的路径表达式来代替用户所建立的复杂度表达式的方法称作补路径.用Xpath语言对XML查询进行处理,并对Xpath表达式以及查询处理进行了研究,Xpath查询处理主要通过对XPE-Tree进行匹配以及两次路径连接运算来实现查询处理.XML的过滤系统通过路径表达式来进行模式和内容匹配,在用户信息输入系统之后,生成过滤引擎,过滤引擎与数据流进行匹配,输出用户感兴趣的信息,以此来完成过滤过程.

一个求有向图路径表达式的算法NNRA

任意程序流程图可抽象为一个有向图,求出有向图的路径表达式,就可知道其对应的程序流程图中所有可能的路径。本文将给出一个算法NNRA,它对任意有向图C,通过节点删去法(Nodc by Node Remove)求出G的路径表达式。

路径表达式的构造方法及路径测试

软件测试是软件设计中一个重要阶段，也是保证软件可靠性的重要手段。路径测试是软件测试中一种重要方法，而测试的关键是确定路径数目和设计测试用例。程序路径表达式是路径测试中路径的一种表示方法。本文讨论了利用程序图进行路径测试中的路径表达式的构造方法。

路径表达式的并行正向指针跟踪算法:设计与性能分析

在对象数据库系统中 ,路径表达式是用于定位复杂对象的不可缺少的工具·由于路径表达式的计算非常耗时 ,因此若要提高数据库性能 ,优化和并行计算路径表达式的执行是关键环节·并行正向指针跟踪算法 (PFPC)充分利用了管道并行性和I/O并行性·在基于分布式共享虚拟存储器 (DSVM)的分布式对象数据库FISH系统上完成了实现和测试·对算法的设计进行了详细描述并分析其性能·

基于路径表达式的XML索引查询技术

为减少结构连接操作时对输入数据大小的依赖、在大部分实际情况下提高算法效率,研究了当前结构连接算法产生大量中间结果而导致过多连接次数的问题,提出一种新的基于结构摘要的索引技术。对路径树和XML树分别编码,使用少量预先计算的路径信息。在结构连接时执行交叉操作,该操作由位图在较短时间内实现,并且只返回结点所在路径的位置信息,减少了I/O次数。实验结果表明了其具有较高的查询效率,并且查询时间不依赖于输入数据的规模。

基于模式匹配的路径表达式查询优化

针对目前路径表达式的查询,提出了一种自顶向下基于模式匹配的查询策略.利用延迟结构连接,减少了目前比较费时的结构连接操作次数;另外在自顶向下基于模式匹配的计算过程中,为了尽可能减小中间结果集,引入一个子模式栈来保存已匹配的子模式,并利用子模式的出栈动作判断当前要处理的子模式和子模式栈的栈顶元素之间的关系(相连或者相交) ,从而可以删掉无用的的中间结果,一定程度上优化了空间复杂度.而且,本查询策略不依赖于特定的索引结构.通过对本查询策略进行理论分析和证明,可以看出,自顶向下基于模式匹配的查询方法是有效的.

基于路径表达式的XML查询优化模型研究与设计

现有的XML查询技术效率不高,查询优化的研究成为业界热点和难点问题。本文基于路径表达式进行优化研究,设计了一个查询优化模型XQO,对XML查询过程进行查询解析、逻辑优化、物理优化。通过优化算法模型的设计优化策略,解决了海量XML查询优化存在的一些问题,并从实验结果对优化模型进行验证。

优化XML路径表达式查询的技术

通过对现有的路径表达式查询中几种优化技术的分析研究,提出了在XML语言查询中的一些重要问题,并根据其主要的技术特点提出了自己的观点,旨在提高对XML路径表达式查询技术的优化。

基于如何优化XML路径表达式查询的技术探究

现阶段，XML文档的查询是根据路径表达来导航的，针对XML查询语言而言，对于其数据库查询优化的关键是XML路径表达式。本文作者通过对现有的路径表达式查询中几种优化技术的分析研究，提出了在XML语言查询中的一些重要问题，并根据其主要的技术特点提出了自己的观点，旨在提高对XML路径表达式查询技术的优化。