Institut für Informatik - Universität Innsbruck
Optimization of Semantic Web QueriesAbstract: The Semantic Web is the initiative of the World Wide Web Consortium (W3C) to make information on the Web readable not only by humans but also by machines. Two fundamental standards released by the W3C are the Resource Description Framework (RDF) as the standard data model for the Semantic Web and SPARQL as the standard querylanguage for RDF data. A systematic investigation into the optimization of SPARQL queries has been missing so far. In this talk we report on some foundational research in this direction. Three crucial ingredients of query optimization are presented: *) an appropriate data structure (which we refer to as pattern trees) which allows for a simplified representation of an important class of SPARQL queries. Since pattern trees have a natural operational semantics, we may consider them as Query Execution Plans (QEPs). *) transformation rules which allow us to transform the pattern trees. We can thus aim at the transformation of patterns trees to obtain better QEPs. Moreover, we may use these transformation rules to define normal forms of pattern trees. *) the study of basic computational problems such as containment and equivalence, which are at the heart of query optimization of any query language. |