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.
Type de document :
Communication dans un congrès
RuleML+RR: Rules and Reasoning, Sep 2018, Luxembourg, Luxembourg. International Joint Conference on Rules and Reasoning, LNCS (11092), pp.48-64, 〈10.1007/978-3-319-99906-7_4〉
Liste complète des métadonnées

https://hal-lirmm.ccsd.cnrs.fr/lirmm-01921140
Contributeur : Efstathios Delivorias <>
Soumis le : mardi 13 novembre 2018 - 16:12:20
Dernière modification le : mercredi 12 décembre 2018 - 14:38:02

Fichier

1810.09304.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

Citation

Stathis Delivorias, Michel Leclère, Marie-Laure Mugnier, Federico Ulliana. On the k-Boundedness for Existential Rules. RuleML+RR: Rules and Reasoning, Sep 2018, Luxembourg, Luxembourg. International Joint Conference on Rules and Reasoning, LNCS (11092), pp.48-64, 〈10.1007/978-3-319-99906-7_4〉. 〈lirmm-01921140〉

Partager

Métriques

Consultations de la notice

45

Téléchargements de fichiers

14