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.2022.12
URN: urn:nbn:de:0030-drops-158869
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2022/15886/
Go to the corresponding LIPIcs Volume Portal

Feier, Cristina

Characterising Fixed Parameter Tractability for Query Evaluation over Guarded TGDs

pdf-format:
LIPIcs-ICDT-2022-12.pdf (0.8 MB)

Abstract

We consider the parameterized complexity of evaluating Ontology Mediated Queries (OMQ) based on Guarded TGDs (GTGD) and Unions of Conjunctive Queries, in the case where relational symbols have unrestricted arity and where the parameter is the size of the OMQ. We establish exact criteria for fixed-parameter tractable (fpt) evaluation of recursively enumerable (r.e.) classes of such OMQs (under the widely held Exponential Time Hypothesis). One of the main technical tools introduced in the paper is an fpt-reduction from deciding parameterized uniform CSPs to parameterized OMQ evaluation. The reduction preserves measures known to be essential for classifying r.e. classes of parameterized uniform CSPs: submodular width (according to the well known result of Marx for unrestricted-arity schemas) and treewidth (according to the well known result of Grohe for bounded-arity schemas). As such, it can be employed to obtain hardness results for evaluation of r.e. classes of parameterized OMQs based on GTGD both in the unrestricted and in the bounded arity case. Previously, for bounded arity schemas, this has been tackled using a technique requiring full introspection into the construction employed by Grohe.

BibTeX - Entry

@InProceedings{feier:LIPIcs.ICDT.2022.12,
  author =	{Feier, Cristina},
  title =	{{Characterising Fixed Parameter Tractability for Query Evaluation over Guarded TGDs}},
  booktitle =	{25th International Conference on Database Theory (ICDT 2022)},
  pages =	{12:1--12:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-223-5},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{220},
  editor =	{Olteanu, Dan and Vortmeier, Nils},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2022/15886},
  URN =		{urn:nbn:de:0030-drops-158869},
  doi =		{10.4230/LIPIcs.ICDT.2022.12},
  annote =	{Keywords: omq, fpt evaluation, guarded tgds, unbounded arity, submodular width}
}

Keywords: omq, fpt evaluation, guarded tgds, unbounded arity, submodular width
Collection: 25th International Conference on Database Theory (ICDT 2022)
Issue Date: 2022
Date of publication: 19.03.2022
Supplementary Material: Audiovisual (Video of the Presentation): https://doi.org/10.5446/57493

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