Chandra, A. K. and Merlin, P. M. (1977). Optimal implementation of conjunctive queries in relational data bases. In Proc. STOC 1977, pp. 77–90. DOI 10.1145/800105.803397
Key takeaways
Read in full (NOTE-907). Defines conjunctive queries (existentially quantified conjunctions of atoms, no equality, constants naming distinct elements) and proves that two are equivalent exactly when there are homomorphisms each way between their natural models (Lemma 13). Every conjunctive query has a minimal equivalent query, unique up to isomorphism, reached by folding (Theorem 12), and that minimal query yields an evaluation program within a constant factor of optimal in the paper’s cost model (Theorem 16). The hardness results are that evaluating a boolean conjunctive query on a database is NP-complete when the query is part of the input (Theorem 7), and that deciding whether one query is a folding of another is NP-complete (Theorem 11). The paper does not state a containment theorem or the NP-completeness of containment or equivalence as such; both are standard corollaries of Lemma 13’s proof and Theorem 11’s construction, and later papers cite them to it.
Why this is here
The equivalence result underneath LIT-1100: two conjunctive queries are equivalent exactly when each maps homomorphically into the other, and every query has a unique minimal equivalent. That containment and equivalence are NP-complete is the corollary later work attributes to it; the paper does not state it.