Jason (jcreed) wrote,

"Provenance Semirings" is a cute paper by Todd Green et al. that Michael Greenberg recommended to me last Friday. It left me with the feeling that deep in my heart I had already known all of its main results before I started reading it, but it brought them to light rather well. That is the best kind of sneaky education.

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-privacy things I've been thinking about in a way that Michael obviously perceived when I gave the 5-minute spiel of those other things and he thought of this paper.

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".
Tags: papers, provenance

  • Post a new comment


    Anonymous comments are disabled in this journal

    default userpic

    Your reply will be screened

    Your IP address will be recorded