Paper Info
Title
On The K-Boundedness For Existential Rules
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 an upper bound on the depth 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. After introducing a general framework which motivates a breadth-first approach to problems related to chase termination for any chase variant, we prove that k-boundedness is decidable for three chase variants.
Year
DOI
Venue
2018
10.1007/978-3-319-99906-7_4
RULES AND REASONING (RULEML+RR 2018)
DocType
Volume
ISSN
Journal
11092
0302-9743
Citations 
PageRank 
References 
0
0.34
13
Authors
4
Name
Order
Citations
PageRank
Stathis Delivorias100.34
Michel Leclère235927.21
Marie-laure Mugnier385980.16
Federico Ulliana4316.57