# Review

- Alon Y. Levy: Review - Complexity of Answering Queries Using Materialized Views. ...

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].

- Alon Y. Levy: Review - Complexity of Answering Queries Using Materialized Views. ...