Oblivious and Semi-Oblivious Boundedness for Existential Rules

Pierre Bourhis, Michel Leclère, Marie-Laure Mugnier, Sophie Tison, Federico Ulliana, Lily Gallois

IJCAI 2019 pp. 1581-1587

doi:10.24963/IJCAI.2019/219 /ijcai/2019/bourhis2019ijcai-oblivious/

Abstract

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.

PDF IJCAI Semantic Scholar

Cite

Text

Bourhis et al. "Oblivious and Semi-Oblivious Boundedness for Existential Rules." International Joint Conference on Artificial Intelligence, 2019. doi:10.24963/IJCAI.2019/219

Markdown

[Bourhis et al. "Oblivious and Semi-Oblivious Boundedness for Existential Rules." International Joint Conference on Artificial Intelligence, 2019.](https://mlanthology.org/ijcai/2019/bourhis2019ijcai-oblivious/) doi:10.24963/IJCAI.2019/219

BibTeX

@inproceedings{bourhis2019ijcai-oblivious,
  title     = {{Oblivious and Semi-Oblivious Boundedness for Existential Rules}},
  author    = {Bourhis, Pierre and Leclère, Michel and Mugnier, Marie-Laure and Tison, Sophie and Ulliana, Federico and Gallois, Lily},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year      = {2019},
  pages     = {1581-1587},
  doi       = {10.24963/IJCAI.2019/219},
  url       = {https://mlanthology.org/ijcai/2019/bourhis2019ijcai-oblivious/}
}