My favourite example is a classic 1977 result of Ashok Chandra and Philip Merlin. They showed that the query containment problem was decidable for conjunctive queries. The conjunctive query containment problem turns out to be equivalent to deciding whether there is a homomorphism between the two input queries. This rephrases a semantics problem, involving quantification over an infinite set, into a syntactic one, requiring only checking a finite number of possible homomorphisms. The homomorphism certificate is only of linear size and so the problem is in NP.
This theorem provides one of the foundations of the theory of database query optimization. The idea is to transform a query into another, faster one. However, one wants an assurance that the optimization process doesn't create a new query that fails to give answers on some databases where the original query did produce results.
Formally, a database query is an expression of the form $\mathbf{x}.Q(\mathbf{x},\mathbf{y})$, where $\mathbf{x}$ is a list of free variables, $\mathbf{y}$ is a list of bound variables, and $Q(\mathbf{x},\mathbf{y})$ is a first-order formula with variables $\mathbf{x}$ and $\mathbf{y}$ of a language with relation symbols. The query $Q$ may contain existential and universal quantifiers, the formula may contain conjunction and disjunction of relational atoms, and negation may also appear. A query is applied to a database instance $I$, which is a set of relations. The result is a set of tuples; when tuple $\mathbf{t}$ in the result is substituted for $\mathbf{x}$ then the formula $Q(\mathbf{t},\mathbf{y})$ can be satisfied. One can then compare two queries: $Q_1$ is contained in $Q_2$ if whenever $Q_1$ applied to an arbitrary database instance $I$ produces some results, then $Q_2$ applied to the same instance $I$ also produces some results. (It is OK if $Q_1$ doesn't produce results but $Q_2$ does, but for containment the implication must hold for every possible instance.)
The query containment problem asks: given two database queries $Q_1$ and $Q_2$, is $Q_1$ contained in $Q_2$?
It was not at all clear before Chandra-Merlin that the problem was decidable. Using just the definition, one has to quantify over the infinite set of all possible databases. If the queries are unrestricted, then the problem is, in fact, undecidable: let $Q_1$ be a formula that is always true, then $Q_1$ is contained in $Q_2$ iff $Q_2$ is valid. (This is Hilbert's Entscheidungsproblem, shown undecidable by Church and Turing in 1936.)
To avoid undecidability, a conjunctive query has a rather limited form: $Q$ only contains existential quantifiers, and negation and disjunction are not allowed. So $Q$ is a positive existential formula with only conjunction of relational atoms. This is a tiny fragment of logic, but it is enough to express a large proportion of useful database queries. The classic SELECT ... FROM statement in SQL expresses conjunctive queries; most search engine queries are conjunctive queries.
One can define homomorphisms between queries in a straightforward way (similar to graph homomorphism, with a bit of extra bookkeeping). The Chandra-Merlin theorem says: given two conjunctive queries $Q_1$ and $Q_2$, $Q_1$ is contained in $Q_2$ iff there is a query homomorphism from $Q_2$ to $Q_1$. This establishes membership in NP, and it is straightforward to show that this is also NP-hard.
- Ashok K. Chandra and Philip M. Merlin, Optimal Implementation of Conjunctive Queries in Relational Data Bases, STOC '77 77–90. doi:10.1145/800105.803397
Decidability of query containment was later extended to unions of conjunctive queries (existential positive queries where disjunction is allowed), although allowing disjunction raises the complexity to $\Pi^P_2$-complete. Decidability and undecidability results have also been established for a more general form of query containment, involving semiring valuations that occur when counting the number of answers, when combining annotations in provenance, or when combining results of queries in probabilistic databases.
