Skip to Main content Skip to Navigation
Conference papers

Semiring Provenance over Graph Databases

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.
Document type :
Conference papers
Complete list of metadata

Cited literature [11 references]  Display  Hide  Download
Contributor : Pierre Senellart Connect in order to contact the contributor
Submitted on : Friday, July 27, 2018 - 2:15:45 PM
Last modification on : Tuesday, October 19, 2021 - 11:14:11 AM
Long-term archiving on: : Sunday, October 28, 2018 - 1:28:20 PM


Files produced by the author(s)


  • HAL Id : hal-01850510, version 1


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⟩



Record views


Files downloads