On the k-Boundedness for Existential Rules - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Access content directly
Conference Papers Year : 2018

On the k-Boundedness for Existential Rules

Stathis Delivorias
  • Function : Author
  • PersonId : 1038859
Michel Leclère
Federico Ulliana


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.
Fichier principal
Vignette du fichier
1810.09304.pdf (201.88 Ko) Télécharger le fichier
Origin : Files produced by the author(s)

Dates and versions

lirmm-01921140 , version 1 (13-11-2018)



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⟩
141 View
169 Download



Gmail Facebook X LinkedIn More