# Querying the Guarded Fragment

arXiv: https://arxiv.org/abs/1309.5822 · HTML: https://mlsanity.com/paper/1309.5822/

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 23 Sep 2013.

## Built on by (most cited first, 6 of 6)

- [Finite Model Theory of the Triguarded Fragment and Related Logics](https://mlsanity.com/paper/2101.08377/) (2021)
- [IID Relaxation by Logical Expressivity: A Research Agenda for Fitting Logics to Neurosymbolic Requirements](https://mlsanity.com/paper/2404.19485/) (2024)
- [Adding Circumscription to Decidable Fragments of First-Order Logic: A Complexity Rollercoaster](https://mlsanity.com/paper/2407.20822/) (2024)
- [Lutz's Spoiler Technique Revisited: A Unified Approach to Worst-Case Optimal Entailment of Unions of Conjunctive Queries in Locally-Forward Description Logics](https://mlsanity.com/paper/2108.05680/) (2021)
- [Finite Entailment of UCRPQs over ALC Ontologies](https://mlsanity.com/paper/2204.14261/) (2022)
- [Decidability of Querying First-Order Theories via Countermodels of Finite Width](https://mlsanity.com/paper/2304.06348/) (2023)

## Abstract (arXiv)

Evaluating a Boolean conjunctive query Q against a guarded first-order theory F is equivalent to checking whether "F and not Q" is unsatisfiable. This problem is relevant to the areas of database theory and description logic. Since Q may not be guarded, well known results about the decidability, complexity, and finite-model property of the guarded fragment do not obviously carry over to conjunctive query answering over guarded theories, and had been left open in general. By investigating finite guarded bisimilar covers of hypergraphs and relational structures, and by substantially generalising Rosati's finite chase, we prove for guarded theories F and (unions of) conjunctive queries Q that (i) Q is true in each model of F iff Q is true in each finite model of F and (ii) determining whether F implies Q is 2EXPTIME-complete. We further show the following results: (iii) the existence of polynomial-size conformal covers of arbitrary hypergraphs; (iv) a new proof of the finite model property of the clique-guarded fragment; (v) the small model property of the guarded fragment with optimal bounds; (vi) a polynomial-time solution to the canonisation problem modulo guarded bisimulation, which yields (vii) a capturing result for guarded bisimulation invariant PTIME.