Bárány, Vince and Gottlob, Georg and Otto, Martin - Querying the Guarded Fragment

lmcs:675 - Logical Methods in Computer Science, May 21, 2014, Volume 10, Issue 2
Querying the Guarded Fragment

Authors: Bárány, Vince and Gottlob, Georg and Otto, Martin

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.

Source : oai:arXiv.org:1309.5822
DOI : 10.2168/LMCS-10(2:3)2014
Volume: Volume 10, Issue 2
Published on: May 21, 2014
Submitted on: May 3, 2011
Keywords: Computer Science - Logic in Computer Science,Computer Science - Databases


Consultation statistics

This page has been seen 211 times.
This article's PDF has been downloaded 78 times.