The selection row: σ is the only operator reading the order #
A well-kinded query of the minimal universe (AggQueryIn.wellKinded: a
term reads a parameter as a plain value only where it is not aggregate)
that uses no selection and never reads an aggregate column as a key
(AggQueryIn.noExplode) is order-blind:
its regular columns commute with every injective map of the values that
fixes the query's constants and the zero the aggregate columns are read
as, whatever the map does to the order. Nothing but a selection reads the
order into a regular column, a key or a difference: the windows and the
ordered aggregations read it, but into an aggregate column, which such a
query never reads back.
The commutation is AggQueryIn.evaluatePlain_orderBlind, the
faithfulness commutation of Provenance.Genericity with the order
dropped from the map and the selection dropped from the syntax, and
stated on the regular reading ColKind.readTuple of the rows. The
witness is σ_{#1<#2}(S): on the one-row instance {(a, b)} with
a < b it keeps the row, on {(b, a)} it keeps nothing, and the swap of
a and b carries one instance to the other (ltWitness_breaks). So
no selection-free query expresses it (ltWitness_not_expressible), and
σ is in every basis whose produced queries read no aggregate column as
a key (sel_mem_of_generatesOnRecNoExplode).
The regular reading of a row #
The commutation #
Order-blindness: a well-kinded query with no selection, reading
no aggregate column as a key, in a signature with no function on values,
commutes on its regular columns with every injective map of the values
that fixes 0 and its constants – whatever the map does to the order.
The aggregate columns are read as 0 on both sides (ColKind.readTuple),
being the only place the order enters. The instance hypotheses are those
of AggQueryIn.evaluatePlain_faithful: the leaves of D' are those of
D mapped, except at the holes, whose rounds may carry aggregate
columns and are asked to agree on their regular reading only; and the
two contexts agree, up to the map, at the parameters that are not
aggregate, which are the only ones a term reads as a plain value
(AggQueryIn.wellKinded). An aggregate parameter is read by the leaf
AggQueryIn.Param alone, into an aggregate column.
Dependency graph
The witness #
The one-row instance S = {(a, b)}.
Instances For
Dependency graph
σ_{#1<#2}(S), the witness: the one selection whose atom reads the order.
Equations
Instances For
Dependency graph
The witness breaks order-blindness: the swap of a < b carries
{(a, b)} to {(b, a)}, where it keeps nothing.
Dependency graph
No selection-free query expresses the witness. A query over ℕ
with no selection, reading no aggregate column as a key or as an apply's
parameter, in a signature
with no function on values, is not plain-equivalent to σ_{#1<#2}(S):
on two fresh values a < b it answers alike, up to the swap, on
{(a, b)} and on {(b, a)}, and the witness does not.
Dependency graph
The row #
Generation with no aggregate column read as a key: the
whole-algebra generation predicate (GeneratesOnRec) with the produced
query also asked to be noExplode and well-kinded. This is the scope of
the annotated generation, where the alternatives are not an operator of
the source language; over it the selection is in every basis, which the
plain construction putting − in place of σ (basisRecDiffOps_isBasis)
escapes only by reading aggregate columns as keys. An apply's right side
reading an aggregate column of its left side as a plain value would escape
it the same way – a window's rank read as a parameter compares two values
against a constant with a difference – and well-kindedness is what refuses
that reading: an aggregate parameter is read by the leaf
AggQueryIn.Param, into an aggregate column.
Equations
- One or more equations did not get rendered due to their size.
Instances For
Dependency graph
The alternatives-free generation of every query of the algebra.
Equations
- GeneratesOnRecNoExplode T sch cnt S = ∀ {n : ℕ} {κ : Fin n → ColKind} (q : AggQuery T n κ), GeneratesAtNoExplode T sch cnt S q
Instances For
Dependency graph
The selection row, in the scope where no aggregate column is read as
a key: σ is in every generating set.
Dependency graph
The selection row, in the scope where no aggregate column is read as
a key: σ is in every generating set.