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/
Go to the corresponding LIPIcs Volume Portal


Feier, Cristina ; Lutz, Carsten ; Przybyłko, Marcin

Answer Counting Under Guarded TGDs

pdf-format:
LIPIcs-ICDT-2021-11.pdf (0.8 MB)


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


DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI