# Review - Complexity of Answering Queries Using Materialized Views.

Alon Y. Levy:
Review - Complexity of Answering Queries Using Materialized Views.
ACM SIGMOD Digital Review 1: (1999)
## Review

This paper considers the complexity of answering queries using
views. Specifically, suppose you have the extensions and the
definitions of a set of views V_{1}, ..., V_{n},
and a query Q, and you want
all the possible answers for Q, given only the tuples in the
extensions of the views. (note that it may not be possible to find
**all** the answers to Q, so we are looking for the maximal set of
answers). The paper considers the data complexity of finding all such
answers.

Previous work on answering queries using views has considered the
problem of finding a query rewriting, i.e., a query expression that
refers to the views, such that when it is applied to the views results
in the maximal set of answers.

The paper shows that the data complexity of the problem is in some
cases NP-hard. An immediate corollary of this result is that in some
cases we cannot find a query rewriting, if the language for expressing
the rewriting is limited to a query language with polynomial-time data
complexity. Two important cases where this happens is (1) when the
query and the views are conjunctive but the query contains the
predicate !=, and (2) when the views are assumed to be complete, i.e.,
to contain all the tuples in their definition. (Note that in the
context of data integration, the views are not necessarily assumed to
be complete).

The results in this paper were further extended in an ICDT-99 paper by
Grahne and Mendelzon [2].

*Copyright © 1999 by the author(s).
Review published with permission.*

## References

- [1]
- Serge Abiteboul, Oliver M. Duschka:
Complexity of Answering Queries Using Materialized Views.
PODS 1998: 254-263
- [2]
- Gösta Grahne, Alberto O. Mendelzon:
Tableau Techniques for Querying Information Sources through Global Schemas.
ICDT 1999: 332-347

Copyright © Fri Mar 12 17:26:56 2010
by Michael Ley (ley@uni-trier.de)