Documentation

Provenance.Semirings.BoolFunc

Boolean-function m-semiring Bool[X] #

This file defines the semiring BoolFunc X of Boolean functions over a set X of Boolean variables. Concretely, BoolFunc X = (X → Bool) → Bool: elements are functions from Boolean assignments to Booleans, with pointwise operations.

Addition is pointwise ||, multiplication is pointwise &&, and the natural order is f ≤ g ↔ ∀ a, f a → g a (pointwise implication).

BoolFunc X is absorptive, idempotent, and left-distributive.

This semiring is used in Green, Karvounarakis & Tannen, Provenance Semirings and surveyed in Senellart, Provenance and Probabilities in Relational Databases.

References #

def BoolFunc (X : Type) :

The type of Boolean functions over Boolean assignments to X: (X → Bool) → Bool with pointwise operations.

Equations
Instances For
    Dependency graph
    def BoolFunc.var {X : Type} (i : X) :

    The i-th variable of BoolFunc X: the Boolean function that returns the value of an assignment at i.

    Equations
    Instances For
      Dependency graph
      @[instance_reducible]
      instance instZeroBoolFunc {X : Type} :
      Equations
      Dependency graph
      @[instance_reducible]
      instance instAddBoolFunc {X : Type} :
      Equations
      Dependency graph
      @[instance_reducible]
      instance instOneBoolFunc {X : Type} :
      Equations
      Dependency graph
      @[instance_reducible]
      instance instMulBoolFunc {X : Type} :
      Equations
      Dependency graph
      @[instance_reducible]
      instance instLEBoolFunc {X : Type} :
      Equations
      Dependency graph
      @[instance_reducible]
      instance instSubBoolFunc {X : Type} :
      Equations
      Dependency graph
      @[instance_reducible]
      Equations
      • One or more equations did not get rendered due to their size.
      Dependency graph
      @[instance_reducible]

      BoolFunc X is a commutative m-semiring with pointwise || as addition, pointwise && as multiplication, and pointwise implication as natural order.

      Equations
      • One or more equations did not get rendered due to their size.
      Dependency graph

      On 𝔹[X] the identity is an admissible δ, so it is the one used (ProvSQL's BoolExpr::delta).

      Dependency graph
      @[instance_reducible]
      Equations
      Dependency graph
      Dependency graph
      Dependency graph
      Dependency graph
      Dependency graph

      BoolFunc X has characteristic 0 in the CharP sense: it is idempotent and nontrivial, so every positive natural-number cast equals 1.

      Dependency graph

      Universal property obstructions #

      The variable functions BoolFunc.var i satisfy two algebraic identities in BoolFunc X that constrain the target of any semiring homomorphism:

      If the target K is not absorptive (there exists a : K with 1 + a ≠ 1), assigning that a to any variable makes a semiring homomorphism BoolFunc X →+* K impossible. Similarly if K's multiplication is not idempotent.

      𝔹[X] is exclusive: 𝟙 ⊖ a is the negation of a, a genuine complement, so the two meet nowhere. This is BoolFunc.mul_sub_self under the name of the property.

      BoolFunc is the source of several other entries of the exclusive column: exclusivity is a unary equation, so any m-semiring each of whose elements is the image of a variable under a homomorphism from BoolFunc inherits it (mul_one_monus_self_eq_zero_of_range, and IntervalUnion.exclusive_of_boolFunc for the instance). Nat and Which are out of that reach, neither being absorptive (BoolFunc.no_hom_of_not_absorptive); they are exclusive for the other reason, their monus against 𝟙 collapsing to 𝟘.

      Dependency graph

      𝔹[X] is multiplicatively idempotent: ⊗ is pointwise conjunction.

      Dependency graph