  Existential rules are a positive fragment of first-order logic that
generalizes function-free Horn rules by allowing existentially quantified
variables in rule heads. This family of languages has recently attracted
significant interest in the context of ontology-mediated query answering.
Forward chaining, also known as the chase, is a fundamental tool for computing
universal models of knowledge bases, which consist of existential rules and
facts. Several chase variants have been defined, which differ on the way they
handle redundancies. A set of existential rules is bounded if it ensures the
existence of a bound on the depth of the chase, independently from any set of
facts. Deciding if a set of rules is bounded is an undecidable problem for all
chase variants. Nevertheless, when computing universal models, knowing that a
set of rules is bounded for some chase variant does not help much in practice
if the bound remains unknown or even very large. Hence, we investigate the
decidability of the k-boundedness problem, which asks whether the depth of the
chase for a given set of rules is bounded by an integer k. We identify a
general property which, when satisfied by a chase variant, leads to the
decidability of k-boundedness. We then show that the main chase variants
satisfy this property, namely the oblivious, semi-oblivious (aka Skolem), and
restricted chase, as well as their breadth-first versions. This paper is under
consideration for publication in Theory and Practice of Logic Programming.
