Talks and Poster Presentations (with Proceedings-Entry):
M. Kröll, R. Pichler, S. Skritek:
"On the Complexity of Enumerating the Answers to Well-designed Pattern Trees";
Talk: International Conference on Database Theory - ICDT 2016,
Bordeaux;
2016-03-15
- 2016-03-18; in: "19th International Conference on Database Theory, ICDT 2016, Bordeaux, France, March 15-18, 2016",
W. Martens, T. Zeume (ed.);
Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik,
LIPIcs 48
(2016),
1
- 18.
English abstract:
Well-designed pattern trees (wdPTs) have been introduced as an extension of conjunctive queries to allow for partial matching - analogously to the OPTIONAL operator of the semantic web query language SPARQL. Several computational problems of wdPTs have been studied in recent years, such as the evaluation problem in various settings, the counting problem, as well as static analysis tasks including the containment and equivalence problems. Also restrictions needed to achieve tractability of these tasks have been proposed. In contrast, the problem of enumerating the answers to a wdPT has been largely ignored so far. In this work, we embark on a systematic study of the complexity of the enumeration problem of wdPTs. As our main result, we identify several tractable and intractable cases of this problem both from a classical complexity point of view and from a parameterized complexity point of view.
Keywords:
SPARQL, Pattern Trees, CQs, Enumeration, Complexity
"Official" electronic version of the publication (accessed through its Digital Object Identifier - DOI)
http://dx.doi.org/10.4230/LIPIcs.ICDT.2016.22
Electronic version of the publication:
http://drops.dagstuhl.de/opus/volltexte/2016/5791/pdf/21.pdf
Related Projects:
Project Head Reinhard Pichler:
Heterogene Information Integration
Project Head Reinhard Pichler:
SEE: SPARQL Evaluation and Extensions
Created from the Publication Database of the Vienna University of Technology.