Counting Database Repairs under Primary Keys Revisited

Marco Calautti, Marco Console, Andreas Pieris

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

Abstract / Description of output

Consistent query answering (CQA) aims to deliver meaningful answers when queries are evaluated over inconsistent databases. Such answers must be certainly true in all repairs, which are consistent databases whose difference from the inconsistent one is somehow minimal. An interesting task in this context is to count the number of repairs that entail the query. This problem has been already studied for conjunctive queries and primary keys; we know that it is #P-complete in data complexity under polynomial-time Turing reductions (a.k.a. Cook reductions). However, as it has been already observed in the literature of counting complexity, there are problems that are “hard-to-count-easy-to-decide”, which cannot be complete (under reasonable assumptions) for #P under weaker reductions, and, in particular, under standard many-one logspace reductions (a.k.a. parsimonious reductions). For such “hard-to-count-easy-to-decide” problems, a crucial question is whether we can determine their exact complexity by looking for subclasses of #P to which they belong. Ideally, we would like to show that such a problem is complete for a subclass of #P under many-one logspace reductions. The main goal of this work is to perform such a refined analysis for the problem of counting the number of repairs under primary keys that entail the query.
Original languageEnglish
Title of host publicationProceedings of the 38th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems
Place of PublicationNew York
Number of pages15
ISBN (Print)978-1-4503-6227-6
Publication statusPublished - 25 Jun 2019
EventACM SIGMOD/PODS International Conference on Management of Data (SIGMOD 2019) - Amsterdam, Netherlands
Duration: 30 Jun 20195 Jul 2019


ConferenceACM SIGMOD/PODS International Conference on Management of Data (SIGMOD 2019)
Abbreviated titleSIGMOD 2019
Internet address

Keywords / Materials (for Non-textual outputs)

  • Inconsistent data
  • Numeric approximation algorithms


Dive into the research topics of 'Counting Database Repairs under Primary Keys Revisited'. Together they form a unique fingerprint.

Cite this