Answer Counting under Guarded TGDs

DOI10.46298/LMCS-19(3:16)2023MaRDI QIDQ6076172zbMATH OpenOpenAlexFDO

Authors Cristina Feier, Carsten Lutz, Marcin Przybyłko

Publication date 23 October 2023

Published in Logical Methods in Computer Science (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/2101.03058

zbMATH Keywords

approximation schemescounting answersontology mediated queriesparametrised complexitytuple generating dependencies

Mathematics Subject Classification ID

Logic in computer science (03B70) Computer science (68-XX)

Abstract: 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.

Cites work

• #NFA Admits an FPRAS: Efficient Enumeration, Counting, and Uniform Generation for Logspace Classes
• A trichotomy in the complexity of counting answers to conjunctive queries
• An introduction to description logic
• Counting Answers to Existential Questions
• Data exchange: semantics and query answering
• Efficient Approximations of Conjunctive Queries
• Fast query answering over existential rules
• scientific article; zbMATH DE number 839556 (Why is no real title available?)
• Linking Data to Ontologies
• On rules with existential variables: walking the decidability line
• Ontology-based data access: a study through disjunctive Datalog, CSP, and MMSNP
• Ontology-Mediated Query Answering with Data-Tractable Description Logics
• Querying the Guarded Fragment
• Semantic Optimization of Conjunctive Queries
• Semantically Acyclic Conjunctive Queries under Functional Dependencies
• Structural tractability of counting of solutions to conjunctive queries
• Taming the infinite chase: query answering under expressive relational constraints
• Testing containment of conjunctive queries under functional and inclusion dependencies
• The complexity of counting homomorphisms seen from the other side
• The complexity of homomorphism and constraint satisfaction problems seen from the other side
• The complexity of weighted counting for acyclic conjunctive queries
• The Parameterized Complexity of Counting Problems
• Towards more expressive ontology languages: the query answering problem
• Tractable counting of the answers to conjunctive queries

This page was built for publication: Answer Counting under Guarded TGDs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6076172)