Abstract
Ensuring the termination of the "chase" algorithm is a fundamental challenge in reasoning with existential rules, particularly when equality is involved. This paper introduces Equality Model-Faithful Acyclicity (EMFA), a novel, highly efficient criterion that directly handles equality to guarantee chase termination. We prove that existing termination checks can be applied to axiomatized versions of rules and demonstrate that EMFA avoids the performance penalties associated with traditional methods while maintaining high expressive power.
Introduction
In knowledge representation, existential rules are used to describe complex relationships, such as "Every person has a parent who is also a person." The chase algorithm is the standard tool for answering queries against these rules by repeatedly applying them to derive new facts. However, the chase is not guaranteed to terminate, potentially leading to infinite loops of object creation.
To address this, researchers use "acyclicity notions"—mathematical checks that ensure termination. While many such checks exist for rules without equality ($x \approx y$), equality is present in approximately 34% of common ontologies and significantly complicates the process. Previous approaches required "axiomatizing" equality—treating it as a standard predicate and adding rules for reflexivity, symmetry, transitivity, and congruence. This method is computationally expensive and often causes termination checks to fail unnecessarily.
Methodology
The authors propose a multi-faceted approach to improve termination checking:
- Theoretical Bridge: A proof that if the chase terminates on an "axiomatized" version of an ontology, it is guaranteed to terminate on the original ontology. This allows for the use of optimized reasoning engines on the original rules while using axiomatized versions solely for safety checks.
- Equality Model-Faithful Acyclicity (EMFA): A direct extension of Model-Faithful Acyclicity (MFA) that handles equality natively. EMFA simulates the chase's behavior, including term merging, to detect potential infinite loops without the overhead of explicit axiomatization.
- Complexity: The check for EMFA is shown to be 2EXPTIME-complete, matching the complexity of standard MFA for rules without equality.
- Implementation: The checks were integrated into the VLog high-performance rule engine.
Experimental Evaluation
The approach was evaluated using two primary datasets:
- MOWLCorp: A web crawl containing 565 rule sets.
- Oxford Ontology Repository (OOR): A curated library of 131 logical theories.
- DBPedia & Claros: Used to benchmark reasoning speed (the chase itself) against the termination check.
Results and Discussion
The experimental results demonstrate that EMFA provides a superior balance of coverage and efficiency.
Coverage and Efficiency
In the MOWLCorp dataset, EMFA successfully identified 387 out of 565 rule sets as terminating. Crucially, the EMFA check is significantly faster than the traditional "MFA + singularization" approach, requiring only 35% to 60% of the computation time.
Reasoning Speedup
The ability to prove termination allows for the use of a "renaming" chase, which handles equality via rewriting rather than axioms. This leads to massive performance gains. For instance, on the DBPedia ontology, the renaming chase completed in 27.5 seconds, compared to 590 seconds for the axiomatized version—a speedup of over 20x.
Conclusion
EMFA represents a significant advancement in ensuring chase termination for ontologies with equality. By avoiding the performance bottlenecks of axiomatization while maintaining high coverage, it enables more robust and efficient reasoning in real-world knowledge bases. Future work will explore extending these notions to the Restricted Chase and developing "cyclicity" checks to definitively identify non-terminating rule sets.
Summary updated