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

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

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

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

含XPath的表达式的解析与应用

提出了在应用XML数据中的一类普遍性问题，指出通过定义、处理含XPath的规则式可有效地提高软件的可扩展性．阐述如何运用JavaCC实现对XPath规则式的解析处理，以及扩展的思路。     

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

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

基于XSLT的XML文档节点间约束关系验证

提出一种基于W3C XSLT技术标准的验证方法,利用XSLT和XPath相关技术,通过定义规范化的输入输出信息结构以及约束规则,完成了对XML文档节点之间约束关系的验证.     

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

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

基于XPath的新闻信息抽取系统设计与实现

随着互联网技术的迅猛发展,因特网成为目前新闻信息最丰富最主要的来源。本文在分析新闻网页的基础上,分析了目前现有的信息抽取技术和XML技术,提出了一个基于XML技术的Web新闻抽取系统。本文主要是充分运用XML中的XPath技术在数据定位方面的优势,并提出一种基于DOM树的XPath生成算法,使用XSLT语言用于描述抽取规则,并使用路径表达式XPath定位待抽取的信息点。     

基于DTD图的查询蕴含测试

XPath被广泛用于查询XML文档.在前人利用已有的XPath查询结果来求得新的查询结果工作的基础上,对一类XPath查询表达式给出了判断能否利用已有的XPath查询结果来求得新的查询结果的算法,这将有可能加快对新查询的处理.     

面向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文档模型使其包含标签信息,并给出了扩展后的文档模型需要满足的规则.然后通过讨论XML文档上的4种操作,描述了面向XML文档的细粒度强制访问控制模型的详细内容.该模型基于XML模式技术,它的控制粒度可以达到文档中的元素或者属性.最后讨论了该模型的体系结构和一些实现机制.     

Authorization Translation for XML Document Transformation

XML access control models proposed in the literature enforce access restrictions directly on the structure and content of an XML document. Therefore access authorization rules (authorizations, for short), which specify access rights of users on information within an XML document, must be revised if they do not match with changed structure of the XML document. In this paper, we present two authorization translation problems. The first is a problem of translating instance-level authorizations for an XML document. The second is a problem of translating schema-level authorizations for a collection of XML documents conforming to a DTD. For the first problem, we propose an algorithm that translates instance-level authorizations of a source XML document into those for a transformed XML document by using instance-tree mapping from the transformed document instance to the source document instance. For the second problem, we propose an algorithm that translates value-independent schema-level authorizations of non-recursive source DTD into those for a non-recursive target DTD by using schema-tree mapping from the target DTD to the source DTD. The goal of authorization translation is to preserve authorization equivalence at instance node level of the source document. The XML access control models use path expressions of XPath to locate data in XML documents. We define property of the path expressions (called node-reducible path expressions) that we can transform schema-level authorizations of value-independent type by schema-tree mapping. To compute authorizations on instances of schema elements of the target DTD, we need to identify the schema elements whose instances are located by a node-reducible path expression of a value-independent schema-level authorization. We give an algorithm that carries out path fragment containment test to identify the schema elements whose instances are located by a node-reducible path expression.     

一种基于DTD的XPath逻辑优化方法

Xpath成为XML数据查询的基本机制.Xpath中表达节点之间的祖孙关系的‘//'和任意匹配字符的‘*'等非确定操作符,增强了Xpath表达方式的灵活性,但同时引入了Xpath处理的复杂性.如何利用DTD减少Xpath中的不确定操作符,从而提高Xpath的执行效率成为一个基本的研究问题.传统方法主要侧重于特定受限Xpath的确定化重写.利用树自动机在一个框架中表达Xpath和DTD,提出了一种新的Xpath树自动机和DTD树自动机的乘积运算,并证明了乘积的结果就是基于DTD的Xpath优化形式,在多项式时间内基于代价获取了Xpath的优化结果.实验数据表明,基于提出的Xpath的逻辑优化方法,能够有效地提高Xpath执行器的执行效率.     

Generalized XML security views

We investigate a generalization of the notion of XML security view introduced by Stoica and Farkas (Proceedings of the 16th International Conference on Data and Applications Security (IFIP’02). IFIP Conference Proceedings, vol. 256, pp. 133–146. Kluwer, Dordrecht, 2002) and later refined by Fan et al. (Proceedings of the ACM SIG- MOD International Conference on Management of Data (SIGMOD’04), pp. 587–598. ACM Press, New York, 2004). The model consists of access control policies specified over DTDs with XPath expressions for data-dependent access control. We provide the notion of security views characterizing information accessible to authorized users. This is a trans- formed DTD schema that can be used by users for query formulation. We develop an algorithm to materialize an authorized version of the document from the view and an algorithm to construct the view from an access control specification. We show that our view construction combined with materialization produces the same result as the direct application of the DTD access specification on the document. We also propose a number of generalizations of possible security policies and show how they affect view construction algorithm. Finally, we provide an evaluation of our system.     

A high concurrency XPath-based locking protocol for XML databases

Providing efficient access to XML documents becomes crucial in XML database systems. More and more concurrency control protocols for XML database systems were proposed in the past few years. Being an important language for addressing data in XML documents, XPath expressions are the basis of several query languages, such as XQurey and XSLT. In this paper, we propose a lock-based concurrency control protocol, called XLP, for transactions accessing XML data by the XPath model. XLP is based on the XPath model and has the features of rich lock modes, low lock conflict and lock conversion. XLP is also proved to ensure conflict serializability. In sum, there are three major contributions in this paper. The proposed XLP supports most XPath axes, rather than simple path expressions only. Conflict conditions and rules in the XPath model are analyzed and derived. Moreover, a lightweighted lock mode, P-lock, is invented and integrated into XLP for better concurrency.     

基于DTD的XML与SQL查询转换算法

针对如何将XML查询转换成SQL查询提出了一个XSLT查询到SQL查询的转换框架和算法，研究了文档类型定义(DTD)和关系模式的相互映射方法及基于XML DTD且不使用任何中间语言将XSLT查询转换为SQL查询的具体过程和算法：从XSLT代码中抽取指令集合，合并、简化并分割其中的XPath，最后抽取出SQL语句的各个组成部分。该算法具有较高的通用性。     

基于XPath的XML查询重写算法

XML安全视图和查询重写是实现访问控制的关键技术。研究基于XML递归安全视图的查询重写问题,提出一种基于XPath查询语言、能处理递归视图的查询重写算法,避免了视图的物化和保存。该算法具有较高通用性,实验结果验证了其有效性。     

Computational complexity of the problem of tree generation under fine-grained access control policies

We consider the problem of deciding whether a fine-grained access control policy for tree updates allows a particular document to be constructed. This problem arises from a number of natural questions related to document security, authenticity, and verifiability. Fine-grained access control is the problem of specifying the set of operations that may be performed on a complex structure. For tree-structured databases and documents, particularly XML, a rule-based approach is most common. In this model, access control policies consist of rules that select the allowed or disallowed targets of queries or updates based on their hierarchical relationships to other nodes.We show that, for a typical form of rule-based fine-grained access control policies based on a simple fragment of XPath, this problem is undecidable. We also prove lower bounds on the complexity of various restrictions of this problem, and demonstrate deterministic and nondeterministic polynomial-time algorithms for two restrictions in particular.These results show that, for sufficiently complex access control languages, certain forms of analysis are very difficult or even impossible, limiting the ability to verify documents, audit existing policies, and evaluate new policies. Thus rule-based access control policies based on XPath are, in some sense, too powerful, demonstrating the need for a model of access control of tree updates that bridges the gap between expressive and analyzable policies.     

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.