pith. sign in

arxiv: 2212.11362 · v7 · pith:OESVGFGFnew · submitted 2022-12-21 · 💻 cs.LO

Tighter Bounds for Query Answering with Guarded TGDs

Antoine Amarilli , Michael Benedikt This is my paper

Pith reviewed 2026-05-24 10:33 UTC · model grok-4.3

classification 💻 cs.LO
keywords guarded TGDsopen-world query answeringconjunctive queriescomplexity boundslinearizationchase procedureEXPTIMENP
0
0 comments X

The pith

Separating guard arity from side-relation arity tightens guarded-TGD query-answering bounds to EXPTIME or NP.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper studies the complexity of open-world conjunctive query answering over incomplete data extended by guarded tuple-generating dependencies. Prior work establishes 2EXPTIME-completeness in general and EXPTIME-completeness once all arities are fixed. The authors introduce a modified linearization technique based on a restricted chase that treats the arity of the guard atom separately from the arity of the remaining relations, called the side signature. This separation yields an EXPTIME upper bound when only the side-signature arity is bounded, and an NP bound when the side signature is fixed and dependency width is bounded.

Core claim

We present a variant of the linearization process for guarded TGDs, making use of a restricted version of the chase, that yields tighter complexity bounds for open-world query answering when the arity of the guard atom and that of the side signature are considered separately. Our results imply that open-world query answering with guarded TGDs can be solved in EXPTIME with arbitrary-arity guard relations if we simply bound the arity of the side signature; and that the complexity drops to NP if we fix the side signature and bound the width of the dependencies.

What carries the argument

Variant linearization process for guarded TGDs that employs a restricted chase procedure to separate guard arity from side-signature arity.

If this is right

  • Open-world query answering with guarded TGDs lies in EXPTIME when guard relations may have arbitrary arity but side-signature arity is bounded.
  • The complexity falls to NP when the side signature is fixed and the width of the dependencies is bounded.
  • The restricted chase maintains correctness of certain-answer computation under the modified linearization.
  • Fixed side signature plus bounded dependency width suffices for membership in NP even with unbounded guard arity.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The arity separation may extend to other existential-rule fragments whose linearizations rely on chase procedures.
  • Database schemas could be engineered to keep side-relation arities small to obtain the EXPTIME bound in practice.
  • The technique suggests that complexity classifications for guarded rules should routinely track guard versus non-guard arities as independent parameters.

Load-bearing premise

The restricted chase correctly computes certain answers and the linearization preserves the complexity reduction when only side-signature arity is bounded.

What would settle it

A guarded TGD set and conjunctive query where the restricted-chase linearization either misses a certain answer or requires more than EXPTIME time despite bounded side arity.

read the original abstract

We consider the complexity of the open-world query answering problem, where we wish to determine certain answers to conjunctive queries over incomplete datasets specified by an initial set of facts and a set of guarded TGDs. This problem has been well-studied in the literature and is decidable but with a high complexity, namely, it is 2EXPTIME complete. Further, the complexity shrinks by one exponential when the arity is fixed. We show in this paper how we can obtain better complexity bounds when considering separately the arity of the guard atom and that of the additional atoms, called the side signature. Our results make use of the technique of linearizing guarded TGDs, introduced in Gottlob, Manna, and Pieris. Specifically, we present a variant of the linearization process, making use of a restricted version of the chase that we recently introduced. Our results imply that open-world query answering with guarded TGDs can be solved in EXPTIME with arbitrary-arity guard relations if we simply bound the arity of the side signature; and that the complexity drops to NP if we fix the side signature and bound the width of the dependencies.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 2 minor

Summary. The paper claims improved complexity bounds for open-world conjunctive query answering under guarded TGDs by separating guard arity from side-signature arity. Using a variant of the linearization technique from Gottlob et al. that incorporates the authors' restricted chase, it asserts that the problem is in EXPTIME when side-signature arity is bounded (arbitrary guard arity) and in NP when the side signature is fixed and dependency width is bounded.

Significance. If the central reduction holds, the results tighten the known 2EXPTIME upper bound and provide a meaningful separation of parameters that could guide practical implementations in database theory. The adaptation of linearization via restricted chase is a technical contribution worth verifying for potential reuse in related decidability results.

