  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.
