Counting Database Repairs under Primary Keys Revisited

Database and Artificial Intelligence Group hosting a talk by Andreas Pieris

ABSTRACT

Consistent query answering 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, it is well-known that Cook reductions blur structural differences between counting problems and complexity classes since #P is not closed under Cook reductions (under reasonable assumptions). The goal of this talk is to perform a refined complexity analysis for the problem of counting the number of repairs under primary keys that entail the query through the lens of standard many-one logspace reductions.

This is joint work with Marco Calautti and Marco Console.

CONTACT

Reinhard Pichler

Andreas Pieris, University of Edinburgh