  Conjunctive query (CQ) evaluation is NP-complete, but becomes tractable for
fragments of bounded hypertreewidth. Approximating a hard CQ by a query from
such a fragment can thus allow for an efficient approximate evaluation. While
underapproximations (i.e., approximations that return correct answers only) are
well-understood, the dual notion of overapproximations (i.e, approximations
that return complete - but not necessarily sound - answers), and also a more
general notion of approximation based on the symmetric difference of query
results, are almost unexplored. In fact, the decidability of the basic problems
of evaluation, identification, and existence of those approximations has been
open.
  This article establishes a connection between overapproximations and
existential pebble games that allows for studying such problems systematically.
Building on this connection, it is shown that the evaluation and identification
problem for overapproximations can be solved in polynomial time. While the
general existence problem remains open, the problem is shown to be decidable in
2EXPTIME over the class of acyclic CQs and in PTIME for Boolean CQs over binary
schemata. Additionally we propose a more liberal notion of overapproximations
to remedy the known shortcoming that queries might not have an
overapproximation, and study how queries can be overapproximated in the
presence of tuple generating and equality generating dependencies.
  The techniques are then extended to symmetric difference approximations and
used to provide several complexity results for the identification, existence,
and evaluation problem for this type of approximations.
