Querying the Guarded Fragment
Authors:
- Vince BárányVBVince Bárány
- Georg GottlobGGGeorg Gottlob
- Martin OttoMOMartin Otto
- 1 July 2010
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- Vol. 10 (10436871) , 1-10
Abstract
Evaluating a boolean conjunctive query q over a guarded first-order theory T is equivalent to checking whether (T & 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 T and (unions of) conjunctive queries q that (i) T implies q iff T implies q over finite models, that is, iff q is true in each finite model of T and (ii) determining whether T 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 16 references indexed in Scilit:
- Highly Acyclic Groups, Hypergraph Covers and the Guarded Fragment2010
- Tractable query answering and rewriting under description logic constraintsJournal of Applied Logic, 2010
- A general datalog-based framework for tractable query answering over ontologies2009
- Data exchange: semantics and query answeringTheoretical Computer Science, 2005
- Finite Conformal Hypergraph Covers and Gaifman Cliques in Finite StructuresThe Bulletin of Symbolic Logic, 2003
- Loosely Guarded Fragment of First-Order Logic has the Finite Model PropertyStudia Logica, 2002
- Decision Procedures for Guarded LogicsLecture Notes in Computer Science, 1999
- A Proof Procedure for Data DependenciesJournal of the ACM, 1984
- Testing containment of conjunctive queries under functional and inclusion dependenciesJournal of Computer and System Sciences, 1984
- The implication problem for data dependencies1981