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

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

FastMatch:一种高效的XML关键字查询算法

现有的XML关键字查询方法包括两步:确定满足特定语义的节点;构建满足特定条件的子树。这种处理方式需要多次扫描关键字倒排表,效率低下。针对这一问题,提出快速分组方法来减少扫描倒排表次数,进而基于快速分组方法提出FastMatch算法。该算法仅需扫描一次关键字倒排表就能构建满足特定条件的子树,从而提高了查询效率。最后通过实验验证了该方法的高效性。     

一种基于XML文档聚类的XML近似查询算法

提出了一种基于XML文档聚类的XML近似查询算法。给出了基于语义的XML文档间距离的计算方法,结合该语义距离,提出了基于网格的八邻域聚类算法对XML数据库进行聚类划分,进而利用在聚类过程中得到的聚类中心对静态有序选择算法的近似查询评估阶段进行优化,使得不用对XML数据库进行完全遍历就能及时返回满足用户需要的查询结果。最后,在汽车外形智能化设计的实验中表明该算法有效地提高了静态有序选择算法的查询效率。     

XML文档过滤算法YFilter的一种改进技术

采用索引技术,对输入的XML文档建立一个双索引结构来改进YFilter算法,优化XML文档过滤性能。藉助索引结构,该算法超前搜索元素结点在文档中的结构信息,预先排除不能保证得到任何匹配结果的元素结点,以避免大量不必要的查询处理。实验结果显示,当输入的XML文档较大时,该算法有较好的过滤性能。     

一种改进的XML查询重写算法研究

查询重写是数据集成的一个关键问题,它是将用户的查询请求自动重写为直接面向数据源的查询请求。最近Michigan大学和IBM的AImaden研究中心提出了一种新的基于约束的XML查询重写算法,但是该算法没有考虑复杂模式匹配重写问题,使得该算法应用受到限制。在原来的算法重写思想基础上,提出了一种改进的XML查询重写算法,扩大原算法的应用范围,并分析了改进算法的正确性和时间复杂度。     

一种支持通配符查询的XML模式匹配算法

XML查询语言当中,包含通配符*的查询能够方便有效地满足一些特殊查询要求,但在大数据时代下XML文件容量与结构复杂性不断增加,现有支持通配符查询的算法需消耗巨量内存来解析XML,并且在对嵌套通配符处理时需要大量的单路径匹配操作和局部结果的缓存。针对此现状,结合现有经典算法,提出一种新的、能够高效解决小枝模式当中含有通配符*的查询算法-WTwigList。该算法首先对查询模式进行通配符的层次关系处理,减少不必要的通配符匹配,以数据流形式解析XML文件并执行局部的扩展Dewey编码,经过滤操作后得到有序的叶子节点编码列表,在列表中执行匹配操作得到结果;其次在真实和合成数据集上做大量实验,结果表明WTwigList算法与现有算法相比,能够有效提高查询效率,在空间效率上具有一定优势,且能够快速准确地处理查询模式中P C关系。     

WebQL:一种XML和HTML查询语言

本文提出了一种Web查询语言WebQL，能同时处理XML和HTML文档资源，实现了结构化查询，提高了查询的准确度和速度，并给出了用VC 实现的WebQL原型系统．     

一种基于关键字的XML文档查询算法

对XML文档查询的常用方法有两种：一种是使用查询语言;另一种是使用关键字,而使用关键字查询XML文档比使用查询语言更为简单方便。给出了一种使用关键字查询XML文档的索引查找算法。该算法只需要扫描一次关键字对应的编码列,就可以找到需要的编码,提高了查询效率。实验表明该算法是可行的和有效的。     

一种基于区间预留编码的XML关键字查询算法

近年来,随着XML数据的爆炸式增长,对XML关键字查询技术的研究日益受到关注。数据编码是关键字查询的基础,目前主要有2种方式--基于路径的编码及区间编码。区间编码可更好地适应对查询中的XML数据进行动态的更新,因而具有更多的优势。本文研究基于区间编码的关键字查询问题,提出一种新的查询算法。该算法首先根据预留的区间值建立索引,再根据最小范围值对索引进行选择遍历,减少了不必要的比较,达到了提高查询效率的目的。研究发现,预留空间的选择对查询效率有一定的影响。为此,本文设计一种基于节点自身进行区间预留的编码方式（Interval Reservation Based on Node, IRBN）,为节点设置权值,并根据权值进行区间值的设定,形成根据节点自身分配区间的较为均衡的编码。实验表明,IRBN编码是合理的,有较高的查询效率。     

