Querying the Guarded Fragment
Authors:
- Vince BárányVBVince Bárány
- Georg GottlobGGGeorg Gottlob
- Martin OttoMOMartin Otto
Preprint
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.Keywords
All Related Versions
This publication has 22 references indexed in Scilit:
- On the finite controllability of conjunctive query answering in databases under open-world assumptionJournal of Computer and System Sciences, 2011
- Tractable query answering and rewriting under description logic constraintsJournal of Applied Logic, 2010
- Tractable Reasoning and Efficient Query Answering in Description Logics: The DL-Lite FamilyJournal of Automated Reasoning, 2007
- Complexity of the Two-Variable Fragment with Counting QuantifiersJournal of Logic, Language and Information, 2005
- The complexity of finite model reasoning in description logicsInformation and Computation, 2005
- Robbers, marshals, and guards: game theoretic and logical characterizations of hypertree widthJournal of Computer and System Sciences, 2003
- Extending partial isomorphisms on finite structuresCombinatorica, 1995
- Relational queries computable in polynomial timeInformation and Control, 1986
- Testing containment of conjunctive queries under functional and inclusion dependenciesJournal of Computer and System Sciences, 1984
- The implication problem for data dependencies1981