基于下推自动机的XML数据流递归查询研究

针对具有子孙轴(//)和谓词([])结构特征的XPath对具有不同递归深度的XML数据流进行递归查询处理问题,提出了基于下推自动机技术的处理方法,通过将XPath各类置步转化成相对应的处理模块,由算法将各类处理模块组合起来,建立了自上而下的树状查询模型.由于查询过程中将会发生多重匹配,从而会产生大量的匹配模式,该模型通过有效的匹配策略和缓存操作,对匹配模式进行保存及检验,成功地实现XML数据流递归查询.实验结果表明,该算法在性能上要优于传统方法.     

基于自动机理论的XML查询重写研究

研究了基于自动机理论的XML查询重写问题,尤其针对局部查询重写技术作了深入研究.通过实例对其有效性进行了合理的分析.     

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

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

基于树自动机的XPath在XML数据流上的高效执行

如何在XML数据流上高效地执行大量的XPath查询成为数据流应用中一个迫切需要解决的关键问题.目前提出的算法或者不能完全支持XPath的常规特性,或者在算法的执行效率和空间代价上不能满足数据流应用的要求.提出了基于树自动机的XEBT机来解决这个问题.与传统方法相比,XEBT机具备如下特征:首先,XEBT机基于表达能力丰富的树自动机,无须附加中间状态,或保存中间结果,就能处理支持{[]}操作符的XPath;其次,XEBT机支持多种优化策略,包括基于DTD的XPath查询自动机的构造;在空间代价有限增加的情况下采用局部确定化减少并发执行的状态;采用自上而下和自下而上相结合的查询处理策略.实验结果表明,提出的方法能够支持复杂的XPath查询,在执行效率和空间代价方面优于传统算法.     

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

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

基于树自动机的XML过滤技术

为了提高XML数据流的查询匹配效率,基于XML过滤技术研究提出了一种基于树自动机的XML过滤技术XTAFilter.该技术利用hash表来存储谓词,并对多个查询表达式XPath通过共享路径构建树自动机,减少了匹配的时间,提高了查询匹配的效率,同时降低系统运行时的活动状态.搭建仿真平台对技术进行验证,仿真实验结果表明,XTAFilter 技术能有效地提高XML数据流的匹配效率,提高了系统的实用性.     

XML数据流基于组着色的XPath查询模型

提出了一种新的XML数据流XPath查询模型GBRender,该模型通过组着色序列来直接处理元素,具有较高的处理效率与较强的适应性.     

一种基于流索引的XML数据流的Xpath查询算法

XML数据流查询过程中,核心操作是父子、祖孙节点的匹配问题.解决这一问题的有效途径是根据查询表达式构造非确定状态自动机,顺序处理解析后的节点,在这个过程中大量与查询无关的节点也参与了匹配.通过对XML数据流添加流索引,在执行查询时,直接跳过与查询不匹配的元素及其子树节点,提高了查询效率.     

XML数据流上的有序XPath查询处理

XML数据流上的查询处理是最近研究工作的一个热点,如何高效地处理XML数据流上的XPath查询是其中的核心问题.之前的相关工作主要考虑了无序XPath查询处理的情况,而在股票信息监控、新闻信息订阅等很多的XML数据流应用中常常需要对有序XPath查询进行有效的支持.对于有序XPath查询的处理,之前的方法需要将查询进行分解,然后通过连接将分解后的子查询得到的中间结果合并.针对有序XPath查询自身的特点,提出了在查询树上引入顺序和位置标记,记录查询结点之间的顺序关系,并在此基础上提出了一种创新的XML数据流上的XPath查询处理算法OrderedXP.相比之前的工作,OrderedXP能够大量地减少缓存的中间结果数目,而且不需要分解原来的查询,避免了额外的连接操作.详细的实验数据验证了OrderedXP能够显著地提高有序XPath查询在XML数据流上的执行效率.     

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

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

XML流数据查询结果的缓存管理

提出一种系统地处理XML数据流的返回结果集的方法.在该方法中,用户对数据的兴趣用XQuery表示,能够处理递归文档以及同时处理多个查询;通过运行时栈驱动的基于二进制的前缀编码,在运行时确定结果集中节点之间的关系,避免了大量结果集之间的连接操作,能够有效减少内存耗费,提高处理性能.     

Scalable Filtering of Multiple Generalized-Tree-Pattern Queries over XML Streams

An XML publish/subscribe system needs to filter a large number of queries over XML streams. Most existing systems only consider filtering the simple XPath statements. In this paper, we focus on filtering of the more complex Generalized-Tree-Pattern (GTP) queries. Our filtering mechanism is based on a novel Tree-of-Path (TOP) encoding scheme, which compactly represents the path matches for the entire document. First, we show that the TOP encodings can be efficiently produced via a shared bottom-up path matching. Second, with the aid of this TOP encoding, we can 1) achieve polynomial time and space complexity for post processing, 2) avoid redundant predicate evaluations, 3) allow an efficient duplicate-free and merge join-based algorithm for merging multiple encoded path matches and 4) simplify the processing of GTP queries. Overall our approach maximizes the sharing opportunity across queries by exploiting the suffix as well as prefix sharing. At the same time, our TOP encodings allow efficient post processing for GTP queries. Extensive performance studies show that our GFilter solution not only achieves significantly better filtering performance than state-of-the-art algorithms, but also is capable of efficiently filtering the more complex GTP queries.     

