XML流上的XQuery前缀共享查询

如何在XML流上高效地执行大量复杂XQuery查询是当今研究的热点之一。在数据选择分发等应用中,还希望在解析流的同时尽早地输出查询结果。为此,本文将XQuery查询的路径导航和结果构造两个阶段分别运行于服务器、客户机两端。导航阶段针对XQuery查询定义了扩展的基本XSIEQ机E-XSIEQ（Extended　XML　Stream　Quervwith　Immediate　Evaluation）,它是一种被索引化、基于栈的自动机。在EXSIEQ机上设计应用了TreeBuf（TreeBuffer）算法,它是一种树型提升缓冲的查询算法,算法使用了前缀共享计算的技术,能高效处理XQuery查询,而且能优化XPath查询。实验证明了TreeBuf算法的高效性。     

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

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

XQuery在XML流上查询的结构化连接

通过分析XQuery查询与XPath查询的区别与联系,定义了扩展的基本XSIEQ机E-XSIEQ,它是一种被索引化、基于栈的自动机。提出用变量表来收集XPath查询结果,并将这些中间结果组织成原子表集合,结果构造时能够根据原子表元组之间的上下文关系,对原子表集合快速地进行连接。描述了XQuery查询过程中的结构化连接算法,给出了结果构造的时间性能分析。     

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

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

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

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

XSIEQ-一种立即计算的XML流查询系统

XSIEQ是一种立即计算谓词并即时输出的XML流查询系统．它利用前缀共享的方法由多个XPath式构造一个NFA，并对NFA状态进行分类和添加索引．使得在运行时能快速确定谓词计算和数据缓存等的时机，XSIEQ还提供在运行时惰性地构造DFA进行查询．陈述了XSIEQ的查询机制以及多重匹配问题的解决方案，最后给出了XSIEQ的两种自动机和YFilter的查询性能对比及分析．     

带谓词的XPath查询的即时处理

介绍了一种立即计算谓词并即时输出的XML流数据查询系统XSIEQ。XSIEQ采用修改了的下推自动机技术,对多个XPath式按前缀共享的方式构造NFA,并对NFA状态进行类型标记和添加索引;从而在运行时能快速确定谓词计算和数据缓存等动作的时机,实现了即时处理;最后给出了XSIEQ和YFilter的查询性能对比及分析。     

一种基于图归约的XPath高性能流数据查询方法

作为网络数据交换和数据共享的标准,XML数据越来越多地用于表示应用系统的流数据。然而,受制于流数据处理有限空间开销等特征,如何高效地实现这种查询成为值得探讨的问题。与传统的基于自动机或层次栈方法不同,文中提出了一种基于图归约的XML查询自动机(GRAT),采用一种图结构来表示针对不同XML流元素的子查询任务之间的关系,通过图的归约变化来实现XPath查询。实验结果表明,基于GRAT的查询算法能够高效地完成复杂的XML查询,流数据处理的吞吐量达到了较高水平。     

M2:一种有效的XPath求值方法

XPath求值性能极大关系到XML应用程序的整体性能.提出的M2(Matrix Match)方法基于节点关系矩阵查询.根据XML区间编码构建关系矩阵,通过查询原语序列的执行实现XPath表达式求值.M2的导航式特点使得XPath的各种查询语义容易实现,包括反向轴操作和以谓词表达的分支查询.对应相同XML数据的关系矩阵可...     

带Order子句的XQuery在XML流上的查询实现

随着XML的广泛应用,使得作为XML文档查询语言的XQuery成为人们研究的热点问题.将复杂XQuery在XML数据流上的查询应用于服务器/客户端模式来满足高效、实时查询的要求,所实现的XQuery查询原型系统XSIEQ支持嵌套、order子句的多关键字排序等.一次典型的XQuery查询过程可分为XPath查询、查询后处理两个阶段,本文着重描述查询后处理过程,最后给出了XSIEQ和Qizx在查询后处理时间性能上的对比及分析.     

面向XPath执行的XML数据流压缩方法

由于XML(extensible markup language)本身是自描述的,所以XML数据流中存在大量冗余的结构信息.如何压缩XML数据流,使得在减少网络传输代价的同时有效支持压缩数据流上的查询处理,成为一个新的研究领域.目前已有的XML数据压缩技术,都需要扫描数据多遍,或者不支持数据流之上的实时查询处理.提出了一种XML数据流的压缩技术XSC(XML stream compression),实时完成XML数据流的压缩和解压缩,XSC动态构建XML元素事件序列字典并输出相关索引,能够根据XML数据流所遵从的DTD,产生XML元素事件序列图,在压缩扫描之前,产生更加合理的结构序列编码.压缩的XML数据流能够直接解压缩用于XPath的执行.实验表明,在XML数据流环境中,XSC在数据压缩率和压缩时间上要优于传统算法.同时,在压缩数据之上查询的执行代价是可以接受的.     

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

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

Schema-aware XPath filtering on XML document streams

The XML stream filtering is gaining widespread attention from the research community in recent years. There have been many efforts to improve the performance of the XML filtering system by utilizing XML schema information. In this paper, we design and implement an XML stream filtering system, SFilter, which uses DTD or XML schema information for improving the performance. We propose the simplification and two kinds of optimization, one is static and the other is dynamic optimization. The Simplification and static optimization transform the XPath queries to make automata as an index structure for the filtering. The dynamic optimization are done in runtime at the filtering time. We developed five kinds of static optimization and two kinds of dynamic optimization. We present the novel filtering algorithm for the resulting transformed XPath queries and runtime optimizing. The experimental result shows that our system filters the XML streams efficiently.