Provenance semirings

TLDR

The work proposes a comprehensive provenance representation based on semirings of polynomials. The authors extend this framework to datalog with formal power series semirings and provide algorithms for datalog provenance calculation and evaluation on incomplete and probabilistic databases. They demonstrate that relational algebra operations for incomplete, probabilistic, bag, and why‑provenance databases are special cases of a common semiring‑based algorithm, and that for certain semirings conjunctive query containment matches standard set semantics.

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.