Query Answering with Transitive and Linear-Ordered Data

Antoine Amarilli, Michael Benedikt, Pierre Bourhis, Michael Vanden Boom

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:

  1. 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.
  2. 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.
Hierarchy of fragments and their relationships.

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).

Complexity results for query answering across various fragments and semantic restrictions.

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

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.
BibTeX
@article{amarilli2018query,
  author = {Antoine Amarilli and Michael Benedikt and Pierre Bourhis and Michael Vanden Boom},
  title = {{Query Answering with Transitive and Linear-Ordered Data}},
  journal = {J. Artif. Intell. Res.},
  year = {2018},
  doi = {10.1613/jair.1.11240},
}
Figure