License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ICDT.2019.20
URN: urn:nbn:de:0030-drops-103220
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2019/10322/
Go to the corresponding LIPIcs Volume Portal

Mengel, Stefan ; Skritek, Sebastian

Characterizing Tractability of Simple Well-Designed Pattern Trees with Projection

pdf-format:
LIPIcs-ICDT-2019-20.pdf (0.6 MB)

Abstract

We study the complexity of evaluating well-designed pattern trees, a query language extending conjunctive queries with the possibility to define parts of the query to be optional. This possibility of optional parts is important for obtaining meaningful results over incomplete data sources as it is common in semantic web settings.
Recently, a structural characterization of the classes of well-designed pattern trees that can be evaluated in polynomial time was shown. However, projection - a central feature of many query languages - was not considered in this study. We work towards closing this gap by giving a characterization of all tractable classes of simple well-designed pattern trees with projection (under some common complexity theoretic assumptions). Since well-designed pattern trees correspond to the fragment of well-designed {AND, OPTIONAL}-SPARQL queries this gives a complete description of the tractable classes of queries with projections in this fragment that can be characterized by the underlying graph structures of the queries.

BibTeX - Entry

@InProceedings{mengel_et_al:LIPIcs:2019:10322,
  author =	{Stefan Mengel and Sebastian Skritek},
  title =	{{Characterizing Tractability of Simple Well-Designed Pattern Trees with Projection}},
  booktitle =	{22nd International Conference on Database Theory (ICDT 2019)},
  pages =	{20:1--20:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-101-6},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{127},
  editor =	{Pablo Barcelo and Marco Calautti},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2019/10322},
  doi =		{10.4230/LIPIcs.ICDT.2019.20},
  annote =	{Keywords: SPARQL, well-designed pattern trees, query evaluation, FPT, characterizing tractable classes}
}

Keywords: SPARQL, well-designed pattern trees, query evaluation, FPT, characterizing tractable classes
Collection: 22nd International Conference on Database Theory (ICDT 2019)
Issue Date: 2019
Date of publication: 19.03.2019

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