Levy, A. Y., Mendelzon, A. O., Sagiv, Y. and Srivastava, D. (1995). Answering queries using views (extended abstract). In Proc. PODS 1995, pp. 95–104. DOI 10.1145/212433.220198
Key takeaways
Read in full (NOTE-909). For conjunctive queries and views, a view can be used in an equivalent rewriting of a query exactly when there is a containment mapping (a homomorphism of bodies) from the view into the query, so every possible use of a stored view is found among those mappings. Without comparison predicates, a minimal rewriting needs no more literals than the query and no new variables, which puts the search in NP; deciding whether some rewriting uses a given set of views (with comparisons only in the query), whether a rewriting with fewer than k literals exists, and whether a rewriting using only the views exists are each NP-complete, and with comparisons in both query and views existence is Π2p-complete. The hardness has two independent sources, the number of mappings and the choice of which query literals to drop, and a polynomial algorithm removes the redundant literals for a given mapping, exactly under stated conditions. Only equivalent rewritings are studied; contained rewritings, the cost of the resulting plan and the size of view collections are outside it.
Why this is here
CLAIM-303 and CLAIM-308 price reuse of a filed argument as access plus verification. This paper gives the complexity of recognizing that stored views answer a new query exactly: NP-complete for conjunctive queries, growing with the query and view definitions, not the stored data.