Why-provenance m-semiring Why[X] #
This file defines the Why provenance semiring Why α = Set (Set α).
Elements are sets of subsets of α (representing sets of witnesses). Addition
is union of families, and multiplication is pairwise union of witnesses.
Why α is idempotent but not absorptive when α is nonempty. It also
does not satisfy left-distributivity of multiplication over monus, contradicting
a claim in Amsterdamer, Deutch & Tannen, On the limitations of provenance for
queries with differences, Table on p. 4.
References #
Dependency graph
Equations
- instCoeWhySet = { coe := Why.carrier }
Dependency graph
Dependency graph
Dependency graph
Equations
Instances For
Dependency graph
Equations
- One or more equations did not get rendered due to their size.
Dependency graph
The support-indicator δ of why-provenance: 𝟘 on the empty
witness family, 𝟙 otherwise. The witness-preserving identity choice
(ProvSQL's historical Why::delta) violates delta_absorb – Why is
not absorptive – so δ collapses group existence to a bare “exists”.
Instances For
Dependency graph
Dependency graph
Why-provenance is a semiring with monus: ∖ is set difference on the outer
level, 2^(2^X) ordered by inclusion.
Named explicitly, and not to be renamed: this name is published as a link target in Sen, Maniu & Senellart, ProvSQL: A General System for Keeping Track of the Provenance and Probability of Data, ICDE 2026.
Registered in the Lax archive as
Lax392996.WhyProvenance.Why.isMSemiring.
Equations
- One or more equations did not get rendered due to their size.
Dependency graph
Equations
- instCommSemiringWithMonusWhy = { toSemiringWithMonus := instSemiringWithMonusWhy, mul_comm := ⋯ }
Dependency graph
Dependency graph
Dependency graph
Why α has characteristic 0 in the CharP sense: it is idempotent and
nontrivial (⟨∅⟩ ≠ ⟨{∅}⟩), so every positive natural-number cast equals 1.
Dependency graph
Dependency graph
Why[X] is not exclusive as soon as there is one label: 𝟙 is {∅} and
a token {{x}} does not contain ∅, so 𝟙 ⊖ {{x}} = 𝟙 and
{{x}} ⊗ 𝟙 = {{x}} ≠ 𝟘. Why[X] is neither absorptive nor distributive, so
this is a failure for reasons unrelated to the absorptive chains.
Dependency graph
In Why[X], as long as X is non-empty, times is not distributive over monus. Note that this contradicts Amsterdamer, Deutch & Tannen, On the limitations of provenance for queries with differences, table page 4, which claims this semiring satisfies axiom A13.