Skip to Main content Skip to Navigation
Conference papers

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 Gallois 4, 5
2 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
5 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 contextof positive existential rules, that is, whether thereexists an upper bound to the depth of the chase pro-cedure, that is independent from the initial instance.By focussing our attention on the oblivious and thesemi-oblivious chase variants, we give a character-ization of boundedness in terms of FO-rewritabilityand chase termination. We show that it is decidableto recognize if a set of rules is bounded for several classes and outline the complexity of the problem.
Document type :
Conference papers
Complete list of metadatas

Cited literature [4 references]  Display  Hide  Download

https://hal-lirmm.ccsd.cnrs.fr/lirmm-02148142
Contributor : Michel Leclère <>
Submitted on : Wednesday, June 5, 2019 - 11:52:54 AM
Last modification on : Monday, January 27, 2020 - 2:00:02 PM

File

camera_ready.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : lirmm-02148142, version 1

Citation

Pierre Bourhis, Michel Leclère, Marie-Laure Mugnier, Sophie Tison, Federico Ulliana, et al.. Oblivious and Semi-Oblivious Boundedness for Existential Rules. IJCAI 2019 - International Joint Conference on Artificial Intelligence, Aug 2019, Macao, China. ⟨lirmm-02148142⟩

Share

Metrics

Record views

263

Files downloads

321