Introduction
In automated reasoning and database theory, there is a fundamental tension between expressivity (the power of a logic to describe complex relationships) and decidability (the ability of a computer to provide a definitive answer in finite time). The "Query Answering" (QA) problem—determining if a query is necessarily true given a set of facts and logical rules—is central to this field. While powerful, rules like Tuple Generating Dependencies (TGDs) often lead to undecidability.
Researchers have long known that "guarding" these rules—ensuring variables in a rule's body appear together in a single "guard" atom—can restore decidability. However, standard guarded logics struggle with common data properties like transitivity (e.g., "if A is a part of B and B is a part of C, then A is a part of C") and linear orders (e.g., timestamps). This paper identifies the specific structural conditions under which these properties can be safely integrated into guarded logics.
A New Taxonomy of Fragments
To navigate this landscape, the authors introduce a hierarchy of logical fragments that extend the Guarded Negation Fragment (GNF) and Frontier-Guarded TGDs (FGTGD). By applying specific restrictions, they define new "sweet spots" for decidable query answering.
As shown in the taxonomy above, these new fragments—such as BaseGNF and BaseCovFGTGD—bridge the gap between highly expressive but undecidable logics and more restrictive, decidable ones.
Methodology: Base-Guardedness and Base-Coveredness
The core contribution of the paper is the introduction of two key structural restrictions:
- Base-Guardedness: Applied to transitive relations, this rule dictates that while transitive relations can be used in the logic, they cannot serve as "guards." The structural backbone of the rules must be formed by standard, non-transitive "base" relations.
- Base-Coveredness: A stricter requirement for linear orders (like $x < y$). It mandates that every time an ordered relation appears in a rule, it must be "covered" by a standard base atom containing all its variables.
To prove these restrictions work, the authors utilize Tree Automata for transitivity, searching for tree-like counterexamples to query entailment. For linear orders, they use a Reduction Technique to compile the requirements into standard guarded logic axioms.
Complexity Results
The paper provides a detailed complexity map for these new fragments, demonstrating that the added expressivity often comes without increasing the worst-case complexity class compared to standard guarded logics.
Key findings from the complexity analysis include:
- Combined Complexity: For both transitive and linear-ordered data under these restrictions, query answering is 2EXPTIME-complete, matching the complexity of the standard Guarded Negation Fragment.
- Data Complexity: When rules are fixed, the problem is generally coNP-complete. However, for the "Base-Covered Frontier-Guarded TGDs" (BaseCovFGTGD) fragment, the data complexity for transitive relations drops to PTIME, suggesting potential for large-scale database applications.
- Undecidability: The results also highlight the fragility of decidability; for fragments like BaseGNF and BaseFGTGD, query answering with linear orders (QAlin) remains undecidable.
Theoretical Insights and Future Work
The most profound insight is that the "danger" of transitivity and ordering arises when they are used to define the structure of the model. By banning them from the guard position, the authors preserve the "tree-likeness" of the models, which is essential for decidability. Furthermore, the paper demonstrates that these results hold even for transitive closure, a significant boost in expressive power for practical applications.
Future research directions include exploring finite model entailment, as the current proofs apply to general entailment (including infinite models). Additionally, while the theoretical bounds are established, developing efficient, real-world implementations of these automata-based algorithms remains a significant engineering challenge.
Summary updated