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

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

Authors: Vince Bárány ; Georg Gottlob ORCID-iD; Martin Otto

    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.

    Volume: Volume 10, Issue 2
    Published on: May 21, 2014
    Accepted on: June 25, 2015
    Submitted on: May 3, 2011
    Keywords: Computer Science - Logic in Computer Science,Computer Science - Databases
    Fundings :
      Source : OpenAIRE Research Graph
    • Domain-centric Intelligent Automated Data Extraction Methodology; Funder: European Commission; Code: 246858

    Linked data

    Source : ScholeXplorer IsCitedBy ARXIV 2008.06824
    Source : ScholeXplorer IsCitedBy DOI 10.1145/3559756
    Source : ScholeXplorer IsCitedBy DOI 10.4230/lipics.icdt.2021.9
    Source : ScholeXplorer IsCitedBy DOI 10.48550/arxiv.2008.06824
    Source : ScholeXplorer IsCitedBy HANDLE 11245.1/832c4278-14a6-4d92-be12-de889584e698
    • 10.1145/3559756
    • 10.48550/arxiv.2008.06824
    • 10.4230/lipics.icdt.2021.9
    • 2008.06824
    • 11245.1/832c4278-14a6-4d92-be12-de889584e698
    Conjunctive Queries: Unique Characterizations and Exact Learnability
    ten Cate, B. ; Dalmau, V. ; Yi, K. ; Wei, Z. ;

    21 Documents citing this article


    Consultation statistics

    This page has been seen 801 times.
    This article's PDF has been downloaded 379 times.