Symbolic aggregate tokens #
AggValue T K is the symbolic aggregate token of the general HAVING
semantics: an aggregate function together with the ≼-sorted occurrence
payload of the originating group, projected to pairs (value of the
aggregated term, occurrence annotation) – exactly the data of
Having.havingGroup that the possible-world semantics of an aggregate
comparison consumes. It is the one-level analogue of KTensor
(deliberately un-quotiented, so the possible worlds of the group can be
read off the token); there is no recursion: ProvSQL rejects aggregation,
grouping and ordering over aggregate values, and likewise rejects
deduplication and difference on token-carrying relations, so no linear
order or decidable equality on tokens is required by any permitted
downstream operator (SeqAggFunc being a function type, structural
decidable equality would not be available anyway).
Readings of a token #
valOn– the aggregate value in one possible world of the group, matchingHaving.aggValOnon the originating group (valOn_ofGroup);specialize– the world-faithful reading: restrict to the occurrences whose annotation is realized by a valuation and aggregate those;collapse– the deterministic reading: aggregate the whole sequence. This is the value ProvSQL displays for an uncompared aggregate (the actual-world value, renderedv (*)), and the reading through which the data-part adequacy of the general evaluator is stated;predProv– the predicate provenance of a comparison against the token: the⊕-sum, over the non-empty possible worlds of the group, of the world annotation times the characteristic value of the comparison. On a token built from a group it coincides with the fused semantics'Having.havingProv(predProv_ofGroup) – the seed of the regression bridge between the general and the fused evaluators.
mapAnn pushes a function K → K' through the annotations of a token:
value-only readings are unchanged (collapse_mapAnn) and specialize
composes with the pushforward (specialize_mapAnn). This is the token
layer of the hom-commutation metatheorem for the general evaluator.
Lifted column values #
A column of a token-carrying relation holds either a regular value or a
token: T ⊕ AggValue T K. AggValue.mapAnnSum and AggValue.collapseSum
extend the pushforward and the deterministic reading to such lifted
values; the kind-indexed syntax of the general evaluator governs
statically which columns hold which arm.
Equations
- One or more equations did not get rendered due to their size.
- instDecidableEqTermIn.decEq (TermIn.const a) (TermIn.const b) = if h : a = b then h ▸ isTrue ⋯ else isFalse ⋯
- instDecidableEqTermIn.decEq (TermIn.const a) (TermIn.outer a_1) = isFalse ⋯
- instDecidableEqTermIn.decEq (TermIn.const a) #a_1 = isFalse ⋯
- instDecidableEqTermIn.decEq (TermIn.const a) (a_1.add a_2) = isFalse ⋯
- instDecidableEqTermIn.decEq (TermIn.const a) (a_1.sub a_2) = isFalse ⋯
- instDecidableEqTermIn.decEq (TermIn.const a) (a_1.mul a_2) = isFalse ⋯
- instDecidableEqTermIn.decEq (TermIn.const a) (TermIn.caseWhen a_1 a_2 a_3 a_4 a_5) = isFalse ⋯
- instDecidableEqTermIn.decEq (TermIn.const a) (a_1.coalesce a_2) = isFalse ⋯
- instDecidableEqTermIn.decEq (TermIn.outer a) (TermIn.const a_1) = isFalse ⋯
- instDecidableEqTermIn.decEq (TermIn.outer a) (TermIn.outer b) = if h : a = b then h ▸ isTrue ⋯ else isFalse ⋯
- instDecidableEqTermIn.decEq (TermIn.outer a) #a_1 = isFalse ⋯
- instDecidableEqTermIn.decEq (TermIn.outer a) (a_1.add a_2) = isFalse ⋯
- instDecidableEqTermIn.decEq (TermIn.outer a) (a_1.sub a_2) = isFalse ⋯
- instDecidableEqTermIn.decEq (TermIn.outer a) (a_1.mul a_2) = isFalse ⋯
- instDecidableEqTermIn.decEq (TermIn.outer a) (TermIn.caseWhen a_1 a_2 a_3 a_4 a_5) = isFalse ⋯
- instDecidableEqTermIn.decEq (TermIn.outer a) (a_1.coalesce a_2) = isFalse ⋯
- instDecidableEqTermIn.decEq (#a) (TermIn.const a_1) = isFalse ⋯
- instDecidableEqTermIn.decEq (#a) (TermIn.outer a_1) = isFalse ⋯
- instDecidableEqTermIn.decEq #a #b = if h : a = b then h ▸ isTrue ⋯ else isFalse ⋯
- instDecidableEqTermIn.decEq (#a) (a_1.add a_2) = isFalse ⋯
- instDecidableEqTermIn.decEq (#a) (a_1.sub a_2) = isFalse ⋯
- instDecidableEqTermIn.decEq (#a) (a_1.mul a_2) = isFalse ⋯
- instDecidableEqTermIn.decEq (#a) (TermIn.caseWhen a_1 a_2 a_3 a_4 a_5) = isFalse ⋯
- instDecidableEqTermIn.decEq (#a) (a_1.coalesce a_2) = isFalse ⋯
- instDecidableEqTermIn.decEq (a.add a_1) (TermIn.const a_2) = isFalse ⋯
- instDecidableEqTermIn.decEq (a.add a_1) (TermIn.outer a_2) = isFalse ⋯
- instDecidableEqTermIn.decEq (a.add a_1) #a_2 = isFalse ⋯
- instDecidableEqTermIn.decEq (a.add a_1) (a_2.sub a_3) = isFalse ⋯
- instDecidableEqTermIn.decEq (a.add a_1) (a_2.mul a_3) = isFalse ⋯
- instDecidableEqTermIn.decEq (a.add a_1) (TermIn.caseWhen a_2 a_3 a_4 a_5 a_6) = isFalse ⋯
- instDecidableEqTermIn.decEq (a.add a_1) (a_2.coalesce a_3) = isFalse ⋯
- instDecidableEqTermIn.decEq (a.sub a_1) (TermIn.const a_2) = isFalse ⋯
- instDecidableEqTermIn.decEq (a.sub a_1) (TermIn.outer a_2) = isFalse ⋯
- instDecidableEqTermIn.decEq (a.sub a_1) #a_2 = isFalse ⋯
- instDecidableEqTermIn.decEq (a.sub a_1) (a_2.add a_3) = isFalse ⋯
- instDecidableEqTermIn.decEq (a.sub a_1) (a_2.mul a_3) = isFalse ⋯
- instDecidableEqTermIn.decEq (a.sub a_1) (TermIn.caseWhen a_2 a_3 a_4 a_5 a_6) = isFalse ⋯
- instDecidableEqTermIn.decEq (a.sub a_1) (a_2.coalesce a_3) = isFalse ⋯
- instDecidableEqTermIn.decEq (a.mul a_1) (TermIn.const a_2) = isFalse ⋯
- instDecidableEqTermIn.decEq (a.mul a_1) (TermIn.outer a_2) = isFalse ⋯
- instDecidableEqTermIn.decEq (a.mul a_1) #a_2 = isFalse ⋯
- instDecidableEqTermIn.decEq (a.mul a_1) (a_2.add a_3) = isFalse ⋯
- instDecidableEqTermIn.decEq (a.mul a_1) (a_2.sub a_3) = isFalse ⋯
- instDecidableEqTermIn.decEq (a.mul a_1) (TermIn.caseWhen a_2 a_3 a_4 a_5 a_6) = isFalse ⋯
- instDecidableEqTermIn.decEq (a.mul a_1) (a_2.coalesce a_3) = isFalse ⋯
- instDecidableEqTermIn.decEq (TermIn.caseWhen a a_1 a_2 a_3 a_4) (TermIn.const a_5) = isFalse ⋯
- instDecidableEqTermIn.decEq (TermIn.caseWhen a a_1 a_2 a_3 a_4) (TermIn.outer a_5) = isFalse ⋯
- instDecidableEqTermIn.decEq (TermIn.caseWhen a a_1 a_2 a_3 a_4) #a_5 = isFalse ⋯
- instDecidableEqTermIn.decEq (TermIn.caseWhen a a_1 a_2 a_3 a_4) (a_5.add a_6) = isFalse ⋯
- instDecidableEqTermIn.decEq (TermIn.caseWhen a a_1 a_2 a_3 a_4) (a_5.sub a_6) = isFalse ⋯
- instDecidableEqTermIn.decEq (TermIn.caseWhen a a_1 a_2 a_3 a_4) (a_5.mul a_6) = isFalse ⋯
- instDecidableEqTermIn.decEq (TermIn.caseWhen a a_1 a_2 a_3 a_4) (a_5.coalesce a_6) = isFalse ⋯
- instDecidableEqTermIn.decEq (a.coalesce a_1) (TermIn.const a_2) = isFalse ⋯
- instDecidableEqTermIn.decEq (a.coalesce a_1) (TermIn.outer a_2) = isFalse ⋯
- instDecidableEqTermIn.decEq (a.coalesce a_1) #a_2 = isFalse ⋯
- instDecidableEqTermIn.decEq (a.coalesce a_1) (a_2.add a_3) = isFalse ⋯
- instDecidableEqTermIn.decEq (a.coalesce a_1) (a_2.sub a_3) = isFalse ⋯
- instDecidableEqTermIn.decEq (a.coalesce a_1) (a_2.mul a_3) = isFalse ⋯
- instDecidableEqTermIn.decEq (a.coalesce a_1) (TermIn.caseWhen a_2 a_3 a_4 a_5 a_6) = isFalse ⋯
Instances For
Dependency graph
Dependency graph
The identity of an aggregate value. Its family is the label of the
operator that produced it, a key telling its groups (or rows) apart, and
the apply parameters the operator reads – an operator evaluated on the
same inputs producing the same occurrences. A regular parameter is
recorded by its value; an aggregate parameter by its own identity, the
aggregate value itself and not the value it takes in a world. The
identity adds the column of the operator that produced the value and the
terms applied to it since (ProjColIn.aggTermOf): two columns of one
family, or one column under two terms, are two different parameters.
- mk {T : Type} (lab : ℕ) (key : List T) (params : List (T ⊕ FamId T)) (col : ℕ) (terms : List (TermIn T 1 0)) : FamId T
Instances For
Dependency graph
Decidable equality, by structural recursion so that the kernel reduces it.
Equations
- One or more equations did not get rendered due to their size.
Instances For
Dependency graph
Decidable equality of parameter lists.
Equations
- One or more equations did not get rendered due to their size.
- FamId.decEqParams [] [] = isTrue ⋯
- FamId.decEqParams [] (head :: tail) = isFalse ⋯
- FamId.decEqParams (head :: tail) [] = isFalse ⋯
- FamId.decEqParams (Sum.inl val :: tail) (Sum.inr val_1 :: tail_1) = isFalse ⋯
- FamId.decEqParams (Sum.inr val :: tail) (Sum.inl val_1 :: tail_1) = isFalse ⋯
Instances For
Dependency graph
Equations
Dependency graph
Decidable equality of a family, stated once: the nested instance is past the size instance search explores.
Dependency graph
The identity carried where none is recorded.
Instances For
Dependency graph
The family: what tells the occurrences apart – the producing operator, its key and the parameters it reads, without the column or the terms applied since. Two values of one family are read in one world.
Instances For
Dependency graph
The identity of a value after a term is applied to it.
Instances For
Dependency graph
The identity of an occurrence an aggregate value reads: the operator
that aggregated it (its label), the values of the apply parameters that
operator reads, its group's key (or its partition's, for a window), and its
position in the group's (or partition's) listing. So the aggregates of one
group, and the frames of one partition, share the occurrences they hold in
common, an aggregation evaluated again on the same input gives the same
occurrences, and one evaluated for other parameter values gives others –
which is the identity the semantics gives occurrences. Two copies of a row
are two positions, so two occurrences.
- lab : ℕ
The aggregating operator's label.
The values of the parameters it reads.
- key : List T
The key of its group or partition.
- pos : ℕ
The position in the group's or partition's listing.
Instances For
Dependency graph
The identities of a group's or a partition's listing, position by position.
Equations
- OccId.listing lab params key len = List.map (fun (i : ℕ) => { lab := lab, params := params, key := key, pos := i }) (List.range len)
Instances For
Dependency graph
A symbolic aggregate token: an aggregate function together with the (≼-sorted) occurrence payload of the originating group – for each occurrence, the value of the aggregated term paired with the occurrence annotation.
- agg : SeqAggFunc T
The sequence aggregate applied by every reading of the token.
The occurrence payload: values of the aggregated term paired with the occurrence annotations, in the group's ≼-order.
- scalar : Bool
Whether the empty world is one of this token's worlds.
A token whose row exists only because its group does is never read where the group is empty, and the reading skips that world. A token whose row exists on its own – an aggregation with no grouping, whose single row survives an empty input, or a window frame that may exclude the row it is computed for – is read there too, and the aggregate then sees the empty sequence. The flag travels with the token because a comparison may be far from the operator that built it, past projections and joins, and cannot otherwise tell which reading applies.
- fam : FamId T
Which occurrence family the token reads: the label of the operator that computed it and the key of its group (or the row a window computed it for). Two aggregate values of one row share their occurrences exactly when they carry the same family, which is what a predicate reading both has to know to read them in one world. No reading of the token itself looks at it.
The identities of its occurrences, one per element of
occs, where the operator that built the token records them (a grouping and a window with noFILTERclause and noDISTINCT); empty otherwise. No reading of the token looks at them: they say which occurrences two aggregate values share, which is what the equivalence ofGenRow.zeqRencompares.
Instances For
Dependency graph
The token of a group with occurrence sequence U, aggregating the
term t with f: the projection of the group payload.
Equations
- AggValue.ofGroup f t U γ = { agg := f, occs := List.map (fun (p : AnnotatedTuple T K m) => (t.eval p.1 γ, p.2)) U, fam := FamId.none }
Instances For
Dependency graph
The occurrence annotations of a token, as a function on positions.
Instances For
Dependency graph
The aggregate value of the token in the possible world W of its
group: the aggregate of the values of the kept occurrences, in order.
Instances For
Dependency graph
The deterministic reading: the aggregate of the whole occurrence sequence.
Instances For
Dependency graph
Merging the occurrences of equal value #
A DISTINCT window aggregate reads one occurrence per class of equal
values in its frame, annotated by the ⊕ of the class's members. That
is a transformation of the occurrence payload, and it has to be decided
where the token is built: no reading of a token recovers it, the
deterministic reading having already collapsed the sequence.
The classes are read in the order the domain gives their values, which
is what makes the reading a function of the values and not of the input
sequence: deduplication leaves one value per class and not a sequence,
so nothing else could fix the order, and an order-dependent aggregate
would otherwise read one the query does not determine. SQL draws the
line in the same place, rejecting an ORDER BY inside a DISTINCT
aggregate unless it appears in the argument list.
It is also what makes the reading world by world sound with no condition on the aggregate: the domain's order restricted to the classes a world holds is that world's own order, an order being stable under passing to a subsequence. The operator that carries the flag is not here yet.
The ⊕ of the annotations of the occurrences of one value: the
annotation its class carries once the occurrences of equal value are
merged.
Instances For
Dependency graph
An occurrence payload read over its distinct values: one
occurrence per class of equal values, carrying the ⊕ of the class's
annotations, the classes read in the order the domain gives their values.
This is what a DISTINCT window aggregate reads, and the order being a
function of the values is what makes it a reading rather than a choice –
so nothing is asked of the aggregate, and in particular not symmetry.
Equations
Instances For
Dependency graph
The same on a token: the payload merged, the aggregate and the convention its own.
Equations
- a.mergeByValue = { agg := a.agg, occs := AggValue.mergeOccs a.occs, scalar := a.scalar, fam := a.fam }
Instances For
Dependency graph
The world-faithful reading under a valuation ν of the annotations:
restrict to the occurrences whose annotation ν realizes, and aggregate
those in order.
Equations
- a.specialize ν = a.agg (List.map Prod.fst (List.filter (fun (o : T × K) => ν o.2) a.occs))
Instances For
Dependency graph
Pushforward of h : K → K' through the annotations of a token; the
values are untouched.
Equations
Instances For
Dependency graph
Predicate provenance of an atomic comparison against a token: the
⊕-sum, over the non-empty possible worlds of the token's group, of the
world annotation times the characteristic value of the comparison between
the world's aggregate value and the regular value c. Non-empty worlds
only: the predicate provenance already enforces group existence, exactly
as in the fused semantics Having.havingProv.
Equations
Instances For
Dependency graph
Predicate provenance in the scalar convention: the same ⊕-sum as
predProv, but over all worlds of the occurrence payload, the empty one
included, where the aggregate reads the empty sequence (valOn_empty).
The two conventions answer to two situations. Where a row exists only
because its group does – a GROUP BY key – the comparison is never read in
a world without occurrences, and predProv is the reading. Where the row
exists on its own and the aggregate may range over nothing – an aggregation
with no grouping, whose single row survives an empty input, or a frame that
may exclude the row it is computed for – the empty world is a world, and the
comparison must be given a value there. predProvScalar is that reading;
the two differ by exactly the empty world's term
(predProvScalar_eq_predProv_add).
Equations
- a.predProvScalar op c = ∑ W : Finset (Fin a.occs.length), Having.worldAnn a.anns W * Having.chi op (a.valOn W) c
Instances For
Dependency graph
The token of a group, read in the scalar convention: the same payload, with the empty world among its worlds. This is what an aggregation with no grouping produces, and what a window frame that may exclude its current row produces.
Equations
- One or more equations did not get rendered due to their size.
Instances For
Dependency graph
Predicate provenance in the token's own convention. A comparison reads a token by the flag it carries, so that an operator settles the convention once, where the token is built, and every comparison downstream follows it.
Equations
- a.predProvOf op c = if a.scalar = true then a.predProvScalar op c else a.predProv op c
Instances For
Dependency graph
Two atoms on one token #
A selection whose predicate conjoins two comparisons of the same token –
a truncation's m < #(k+1) ≤ m+c, a HAVING such as count(*) > 2 AND count(*) < 5 – multiplies the two atoms' provenances, each summed over
the worlds of the token separately. That is not in general the sum over
the worlds where both comparisons hold, and the definitions below name
the joint reading so that the difference can be stated.
The predicate provenance of two aggregate atoms on one token, read
jointly: the ⊕-sum over the worlds in which both comparisons hold.
Equations
- a.predProvAnd op₁ c₁ op₂ c₂ = ∑ W : Finset (Fin a.occs.length) with W.Nonempty, Having.worldAnn a.anns W * (Having.chi op₁ (a.valOn W) c₁ * Having.chi op₂ (a.valOn W) c₂)
Instances For
Dependency graph
The scalar-convention counterpart of predProvAnd: the same joint
sum, over all worlds of the token, the empty one included. This is the
reading a window's token needs, its frame being allowed to exclude the
row it is computed for.
Equations
- a.predProvScalarAnd op₁ c₁ op₂ c₂ = ∑ W : Finset (Fin a.occs.length), Having.worldAnn a.anns W * (Having.chi op₁ (a.valOn W) c₁ * Having.chi op₂ (a.valOn W) c₂)
Instances For
Dependency graph
The joint reading in the token's own convention.
Equations
- a.predProvOfAnd op₁ c₁ op₂ c₂ = if a.scalar = true then a.predProvScalarAnd op₁ c₁ op₂ c₂ else a.predProvAnd op₁ c₁ op₂ c₂
Instances For
Dependency graph
A range test on one token reads jointly exactly under these two
properties. A selection whose predicate conjoins two comparisons of the
same token – a truncation's m < #(k+1) ≤ m+c, a HAVING such as
count(*) > 2 AND count(*) < 5 – multiplies the two provenances, each
summed over the worlds separately. That is the joint sum over the worlds
where both hold when the m-semiring is exclusive and its multiplication
is idempotent, and not otherwise.
Dependency graph
A test in place of a comparison #
An atom that carries a three-valued test on the token's value rather
than a comparison against a term reads the same way – one sum over the
worlds, weighted by whether the test holds there – and a range is then
one atom. The ∧ rule becomes a decomposition of that sum, which is
what the hypotheses above are for.
The predicate provenance of an arbitrary three-valued test on the
token's value: the ⊕-sum, over the worlds of the group, of the world's
annotation weighted by whether the test holds there. predProv is the
case of a comparison against a term, and a range is the case of the
conjunction of two – one atom, and not a product of two.
Equations
- a.predProvWith P = ∑ W : Finset (Fin a.occs.length) with W.Nonempty, Having.worldAnn a.anns W * Having.chiOf P (a.valOn W)
Instances For
Dependency graph
The scalar-convention counterpart: the same sum over all worlds, the empty one included.
Equations
- a.predProvScalarWith P = ∑ W : Finset (Fin a.occs.length), Having.worldAnn a.anns W * Having.chiOf P (a.valOn W)
Instances For
Dependency graph
The test read in the token's own convention.
Equations
- a.predProvOfWith P = if a.scalar = true then a.predProvScalarWith P else a.predProvWith P
Instances For
Dependency graph
Reindexing bridges #
The occurrence payload of ofGroup is a List.map image of the group
sequence, so worlds over the token and worlds over the group live over
propositionally – not definitionally – equal position types. The bridges
below transport seqOf, worldAnn and the two readings along the
length-preserving equivalence finCongr.
The readings, related #
COUNT(κ) ≥ 1 is the ⊕-sum of the occurrence annotations. Where
the counted values are never null, every non-empty world counts at least
one and the empty world counts none, so the comparison holds in exactly the
non-empty worlds – an upward-closed family, which Having.sum_ann_meet
collapses. Absorptivity is what that collapse needs; distributivity of ⊗
over ⊖ is not used.
Dependency graph
Regression bridge, token side. The predicate provenance of a comparison against the token of a group is the fused semantics' predicate provenance of the same comparison on that group.
Dependency graph
Pushforward lemmas #
Lifted column values #
Pushforward of h : K → K' on a lifted column value: data is
untouched, a token maps its annotations.
Equations
Instances For
Dependency graph
Deterministic reading of a lifted column value: data is itself, a token collapses.
Equations
Instances For
Dependency graph
Reading an aggregate value as a key: its worlds and its values #
An operator comparing keys reads an aggregate column in each world, so what it needs of the column is the set of values it takes and, for each, the provenance of taking it.
The worlds of an aggregate value: every subfamily when it is read in the scalar convention, the non-empty ones when it is grouped.
Instances For
Dependency graph
Val(a): the values the aggregate value takes over its worlds.
Equations
- a.vals = Finset.image a.valOn a.worlds
Instances For
Dependency graph
The same set, read off the aggregate, the convention and the list of values alone – which is what makes it insensitive to anything that moves occurrences without moving their values.
Equations
- AggValue.valsOf f sc L = Finset.image (fun (W : Finset (Fin L.length)) => f (Having.seqOf L W)) {W : Finset (Fin L.length) | sc = true ∨ W.Nonempty}
Instances For
Dependency graph
The values a token takes depend on its occurrences only through their values.
Dependency graph
Pushing the annotations forward changes no value the token takes.
Dependency graph
[a ≐ v]: the predicate provenance of the atom comparing the
aggregate value with v, under SQL's null-safe equality – so the case
v = NULL is the atom a IS NULL and asks for no separate clause.
Equations
- a.altProv v = a.predProvOfWith fun (x : T) => CompOp.syneq.eval3 x v
Instances For
Dependency graph
The alternatives exhaust the worlds: their shares add up to what the aggregate value's worlds carry, so reading a key through them loses nothing and invents nothing.
Dependency graph
Distinct alternatives of one occurrence exclude each other,
where K is exclusive: distinct values come from distinct worlds, and
two distinct worlds' annotations multiply to 𝟘. In 𝔹[X] this is
the statement that exactly one alternative of a present occurrence
holds under each valuation; over ℕ[X], where exclusivity fails, an
operator that combines two alternatives of one occurrence – a window
over a partition holding both – counts worlds that do not exist.