TL;DR
This paper tackles the challenge of determining whether a reasoning process called the "restricted chase" will eventually halt when dealing with complex ontology rules that include disjunctions. They introduce novel criteria for both ensuring termination (acyclicity) and detecting non-termination (cyclicity), significantly improving upon existing methods and empirically demonstrating their effectiveness on real-world ontologies.
What Problem Does This Paper Address?
Ontologies, which are formal representations of knowledge, often use rules to define relationships between concepts. A key task in ontology reasoning is answering queries, which involves inferring new facts based on these rules and existing data. The "chase" is a fundamental algorithm for this, but it can run indefinitely, especially when rules are complex. This paper focuses on "existential rules with disjunctions," a powerful formalism that captures many features of popular ontology languages like OWL. The core problem is that determining whether the chase will always terminate for such rules is undecidable. Existing methods for simpler rule types are often insufficient or too pessimistic for these more expressive rules. The authors aim to develop better criteria to precisely identify when the chase will terminate and, crucially, when it won't.
Methods
The paper introduces several new criteria for analyzing the termination behavior of the restricted chase:
- Restricted Joint Acyclicity (RJA): An adaptation of existing acyclicity notions for deterministic rules. It uses a dependency graph between existential variables to detect cycles that would lead to infinite derivations.
- Restricted Model-Faithful Acyclicity (RMFA): This criterion extends the concept of "model-faithful acyclicity" to handle disjunctions and the restricted chase. It involves a modified chase on a "critical instance" of the data, incorporating a "blocking" mechanism to prevent rules from being applied if their heads are already satisfied.
- Restricted Model-Summarising Acyclicity (RMSA): A simpler criterion that aims to be more general than RJA while being computationally less demanding than RMFA. It uses fresh constants and a special relation to track potential cycles.
- Cyclicity Criteria (MFC and RMFC): For the first time, the authors propose criteria to prove non-termination. These methods look for specific patterns (cyclic terms) that emerge during a chase process, indicating that the process will necessarily continue infinitely for certain inputs.
Datasets
The authors evaluated their criteria using the MOWLCorp corpus, a large collection of real-world OWL ontologies. They transformed these ontologies into rule sets, excluding those with nominals or at-most-restrictions. The final dataset comprised 1,576 ontologies with up to 1,000 existential quantifiers after normalization.
Key Insights and Ideas
- Disjunctions complicate termination: The presence of disjunctions in rules makes existing termination criteria less effective and introduces new challenges for analyzing chase behavior.
- Acyclicity is not enough: While acyclicity criteria are good for proving termination, they often fail to classify many realistic ontologies. The paper's new criteria (RMFA, RMSA) are more general and capture more terminating cases.
- Non-termination is detectable: The most significant novelty is the introduction of criteria (MFC, RMFC) to prove that a chase will be infinite. This is crucial because undecidability means we can't always prove termination, but proving non-termination is equally important for understanding reasoning limits.
- Empirical validation is key: The authors demonstrate that their new criteria significantly improve classification rates on real-world ontologies, showing that a substantial portion of "open" cases (where termination couldn't be proven) are actually cyclic.
Key Results
- The proposed criteria (RJA, RMFA, RMSA) are shown to be more general than existing ones, classifying a larger percentage of ontologies.
- Their combined approach (RMFA and RMFC) can decide termination for 84.2% of the tested ontologies.
- For deterministic rules, their methods characterize 96.3% of ontologies as either acyclic or cyclic.
- A significant portion of ontologies that were previously unclassifiable are now identified as cyclic by the new criteria.
- The paper provides complexity results for their criteria, showing they are generally in EXPTIME or coN2EXPTIME, with some cases becoming P-complete or coNP-complete for bounded arities or variables.
Limitations and Future Work
- Undecidability remains: While the paper significantly improves classification rates, the fundamental undecidability of chase termination for existential rules with disjunctions means there will always be some ontologies that remain unclassified.
- Future work directions: The authors suggest that their work provides a strong foundation for developing more practical chase-based reasoners. They highlight that many existing OWL reasoners already use chase-like algorithms, and their criteria could be integrated to improve their capabilities. Further research could focus on integrating these criteria into existing reasoners and exploring their application to other expressive ontology languages.
Summary updated