On the Computational Complexity of Consistent Query Answers
| dc.creator | Chomicki, Jan | |
| dc.creator | Marcinkowski, Jerzy | |
| dc.date | 2002-04-05 | |
| dc.date.accessioned | 2026-07-07T03:18:16Z | |
| dc.date.available | 2026-07-07T03:18:16Z | |
| dc.description | 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. | |
| dc.description | 9 pages | |
| dc.identifier | https://arxiv.org/abs/cs/0204010 | |
| dc.identifier | http://arxiv.org/abs/cs/0204010 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/31042 | |
| dc.subject | Databases | |
| dc.subject | H.2.3; F.4.1; I.2.3 | |
| dc.title | On the Computational Complexity of Consistent Query Answers | |
| dc.type | text |