Restricted Chase Termination for Existential Rules: A Hierarchical Approach and Experimentation

摘要

The chase procedure for existential rules is an indispensable tool for several database applications,where its termination guarantees the decidability of these tasks. Most previous studieshave focused on the skolem chase variant and its termination analysis. It is known that therestricted chase variant is a more powerful tool in termination analysis provided a database isgiven. But all-instance termination presents a challenge since the critical database and similartechniques do not work. In this paper, we develop a novel technique to characterize the activenessof all possible cycles of a certain length for the restricted chase, which leads to the formulationof a framework of parameterized classes of the finite restricted chase, called k-safe(Φ) rule sets.This approach applies to any class of finite skolem chase identified with a condition of acyclicity.More generally, we show that the approach can be applied to the hierarchy of bounded rule setspreviously only defined for the skolem chase. Experiments on a collection of ontologies from theweb show the applicability of the proposed methods on real-world ontologies.