一种改进的基于小枝模式的XML数据库查询算法

XML已经成为Internet上一种普遍的数据交换标准,目前已经出现了多种对XML文档的查询方法。针对小枝模式的XML查询,提出了一种改进的小枝栈算法。该算法将路径栈算法的思想应用到它的主算法中实现了小枝模式查询。与仅使用路径栈算法相比,改进后的小枝栈算法在运行过程中不会产生中间结果,而且提高了找到小枝模式根元素后的查询效率。     

XML数据流中的后兄弟查询算法

针对在XML文档树模型中进行后兄弟节点查询时内存消耗大、匹配效率低等缺陷,提出一种基于XML数据流与栈的后兄弟查询算法。采用SAX解析器与结构连接方法,对XML文档中所有已知节点与后兄弟节点进行精确匹配并输出。结果表明,该算法具有适用范围广、占用系统资源少、匹配效率高等优势。     

面向方面XML查询技术

提出一种有效的方法对XML文档进行描述,解决原有方法中改变XML文档结点时需要对XML文档结点进行重新编码,并改进结构连接查询效率.提出利用面向方面编程方式对XML文档进行定义.在XML文档定义中引入织入,并通过实现对XML Schema的扩充,使XML文档定义具有面向方面编程技术的功能,给出相关结构连接算法.方法避免了由于扩充XML文档而对结点重新编码,减少了修改结点信息的次数,提高文档的重用性.提供了不同织入文档情况下的实验结果,比较不同结构连接算法的性能,实验结果表明该文工作有意义.     

XML数据查询的并行算法

目前已经提出了多种查询XML数据的方法,然而这些传统的方法不能充分利用多处理器和多核心处理器的优势。本文提出了一种XML查询的并行算法,大幅提高了共享存储器多处理器、多核心处理器系统中XML数据的查询效率。     

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

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

基于X-RESTORE查询XML视图

基于转换 XML文档到关系数据库中进行存储与查询的策略 ,研究了 XML视图查询的有效计算问题 .提出了XML 视图查询的合成重写技术 ,它能够消除视图查询中所有在视图结构上的路径导航操作 ,并将视图查询中所有在原文档结构上的路径导航操作以及所有谓词操作下推到视图定义中去 ,与视图定义中的路径导航操作相结合 ,形成统一的在原文档结构上的路径导航操作 .视图合成重写不仅避免了对视图中不出现在最后结果中的中间 XML 片段的构造 ,而且允许将查询中的所有内存密集型或数据密集型操作尽量下推到关系引擎中去执行 ,从而提高 XQuery查询的执行性能     

基于Nearest Pair 的XML 关键词检索算法

随着大量数据以XML格式保存,针对XML文档的关键词检索技术已经成为信息检索和数据库等相关领域的研究热点.以树的杜威编码为基础,分析并证明了XML 关键词检索中核心概念SLCA(smallest lowest commonancestor)的两个重要性质,并在其基础上提出了Nearest Pair 算法.该算法采用二分迭代查找技术寻找最邻近点,将求解中间结果的次数降低了一个量级.实验结果表明,该算法的性能在绝大多数情况下优于现有主流算法.     

双时态XML查询中now语义失真的研究与扩展

本文研究如何有效地查询基于"单属性表示时态信息"的XML文档的时态信息操作,并选择XML功能较为强大的查询语言XQuery进行时态查询扩展.文中先计论如何解决时态数据库中特殊元素now的语义失真的问题,然后对XQuery进行双时态扩展,最后给出扩展后的查询实例.     

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

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

XML/GML非空间数据查询的结构连接算法

为利用Dewey前缀编码索引方案实现对XML/GML文档的编码并消除其缺点,提出一种扩展的Dewey编码方案——Ex-Dewey。在保留Dewey前缀编码优点的同时提出节点插入及删除对已有节点编码值串无影响的更新策略。针对Ex-Dewey编码方案提出一种在XML/GML非空间数据查询时快速确定候选节点间先辈-子孙、父-子关系的结构化连接算法——ED-XQ-SJ。给出算法思想、描述与验证。该算法无须访问实际存储的节点,算法复杂度较低且I/O开销减少。     

一种XML文档模式有效性验证算法

XML Schema作为XML文档模式的定义语言,其语法本身不能保证定义模式的有效性。该文首先分析影响XML文档模式有效性的因素,并构造了XML文档模式图。依据XML实例文档特点,分析了XML文档模式图性质,其中包括递归引用可能导致死锁发生的原因。最后,给出了XML文档模式有效性验证算法,从而弥补了常见验证工具功能的不完整。