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 '24), May13--17, 2024, Singapore, Singapore
%D 2024
%I ACM
%K
%R 10.1145/3589334.3645557
%T NPCS: Native Provenance Computation for SPARQL
%U https://doi.org/10.1145/3589334.3645557
%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.
%@ 979-8-4007-0171-9/24/05
@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-10T12:15:27.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/223a753ee5337aec4e9d046c757c9963d/ki},
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},
interhash = {01a1d68cc500eb3e7b1e506432d2a36a},
intrahash = {23a753ee5337aec4e9d046c757c9963d},
isbn = {979-8-4007-0171-9/24/05},
keywords = {},
language = {English},
month = may,
publisher = {ACM},
timestamp = {2024-02-21T10:25:51.000+0100},
title = {NPCS: Native Provenance Computation for SPARQL},
url = {https://doi.org/10.1145/3589334.3645557},
venue = {Singapore},
year = 2024
}