Abstract
Reasoning with disjunctive existential rules often relies on the Skolem chase, a procedure whose termination is undecidable. This paper introduces two novel theoretical tools, Disjunctive Model-Faithful Acyclicity (DMFA) and Disjunctive Model-Faithful Cyclicity (DMFC), designed to predict chase termination and non-termination, respectively. By incorporating the concept of blockedness and head-choices, these notions significantly tighten the approximation of the chase. Empirical evaluations on real-world datasets—OXFD, ORE15, and MOWL—demonstrate that our methods can successfully classify nearly 99% of tested rule sets where previous methods struggled, marking a significant advancement in the practical analysis of disjunctive rule sets.
Introduction
In knowledge representation and the Semantic Web, existential rules are essential for describing complex relationships. To answer queries against these rules, the Skolem chase algorithm materializes new facts. However, the introduction of new objects by existential rules can lead to infinite loops, making chase termination an undecidable problem. Researchers typically employ "acyclicity notions" to prove termination and "cyclicity notions" to prove non-termination.
While effective for simple rules, existing notions like Model-Faithful Acyclicity (MFA) and Model-Faithful Cyclicity (MFC) perform poorly on disjunctive rules—rules where the conclusion contains logical disjunctions (OR). Previous benchmarks showed that these tools often left a significant gap in our ability to predict reasoner behavior, failing to classify a large portion of real-world rule sets.
Methodology
This work introduces two primary notions specifically tailored for the disjunctive Skolem chase:
Disjunctive Model-Faithful Acyclicity (DMFA)
DMFA enhances the standard MFA by incorporating "blockedness." It identifies "harmless" triggers—logical paths that appear to cause loops but are structurally impossible to activate during an actual chase. By filtering out these "ghost loops," DMFA provides a much more accurate proof of termination. The authors also developed an optimized variant, $DMFA^k$, for practical use.
Disjunctive Model-Faithful Cyclicity (DMFC)
To handle the non-deterministic nature of disjunctions, DMFC utilizes "head-choices." It identifies specific branches within a disjunction that, if followed, are guaranteed to lead to an infinite chain of new objects. This allows for a robust proof of non-termination even in complex branching scenarios. The practical implementation used in testing is denoted as $DMFC^s$.
Both DMFA and DMFC are theoretically complex (2EXPTIME-complete), but the optimized versions allow for efficient evaluation on large-scale datasets.
Experimental Evaluation
The proposed notions were evaluated using three major ontology repositories converted into disjunctive existential rules: the Oxford Ontology Repository (OXFD), the OWL Reasoner Evaluation 2015 dataset (ORE15), and the Manchester OWL Corpus (MOWL). These datasets represent diverse real-world logic problems from the Semantic Web and bio-ontologies.
As shown in the results in the table above, the new notions provide a massive leap in performance. On the ORE15 dataset, while MFA and MFC only classified approximately 58% of the rule sets, the combination of $DMFA^2$ and $DMFC^s$ classified over 99% of the instances that finished within the timeout. Similar improvements were observed in the MOWL dataset, where coverage increased from approximately 60% to 97%. The $DMFA^2$ variant was particularly effective at proving termination for complex ontologies that appeared cyclic under less sophisticated analysis.
Conclusion
The introduction of DMFA and DMFC significantly advances the state-of-the-art in predicting the termination of the disjunctive Skolem chase. By accounting for blockedness and non-deterministic branching, these tools provide near-complete coverage of real-world datasets. Future work will focus on extending these notions to the "restricted chase," which avoids redundant fact materialization, and developing "fact-dependent" notions that can distinguish between rule sets that loop only under specific initial conditions.
Summary updated