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.
%0 Conference Paper
%1 zubaria2024native
%A Asma, Zubaria
%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 ac-coffee ac-knowgraphs ac-krbuilding myown
%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-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.
%@ 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-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.},
added-at = {2024-03-08T21:05:52.000+0100},
author = {Asma, Zubaria 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/2d6bbef73586371f852be69b559955b29/analyticcomp},
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 = {c406401fab6f9687f85c89e0de34325a},
intrahash = {d6bbef73586371f852be69b559955b29},
isbn = {979-8-4007-0171-9/24/05},
keywords = {ac-coffee ac-knowgraphs ac-krbuilding myown},
language = {English},
month = may,
publisher = {ACM},
timestamp = {2024-03-15T10:46:28.000+0100},
title = {NPCS: Native Provenance Computation for SPARQL},
url = {https://doi.org/10.1145/3589334.3645557},
venue = {Singapore},
year = 2024
}