Provenance semirings

Abstract

We show that relational algebra calculations for incomplete databases, probabilistic databases, bag semantics and why- provenance are particular cases of the same general algo- rithms involving semirings. This further suggests a com- prehensive 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.