DI-UMONS : Dépôt institutionnel de l’université de Mons

Recherche transversale
(titres de publication, de périodique et noms de colloque inclus)
2009-11-01 - Article/Dans un journal avec peer-review - Anglais - 24 page(s)

Wijsen Jef , "On the consistent rewriting of conjunctive queries under primary key constraints" in Information Systems, 34, 7, 578-601

  • Edition : Pergamon Press - An Imprint of Elsevier Science
  • Codes CREF : Informatique mathématique (DI1160)
  • Unités de recherche UMONS : Systèmes d'information (S832)
Texte intégral :

Abstract(s) :

(Anglais) This article deals with the computation of consistent answers to queries on relational databases that violate primary key constraints. A repair of such inconsistent database is obtained by selecting a maximal number of tuples from each relation without ever selecting two distinct tuples that agree on the primary key. We are interested in the following problem: Given a Boolean conjunctive query q, compute a Boolean first-order (FO) query @j such that for every database db, @j evaluates to true on db if and only if q evaluates to true on every repair of db. Such @j is called a consistent FO rewriting of q. We use novel techniques to characterize classes of queries that have a consistent FO rewriting. In this way, we are able to extend previously known classes and discover new ones. Finally, we use an Ehrenfeucht-Fraisse game to show the non-existence of a consistent FO rewriting for @?x@?y(R(x@?,y)@?R(y@?,c)), where c is a constant and the first coordinate of R is the primary key.

Identifiants :
  • DOI : 10.1016/j.is.2009.03.011