A Practical Dynamic Programming Approach to Datalog Provenance Computation - Archive ouverte HAL Access content directly
Preprints, Working Papers, ... Year :

A Practical Dynamic Programming Approach to Datalog Provenance Computation

(1) , (2) , (1, 3)
1
2
3

Abstract

We establish a translation between a formalism for dynamic programming over hypergraphs and the computation of semiring-based provenance for Datalog programs. The benefit of this translation is a new method for computing provenance for a specific class of semirings. Theoretical and practical optimizations lead to an efficient implementation using \textsc{Souffl\'e}, a state-of-the-art Datalog interpreter. Experimental results on real-world data suggest this approach to be efficient in practical contexts, even competing with our previous dedicated solutions for computing provenance in annotated graph databases. The cost overhead compared to plain Datalog evaluation is fairly moderate in many cases of interest.

Dates and versions

hal-03465813 , version 1 (03-12-2021)

Identifiers

Cite

Yann Ramusat, Silviu Maniu, Pierre Senellart. A Practical Dynamic Programming Approach to Datalog Provenance Computation. 2021. ⟨hal-03465813⟩
36 View
0 Download

Altmetric

Share

Gmail Facebook Twitter LinkedIn More