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.

Counting Database Repairs under Primary Keys Revisited / Calautti, Marco; Console, Marco; Pieris, Andreas. - (2019), pp. 104-118. (Intervento presentato al convegno PODS tenutosi a Amsterdam nel 30th June-5th July 2019) [10.1145/3294052.3319703].

Counting Database Repairs under Primary Keys Revisited

Marco Calautti;
2019-01-01

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.
2019
Proceedings of the 38th ACM SIGMOD-SIGACT-SIGAI Symposium on Principlesof Database Systems, PODS 2019, Amsterdam, The Netherlands, June 30 - July 5, 2019
New York City
ACM
Calautti, Marco; Console, Marco; Pieris, Andreas
Counting Database Repairs under Primary Keys Revisited / Calautti, Marco; Console, Marco; Pieris, Andreas. - (2019), pp. 104-118. (Intervento presentato al convegno PODS tenutosi a Amsterdam nel 30th June-5th July 2019) [10.1145/3294052.3319703].
File in questo prodotto:
File Dimensione Formato  
c13.pdf

Solo gestori archivio

Tipologia: Post-print referato (Refereed author’s manuscript)
Licenza: Tutti i diritti riservati (All rights reserved)
Dimensione 834.88 kB
Formato Adobe PDF
834.88 kB Adobe PDF   Visualizza/Apri
3294052.3319703.pdf

Solo gestori archivio

Tipologia: Versione editoriale (Publisher’s layout)
Licenza: Tutti i diritti riservati (All rights reserved)
Dimensione 1.93 MB
Formato Adobe PDF
1.93 MB Adobe PDF   Visualizza/Apri

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11572/260167
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 15
  • ???jsp.display-item.citation.isi??? 10
social impact