基于XPath的XML查询优化

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

规则路径表示下XML数据查询的动态规划优化方法

本文介绍了对有规则路径表示的XML数据查询的处理方法，包括传统的处理方法、改进的处理方法及相关的理论基础；然后提出了用动态规划算法对XML数据查询的处理进行优化，包括设计步骤和具体算法；最后对全文内容进行了简要总结。     

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

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

基于F&B索引的XML查询处理算法

XML已成为信息交换和表示的标准.对XML数据的查询将返回满足特定约束的XML节点子集.对于大文件的XML数据的查询处理通常分为两步:1.为该XML数据建立一个索引;2.在索引上完成查询处理无需访问源文档.XML索引为查询处理提供了高效的帮助,其中F&B索引是已知的处理分枝查询最小的索引,但快速创建F&B索引和利用F&B索引完成查询处理的算法却很少有人研究.提出了一种素数序列标记法,这种标记法不仅有助于快速地建立F&B索引,更可以高效地完成F&B索引上的查询处理.此外,还给出了F&B索引上的区间标记法与CCPI的创建过程,这两种编码创建过程无需在建立F&B索引后二次创建,仅需与F&B索引创建过程一起对文档使用SAX解析器分析一次即可得到.这样,可以在F&B索引的区间标记法上使用TwigStack算法执行查询处理,在F&B索引的CCPI标记法上使用关联路径连接算法执行查询处理.还给出了基于素数序列标记法的查询处理算法,即素数整除匹配算法,该算法可以高效地判定某节点是否有某分枝子结构.实验表明基于素数序列标记法的F&B索引创建方法比SAM算法快,在多个数据集F&B索引上素数整除匹配算法优于关联路径连接算法和Twi...     

支持XML查询代数和树模式查询的XQuery系统框架

XQuery语言的高性能实现需要利用XML查询代数提供的查询优化方法,也需要采取高效的树模式整体匹配算法。为了将这两种XML查询处理技术有效地结合在XQuery语言处理系统中,提出了一种通用系统框架来支持XQuery语言的高性能实现。在这个框架内,提供开放式XML数据源连接,并且通过作为中间语言的一种函数式查询计划描述语言FXQL来支持各种查询代数算子和树查询模式的表示,既允许采用各种XML查询代数,又允许采用各种树模式查询算法;进而,通过这种中间层的程序变换可以实现基于各种查询代数的查询重写,并从查询计划中分离出独立的树模式查询计算,使两种查询处理技术适当地统一在同一系统框架中,有效地支持了多种环境下XQuery语言的实现。     

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

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

基于键规则的XML实体抽取方法

XML上实体抽取问题的任务是要从XML数据中抽取出描述现实世界某个物理实体的数据实体.利用XML查询提供实体的表示方法,基于键规则中有关实体的语义信息,给出了求解XML上实体抽取问题的基于键规则的实体抽取(key-based entity extraction,KEE)方法.KEE方法利用查询松弛技术,自动地生成抽取实体的候选查询集合,基于相似性测度,从候选查询中选取适用于抽取实体的查询集合.作为KEE方法的一个具体实现,SharingEE算法利用标准化的查询松弛技术,减少了候选查询中的冗余,利用基于自动机的查询处理技术,在多个候选查询之间共享中间结果,从而减少计算开销.在真实和模拟数据上运行的实验验证了算法的效率和有效性.实验结果表明,KEE方法可以很好地解决实体抽取问题,并可以扩展到大规模数据上.     

一种XML数据流上的马尔可夫剪切分片技术

与传统数据库对XML数据的处理不同,对XML数据流的处理不仅受实时性的约束,还受存储空间的限制.在Hole-Filler模型的基础上,首先利用XML的查询统计信息,定义了路径频率树,在此基础上,提出基于马尔可夫表的XML数据流剪切分片策略及算法,有效地提高了XML片段的利用率,增强了XML片段的内聚性.实验结果表明,基于马尔可夫表的XML剪切算法在剪切时间、查询时间、空间消耗等方面都表现出较好的性能.     

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

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

动态图结构XML数据上的查询处理算法

XML数据可以用图结构模型来表示.在实际应用中,这种图结构的数据会进行动态更新.目前,对于图结构XML数据上的更新操作并没有正式的定义,而且对于动态XML上查询处理的研究还很少.详细地讨论了图结构XML数据上的更新操作,并基于支持更新的可达性编码ICDBS,提出了IGraph算法对动态图结构XML数据上的查询进行处理.实验表明该算法具有很好的效率.     

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

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

Weighted path queries on semistructured databases

Path queries have been extensively used to query semistructured data, such as the Web and XML documents. In this paper we introduce weighted path queries, an extension of path queries enabling several classes of optimization problems (such as the computation of shortest paths) to be easily expressed. Weighted path queries are based on the notion of weighted regular expression, i.e., a regular expression whose symbols are associated to a weight. We characterize the problem of answering weighted path queries and provide an algorithm for computing their answer. We also show how weighted path queries can be effectively embedded into query languages for XML data to express in a simple and compact form several meaningful research problems.     

基于视图的正则路径查询重写

正则路径查询的重写是实现XML查询重写优化的基础。通过比较正则路径视图和正则路径查询的结构信息,分析了两者之间进行映射应满足的条件,描述了正则路径视图到正则路径查询的映射和基于有穷自动机的映射过滤算法,并从理论上阐明了两个算法的重写等价性。借助于此两个算法,能够极大地减少需要求解的映射数目和提高正则路径查询处理的效率。     

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

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

基于扩展路径表达式的XML查询

XML查询问题是当前计算机界研究的热点问题之一，国内外学者提出了众多的模型与算法．其中，日本学者Makoto Murata等提出采用扩展路径表达式来表达查询，并利用hedge自动机和字符串自动机进行XML的查询计算．这种方法与采用路径表达式控制的XML查询相比，克服了后者不能充分利用XML文档有序性的缺点．另外，扩展路径表达式具有较强的表达能力，可以表达任何MSO(一元二阶逻辑)查询．因此，扩展路径表达式已作为XML查询问题研究的主要理论框架之一，但是扩展路径表达式的编写比较困难，表达式也比较复杂，导致算法时间复杂度的提高．在扩展路径表达式中引入通配符，使得扩展路径表达式更加简单灵活；同时在查询的计算过程中提出并应用带截止集的自动机提高计算的时间效率．     

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

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

基于关系数据库有效地实现RPE查询

各种XML查询语言的共同特点就是利用正则路径表达式(RPE)来导航XML文档的查询。本文结合我们提出的一种新的XML数据的关系存储模式，对有效地实现RPE查询的相关研究工作进行了总结，并提出了两个有效地实现包含连接的索引改进归并连接算法。算法采用索引定位技术、短路技术和预侦技术来减少连接代价。因此，不仅能够在当前上下文计算环境下有效地实现包含连接的计算，而且能够大量地避免包含连接中不必要的扫描和搜索。     

基于ＳＱＬ的ＸＭＬ查询的有效实现

讨论了关系数据库中利用ＳＱＬ语句实现ＸＭＬ查询的问题,首先提出了一个利用映射信息（映射图）将带正则路径表达式的ＸＭＬ查询重写为一组简单路径查询的算法,该过程中的一个关键问题的Ｋleene表达式不能直接利用映射图重写,为此,提出了利用路径实例的统计信息来扩展Ｋleene表达式的算法,然后,进一步描述了将简单路径表达式查询重写为ＳＱＬ查询的方法,这些算法在ＸＭＬ－关系系统原型ＶＸＭＬＲ中实现,初步性能研究表明提出了方法是有效的。     

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

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