Oblivious and Semi-Oblivious Boundedness for Existential Rules - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier
Rapport (Rapport De Recherche) Année : 2020

Oblivious and Semi-Oblivious Boundedness for Existential Rules

Résumé

We study the notion of boundedness in the context of positive existential rules, that is, whether there exists an upper bound to the depth of the chase procedure , that is independent from the initial instance. By focussing our attention on the oblivious and the semi-oblivious chase variants, we give a characterization of boundedness in terms of FO-rewritability and chase termination. We show that it is decidable to recognize if a set of rules is bounded for several classes and outline the complexity of the problem. This report contains the paper published at IJCAI 2019 [Bourhis et al., 2019] and an appendix with full proofs.
Fichier principal
Vignette du fichier
2006.08467-boundedness.pdf (268.15 Ko) Télécharger le fichier
Origine Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

lirmm-02920624 , version 1 (24-08-2020)

Identifiants

Citer

Pierre Bourhis, Michel Leclère, Marie-Laure Mugnier, Sophie Tison, Federico Ulliana, et al.. Oblivious and Semi-Oblivious Boundedness for Existential Rules. [Research Report] LIRMM (UM, CNRS). 2020. ⟨lirmm-02920624⟩
155 Consultations
105 Téléchargements

Altmetric

Partager

More