Semiring Provenance over Graph Databases


Yann Ramusat, ENS, PSL University; Silviu Maniu, LRI, Université Paris-Sud, Université Paris-Saclay; Pierre Senellart, DI ENS, ENS, CNRS, PSL University & Inria Paris & LTCI, Télécom ParisTech


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.

Open Access Media

USENIX is committed to Open Access to the research presented at our events. Papers and proceedings are freely available to everyone once the event begins. Any video, audio, and/or slides that are posted after the event are also free and open to everyone. Support USENIX and our commitment to Open Access.

@inproceedings {220323,
author = {Yann Ramusat and Silviu Maniu and Pierre Senellart},
title = {Semiring Provenance over Graph Databases},
booktitle = {10th USENIX Workshop on the Theory and Practice of Provenance (TaPP 2018)},
year = {2018},
address = {London},
url = {},
publisher = {USENIX Association},
month = jul