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

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

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

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

面向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流上的XQuery前缀共享查询

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

XML流管理研究综述

近年来,XML流管理是数据流研究领域中的一个热点研究问题.不同于传统数据库管理系统,XML数据流管理系统需要在使用少量内存的情况下随时处理在线到达的数据流;由于XML流具有递归的、层次的结构,并且用户兴趣通常用XML查询语言来表示,因此,XML流管理技术与关系型数据流(基于元组的数据)管理技术有很大不同.综述XML流管理技术及各项研究成果;指出XML流管理系统的特点;比较了当前典型的XML数据流管理系统;系统地阐述和分析当前国内外已有的XML流数据处理方法(包括基于自动机的方法、基于索引的方法,基于序列的方法)和流处理的相关优化技术;指出尚需进一步研究的问题.     

基于XPath的XML数据提取的C#实现

简要介绍了XPath技术,分析了使用XPath路径表示式选择XML文档节点的方式,分析了.NET对XML文档的访问支持,探讨了在.NET环境下,基于XPath技术使用C#语言实现XML文档数据提取的解决方案,为Web信息抽取软件的开发打下基础。     

基于XML的异构数据集成模式的研究

随着信息技术的发展,任何一个独立单位都有可能成为一个异构的数据源。为实现企业异构数据库间信息的共享和集成,对数据集成的原理以及主要技术进行了研究,重点分析了 XML 与数据库之间的映射、XML 文档存储模式、将 XML 查询转化为 SQL 的查询转换问题以及如何将关系数据发布为 XML 文档。该方案简单易行,保证了各系统仍然按照原来的方式运行,只是在需要进行信息交换时通过转换接口把本地数据库数据转换成 XML 文档即可。     

基于XML的网络管理

当前,应用XML相关技术的基于XML的网络管理已经表现出了很多的优势,然而,现有的网络设备都是内嵌SNMP代理,并使用SNMP的管理者。这里将介绍基于XML的网络管理的四种方式,并介绍基于XML的管理者,基于XML的代理和通道等技术。     

XML Q&A

问:XPath是什么? 答:XPath相当简单,但功能又很强大。由于XML对文档与数据的层次结构进行了描述,一条XPath语句可以很容易地在树中找到所需要的信息。参考以下的XML代码节选:     

基于XPath的XML查询优化

随着XML作为Internet上数据表示和交换的标准,如何高效地进行XML数据的查询己经变得越来越重要,许多XML查询语言也随之出现。这些查询语言虽然种类繁多,但都有个共同特征：使用基于XPath数据模型下规则路径表示来查询XML数据。研究表明,当前的关系数据库技术在处理规则路径表示的查询时通常效率不高。 文章在介绍了传统的基于遍历树的方法的基础上重点讨论了基于路径分解的查询处理算法,并对选择连接顺序算法提出了基于动态规划思想的改进,     

Worst-case optimal algorithm for XPath evaluation over XML streams

We consider the XPath evaluation problem: Evaluate an XPath query Q on a streaming XML document D; i.e., determine the set Q(D) of document elements selected by Q. We mainly consider Conjunctive XPath queries that involve only the child and descendant axes. Previously known in-memory algorithms for this problem use O(|D|) space and O(|Q||D|) time. Several previously known algorithms for the streaming version use Ω(dn) space and Ω(dn|D|) time in the worst case; d denotes the depth of D, and n denotes the number of location steps in Q. Their exponential space requirement could well exceed the O(|D|) space used by the in-memory algorithms. We present an efficient algorithm that uses O(d|Q|+nc) space and O((|Q|+dn)|D|) time in the worst case; c denotes the maximum number of elements of D that can be candidates for output, at any one instant. For some worst case Q and D, the memory space used by our algorithm matches our lower bound proved in a different paper; so, our algorithm uses optimal memory space in the worst case.     

基于LazyDFA的XPath在XML数据流上查询优化算法

针对XML数据流上XPath查询处理及查询优化问题,给出了一种基于lazyDFA技术的解决方案,并提出了优化算法。共享NFA状态表,通过将NFA中的状态分成共享和独享两个状态集来降低lazyDFA的内存使用量;建立状态转移表优化算法通过在lazyDFA状态结构中增加一个状态转移表,来提高lazyDFA的查询速度。实验结果表明,提出的方法能够在执行效率和空间代价方面优于传统算法。     

Memory lower bounds for XPath evaluation over XML streams

We consider the XPath evaluation problem: Evaluate an XPath query Q on a streaming XML document D. We consider two versions of the problem: 1) Filtering Problem: Determine if there is a match for Q in D. 2) Node Selection Problem: Determine the set Q(D) of document nodes selected by Q. We consider Conjunctive XPath (CXPath) queries that involve only the child and descendant axes. Let d denote the depth of D, and n denote the number of location steps in Q. Bar-Yossef et al. (2007, 2005) [6] and [7] presented lower bounds on the memory space required by any algorithm to solve these two problems. Their lower bounds apply to each query in a large subset of XPath, and are obtained (mostly) using nonrecursive(Q,D). In this paper, we present larger lower bounds for a different class of queries (namely, CXPath queries with independent predicates), on recursive(Q,D). One of our results is an Ω(n⋅maxcands(Q,D)) lower bound for the node selection problem, for a worst-case Q; maxcands(Q,D) is the maximum number of nodes of D that can be candidates for output, at any one instant. So, there is no algorithm for the node selection problem that uses O(f(d,|Q|)+maxcands(Q,D)) space, for any function f. This shows that some previously published algorithms are incorrect.     

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.     

Temporal XML: modeling, indexing, and query processing

In this paper we address the problem of modeling and implementing temporal data in XML. We propose a data model for tracking historical information in an XML document and for recovering the state of the document as of any given time. We study the temporal constraints imposed by the data model, and present algorithms for validating a temporal XML document against these constraints, along with methods for fixing inconsistent documents. In addition, we discuss different ways of mapping the abstract representation into a temporal XML document, and introduce TXPath, a temporal XML query language that extends XPath 2.0. In the second part of the paper, we present our approach for summarizing and indexing temporal XML documents. In particular we show that by indexing continuous paths, i.e., paths that are valid continuously during a certain interval in a temporal XML graph, we can dramatically increase query performance. To achieve this, we introduce a new class of summaries, denoted TSummary, that adds the time dimension to the well-known path summarization schemes. Within this framework, we present two new summaries: LCP and Interval summaries. The indexing scheme, denoted TempIndex, integrates these summaries with additional data structures. We give a query processing strategy based on TempIndex and a type of ancestor-descendant encoding, denoted temporal interval encoding. We present a persistent implementation of TempIndex, and a comparison against a system based on a non-temporal path index, and one based on DOM. Finally, we sketch a language for updates, and show that the cost of updating the index is compatible with real-world requirements.     

流数据的连续查询优化技术*

介绍了流数据、连续查询的概念以及连续查询的语义,描述了流数据查询模型,并对流数据查询优化进行了讨论.     

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

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

一种基于树状逻辑式的XML查询方法*

随着XML在各类数据表示中的广泛应用,XML文档的查询方法成为当前数据处理的一个重要问题。已有的研究如XPath和XQuery得到应用,但其查询表现存在一些缺点需要改进。从模板匹配的角度出发,基于谓词逻辑设计了树状逻辑表达式LXT。该表达式的特点是能以树状结构模板描述XML文档查询需求。在此基础上,进一步探讨了基于LXT表达式的XML文档查询方法,从数据的查询过滤、结果的组织构造与含义等方面描述了利用LXT的特点设计XML查询表现形式的基本思路。