Oblivious and Semi-Oblivious Boundedness for Existential Rules
Oblivious and Semi-Oblivious Boundedness for Existential Rules
Pierre Bourhis, Michel Leclère, Marie-Laure Mugnier, Sophie Tison, Federico Ulliana, Lily Gallois
Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence
Main track. Pages 1581-1587.
https://doi.org/10.24963/ijcai.2019/219
We study the notion of boundedness in the context positive existential rules, that is, wether 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 of rules and outline the complexity of the problem.
Keywords:
Knowledge Representation and Reasoning: Description Logics and Ontologies
Knowledge Representation and Reasoning: Knowledge Representation Languages
Knowledge Representation and Reasoning: Automated Reasoning and Theorem Proving
Knowledge Representation and Reasoning: Logics for Knowledge Representation