TwigStar——快速处理XML Twig查询中含通配符*的算法

XMLTwig查询可以表示为一棵带标签结点的查询树,它支持对XML文档进行带有复杂谓词的结构或内容查询.整体(holistic)Twig查询算法已经被公认为XML查询处理的核心算法.很多学者提出了大量基于整体处理的XML Twig查询算法.但是目前已有的算法都只适合于Twig查询中不包含通配符*的情况.而当Twig查询中包含通配符*时,一种简单而直接处理的方法就是,把被查询文档中的所有结点元素都读到内存,把这些元素都看做通配符*所对应的元素,然后按照已有的算法进行查询处理.显然这种方法是不合理的,它会增加大量I/O开销.因此提出了一种有效地支持通配符*的查询处理算法.通过建立索引,它可以很好地处理含通配符*的查询,从而可以避免不必要的I/O开销.最后通过实验证明,算法要明显好于已有的算法.     

包含OR,AND和NOT谓词的复杂Twig查询处理算法

针对同时包含OR,AND和NOT谓词的复杂XMLTwig模式查询,提出一种标准的查询模式和对应的整体匹配算法AllTwigList.查询时将复杂Twig模式当作一个整体进行处理,避免因对复杂Twig模式进行分解而导致大量中间结果的产生和对同一查询节点的重复处理,有效减少查询处理规模.基于不同数据集的实验表明,使用AllTwigList算法可以很大程度提高查询处理的性能.     

基于压缩叶子流的XML Twig查询

在XML数据库中的XML Twig查询是最近查询所关注的焦点,特别是基于整体的算法.很大部分查询算法是通过对XML文档进行编码来实现的,但是,这些算法忽略了文档中双生节点的共有特性.提出了用路径标记来代替已有的编码策略,通过路径标记策略,实现了一种新的基于压缩叶子流的Twig查询算法--CPJoin.不同于先前的算法,CPJoin不需要扫描文档中每一个节点,而是通过把具有相同特征的节点进行压缩来得到一个压缩流,只需要扫描对应查询叶子的压缩流,同时对于已有的两阶段算法,进行重组来减少中间结果的存储.最后,通过真实数据与合成数据上的实验结果来证明基于压缩叶子流的CPJoin算法,提高了Twig查询的性能.     

F-Index:一种加速Twig查询处理的扁平结构索引

如何快速、有效地处理twig形式的查询是XML查询处理的关键问题,通过过滤与查询无关的元素可以减少查询中需要处理的元素数目,从而提高查询的执行效率.提出一种扁平结构索引F-Index,能够快速过滤所有与查询无关的索引结点,进而过滤掉查询无关的元素,在处理深度嵌套的复杂结构XML文档时具有很大的优势.提出一种新的查询算法,能够有效处理过滤后剩余元素的匹配问题.基于不同数据集的实验表明,使用F-Index进行过滤可以极大地提高查询处理的性能.     

有效的非完全结构XML查询

讨论了有意义的非完全结构XMI查询(NFS)结果的定义,提出了一种易于扩展的基于模式和实体的有意义判断模型--PE模型;基于PE模型,设计了具体的等价模式和等价查询项判断方法,提出了PE索引和I2P倒排索引,设计了一种有效的NFS查询算法来处理有意义的判断以及路径查询和关键字查询.实验表明,文中方法的查询质量和效率要优于XSEarch系统和Timber系统.     

针对XML流数据的复杂Twig Pattern查询处理

XML流数据处理在研究领域引起了研究者的广泛兴趣.针对XML流数据的、具有嵌套AND/OR谓词的复杂Twig Pattern查询处理,提出一种新方法.为了提高查询处理性能,将所有Twig Pattern合并为一个共享前缀的查询树,其中,AND/OR谓词被表示为单独的抽象语法树,因而能够以文档顺序、单遍地处理复杂Twig Pattern的匹配,并避免了YFilter中对嵌套谓词进行后置处理所产生的中间结果.实验结果表明,该方法能够有效改善Twig Pattern的处理性能,尤其是在处理大文档的情况下.基于已     

一种支持高效XML 路径查询的自适应结构索引

