IOS Press Flexible Query Processing for SPARQL

Abstract. Flexible querying techniques can enhance users ’ access to complex, heterogeneous datasets in settings such as RDF Linked Data where the user may not always know how a query should be formulated in order to retrieve the desired answers. This paper presents query processing algorithms for an extended fragment of SPARQL 1.1 incorporating regular path queries (property path queries), and query approximation and relaxation operators. Our flexible query processing approach is based on query rewriting and returns answers incrementally according to their “distance ” from the exact form of the query. We formally show the soundness, completeness and termination properties of our query rewriting algorithm. We also present empirical results that show promising query processing performance for the extended language. 1