Documentation

Provenance.Semirings.Why

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 #

structure Why (α : Type) :
Instances For
    Dependency graph
    theorem Why.ext {α : Type} {x y : Why α} (carrier : x.carrier = y.carrier) :
    x = y
    Dependency graph
    theorem Why.ext_iff {α : Type} {x y : Why α} :
    Dependency graph
    @[instance_reducible]
    instance instCoeWhySet {α : Type} :
    Coe (Why α) (Set (Set α))
    Equations
    Dependency graph
    @[instance_reducible]
    instance instZeroWhy {α : Type} :
    Zero (Why α)
    Equations
    Dependency graph
    @[instance_reducible]
    instance instAddWhy {α : Type} :
    Add (Why α)
    Equations
    Dependency graph
    def why_mul {α : Type} (a b : Why α) :
    Why α
    Equations
    Instances For
      Dependency graph
      @[instance_reducible]
      Equations
      • One or more equations did not get rendered due to their size.
      Dependency graph
      def Why.deltaInd {α : Type} (a : Why α) :
      Why α

      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”.

      Equations
      Instances For
        Dependency graph
        Dependency graph
        theorem Why.deltaInd_of_ne {α : Type} {a : Why α} (h : a ≠ 0) :
        Dependency graph
        @[instance_reducible]

        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
        @[instance_reducible]
        Equations
        Dependency graph
        Dependency graph
        Dependency graph
        instance Why.instCharPZero {α : Type} :
        CharP (Why α) 0

        Why α has characteristic 0 in the CharP sense: it is idempotent and nontrivial (⟨∅⟩ ≠ ⟨{∅}⟩), so every positive natural-number cast equals 1.

        Dependency graph
        theorem Why.not_absorptive {α : Type} (hNotEmpty : ∃ (x : α), ⊤) :
        Dependency graph
        theorem Why.not_exclusive {α : Type} [Inhabited α] :

        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.

        Dependency graph