Two occurrence families as one #
What a predicate reading two aggregate values annotates is the ⊕ over
the worlds of the union of the two families it reads. The families of
two tokens are indexed separately – Fin m and Fin n – so the union
has to be built. Having.catAnn concatenates the two annotation
functions into one family on Fin (m + n), Having.leftFam and
Having.rightFam are the two parts inside it, and Having.catWorld
pairs a world of each into a world of the concatenation, leftPart and
rightPart reading them back.
The reindexing lemmas say that reading a part of the concatenation is
reading the family it came from (relAnn_catWorld_left and its right
twin), and they need nothing of K. From them, a world of the union
carries the product of its two halves' annotations exactly where K is
complemented (worldAnn_catWorld) – so the split form in which a
two-family reading is usually written is the union reading there, and
need not be elsewhere.
The concatenation of two occurrence families: m + n occurrences,
the first m of the left family and the last n of the right.
Equations
- Having.catAnn α β = Fin.append α β
Instances For
Dependency graph
The left family inside the concatenation.
Equations
Instances For
Dependency graph
The right family inside the concatenation.
Equations
Instances For
Dependency graph
A world of each family, as one world of the concatenation.
Equations
- Having.catWorld W₁ W₂ = Finset.map (Fin.castAddEmb n) W₁ ∪ Finset.map (Fin.natAddEmb m) W₂
Instances For
Dependency graph
The left half of a world of the concatenation.
Equations
- Having.leftPart W = {i : Fin m | Fin.castAdd n i ∈ W}
Instances For
Dependency graph
The right half of a world of the concatenation.
Equations
- Having.rightPart W = {j : Fin n | Fin.natAdd m j ∈ W}
Instances For
Dependency graph
Dependency graph
Dependency graph
Dependency graph
The worlds of the concatenation are the pairs of worlds.
Equations
- One or more equations did not get rendered due to their size.
Instances For
Dependency graph
The joint reading of a test of two tokens #
What a predicate reading two aggregate values annotates: the ⊕
over the worlds of the union of the two families – those meeting each
grouped one, a scalar token being exempt as always – of the world's
annotation times the truth of the test there.
This is the definition; the structural rules ∧ ↦ ⊗ and ∨ ↦ ⊕
compute it where the m-semiring's properties license them.
Equations
- One or more equations did not get rendered due to their size.
Instances For
Dependency graph
A test that does not depend on the world factors out of the joint
reading. A regular atom is such a test – it reads no occurrence
family, so its truth is the same in every world – so conjoining one to
a predicate multiplies the predicate's provenance by 𝟙 or by 𝟘 and
changes nothing else. This is why a selection on regular columns
standing between two aggregate selections neither changes a family nor
contributes to the annotation of a row that survives it.
Dependency graph
Two columns from two different groupings #
Everything here reads the two families as disjoint – jointPair
sums over the worlds of their concatenation, where the two halves are
chosen independently. That is the joint reading when the families
genuinely are disjoint, which is what two columns coming from two
different groupings give; it is not the joint reading when the
families coincide. Two aggregates of one group are one family, the
sequence of occurrences alone making it
(AggValue.annList_ofGroup), and reading them as two independent
families counts a world once per half – over ℕ, 4 where the
one-family reading gives 2 (natRange_jointPair_ne).
So the factorization below is about columns from different groupings,
and says nothing about a conjunction of tests on two aggregates of one
group, which needs exclusivity and an idempotent ⊗
(AggValue.predProvOf_mul_predProvOf) and fails over ℕ.
Two one-column tests read jointly factorize over disjoint
families, K being complemented. The disjointness is in jointPair
itself, so this is a statement about two families that genuinely are
disjoint and not about two columns of one group.
Dependency graph
Where the two columns come from different groupings, the single
atom comparing the tuple (a, b) with (v₁, v₂) is the two columns
read one after the other, K being complemented: [a ≐ v₁] ⊗ [b ≐ v₂].
Where they come from one grouping their families coincide and this does
not apply; there the tuple atom is a definition and the column-by-column
product is a different value.
Dependency graph
Reading one family as two independent halves is exactly the
column-by-column product. Instantiating the factorization at a = b
says it: where a conjunction's two tests are read over one family split
in two, what comes out is the product of the two one-test readings. So
the gap between the tuple atom and the column-by-column reading, within
one grouping, is the gap between a conjunction over one family and the
product of its atoms – which needs exclusivity and an idempotent ⊗
(AggValue.predProvOf_mul_predProvOf) and fails over ℕ.
Three constructs that look unrelated in SQL meet the same identity: a
range atom against its two bounds, two selections against one selection
on their conjunction, and two aggregate key columns against the atom on
their tuple. They fail together, at 4 against 2, or not at all.
Dependency graph
When the existence factors do absorb the ∨ rule #
ChainFive shows an idempotent ⊕ is not enough and δ = id is
necessary. For two singleton grouped families the two hypotheses
together are enough, and the statement is pure algebra: with δ the
identity each existence factor is its family's own annotation, so the
reported row is α ⊗ β ⊗ (α⊗[P] ⊕ β⊗[Q]) and the joint one
α ⊗ β ⊗ [P ∨ Q], the single world of the union carrying α ⊗ β.
Each hypothesis does an identifiable job. Where one test holds the
reported row repeats that side's annotation – α ⊗ β ⊗ α – and
⊗-idempotence collapses it, which δ = id supplies for free from
the axiom δ(x) ⊗ x = x. Where both hold it carries two copies of
α ⊗ β, and ⊕-idempotence collapses those. Where neither holds both
sides are 𝟘. What is not covered is families of several
occurrences, where the complement factors are no longer trivial.
The row-level absorption for two singleton grouped families.