Answering queries using views.
Alon Y. Levy, Alberto O. Mendelzon, Yehoshua Sagiv and Divesh Srivastava.
We consider the problem of computing answers to queries by using
materialized views. Aside from its potential in optimizing query
evaluation, the problem also arises in applications such as Global
Information Systems, Mobile Computing and maintaining physical
data independence. We consider the problem of finding a rewriting
of a query that uses the materialized views, the problem of
finding minimal rewritings, and finding complete rewritings
(i.e., rewritings that use only the views). We show that all the
possible rewritings can be obtained by considering containment
mappings from the views to the query, and that the problems we
consider are NP-complete when both the query and the views are
conjunctive and don't involve built-in comparison predicates. We
show that the problem has two independent sources of complexity
(the number of possible containment mappings, and the complexity
of deciding which literals from the original query can be deleted).
We describe a polynomial time algorithm for finding rewritings,
and show that under certain conditions, it will find the minimal
rewriting. Finally, we analyze the complexity of the problems
when the queries and views may be disjunctive and involve built-in
comparison predicates.