提出了一种新的自适应结构索引:AS-Index(adaptive structural index),能够克服现有静态索引和自适应索引的缺陷,具备高效的查询和调整性能.AS-Index 建立在F&B-Index 的基础之上,其索引结构包括F&B-Index,Query-Table 和Part-Table.Query-Table 能够记录频繁查询,避免了查询过程中的冗余操作.并且,在Query-Table 的基础上提出了自底向上的查询处理过程,能够充分利用现有的频繁查询高效地回答非频繁查询.Part-Table 用于优化包含祖先后裔边的查询,进一步提高了查询性能.现有的自适应结构索引的调整粒度是XML 元素节点,调整过程往往需要遍历整个文档.而AS-Index 是基于F&B-Index 节点的增量调整,其过程是局部的,高效的,并且能够支持复杂分支查询的调整.实验结果表明,AS-Index 在查询和调整性能上优于现有的XML 结构索引.同时,相比于现有的自适应结构索引,AS-Index 针对大规模文档具有更加优良的可扩展性.     

一种支持通用θ-Join的并行查询处理机制

并行查询处理,特别是并行连接查询处理技术是并行数据库中的关键技术.然而,目前的并行查询处理方法尚存在着一些局限性,如绝大多数的并行Join算法依赖于Hash方法对数据进行分治,因此只能支持等值Join等查询类型.为了解决这一问题,提出了一种基于伪半连接的通用θ-Join查询处理算法,并给出了基于查询语法树及并行执行计划的并行数据库通用查询处理方法.在此基础上,实现了一个并行分布式数据库原型系统PD-DBMS,实验结果表明,此方法提供了良好的并行查询处理性能.     

基于结构化联接的多版本XML文档查询处理

结构连接是XML查询处理的核心操作,受到了研究界的关注。高效的算法是高效查询处理的关键。目前已经提出了许多结构连接的算法,但都不支持多版本的XML文档。文章对经典结构连接算法进行了扩充,使之支持多版本的XML文档。     

一种GML文档的Twig模式查询算法

GML文档是XML技术在GIS方面的应用,成为空间数据在Internet上的实际表示、传输和交换的标准。目前,GML文档的查询是GIS领域的研究热点。对这一问题,研究了GML文档的数据特点和结构特点,设计了一种新的索引结构--GB树,GB树是专门针对GML文档中空间数据节点的索引结构。将XML Twig模式查询思想引入GML文档查询,借助GB树的索引特点,提出了GML文档的Twig模式查询算法--GMLTwigStackGB。GMLTwigStackGB算法保留了XML文档Twig模式查询算法的优势和特点,具有完整的空间查询功能。测试实验表明,该算法能够高效地满足GML文档上的各种数据查询。     

一种预测性连续时空区域查询处理方法

预测性连续时空区域查询在用户指定的时间范围期间持续地返回给定未来查询时间范围期间将出现在查询区域的移动对象。论文提出了一种预测性连续时空区域查询处理方法,设计了支持连续查询处理的两种索引结构。移动对象索引用于记录移动对象不断更新的位置信息,它用于支持查询的首次处理。连续查询索引结构用于记录所有查询结果可能受到移动对象位置变化影响的连续查询,它用于支持连续查询处理。实验表明,论文提出的方法能够有效地提高处理大量连续查询的效率。     

并行数据库复杂关系查询优化的一种方法

查询优化不仅是顺序数据库系统的重要组成部分，也是并行数据库的重要组成部分，而多个Ｊｏｉｎ操作的复杂关系数据库的查询经又是目前研究的 主要课题。     

一种支持对象代理数据库高效查询处理的索引结构

文中为对象代理数据库提出了一种新的索引结构--路径导航索引(Path Navigation Index,PNI),能够克服路径表达式计算开销大的缺点,使对象代理数据库跨类查询与代理对象查询具备高效的查询性能.PNI索引建立在代理层次的路径实例之上,包括Path-Instance-Table,Identity-Index和Attribute-Index 3个组成部分.Path-Instance-Table能够物化存储路径实例,避免查询处理过程中冗余的对象导航遍历.Identity-Index与Attribute-Index用于对路径实例进行关联检索,能够避免对象导航过程中的条件判断.通过实验分析了影响路径表达式计算的不同因素,实验结果表明,利用PNI索引计算路径表达式的方法在多数情况下性能要优于现有计算方法,尤其适用于带谓词的路径表达式计算.     

