Deduction with Contradictions in Datalog

Serge Abiteboul 1, 2 Daniel Deutch 3 Victor Vianu 4
2 DAHU - Verification in databases
LSV - Laboratoire Spécification et Vérification [Cachan], ENS Cachan - École normale supérieure - Cachan, Inria Saclay - Ile de France, CNRS - Centre National de la Recherche Scientifique : UMR8643
Abstract : We study deduction in the presence of inconsistencies. Following previous works, we capture deduction via datalog programs and inconsistencies through violations of functional dependencies (FDs). We study and compare two semantics for datalog with FDs: the first, of a logical nature, is based on inferring facts one at a time, while never violating the FDs; the second, of an operational nature, consists in a fixpoint computation in which maximal sets of facts consistent with the FDs are inferred at each stage. Both semantics are nondeterministic, yielding sets of possible worlds. We introduce a PTIME (in the size of the extensional data) algorithm, that given a datalog program, a set of FDs and an input instance, produces a c-table representation of the set of possible worlds. Then, we propose to quantify nondeterminism with probabilities, by means of a probabilistic semantics. We consider the problem of capturing possible worlds along with their probabilities via probabilistic c-tables. We then study classical computational problems in this novel context. We consider the problems of computing the probabilities of answers, of identifying most likely supports for answers, and of determining the extensional facts that are most influential for deriving a particular fact. We show that the interplay of recursion and FDs leads to novel technical challenges in the context of these problems.
Type de document :
Communication dans un congrès
International Conference on Database Theory, 2014, Athens, Greece. 2014
Liste complète des métadonnées

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

https://hal.inria.fr/hal-00923265
Contributeur : Serge Abiteboul <>
Soumis le : jeudi 2 janvier 2014 - 11:05:54
Dernière modification le : jeudi 9 février 2017 - 15:47:12
Document(s) archivé(s) le : samedi 8 avril 2017 - 09:44:49

Fichier

13DatalogFD.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-00923265, version 1

Collections

Citation

Serge Abiteboul, Daniel Deutch, Victor Vianu. Deduction with Contradictions in Datalog. International Conference on Database Theory, 2014, Athens, Greece. 2014. 〈hal-00923265〉

Partager

Métriques

Consultations de
la notice

598

Téléchargements du document

358