Efficient evaluation of SPARQL property path queries over PROV-DM provenance graphs in an RDBMS

Millions of useful resources on the Web are enhanced with machine-processable annotations using W3C Resource Description Framework (RDF). It is crucial to design efficient data management techniques to support querying of existing RDF datasets using standard SPARQL queries. To address this challenge, we use a Relational Database Management System (RDBMS) for efficient and scalable storage and querying backend for RDF data. Our solution requires designing novel algorithms for translating SPARQL queries into equivalent SQL queries, such that the latter can be efficiently executed in an RDBMS. The focus of this work is on the translation of SPARQL property paths queries. We propose three SPARQL-to-SQL translation strategies in the presence of property paths: (i) iterative translation with inner joins, (ii) iterative translation with outer joins and, (iii) recursive translation. Our evaluation of the proposed approaches over RDF datasets composed of W3C PROV-DM provenance graphs reveals a number of interesting applicability patterns