[Zurück]

P. Barceló, R. Pichler, S. Skritek:
"Efficient Evaluation of Well-designed Pattern Trees (Extended Abstract)";
Vortrag: 9th Alberto Mendelzon International Workshop on Foundations of Data Management (AMW 2015), Lima, Peru; 06.05.2015 - 08.05.2015; in: "Proceedings of the 9th Alberto Mendelzon International Workshop on Foundations of Data Management, Lima, Peru, May 6 - 8, 2015", A. Cali, M. Vidal (Hrg.); CEUR Workshop Proceedings, 1378 (2015), Paper-Nr. 5, 6 S.

Conjunctive queries (CQs) constitute the core of the query languages for relational databases and also the most intensively studied querying mechanism in the database theory community. But CQs suffer from a serious drawback
when dealing with incomplete information: If it is not possible to match the complete query with the data, they return no answer at all. The semantic web therefore provides a formalism - known as well-designed pattern trees (WDPTs) - that tackles this problem. In particular, WDPTs allow us to match patterns over the data if available, but do not fail to give an answer otherwise. Here, we abstract away the specifics of semantic web applications and study WDPTs over arbitrary relational schemas. Since our language properly subsumes the class of CQs, the evaluation problem associated with it is intractable. In this paper we identify natural structural properties of WDPTs that lead to tractability of various variants of the evaluation problem.

http://ceur-ws.org/Vol-1378/AMW_2015_paper_5.pdf

Projektleitung Reinhard Pichler:
Heterogene Information Integration

Projektleitung Reinhard Pichler:
SEE: SPARQL Evaluation and Extensions