Computer Science – Databases
Scientific paper
2006-04-02
Computer Science
Databases
26 pages, 2 figures
Scientific paper
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.
Bertossi Leopoldo
Lopatenko Andrei
No associations
LandOfFree
Complexity of Consistent Query Answering in Databases under Cardinality-Based and Incremental Repair Semantics does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Complexity of Consistent Query Answering in Databases under Cardinality-Based and Incremental Repair Semantics, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Complexity of Consistent Query Answering in Databases under Cardinality-Based and Incremental Repair Semantics will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-173230