Talks and Poster Presentations (with Proceedings-Entry):
A. Letelier, J. Perez, R. Pichler, S. Skritek:
"Static analysis and optimization of semantic web queries";
Talk: ACM Symposium on Principles of Database Systems (PODS),
Scottsdale, Arizona, USA;
- 2012-05-24; in: "Proceedings of the 31st symposium on Principles of Database Systems",
M. Benedikt, M. Krötzsch, M. Lenzerini (ed.);
Static analysis is a fundamental task in query optimization. In this paper we study static analysis and optimization techniques for SPARQL, which is the standard language for querying Semantic Web data. Of particular interest for us is the optionality feature in
SPARQL. It is crucial in Semantic Web data management, where data sources are inherently incomplete and the user is usually interested
in partial answers to queries. This feature is one of the most complicated constructors in SPARQL and also the one that makes this language depart from classical query languages such as relational conjunctive queries. We focus on the class of welldesigned SPARQL queries, which has been proposed in the literature as a fragment of the language with good properties regarding query evaluation. We first propose a tree representation for SPARQL queries, called pattern trees, which captures the class of well-designed SPARQL graph patterns and which can be considered as a query execution plan. Among other results, we propose several transformation rules for pattern trees, a simple normal form, and study equivalence and containment. We also study the enumeration and counting problems for this class of queries.
"Official" electronic version of the publication (accessed through its Digital Object Identifier - DOI)
Project Head Reinhard Pichler:
Created from the Publication Database of the Vienna University of Technology.