Rewriting and evaluating XPath queries using views

Rewriting and evaluating queries using views, also known as answering queries using views, is to utilize previously defined and materialized views to evaluate queries in order to save the cost of accessing large real database. It is a classic problem, and appears in many applications, such as query optimization, data integration, data warehouse and query caching. With the prevalence of XML technologies, rewriting XML queries using XML views has caught the attention of both researchers and system designers, and is believed to be a promising technique in web and database applications. Since XPath serves as the core sub-language of the major XML query languages, such as XQuery and XSLT, it is of immense value to study how to rewrite and evaluate XPath queries using XPath views. In this thesis, contained rewriting for XPath queries using XPath views is studied. Contained rewriting is proposed to provide best effort to answer a user’s query when equivalent rewriting does not exit. Given a query and a view, there may be an exponential number of contained rewritings. Some of them are redundant because the query answers produced by these redundant contained rewritings can be covered by other contained rewritings. Obviously, it is unnecessary to evaluate redundant contained rewritings on materialized views. We investigate the problem and propose a series of methods to discover all irredundant contained rewritings, and we show the correctness of the proposed methods. Furthermore, we study the evaluation of a group of contained rewritings on a given materialized view. The problem is transformed into evaluating component patterns, and four pruning rules and three heuristic rules are developed to speed up the evaluation dramatically. When a schema is available, we discuss how to utilize schema information for rewriting a query using a view, because a query, not answerable using a view in general, may be answerable using the view if the query and the view are complied with schema constraints. Finally, a set of filtering techniques are given to select promising views to answer users' query. Indexes and three algorithms are developed to quickly identify whether a view should be used or not.