One of the principal achievements of the Semantic Web is to make the information on the meaning of data on the web accessible to machines. This enables the development of tools that support users in finding the relevant data and joining the data from various sources in a meaningful way. To reap the fruits of the Semantic Web, an efficient query mechanism for Semantic Web data and an appropriate way of dealing with the heterogeneity of data on the web are required. The goal of this project is precisely to lay the foundation for an efficient evaluation of queries in the Semantic Web query language SPARQL. To take care of the heterogeneity of data on the web, we will extend our query evaluation techniques to a combined
query language that integrates also features of XQuery - the standard query language for XML data. In order to achieve these goals we will apply and significantly extend well established query optimization techniques from relational databases.