Provenance Semirings

We show that relational algebra calculations for incomplete
databases, probabilistic databases, bag semantics and why-provenance
are particular cases of the same general algorithms involving
semirings. This further suggests a comprehensive provenance
representation that uses semirings of polynomials.

We extend these considerations to datalog, using semirings of formal
power series for its provenance. We give algorithms for datalog
provenance calculation as well as a generalization of datalog
evaluation for incomplete, probabilistic, and other database models.

We will also show that semiring semantics and provenance calculations
extend smoothly beyond the relational model---to a nested relational
calculus for semiring-valued collections.

Joint work with T.J. Green, G. Karvounarakis and J.N. Foster