Green, T. J., Karvounarakis, G. and Tannen, V. (2007). Provenance semirings. In Proc. PODS 2007, pp. 31–40. DOI 10.1145/1265530.1265535
Key takeaways
Read in full (NOTE-913). Annotating each input tuple with an element of a commutative semiring, and computing union and projection with + and join with ·, gives one positive relational algebra (RA+) that is set semantics over the Booleans, bag semantics over the naturals, c-tables over positive Boolean expressions, event tables over sets of outcomes, and lineage over sets of tuple ids. The polynomials N[X] in the tuple ids are the most general such annotation: for any RA+ query and any commutative semiring K, the K-annotated answer is the provenance polynomial evaluated at the input’s K-annotations (Theorem 4.3). For datalog the paper needs ω-continuous semirings and formal power series N∞⟦X⟧, with the analogous factorization (Theorem 6.4) and a criterion for infinite coefficients (Theorem 6.5). Everything is positive: no negation, difference or aggregation, and revaluing inputs can only remove output tuples, never add them; trust and deletion propagation are not treated.
Why this is here
QUESTION-105 and CLAIM-303: for positive relational queries, annotation by provenance polynomials is the most general, and set, bag, probabilistic and lineage answers are its evaluations. Deletion propagation follows by setting a deleted fact’s annotation to zero; that is the record’s application, not the paper’s statement.