The Case of SPARQL UNION, FILTER and DISTINCT

SPARQL’s Basic Graph Pattern (BGP) queries are well-researched for query optimisation and RDF indexing techniques. They resemble SQL inner joins and benefit from reorderability of triple patterns in their performance optimisation. But other components of SPARQL such as OPTIONAL, UNION, FILTER, DISTINCT pose more challenges, as they are part of the SPARQL recursive grammar and impose restrictions on the reorderability of triple patterns. These components are important because they help in querying the semi-structured data as opposed to the strictly structured relational data with a stringent schema. In this paper, we use previously published optimisation techniques for BGP-OPTIONAL queries as primitives, and show how they can be used for SPARQL queries with any intermix of UNION, FILTER, and DISTINCT clauses. We mainly focus on the structural aspects of these queries, identify UNION, FILTER, and DISTINCT queries that can use these BGP-OPTIONAL optimisation techniques, and extend some of the previously published theoretical results.