An efficient XML encoding and labeling method for query processing and updating on dynamic XML data

In this paper, we propose an efficient encoding and labeling scheme for XML, called EXEL, which is a variant of the region labeling scheme using ordinal and insert-friendly bit strings. We devise a binary encoding method to generate the ordinal bit strings, and an algorithm to make a new bit string inserted between bit strings without any influences on the order of preexisting bit strings. These binary encoding method and bit string insertion algorithm are the bases of the efficient query processing and the complete avoidance of re-labeling for updates. We present query processing and update processing methods based on EXEL. In addition, the Stack-Tree-Desc algorithm is used for an efficient structural join, and the String B-tree indexing is utilized to improve the join performance. Finally, the experimental results show that EXEL enables complete avoidance of re-labeling for updates while providing fairly reasonable query processing performance.     

Secure query processing against encrypted XML data using Query-Aware Decryption

Dissemination of XML data on the internet could breach the privacy of data providers unless access to the disseminated XML data is carefully controlled. Recently, the methods using encryption have been proposed for such access control. However, in these methods, the performance of processing queries has not been addressed. A query processor cannot identify the contents of encrypted XML data unless the data are decrypted. This limitation incurs overhead of decrypting the parts of the XML data that would not contribute to the query result. In this paper, we propose the notion of Query-Aware Decryption for efficient processing of queries against encrypted XML data. Query-Aware Decryption allows us to decrypt only those parts that would contribute to the query result. For this purpose, we disseminate an encrypted XML index along with the encrypted XML data. This index, when decrypted, informs us where the query results are located in the encrypted XML data, thus preventing unnecessary decryption for other parts of the data. Since the size of this index is much smaller than that of the encrypted XML data, the cost of decrypting this index is negligible compared with that for unnecessary decryption of the data itself. The experimental results show that our method improves the performance of query processing by up to six times compared with those of existing methods. Finally, we formally prove that dissemination of the encrypted XML index does not compromise security.     

Efficiently supporting order in XML query processing

XML is an ordered data model and XQuery expressions return results that have a well-defined order. However, little work on how order is supported in XML query processing has been done to date. In this paper we study the issues related to handling order in the XML context, namely challenges imposed by the XML data model, the variety of order requirements of the XQuery language, and the need to maintain order in the presence of updates to the XML data. We propose an efficient solution that addresses all these issues. Our solution is based on a key encoding for XML nodes that serves as node identity and at the same time encodes order. We design rules for encoding order of processed XML nodes based on the XML algebraic query execution model and the node key encoding. These rules do not require any actual sorting for intermediate results during execution. Our approach enables efficient order-sensitive incremental view maintenance as it makes most XML algebra operators distributive with respect to bag union. We prove the correctness of our order encoding approach. Our approach is implemented and integrated with Rainbow, an XML data management system developed at WPI. We have tested the efficiency of our approach using queries that have different order requirements. We have also measured the relative cost of different components related to our order solution in different types of queries. In general the overhead of maintaining order in our approach is very small relative to the query processing time.     

Efficient recursive XML query processing using relational database systems

Recursive queries are quite important in the context of XML databases. In addition, several recent papers have investigated a relational approach to store XML data and there is growing evidence that schema-conscious approaches are a better option than schema-oblivious techniques as far as query performance is concerned. However, the issue of recursive XML queries for such approaches has not been dealt with satisfactorily. In this paper we argue that it is possible to design a schema-oblivious approach that outperforms schema-conscious approaches for certain types of recursive queries. To that end, we propose a novel schema-oblivious approach, called Sucxent++ (Schema Unconcious XML Enabled System), that outperforms existing schema-oblivious approaches such as XParent by up to 15 times and schema-conscious approaches (Shared-Inlining) by up to eight times for recursive query execution. Our approach has up to two times smaller storage requirements compared to existing schema-oblivious approaches and 10% less than schema-conscious techniques. In addition Sucxent++ performs marginally better than Shared-Inlining and is 5.7–47 times faster than XParent as far as insertion time is concerned.     

Attribute grammars for scalable query processing on XML streams

