Existential Rules: A Graph-Based View

Marie-Laure Mugnier 1
1 GRAPHIK - Graphs for Inferences on Knowledge
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier, CRISAM - Inria Sophia Antipolis - Méditerranée
Abstract : We consider rules that allow to assert the existence of new individuals, an ability called value invention in databases. These rules are of the form body --> head, where the body and the head are function-free conjunctions of atoms, and variables that occur only in the head are existentially quantified, hence their name existential rules. Existential rules have long been studied in databases as high-level constraints called tuple generating dependencies. Recently, there has been renewed interest for these rules in the context of ontology-based data access (OBDA), a new paradigm that seeks to exploit the semantics encoded in ontologies while querying data. The deductive database language Datalog could be seen as a natural candidate for expressing ontological knowledge in this context, however its limitation is that it does not allow for value invention, since all variables in a rule head necessarily occur in the rule body. Value invention has been recognized as a necessary prerequisite in an open-world perspective, where all individuals are not known a priori. It is in particular a feature of description logics (DLs), well-known languages dedicated to ontological representation and reasoning. This prerequisite motivated the recent extension of Datalog to existential rules, which gave rise to the Datalog +/- formalism. In this talk, we present a graph view of the existential rule framework and some related results.
Document type :
Conference papers
Liste complète des métadonnées

Contributor : Marie-Laure Mugnier <>
Submitted on : Monday, December 10, 2012 - 10:15:08 PM
Last modification on : Wednesday, December 12, 2018 - 2:38:02 PM


  • HAL Id : lirmm-00763474, version 1



Marie-Laure Mugnier. Existential Rules: A Graph-Based View. 2nd International Workshop on Datalog 2.0, Vienne, Austria. pp.21-26. ⟨lirmm-00763474⟩



Record views