Counting Database Repairs Entailing a Query: The Case of Functional Dependencies

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract / Description of output

A key task in the context of consistent query answering is to count the number of repairs that entail the query, with the ultimate goal being a precise data complexity classification. This has been achieved in the case of primary keys and self-join-free conjunctive queries (CQs) via an FP/#P-complete dichotomy. We lift this result to the more general case of functional dependencies (FDs). Another important task in this context is whenever the counting problem in question is intractable, to classify it as approximable, i.e., the target value can be efficiently approximated with error guarantees via a fully polynomial-time randomized approximation scheme (FPRAS), or as inapproximable. Although for primary keys and CQs (even with self-joins) the problem is always approximable, we prove that this is not the case for FDs. We show, however, that the class of FDs with a left-hand side chain forms an island of approximability. We see these results, apart from being interesting in their own right, as crucial steps towards a complete classification of approximate counting of repairs in the case of FDs and self-join-free CQs.
Original languageEnglish
Title of host publicationProceedings of the 41st ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems
Place of PublicationNew York, NY, USA
PublisherAssociation for Computing Machinery (ACM)
Pages403–412
Number of pages10
ISBN (Print)9781450392600
DOIs
Publication statusPublished - 13 Jun 2022
EventThe 41st ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems - Philadelphia, United States
Duration: 13 Jun 202215 Jun 2022
Conference number: 41

Publication series

NamePODS '22
PublisherAssociation for Computing Machinery

Symposium

SymposiumThe 41st ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems
Abbreviated titlePODS 2022
Country/TerritoryUnited States
CityPhiladelphia
Period13/06/2215/06/22

Keywords / Materials (for Non-textual outputs)

  • database repairs
  • efficient approximations
  • conjunctive queries
  • functional dependencies
  • counting

Fingerprint

Dive into the research topics of 'Counting Database Repairs Entailing a Query: The Case of Functional Dependencies'. Together they form a unique fingerprint.

Cite this