A More General Theory of Static Approximations for Conjunctive Queries

Pablo Barceló, Miguel Romero, Thomas Zeume

Research output: Contribution to journalArticlepeer-review


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.

Original languageEnglish
Pages (from-to)916-964
Number of pages49
JournalTheory of Computing Systems
Issue number5
StatePublished - 1 Jul 2020
Externally publishedYes


  • Approximations
  • Conjunctive queries
  • Existential pebble game
  • Hypertreewidth


Dive into the research topics of 'A More General Theory of Static Approximations for Conjunctive Queries'. Together they form a unique fingerprint.

Cite this