Abstract
We consider entailment problems involving powerful constraint languages such as guarded existential rules, in which additional semantic restrictions are put on a set of distinguished relations. We consider restricting a relation to be transitive, restricting a relation to be the transitive closure of another relation, and restricting a relation to be a linear order. We give some natural generalizations of guardedness that allow inference to be decidable in each case, and isolate the complexity of the corresponding decision problems. Finally we show that slight changes in our conditions lead to undecidability.
Introduction
In automated reasoning and database theory, balancing expressivity and decidability is a fundamental challenge. Existential rules, or Tuple Generating Dependencies (TGDs), are widely used for knowledge representation. While general TGDs lead to undecidability in query answering (QA), the "guarded" fragment—where variables in a rule are constrained by a single "guard" atom—remains decidable. However, real-world data often involves semantics like transitivity (e.g., "part-of" hierarchies) and linear orders (e.g., temporal sequences) that standard guarded logic struggles to handle without losing decidability.
Fragments and Methodology
The authors introduce a hierarchy of logic fragments to safely incorporate these semantic properties. The core innovation lies in two structural restrictions:
- Base-Guardedness: The schema is partitioned into "base" relations and "distinguished" relations (transitive or ordered). A rule is base-guarded if its variables are guarded by a base relation, preventing distinguished relations from acting as primary guards.
- Base-Coveredness: For linear orders, a stricter condition is required. A rule or query is base-covered if every ordered relationship is "covered" by a standard base relation.
To establish decidability, the authors prove that satisfied queries possess "tree-like witnesses," allowing the use of 2-way alternating parity tree automata for decision procedures. For linear orders, they employ "axiom compilation" to simulate ordered behavior within a guarded framework.
Key Results
The research provides a comprehensive taxonomy of complexity for these new fragments across different semantic restrictions: transitivity (QAtr), transitive closure (QAtc), and linear orders (QAlin).
Key findings include:
- Combined Complexity: For the broad BaseGNF fragment, QA remains 2EXPTIME-complete, matching standard guarded logic. This indicates that the extra semantic power comes without increasing worst-case combined complexity.
- Data Complexity: Most fragments are CoNP-complete. However, the BaseCovFGTGD fragment achieves PTIME data complexity for transitivity, a significant result for scalable database applications.
- Undecidability Boundaries: The authors prove that if these "base" restrictions are relaxed even slightly (e.g., allowing a transitive relation to be a guard), the problem immediately becomes undecidable.
Conclusion
This work identifies new decidable "sweet spots" for reasoning with ordered data by introducing base-guardedness and base-coveredness. While the results are theoretically robust, practical implementation remains a challenge due to the complexity of tree automata. Future research may focus on finite entailment and developing more efficient chase-based algorithms for these fragments.
Summary updated