Also it's Wadler-approved.
If you are as categorically-minded as I try to be, I recommend you play "where's waldo" by substituting "the free semiring" or "the free ω-complete semiring" for "waldo".
This paper is curiously relevant to the other Lipschitz-continuity/differential-privac
Both my thoughts and the paper's results have to do with "enrichment" in one form or another, where I use that word to suggest what happens in enriched categories where you say, ok, I had a plain old set of morphisms before, but now I want a set with stuff, like algebraic structure, or order structure, or topological structure, or whatnot.
The provenance semiring is a way of enriching a database --- but more specially than that, it's the free way of doing it in an appropriate sense, and so it generalizes probabalistic databases, and maybe databases, and fuzzy databases, and tropical semiring databases, and so on.
But it doesn't seem to cover a notion of metric, which is what I presently care about, because a metric is about assigning a real number (more generally perhaps a semiring element) to two points in the type of all databases, and provenance is about assigning one semiring element to each row in a database.
---
Some other neat stuff that vaguely has to do with provenance is "debugging by program slicing".