Efficient approximations of conjunctive queries

Pablo Barceló, Leonid Libkin, Miguel Romero

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

9 Scopus citations


When finding exact answers to a query over a large database is infeasible, it is natural to approximate the query by a more efficient one that comes from a class with good bounds on the complexity of query evaluation. In this paper we study such approximations for conjunctive queries. These queries are of special importance in databases, and we have a very good understanding of the classes that admit fast query evaluation, such as acyclic, or bounded (hyper)treewidth queries. We define approximations of a given query Q as queries from one of those classes that disagree with Q as little as possible. We mostly concentrate on approximations that are guaranteed to return correct answers. We prove that for the above classes of tractable conjunctive queries, approximations always exist, and are at most polynomial in the size of the original query. This follows from general results we establish that relate closure properties of classes of conjunctive queries to the existence of approximations. We also show that in many cases, the size of approximations is bounded by the size of the query they approximate. We establish a number of results showing how combinatorial properties of queries affect properties of their approximations, study bounds on the number of approximations, as well as the complexity of finding and identifying approximations. We also look at approximations that return all correct answers and study their properties.

Original languageEnglish
Title of host publicationPODS '12 - Proceedings of the 31st Symposium on Principles of Database Systems
Number of pages12
StatePublished - 2012
Externally publishedYes
Event31st ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, PODS '12 - Scottsdale, AZ, United States
Duration: 21 May 201223 May 2012

Publication series

NameProceedings of the ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems


Conference31st ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, PODS '12
Country/TerritoryUnited States
CityScottsdale, AZ


  • acyclic queries
  • conjunctive queries
  • graphs
  • homomorphisms
  • hypertree width
  • query approximation
  • query evaluation
  • tractability
  • treewidth


Dive into the research topics of 'Efficient approximations of conjunctive queries'. Together they form a unique fingerprint.

Cite this