Edinburgh Research Explorer

Counting Database Repairs under Primary Keys Revisited

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

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


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.

    Research areas

  • Inconsistent data, Numeric approximation algorithms


ACM SIGMOD/PODS International Conference on Management of Data (SIGMOD 2019)


Amsterdam, Netherlands

Event: Conference

Download statistics

No data available

ID: 84254101