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*. 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.
%0 Conference Paper
%1 zubaria2024native
%A Zubaria, Asma
%A Hernández, Daniel
%A Galárraga, Luis
%A Flouris, Giorgos
%A Fundulaki, Irini
%A Hose, Katja
%B Proceedings of the ACM Web Conference 2024, WWW 2024, Singapore, 13 - 17 May 2024
%D 2024
%I ACM
%K ac-coffee ac-krbuilding myown
%T NPCS: Native Provenance Computation for SPARQL
%X 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*. 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,
abstract = {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*. 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.},
added-at = {2024-02-07T19:41:42.000+0100},
author = {Zubaria, Asma and Hernández, Daniel and Galárraga, Luis and Flouris, Giorgos and Fundulaki, Irini and Hose, Katja},
biburl = {https://puma.ub.uni-stuttgart.de/bibtex/2bd0b4a980dfb313e213697b5327e0492/analyticcomp},
booktitle = {Proceedings of the {ACM} Web Conference 2024, {WWW} 2024, Singapore, 13 - 17 May 2024},
eventdate = {13 May 2024 - 17 May 2024},
interhash = {01a1d68cc500eb3e7b1e506432d2a36a},
intrahash = {bd0b4a980dfb313e213697b5327e0492},
keywords = {ac-coffee ac-krbuilding myown},
publisher = {ACM},
timestamp = {2024-02-07T20:25:27.000+0100},
title = {NPCS: Native Provenance Computation for SPARQL},
venue = {Singapore},
year = 2024
}
