Title: Provenance Semirings
T.J. Green, G. Karvounarakis, V. Tannen
University of Pennsylvania

Abstract:
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 and semirings of formal power series. We give algorithms
for datalog provenance calculation as well as datalog evaluation for
incomplete and probabilistic databases. Finally, we show that for some
semirings containment of conjunctive queries is the same as for standard
set semantics.