[Back]

A. Letelier, J. Perez, R. Pichler, S. Skritek:
"Static Analysis and Optimization of Semantic Web Queries";
ACM Transactions on Database Systems (invited), 38 (2013), 4; 25:1 - 25:45.

Static analysis is a fundamental task in query optimization. In this article 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 well-designed 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. Among other results, we propose several rules that can be used to transform pattern trees into a simple normal form, and study equivalence and containment. We also study the evaluation and enumeration problems for this class of queries.

Optimization, query containment, RDF, Semantic Web, SPARQL

http://dx.doi.org/10.1145/2500130

http://delivery.acm.org/10.1145/2510000/2500130/a25-letelier.pdf?ip=128.131.239.247&id=2500130&acc=ACTIVE%20SERVICE&key=C2716FEBFA981EF141830814F84EDB9544A7A4963E396D04&CFID=390683302&CFTOKEN=90486392&__acm__=1387558492_f0dea17e83a854f4cbfa4f4d54ba6a35

Project Head Reinhard Pichler:
SEE: SPARQL Evaluation and Extensions

Project Head Reinhard Pichler:
Service-orientierte Datenintegration

Project Head Reinhard Pichler:
Theoretisch Effiziente Lösbarkeit vs. Praktische Berechnung