Existential Rules: A Study Through Chase Termination, FO-Rewritability and Boundedness

摘要

Existential rules, also known as Datalog+, are an expressive knowledge representation and reasoning language, which has been mainly investigated in the context of ontological query answering. This talk will first review the landscape of decidable classes of existential rules with respect to two fundamental problems, namely chase termination (does a given set of rules ensure that the chase terminates for any factbase?) and FO-rewritability (does a given set of rules ensure that any conjunctive query can be rewritten as a first-order query?). Regarding the chase, we will specifically focus on four well-known variants: the oblivious chase, the semi-oblivious (or skolem) chase, the restricted chase, and the core chase. We will then study the relationships between chase termination and FO-rewritability, which have been little investigated so far. This study leads us to another fundamental problem, namely boundedness (does a given set of rules ensure that the chase terminates for any factbase within a predefined depth?). The boundedness problem was deeply investigated in the context of datalog. It is known that boundedness and FO-rewritability arc equivalent properties for datalog rules. Such an equivalence does not hold for general existential rules. We will provide a characterization of boundedness in terms of chase termination and FO-rewritability for the oblivious and semi-oblivious chase variants. Interesting questions remain open. This talk will rely on results from the literature and joint work published at ICDT 2019 and IJCAI 2019.