Halevy, A. Y. (2001). Answering queries using views: A survey. The VLDB Journal 10(4), 270–294. DOI 10.1007/s007780100054
Key takeaways
Read in full (NOTE-921). A survey that separates two problems of answering queries from stored views: finding an equivalent rewriting, which query optimization needs, and finding a maximally-contained rewriting or all certain answers, which data integration needs when sources are incomplete. Its theoretical findings, mostly reported from other papers: an equivalent conjunctive rewriting exists only if one exists no longer than the query, so finding one is NP-complete in the size of the query and view definitions, and checking a candidate is itself NP-complete; the inverse-rules algorithm builds the maximally-contained rewriting, as a possibly recursive datalog program, in time polynomial in the query and views; and finding all certain answers is polynomial in the size of the stored data in many open-world cases, but co-NP-hard in that size under the closed-world assumption even for conjunctive views and queries, or open-world with union in the views or ≠ in the query. Choosing which views to store is left as the next problem; cost-based choice among rewritings is described for practical optimizers, without guarantees.
Why this is here
The survey of the problem LIT-1100 opened, for CLAIM-303: reuse is graded. Certifying an exact rewriting is hard, while a maximally contained rewriting can be built in polynomial time; certain answers depend on the open- or closed-world assumption.