Consistent Query Answers in the Presence of Universal Constraints

Slawomir Staworko 1, 2, * Jan Chomicki 3
* Auteur correspondant
1 MOSTRARE - Modeling Tree Structures, Machine Learning, and Information Extraction
LIFL - Laboratoire d'Informatique Fondamentale de Lille, Inria Lille - Nord Europe
Abstract : The framework of consistent query answers and repairs has been introduced to alleviate the impact of inconsistent data on the answers to a query. A repair is a minimally different consistent instance and an answer is consistent if it is present in every repair. In this article we study the complexity of consistent query answers and repair checking in the presence of universal constraints. We propose an extended version of the conflict hypergraph which allows to capture all repairs w.r.t. a set of universal constraints. We show that repair checking is in PTIME for the class of full tuple-generating dependencies and denial constraints, and we present a polynomial repair algorithm. This algorithm is sound, i.e. always produces a repair, but also complete, i.e. every repair can be constructed. Next, we present a polynomial-time algorithm computing consistent answers to ground quantifier-free queries in the presence of denial constraints, join dependencies, and acyclic full-tuple generating dependencies. Finally, we show that extending the class of constraints leads to intractability. For arbitrary full tuple-generating dependen- cies consistent query answering becomes coNP-complete. For arbitrary universal constraints consistent query answering is Πp2-complete and repair checking coNP- complete.
Type de document :
Article dans une revue
Information Systems, Elsevier, 2010, 35 (1), pp.1-22
Liste complète des métadonnées

Littérature citée [39 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/inria-00489298
Contributeur : Slawomir Staworko <>
Soumis le : lundi 5 septembre 2011 - 19:06:07
Dernière modification le : jeudi 11 janvier 2018 - 06:22:13
Document(s) archivé(s) le : mardi 13 novembre 2012 - 09:51:04

Fichier

staworko-is09.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : inria-00489298, version 1

Collections

Citation

Slawomir Staworko, Jan Chomicki. Consistent Query Answers in the Presence of Universal Constraints. Information Systems, Elsevier, 2010, 35 (1), pp.1-22. 〈inria-00489298〉

Partager

Métriques

Consultations de la notice

247

Téléchargements de fichiers

133