Projects per year
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 #Pcomplete in data complexity under polynomialtime 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 “hardtocounteasytodecide”, which cannot be complete (under reasonable assumptions) for #P under weaker reductions, and, in particular, under standard manyone logspace reductions (a.k.a. parsimonious reductions). For such “hardtocounteasytodecide” 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 manyone 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 language  English 

Title of host publication  Proceedings of the 38th ACM SIGMODSIGACTSIGAI Symposium on Principles of Database Systems 
Place of Publication  New York 
Publisher  ACM 
Pages  104118 
Number of pages  15 
ISBN (Print)  9781450362276 
DOIs  
Publication status  Published  25 Jun 2019 
Event  ACM SIGMOD/PODS International Conference on Management of Data (SIGMOD 2019)  Amsterdam, Netherlands Duration: 30 Jun 2019 → 5 Jul 2019 http://sigmod2019.org/ 
Conference
Conference  ACM SIGMOD/PODS International Conference on Management of Data (SIGMOD 2019) 

Abbreviated title  SIGMOD 2019 
Country  Netherlands 
City  Amsterdam 
Period  30/06/19 → 5/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.
Projects


VADA: Value Added Data Systems: Principles and Architecture
Libkin, L., Buneman, P., Fan, W. & Pieris, A.
1/04/15 → 30/09/20
Project: Research