SPARQL-to-SQL Query Translation: Bottom-Up or Top-Down?

Emerging Semantic Web Services rely on the availability of metadata that describes various functional and non-functional characteristics of computational resources. A number of semantic vocabularies and datasets describing existing services and workflows are publicly available and their rapid growth brings forward a new challenge -- efficient management of semantic data. Many existing semantic data repositories use conventional relational databases to store and query large RDF datasets. The most complex component of this approach is SPARQL-to-SQL query translation. Existing algorithms translate SPARQL queries to SQL using either bottom-up or top-down strategy and result in semantically equivalent but syntactically different relational queries. While it can be expected that relational query optimizers produce identical query execution plans for semantically equivalent bottom-up and top-down queries, is this usually the case in practice? To address this question, we study bottom-up and top-down translations of SPARQL queries with complex nested optional graph patterns that yield SQL queries with left outer joins whose reordering is not always possible. This paper reports our on-going research and performance study featuring SPARQL queries with nested optional graph patterns over semantic data repositories instantiated in Oracle, DB2, and Postgre SQL.