Documentation

Provenance.Semirings.Which

Which-provenance m-semiring (lineage) #

This file defines the Which (or lineage) provenance semiring Which α. Elements are either a finite set wset s representing the witnesses or wbot (bottom). Addition takes the union of witness sets, and multiplication does likewise.

Which α is idempotent. It is absorptive if and only if α is empty. It does not satisfy left-distributivity of multiplication over monus when α is nonempty.

The lineage semiring is discussed in Green & Tannen, The Semiring Framework for Database Provenance.

References #

inductive Which (α : Type) :
Instances For
    Dependency graph
    @[instance_reducible]
    instance instZeroWhich {α : Type} :
    Zero (Which α)
    Equations
    Dependency graph
    @[instance_reducible]
    instance instAddWhich {α : Type} [DecidableEq α] :
    Add (Which α)
    Equations
    • One or more equations did not get rendered due to their size.
    Dependency graph
    @[instance_reducible]
    instance instMulWhich {α : Type} [DecidableEq α] :
    Mul (Which α)
    Equations
    • One or more equations did not get rendered due to their size.
    Dependency graph
    @[instance_reducible]
    instance instOneWhich {α : Type} :
    One (Which α)
    Equations
    Dependency graph
    @[instance_reducible]
    instance instSubWhich {α : Type} [DecidableEq α] :
    Sub (Which α)
    Equations
    • One or more equations did not get rendered due to their size.
    Dependency graph
    @[instance_reducible]
    instance instLEWhich {α : Type} :
    LE (Which α)
    Equations
    • One or more equations did not get rendered due to their size.
    Dependency graph
    @[instance_reducible]
    Equations
    • One or more equations did not get rendered due to their size.
    Dependency graph
    @[instance_reducible]
    Equations
    Dependency graph
    Dependency graph
    Dependency graph
    def Which.deltaInd {α : Type} :
    Which α → Which α

    The support-indicator δ of which-provenance: ⊥ on ⊥, the empty label set (𝟙) otherwise. The identity choice (ProvSQL's historical Which::delta) violates delta_absorb – Which is not absorptive, ⊗ and ⊕ both being union.

    Equations
    Instances For
      Dependency graph
      theorem Which.deltaInd_of_ne {α : Type} {a : Which α} (h : a ≠ 0) :
      Dependency graph
      @[instance_reducible]
      Equations
      • One or more equations did not get rendered due to their size.
      Dependency graph
      @[instance_reducible]
      Equations
      Dependency graph
      theorem Which.not_absorptive {α : Type} [DecidableEq α] (h : ∃ (x : α), ⊤) :

      Which[X] is not absorptive as long as there is at least one variable

      Dependency graph
      Dependency graph
      Dependency graph
      instance Which.instCharPZero {α : Type} [DecidableEq α] :
      CharP (Which α) 0

      Which α has characteristic 0 in the CharP sense: it is idempotent and nontrivial (wbot ≠ wset ∅), so every positive natural-number cast equals 1.

      Dependency graph

      In Which[X], as long as X is non-empty, times is not distributive over monus.

      Dependency graph

      Lin[X] is exclusive: 𝟙 is wset ∅, which is below every wset s, so 𝟙 ⊖ a is 𝟘 for every a ≠ 𝟘, and 𝟘 annihilates. As in ℕ this is the collapsing route to exclusivity rather than the complementing one – and unlike ℕ, Lin[X] is not distributive (Which.not_mul_sub_left_distributive), so exclusivity and distributivity are independent.

      Dependency graph

      Lineage is multiplicatively idempotent: ⊗ is union of witness sets.

      Dependency graph