major comments (2)
  1. [§4] §4 (Variant Linearization and Restricted Chase): The argument that the variant linearization correctly computes certain answers for the original guarded TGDs (and thus transfers the complexity reduction) rests on the restricted chase omitting no necessary derivations relative to the standard chase when only side-signature arity is bounded. No explicit equation or lemma is cited showing equivalence of the two chases on the linearised instance under this parameter restriction; this is load-bearing for both the EXPTIME and NP claims.
  2. [Theorem 5.1] Theorem 5.1 (or equivalent statement of the EXPTIME bound): The reduction to a linear-TGD instance whose chase is tractable assumes the linearization preserves query equivalence after the restricted-chase step. If the restricted chase is strictly weaker than the standard chase on some guarded TGDs with bounded side arity, the certain-answer computation would be incomplete and the complexity claim would not apply to the original problem.
minor comments (2)
  1. The abstract and introduction could clarify whether the bounded-width assumption for the NP result applies to the original guarded TGDs or only after linearization.
  2. [§2] Notation for the side signature and guard arity should be introduced with an explicit example in §2 to aid readability.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for their thorough review and valuable feedback on our manuscript. We are pleased that the significance of separating guard arity from side-signature arity is recognized. Below we provide point-by-point responses to the major comments, and we commit to revisions that strengthen the technical presentation.

read point-by-point responses

  1. Referee: [§4] §4 (Variant Linearization and Restricted Chase): The argument that the variant linearization correctly computes certain answers for the original guarded TGDs (and thus transfers the complexity reduction) rests on the restricted chase omitting no necessary derivations relative to the standard chase when only side-signature arity is bounded. No explicit equation or lemma is cited showing equivalence of the two chases on the linearised instance under this parameter restriction; this is load-bearing for both the EXPTIME and NP claims.

    Authors: We acknowledge that an explicit lemma would make the argument clearer. In the revised version, we will introduce a new lemma in Section 4 that formally establishes the equivalence between the certain answers obtained via the restricted chase on the linearized instance and those from the standard chase on the original guarded TGDs, under the assumption of bounded side-signature arity. The proof will build on the properties of the restricted chase we introduced in prior work, showing that no derivations relevant to query answering are omitted due to the arity bound restricting the possible join patterns. revision: yes

  2. Referee: [Theorem 5.1] Theorem 5.1 (or equivalent statement of the EXPTIME bound): The reduction to a linear-TGD instance whose chase is tractable assumes the linearization preserves query equivalence after the restricted-chase step. If the restricted chase is strictly weaker than the standard chase on some guarded TGDs with bounded side arity, the certain-answer computation would be incomplete and the complexity claim would not apply to the original problem.

    Authors: The correctness of the reduction in Theorem 5.1 is predicated on the equivalence result from Section 4. By adding the explicit lemma as outlined in our response to the previous comment, we will ensure that the preservation of query equivalence is rigorously documented. We are confident in the correctness because the restricted chase is designed to generate all facts necessary for answering conjunctive queries when the side atoms have bounded arity, as the guard atom handles the main connections. Should there be a specific instance where this fails, we invite the referee to provide it for further analysis. revision: yes

Circularity Check

0 steps flagged

No significant circularity; bounds derived from independent analysis of linearized instances

full rationale

