Skip to Main content Skip to Navigation
Conference papers

Provenance-Based Algorithms for Rich Queries over Graph Databases

Abstract : In this paper, we investigate the efficient computation of the provenance of rich queries over graph databases. We show that semiring-based provenance annotations enrich the expressiveness of routing queries over graphs. Several algorithms have previously been proposed for provenance computation over graphs, each yielding a trade-off between time complexity and generality. Here, we address the limitations of these algorithms and propose a new one, partially bridging a complexity and expressiveness gap and adding to the algorithmic toolkit for solving this problem. Importantly, we provide a comprehensive taxonomy of semirings and corresponding algorithms, establishing which practical approaches are needed in different cases. We implement and comprehensively evaluate several practical applications of the problem (e.g., shortest distances, top-shortest distances, Boolean or integer path features), each corresponding to a specific semiring and algorithm, that depends on the properties of the semiring. On several real-world and synthetic graph datasets, we show that the algorithms we propose exhibit large practical benefits for processing rich graph queries.
Document type :
Conference papers
Complete list of metadata
Contributor : Pierre Senellart Connect in order to contact the contributor
Submitted on : Friday, February 12, 2021 - 2:56:19 PM
Last modification on : Friday, January 21, 2022 - 3:17:19 AM
Long-term archiving on: : Friday, May 14, 2021 - 9:32:58 AM


Files produced by the author(s)


Distributed under a Creative Commons Attribution - NonCommercial - NoDerivatives 4.0 International License


  • HAL Id : hal-03140067, version 1


Yann Ramusat, Silviu Maniu, Pierre Senellart. Provenance-Based Algorithms for Rich Queries over Graph Databases. EDBT 2021 - 24th International Conference on Extending Database Technology, Mar 2021, Nicosia / Virtual, Cyprus. ⟨hal-03140067⟩



Les métriques sont temporairement indisponibles