使用DTD优化XML数据流上的XPath查询

如何在XML数据流上高效地执行XPath查询,是XML数据流管理的关键问题。DTD结构信息对提高XML查询效率有很大帮助,已有的大部分算法没有利用这一资源。提出了一种使用DTD进行XML数据流查询处理的方法,具有以下特征:利用树自动机表示XPath;通过XPath树自动机与DTD树匹配,预先标识不匹配查询结构的DTD节点;给出一种利用DTD的XML流索引方法DBXSI;执行查询时,根据流索引信息直接跳过某些与查询不匹配的节点及子树。实验结果表明:该方法可有效支持Xpath查询,效率优于传统算法。     

数据流上的预测聚集查询处理算法

实时数据流未来趋势的预测具有重要的实际应用意义.例如,在环境监测传感器网络中,通过对感知数据流进行预测聚集查询,观察者可以预测网络覆盖的区域在未来一段时间内的平均温度和湿度,以确定是否会发生异常事件.目前的研究工作多数集中在数据流上当前数据的查询,数据流上预测查询的研究工作还很少.采用多元线性回归方法,给出了数据流上的聚集值预测模型,提出了一种数据流预测聚集查询处理方法.当预测失败的次数大于预先给定的阈值时,给出了一种预测模型自动调整策略,以降低预测误差.还提出了滑动窗口的更新周期、数据流的流速对预测精度影响的数学模型.理论分析与实验结果表明,提出的预测聚集查询处理算法具有较高的性能,并且能够返回满足用户精度要求的预测查询结果.在实验中,采用TPC-H国际标准测试数据和TAO(tropical atmosphere ocean)测量的海洋表面空气温度数据来构造数据流.     

基于Hole-Filler模型的XML数据流上的SLCA算法

与传统数据库对XML数据的处理不同,对XML数据流的处理不仅受实时性的约束,还受存储空间的限制.在XML片段无序传送的广播模型中,考虑在XML数据流上进行高效的关键字查询,进而首次提出近似SLCA算法.SLCA算法利用结构Hash表和LCA表对关键字进行匹配并计算SLCA,从而避免冗余操作.同时,SLCA算法可以对匹配结果立即输出而不必等到数据流传输结束.实验结果表明,基于Hole-Filler模型的XML数据流上的SLCA算法在节省时间和空间开销方面均表现出较好的性能.     

基于概率模型的数据流预测查询算法

挖掘在线数据流的变化趋势并预测未来时间窗口上的可能值,可以为许多时间敏感的应用提供重要决策支持.通过将数量可能无限的流数据元素映射到离散的且数量有限的流数据状态空间,不断变化的流数据变化趋势可以模拟成连续的流数据状态变化的过程,进而在很小的时间与空间代价下,数据流状态变迁的趋势动态存储在状态变迁图中.通过分析状态变迁图中的流数据变迁的统计规律,数据流上未来时刻的可能值可以应用马尔可夫模型在线连续预测.     

一种数据流上的多Top-k查询资源共享技术研究

随着传感器网络、大规模实时监控等相关技术的发展和应用,出现了大量的流式数据,如何对这些数据进行查询分析是目前研究的热点.Top-k查询作为一种基础聚集查询,在很多领域起着重要作用.主要研究对于具有不同时间窗口的多个Top-k查询,如何提高资源共享的性能.提出了一种资源共享策略RS-Tpk,充分利用了Top-k查询本身的特点,通过在不同切片间进行数据传递,提高切片间资源共享的范围,降低了计算时间.详细的实验和理论分析证明了该方法的有效性.     

数据流上的连续预测聚集查询

提出了一种数据流上未来值的连续查询,称为连续预测查询．采用数理统计的方法给出了带有COUNT聚集函数的连续预测聚集查询实现算法．通过采用TPC-H标准测试数据和随机生成的模拟数据进行了实验．理论和实验结果表明,给出的带有COUNT的连续预测聚集查询实现算法具有很高的性能和精度．