Skip to Main content Skip to Navigation
Reports

Oblivious and Semi-Oblivious Boundedness for Existential Rules

Pierre Bourhis 1, 2 Michel Leclère 3 Marie-Laure Mugnier 3 Sophie Tison 4, 5 Federico Ulliana 3 Lily Galois 4, 5
1 SPIRALS - Self-adaptation for distributed services and large software systems
Inria Lille - Nord Europe, CRIStAL - Centre de Recherche en Informatique, Signal et Automatique de Lille (CRIStAL) - UMR 9189
3 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
4 LINKS - Linking Dynamic Data
Inria Lille - Nord Europe, CRIStAL - Centre de Recherche en Informatique, Signal et Automatique de Lille (CRIStAL) - UMR 9189
Abstract : 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.
Complete list of metadatas

Cited literature [5 references]  Display  Hide  Download

https://hal-lirmm.ccsd.cnrs.fr/lirmm-02920624
Contributor : Marie-Laure Mugnier <>
Submitted on : Monday, August 24, 2020 - 6:31:11 PM
Last modification on : Tuesday, September 29, 2020 - 12:24:14 PM

File

2006.08467-boundedness.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : lirmm-02920624, version 1
  • ARXIV : 2006.08467

Citation

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⟩

Share

Metrics

Record views

38

Files downloads

23