Abstract: 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.
Recommendations
- Querying the guarded fragment with transitivity
- Guarded fragments with constants
- The guarded fragment with transitive guards
- Deciding the guarded fragments by resolution
- One-dimensional guarded fragments
- scientific article; zbMATH DE number 1303345
- Interpolation and definability in guarded fragments
- PROBABILISTIC ROLE MODELS AND THE GUARDED FRAGMENT
- scientific article; zbMATH DE number 1254010
- scientific article; zbMATH DE number 1950259
Cited in
(25)- Logical separability of labeled data examples under ontologies
- On the data complexity of consistent query answering
- Recent advances in Datalog^
- Querying the unary negation fragment with regular path expressions
- Towards more expressive ontology languages: the query answering problem
- Finite satisfiability for guarded fixpoint logic
- Finite model reasoning over existential rules
- SOME MODEL THEORY OF GUARDED NEGATION
- Guarded-based disjunctive tuple-generating dependencies
- Guarded Ontology-Mediated Queries
- Semiring Provenance for Guarded Logics
- One-dimensional guarded fragments
- When can we answer queries using result-bounded data interfaces?
- scientific article; zbMATH DE number 7104937 (Why is no real title available?)
- Reasoning on anonymity in Datalog+/--
- Querying the guarded fragment with transitivity
- Guarded negation
- Guarded negation
- Answer Counting under Guarded TGDs
- Saturation-based Boolean conjunctive query answering and rewriting for the guarded quantification fragments
- How to tell easy from hard: complexities of conjunctive query entailment in extensions of \(\mathcal{ALC}\)
- Finite-model reasoning for graph queries and description logics
- Decidability of querying first-order theories via countermodels of finite width
- Conjunctive queries: unique characterizations and exact learnability
- A more general theory of static approximations for conjunctive queries
This page was built for publication: Querying the Guarded Fragment
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5417742)
