On the Computational Complexity of Consistent Query Answers

Original · EN

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 type of the constraints considered, their number, and the size of the query. We obtain several new PTIME cases, using new algorithms.