Oblivious and Semi-Oblivious Boundedness for Existential Rules
This work addresses a foundational issue in knowledge representation and database theory, providing theoretical insights for rule-based systems, though it is incremental in nature.
The paper tackles the problem of determining boundedness for existential rules, specifically whether the chase procedure depth has an upper bound independent of the initial instance, and shows that boundedness is decidable for several classes with outlined complexity.
We study the notion of boundedness in the context of positive existential rules, that is, whether there exists an upper bound to the depth of the chase procedure, that is independent from the initial instance. By focussing our attention on the oblivious and the semi-oblivious chase variants, we give a characterization of boundedness in terms of FO-rewritability and chase termination. We show that it is decidable to recognize if a set of rules is bounded for several classes and outline the complexity of the problem. This report contains the paper published at IJCAI 2019 and an appendix with full proofs.