Bottom-up mining of XML query patterns to improve XML querying

Querying XML data is a computationally expensive process due to the complex nature of both the XML data and the XML queries. In this paper we propose an approach to expedite XML query processing by caching the results of frequent queries. We discover frequent query patterns from user-issued queries using an efficient bottom-up mining approach called VBUXMiner. VBUXMiner consists of two main steps. First, all queries are merged into a summary structure named "compressed global tree guide" (CGTG). Second, a bottom-up traversal scheme based on the CGTG is employed to generate frequent query patterns. We use the frequent query patterns in a cache mechanism to improve the XML query performance. Experimental results show that our proposed mining approach outperforms the previous mining algorithms for XML queries, such as XQPMinerTID and FastXMiner, and that by caching the results of frequent query patterns, XML query performance can be dramatically improved.

Efficient processing of ordered XML twig pattern matching based on extended Dewey

Finding all occurrences of a twig pattern is a core operation of extensible markup language (XML) query processing. Holistic twig join algorithms, which avoid a large number of intermediate results, represent the state-of-the-art algorithms. However, ordered XML twig join is mentioned rarely in the literature and previous algorithms developed in attempts to solve the problem of ordered twig pattern (OTP) matching have poor performance. In this paper, we first propose a novel children linked stacks encoding scheme to represent compactly the partial ordered twig join results. Based on this encoding scheme and extended Dewey, we design a novel holistic OTP matching algorithm, called OTJFast, which needs only to access the labels of the leaf query nodes. Furthermore, we propose a new algorithm, named OTJFaster, incorporating three effective optimization rules to avoid unnecessary computations. This works well on available indices (such as B+-tree), skipping useless elements. Thus, not only is disk access reduced greatly, but also many unnecessary computations are avoided. Finally, our extensive experiments over both real and synthetic datasets indicate that our algorithms are superior to previous approaches.

Accomplishing Deterministic XML Query Optimization

As the popularity of XML (extensible Markup Language) keeps growing rapidly,the management of XML compliant structured-document databases has become a very interesting andcompelling research area. Query optimization for XML structured-documents stands out as one of themost challenging research issues in this area because of the much enlarged optimization (search)space, which is a consequence of the intrinsic complexity of the underlying data model of XML data.We therefore propose to apply deterministic transformations on query expressions to mostaggressively prune the search space and fast achieve a sufficiently improved alternative (if not theoptimal) for each incoming query expression. This idea is not just exciting but practicallyattainable. This paper first provides an overview of our optimization strategy, and then focuses onthe key implementation issues of our rule-based transformation system for XML query optimization ina database environment. The performance results we obtained from experimentation show that ourapproach is a valid and effective one.

Semantic Cache Replacement Strategy for XML Algebra-Based Query Optimization

Aiming at the fact that traditional cache replacement strategy lacks pertinence to the semantic cache in the process of extensible markup language （XML） algebra query, a replacement strategy based on the semantic cache contribution value is proposed. First, pattern matching rules for XML algebra query and semantic caches are given. Second, the method of calculating the semantic cache contribution value is proposed. In XML documents with four different sizes, the experimental results of time efficiency show that this strategy supports environment of the XML algebra query and it has better time efficiency than both least frequency used （LFU） and least recently used （LRU）.

Structural Join and Staircase Join Algorithms of Sibling Relationship

The processing of XML queries can result in evaluation of various structural relationships. Efficient algorithms for evaluating ancestor-descendant and parent-child relationships have been proposed. Whereas the problems of evaluating preceding-sibling-following-sibling and preceding-following relationships are still open. In this paper, we studied the structural join and staircase join for sibling relationship. First, the idea of how to filter out and minimize unnecessary reads of elements using parent＇s structural information is introduced, which can be used to accelerate structural joins of parent-child and preceding-sibling-following-sibling relationships. Second, two efficient structural join algorithms of sibling relationship are proposed. These algorithms lead to optimal join performance： nodes that do not participate in the join can be judged beforehand and then skipped using B^＋-tree index. Besides, each element list joined is scanned sequentially once at most. Furthermore, output of join results is sorted in document order. We also discussed the staircase join algorithm for sibling axes. Studies show that, staircase join for sibling axes is close to the structural join for sibling axes and shares the same characteristic of high efficiency. Our experimental results not only demonstrate the effectiveness of our optimizing techniques for sibling axes, but also validate the efficiency of our algorithms. As far as we know, this is the first work addressing this problem specially.

An Effective Semantic Cache for Exploiting XPath Query/View Answerability

Maintaining a semantic cache of materialized XPath views inside or outside the database is a novel, feasible and efficient approach to facilitating XML query processing. However, most of the existing approaches incur the following disadvantages： 1） they cannot discover enough potential cached views sufficiently to effectively answer subsequent queries; or 2） they are inefficient for view selection due to the complexity of XPath expressions. In this paper, we propose SCEND, an effective Semantic Cache based on dEcompositioN and Divisibility, to exploit the XPath query/view answerability. The contributions of this paper include： 1） a novel technique of decomposing complex XPath queries into some much simpler ones, which can facilitate discovering more potential views to answer a new query than the existing methods and thus can adequately exploit the query/view answerability; 2） an efficient view-section method by checking the divisibility between two positive numbers assigned to queries and views; 3） a cache-replacement approach to further enhancing the query/view answerability; 4） an extensive experimental study which demonstrates that our approach achieves higher performance and outperforms the existing state-of-the-art alternative methods significantly.