Cristina Feier ; Carsten Lutz ; Marcin Przybyłko - Answer Counting under Guarded TGDs

lmcs:8768 - Logical Methods in Computer Science, September 14, 2023, Volume 19, Issue 3 - https://doi.org/10.46298/lmcs-19(3:16)2023
Answer Counting under Guarded TGDsArticle

Authors: Cristina Feier ; Carsten Lutz ; Marcin Przybyłko

    We study the complexity of answer counting for ontology-mediated queries and for querying under constraints, considering conjunctive queries and unions thereof (UCQs) as the query language and guarded TGDs as the ontology and constraint language, respectively. Our main result is a classification according to whether answer counting is fixed-parameter tractable (FPT), W[1]-equivalent, #W[1]-equivalent, #W[2]-hard, or #A[2]-equivalent, lifting a recent classification for UCQs without ontologies and constraints due to Dell et al. The classification pertains to various structural measures, namely treewidth, contract treewidth, starsize, and linked matching number. Our results rest on the assumption that the arity of relation symbols is bounded by a constant and, in the case of ontology-mediated querying, that all symbols from the ontology and query can occur in the data (so-called full data schema). We also study the meta-problems for the mentioned structural measures, that is, to decide whether a given ontology-mediated query or constraint-query specification is equivalent to one for which the structural measure is bounded.


    Volume: Volume 19, Issue 3
    Published on: September 14, 2023
    Accepted on: June 28, 2023
    Submitted on: November 29, 2021
    Keywords: Computer Science - Databases
    Funding:
      Source : OpenAIRE Graph
    • Custom-Made Ontology Based Data Access; Funder: European Commission; Code: 647289

    Consultation statistics

    This page has been seen 984 times.
    This article's PDF has been downloaded 191 times.