Counting Database Repairs under Primary Keys Revisited

Marco Calautti, Marco Console, Andreas Pieris

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

Abstract

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
PublisherACM
Pages104-118
Number of pages15
ISBN (Print)978-1-4503-6227-6
DOIs
Publication statusPublished - 25 Jun 2019
EventACM SIGMOD/PODS International Conference on Management of Data (SIGMOD 2019) - Amsterdam, Netherlands
Duration: 30 Jun 20195 Jul 2019
http://sigmod2019.org/

Conference

ConferenceACM SIGMOD/PODS International Conference on Management of Data (SIGMOD 2019)
Abbreviated titleSIGMOD 2019
CountryNetherlands
CityAmsterdam
Period30/06/195/07/19
Internet address

Keywords

  • Inconsistent data
  • Numeric approximation algorithms

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

Cite this