[Back]

M. Kröll, R. Pichler, S. Skritek:
"On the Complexity of Enumerating the Answers to Well-Designed Pattern Trees";
Talk: 10th Alberto Mendelzon International Workshop on Foundations of Data Management, Panama City, Panama; 2016-05-08 - 2016-05-10; in: "Proceedings of the 10th Alberto Mendelzon International Workshop on Foundations of Data Management, Panama City, Panama, May 8-10, 2016", R. Pichler, A. da Silva (ed.); CEUR Workshop Proceedings, 1644 (2016), Paper ID 14, 5 pages.

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. This is an extended abstract of a paper by the same authors published at ICDT 2016.

enumeration, complexity, conjunctive queries, CQs, pattern trees, parameterized complexity, SPARQL OPTIONAL

http://ceur-ws.org/Vol-1644/paper14.pdf

Project Head Reinhard Pichler:
Heterogene Information Integration

Project Head Reinhard Pichler:
SEE: SPARQL Evaluation and Extensions