An Isaac Newton Institute Workshop

Logic and Databases

Cardinality-based semantics for consistent query answering: incremental and parameterized complexity

27th February 2006

Authors: Leopoldo Bertossi (Carleton University), Andrei Lopatenko (Free University Bolzano-Bozen)


Consistent Query Answering (CQA) is the problem of computing from a database the answers to a query that are consistent with respect to certain integrity constraints, that the database, as a whole, may fail to satisfy. Consistent answers have been characterized as those that are invariant under certain minimal forms of restoration of the consistency of the database.

In this paper we investigate algorithmic and complexity theoretic issues of CQA under database repairs that minimally depart -wrt the cardinality of the symmetric difference- from the original database. Research on this kind of repairs had been suggested in the literature, but no systematic study had been done. Here we obtain first tight complexity bounds.

We also address, considering for the first time a dynamic scenario for CQA, the problem of incremental complexity of CQA, that naturally occurs when an originally consistent database becomes inconsistent after the execution of a sequence of update operations. Tight bounds on incremental complexity are provided for various semantics under denial constraints, e.g. (a) minimum tuple-based repairs wrt cardinality, (b) minimal tuple-based repairs wrt set inclusion, and (c) minimum numerical aggregation of attribute-based repairs. Fixed parameter tractability is also investigated in this dynamic context, where the size of the update sequence becomes the relevant parameter.

Related Links