Existential Rules: A Graph-Based View

International audienceWe 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