We introduce the notion of XML Stream Attribute Grammars (XSAGs). XSAGs are the first scalable query language for XML streams (running strictly in linear time with bounded memory consumption independent of the size of the stream) that allows for actual data transformations rather than just document filtering. XSAGs are also relatively easy to use for humans. Moreover, the XSAG formalism provides a strong intuition for which queries can or cannot be processed scalably on streams. We introduce XSAGs together with the necessary language-theoretic machinery, study their theoretical properties such as expressiveness and complexity, and discuss their implementation.     

A coherent query language for XML

Text search engines are inadequate for indexing and searching XML documents because they ignore metadata and aggregation structure implicit in the XML documents. On the other hand, the query languages supported by specialized XML search engines are very complex. In this paper, we present a simple yet flexible query language, and develop its semantics to enable intuitively appealing extraction of relevant fragments of information while simultaneously falling back on retrieval through plain text search if necessary. Our approach combines and generalizes several available techniques to obtain precise and coherent results.

XML数据查询语言XQuery应用分析

目前,XML已经成为事实上的数据表示和数据交换标准,XQuery是用来对XML文档进行数据查询的W3C候选推荐标准。结合XQuery规范的最新发展状况,介绍XQuery查询语言的主要特性,通过实例讨论XQuery语言在数据查询、转换等方面的应用。对SQL/XML和Xquery进行了比较,并分析了XQuery的实现与应用情况。     

基于关系数据库的实时XML数据查询处理

力图用成熟的关系数据库查询机制处理符合DTD的XML文档。提出了一整套数据模型、转换规则和算法描述,可以将XML文档转换为关系元组,从而达到用XML实现基于关系数据库的实时数据一致性查询处理的目的。     

XML形式数据模型及其查询代数

提出了XML的形式数据模型及其查询代数,主要包括以下几个方面：构造先后序关系、引入带根连通有向图、建立XML形式数据模型(XFDM)和XML查询代数(XFQA)。它形成了一个较为完整的XML数据库管理系统的理论基础,可以作为XML以及其它半结构化数据库管理系统查询存储、查询分解、查询优化和查询实现的形式化基础。     

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

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

The dynamic predicate: integrating access control with query processing in XML databases

Recently, access control on XML data has become an important research topic. Previous research on access control mechanisms for XML data has focused on increasing the efficiency of access control itself, but has not addressed the issue of integrating access control with query processing. In this paper, we propose an efficient access control mechanism tightly integrated with query processing for XML databases. We present the novel concept of the dynamic predicate (DP), which represents a dynamically constructed condition during query execution. A DP is derived from instance-level authorizations and constrains accessibility of the elements. The DP allows us to effectively integrate authorization checking into the query plan so that unauthorized elements are excluded in the process of query execution. Experimental results show that the proposed access control mechanism improves query processing time significantly over the state-of-the-art access control mechanisms. We conclude that the DP is highly effective in efficiently checking instance-level authorizations in databases with hierarchical structures.     

Efficient access control labeling scheme for secure XML query processing

We propose an efficient access control labeling scheme for secure query processing under dynamic Extensible Markup Language (XML) data streams. In recent years, XML has become an active research area. In particular, the needs for an efficient and secure query processing method for dynamic XML data in a ubiquitous data stream environment has become very important. The proposed access control labeling scheme supports the efficient processing of dynamic XML data, eliminating the need for re-labeling and secure query processing. Our proposal has the advantage of having an adaptable access control scheme for an existing XML labeling method.     

一种改进的XML查询重写算法研究

查询重写是数据集成的一个关键问题,它是将用户的查询请求自动重写为直接面向数据源的查询请求。最近Michigan大学和IBM的AImaden研究中心提出了一种新的基于约束的XML查询重写算法,但是该算法没有考虑复杂模式匹配重写问题,使得该算法应用受到限制。在原来的算法重写思想基础上,提出了一种改进的XML查询重写算法,扩大原算法的应用范围,并分析了改进算法的正确性和时间复杂度。     

基于关系代数的XML数据查询

XML渐已成为Web上数据表示和交换的通用语言。为了有效地利用大量的XML文档,需要研究XML数据查询技术。提出了基于关系代数的XML数据查询方法。XML子句可以用关系代数表达式表示,并通过关系代数操作得到查询结果。该方法为查询XML数据提供了一种简洁和有效的手段。     

