ELLIS header
University of Stuttgart Logo
Max Planck Institute for Intelligent Systems Logo

NPCS: Native Provenance Computation for SPARQL

Zubaria Asma, Daniel Hernández, Luis Galárraga, Giorgos Flouris, Irini Fundulaki, Katja Hose

Proceedings of the ACM Web Conference 2024 (WWW ’24), May13–17, 2024, Singapore, Singapore, 2024.


The popularity of Knowledge Graphs (KGs) both in industry and academia owes credit to their flexible data model, suitable for data integration from multiple sources. Several KG-based applications such as trust assessment or view maintenance on dynamic data rely on the ability to compute provenance explanations for query results. The how-provenance of a query result is an expression that encodes the records (triples or facts) that explain its inclusion in the result set. This article proposes NPCS, a Native Provenance Computation approach for SPARQL queries. NPCS annotates query results with their how-provenance. By building upon spm-provenance semirings, NPCS supports both monotonic and non-monotonic SPARQL queries. Thanks to its reliance on query rewriting techniques, the approach is directly applicable to already deployed SPARQL engines using different reification schemes – including RDF-star. Our experimental evaluation on two popular SPARQL engines (GraphDB and Stardog) shows that our novel query rewriting brings a significant runtime improvement over existing query rewriting solutions, scaling to RDF graphs with billions of triples.



@inproceedings{zubaria2024native, author = {Asma, Zubaria and Hernández, Daniel and Galárraga, Luis and Flouris, Giorgos and Fundulaki, Irini and Hose, Katja}, booktitle = {Proceedings of the ACM Web Conference 2024 (WWW '24), May13--17, 2024, Singapore, Singapore}, doi = {10.1145/3589334.3645557}, eventdate = {May 13 -17 2024}, eventtitle = {WWW '24}, isbn = {979-8-4007-0171-9/24/05}, language = {English}, publisher = {ACM}, title = {NPCS: Native Provenance Computation for SPARQL}, url = {https://doi.org/10.1145/3589334.3645557}, venue = {Singapore}, year = {2024} }