Computer Science – Databases
Scientific paper
2002-04-05
Computer Science
Databases
9 pages
Scientific paper
We consider here the problem of obtaining reliable, consistent information from inconsistent databases -- databases that do not have to satisfy given integrity constraints. We use the notion of consistent query answer -- a query answer which is true in every (minimal) repair of the database. We provide a complete classification of the computational complexity of consistent answers to first-order queries w.r.t. functional dependencies and denial constraints. We show how the complexity depends on the {\em type} of the constraints considered, their {\em number}, and the {\em size} of the query. We obtain several new PTIME cases, using new algorithms.
Chomicki Jan
Marcinkowski Jerzy
No associations
LandOfFree
On the Computational Complexity of Consistent Query Answers 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 On the Computational Complexity of Consistent Query Answers, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On the Computational Complexity of Consistent Query Answers will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-550819