Semirings with monus #
This file defines semirings with monus and introduces their main properties.
Many semirings relevant for provenance can be equipped with a monus - operator, resulting in what is called a semiring with monus, or m-semiring. This is standard in semiring theory [Ame84] and was introduced in the setting of provenance semirings by Geerts and Poggi [GP10]. The class is the algebraic structure underlying the annotated query semantics of Section IV-A of Sen, Maniu & Senellart, ProvSQL: A General System for Keeping Track of the Provenance and Probability of Data (Definition 5).
References #
Definition of a SemiringWithMonus #
A SemiringWithMonus is a naturally ordered semiring
with a monus operation that is compatible with the natural order.
We do not require the semiring to be necessarily commutative.
In addition to monus, the class carries a δ : α → α operator subject
to three axioms (delta_zero, delta_natCast_pos, and
delta_absorb). This is the duplicate-eliminating support
operator used to interpret aggregation in the framework of
Amsterdamer, Deutch & Tannen, Provenance for aggregate queries,
mirroring ProvSQL's Semiring::delta.
- zero : α
- add : α → α → α
- one : α
- mul : α → α → α
- sub : α → α → α
- delta : α → α
Duplicate-eliminating support operator. Sends
0to0and any positive integer iterate of1to1. δsends0to0.δsends every positive integer iterate of1(i.e., every positive natural-number cast) to1.A δ-guard is absorbed by any multiple of one of its summands:
a ⊗ δ(a ⊕ b) = a. This is what makes a group-existence factor redundant next to any provenance that already contains an occurrence of the group:δreally acts as “the group exists” and nothing more. Both usual choices ofδsatisfy it in their natural habitat: the indicator (δ x = 𝟙forx ≠ 𝟘) in any canonically ordered semiring (delta_absorb_indicator), and the identity in lattice-like semirings, where it is absorptiona ⊓ (a ⊔ b) = a.
Instances
Dependency graph
Main properties #
Uniqueness of monus. The monus operation is determined by its
adjunction property: any binary operation s satisfying
s a b ≤ c ↔ a ≤ b + c coincides with ⊖. Consequently, a naturally
ordered semiring admits at most one monus operation.
Dependency graph
In a SemiringWithMonus, a - a = 0.
Dependency graph
In a SemiringWithMonus, 0 - a = 0.
Dependency graph
In a SemiringWithMonus, a - 0 = a.
Dependency graph
In a SemiringWithMonus, a + (b -a) = b + (a - b).
Dependency graph
In a SemiringWithMonus, monus is left-distributive over plus.
Dependency graph
Additional properties #
The following properties do not always hold in an arbitrary m-semiring.
A Semiring is idempotent if a + a = a.
Equations
- idempotent α = ∀ (a : α), a + a = a
Instances For
Dependency graph
A Semiring is multiplicatively idempotent when a ⊗ a = a. It is
the lattice-like condition: with ⊕-idempotence it makes the semiring a
bounded distributive lattice, and it is what a world annotation needs in
order to survive being multiplied by itself – which is what happens when
two atoms of one predicate read the same occurrence family
(AggValue.predProvOf_mul_predProvOf). 𝔹, 𝔹[X], lineage and
interval union have it; ℕ and the absorptive numeric domains do
not.
Equations
- mulIdempotent α = ∀ (a : α), a * a = a
Instances For
Dependency graph
A Semiring is absorptive (also called 0-closed or 0-bounded) if 1 + a = 1.
Equations
- absorptive α = ∀ (a : α), 1 + a = 1
Instances For
Dependency graph
We define left-distributivity of times over monus in a SemiringWithMonus.
Instances For
Dependency graph
A SemiringWithMonus is exclusive when every element is orthogonal to
what 𝟙 retains after removing it: a ⊗ (𝟙 ⊖ a) = 𝟘.
This is weaker than asking 𝟙 ⊖ a to be a complement of a, which would
also require a ⊕ (𝟙 ⊖ a) = 𝟙: ℕ is exclusive, and there 𝟙 ⊖ 2 = 𝟘
joins with 2 to 2, not to 𝟙.
Exclusivity is what makes two distinct possible worlds of one occurrence
family annihilate each other (worldAnn_mul_eq_zero_of_ne), hence what makes
the alternatives of an occurrence exclude each other. It holds in Bool,
BoolFunc, Nat, Which and IntervalUnion, and fails in How, Why,
Viterbi, MinMax, Lukasiewicz, Tropical and ChainFive (the catalog
theorems named exclusive and not_exclusive in Provenance.Semirings.*).
Those five are not five independent facts. Exclusivity is a unary equation,
so it passes both to subalgebras and to the elements reached by a
homomorphism out of an exclusive semiring. Bool and IntervalUnion inherit
it from BoolFunc on those two routes: Bool embeds in BoolFunc as the
constant functions (Bool.exclusive_of_boolFunc, by
exclusive_of_injective_homomorphism_exclusive), while every interval union
is the image of a variable under a homomorphism from BoolFunc
(IntervalUnion.exclusive_of_boolFunc, by
mul_one_monus_self_eq_zero_of_range – that homomorphism has a finite domain
and is never onto, so the element-by-element form is what applies, not the
surjective one). Nat and Which
are beyond that reach, neither being absorptive
(BoolFunc.no_hom_of_not_absorptive), and are exclusive for the other of the
two reasons: their monus against 𝟙 collapses to 𝟘 rather than
complementing.
Note that How – the universal semiring, in which provenance circuits are
built – is not exclusive, so the terms exclusivity cancels are carried by a
circuit and vanish only on evaluation into a semiring that has the property,
homomorphisms commuting with ⊖.
Independence #
Exclusivity is independent of each of the three properties above, every combination being realized in the catalog:
| exclusive | not exclusive | |
|---|---|---|
| absorptive | Bool | Viterbi |
| not absorptive | Nat | How |
| idempotent | Bool | Why |
| not idempotent | Nat | How |
mul_sub_left_distributive | Bool | Viterbi |
not mul_sub_left_distributive | Which | Why |
Independence is not absence of interaction: absorptivity and exclusivity
constrain each other jointly without either implying the other, by
eq_zero_or_one_of_exclusive_of_absorptive.
Instances For
Dependency graph
A SemiringWithMonus is complemented when 𝟙 ⊖ · turns ⊕ into
⊗: the De Morgan law of a complement.
It is what makes the annotation of a world of a family split along a
partition of that family into the annotations of the two halves
(Having.worldAnn_split), and so what lets a predicate whose atoms read
disjoint families be evaluated atom by atom rather than over the union.
It is not an m-semiring identity – the non-negative reals with truncated
subtraction fail it at a = b = ½, which
nnreal_not_complemented records against the
m-semiring instance there – but it is proved for
every semiring of the catalog, for one of two reasons. Either
𝟙 ⊖ · is a genuine complement, which is De Morgan's law: 𝔹
(Bool.complemented), 𝔹[X] (BoolFunc.complemented) and the temporal
semiring (IntervalUnion.complemented). Or 𝟙 ⊖ · takes only the two
values 𝟘 and 𝟙, is 𝟘 exactly on a property that a sum has iff one
of its summands has, and ⊗ is 𝟘-absorbing with 𝟙 ⊗ 𝟙 = 𝟙: ℕ
(Nat.complemented), ℕ[X] (How.complemented, the constant
coefficient), Lin[X] (Which.complemented), Why[X]
(Why.complemented, the empty witness), the tropical semirings
(MinTropical.complemented), Viterbi (Viterbi.complemented), the
bounded linear order (MinMax.complemented) and Łukasiewicz
(Lukasiewicz.complemented). The second reason is a fact about each
semiring and not a consequence of the two-valuedness alone, which is why
each is proved rather than argued once.
Instances For
Dependency graph
Absorptivity implies idempotence
Dependency graph
In a SemiringWithMonus, right-distributivity of monus
over plus implies idempotence.
Dependency graph
In a SemiringWithMonus, idempotence implies right-distributivity of monus
over plus.
Dependency graph
A SemiringWithMonus is idempotent iff monus is right-distributive
over plus.
Dependency graph
Finite-family version of add_monus_of_idempotent: in an idempotent
SemiringWithMonus, monus distributes over the sum of any multiset of
annotations, (⨁ᵢ aᵢ) ⊖ c = ⨁ᵢ (aᵢ ⊖ c).
Dependency graph
Dependency graph
Monus is antitone in its second argument: subtracting more leaves less.
Together with monus_le this is what lets a subtrahend be replaced by a
larger one inside an upper bound.
Dependency graph
Exclusivity #
exclusive says a ⊗ (𝟙 ⊖ a) = 𝟘. The possible-world arguments consume a
two-argument form, a ⊗ (𝟙 ⊖ (a ⊕ b)) = 𝟘: an occurrence present in one
world and absent from another contributes a to the first world's annotation
and 𝟙 ⊖ (a ⊕ b) to the second's. The two forms are equivalent, so the
one-argument form is what a semiring is checked against and the two-argument
form is what the proofs use.
Exclusivity against absorptivity #
An absorptive m-semiring has 𝟙 at the top of its natural order, so 𝟙 ⊖ a
is the least element joining with a to 𝟙 – the least relative complement.
Exclusivity then asks that least complement to be orthogonal to a, which a
chain cannot deliver: there the join of two elements is one of them, so the
only complement of a non-𝟙 element is 𝟙 itself.
In an absorptive semiring 𝟙 is the greatest element of the natural
order.
Dependency graph
In an absorptive m-semiring, 𝟙 ⊖ a joins with a to 𝟙; by
monus_smallest it is the least element that does.
Dependency graph
Absorptivity and exclusivity together are restrictive. If 𝟙 is
join-irreducible – as it is in every absorptive m-semiring whose natural order
is total – then an exclusive one has no element besides 𝟘 and 𝟙.
Dependency graph
The contrapositive, in the form the catalog uses: a totally ordered
absorptive m-semiring with an element other than 𝟘 and 𝟙 is not
exclusive. This one argument covers Viterbi, MinMax, Lukasiewicz,
Tropical and ChainFive.
Dependency graph
Characteristic of idempotent semirings #
In an idempotent semiring (a + a = a), every positive natural-number cast
collapses to 1. With 1 ≠ 0 this yields CharP K 0. Note that this is
strictly weaker than CharZero K, which fails for idempotent semirings since
the cast ℕ → K is not injective.
In a semiring with idempotent addition, the cast of any positive natural
number equals 1.
Dependency graph
Generic constructions of δ #
In the m-semirings used for provenance the δ operator is invariably
realized in one of two ways: as the identity (when the semiring is
idempotent, so every positive natural cast already equals 1) or as the
indicator-of-nonzero (a ↦ if a = 0 then 0 else 1). The lemmas below
package the proofs of the δ axioms for both candidates so each
concrete instance can plug them in directly.
δ := id satisfies delta_natCast_pos in any idempotent semiring:
every positive natural-number cast collapses to 1.
Dependency graph
What the δ axioms ask of a candidate, as a predicate, so that
the choices open to a given semiring can be compared.
δsends𝟘to𝟘.δsends every positive natural cast to𝟙.A
δ-guard is absorbed by any multiple of one of its summands.
Instances For
Dependency graph
The identity is a legal δ exactly where the semiring absorbs and
its 𝟙 is additively idempotent. The absorption clause is the one a
reader expects – a ⊓ (a ⊔ b) = a in a lattice-like semiring – but it
is not the whole condition: δ must send every positive cast of 𝟙
to 𝟙, which for the identity says n · 𝟙 = 𝟙, that is, that ⊕
does not accumulate copies of 𝟙. Min-max satisfies both; ℕ fails
the second, which is why the identity is not available there even
though the first is what one thinks to check.
Dependency graph
The “indicator-of-nonzero” recipe: δ a = 0 when a = 0 and
δ a = 1 otherwise. Captured abstractly so a single set of axioms can
serve all the concrete instances that use it (ℕ, ℕ[X], Tropical,
Viterbi, Lukasiewicz).
Instances For
Dependency graph
Any δ matching the indicator recipe satisfies delta_natCast_pos
in a nontrivial semiring of characteristic 0 (in the CharP sense):
positive natural-number casts are nonzero, so δ sends them to 1.
Dependency graph
Any δ matching the indicator recipe satisfies delta_absorb in a
canonically ordered semiring: if a ⊕ b = 𝟘 then a = 𝟘 by zero-sum
freeness, and otherwise δ(a ⊕ b) = 𝟙.
Dependency graph
The support map is a legal δ wherever the casts are non-zero.
It is the greatest legal choice, the identity the least where it is
available.
Dependency graph
Admissibility of a candidate δ #
δ is not determined by the axioms, and the two operators used in practice
are the identity and the support indicator. IsDelta states the axioms as a
predicate on a candidate operator, so that a semiring can record which of
the two it must use: the identity is preferred where it is admissible, and
the indicator is forced exactly where ¬ IsDelta id holds. The three
not_isDelta_id_of_* lemmas below cover the three ways the identity fails,
in increasing order of subtlety.
A candidate operator δ : K → K satisfies the δ-axioms of
SemiringWithMonus.
δsends𝟘to𝟘.δsends every positive natural-number cast to𝟙.A δ-guard is absorbed by any multiple of one of its summands.
Instances For
Dependency graph
To refute δ := id, exhibit a pair violating the lattice absorption law
a ⊗ (a ⊕ b) = a, which is what delta_absorb demands of the identity.
Dependency graph
δ := id requires the semiring to be idempotent: delta_natCast_pos at
n = 2 reads 𝟙 ⊕ 𝟙 = 𝟙, whence a ⊕ a = a ⊗ (𝟙 ⊕ 𝟙) = a. This is the
crudest of the three obstructions, and the one that rules the identity out
of the counting semirings (ℕ, ℕ[X]).
Dependency graph
δ := id requires multiplicative idempotence as soon as addition is
idempotent: delta_absorb at b = a reads a ⊗ (a ⊕ a) = a ⊗ a = a. This is
the obstruction in the absorptive semirings whose ⊗ is a genuine product
(Viterbi, Łukasiewicz), where the two coarser tests below say nothing.
Dependency graph
δ := id requires absorptivity: delta_absorb at a = 𝟙 reads
𝟙 ⊗ (𝟙 ⊕ b) = 𝟙, i.e., 𝟙 ⊕ b = 𝟙.
Dependency graph
Existence of a δ-like operator #
This is the abstract counterpart of the SemiringWithMonus δ-axioms: we
characterize, in an arbitrary nontrivial semiring (no order assumed), when
a function δ : K → K satisfying δ 0 = 0 and δ ((n : K)) = 1 for
0 < n can exist. The class also demands delta_absorb, which the iff
below ignores, so it should be read as a statement about how much of the
ProvSQL δ interface is consistent with a given characteristic, not as a
full existence proof for the class. (Constructing a witness for
delta_absorb requires more structure: in a canonically ordered semiring
the indicator works, see delta_absorb_indicator.)
In any nontrivial semiring, a function δ : K → K satisfying δ 0 = 0
and δ ((n : K)) = 1 for every positive natural cast n exists if and only
if K has characteristic 0 in the CharP sense. The forward direction
follows because δ 0 = 0 and δ ((n : K)) = 1 are inconsistent when
(n : K) = 0 for some 0 < n (it would force 0 = 1). The backward
direction defines δ as the indicator of being nonzero.
Note that the δ operator is not uniquely determined by these axioms: they
only pin its values on the image of ℕ. Two typical choices are δ as the
indicator of being nonzero (δ x = if x = 0 then 0 else 1, used in the
backward direction below) and, in an idempotent semiring, δ as the identity
(since every positive natural cast then equals 1, see
natCast_pos_eq_one_of_idempotent). Both are idempotent (δ (δ a) = δ a);
adding idempotence as a third requirement would leave the statement
unchanged, since the forward direction never uses it and the indicator
witness satisfies it.
Dependency graph
The companion of delta_exists_iff_charP_zero for the full axiom set: in a
nontrivial canonically ordered semiring, an admissible δ exists if and only if
the characteristic is 0.
Dependency graph
Commutative SemiringWithMonuss #
SemiringWithMonus is intentionally not assumed to be commutative; however, every
provenance semiring used in this library is in fact commutative, and the algebraic
identities that drive HAVING-style aggregate provenance (see Provenance.Having)
require it. CommSemiringWithMonus packages a SemiringWithMonus together with
the commutativity axiom, producing a CommMonoid instance whose Mul matches
the one already supplied by SemiringWithMonus, so no Mul diamond appears when
Finset.prod is used.
A SemiringWithMonus whose multiplication is commutative.
- zero : K
- add : K → K → K
- one : K
- mul : K → K → K
- sub : K → K → K
- delta : K → K
Multiplication on
Kis commutative.
Instances
Dependency graph
A CommSemiringWithMonus is automatically a CommMonoid, sharing its
multiplicative structure with the underlying SemiringWithMonus. This makes
Finset.prod usable without introducing a separate CommSemiring hypothesis
that would cause a Mul diamond.
Equations
- instCommMonoidOfCommSemiringWithMonus = { toMonoid := h.toMonoid, mul_comm := ⋯ }
Dependency graph
An exclusive lattice m-semiring is a Boolean algebra #
In an absorptive m-semiring ⊕ is the join of a lattice whose top is
𝟙 (le_one_of_absorptive) and, where ⊗ is idempotent too, ⊗ is its
meet: the two lattice absorption laws are derived from 𝟙 ⊕ a = 𝟙 and
distributivity (add_mul_self, mul_add_self) rather than assumed. The
lattice is distributive, ⊗ distributing over ⊕ by the semiring
axioms, and one distributive law in a lattice gives the other.
In such a semiring 𝟙 ⊖ a always joins a to 𝟙
(add_one_monus_eq_one_of_absorptive, by residuation), and
exclusivity is exactly what makes it a complement – exclusive says
it meets a at 𝟘 – after which the complement is unique
(monus_one_unique_compl). So an exclusive lattice m-semiring is a
distributive lattice in which every element has a complement, i.e., a
Boolean algebra; conversely, in a Boolean algebra residuation forces
a ⊖ b = a ⊓ bᶜ, whose exclusivity is a ⊓ aᶜ = ⊥. What follows is the
elementwise content of that characterization, stated without building the
lattice structure.
The first lattice absorption law, derived: a ⊕ a ⊗ b = a.
Dependency graph
The second, where ⊗ is idempotent: a ⊗ (a ⊕ b) = a.
Dependency graph
Exclusivity makes 𝟙 ⊖ a a complement: it joins a to 𝟙 and
meets it at 𝟘.
Dependency graph
And the complement is unique, by the distributive-lattice
argument: any b joining a to 𝟙 and meeting it at 𝟘 is 𝟙 ⊖ a.
With monus_one_isCompl this is what identifies 𝟙 ⊖ · with Boolean
complementation.
Dependency graph
Homomorphisms of SemiringWithMonuss #
Definition of a homomorphism of SemiringWithMonuss. Preserves the
semiring structure (via RingHom), the monus (map_sub), and the δ
operator (map_delta). The latter is required for hom commutation of the
aggregation operator, where δ appears on the row-annotation column
(Definition 7 / R5 of Sen, Maniu & Senellart).
- toFun : α → β
- map_delta (a : α) : self.toRingHom (SemiringWithMonus.delta a) = SemiringWithMonus.delta (self.toRingHom a)
The hom preserves
δ:h (δ a) = δ (h a).
Instances
Dependency graph
Equations
- instCoeFunSemiringWithMonusHomForall α β = { coe := fun (f : SemiringWithMonusHom α β) (x : α) => f.toRingHom x }
Dependency graph
If ν is an injective m-semiring homomorphism from α to β, and β is exclusive, so is α.
Dependency graph
If ν is an m-semiring homomorphism from α onto β, and α is exclusive, so is β. Exclusivity passes to quotients as idempotence and distributivity do, being likewise an equation.
Dependency graph
Miscellaneous #
On an arbitrary semiring the natural relation a ≼ b ↔ ∃ c, b = a + c
is always a preorder (reflexive by c = 0, transitive by adding witnesses)
but not always antisymmetric: on ℤ, any two elements are related in both
directions, e.g., 0 ≼ 1 ≼ 0 with 0 ≠ 1. This is why SemiringWithMonus
assumes the canonically ordered structure instead of deriving an order
from +.