License: 
Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ICDT.2021.11
URN: urn:nbn:de:0030-drops-137195
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2021/13719/
Feier, Cristina ;
Lutz, Carsten ;
Przybyłko, Marcin
Answer Counting Under Guarded TGDs
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. [Holger Dell et al., 2019]. 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.
BibTeX - Entry
@InProceedings{feier_et_al:LIPIcs.ICDT.2021.11,
author = {Feier, Cristina and Lutz, Carsten and Przyby{\l}ko, Marcin},
title = {{Answer Counting Under Guarded TGDs}},
booktitle = {24th International Conference on Database Theory (ICDT 2021)},
pages = {11:1--11:22},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-179-5},
ISSN = {1868-8969},
year = {2021},
volume = {186},
editor = {Yi, Ke and Wei, Zhewei},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2021/13719},
URN = {urn:nbn:de:0030-drops-137195},
doi = {10.4230/LIPIcs.ICDT.2021.11},
annote = {Keywords: Ontology-Mediated Querying, Querying under Constraints, Answer Counting, Parameterized Complexity}
}
|
Keywords: |
|
Ontology-Mediated Querying, Querying under Constraints, Answer Counting, Parameterized Complexity |
|
Collection: |
|
24th International Conference on Database Theory (ICDT 2021) |
|
Issue Date: |
|
2021 |
|
Date of publication: |
|
11.03.2021 |