一种中文数据库查询语言的优化处理方法

本文介绍一种中文数据库查询语言的优化处理方法。该方法能将用户输入的查询条件自动分解成ＳＱＬ语言中条件子句ＷＨＥＲＥ和分类条件子句ＨＡＶＩＮＧ，以提高查询效率。     

DM XML加速线性Twig查询的实现

每一个复杂的Twig查询都由线性Twig查询构成,有效地处理线性Twig查询显得非常重要。DM XML系统以国产DM5.6关系数据库为平台,融合结构映射和模型映射,实现独特的路径分区编码方案来存储XML数据。在系统中,线性Twig查询解析后,形成线性Twig查询的路径集,而该集合中的每一个路径可被唯一变换为关系数据库中整型主键的范围查询。实验结果显示,路径分区编码方案能加速线性Twig查询,它将为高效实现复杂Twig查询奠定基础。     

一种高效的XML多分支路径查询算法

目前XML单路径查询和简单的分支路径查询已经得到了较好的解决,但如何高效地实现XML多分支路径查询还没有很好的方法。提出一种高效的XML多分支查询算法MBPQ。算法MBPQ首先对XML文档和被查询的多分支路径结点分别按照各自不同的方式进行编码,并将被查询的多分支路径拆分成单路径,最后将单路径查询匹配成多分支查询结果。在单路径查询结果匹配过程中,算法MBPQ利用栈控制匹配过程,按照查询树从左到右、自底向上的顺序匹配具有共同祖先结点的单路径查询结果,从而提高匹配效率。实验表明,与现有的XML多分支查询一般算法相比,算法MBPQ的查询效率高。     

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

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

不确定图数据库中高效查询处理

近年来,在多种领域中产生的大量数据都可以自然地建模为图结构,比如蛋白质交互网络、社会网络等.测量手段的不准确性以及数据本身的性质导致不确定性在很多图数据中普遍存在.文中研究不确定图数据库中的高效查询处理方法.首先给出一种数据模型来表示图的不确定性.鉴于对用户提交的查询图通常会产生大量匹配结果,高效得到概率最大的k个匹配常常更具有现实意义.因此文中形式化提出概率top-k子图匹配查询的问题.为了解决提出的查询问题,以附带概率信息的邻居子图为基础,设计了一种有效的索引结构.另外,提出一种高效的基于索引的查询处理方法.该查询处理方法的核心是一个基于搜索树的匹配算法,其中运用了一种概率剪枝技术来提高性能.实验结果表明,所提出方法具有良好的效率和可扩展性.     

Native XML数据库的结构连接算法研究

Native XML数据库的快速查询,可以通过基于XML文档编码的结构连接算法实现。在对现有结构连接算法进行综述的前提下,提出一种新的Native XML数据库的结构连接算法——基于深度均匀划分的结构连接算法(DRIAM)。该算法不要求输入数据AList和DList有序或在其节点编码上建有索引,避免了排序和索引所增加的额外开销;不需要输入数据AList和Dlist全部加载到内存中,可以适应不同内存大小限制的情况,并且该算法时间复杂度非常低。     

一种基于扩展不完全Kripke结构的三值逻辑模型检测方法

多值模型检测是解决形式化验证中状态爆炸问题的一种重要方法,三值模型检测是多值模型检测的基础,其中如何检验不确定状态的真值是一难点。针对不确定状态检验,提出了一种模型检测方法,首先对不完全Kripke结构PKS进行了扩展,然后在扩展后的模型上给出了检测不确定状态真值的方法,最后给出了基于扩展不完全Kripke结构的三值逻辑模型检测算法。与已有的三值逻辑模型检测算法相比,该算法降低了算法复杂度,完善了对于不确定或不一致信息的处理,从而增强了三值逻辑模型检测的实用性。