Semiring Provenance over Graph Databases - Archive ouverte HAL Access content directly
Conference Papers Year :

Semiring Provenance over Graph Databases

(1, 2) , (3) , (4, 1, 5)
1
2
3
4
5

Abstract

We generalize three existing graph algorithms to compute the provenance of regular path queries over graph databases, in the framework of provenance semirings – algebraic structures that can capture different forms of provenance. Each algorithm yields a different trade-off between time complexity and generality, as each requires different properties over the semiring. Together, these algorithms cover a large class of semirings used for provenance (top-k, security, etc.). Experimental results suggest these approaches are complementary and practical for various kinds of provenance indications, even on a relatively large transport network.
Fichier principal
Vignette du fichier
tapp2018-paper-ramusat.pdf (593.98 Ko) Télécharger le fichier
Origin : Files produced by the author(s)
Loading...

Dates and versions

hal-01850510 , version 1 (27-07-2018)

Identifiers

  • HAL Id : hal-01850510 , version 1

Cite

Yann Ramusat, Silviu Maniu, Pierre Senellart. Semiring Provenance over Graph Databases. 10th USENIX Workshop on the Theory and Practice of Provenance (TaPP 2018), Jul 2018, London, United Kingdom. ⟨hal-01850510⟩
274 View
93 Download

Share

Gmail Facebook Twitter LinkedIn More