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

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

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

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

利用DTD模式优化基于路径的XML的查询

XML作为一种数据的表示形式,正在数据库及网络中数据传输的领域被广泛使用,提高对它查询的速度也成为一个我们研究的方向,最近提出了利用DTD来提高查询效率的方法,基于这一思想,为了更高效地利用DTD,这篇文章提出了一种更高效利用DTD的方法,首先介绍了扫描DTD树的结果,即真路径的存储方式,然后给出了扫描DTD树的算法,我们还给出了怎样利用真路径对文档树进行扫描的算法,最后给出了例子,并分析了我们提高效率的原理.     

DTD上的lazyDFA XML数据流查询优化算法

针对XML数据流上的XPath查询处理问题,基于自动机技术构造的lazyDFA查询处理器是一种有效的解决方法。为了提高lazyDFA的查询处理效率,提出了利用DTD的语义信息和结构信息对lazyDFA进行优化的算法。实验结果表明,优化算法可以有效的加快lazyDFA的查询速度,降低内存消耗。     

基于DTD节点自动机的XML模式验证方法

XML已经成为Web环境中数据表示和交换的标准。XML的模式验证在XML的使用中地位重要。DTD作为模式描述的一种方法,应用广泛,但使用DTD描述的模式不能正常表示同构的XML数据。文章扩展了DTD并提出了一种基于自动机的模式验证方法,将扩展的DTD中每个元素转换为一个自动机,将XML文档编码为字符串,并将字符串作为自动机的输入进行验证,可以有效地验证同构的XML。     

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

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

基于形式语言理论的Active XML重写算法

主动XML（AXML）是指一部分数据直接给出,另一部分数据以Web Services调用方式隐含给出XML文档。研究AXML重写问题,给出AXML重写系统的形式化定义,提出一个基于树自动机理论的AXML文档重写算法,并证明该算法的正确性及有效性。实验数据表明,基于树自动机的AXML文档交换方法具有良好的执行效率。     

基于倒排表与B+树的联合索引技术

为提高XML文档的查询效率,提出一种基于倒排表与B+树的联合索引技术。DTD结构索引和内容索引采用倒排表作为索引单位,XML文档索引使用B+树作为索引基本组织。在DTD结构索引的结点编码中设置标识信息,便于确定需要查询的文档。通过建立DTD结构索引、XML文档索引和内容索引,实现混合型XML文档的查询。理论分析与实验结果表明,该技术具有较小的空间开销和较高的查询效率。     

XML DTD数据映射方案的研究

XML已经成为网上数据交互的标准。所有的XML都应遵循两种标准之一：DTD或XML Schema。本文首先分析了XML DTD中元素、属性和操作符,其次给出了XML DTD简化规划,最后讨论了XML DTD到关系模式的映射规则和映射步骤。     

OreintXA:一种有效的XQuery查询代数

XQuery是XML查询语言的推荐标准.现有的XQuery处理策略有两种方法,一种是基于核心语法一次一结点的方法,另一种是基于查询代数的一次一集合的方法.单独使用这两种方法都不能很好地处理XQuery查询.一方面,基于核心语法树的方法效率低,而且很难优化,而现有基于代数的方法又不能很好地满足XQuery的过程化查询语言的特性.描述了一个有效的XQuery代数系统--OrientXA.它是在总结现有的基于代数的XQuery查询工作、分析未解决的问题,并吸收了前述的两种策略的思想的基础上提出来的.它第一次提出了构造模式树的概念,其中的构造操作符能体现XQuery的灵活特征.由于操作符具有很强的表达能力,OrientXA能够表达W3C的用例和XMark测试集的所有查询.     

DTD上的YFilter数据流查询优化算法

为了提高YFilter的查询处理效率,在已有的研究工作和YFilter的过滤技术上,定义了唯一父亲约束的完整性约束,并结合DTD的结构和约束信息优化XPath表达式,这种优化算法是在系统运行前进行的预处理,所以有效地降低了YFilter系统的查询时间和空间复杂度.实验结果表明,优化后查询表达式之间相同的前缀增加了,减少了有限自动机的状态数目,并且有效地加快了YFilter的查询速度.     

一种XML数据流之上持续查询执行器的增量维护方法

在XML数据流的海量持续查询处理领域中,很少有研究涉及到在查询集合发生变化的情况下,如何调整查询执行器以满足当前查询集合的问题．由于XML数据查询的数目是海量的,查询执行器重新构建的代价非常高．针对上述问题,提出了基于转换累计自动机的查询执行器的增量维护方法,来完成查询集合的增量增加和删除,从而避免了执行器重构的昂贵代价．同时,利用XML文档DTD结构约束,提高了查询执行器增量维护的效率,减少了增量维护所导致的空间冗余．实验表明,该方法能够以有限空间为代价,有效完成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.     

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

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

Bounded determinization of timed automata with silent transitions

Deterministic timed automata are strictly less expressive than their non-deterministic counterparts, which are again less expressive than those with silent transitions. As a consequence, timed automata are in general non-determinizable. This is unfortunate since deterministic automata play a major role in model-based testing, observability and implementability. However, by bounding the length of the traces in the automaton, effective determinization becomes possible. We propose a novel procedure for bounded determinization of timed automata. The procedure unfolds the automata to bounded trees, removes all silent transitions and determinizes via disjunction of guards. The proposed algorithms are optimized to the bounded setting and thus are more efficient and can handle a larger class of timed automata than the general algorithms. We show how to apply the approach in a fault-based test-case generation method, called model-based mutation testing, that was previously restricted to deterministic timed automata. The approach is implemented in a prototype tool and evaluated on several scientific examples and one industrial case study. To our best knowledge, this is the first implementation of this type of procedure for timed automata.     

The complexity of tree automata and XPath on grammar-compressed trees

The complexity of various membership problems for tree automata on compressed trees is analyzed. Two compressed representations are considered: dags, which allow to share identical subtrees in a tree, and straight-line context-free tree grammars, which moreover allow to share identical intermediate parts in a tree. Several completeness results for the classes NL, P, and PSPACE are obtained. Finally, the complexity of the evaluation problem for (structural) XPath queries on trees that are compressed via straight-line context-free tree grammars is investigated.