Provenance-Based Algorithms for Rich Queries over Graph Databases - Archive ouverte HAL Access content directly
Conference Papers Year :

Provenance-Based Algorithms for Rich Queries over Graph Databases

(1) , (2) , (1, 3)
1
2
3
Yann Ramusat
  • Function : Author
  • PersonId : 1087951

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.
Fichier principal
Vignette du fichier
p16.pdf (675.09 Ko) Télécharger le fichier
Origin : Files produced by the author(s)

Dates and versions

hal-03140067 , version 1 (12-02-2021)

Licence

Attribution - NonCommercial - NoDerivatives - CC BY 4.0

Identifiers

  • HAL Id : hal-03140067 , version 1

Cite

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⟩
214 View
293 Download

Share

Gmail Facebook Twitter LinkedIn More