A Single Approach to Decide Chase Termination on Linear Existential Rules

Michel Leclère 1 Marie-Laure Mugnier 1 Michaël Thomazo 2 Federico Ulliana 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
2 VALDA - Value from Data
DI-ENS - Département d'informatique de l'École normale supérieure, Inria de Paris
Abstract : Existential rules, long known as tuple-generating dependencies in database theory, have been intensively studied in the last decade as a powerful formalism to represent ontological knowledge in the context of ontology-based query answering. A knowledge base is then composed of an instance that contains incomplete data and a set of existential rules, and answers to queries are logically entailed from the knowledge base. This brought again to light the fundamental chase tool, and its different variants that have been proposed in the literature. It is well-known that the problem of determining, given a chase variant and a set of existential rules, whether the chase will halt on a given instance / on any instance, is undecidable. Hence, a crucial issue is whether it becomes decidable for known subclasses of existential rules. We consider linear existential rules, a simple yet important subclass of existential rules. We study the decidability of the associated chase termination problem for different chase variants, with a novel approach based on a single graph and a single notion of forbidden pattern. Besides the theoretical interest of a unified approach, an original result is the decidability of the restricted chase termination for linear existential rules.
Type de document :
Communication dans un congrès
DL: Description Logics, Oct 2018, Tempe, United States. 31st International Workshop on Description Logics, 2018, 〈http://www.dcs.bbk.ac.uk/~michael/dl2018/〉
Liste complète des métadonnées

https://hal-lirmm.ccsd.cnrs.fr/lirmm-01892353
Contributeur : Marie-Laure Mugnier <>
Soumis le : mercredi 10 octobre 2018 - 15:28:40
Dernière modification le : jeudi 11 octobre 2018 - 01:20:14

Fichier

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

Identifiants

  • HAL Id : lirmm-01892353, version 1
  • ARXIV : 1810.02132

Citation

Michel Leclère, Marie-Laure Mugnier, Michaël Thomazo, Federico Ulliana. A Single Approach to Decide Chase Termination on Linear Existential Rules. DL: Description Logics, Oct 2018, Tempe, United States. 31st International Workshop on Description Logics, 2018, 〈http://www.dcs.bbk.ac.uk/~michael/dl2018/〉. 〈lirmm-01892353〉

Partager

Métriques

Consultations de la notice

11

Téléchargements de fichiers

8