| View-based query rewriting has important practical applications in a variety of data-management problems such as data integration, query optimization, data warehousing, and website design. Given a query and a set of views over a database schema, it is often necessary to rewrite the query in terms of the views. Answers to the query are then obtained by executing the rewriting. However, there may not always exist an equivalent rewriting of the given query using the given set of views. In this thesis, we study contained and containing rewritings; these rewritings produce respectively a subset and a superset of the set of query answers. In a given language, these represent best-approximation rewritings, as they provide the greatest underestimate and the least overestimate of the answer, respectively. We consider queries and views in the language of conjunctive queries with arithmetic comparisons (CQACs). The well-understood language of conjunctive queries (CQs) does not capture the in- or non-equalities that are characteristic of SQL select-project-join (SPJ) queries. Hence CQACs, which capture the full expressive power of SQL SPJ queries, are practically important to the many applications that need to use arithmetic comparisons.;For contained rewritings, we present a sound and complete algorithm Build-MaxCR for constructing, for CQAC queries and views, a maximally-contained rewriting (MCR) whose all CQAC disjuncts have up to a predetermined number of view literals. (This restriction on the number of view literals is due to the fact that for CQAC queries and views, a general view-based union-of-CQAC MCR may have an unbounded number of CQAC disjuncts.) To the best of our knowledge, Build-MaxCR is the first algorithm to find union-of-CQAC MCRs for arbitrary CQAC queries and views. For containing rewritings, we present a sound and efficient algorithm pruned-MiCR, which computes a CQAC containing rewriting that does not contain any other CQAC containing rewriting (i.e., computes a minimally containing rewriting, MiCR) and that has the minimum possible number of relational subgoals. As a result, the MiCR rewriting produced by algorithm pruned-MiCR may be very efficient to execute. Our experimental results indicate that our algorithms have good scalability and perform well in many practical cases, due to their extensive pruning of the search space. |
