Talks and Poster Presentations (with Proceedings-Entry):

S. Skritek, S. Mengel:
"Characterizing Tractability of Simple Well-Designed Pattern Trees with Projection";
Poster: ICDT 2019 - 22nd International Conference on Database Theory, Lissabon, Portugal; 2019-03-26 - 2019-03-28; in: "22nd International Conference on Database Theory, {ICDT} 2019", Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 127 (2019), ISBN: 978-3-95977-101-6; 20:1 - 20:18.

English 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

SPARQL, well-designed pattern trees, query evaluation, FPT, characterizing tractable classes

"Official" electronic version of the publication (accessed through its Digital Object Identifier - DOI)

Related Projects:
Project Head Reinhard Pichler:

Created from the Publication Database of the Vienna University of Technology.