The derivation applies a variant linearization (building on Gottlob-Manna-Pieris and the authors' prior restricted chase) to obtain tighter EXPTIME/NP bounds by separately bounding guard arity vs. side-signature arity and dependency width. This involves new complexity arguments on the resulting linear-TGD instance rather than any self-definitional reduction, fitted-parameter renaming, or load-bearing self-citation chain that collapses the result to its inputs by construction. The cited prior results are external to the present paper and the central claims do not reduce to them tautologically.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

Based solely on the abstract, the results rest on standard definitions of guarded TGDs, the chase procedure, and linearization from prior literature; no free parameters, ad-hoc axioms, or invented entities are introduced in the provided text.

pith-pipeline@v0.9.0 · 5732 in / 1239 out tokens · 42648 ms · 2026-05-24T10:33:41.894657+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

24 extracted references · 24 canonical work pages

  1. [1]

    Amarilli and M

    A. Amarilli and M. Benedikt. When can we answer queries us ing result-bounded data interfaces? PODS, 2018

    work page 2018

  2. [2]

    Amarilli and M

    A. Amarilli and M. Benedikt. When can we answer queries us ing result-bounded data interfaces? LMCS, 18(2), 2022

    work page 2022

  3. [3]

    Baget, M

    J. Baget, M. Lecl` ere, and M. Mugnier. Walking the decida bility line for rules with existential variables. In KR, 2010

    work page 2010

  4. [4]

    B´ ar´ any, M

    V. B´ ar´ any, M. Benedikt, and P. Bourhis. Access patterns and integrity constraints revisited. In ICDT, 2013

    work page 2013

  5. [5]

    B´ ar´ any, M

    V. B´ ar´ any, M. Benedikt, and B. ten Cate. Some model theory of guarded negation. Journal of Symbolic Logic, 2018

    work page 2018

  6. [6]

    Benedikt, P

    M. Benedikt, P. Bourhis, L. Jachiet, and M. Thomazo. Reas oning about disclosure in data integration in the presence of source constraints. In IJCAI, 2019

    work page 2019

  7. [7]

    Benedikt, M

    M. Benedikt, M. Buron, S. Germano, K. Kappelmann, and B. M otik. Rewriting the infinite chase. PVLDB, 2022

    work page 2022

  8. [8]

    Benedikt, M

    M. Benedikt, M. Buron, S. Germano, K. Kappelmann, and B. M otik. Rewriting the infinite chase for guarded TGDs. TODS, 2024

    work page 2024

  9. [9]

    Reasoning in Description Logics using Resolution and Deduc tive Databases

    Boris Motik. Reasoning in Description Logics using Resolution and Deduc tive Databases . PhD thesis, Karlsruhe Institute of Technology, 2006

    work page 2006

  10. [10]

    Cal ` ı, G

    A. Cal ` ı, G. Gottlob, and M. Kifer. Taming the infinite ch ase: Query answering under expressive rela- tional constraints. JAIR, 2013

    work page 2013

  11. [11]

    Cal ` ı, G

    A. Cal ` ı, G. Gottlob, and T. Lukasiewicz. A general Data log-based framework for tractable query an- swering over ontologies. Journal of Web Semantics , 14, 2012

    work page 2012

  12. [12]

    Cal ` ı, G

    A. Cal ` ı, G. Gottlob, T. Lukasiewicz, and A. Pieris. A lo gical toolbox for ontological reasoning. SIGMOD Record, 40(3), 2011

    work page 2011

  13. [13]

    Cal ` ı, D

    A. Cal ` ı, D. Lembo, and R. Rosati. Query rewriting and an swering under constraints in data integration systems. In IJCAI, 2003

    work page 2003

  14. [14]

    B. t. Cate and M. Franceschet. Guarded fragments with co nstants. Journal of Logic, Language and Information, 14(3), 2005

    work page 2005

  15. [15]

    Deutsch, B

    A. Deutsch, B. Lud¨ ascher, and A. Nash. Rewriting queri es using views with access patterns under integrity constraints. TCS, 371(3), 2007. 38 TIGHTER BOUNDS FOR QUERY ANSWERING WITH GUARDED TGDS

    work page 2007

  16. [16]

    Fagin, P

    R. Fagin, P. G. Kolaitis, R. J. Miller, and L. Popa. Data e xchange: Semantics and query answering. TCS, 336(1), 2005

    work page 2005

  17. [17]

    Gottlob, M

    G. Gottlob, M. Manna, and A. Pieris. Polynomial combine d rewritings for existential rules. In KR, 2014

    work page 2014

  18. [18]

    Gottlob, M

    G. Gottlob, M. Manna, and A. Pieris. Multi-head guarded existential rules over fixed signatures. In KR, 2020

    work page 2020

  19. [19]

    D. S. Johnson and A. C. Klug. Testing containment of conj unctive queries under functional and inclusion dependencies. JCSS, 28(1), 1984

    work page 1984

  20. [20]

    Kappelmann

    K. Kappelmann. Decision procedures for guarded logics , 2019. https://arxiv.org/abs/1911.03679

    work page arXiv 2019

  21. [21]

    L. Libkin. Elements of Finite Model Theory . Springer, 1995

    work page 1995

  22. [22]

    Lukasiewicz, M

    T. Lukasiewicz, M. V. Martinez, A. Pieris, and G. I. Sima ri. From classical to consistent query answering under existential rules. In AAAI, 2015

    work page 2015

  23. [23]

    Maier, A

    D. Maier, A. O. Mendelzon, and Y. Sagiv. Testing implica tions of data dependencies. TODS, 4(4), 1979

    work page 1979

  24. [24]

    A. Onet. The chase procedure and its applications in dat a exchange. In Data Exchange, Integration, and Streams, 2013. Appendix A. Proof of the Semi-Width Result (Proposition 2.7) In this appendix, we prove the NP bound on OWQA for bounded semi-width linear TGDs, i.e., Proposition 2.7. Recall its statement: Proposition 2.7. For fixed w, there is an NP algo...

    work page 2013