RDBMS中层次查询结果的XML文档生成

数据库应用系统中相当多的数据都呈现出相应的层次特征,对这类数据,常常需要生成元素间保持层次特征的XML文档,用一般的查询机制来解决这个问题比较繁琐,以Oracle9i数据库第2版为例,应用层次查询,并结合OracleXML DB,对层次查询结果相对应的保持层次特征的XML文档的生成机制进行了研究,并将其应用于税务信息综合查询系统之中.结果表明,该方法简单、效率高、应用效果良好.     

面向对象XML数据查询的代价估计研究

由于XML具有丰富的表达能力、自描述性和灵活性等优点,而面向对象的概念又具有很强的建模能力,将面向对象的概念引入到XML可以提高XML模式语言的建模能力。而面向对象XML数据查询的值匹配条件的查询代价估计问题是一种典型的多元素查询条件的代价估计问题。XML数据的值分布与其他值信息的分布有关,还与XML数据的结构信息有关,很难使用某种单一的代价估计方法。针对以上问题,提出了一种基于直方图,在估计过程中结合查询树结构的代价估计方法。     

XML压缩文档上的数值更新方法

近年来,XML已成为Web上信息交流和资源共享的主要载体。但XML自身的自冗余特性限制了它的普遍应用。目前,已经有研究成果提出了XML的压缩方法。压缩的XML文档能够有效利用存储空间,节省网络带宽。在实际应用中,经常需要对压缩存储的XML文档进行更新。对于大的压缩文档,如果先解压再更新,会消耗大量时间,因此,高效的更新方法应该避免解压缩文档,在压缩的XML文档上直接进行更新操作。本文针对压缩XML文档中的数值类型（包括整型和浮点型）数据,研究了在保持压缩状态条件下如何进行有效的数值更新,提出了基于XPRESS实现的Naive数值更新方法,以及修改XPRESS编码方法实现的更为高效的Pivot数值更新方法。通过大量的实验证明,Pivot数值更新方法不仅能够提供高效的更新处理,而且保持了XPRESS的高压缩率。     

Incremental sequence-based frequent query pattern mining from XML queries

Existing algorithms of mining frequent XML query patterns (XQPs) employ a candidate generate-and-test strategy. They involve expensive candidate enumeration and costly tree-containment checking. Further, most of existing methods compute the frequencies of candidate query patterns from scratch periodically by checking the entire transaction database, which consists of XQPs transferred from user query logs. However, it is not straightforward to maintain such discovered frequent patterns in real XML databases as there may be frequent updates that may not only invalidate some existing frequent query patterns but also generate some new frequent query patterns. Therefore, a drawback of existing methods is that they are rather inefficient for the evolution of transaction databases. To address above-mentioned problems, this paper proposes an efficient algorithm ESPRIT to mine frequent XQPs without costly tree-containment checking. ESPRIT transforms XML queries into sequences using a one-to-one mapping technique and mines the frequent sequences to generate frequent XQPs. We propose two efficient incremental algorithms, ESPRIT-i and ESPRIT-i ⁺, to incrementally mine frequent XQPs. We devise several novel optimization techniques of query rewriting, cache lookup, and cache replacement to improve the answerability and the hit rate of caching. We have implemented our algorithms and conducted a set of experimental studies on various datasets. The experimental results demonstrate that our algorithms achieve high efficiency and scalability and outperform state-of-the-art methods significantly.     

Extending path summary and region encoding for efficient structural query processing in native XML databases

Optimizing query processing is always a challenging task in the XML database community. Current state-of-the-art approaches focus mainly on simple query. Yet, as the usage of XML shifts towards the data-oriented paradigm, more and more complex query processing needs to be supported. In this paper, we present TwigX-Guide, a hybrid system, which takes advantage of the beautiful features of path summary in DataGuide and region encoding in TwigStack to improve complex query processing. Experimental results indicate that TwigX-Guide can process complex queries on an average 38% better than the TwigStack algorithm, 31% better than TwigINLAB, 11% better than TwigStackList and about 9% better than TwigStackXB in terms of execution time.