A more general theory of static approximations for conjunctive queries

Pablo Barceló, Miguel Romero, Thomas Zeume

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

1 Scopus citations


Conjunctive query (CQ) evaluation is NP-complete, but becomes tractable for fragments of bounded hypertreewidth. If a CQ is hard to evaluate, it is thus useful to evaluate an approximation of it in such fragments. While underapproximations (i.e., those that return correct answers only) are well-understood, the dual notion of overapproximations 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, is open. We develop a connection with existential pebble game tools that allows the systematic study of such problems. In particular, we show that the evaluation and identification of overapproximations can be solved in polynomial time. We also make progress in the problem of existence of overapproximations, showing it to be decidable in 2EXPTIME over the class of acyclic CQs. Furthermore, we look at when overapproximations do not exist, suggesting that this can be alleviated by using a more liberal notion of overapproximation. We also show how to extend our tools to study symmetric difference approximations. We observe that such approximations properly extend under- and over-approximations, settle the complexity of its associated identification problem, and provide several results on existence and evaluation.

Original languageEnglish
Title of host publication21st International Conference on Database Theory, ICDT 2018
EditorsYael Amsterdamer, Benny Kimelfeld
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
ISBN (Electronic)9783959770637
StatePublished - 1 Mar 2018
Externally publishedYes
Event21st International Conference on Database Theory, ICDT 2018 - Vienna, Austria
Duration: 26 Mar 201829 Mar 2018

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
ISSN (Print)1868-8969


Conference21st International Conference on Database Theory, ICDT 2018


  • Approximations
  • Conjunctive queries
  • Hypertreewidth
  • Pebble games


Dive into the research topics of 'A more general theory of static approximations for conjunctive queries'. Together they form a unique fingerprint.

Cite this