|
|
|
This paper considers the complexity of answering queries using views. Specifically, suppose you have the extensions and the definitions of a set of views V1, ..., Vn, 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.
