On the k-Boundedness for Existential Rules

Stathis Delivorias 1 Michel Leclère 1 Marie-Laure Mugnier 1 Federico Ulliana 1
1 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
Abstract : The chase is a fundamental tool for existential rules. Several chase variants are known, which differ on how they handle redundancies possibly caused by the introduction of nulls. Given a chase variant, the halting problem takes as input a set of existential rules and asks if this set of rules ensures the termination of the chase for any factbase. It is well-known that this problem is undecidable for all known chase variants. The related problem of boundedness asks if a given set of existential rules is bounded, i.e., whether there is a predefined upper bound on the number of (breadth-first) steps of the chase, independently from any factbase. This problem is already undecidable in the specific case of datalog rules. However , knowing that a set of rules is bounded for some chase variant does not help much in practice if the bound is unknown. Hence, in this paper, we investigate the decidability of the k-boundedness problem, which asks whether a given set of rules is bounded by an integer k. We prove that k-boundedness is decidable for three chase variants, namely the oblivious, semi-oblivious and restricted chase.
Complete list of metadatas

Cited literature [23 references]  Display  Hide  Download

https://hal-lirmm.ccsd.cnrs.fr/lirmm-01921140
Contributor : Efstathios Delivorias <>
Submitted on : Tuesday, November 13, 2018 - 4:12:20 PM
Last modification on : Friday, July 5, 2019 - 8:21:09 PM
Long-term archiving on : Thursday, February 14, 2019 - 3:46:49 PM

File

1810.09304.pdf
Files produced by the author(s)

Identifiers

Collections

Citation

Stathis Delivorias, Michel Leclère, Marie-Laure Mugnier, Federico Ulliana. On the k-Boundedness for Existential Rules. RuleML+RR, Sep 2018, Luxembourg, Luxembourg. pp.48-64, ⟨10.1007/978-3-319-99906-7_4⟩. ⟨lirmm-01921140⟩

Share

Metrics

Record views

142

Files downloads

128