Complexity of Consistent Query Answering in Databases under Cardinality-Based and Incremental Repair Semantics

Thumbnail Image

Date

Authors

Journal Title

Journal ISSN

Volume Title

Publisher

Abstract

Description

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 database consistency. 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. We obtain first tight complexity bounds. We also address 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. Fixed parameter tractability is also investigated in this dynamic context, where the size of the update sequence becomes the relevant parameter.
26 pages, 2 figures

Keywords

Databases, Computational Complexity

Citation

URI

http://salesiana.dossiersoluciones.com/handle/123456789/111009

Consulte el texto completo en el siguiente enlace:

https://arxiv.org/abs/cs/0604002
 http://arxiv.org/abs/cs/0604002

Collections

arXiv