The chase is a ubiquitous algorithm in database theory. However, for existential rules (aka tuple-generating dependencies), its termination is not guaranteed, and even undecidable in general. The problem of termination becomes particularly difficult for the restricted (or standard) chase, for which the order of rule application matters. Thus, decidability of restricted chase termination is still open for many well-behaved classes such as linear or guarded multi-headed rules. We make a step forward by showing that all-instances restricted chase termination is decidable in the linear multi-headed case.

The chase is a fundamental algorithm with ubiquitous uses in database theory. Given a database and a set of existential rules (aka tuple-generating dependencies), it iteratively extends the database to ensure that the rules are satisfied in a most general way. This process may not terminate, and a major problem is to decide whether it does. This problem has been studied for a large number of chase variants, which differ by the conditions under which a rule is applied to extend the database. Surprisingly, the complexity of the universal termination of the restricted (aka standard) chase is not fully understood. We close this gap by placing universal restricted chase termination in the analytical hierarchy. This higher hardness is due to the fairness condition, and we propose an alternative condition to reduce the hardness of universal termination.

This paper addresses one of the fundamental open questions in the realm of existential rules: the conjecture on the finite controllability of bounded derivation depth rule sets (bdd⇒fc). We take a step toward a positive resolution of this conjecture by demonstrating that universal models generated by BDD rule sets cannot contain arbitrarily large tournaments (arbitrarily directed cliques) without entailing a loop query, ∃ E (x,x). This simple yet elegant result narrows the space of potential counterexamples to the (bdd⇒fc) conjecture.

Ontology-based query answering is a problem that takes as input a set of facts F, an ontology R (typically expressed by existential rules), a Boolean query q , and asks whether R and F entails q. This problem is undecidable in general, and a widely investigated approach to tackle it is called query rewriting: from (R,q) (a ``rule query'') is computed q_R such that for any set of facts F, it holds that R and F entail q iff F entails q_R. The literature mostly focused on q_R expressed as a union of conjunctive queries (UCQs), and an algorithm that such a q_R whenever it exists has been proposed in the literature. However, UCQ-rewritability is applicable only in restricted settings. This raises the question whether such a generic algorithm can be designed for a more expressive language, such as datalog. We solve this question by the negative, by studying the difference between datalog-expressibility and datalog-rewritability. In particular, we show that query answering under datalog-expressible rule queries is undecidable.