Consistent Query Answering without Repairs in Tables with Nulls and Functional Dependencies - Laboratoire Interdisciplinaire des Sciences du Numérique Accéder directement au contenu
Pré-Publication, Document De Travail Année : 2023

Consistent Query Answering without Repairs in Tables with Nulls and Functional Dependencies

Dominique Laurent
  • Fonction : Auteur
  • PersonId : 860350

Résumé

In this paper, we study consistent query answering in tables with nulls and functional dependencies. Given such a table T, we consider the set \mathcal{T} of all tuples that can be built up from constants appearing in T; and we use set theoretic semantics for tuples and functional dependencies to characterize the tuples of \mathcal{T} in two orthogonal ways: first as true or false tuples; and then as consistent or inconsistent tuples. Queries are issued against T and evaluated in \mathcal{T}. In this setting, we consider a query Q: select X from T where Condition over T and define its consistent answer to be the set of tuples x in \mathcal{T} such that: (a) x is a true and consistent tuple with schema X and (b) there exists a true super-tuple t of x in \mathcal{T} satisfying the condition. We show that, depending on the `status' that the super-tuple t has in \mathcal{T}, there are different types of consistent answer to Q. The main contributions of the paper are: (a) a novel approach to consistent query answering {\em not} using table repairs; (b) polynomial algorithms for computing the sets of true/false tuples and the sets of consistent/inconsistent tuples of \mathcal{T}; (c) polynomial algorithms in the size of T for computing different types of consistent answer for both conjunctive and disjunctive queries; and (d) a detailed discussion of the differences between our approach and the approaches using table repairs.
Fichier principal
Vignette du fichier
LS-RR-2023-extended.pdf (621.45 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)

Dates et versions

hal-03931310 , version 1 (09-01-2023)
hal-03931310 , version 2 (16-02-2023)

Licence

Paternité

Identifiants

Citer

Dominique Laurent, Nicolas Spyratos. Consistent Query Answering without Repairs in Tables with Nulls and Functional Dependencies. 2023. ⟨hal-03931310v2⟩
58 Consultations
26 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More