Kind-indexed general queries and their annotated semantics #
The general (non-fused) HAVING semantics: aggregate values produced by a
grouping operator γ^≼ are carried through further operators – projection,
join, union, additional selections – as symbolic tokens (AggValue) in
dedicated columns, and compared downstream, the possible worlds of such a
comparison being those of the originating group.
Kind-indexed syntax #
Queries are indexed by a column-kind vector κ : Fin n → ColKind
(regular vs aggregate-token), so that the scope conditions are enforced
statically and no theorem carries a well-formedness hypothesis:
Gamma(the decomposedγ^≼) takes an all-regular input – no aggregation over aggregate values;DedupandDiffexist only at all-regular kind vectors – no deduplication or difference over token columns (ProvSQL rejects these);- projection columns are either regular terms over regular columns
(
ProjColIn.term) or verbatim copies of token columns (ProjColIn.token) – no arithmetic over tokens (the constant-folded normal form); - selection atoms are regular comparisons over regular columns, or a
comparison of one bare token column against a regular term
(the normal form after ProvSQL's
normalize_agg_comparison).
Factored annotations and the σ/predsem combination #
The row annotation of the general evaluator is kept in factored form
GenAnn: a concrete part base : K together with pending, a multiset
of group-existence factors – one entry per γ-group whose tokens have
not yet been compared, recorded as the group's occurrence-annotation list
l and worth δ(⊕ l). The effective annotation of a row is
base ⊗ ⊗_{l ∈ pending} δ(⊕ l) (GenAnn.finalize).
This factoring implements the replace-the-δ-factor combination rule:
Gammaoutputs rows withbase = 𝟙and the group's factor pending – an uncompared group row finalizes toδ(⊕ U), as in ProvSQL;- a selection with aggregate atoms multiplies the predicate provenance
predsem(ψ)intobaseand removes a pending group factor exactly when the compared occurrences are that whole group – every compared token carries the factor's annotation list. In that case the predicate provenance ranges over the non-empty worlds of the very same occurrences, so it subsumes the group-existence factor, and conjoining both would count it twice in a non-idempotent semiring. A predicate comparing tokens of several groups keeps every group factor: its predicate provenance does not entail each group's existence (a disjunction guards only the disjunct that fires), and likewise a predicate that does not entail existence at all (GenPredIn.entailsExistence– e.g., an aggregate atom∨-mixed with a regular atom, whoseχcan fire in worlds where the group is empty) supersedes nothing. This mirrors ProvSQL's structural supersede (cmp_supersede.cppwithhaving_entails_group_existence), which drops a δ only when its ⊕-operands are exactly the compared aggregates' occurrence tokens and the predicate entails existence. Annotations accumulated from traversed operators (join partners inbase, other groups' pending entries) are always preserved; - a second selection comparing the same group's tokens finds no pending
entry left and simply multiplies: repeated comparisons yield the
⊗-product of their predicate provenances, matching the circuits ProvSQL builds (timesofcmpgates) – which coincides with the joint possible-world reading in idempotent semirings; - a projection dropping the last copy of a token column cashes the
group's factor into
base(the group can never be compared again).
∧ ↦ ⊗, ∨ ↦ ⊕ and ¬ pushed down to the atoms by De Morgan duality
with comparison-operator complementation, exactly as in HavingPred and
in ProvSQL. A selection whose predicate contains no aggregate atom
filters classically, matching Query.evaluateAnnotated.
Scalar aggregation (aggregation without grouping, whose empty input is a
real possible world in ProvSQL) is out of scope: Gamma is the grouped
operator only.
The kind of a column: a regular value or an aggregate token.
Instances For
Dependency graph
Dependency graph
The value-arm kind of a column kind: prov columns hold ordinary
values (as ProvSQL's uuid columns do), so their conformance arm is
reg.
Equations
Instances For
Dependency graph
A lifted column value: a regular value or an aggregate token, the
token being an ordinary one or a nested one (AggTok).
Instances For
Dependency graph
The deterministic reading of a lifted value.
Equations
Instances For
Dependency graph
How a lifted value is read as an aggregate expression: an
aggregate expression is itself – a term over several aggregate columns
is one – an ordinary token is the expression of itself
(AggExpr.ofValue, keeping the identities of its occurrences), and a
regular value reads no occurrence and returns itself
(NestedValue.constInner), so that aggregating a regular column nests
nothing. A nested value is no expression and is read here through its
collapse; a second-level aggregation reads it as a node instead
(GenValue.innerAt).
Equations
- One or more equations did not get rendered due to their size.
- GenValue.innerValue (Sum.inl v) = NestedValue.constInner v
- GenValue.innerValue (Sum.inr (AggTok.nest a)) = NestedValue.constInner a.collapse
- GenValue.innerValue (Sum.inr (AggTok.expr e)) = e
Instances For
Dependency graph
The storey a lifted value is read at by a second-level
aggregation: one above a nested value's own, 0 for anything else.
Equations
- GenValue.innerLev (Sum.inr (AggTok.nest a)) = a.lev + 1
- x✝.innerLev = 0
Instances For
Dependency graph
How a lifted value is read as the inner reading of a nested
aggregation of storey D: a nested value of storey D - 1 is a node of
that storey, read world by world with its own occurrences; anything else
is what storey D - 1 reads, down to an aggregate expression at storey
0 (GenValue.innerValue). The aggregation takes D to be the largest
storey its group's rows need, so every nested value is placed at its own
storey and none is read through its collapse.
Equations
- x.innerAt 0 = x.innerValue
- GenValue.innerAt (Sum.inr (AggTok.nest a)) D.succ = if h : a.lev = D then Sum.inr (h ▸ a.toNode) else Sum.inl (GenValue.innerAt (Sum.inr (AggTok.nest a)) D)
- x.innerAt D.succ = Sum.inl (x.innerAt D)
Instances For
Dependency graph
The factored annotation of a row of the general evaluator: the
concrete part base, and one pending group-existence factor per
γ-group whose tokens have not been compared yet, recorded as the
group's occurrence-annotation list.
- base : K
The concrete annotation accumulated so far.
The occurrence-annotation lists of the uncompared groups.
Instances For
Dependency graph
The effective annotation: the concrete part times the pending
group-existence factors δ(⊕ l).
Equations
- a.finalize = a.base * (Multiset.map (fun (l : List K) => SemiringWithMonus.delta l.sum) a.pending).prod
Instances For
Dependency graph
A row of the general evaluator.
Instances For
Dependency graph
Terms over regular columns #
A term over the regular columns of a kind-indexed tuple: the index
constructor requires its column to be regular, so terms over token
columns are unrepresentable.
- const {T : Type} {c n : ℕ} {κ : Fin n → ColKind} : T → TermGIn T c κ
- outer
{T : Type}
{c n : ℕ}
{κ : Fin n → ColKind}
: Fin c → TermGIn T c κ
An outer column: a column of the query this one is applied to, read as a value. It is what makes a query open, and there are none of them in a closed query,
cbeing0there. - index {T : Type} {c n : ℕ} {κ : Fin n → ColKind} (k : Fin n) : κ k = ColKind.reg → TermGIn T c κ
- provIndex {T : Type} {c n : ℕ} {κ : Fin n → ColKind} (k : Fin n) : κ k = ColKind.prov → TermGIn T c κ
- cmpAgg
{T : Type}
{c n : ℕ}
{κ : Fin n → ColKind}
(k : Fin n)
: κ k = ColKind.agg → CompOp → TermGIn T c κ → TermGIn T c κ
The aggregate-comparison gate (ProvSQL's
provsql_having): the predicate provenance of comparing the token in columnkagainst the term. Its faithful semantics lives in the rewritten world's term evaluator; the generic evaluators give it a total junk value, and on token-free kinds the constructor is unrepresentable. - chiGate
{T : Type}
{c n : ℕ}
{κ : Fin n → ColKind}
: CompOp → TermGIn T c κ → TermGIn T c κ → TermGIn T c κ
The regular-comparison indicator gate: the characteristic value
χof a comparison between two regular terms –𝟙if it holds on the row,𝟘otherwise. It is the primitive aHAVINGpredicate needs for its regular atoms, and likecmpAggits faithful semantics lives in the rewritten world's term evaluator – the generic evaluators give it a total junk value. UnlikecmpAggit carries no kind constraint, so it is representable over all-regular columns: the fragment on which the rewritten world's evaluator collapses to the plain semantics is cut out byTermGIn.chiFreeinstead. - add {T : Type} {c n : ℕ} {κ : Fin n → ColKind} : TermGIn T c κ → TermGIn T c κ → TermGIn T c κ
- sub {T : Type} {c n : ℕ} {κ : Fin n → ColKind} : TermGIn T c κ → TermGIn T c κ → TermGIn T c κ
- mul {T : Type} {c n : ℕ} {κ : Fin n → ColKind} : TermGIn T c κ → TermGIn T c κ → TermGIn T c κ
- caseWhen
{T : Type}
{c n : ℕ}
{κ : Fin n → ColKind}
: CompOp → TermGIn T c κ → TermGIn T c κ → TermGIn T c κ → TermGIn T c κ → TermGIn T c κ
SQL's searched
CASE, asTermIn.caseWhen. - coalesce
{T : Type}
{c n : ℕ}
{κ : Fin n → ColKind}
: TermGIn T c κ → TermGIn T c κ → TermGIn T c κ
SQL's
COALESCE, asTermIn.coalesce.
Instances For
Dependency graph
A term of a closed query: no outer column to read.
Instances For
Dependency graph
Evaluation of a term on a lifted tuple. On the regular columns the
kind index guarantees a regular value; the token arm of collapseSum is
never reached on kind-conformant tuples and merely keeps the function
total.
Equations
- (TermGIn.const a).eval u γ = a
- (TermGIn.outer k).eval u γ = γ k
- (TermGIn.index k a).eval u γ = AggValue.collapseSum (u k)
- (TermGIn.provIndex k a).eval u γ = AggValue.collapseSum (u k)
- (TermGIn.cmpAgg k a a_1 a_2).eval u γ = 0
- (TermGIn.chiGate a a_1 a_2).eval u γ = 0
- (t₁.add t₂).eval u γ = t₁.eval u γ + t₂.eval u γ
- (t₁.sub t₂).eval u γ = t₁.eval u γ - t₂.eval u γ
- (t₁.mul t₂).eval u γ = t₁.eval u γ * t₂.eval u γ
- (TermGIn.caseWhen op t₁ t₂ t₃ t₄).eval u γ = if op.eval3 (t₁.eval u γ) (t₂.eval u γ) = Kleene.true then t₃.eval u γ else t₄.eval u γ
- (t₁.coalesce t₂).eval u γ = if ValueType.isNull (t₁.eval u γ) = true then t₂.eval u γ else t₁.eval u γ
Instances For
Dependency graph
Generalized selection predicates #
A generalized selection predicate: regular comparisons between terms over regular columns, aggregate comparisons of one bare token column against a regular term (the constant-folded normal form), and Boolean structure.
- cmp
{T : Type}
{c n : ℕ}
{κ : Fin n → ColKind}
: CompOp → TermGIn T c κ → TermGIn T c κ → GenPredIn T c κ
Regular atom: comparison of two terms over regular columns.
- aggCmp
{T : Type}
{c n : ℕ}
{κ : Fin n → ColKind}
(k : Fin n)
: κ k = ColKind.agg → CompOp → TermGIn T c κ → GenPredIn T c κ
Aggregate atom: the token in column
kcompared against a regular term (a per-group constant: query constant or group-key attribute). - aggRange
{T : Type}
{c n : ℕ}
{κ : Fin n → ColKind}
(k : Fin n)
: κ k = ColKind.agg → CompOp → TermGIn T c κ → CompOp → TermGIn T c κ → GenPredIn T c κ
A range atom: the token in column
kcompared against two regular terms at once, read as one atom and not as the conjunction of two. The difference is not in what it says on a row – the two agree classically – but in what it annotates: one⊕-sum over the worlds where both comparisons hold, which is what a truncation'sm < #(k+1) ≤ m+casks for. A conjunction of two atoms instead multiplies two sums, and that is the same value only when the m-semiring is exclusive with an idempotent⊗(AggValue.predProvOf_mul_predProvOf_with). - and {T : Type} {c n : ℕ} {κ : Fin n → ColKind} : GenPredIn T c κ → GenPredIn T c κ → GenPredIn T c κ
- or {T : Type} {c n : ℕ} {κ : Fin n → ColKind} : GenPredIn T c κ → GenPredIn T c κ → GenPredIn T c κ
- not {T : Type} {c n : ℕ} {κ : Fin n → ColKind} : GenPredIn T c κ → GenPredIn T c κ
Instances For
Dependency graph
A predicate of a closed query.
Instances For
Dependency graph
The worlds a predicate is read in #
A predicate reading aggregate values is read in every world of the families they read, one world per family: values of one family share their occurrences and are read in one world, values of different families in independent ones. A world of a joint reading carries the product of its present annotations, the sum of its absent ones – the monus is taken once, over all the families – and the value each compared column takes there.
The value as an aggregate expression over its occurrence family: an ordinary token is the one-leaf expression, an expression is itself. A nested value is read through its own worlds and never here.
Equations
Instances For
Dependency graph
Whether a subfamily of a flat family is a world of every value of it
the columns M hold.
Equations
Instances For
Dependency graph
Whether a world of a nested family is a world of every nested value
the columns M hold.
Equations
Instances For
Dependency graph
The worlds of one family, read at the columns M of the row that
hold its values: per world, the product of the present annotations, the
sum of the absent ones, and the value of each of those columns. The
family is listed by the first of them, x₀; a world is one every value
of the family accepts – one meeting the group of each grouped value.
Equations
- One or more equations did not get rendered due to their size.
Instances For
Dependency graph
The aggregate columns among cols, with their values.
Equations
Instances For
Dependency graph
Two joint worlds read together: products multiply, absent sums add, and each column takes its value from the one that gives it one.
Equations
Instances For
Dependency graph
What groups two values of a row into one family of a joint reading: the family they were stamped with, together with their occurrence annotations and kind. Tokens of one family produced by one evaluation carry the same occurrences, so in a query whose operators bear distinct labels this is the family; the occurrences' annotations (and, for a nested value, its occurrences themselves) are part of the key so that the reading is defined on every row, a family being read in the worlds of the occurrences its members actually carry.
Equations
Instances For
Dependency graph
Decidable equality of a family key, stated once: the type is past the size instance search explores, and the nested component, which carries inner expressions, is compared classically – so that two keys with no nested component still compare in the kernel.
Equations
Dependency graph
The joint worlds of the columns cols of a row: one world of each
family they hold.
Equations
- One or more equations did not get rendered due to their size.
Instances For
Dependency graph
Does the predicate contain an aggregate atom? Selections without one filter classically.
Equations
- (GenPredIn.cmp a a_1 a_2).hasAggAtom = false
- (GenPredIn.aggCmp k a a_1 a_2).hasAggAtom = true
- (GenPredIn.aggRange k a a_1 a_2 a_3 a_4).hasAggAtom = true
- (φ.and ψ).hasAggAtom = (φ.hasAggAtom || ψ.hasAggAtom)
- (φ.or ψ).hasAggAtom = (φ.hasAggAtom || ψ.hasAggAtom)
- φ.not.hasAggAtom = φ.hasAggAtom
Instances For
Dependency graph
Classical (per-tuple) truth of a predicate, reading a compared token through its deterministic collapse. Used by the evaluator only on aggregate-atom-free predicates, where tokens are never consulted.
Equations
- (GenPredIn.cmp a a_1 a_2).eval3 u γ = a.eval3 (a_1.eval u γ) (a_2.eval u γ)
- (GenPredIn.aggCmp k a a_1 a_2).eval3 u γ = a_1.eval3 (AggValue.collapseSum (u k)) (a_2.eval u γ)
- (GenPredIn.aggRange k a a_1 a_2 a_3 a_4).eval3 u γ = (a_1.eval3 (AggValue.collapseSum (u k)) (a_2.eval u γ)).and (a_3.eval3 (AggValue.collapseSum (u k)) (a_4.eval u γ))
- (φ_1.and ψ).eval3 u γ = (φ_1.eval3 u γ).and (ψ.eval3 u γ)
- (φ_1.or ψ).eval3 u γ = (φ_1.eval3 u γ).or (ψ.eval3 u γ)
- φ_1.not.eval3 u γ = (φ_1.eval3 u γ).not
Instances For
Dependency graph
The rows a selection keeps: those on which the predicate is true. A row on which it is unknown is kept by neither the predicate nor its negation.
Equations
- φ.holds u γ = (φ.eval3 u γ = Kleene.true)
Instances For
Dependency graph
Structural decidability of holds.
Equations
- φ.decHolds u γ = GenPredIn.decHolds._aux_1 φ u γ
Instances For
Dependency graph
Equations
- φ.instDecidableHolds γ u = φ.decHolds u γ
Dependency graph
Predicate provenance of a generalized predicate on a row, with
¬ pushed down to the atoms by De Morgan duality (the neg flag):
a regular atom contributes its characteristic value χ, an aggregate
atom the predicate provenance predProv of the comparison over its
token's group, ∧ ↦ ⊗ and ∨ ↦ ⊕ (swapped under neg), and negated
atoms complement their comparison operator, as in ProvSQL.
These rules are a short cut, and what they are a short cut for is the
joint evaluation of the predicate's Boolean function in every world:
the ⊕, over the worlds of the union of the families the predicate
reads, of the world's annotation times the function's truth there,
which is AggExpr.predProv. That is the semantics, for ProvSQL as for
the library; computing it structurally is what an m-semiring with the
right properties permits, and the properties are the content of the
theorems. On one atom the two always agree
(AggExpr.predProv_ofValue). On a conjunction the product is a
decomposition of the joint reading under complementedness, exclusivity
and an idempotent ⊗ (Having.sum_mul_sum_of_overlap, and
complemented alone where the families are disjoint). On a disjunction
there is no such theorem: the ⊕ fires in worlds where one group is
empty, which are no worlds of the predicate, and 𝔹 and ℕ both
witness the difference (bool_or_ne_joint, nat_or_ne_joint), so
there the sum has to be computed rather than short cut. A range is the
same point for ∧ on one family, which is why aggRange is an atom of
its own rather than two atoms conjoined.
Equations
- One or more equations did not get rendered due to their size.
- (GenPredIn.cmp a a_1 a_2).predsem neg u γ = Having.chi (if neg = true then a.negate else a) (a_1.eval u γ) (a_2.eval u γ)
- (GenPredIn.aggCmp k a a_1 a_2).predsem neg u γ = match u k with | Sum.inl val => 0 | Sum.inr a => AggTok.predProvOf (if neg = true then a_1.negate else a_1) (a_2.eval u γ) a
- (φ_1.and ψ).predsem neg u γ = if neg = true then φ_1.predsem neg u γ + ψ.predsem neg u γ else φ_1.predsem neg u γ * ψ.predsem neg u γ
- (φ_1.or ψ).predsem neg u γ = if neg = true then φ_1.predsem neg u γ * ψ.predsem neg u γ else φ_1.predsem neg u γ + ψ.predsem neg u γ
- φ_1.not.predsem neg u γ = φ_1.predsem (!neg) u γ
Instances For
Dependency graph
The token columns compared by the predicate's aggregate atoms.
Equations
- (GenPredIn.cmp a a_1 a_2).comparedCols = ∅
- (GenPredIn.aggCmp k a a_1 a_2).comparedCols = {k}
- (GenPredIn.aggRange k a a_1 a_2 a_3 a_4).comparedCols = {k}
- (φ.and ψ).comparedCols = φ.comparedCols ∪ ψ.comparedCols
- (φ.or ψ).comparedCols = φ.comparedCols ∪ ψ.comparedCols
- φ.not.comparedCols = φ.comparedCols
Instances For
Dependency graph
The predicate's truth when each compared column takes the value v
gives it.
Equations
- (GenPredIn.cmp a a_1 a_2).eval3W v u γ = a.eval3 (a_1.eval u γ) (a_2.eval u γ)
- (GenPredIn.aggCmp k a a_1 a_2).eval3W v u γ = (v k).elim Kleene.unknown fun (a : T) => a_1.eval3 a (a_2.eval u γ)
- (GenPredIn.aggRange k a a_1 a_2 a_3 a_4).eval3W v u γ = (v k).elim Kleene.unknown fun (a : T) => (a_1.eval3 a (a_2.eval u γ)).and (a_3.eval3 a (a_4.eval u γ))
- (φ_1.and ψ).eval3W v u γ = (φ_1.eval3W v u γ).and (ψ.eval3W v u γ)
- (φ_1.or ψ).eval3W v u γ = (φ_1.eval3W v u γ).or (ψ.eval3W v u γ)
- φ_1.not.eval3W v u γ = (φ_1.eval3W v u γ).not
Instances For
Dependency graph
The joint predicate provenance: over the joint worlds of the
families the predicate reads, the world's annotation times the truth of
the predicate there (its falsity under neg).
Equations
- One or more equations did not get rendered due to their size.
Instances For
Dependency graph
Does the predicate provenance entail the compared groups' existence
(under the polarity neg of the enclosing negations)? An aggregate atom
does – its predicate provenance ranges over non-empty worlds only – while
a regular atom's χ does not. A conjunction (∧ positively, ∨ under
negation) entails as soon as one factor does; a disjunction only if every
disjunct does. Mirrors ProvSQL's having_entails_group_existence: the
supersede of the group-existence factor is licensed only when this holds,
since e.g., agg-atom ∨ regular-atom can fire in worlds where the group
is empty.
Equations
- (GenPredIn.cmp a a_1 a_2).entailsExistence x✝ = false
- (GenPredIn.aggCmp k a a_1 a_2).entailsExistence x✝ = true
- (GenPredIn.aggRange k a a_1 a_2 a_3 a_4).entailsExistence x✝ = true
- (φ.and ψ).entailsExistence x✝ = if x✝ = true then φ.entailsExistence x✝ && ψ.entailsExistence x✝ else φ.entailsExistence x✝ || ψ.entailsExistence x✝
- (φ.or ψ).entailsExistence x✝ = if x✝ = true then φ.entailsExistence x✝ || ψ.entailsExistence x✝ else φ.entailsExistence x✝ && ψ.entailsExistence x✝
- φ.not.entailsExistence x✝ = φ.entailsExistence !x✝
Instances For
Dependency graph
Projection columns #
The function a term over one variable computes. A column that reads an aggregate column reads it through a term, and the aggregate expression it builds applies the function the term computes: this is that function.
Instances For
Dependency graph
A unary term reading a column: the same term with the column in
place of its variable. It is how a term over an aggregate column re-types
– read on the column as a regular one – and TermIn.evalPlain_atCol
says the two compute the same value.
Equations
- TermIn.atCol i h (TermIn.const a) = TermGIn.const a
- TermIn.atCol i h (TermIn.outer a) = TermGIn.index i h
- TermIn.atCol i h #j = j.elim0
- TermIn.atCol i h (t₁.add t₂) = (TermIn.atCol i h t₁).add (TermIn.atCol i h t₂)
- TermIn.atCol i h (t₁.sub t₂) = (TermIn.atCol i h t₁).sub (TermIn.atCol i h t₂)
- TermIn.atCol i h (t₁.mul t₂) = (TermIn.atCol i h t₁).mul (TermIn.atCol i h t₂)
- TermIn.atCol i h (TermIn.caseWhen op t₁ t₂ t₃ t₄) = TermGIn.caseWhen op (TermIn.atCol i h t₁) (TermIn.atCol i h t₂) (TermIn.atCol i h t₃) (TermIn.atCol i h t₄)
- TermIn.atCol i h (t₁.coalesce t₂) = (TermIn.atCol i h t₁).coalesce (TermIn.atCol i h t₂)
Instances For
Dependency graph
One output column of a generalized projection: a regular term over the regular input columns, or a verbatim copy of a token column (no arithmetic over tokens: the normal form).
- term {T : Type} {c n : ℕ} {κ : Fin n → ColKind} : TermGIn T c κ → ProjColIn T c κ
- token {T : Type} {c n : ℕ} {κ : Fin n → ColKind} (k : Fin n) : κ k = ColKind.agg → ProjColIn T c κ
- aggTerm
{T : Type}
{c n : ℕ}
{κ : Fin n → ColKind}
(k : Fin n)
: κ k = ColKind.agg → (T → T) → ProjColIn T c κ
A term over one aggregate column: the column the term names, read through
gf. It is again an aggregate column – the unary aggregate expressiongf(a)ofProvenance.AggExpr, whichAggValue.postcomprepresents – and it is what SQL'scount(*) + 1and the ranks produce. Only the value ofgfin each world is used, so any deterministic function of SQL can be one. - aggTermOf
{T : Type}
{c n : ℕ}
{κ : Fin n → ColKind}
(k : Fin n)
: κ k = ColKind.agg → TermIn T 1 0 → ProjColIn T c κ
A term over one aggregate column, which is the shape the source language has: the column the term names, read through a term of the language,
TermIn.unarybeing the function it computes. This is the aggregate expressiong(a)withgthe function the term computes;aggTerm, which takes any function, is wider. Being a term, it re-types like any other column: the same term reads a regular column. - provTerm {T : Type} {c n : ℕ} {κ : Fin n → ColKind} : TermGIn T c κ → ProjColIn T c κ
Instances For
Dependency graph
Whether a column is one the source language writes. Every column
is, except the one carrying an arbitrary function of an aggregate column:
that one belongs to the rewritten world, where the cast of a column has
to act on the data arm of a composite value and leave the annotation arm
alone. AggQueryIn.usesOnly asks for it, as it asks a query to be free
of the other operators of that world.
Equations
- (ProjColIn.term a).sourceCol = true
- (ProjColIn.token k a).sourceCol = true
- (ProjColIn.aggTerm k a a_1).sourceCol = false
- (ProjColIn.aggTermOf k a a_1).sourceCol = true
- (ProjColIn.provTerm a).sourceCol = true
Instances For
Dependency graph
A projection column of a closed query.
Instances For
Dependency graph
The kind of the output column.
Equations
- (ProjColIn.term a).kind = ColKind.reg
- (ProjColIn.token k a).kind = ColKind.agg
- (ProjColIn.aggTerm k a a_1).kind = ColKind.agg
- (ProjColIn.aggTermOf k a a_1).kind = ColKind.agg
- (ProjColIn.provTerm a).kind = ColKind.prov
Instances For
Dependency graph
A term applied to an aggregate value: the value post-composed, its
identity recording the term (FamId.addTerm), so that two terms of one
column are two different parameters.
Equations
- AggTok.postcompTerm t x = AggTok.setFam (FamId.addTerm t x.fam) none (AggTok.postcomp t.unary x)
Instances For
Dependency graph
Evaluation of a projection column on a lifted tuple.
Equations
- (ProjColIn.term a).eval u γ = Sum.inl (a.eval u γ)
- (ProjColIn.token k a).eval u γ = u k
- (ProjColIn.aggTerm k a a_1).eval u γ = Sum.map a_1 (AggTok.postcomp a_1) (u k)
- (ProjColIn.aggTermOf k a a_1).eval u γ = Sum.map a_1.unary (AggTok.postcompTerm a_1) (u k)
- (ProjColIn.provTerm a).eval u γ = Sum.inl (a.eval u γ)
Instances For
Dependency graph
An ORDER BY inside an aggregation #
SQL writes one inside the aggregate – array_agg(x ORDER BY y),
string_agg, the ordered-set aggregates – and a symmetric aggregate
does not need it: count and sum read the same value whichever order
their group comes in. GroupOrder.unord says there is no clause, and
then the group is read in the domain's canonical order, which is what
every aggregation of this library did before the clause existed.
The order an aggregate reads its group in. A clause's ties are
broken by the row, as a window's are (OrderSpec.readLe), so the
sequence is a function of the group and not of any listing of it.
- unord
{T : Type}
{m : ℕ}
: GroupOrder T m
No clause: the group is read in the domain's canonical order.
- byCols
{T : Type}
{m p : ℕ}
(cols : Tuple (Fin m) p)
(spec : OrderSpec p)
: GroupOrder T m
The group is read in the clause
specon the columnscols.
Instances For
Dependency graph
The rows of a group in the order its aggregate reads them.
Equations
- Relation.groupSeqOrd is GroupOrder.unord r g = Relation.groupSeq is r g
- Relation.groupSeqOrd is (GroupOrder.byCols cols spec) r g = OrderSpec.sortSeq cols.key id spec (Relation.groupSeq is r g)
Instances For
Dependency graph
The same, cut by a FILTER clause where the aggregate carries
one: the clause cuts what the aggregate reads, and the order is the
aggregate's own.
Equations
- Relation.groupSeqOptOrd is ord r g none = Relation.groupSeqOrd is ord r g
- Relation.groupSeqOptOrd is ord r g (some φ) = List.filter φ.keeps (Relation.groupSeqOrd is ord r g)
Instances For
Dependency graph
The annotated group in the order its aggregate reads it: the occurrence sequence a token is built over. The clause reads the data columns, so it moves no annotation between occurrences carrying different rows.
Equations
- Having.havingGroupOrd is GroupOrder.unord r g = Having.havingGroup is r g
- Having.havingGroupOrd is (GroupOrder.byCols cols spec) r g = OrderSpec.sortSeq cols.key Prod.fst spec (Having.havingGroup is r g)
Instances For
Dependency graph
Kind-indexed queries #
Dependency graph
A term reads regular columns only. An aggregate column holds a
token, and a plain term reading one would read it through its
deterministic collapse – the value SQL prints for it, but not what it
reads in a given world. A window asks this of its aggregate term
(WinReadsReg); the way to read an aggregate column as a value is
AggQueryIn.Explode, which turns it into a regular one.
Equations
- TermIn.regOnly κ (TermIn.const a) = true
- TermIn.regOnly κ (TermIn.outer a) = true
- TermIn.regOnly κ #k = ((κ k).base == ColKind.reg)
- TermIn.regOnly κ (t₁.add t₂) = (TermIn.regOnly κ t₁ && TermIn.regOnly κ t₂)
- TermIn.regOnly κ (t₁.sub t₂) = (TermIn.regOnly κ t₁ && TermIn.regOnly κ t₂)
- TermIn.regOnly κ (t₁.mul t₂) = (TermIn.regOnly κ t₁ && TermIn.regOnly κ t₂)
- TermIn.regOnly κ (TermIn.caseWhen a t₁ t₂ t₃ t₄) = (TermIn.regOnly κ t₁ && TermIn.regOnly κ t₂ && TermIn.regOnly κ t₃ && TermIn.regOnly κ t₄)
- TermIn.regOnly κ (t₁.coalesce t₂) = (TermIn.regOnly κ t₁ && TermIn.regOnly κ t₂)
Instances For
Dependency graph
What a window may read of its input: its PARTITION BY, its
ORDER BY and its aggregate term read regular columns only. An aggregate
column of the input – that of an earlier window of the same SELECT, say
– is carried through unchanged and read by nothing, the determinized peer
order included (ColKind.readTuple). That is what makes the column read
in a world what the plain window reads of that world: an aggregate column
can order two occurrences one way in one world and the other way in the
next, so a window that read one would not commute with the possible
worlds. Ordering or partitioning by an aggregate reads it as a key,
through AggQueryIn.Explode.
Equations
- WinReadsReg κ P O t = ((∀ (k : Fin m), (κ (P k)).base = ColKind.reg) ∧ (∀ (k : Fin p), (κ (O k)).base = ColKind.reg) ∧ TermIn.regOnly κ t = true)
Instances For
Dependency graph
An all-regular input satisfies it with nothing to check.
Dependency graph
A multi-frame window (AggQueryIn.WinExpr) asks no such condition,
because its input is all-regular: its column is indexed by occurrence
rather than determined by the row, and an occurrence of the relation a
window reads does not determine the row it came from – two rows differing
only in an aggregate column read alike – so carrying an aggregate column
through one would need a canonical listing of general rows, which is an
order on AggTok.
What a selection on a recursive term asks of its predicate: no
aggregate atom. On a closed query – no hole – it asks nothing, and
trivial discharges it, which is what lets a closed selection be
written without a proof.
Instances For
Dependency graph
A predicate with no aggregate atom is fine on any term.
Dependency graph
The condition is read off the predicate's atoms only.
Dependency graph
A conjunction of two admissible predicates is admissible.
Dependency graph
Kind-indexed general queries. The index discipline enforces the
scope conditions: Gamma aggregates an all-regular input, Dedup and
Diff require all-regular kinds, and the projection/selection grammars
never compute over tokens.
- Rel
{T : Type}
{c : ℕ}
(n : ℕ)
: String → AggQueryIn T c n (ColKind.allReg n)
Base relation (all-regular).
- Hole
{T : Type}
{c : ℕ}
(n : ℕ)
(s : String)
(κ : Fin n → ColKind := ColKind.allReg n)
: AggQueryIn T c n κ [(s, n)]
The recursive reference: the relation name
sof aritynbound by the enclosing recursion, which is the one hole a recursive term holds. The last index of the syntax lists a term's holes, so a closed query has none, a recursion's term has exactly this one, and the operators a hole may sit under are those whose typing passes the index through: a projection, a selection with no aggregate atom, either side of a product, the left side of an apply, either side of a union, the alternatives and a retagging. Everything else is closed. This restriction on a recursive term is in the type rather than beside it. - Param
{T : Type}
{c m : ℕ}
(pv : Fin m → T ⊕ Fin c)
(ρ : Fin m → ColKind)
: AggQueryIn T c m ρ
Parameters, as a relation: one row annotated
𝟙, columnkbeing the parameterpv kof the context – or the constant it names – with kindρ k. In the right side of an apply the context starts with the row of its left side, and an aggregate column of that row is here an aggregate value, with its occurrences, read as any aggregate column is: a token column of a projection, an aggregate atom of a selection, a nested aggregation's term. That is how the semantics reads an aggregate parameter, world by world; a term'souter kreads a parameter as a plain value, and only a non-aggregate one (AggQueryIn.wellKinded). The parameters are addressed by position, likeouter, so the leaf substitutes as a term does. - Empty
{T : Type}
{c : ℕ}
: AggQueryIn T c 0 (ColKind.allReg 0)
The empty relation of arity
0, empty on every instance. It is the one leaf that belongs to the query and not to the instance, which is what makes it the base of everything a query can build from nowhere: the unit relation is the scalar aggregation of it with no aggregate (Derived.unit, one empty tuple annotated𝟙, which is PostgreSQL'sSELECT;), and SQL'sVALUESis a union of projections of that onto constants (Derived.values). A constant relation therefore needs no leaf of its own, and this one needs no side condition: non-emptiness is a condition of the derived notation, not of the syntax.Keeping it at arity
0is what leavesGammaScalaralone in its class: every other operator is empty on an empty instance, and the scalar aggregation is the one that emits a row regardless. - Proj
{T : Type}
{c n m : ℕ}
{κ : Fin n → ColKind}
{l : List (String × ℕ)}
(ps : Tuple (ProjColIn T c κ) m)
: AggQueryIn T c n κ l → AggQueryIn T c m (fun (j : Fin m) => (ps j).kind) l
Generalized projection.
- Sel
{T : Type}
{c n : ℕ}
{κ : Fin n → ColKind}
{l : List (String × ℕ)}
(φ : GenPredIn T c κ)
: AggQueryIn T c n κ l → (hφ : autoParam (SelOK l φ) _auto_1) → AggQueryIn T c n κ l
Generalized selection. On a recursive term – one with a hole – the predicate carries no aggregate atom, which the trailing proof says; on a closed query it says nothing, and the tactic finds it.
- Prod
{T : Type}
{c n₁ n₂ : ℕ}
{κ₁ : Fin n₁ → ColKind}
{κ₂ : Fin n₂ → ColKind}
{l₁ l₂ : List (String × ℕ)}
: AggQueryIn T c n₁ κ₁ l₁ → AggQueryIn T c n₂ κ₂ l₂ → AggQueryIn T c (n₁ + n₂) (Fin.append κ₁ κ₂) (l₁ ++ l₂)
Cartesian product (join).
- Apply
{T : Type}
{c n₁ n₂ : ℕ}
{κ₁ : Fin n₁ → ColKind}
{κ₂ : Fin n₂ → ColKind}
{l : List (String × ℕ)}
: AggQueryIn T c n₁ κ₁ l → AggQueryIn T (n₁ + c) n₂ κ₂ → AggQueryIn T c (n₁ + n₂) (Fin.append κ₁ κ₂) l
Apply – SQL's
LATERAL, the operator of Galindo-Legaria & Joshi: a product whose right side is read once per row of the left and may read that row's columns. The right side's context is the left side's columns followed by the ambient outer ones, so in a closed apply the right side reads exactly the left arity. Its output pairs each rowuof the left with each row of the right read atu, and multiplies their annotations.It is not derivable from the cross product once annotations are there: the product reads its right side once, the apply once per row of the left, and it is the apply that a correlated subquery needs.
The left side may carry aggregate columns, so that a product of two token-carrying relations is an apply too. The right side reads such a column world by world: the left row's values, tokens included, are the context of the environment the evaluator carries (
EvalEnv), and the leafAggQueryIn.Paramreads them into columns of the same kinds. A term reads a parameter as a plain value only where it is not aggregate (AggQueryIn.wellKinded). - Sum
{T : Type}
{c n : ℕ}
{κ : Fin n → ColKind}
{l₁ l₂ : List (String × ℕ)}
: AggQueryIn T c n κ l₁ → AggQueryIn T c n κ l₂ → AggQueryIn T c n κ (l₁ ++ l₂)
Union (all).
- Dedup
{T : Type}
{c n : ℕ}
: AggQueryIn T c n (ColKind.allReg n) → AggQueryIn T c n (ColKind.allReg n)
Duplicate elimination – all-regular only.
- Diff
{T : Type}
{c n : ℕ}
: AggQueryIn T c n (ColKind.allReg n) → AggQueryIn T c n (ColKind.allReg n) → AggQueryIn T c n (ColKind.allReg n)
Difference – all-regular only.
- Mu
{T : Type}
{c n : ℕ}
{κ : Fin n → ColKind}
(s : String)
: AggQueryIn T c n κ → AggQueryIn T c n κ [(s, n)] → AggQueryIn T c n κ
Recursion with duplicate-preserving rounds: SQL's
WITH RECURSIVE … UNION ALL. The relation namesof aritynis bound to the previous round insideq₁, so the rounds areM₀ = ⟦q₀⟧andM_{i+1} = ⟦q₁⟧_{d[s ↦ Mᵢ]}, and the query is their multiset sum.The operator is partial: it means the sum of the rounds up to the first empty one, and means nothing where no round is empty (
MuSettles). The evaluator is total and says⨄_{i<n} Mᵢfor thatnwhere there is one, junk elsewhere, which is why every result about a recursion carriesAggQueryIn.recSettles; a bounded computation witnesses the value throughAggQueryIn.evaluate_Mu_of_empty. The round count is not part of the query: a recursion that stops at a count rather than at its own rounds is not this operator.The rows a round carries may hold aggregate columns, with their aggregate values: the annotated evaluator binds the round in an environment of general rows (
EvalEnv), not in the database. The recursive term reads them as the restriction on it allows – carried by a projection, as a token or under a term (aggTermOf), but never compared, its selections reading regular columns only (SelOK). - MuSet
{T : Type}
{c n : ℕ}
(s : String)
: AggQueryIn T c n (ColKind.allReg n) → AggQueryIn T c n (ColKind.allReg n) [(s, n)] → AggQueryIn T c n (ColKind.allReg n)
Recursion up to duplicates: SQL's
WITH RECURSIVE … UNION. The least fixpoint the semantics says it is:X₀empty,X_{j+1} = ⟦ε(q₀ ⊎ q₁)⟧_{d[s ↦ X_j]}with annotations, and the query isX_jfor the firstjwithX_{j+1} = X_j.Partial, like
Mu: it means nothing where the rounds never settle (MuSetSettles), the evaluator says junk there, and results carryAggQueryIn.recSettles;AggQueryIn.evaluate_MuSet_of_fixturns a round that repeats into the value. It settles whenever no tuple has a derivation through itself, and in an absorptive semiring with such derivations too. - Explode
{T : Type}
{c n : ℕ}
{κ : Fin n → ColKind}
{l : List (String × ℕ)}
(k : Fin n)
: κ k = ColKind.agg → AggQueryIn T c n κ l → AggQueryIn T c n (Function.update κ k ColKind.reg) l
Exploding an aggregate column: reading it as a key. Every operator here that compares keys –
Dedup,Diff, the grouping and partition indices – takes regular columns, so a query that groups on a count or deduplicates on an aggregate is written by first reading the column as a key: the occurrence is replaced by its alternatives, one per value the column takes, each carrying[a ≐ v], and the column becomes regular (GenRow.alternativesAt). This is ProvSQL'srewrite_explode_agg_value(one row per value the aggregate takes over the possible worlds), the reading of an aggregate column as a key, as against the reading as a value, which the aggregate atoms and terms have world by world and which needs no operator. Over a plain relation an aggregate value is a value and this is the identity – it is a typing device there, charged to no class byusesOnly; in the annotated semantics it is an operator of its own, out of the language the annotated classification is about (noExplode). - Gamma
{T : Type}
{c m n₁ n₂ lab : ℕ}
{rd : Fin c → Bool}
(is : Tuple (Fin m) n₁)
(ts : Tuple (TermIn T c m) n₂)
(fs : Tuple (SeqAggFunc T) n₂)
: AggQueryIn T c m (ColKind.allReg m) →
(keep : optParam (Fin n₂ → Option (Selection T m)) fun (x : Fin n₂) => none) →
(ord : optParam (GroupOrder T m) GroupOrder.unord) →
AggQueryIn T c (n₁ + n₂) (Fin.append (fun (x : Fin n₁) => ColKind.reg) fun (x : Fin n₂) => ColKind.agg)
The decomposed grouping operator
γ^≼: group the (all-regular) input by the key columnsis; one output row per group, carrying the key followed by one aggregate token per(term, aggregate)pair.Each pair may carry a
FILTERclause,keep j, which cuts what that aggregate reads of its group – and nothing else. A filtered aggregate's column is therefore an aggregate expression over the whole group (AggExpr.ofGroupWhen): the worlds are the group's non-empty subfamilies, as with no clause, every occurrence carrying its annotation to them, and the leaf readsf []in a world holding only rejected rows – the row SQL emits for a group all of whose rows the clause rejects.noneis the aggregate with no clause, and the clause that keeps everything reads exactly asnonedoes. The clause reads the group's input row and no outer column, as SQL's does.It reads regular columns only, and not by convention: SQL forbids an aggregate inside the
FILTERof an aggregate, so a clause is a predicate of the plain value domain and not an atom over a token. Two consequences the metatheory lives off. Its truth at an occurrence is the same in every world, which is why no result here carries a hypothesis about what a clause reads – the worlds it cuts are the occurrence's own. And it is preserved by any transport that keeps the data columns, which is why the rewriting can carry a clause unchanged (Selection.castToAnnotatedTuple) with nothing to prove about it.Its
ordis theORDER BYinside the aggregates, which SQL writes asarray_agg(x ORDER BY y): the group is read in that clause's order rather than in the domain's canonical one, andGroupOrder.unord– the default – says there is no clause. A symmetric aggregate reads the same value either way; it is forarray_agg,string_aggand the order-dependent picks that the clause is the aggregate's own. The group's occurrence sequence, its existence factor and the rewritten world's reading all follow it (Having.havingGroupOrd,Relation.groupSeqOrd). - GammaScalar
{T : Type}
{c m n₂ lab : ℕ}
{rd : Fin c → Bool}
(ts : Tuple (TermIn T c m) n₂)
(fs : Tuple (SeqAggFunc T) n₂)
: AggQueryIn T c m (ColKind.allReg m) →
(ord : optParam (GroupOrder T m) GroupOrder.unord) → AggQueryIn T c n₂ fun (x : Fin n₂) => ColKind.agg
Aggregation without grouping: one output row whatever the input, its aggregates reading the whole of it.
It is not
Gammawith no keys. SQL forms a single group here that exists even over no row, so the row is annotated𝟙and carries no group-existence factor, and its tokens have the empty world among their worlds (AggValue.ofScalarGroup): an aggregate over an empty input has a value, and a comparison against it has to be given one. - GammaNest
{T : Type}
{c m n₁ : ℕ}
{κ : Fin m → ColKind}
{lab : ℕ}
{rd : Fin c → Bool}
(is : Tuple (Fin m) n₁)
(his : ∀ (k : Fin n₁), κ (is k) ≠ ColKind.agg)
(p : ProjColIn T c κ)
(f : Multiset T → T)
: AggQueryIn T c m κ → AggQueryIn T c (n₁ + 1) (Fin.append (fun (k : Fin n₁) => κ (is k)) fun (x : Fin 1) => ColKind.agg)
Second-level aggregation (an aggregate column read as a value): group by the key columns
is, none of which may be an aggregate column, and aggregate the projection columnpover each group underf. Becausepmay read an aggregate column, the token this builds is nested: its occurrences are the group's rows, and what each carries is the aggregate value read there rather than a value (AggTok.nest).Its occurrences are a bag. They carry tokens, which
≼does not order – that order is an order on plain tuples – so there is no sequence for an order-dependentfto read, and the outer aggregate is a function of the bag. An order-dependent outer aggregate has no reading of this kind and needs none: it goes throughExplode, after which the column read is regular and the aggregation is an ordinaryGamma.Where
preads a regular column the nesting degenerates – each occurrence carries an inner value that reads nothing (GenValue.innerValue) – and the token isGamma's own, read over the bag instead of over the≼-sorted sequence.One output token and not
n₂of them: two nested values over one group read it as two families, which is the joint readingAggExprgives an expression and not a product of two tokens. - ProvSum
{T : Type}
{c m n₁ : ℕ}
{κ : Fin m → ColKind}
(is : Tuple (Fin m) n₁)
(his : ∀ (k : Fin n₁), κ (is k) ≠ ColKind.agg)
(t : TermGIn T c κ)
: AggQueryIn T c m κ → AggQueryIn T c (n₁ + 1) (Fin.append (fun (k : Fin n₁) => κ (is k)) fun (x : Fin 1) => ColKind.prov)
Provenance aggregation: group by the key columns
is(none of which may be a token column) and⊕-sum the termtover each group into a singleprovoutput column – the abstract counterpart of ProvSQL's⊕-gate creation in rewritten plans. - Retag {T : Type} {c n : ℕ} {κ κ' : Fin n → ColKind} {l : List (String × ℕ)} (h : ∀ (k : Fin n), (κ k).base = (κ' k).base) : AggQueryIn T c n κ l → AggQueryIn T c n κ' l
- GammaTok
{T : Type}
{c m n₁ n₂ : ℕ}
{κ : Fin m → ColKind}
{lab : ℕ}
{rd : Fin c → Bool}
(is : Tuple (Fin m) n₁)
(his : ∀ (k : Fin n₁), κ (is k) ≠ ColKind.agg)
(ts : Tuple (TermIn T c m) n₂)
(fs : Tuple (SeqAggFunc T) n₂)
(a : TermGIn T c κ)
: AggQueryIn T c m κ →
(keep : optParam (Fin n₂ → Option (Selection T m)) fun (x : Fin n₂) => none) →
AggQueryIn T c (n₁ + n₂ + 1)
(Fin.append (Fin.append (fun (k : Fin n₁) => κ (is k)) fun (x : Fin n₂) => ColKind.agg) fun (x : Fin 1) =>
ColKind.prov)
Token-building grouping (ProvSQL's
provsql_agg): group by the key columnsis, output the keys, one aggregate token per(term, aggregate)pair whose occurrence annotations are the values of the explicit annotation terma(in rewritten plans: the provenance column of the subquery), and a trailingprovcolumn carrying the group-existence guard. Its faithful semantics lives in the rewritten world's evaluator; the generic evaluators give it total modeling semantics, and the world-faithfulness exclusions (noProvSum) rule it out of source queries.Its
keepis the same clause asAggQueryIn.Gamma's, read the same way: it cuts what an aggregate reads and leaves the family and the guard whole, so a filtered aggregate's column is an aggregate expression (AggExpr.ofGroupWhen) and not an ordinary token. The rewriting carries the source's clause into it unchanged (Selection.castToAnnotatedTuple), a clause asking the rewriting for no rule of its own.A clause over the rewritten schema could also compare the provenance column, which the transport never produces and which the semantics permits in one form only: as an evaluation of the annotation in
𝔹whose result does not enter an annotation, the way the displayed-value aggregate reads the rows whose token holds underhTop. Anything else would be evaluating an annotation while building one. - Win
{T : Type}
{c n m p : ℕ}
{κ : Fin n → ColKind}
{lab : ℕ}
{rd : Fin c → Bool}
(P : Tuple (Fin n) m)
(O : Tuple (Fin n) p)
(o : OrderSpec p)
(w : ValueFrame T p)
{hsql : ValueFrame.IsSQL o w}
(t : TermIn T c n)
(f : SeqAggFunc T)
: AggQueryIn T c n κ →
WinReadsReg κ P O t →
(dist : optParam Bool false) →
(keep : optParam (Option (Selection T n)) none) → AggQueryIn T c (n + 1) (Fin.snoc κ ColKind.agg)
The window operator. Every occurrence of the input keeps its row and its annotation and gains one column: the aggregate of
tunderfover that occurrence's frame, given by the partition columnsP, the order columnsO, theORDER BYclauseoand a framewdetermined by values. The clause does two things SQL asks of it and the domain's order cannot: it bounds aRANGEorGROUPSframe, and it fixes the order the frame is read in, which is what an aggregate that is not symmetric depends on.The frame is one of SQL's under the clause
o(hsql,ValueFrame.IsSQL): a frame clause reads its bounds in the window's ownORDER BY, and the wider language ofFrameCond, which may compare order columns each under a clause of its own, names frames no frame clause gives.It removes no row, merges none and changes no annotation, so it creates no group and produces no group-existence factor. Which occurrence a row is matters – two occurrences carrying the same row may have different frames, which is what
EXCLUDE CURRENT ROWasks for – and the convention in which a row reads its token is decided per row, by whether the row is in its own frame (ValueFrame.token).distsays whether the aggregate reads the frame's distinct values: one occurrence per class of equal values, carrying the⊕of the class's members and read in the order the domain gives their values (AggValue.mergeByValue), which no reading of the unmerged token recovers, so the operator has to carry it. Over plain relations it isSeqAggFunc.distinct, and the order being a function of the values is what makes the reading world by world sound with no condition on the aggregate (AggValue.specialize_mergeByValue). It defaults tofalse, so a window written without it means what it meant.Its input need not be all-regular, which is what a second window of one
SELECTneeds:rank() OVER (…), avg(x) OVER (…)is two windows, the second over a relation that already holds the first one's aggregate column. Such a column is carried through unchanged and read by nothing –WinReadsRegasks the partition, the order and the term to read regular columns, andColKind.readTuplekeeps an aggregate column out of the determinized peer order as well. Both halves are needed: an aggregate column can order two peers one way in one world and the other way in the next, so a window reading one would not commute with the possible worlds. Ordering or partitioning by an aggregate reads it as a key, throughAggQueryIn.Explode. - WinExpr
{T : Type}
{c n m p q lab : ℕ}
{rd : Fin c → Bool}
(P : Tuple (Fin n) m)
(O : Tuple (Fin n) p)
(o : OrderSpec p)
(ws : Fin q → ValueFrame T p)
{hsql : ∀ (l : Fin q), ValueFrame.IsSQL o (ws l)}
(ts : Fin q → TermIn T c n)
(fs : Fin q → SeqAggFunc T)
(g : (Fin q → T) → T)
: AggQueryIn T c n (ColKind.allReg n) →
(keeps : optParam (Fin q → Option (Selection T n)) fun (x : Fin q) => none) →
AggQueryIn T c (n + 1) (Fin.snoc (ColKind.allReg n) ColKind.agg)
A window over several frames of one partition, whose column is an aggregate expression and not an aggregate: leaf
laggregatests lwithfs lover the framews l, andgcombines the leaves' values. SQL's distribution functions are this operator –(r-1)/(N-1)forpercent_rank,c/Nforcume_dist, the bucket arithmetic forntile– each reading two frames of one partition.It reads the union of its frames as one family and records per leaf which of those occurrences that leaf reads (
ValueFrame.exprOf). The two families are nested –w_≺inside the partition – so a reading that cannot tell which occurrences the two share invents worlds: a rank of three beside a count of one. Everything is indexed by occurrence, so anEXCLUDE CURRENT ROWframe is as exact here as a single-frame window's. Each frame is one of SQL's under the clauseo(hsql), as a single-frame window's is.Why this is an operator and not a projection, here. It is a primitive of this syntax and not of the semantics. An aggregate value read as
⟨f, t, U⟩, carrying the occurrence sequence itself, makes a projection forming a term over two window columns denote the right aggregate expression overU₁ ∪ U₂already, with nothing to reconstruct.AggValuekeeps a value per occurrence instead ofU(the term is applied when the token is built), so two finished columns can no longer be related, and the sharing has to be recorded where it is still known.AggExpr.occsdoes record it – the value each leaf reads at each occurrence – but only for a leaf set fixed when the family is built, which is what an operator has and a projection does not.Like
Winit removes no row, merges none and changes no annotation, so it creates no group and leaves nothing pending. It is the one operator of the syntax that builds a non-tokcolumn, which is whyAggQueryIn.evaluate_ordinaryTokensis conditional onnoWinExpr.Its input is all-regular, where
Win's need not be, and that is a limit of the representation rather than of the semantics. A window over one frame carries an aggregate column of its input through unchanged, because its token is a function of the relation and of the row alone (ValueFrame.tokenOf) and needs no indexing; here the column is a function of the occurrence, which is what keepsEXCLUDE CURRENT ROWexact, and an occurrence is a position in a listing of the rows. A listing of a bag has to be independent of the listing it is computed from, so it is taken in the domain's order (OccFam.ofSorted) – and rows holding aggregate values have no order to be listed by, a token carrying functions. A family indexed by occurrences as primitive objects, in the manner ofNestedValue.World, would carry such a column with nothing further to prove: nothing here fails world by world, the reading a window takes of its input being the same in every world either way (ColKind.readTuple).
Instances For
Dependency graph
A closed query: one that reads no outer column.
Equations
- AggQuery T n κ = AggQueryIn T 0 n κ
Instances For
Dependency graph
Transport a query along an equality of kind vectors (kind vectors arising from projections are rarely definitionally all-regular).
Equations
- AggQueryIn.castKind h = Eq.rec (motive := fun (x : Fin n → ColKind) (h : κ = x) => AggQueryIn T c n κ l → AggQueryIn T c n x l) id h
Instances For
Dependency graph
The general evaluator #
The regular-value reading of a lifted tuple (token columns collapse;
on the all-regular rows fed to Dedup, Diff and Gamma no token
occurs).
Equations
- GenRow.plainTuple u k = AggValue.collapseSum (u k)
Instances For
Dependency graph
Finalize a general row into an annotated tuple: collapse the tuple to its regular reading and cash the pending group factors.
Equations
- r.toAnnotated = (GenRow.plainTuple r.1, r.2.finalize)
Instances For
Dependency graph
What a window reads of a plain row: its regular columns, and a
constant where the kinds put an aggregate column. Nothing of an aggregate
column is read – not even to break a tie in the ORDER BY, which is why
the determinized peer order is the same in every world (WinReadsReg
says why that is what a window must do). On all-regular columns it is the
row itself.
Equations
- ColKind.readTuple κ u k = match (κ k).base with | ColKind.agg => 0 | x => u k
Instances For
Dependency graph
What a window reads of a general row: ColKind.readTuple of its
columns, which is their collapse wherever a regular column sits.
Equations
- GenRow.readTuple κ u k = match (κ k).base with | ColKind.agg => 0 | x => AggValue.collapseSum (u k)
Instances For
Dependency graph
The occurrence a window's input relation gives a row of its input: what the window reads of the row, carrying the row's annotation.
Equations
- GenRow.readAnnotated κ r = (GenRow.readTuple κ r.1, r.2.finalize)
Instances For
Dependency graph
The copy number of each element of a list: how many equal elements
come before it, seen holding those already passed.
Equations
- List.copyNums eq x✝ [] = []
- List.copyNums eq x✝ (a :: as) = List.countP (eq a) x✝ :: List.copyNums eq (a :: x✝) as
Instances For
Dependency graph
The identities of a window's occurrences: an occurrence of the frame
of the row is numbered by the position, in the listing of its partition, of
the first row equal to it, plus its copy number among the equal rows of the
frame. So the frames of one partition give one occurrence one identity, and
a frame holding a row holds the identity of its first copy. Two equal rows
get one frame: under EXCLUDE CURRENT ROW the semantics gives each the
frame without itself, which a frame computed from the row alone cannot.
Equations
- One or more equations did not get rendered due to their size.
Instances For
Dependency graph
The row a window gives a row of its input: the row itself, one
column longer, carrying the token the relation gives it – or, under a
FILTER clause, the aggregate expression over the whole frame whose leaf
reads what the clause keeps.
Its own columns go through untouched, aggregate columns included: a window reads regular columns and rewrites none of them. So do its annotation and its pending factors, a window creating no group.
Equations
- One or more equations did not get rendered due to their size.
Instances For
Dependency graph
The identities of a multi-frame window's occurrences: an
occurrence the expression of the row i reads is numbered by its index in
the sorted input, which is how the expression indexes it. So the
expressions of every row give one occurrence one identity.
Equations
Instances For
Dependency graph
Embed an annotated tuple as a general row (all-regular, nothing pending).
Instances For
Dependency graph
The alternatives of an occurrence at one aggregate column: one
row per value the column's aggregate value takes, the column made
regular and the annotation multiplied by [a ≐ v]
(AggValue.altProv). A column already regular has the occurrence
itself as its only alternative. This is how an operator that compares
keys reads an aggregate column.
Equations
- One or more equations did not get rendered due to their size.
Instances For
Dependency graph
The multiset of occurrence-annotation lists of the token columns of a tuple (used by projection to detect dropped groups).
Equations
- tokenLists u = Multiset.filterMap (fun (k : Fin n) => match u k with | Sum.inl val => none | Sum.inr a => some a.annList) Finset.univ.val
Instances For
Dependency graph
Equations
- (TermGIn.const a).evalPlain u γ = a
- (TermGIn.outer k).evalPlain u γ = γ k
- (TermGIn.index k a).evalPlain u γ = u k
- (TermGIn.provIndex k a).evalPlain u γ = u k
- (TermGIn.cmpAgg k a a_1 a_2).evalPlain u γ = 0
- (TermGIn.chiGate a a_1 a_2).evalPlain u γ = 0
- (t₁.add t₂).evalPlain u γ = t₁.evalPlain u γ + t₂.evalPlain u γ
- (t₁.sub t₂).evalPlain u γ = t₁.evalPlain u γ - t₂.evalPlain u γ
- (t₁.mul t₂).evalPlain u γ = t₁.evalPlain u γ * t₂.evalPlain u γ
- (TermGIn.caseWhen op t₁ t₂ t₃ t₄).evalPlain u γ = if op.eval3 (t₁.evalPlain u γ) (t₂.evalPlain u γ) = Kleene.true then t₃.evalPlain u γ else t₄.evalPlain u γ
- (t₁.coalesce t₂).evalPlain u γ = if ValueType.isNull (t₁.evalPlain u γ) = true then t₂.evalPlain u γ else t₁.evalPlain u γ
Instances For
Dependency graph
A term over regular columns read as a general term: the same term, the kind index witnessing that every column it reads is regular. It is what a projection needs to carry a term of the aggregation grammar, whose input is all-regular.
Equations
- (TermIn.const a).toGen = TermGIn.const a
- (TermIn.outer a).toGen = TermGIn.outer a
- (#k).toGen = TermGIn.index k ⋯
- (t₁.add t₂).toGen = t₁.toGen.add t₂.toGen
- (t₁.sub t₂).toGen = t₁.toGen.sub t₂.toGen
- (t₁.mul t₂).toGen = t₁.toGen.mul t₂.toGen
- (TermIn.caseWhen a t₁ t₂ t₃ t₄).toGen = TermGIn.caseWhen a t₁.toGen t₂.toGen t₃.toGen t₄.toGen
- (t₁.coalesce t₂).toGen = t₁.toGen.coalesce t₂.toGen
Instances For
Dependency graph
The gate-free fragment #
The indicator gate TermGIn.chiGate is the one term constructor whose
faithful reading needs the rewritten world: it produces a provenance
value out of a comparison between regular values, which the generic
evaluators – having no annotation to return – can only approximate by
the junk constant. The cmpAgg gate escapes the same fate only because
its kind constraint keeps it off the columns the plain semantics sees.
The predicates below cut out the fragment where no indicator gate occurs,
on which the rewritten world's evaluator is the plain semantics
(AggQueryIn.evaluateRew_plain).
No indicator gate in a term.
Equations
- (TermGIn.const a).chiFree = True
- (TermGIn.outer a).chiFree = True
- (TermGIn.index k a).chiFree = True
- (TermGIn.provIndex k a).chiFree = True
- (TermGIn.cmpAgg k a a_1 t).chiFree = t.chiFree
- (TermGIn.chiGate a a_1 a_2).chiFree = False
- (t₁.add t₂).chiFree = (t₁.chiFree ∧ t₂.chiFree)
- (t₁.sub t₂).chiFree = (t₁.chiFree ∧ t₂.chiFree)
- (t₁.mul t₂).chiFree = (t₁.chiFree ∧ t₂.chiFree)
- (t₁.coalesce t₂).chiFree = (t₁.chiFree ∧ t₂.chiFree)
- (TermGIn.caseWhen a t₁ t₂ t₃ t₄).chiFree = (t₁.chiFree ∧ t₂.chiFree ∧ t₃.chiFree ∧ t₄.chiFree)
Instances For
Dependency graph
No indicator gate in a predicate.
Equations
Instances For
Dependency graph
No indicator gate in a projection column.
Equations
- (ProjColIn.term t).chiFree = t.chiFree
- (ProjColIn.provTerm t).chiFree = t.chiFree
- (ProjColIn.token k a).chiFree = True
- (ProjColIn.aggTerm k a a_1).chiFree = True
- (ProjColIn.aggTermOf k a a_1).chiFree = True
Instances For
Dependency graph
The rounds of a recursion #
Both recursions iterate a step on relations; neither needs the query
syntax, so both are plain recursions on the round number with their own
lemmas. muSum collects the rounds of Mu – their multiset sum –
and muIter runs the fixpoint iteration of MuSet.
What the semantics calls “some round is empty” is in force here as the
hypothesis step 0 = 0: the sum ⨄_{i≥0} Mᵢ over all rounds is a
relation only because an empty round is a fixpoint of the round
function, which is what SQL's requirement that the recursive reference
occur in the body buys. Nothing in this syntax enforces that, so it is
asked for where it is used.
The multiset sum of the first b + 1 iterates of step from M.
Instances For
Dependency graph
The b-th iterate of step from the empty relation.
Instances For
Dependency graph
What the recursions mean: the rounds settling #
muSum and muIter run a given number of rounds, which is a tool and
not the semantics: a recursion means the value its rounds settle at, and
means nothing where they do not settle. MuSetSettles and MuSettles
say when there is such a value, muFix and muSumFix are it, and the
two transfer lemmas below are how a bounded computation witnesses it –
reach a round that repeats, or an empty one, and the semantics is that
value.
A set recursion settles when some round equals the next. The rounds are then constant from there on, so the value is well defined.
Instances For
Dependency graph
A duplicate-preserving recursion settles when some round past the first is empty, which is where SQL's own iteration stops.
Instances For
Dependency graph
The first round at which a set recursion repeats; 0 where it never
does (Nat.sInf_empty), which is junk and is what makes the total
function below say nothing where the semantics says nothing.
Instances For
Dependency graph
The number of rounds a duplicate-preserving recursion sums: up to the
first empty one, 0 where there is none.
Instances For
Dependency graph
The value a set recursion settles at – X_j for the first j
with X_{j+1} = X_j. Junk (∅) where the rounds never settle, which no
statement about it may read: a result about a set recursion carries
MuSetSettles as a hypothesis.
Instances For
Dependency graph
The value a duplicate-preserving recursion settles at – the sum of the rounds up to the first empty one. Junk where no round is empty.
Instances For
Dependency graph
A map commutes with the value a set recursion settles at, where
it settles: the images of the rounds are the rounds of the image, so a
fixpoint maps to a fixpoint, and the image settles no later. This is what
replaces muIter_map once the round count is not part of the query.
Dependency graph
A map commutes with the value a duplicate-preserving recursion settles at, where it settles and an empty round stays empty.
Dependency graph
Steps that agree have the same settling value, for a duplicate-preserving recursion.
Dependency graph
Steps that agree have the same fixpoint, for a duplicate-eliminating recursion.
Dependency graph
Duplicate elimination on an annotated relation: one slot per tuple,
annotated by the ⊕ of its copies – what Dedup computes, named for
the rounds of MuSet.
Equations
- r.dedupAnn = ↑↑(groupByKey r)
Instances For
Dependency graph
The kind of a lifted value.
Equations
Instances For
Dependency graph
A row has the kinds κ: a regular value where κ says regular or
provenance, a token where it says aggregate.
Instances For
Dependency graph
Dependency graph
What the annotated evaluator reads besides the database and the
plain context: the rounds a recursion binds to its name, as general rows
– a round may carry aggregate columns, which a database cannot hold – and
the context with its aggregate values, which an apply extends with the row
of its left side and the leaf AggQueryIn.Param reads. A closed query
reads neither.
The round bound to each recursive name, at each arity.
The context, aggregate values included.
Instances For
Dependency graph
Binding a recursive name to a round.
Equations
Instances For
Dependency graph
The context of arity c, aggregate values included: the one the
environment holds when it has that arity, and the plain context read as
regular values otherwise – which is what a context with no aggregate value
is.
Equations
Instances For
Dependency graph
Setting the context.
Instances For
Dependency graph
What the leaf AggQueryIn.Param pv ρ reads: the row whose column k is
the parameter or constant pv k, when it has the kinds ρ, annotated
𝟙.
Equations
- One or more equations did not get rendered due to their size.
Instances For
Dependency graph
Every value the environment holds has the property Q: in the
rows of every round it binds and in its context.
Equations
Instances For
Dependency graph
The parameters an operator reads #
An occurrence belongs to the operator that produces it and to the values of the apply parameters that operator reads: an operator evaluated on the same inputs produces the same occurrences, and one reading different parameter values produces different ones. So the family an aggregating operator stamps on its values records those values, and these functions say which parameters (outer columns) a term, a predicate or a whole subquery reads.
Does the term read the outer column k?
Equations
- TermIn.readsOuter k (TermIn.const a) = false
- TermIn.readsOuter k (TermIn.outer j) = decide (j = k)
- TermIn.readsOuter k #a = false
- TermIn.readsOuter k (t₁.add t₂) = (TermIn.readsOuter k t₁ || TermIn.readsOuter k t₂)
- TermIn.readsOuter k (t₁.sub t₂) = (TermIn.readsOuter k t₁ || TermIn.readsOuter k t₂)
- TermIn.readsOuter k (t₁.mul t₂) = (TermIn.readsOuter k t₁ || TermIn.readsOuter k t₂)
- TermIn.readsOuter k (t₁.coalesce t₂) = (TermIn.readsOuter k t₁ || TermIn.readsOuter k t₂)
- TermIn.readsOuter k (TermIn.caseWhen a t₁ t₂ t₃ t₄) = (TermIn.readsOuter k t₁ || TermIn.readsOuter k t₂ || TermIn.readsOuter k t₃ || TermIn.readsOuter k t₄)
Instances For
Dependency graph
Does the term read the outer column k?
Equations
- TermGIn.readsOuter k (TermGIn.const a) = false
- TermGIn.readsOuter k (TermGIn.outer j) = decide (j = k)
- TermGIn.readsOuter k (TermGIn.index k_1 a) = false
- TermGIn.readsOuter k (TermGIn.provIndex k_1 a) = false
- TermGIn.readsOuter k (TermGIn.cmpAgg k_1 a a_1 t) = TermGIn.readsOuter k t
- TermGIn.readsOuter k (TermGIn.chiGate a t₁ t₂) = (TermGIn.readsOuter k t₁ || TermGIn.readsOuter k t₂)
- TermGIn.readsOuter k (t₁.add t₂) = (TermGIn.readsOuter k t₁ || TermGIn.readsOuter k t₂)
- TermGIn.readsOuter k (t₁.sub t₂) = (TermGIn.readsOuter k t₁ || TermGIn.readsOuter k t₂)
- TermGIn.readsOuter k (t₁.mul t₂) = (TermGIn.readsOuter k t₁ || TermGIn.readsOuter k t₂)
- TermGIn.readsOuter k (t₁.coalesce t₂) = (TermGIn.readsOuter k t₁ || TermGIn.readsOuter k t₂)
- TermGIn.readsOuter k (TermGIn.caseWhen a t₁ t₂ t₃ t₄) = (TermGIn.readsOuter k t₁ || TermGIn.readsOuter k t₂ || TermGIn.readsOuter k t₃ || TermGIn.readsOuter k t₄)
Instances For
Dependency graph
Does the predicate read the outer column k?
Equations
- GenPredIn.readsOuter k (GenPredIn.cmp a a_1 a_2) = (TermGIn.readsOuter k a_1 || TermGIn.readsOuter k a_2)
- GenPredIn.readsOuter k (GenPredIn.aggCmp k_1 a a_1 a_2) = TermGIn.readsOuter k a_2
- GenPredIn.readsOuter k (GenPredIn.aggRange k_1 a a_1 a_2 a_3 a_4) = (TermGIn.readsOuter k a_2 || TermGIn.readsOuter k a_4)
- GenPredIn.readsOuter k (φ.and ψ) = (GenPredIn.readsOuter k φ || GenPredIn.readsOuter k ψ)
- GenPredIn.readsOuter k (φ.or ψ) = (GenPredIn.readsOuter k φ || GenPredIn.readsOuter k ψ)
- GenPredIn.readsOuter k φ.not = GenPredIn.readsOuter k φ
Instances For
Dependency graph
Does the projection column read the outer column k?
Equations
- ProjColIn.readsOuter k (ProjColIn.term t) = TermGIn.readsOuter k t
- ProjColIn.readsOuter k (ProjColIn.token k_1 a) = false
- ProjColIn.readsOuter k (ProjColIn.aggTerm k_1 a a_1) = false
- ProjColIn.readsOuter k (ProjColIn.aggTermOf k_1 a a_1) = false
- ProjColIn.readsOuter k (ProjColIn.provTerm t) = TermGIn.readsOuter k t
Instances For
Dependency graph
Does the query read the outer column k? An apply's right side
reads its own parameters after the left row's columns, and an aggregating
operator reads the parameters it records, its stamps holding their
values.
Equations
- One or more equations did not get rendered due to their size.
- (AggQueryIn.Rel x✝¹ a).readsOuter x✝ = false
- (AggQueryIn.Hole x✝² s x✝¹).readsOuter x✝ = false
- (AggQueryIn.Param pv x✝¹).readsOuter x✝ = (List.finRange x✝²).any fun (i : Fin x✝²) => Sum.elim (fun (x : T) => false) (fun (j : Fin x✝³) => decide (j = x✝)) (pv i)
- AggQueryIn.Empty.readsOuter x✝ = false
- (AggQueryIn.Proj ps q).readsOuter x✝ = (((List.finRange x✝²).any fun (j : Fin x✝²) => ProjColIn.readsOuter x✝ (ps j)) || q.readsOuter x✝)
- (AggQueryIn.Sel φ q hφ).readsOuter x✝ = (GenPredIn.readsOuter x✝ φ || q.readsOuter x✝)
- (q₁.Prod q₂).readsOuter x✝ = (q₁.readsOuter x✝ || q₂.readsOuter x✝)
- (q₁.Apply q₂).readsOuter x✝ = (q₁.readsOuter x✝ || q₂.readsOuter (Fin.natAdd n₁ x✝))
- (q₁.Sum q₂).readsOuter x✝ = (q₁.readsOuter x✝ || q₂.readsOuter x✝)
- q.Dedup.readsOuter x✝ = q.readsOuter x✝
- (q₁.Diff q₂).readsOuter x✝ = (q₁.readsOuter x✝ || q₂.readsOuter x✝)
- (AggQueryIn.Explode k a q).readsOuter x✝ = q.readsOuter x✝
- (AggQueryIn.Mu s q₀ q₁).readsOuter x✝ = (q₀.readsOuter x✝ || q₁.readsOuter x✝)
- (AggQueryIn.MuSet s q₀ q₁).readsOuter x✝ = (q₀.readsOuter x✝ || q₁.readsOuter x✝)
- (AggQueryIn.Gamma is ts fs q keep ord).readsOuter x✝ = (((List.finRange n₂).any fun (j : Fin n₂) => TermIn.readsOuter x✝ (ts j)) || q.readsOuter x✝ || rd x✝)
- (AggQueryIn.GammaScalar ts fs q ord).readsOuter x✝ = (((List.finRange x✝¹).any fun (j : Fin x✝¹) => TermIn.readsOuter x✝ (ts j)) || q.readsOuter x✝ || rd x✝)
- (AggQueryIn.GammaNest is his p f q).readsOuter x✝ = (ProjColIn.readsOuter x✝ p || q.readsOuter x✝ || rd x✝)
- (AggQueryIn.ProvSum is his t q).readsOuter x✝ = (TermGIn.readsOuter x✝ t || q.readsOuter x✝)
- (AggQueryIn.Retag h q).readsOuter x✝ = q.readsOuter x✝
- (AggQueryIn.Win P O o w t f q a dist keep).readsOuter x✝ = (TermIn.readsOuter x✝ t || q.readsOuter x✝ || rd x✝)
- (AggQueryIn.WinExpr P O o ws ts fs g q_1 keeps).readsOuter x✝ = (((List.finRange q).any fun (j : Fin q) => TermIn.readsOuter x✝ (ts j)) || q_1.readsOuter x✝ || rd x✝)
Instances For
Dependency graph
The values of the parameters an operator reads, in the order of the context: what a family records besides the operator's label and the key of the group.
Equations
Instances For
Dependency graph
How a family records a parameter: a regular one by its value, an aggregate one by its identity – the aggregate value itself, not the value it takes in a world.
Equations
- GenValue.paramId (Sum.inl val) = Sum.inl val
- GenValue.paramId (Sum.inr a) = Sum.inr a.fam
Instances For
Dependency graph
The parameters of the context E that the read set r records.
Instances For
Dependency graph
The nested value of a bag of lifted values, each with its
annotation: one occurrence per element, carrying what the value reads at
the storey the bag needs – one above the deepest nested value it holds
(GenValue.innerAt).
Equations
- One or more equations did not get rendered due to their size.
Instances For
Dependency graph
The nested value a second-level aggregation builds over a group: one occurrence per row, carrying what the column reads there, and the row's annotation.
Equations
- nestOfGroup p γ f φ grp = nestOfVals f φ (Multiset.map (fun (row : GenRow T K m) => (p.eval row.1 γ, row.2.finalize)) grp)
Instances For
Dependency graph
The general annotated evaluator. All operators preserve the factored-annotation discipline described in the module docstring.
Equations
- One or more equations did not get rendered due to their size.
- (AggQueryIn.Rel n s).evaluate d γ E = match AnnotatedDatabase.find n s d with | none => ∅ | some rn => Multiset.map GenRow.ofAnnotated rn
- (AggQueryIn.Hole n s κ).evaluate d γ E = Multiset.filter (fun (r : GenRow T K n) => GenRow.Conforms κ r.1) (E.holes s n)
- (AggQueryIn.Param pv κ).evaluate d γ E = E.paramRows γ pv κ
- AggQueryIn.Empty.evaluate d γ E = ∅
- (q₁.Sum q₂).evaluate d γ E = q₁.evaluate d γ E + q₂.evaluate d γ E
- q_2.Dedup.evaluate d γ E = Multiset.map GenRow.ofAnnotated ↑↑(groupByKey (Multiset.map GenRow.toAnnotated (q_2.evaluate d γ E)))
- (AggQueryIn.Explode k a q_2).evaluate d γ E = (q_2.evaluate d γ E).bind fun (r : GenRow T K n) => r.alternativesAt k
- (AggQueryIn.Mu s q₀ q₁).evaluate d γ E = muSumFix (fun (X : Multiset (GenRow T K n)) => q₁.evaluate d γ (E.assignHole s X)) (q₀.evaluate d γ E)
- (AggQueryIn.Retag h q_2).evaluate d γ E = q_2.evaluate d γ E
Instances For
Dependency graph
The final annotated relation computed by a general query: evaluate, then finalize every row.
Equations
- q.evaluateAnnotated d γ E = Multiset.map GenRow.toAnnotated (q.evaluate d γ E)
Instances For
Dependency graph
What the recursions compute, and when the bound drops out #
The round function of Mu: the body read with the name bound to the
previous round. A round is a bag of general rows, aggregate columns
included.
Equations
- AggQueryIn.muStep s q₁ d γ E X = q₁.evaluate d γ (E.assignHole s X)
Instances For
Dependency graph
The round function of MuSet: ε(q₀ ⊎ q₁) read with the name bound
to the previous round.
Equations
- AggQueryIn.muSetStep s q₀ q₁ d γ E X = (q₀.evaluateAnnotated d γ E + q₁.evaluateAnnotated d γ (E.assignHole s (Multiset.map GenRow.ofAnnotated X))).dedupAnn
Instances For
Dependency graph
The row a window gives a row of its input relation: the row itself, one column longer, with the token the relation gives it, its annotation kept and nothing pending – a window creates no group.
Equations
- One or more equations did not get rendered due to their size.
Instances For
Dependency graph
The Win case of the evaluator, read off the relation. The output is
the input relation mapped row by row, each row gaining the token its relation
gives it. This is the form every theorem about the operator uses; that it is
legitimate – that an occurrence's token is determined by the relation even
though its frame is not determined by its row – is ValueFrame.tokenOf.
Dependency graph
The plain evaluator #
The classical (per-instance) semantics of a general query: aggregate
columns hold the computed aggregate values, and every selection filters
classically – including aggregate comparisons, evaluated on the computed
values. This is the semantics the data-part adequacy connects to the
annotated evaluator through AggValue.collapse (the annotated side keeps
classically-failing rows with annotation 𝟘, exactly as ProvSQL emits
them, so adequacy is stated on the query stripped of its aggregate
selections and differences, stripAgg).
Classical truth of a predicate on a regular tuple: aggregate atoms compare the computed aggregate value of their column.
Equations
- (GenPredIn.cmp op t₁ t₂).evalPlain3 u γ = op.eval3 (t₁.evalPlain u γ) (t₂.evalPlain u γ)
- (GenPredIn.aggCmp k a op t).evalPlain3 u γ = op.eval3 (u k) (t.evalPlain u γ)
- (GenPredIn.aggRange k a op₁ t₁ op₂ t₂).evalPlain3 u γ = (op₁.eval3 (u k) (t₁.evalPlain u γ)).and (op₂.eval3 (u k) (t₂.evalPlain u γ))
- (φ_2.and ψ).evalPlain3 u γ = (φ_2.evalPlain3 u γ).and (ψ.evalPlain3 u γ)
- (φ_2.or ψ).evalPlain3 u γ = (φ_2.evalPlain3 u γ).or (ψ.evalPlain3 u γ)
- φ_2.not.evalPlain3 u γ = (φ_2.evalPlain3 u γ).not
Instances For
Dependency graph
The rows a selection keeps classically: those on which the predicate is true.
Equations
- φ.holdsPlain u γ = (φ.evalPlain3 u γ = Kleene.true)
Instances For
Dependency graph
Structural decidability of holdsPlain.
Equations
- φ.decHoldsPlain u γ = GenPredIn.decHoldsPlain._aux_1 φ u γ
Instances For
Dependency graph
Equations
- φ.instDecidableHoldsPlain γ u = φ.decHoldsPlain u γ
Dependency graph
Plain evaluation of a projection column.
Equations
- (ProjColIn.term a).evalPlain u γ = a.evalPlain u γ
- (ProjColIn.token k a).evalPlain u γ = u k
- (ProjColIn.aggTerm k a a_1).evalPlain u γ = a_1 (u k)
- (ProjColIn.aggTermOf k a a_1).evalPlain u γ = a_1.unary (u k)
- (ProjColIn.provTerm a).evalPlain u γ = a.evalPlain u γ
Instances For
Dependency graph
The value a window's added column takes on a row of a plain relation: the aggregate of the term over that row's frame, read off the relation.
Equations
- ValueFrame.windowValue P O o w t f R u γ = f (List.map (fun (v : Tuple T n) => t.eval v γ) (ValueFrame.frameListOf id P O o w R u))
Instances For
Dependency graph
The value a window's added column takes under a FILTER
clause: the aggregate over the rows of the frame the clause keeps.
Equations
- ValueFrame.windowValueWhen P O o w t f keep R u γ = f (List.map (fun (v : Tuple T n) => t.eval v γ) (List.filter keep (ValueFrame.frameListOf id P O o w R u)))
Instances For
Dependency graph
The value one leaf of a multi-frame window takes: the aggregate
over its frame, over the part its own FILTER clause keeps where it
carries one.
Equations
- ValueFrame.windowValueOpt P O o w t f none R u γ = ValueFrame.windowValue P O o w t f R u γ
- ValueFrame.windowValueOpt P O o w t f (some φ) R u γ = ValueFrame.windowValueWhen P O o w t f φ.keeps R u γ
Instances For
Dependency graph
The plain evaluator: standard multiset semantics, with Gamma
computing the aggregate of each group's full occurrence sequence (in the
canonical ≼ order of Relation.groupSeq) and every selection filtering
classically. Diff is the all-or-nothing difference of
Query.evaluate.
Equations
- One or more equations did not get rendered due to their size.
- (AggQueryIn.Rel x✝² s).evaluatePlain x✝¹ x✝ = match Database.find x✝² s x✝¹ with | none => ∅ | some rn => rn
- (AggQueryIn.Hole x✝³ s x✝²).evaluatePlain x✝¹ x✝ = match Database.find x✝³ s x✝¹ with | none => ∅ | some rn => rn
- (AggQueryIn.Param pv x✝²).evaluatePlain x✝¹ x✝ = {fun (k : Fin x✝³) => Sum.elim id x✝ (pv k)}
- AggQueryIn.Empty.evaluatePlain x✝¹ x✝ = 0
- (AggQueryIn.Proj ps q).evaluatePlain x✝¹ x✝ = Multiset.map (fun (u : Tuple T n_1) (j : Fin x✝³) => (ps j).evalPlain u x✝) (q.evaluatePlain x✝¹ x✝)
- (AggQueryIn.Sel φ q hφ).evaluatePlain x✝¹ x✝ = Multiset.filter (fun (u : Tuple T x✝⁴) => φ.holdsPlain u x✝) (q.evaluatePlain x✝¹ x✝)
- (q₁.Prod q₂).evaluatePlain x✝¹ x✝ = q₁.evaluatePlain x✝¹ x✝ * q₂.evaluatePlain x✝¹ x✝
- (q₁.Sum q₂).evaluatePlain x✝¹ x✝ = q₁.evaluatePlain x✝¹ x✝ + q₂.evaluatePlain x✝¹ x✝
- q.Dedup.evaluatePlain x✝¹ x✝ = Multiset.dedup (q.evaluatePlain x✝¹ x✝)
- (AggQueryIn.Explode k a q).evaluatePlain x✝¹ x✝ = q.evaluatePlain x✝¹ x✝
- (AggQueryIn.Mu s q₀ q₁).evaluatePlain x✝¹ x✝ = muSumFix (fun (X : Multiset (Tuple T x✝³)) => q₁.evaluatePlain (Database.assign s X x✝¹) x✝) (q₀.evaluatePlain x✝¹ x✝)
- (AggQueryIn.MuSet s q₀ q₁).evaluatePlain x✝¹ x✝ = muFix fun (X : Multiset (Tuple T x✝²)) => Multiset.dedup (q₀.evaluatePlain x✝¹ x✝ + q₁.evaluatePlain (Database.assign s X x✝¹) x✝)
- (q₁.Diff q₂).evaluatePlain x✝¹ x✝ = Multiset.filter (fun (t : Tuple T x✝²) => t ∉ q₂.evaluatePlain x✝¹ x✝) (q₁.evaluatePlain x✝¹ x✝)
- (AggQueryIn.Retag h q).evaluatePlain x✝¹ x✝ = q.evaluatePlain x✝¹ x✝
Instances For
Dependency graph
Where the aggregate is symmetric the sequence a frame is read in does
not matter: any listing of the frame gives the value the window gives, so
the canonical order the library sorts by is as good as the order an ORDER BY asks for. It is for an aggregate that is not symmetric – PICKFIRST –
that the two have to be the same order.
Dependency graph
The Win case of the plain evaluator, read off the relation.
Dependency graph
The row a window gives a row of its input relation under a FILTER
clause: as ValueFrame.windowRow, with the clause's column – an
aggregate expression over the whole frame, the clause cutting what its
leaf reads (ValueFrame.exprWhenOf).
Equations
- One or more equations did not get rendered due to their size.
Instances For
Dependency graph
Strip a general query of the constructs whose annotated data part
keeps rows the classical semantics removes: differences (annotated Diff
never removes tuple slots) and selections containing an aggregate atom
(the annotated evaluator keeps classically-failing rows annotated 𝟘,
as ProvSQL emits them). The data-part adequacy of evaluateAnnotated
is stated against the plain evaluation of the stripped query, mirroring
Query.stripDiff in Provenance.QueryAdequacy.
Equations
- (AggQueryIn.Rel x✝ s).stripAgg = AggQueryIn.Rel x✝ s
- (AggQueryIn.Hole x✝¹ s x✝).stripAgg = AggQueryIn.Hole x✝¹ s x✝
- (AggQueryIn.Param pv x✝).stripAgg = AggQueryIn.Param pv x✝
- AggQueryIn.Empty.stripAgg = AggQueryIn.Empty
- (AggQueryIn.Proj ps q).stripAgg = AggQueryIn.Proj ps q.stripAgg
- (AggQueryIn.Sel φ q hφ).stripAgg = if φ.hasAggAtom = true then q.stripAgg else AggQueryIn.Sel φ q.stripAgg hφ
- (q₁.Prod q₂).stripAgg = q₁.stripAgg.Prod q₂.stripAgg
- (q₁.Apply q₂).stripAgg = q₁.stripAgg.Apply q₂.stripAgg
- (q₁.Sum q₂).stripAgg = q₁.stripAgg.Sum q₂.stripAgg
- q.Dedup.stripAgg = q.stripAgg.Dedup
- (q₁.Diff a).stripAgg = q₁.stripAgg
- (AggQueryIn.Explode k h q).stripAgg = AggQueryIn.Explode k h q.stripAgg
- (AggQueryIn.Mu s q₀ q₁).stripAgg = AggQueryIn.Mu s q₀.stripAgg q₁.stripAgg
- (AggQueryIn.MuSet s q₀ q₁).stripAgg = AggQueryIn.MuSet s q₀.stripAgg q₁.stripAgg
- (AggQueryIn.Gamma is ts fs q keep ord).stripAgg = AggQueryIn.Gamma is ts fs q.stripAgg keep ord
- (AggQueryIn.GammaScalar ts fs q ord).stripAgg = AggQueryIn.GammaScalar ts fs q.stripAgg ord
- (AggQueryIn.GammaNest is his p f q).stripAgg = AggQueryIn.GammaNest is his p f q.stripAgg
- (AggQueryIn.ProvSum is his t q).stripAgg = AggQueryIn.ProvSum is his t q.stripAgg
- (AggQueryIn.Retag h q).stripAgg = AggQueryIn.Retag h q.stripAgg
- (AggQueryIn.GammaTok is his ts fs a q keep).stripAgg = AggQueryIn.GammaTok is his ts fs a q.stripAgg keep
- (AggQueryIn.Win P O o w t f q hrr dist keep).stripAgg = AggQueryIn.Win P O o w t f q.stripAgg hrr dist keep
- (AggQueryIn.WinExpr P O o ws ts fs g q_1 keeps).stripAgg = AggQueryIn.WinExpr P O o ws ts fs g q_1.stripAgg keeps
Instances For
Dependency graph
No plan-level provenance aggregation. The possible-world
metatheorems (random-world commutation, PQE) are about source queries;
ProvSum is a rewriting-target operator whose deterministic group sum
is not world-faithful – exactly as the classical Agg was excluded from
the annotated evaluators.
Equations
- (AggQueryIn.Rel x✝ s).noProvSum = True
- (AggQueryIn.Hole x✝¹ s x✝).noProvSum = True
- (AggQueryIn.Param pv x✝).noProvSum = True
- AggQueryIn.Empty.noProvSum = True
- (AggQueryIn.Proj ps q).noProvSum = q.noProvSum
- (AggQueryIn.Sel φ q hφ).noProvSum = q.noProvSum
- (q₁.Prod q₂).noProvSum = (q₁.noProvSum ∧ q₂.noProvSum)
- (q₁.Apply q₂).noProvSum = (q₁.noProvSum ∧ q₂.noProvSum)
- (q₁.Sum q₂).noProvSum = (q₁.noProvSum ∧ q₂.noProvSum)
- q.Dedup.noProvSum = q.noProvSum
- (q₁.Diff a).noProvSum = (q₁.noProvSum ∧ a.noProvSum)
- (AggQueryIn.Explode k h q).noProvSum = q.noProvSum
- (AggQueryIn.Mu s q₀ q₁).noProvSum = (q₀.noProvSum ∧ q₁.noProvSum)
- (AggQueryIn.MuSet s q₀ q₁).noProvSum = (q₀.noProvSum ∧ q₁.noProvSum)
- (AggQueryIn.Gamma is ts fs q keep ord).noProvSum = q.noProvSum
- (AggQueryIn.GammaScalar ts fs q ord).noProvSum = q.noProvSum
- (AggQueryIn.GammaNest is his p f q).noProvSum = q.noProvSum
- (AggQueryIn.ProvSum is his t q).noProvSum = False
- (AggQueryIn.Retag h q).noProvSum = q.noProvSum
- (AggQueryIn.GammaTok is his ts fs a q keep).noProvSum = False
- (AggQueryIn.Win P O o w t f q hrr dist keep).noProvSum = q.noProvSum
- (AggQueryIn.WinExpr P O o ws ts fs g q_1 keeps).noProvSum = q_1.noProvSum
Instances For
Dependency graph
Terms reading the context only where it is plain #
A term reads a parameter as a plain value through outer k; that is the
right reading only of a parameter that is not aggregate, an aggregate one
being read, world by world, through the leaf AggQueryIn.Param.
outerOk ok says every outer k of a term has ok k, and the readings
agree on contexts agreeing there.
Every outer column the term reads satisfies ok.
Equations
- TermIn.outerOk ok (TermIn.const a) = True
- TermIn.outerOk ok (TermIn.outer j) = ok j
- TermIn.outerOk ok #a = True
- TermIn.outerOk ok (t₁.add t₂) = (TermIn.outerOk ok t₁ ∧ TermIn.outerOk ok t₂)
- TermIn.outerOk ok (t₁.sub t₂) = (TermIn.outerOk ok t₁ ∧ TermIn.outerOk ok t₂)
- TermIn.outerOk ok (t₁.mul t₂) = (TermIn.outerOk ok t₁ ∧ TermIn.outerOk ok t₂)
- TermIn.outerOk ok (t₁.coalesce t₂) = (TermIn.outerOk ok t₁ ∧ TermIn.outerOk ok t₂)
- TermIn.outerOk ok (TermIn.caseWhen a t₁ t₂ t₃ t₄) = (TermIn.outerOk ok t₁ ∧ TermIn.outerOk ok t₂ ∧ TermIn.outerOk ok t₃ ∧ TermIn.outerOk ok t₄)
Instances For
Dependency graph
Equations
- TermGIn.outerOk ok (TermGIn.const a) = True
- TermGIn.outerOk ok (TermGIn.outer j) = ok j
- TermGIn.outerOk ok (TermGIn.index k a) = True
- TermGIn.outerOk ok (TermGIn.provIndex k a) = True
- TermGIn.outerOk ok (TermGIn.cmpAgg k a a_1 t) = TermGIn.outerOk ok t
- TermGIn.outerOk ok (TermGIn.chiGate a t₁ t₂) = (TermGIn.outerOk ok t₁ ∧ TermGIn.outerOk ok t₂)
- TermGIn.outerOk ok (t₁.add t₂) = (TermGIn.outerOk ok t₁ ∧ TermGIn.outerOk ok t₂)
- TermGIn.outerOk ok (t₁.sub t₂) = (TermGIn.outerOk ok t₁ ∧ TermGIn.outerOk ok t₂)
- TermGIn.outerOk ok (t₁.mul t₂) = (TermGIn.outerOk ok t₁ ∧ TermGIn.outerOk ok t₂)
- TermGIn.outerOk ok (t₁.coalesce t₂) = (TermGIn.outerOk ok t₁ ∧ TermGIn.outerOk ok t₂)
- TermGIn.outerOk ok (TermGIn.caseWhen a t₁ t₂ t₃ t₄) = (TermGIn.outerOk ok t₁ ∧ TermGIn.outerOk ok t₂ ∧ TermGIn.outerOk ok t₃ ∧ TermGIn.outerOk ok t₄)
Instances For
Dependency graph
Equations
- GenPredIn.outerOk ok (GenPredIn.cmp a a_1 a_2) = (TermGIn.outerOk ok a_1 ∧ TermGIn.outerOk ok a_2)
- GenPredIn.outerOk ok (GenPredIn.aggCmp k a a_1 a_2) = TermGIn.outerOk ok a_2
- GenPredIn.outerOk ok (GenPredIn.aggRange k a a_1 a_2 a_3 a_4) = (TermGIn.outerOk ok a_2 ∧ TermGIn.outerOk ok a_4)
- GenPredIn.outerOk ok (φ.and ψ) = (GenPredIn.outerOk ok φ ∧ GenPredIn.outerOk ok ψ)
- GenPredIn.outerOk ok (φ.or ψ) = (GenPredIn.outerOk ok φ ∧ GenPredIn.outerOk ok ψ)
- GenPredIn.outerOk ok φ.not = GenPredIn.outerOk ok φ
Instances For
Dependency graph
Equations
- ProjColIn.outerOk ok (ProjColIn.term t) = TermGIn.outerOk ok t
- ProjColIn.outerOk ok (ProjColIn.token k a) = True
- ProjColIn.outerOk ok (ProjColIn.aggTerm k a a_1) = True
- ProjColIn.outerOk ok (ProjColIn.aggTermOf k a a_1) = True
- ProjColIn.outerOk ok (ProjColIn.provTerm t) = TermGIn.outerOk ok t
Instances For
Dependency graph
The kinds of the rounds each recursive name is bound to.
Instances For
Dependency graph
Dependency graph
Binding a recursive name to rounds of kinds κ.
Equations
Instances For
Dependency graph
The query is well-kinded in a context of kinds ρc, its recursive
names bound to rounds of kinds HK: a hole has the kinds of the rounds of
its name, a parameter leaf the kinds of the parameters it reads (a
constant being regular), and so, inside, at every apply and every
recursion. This is what the kind-indexed syntax cannot say by itself,
the context and the rounds being read through the evaluation's
environment.
Equations
- One or more equations did not get rendered due to their size.
- (AggQueryIn.Rel x✝² a).wellKinded x✝¹ x✝ = True
- (AggQueryIn.Hole x✝³ s x✝²).wellKinded x✝¹ x✝ = ∀ (k : Fin x✝³), (x✝² k).base = (x✝ s x✝³ k).base
- (AggQueryIn.Param pv x✝²).wellKinded x✝¹ x✝ = ∀ (k : Fin x✝³), (x✝² k).base = Sum.elim (fun (x : T) => ColKind.reg) (fun (j : Fin x✝⁴) => (x✝¹ j).base) (pv k)
- AggQueryIn.Empty.wellKinded x✝¹ x✝ = True
- (AggQueryIn.Proj ps q).wellKinded x✝¹ x✝ = ((∀ (j : Fin x✝³), ProjColIn.outerOk (fun (k : Fin x✝⁴) => (x✝¹ k).base ≠ ColKind.agg) (ps j)) ∧ q.wellKinded x✝¹ x✝)
- (AggQueryIn.Sel φ q hφ).wellKinded x✝¹ x✝ = (GenPredIn.outerOk (fun (k : Fin x✝⁵) => (x✝¹ k).base ≠ ColKind.agg) φ ∧ q.wellKinded x✝¹ x✝)
- (q₁.Prod q₂).wellKinded x✝¹ x✝ = (q₁.wellKinded x✝¹ x✝ ∧ q₂.wellKinded x✝¹ x✝)
- (q₁.Apply q₂).wellKinded x✝¹ x✝ = (q₁.wellKinded x✝¹ x✝ ∧ q₂.wellKinded (Fin.append κ₁ x✝¹) x✝)
- (q₁.Sum q₂).wellKinded x✝¹ x✝ = (q₁.wellKinded x✝¹ x✝ ∧ q₂.wellKinded x✝¹ x✝)
- q.Dedup.wellKinded x✝¹ x✝ = q.wellKinded x✝¹ x✝
- (q₁.Diff q₂).wellKinded x✝¹ x✝ = (q₁.wellKinded x✝¹ x✝ ∧ q₂.wellKinded x✝¹ x✝)
- (AggQueryIn.Explode k a q).wellKinded x✝¹ x✝ = q.wellKinded x✝¹ x✝
- (AggQueryIn.Mu s q₀ q₁).wellKinded x✝¹ x✝ = (q₀.wellKinded x✝¹ x✝ ∧ q₁.wellKinded x✝¹ (x✝.assign s x✝²))
- (AggQueryIn.MuSet s q₀ q₁).wellKinded x✝¹ x✝ = (q₀.wellKinded x✝¹ x✝ ∧ q₁.wellKinded x✝¹ (x✝.assign s (ColKind.allReg x✝²)))
- (AggQueryIn.Gamma is ts fs q keep ord).wellKinded x✝¹ x✝ = ((∀ (j : Fin n₂), TermIn.outerOk (fun (k : Fin x✝²) => (x✝¹ k).base ≠ ColKind.agg) (ts j)) ∧ q.wellKinded x✝¹ x✝)
- (AggQueryIn.GammaScalar ts fs q ord).wellKinded x✝¹ x✝ = ((∀ (j : Fin x✝²), TermIn.outerOk (fun (k : Fin x✝³) => (x✝¹ k).base ≠ ColKind.agg) (ts j)) ∧ q.wellKinded x✝¹ x✝)
- (AggQueryIn.GammaNest is his p f q).wellKinded x✝¹ x✝ = (ProjColIn.outerOk (fun (k : Fin x✝²) => (x✝¹ k).base ≠ ColKind.agg) p ∧ q.wellKinded x✝¹ x✝)
- (AggQueryIn.ProvSum is his t q).wellKinded x✝¹ x✝ = (TermGIn.outerOk (fun (k : Fin x✝²) => (x✝¹ k).base ≠ ColKind.agg) t ∧ q.wellKinded x✝¹ x✝)
- (AggQueryIn.Retag h q).wellKinded x✝¹ x✝ = q.wellKinded x✝¹ x✝
- (AggQueryIn.Win P O o w t f q a dist keep).wellKinded x✝¹ x✝ = (TermIn.outerOk (fun (k : Fin x✝²) => (x✝¹ k).base ≠ ColKind.agg) t ∧ q.wellKinded x✝¹ x✝)
- (AggQueryIn.WinExpr P O o ws ts fs g q_1 keeps).wellKinded x✝¹ x✝ = ((∀ (j : Fin q), TermIn.outerOk (fun (k : Fin x✝²) => (x✝¹ k).base ≠ ColKind.agg) (ts j)) ∧ q_1.wellKinded x✝¹ x✝)
Instances For
Dependency graph
The environment agrees with the kinds: its context, at the arity
c, has the kinds ρc and the plain values γ, and every round it binds
to a name has the kinds HK gives that name.
Equations
- E.Kinded γ ρc HK = (GenRow.Conforms ρc (E.ctxAt c γ) ∧ GenRow.plainTuple (E.ctxAt c γ) = γ ∧ ∀ (s : String) (n : ℕ), ∀ r ∈ E.holes s n, GenRow.Conforms (HK s n) r.1)
Instances For
Dependency graph
No aggregate column read as a key. Reading one produces a row
per value the column takes in some world, so the data part of the
annotated evaluation is not the data part of any one world, and the
annotation-forgetting adequacy of evaluateAnnotated_toPlain does not
hold for it – unlike the readings that are world readings, the
Boolean support and the random world, which Explode respects.
Equations
- (AggQueryIn.Rel x✝ s).noExplode = True
- (AggQueryIn.Hole x✝¹ s x✝).noExplode = True
- (AggQueryIn.Param pv x✝).noExplode = True
- AggQueryIn.Empty.noExplode = True
- (AggQueryIn.Proj ps q).noExplode = q.noExplode
- (AggQueryIn.Sel φ q hφ).noExplode = q.noExplode
- (q₁.Prod q₂).noExplode = (q₁.noExplode ∧ q₂.noExplode)
- (q₁.Apply q₂).noExplode = (q₁.noExplode ∧ q₂.noExplode)
- (q₁.Sum q₂).noExplode = (q₁.noExplode ∧ q₂.noExplode)
- q.Dedup.noExplode = q.noExplode
- (q₁.Diff a).noExplode = (q₁.noExplode ∧ a.noExplode)
- (AggQueryIn.Explode k h q).noExplode = False
- (AggQueryIn.Mu s q₀ q₁).noExplode = (q₀.noExplode ∧ q₁.noExplode)
- (AggQueryIn.MuSet s q₀ q₁).noExplode = (q₀.noExplode ∧ q₁.noExplode)
- (AggQueryIn.Gamma is ts fs q keep ord).noExplode = q.noExplode
- (AggQueryIn.GammaScalar ts fs q ord).noExplode = q.noExplode
- (AggQueryIn.GammaNest is his p f q).noExplode = q.noExplode
- (AggQueryIn.ProvSum is his t q).noExplode = q.noExplode
- (AggQueryIn.Retag h q).noExplode = q.noExplode
- (AggQueryIn.GammaTok is his ts fs a q keep).noExplode = q.noExplode
- (AggQueryIn.Win P O o w t f q hrr dist keep).noExplode = q.noExplode
- (AggQueryIn.WinExpr P O o ws ts fs g q_1 keeps).noExplode = q_1.noExplode
Instances For
Dependency graph
Join conditions on key columns #
The conjunction of key equalities between two blocks of regular columns
(the join condition of the Diff rewriting).
The atoms are SQL's IS NOT DISTINCT FROM, not =: a key join keys on
values, two nulls being the same key, where NULL = NULL is unknown and
would drop the row.
Equations
- One or more equations did not get rendered due to their size.
Instances For
Dependency graph
Kind transport is transparent to evaluation (row types do not mention the kind vector).
Dependency graph
The kind vector of a Gamma output: key columns then token columns.
Equations
- ColKind.gammaKinds n₁ n₂ = Fin.append (fun (x : Fin n₁) => ColKind.reg) fun (x : Fin n₂) => ColKind.agg
Instances For
Dependency graph
Kind conformance #
Rows produced by the general evaluator conform to the query's kind vector: regular columns hold regular values, token columns hold tokens. This is an invariant lemma, not a hypothesis: the kind-indexed syntax makes it hold by construction, and downstream theorems (the random-world commutation in particular) invoke it instead of assuming wellformedness.
Every aggregate column of a tuple holds an ordinary token –
neither a nested value nor an expression over several of them. On a
row the evaluator produces it is a theorem for a query with no
multi-frame window, no second-level aggregation and no FILTER clause
(AggQueryIn.evaluate_ordinaryTokens).
Instances For
Dependency graph
No column of a tuple holds a nested token. Weaker than
GenRow.OrdinaryTokens, which also excludes an aggregate expression.
On a row the evaluator produces it is a theorem for a query with no
second-level aggregation (AggQueryIn.evaluate_noNested).
Instances For
Dependency graph
No FILTER clause. A grouping may cut the occurrence sequence
one of its aggregates reads (AggQueryIn.Gamma's keep, and
AggQueryIn.GammaTok's in the rewritten world), a window the part of its
frame it reads (AggQueryIn.Win's keep), and a multi-frame window the
part of each leaf's frame (AggQueryIn.WinExpr's keeps).
What asks this is AggQueryIn.evaluate_ordinaryTokens, and for the
reason that fence exists: a filtered aggregate of a grouping or of a
frame builds an aggregate expression and not an ordinary token, the
clause cutting what the expression reads and not its family. Nothing
else asks it. In particular the rewritten world's evaluator reads a
clause like the plain one does – both through
Relation.groupSeqOpt and ValueFrame.windowValueOpt – so
AggQueryIn.evaluateRew_plain covers a filtered grouping and a filtered
window, as the evaluators, the hom commutation, the possible-world
reading and the data-part adequacy already did.
Equations
- (AggQueryIn.Rel x✝ s).noFilter = True
- (AggQueryIn.Hole x✝¹ s x✝).noFilter = True
- (AggQueryIn.Param pv x✝).noFilter = True
- AggQueryIn.Empty.noFilter = True
- (AggQueryIn.Proj ps q).noFilter = q.noFilter
- (AggQueryIn.Sel φ q hφ).noFilter = q.noFilter
- (q₁.Prod q₂).noFilter = (q₁.noFilter ∧ q₂.noFilter)
- (q₁.Apply q₂).noFilter = (q₁.noFilter ∧ q₂.noFilter)
- (q₁.Sum q₂).noFilter = (q₁.noFilter ∧ q₂.noFilter)
- q.Dedup.noFilter = q.noFilter
- (q₁.Diff a).noFilter = (q₁.noFilter ∧ a.noFilter)
- (AggQueryIn.Explode k h q).noFilter = q.noFilter
- (AggQueryIn.Mu s q₀ q₁).noFilter = (q₀.noFilter ∧ q₁.noFilter)
- (AggQueryIn.MuSet s q₀ q₁).noFilter = (q₀.noFilter ∧ q₁.noFilter)
- (AggQueryIn.Gamma is ts fs q keep ord).noFilter = ((∀ (j : Fin n₂), keep j = none) ∧ q.noFilter)
- (AggQueryIn.GammaScalar ts fs q ord).noFilter = q.noFilter
- (AggQueryIn.GammaNest is his p f q).noFilter = q.noFilter
- (AggQueryIn.ProvSum is his t q).noFilter = q.noFilter
- (AggQueryIn.Retag h q).noFilter = q.noFilter
- (AggQueryIn.GammaTok is his ts fs a q keep).noFilter = ((∀ (j : Fin n₂), keep j = none) ∧ q.noFilter)
- (AggQueryIn.Win P O o w t f q hrr dist keep).noFilter = (keep = none ∧ q.noFilter)
- (AggQueryIn.WinExpr P O o ws ts fs g q_1 keeps).noFilter = ((∀ (l : Fin q), keeps l = none) ∧ q_1.noFilter)
Instances For
Dependency graph
No second-level aggregation. GammaNest is the one operator of
the syntax that builds a nested token, and what this excludes is the
two syntactic token fences it is the counterexample to
(AggQueryIn.evaluate_noNested, AggQueryIn.evaluate_ordinaryTokens).
Everything else covers it, at every storey: the evaluators and the kind
conformance ask nothing, the data-part adequacy, the guardedness and the
rewritten world's plain reading are proved, and so are the random world,
the PQE results and the hom commutation.
What the hom reads of a nested value. A nested world's weight is not
a function of the four readings its occurrences' inner values carry:
NestedValue.World.ann is presentProd ⊗ (𝟙 ⊖ absentSum) with the monus
taken once, over the value's own occurrences, each expression family
and each inner node together, while a reading bundles a monus per world.
So GenValue.Equiv relates a nested column by its collapse, convention
and aggregate only, and the hom carries the rest structurally: two nested
values built from related listings are related occurrence by occurrence
(NestInner.Rel), and their worlds then correspond one by one, with the
kept product and the absent sum pushed through the hom
(NestedValue.WCorr, wcorr_of_rel).
Equations
- (AggQueryIn.Rel x✝ s).noGammaNest = True
- (AggQueryIn.Hole x✝¹ s x✝).noGammaNest = True
- (AggQueryIn.Param pv x✝).noGammaNest = True
- AggQueryIn.Empty.noGammaNest = True
- (AggQueryIn.Proj ps q).noGammaNest = q.noGammaNest
- (AggQueryIn.Sel φ q hφ).noGammaNest = q.noGammaNest
- (q₁.Prod q₂).noGammaNest = (q₁.noGammaNest ∧ q₂.noGammaNest)
- (q₁.Apply q₂).noGammaNest = (q₁.noGammaNest ∧ q₂.noGammaNest)
- (q₁.Sum q₂).noGammaNest = (q₁.noGammaNest ∧ q₂.noGammaNest)
- q.Dedup.noGammaNest = q.noGammaNest
- (q₁.Diff a).noGammaNest = (q₁.noGammaNest ∧ a.noGammaNest)
- (AggQueryIn.Explode k h q).noGammaNest = q.noGammaNest
- (AggQueryIn.Mu s q₀ q₁).noGammaNest = (q₀.noGammaNest ∧ q₁.noGammaNest)
- (AggQueryIn.MuSet s q₀ q₁).noGammaNest = (q₀.noGammaNest ∧ q₁.noGammaNest)
- (AggQueryIn.Gamma is ts fs q keep ord).noGammaNest = q.noGammaNest
- (AggQueryIn.GammaScalar ts fs q ord).noGammaNest = q.noGammaNest
- (AggQueryIn.GammaNest is his p f q).noGammaNest = False
- (AggQueryIn.ProvSum is his t q).noGammaNest = q.noGammaNest
- (AggQueryIn.Retag h q).noGammaNest = q.noGammaNest
- (AggQueryIn.GammaTok is his ts fs a q keep).noGammaNest = q.noGammaNest
- (AggQueryIn.Win P O o w t f q hrr dist keep).noGammaNest = q.noGammaNest
- (AggQueryIn.WinExpr P O o ws ts fs g q_1 keeps).noGammaNest = q_1.noGammaNest
Instances For
Dependency graph
Every recursion of the query settles. A recursion means the value
its rounds settle at and means nothing elsewhere, so a result that
evaluates one asks this: at a MuSet, that the iteration repeats a round
(MuSetSettles); at a Mu, that some round is empty (MuSettles) and
that an empty round stays empty, which is what SQL's requirement that the
recursive reference occur in the body buys.
It is asked at every database, because a nested recursion is evaluated at the databases its enclosing rounds produce. A query with no recursion satisfies it with no content, every clause but the two recursions asking only what its subqueries ask.
Equations
- One or more equations did not get rendered due to their size.
- (AggQueryIn.Rel x✝ s).recSettles = True
- (AggQueryIn.Hole x✝¹ s x✝).recSettles = True
- (AggQueryIn.Param pv x✝).recSettles = True
- AggQueryIn.Empty.recSettles = True
- (AggQueryIn.Proj ps q).recSettles = q.recSettles
- (AggQueryIn.Sel φ q hφ).recSettles = q.recSettles
- (q₁.Prod q₂).recSettles = (q₁.recSettles ∧ q₂.recSettles)
- (q₁.Apply q₂).recSettles = (q₁.recSettles ∧ q₂.recSettles)
- (q₁.Sum q₂).recSettles = (q₁.recSettles ∧ q₂.recSettles)
- q.Dedup.recSettles = q.recSettles
- (q₁.Diff a).recSettles = (q₁.recSettles ∧ a.recSettles)
- (AggQueryIn.Explode k h q).recSettles = q.recSettles
- (AggQueryIn.Gamma is ts fs q keep ord).recSettles = q.recSettles
- (AggQueryIn.GammaScalar ts fs q ord).recSettles = q.recSettles
- (AggQueryIn.GammaNest is his p f q).recSettles = q.recSettles
- (AggQueryIn.ProvSum is his t q).recSettles = q.recSettles
- (AggQueryIn.Retag h q).recSettles = q.recSettles
- (AggQueryIn.GammaTok is his ts fs a q keep).recSettles = q.recSettles
- (AggQueryIn.Win P O o w t f q hrr dist keep).recSettles = q.recSettles
- (AggQueryIn.WinExpr P O o ws ts fs g q_1 keeps).recSettles = q_1.recSettles
Instances For
Dependency graph
Every aggregating operator records the parameters it reads: its
read set rd holds every outer column its subtree reads – the operator's
readsOuter, which counts rd itself, is rd. Then the identity of
occurrences is that an operator evaluated on the same inputs produces
the same occurrences, and this is a condition on the queries a result is
about. A recorded set may hold more than the subtree reads: the passes
keep each operator's recorded set while rewriting below it, so their
outputs record what their sources read.
Equations
- (AggQueryIn.Rel x✝ s).readsRecorded = True
- (AggQueryIn.Hole x✝¹ s x✝).readsRecorded = True
- (AggQueryIn.Param pv x✝).readsRecorded = True
- AggQueryIn.Empty.readsRecorded = True
- (AggQueryIn.Proj ps q).readsRecorded = q.readsRecorded
- (AggQueryIn.Sel φ q hφ).readsRecorded = q.readsRecorded
- (q₁.Prod q₂).readsRecorded = (q₁.readsRecorded ∧ q₂.readsRecorded)
- (q₁.Apply q₂).readsRecorded = (q₁.readsRecorded ∧ q₂.readsRecorded)
- (q₁.Sum q₂).readsRecorded = (q₁.readsRecorded ∧ q₂.readsRecorded)
- q.Dedup.readsRecorded = q.readsRecorded
- (q₁.Diff a).readsRecorded = (q₁.readsRecorded ∧ a.readsRecorded)
- (AggQueryIn.Explode k h q).readsRecorded = q.readsRecorded
- (AggQueryIn.Mu s q₀ q₁).readsRecorded = (q₀.readsRecorded ∧ q₁.readsRecorded)
- (AggQueryIn.MuSet s q₀ q₁).readsRecorded = (q₀.readsRecorded ∧ q₁.readsRecorded)
- (AggQueryIn.Gamma is ts fs q keep ord).readsRecorded = (rd = (AggQueryIn.Gamma is ts fs q keep ord).readsOuter ∧ q.readsRecorded)
- (AggQueryIn.GammaScalar ts fs q ord).readsRecorded = (rd = (AggQueryIn.GammaScalar ts fs q ord).readsOuter ∧ q.readsRecorded)
- (AggQueryIn.GammaNest is his p f q).readsRecorded = (rd = (AggQueryIn.GammaNest is his p f q).readsOuter ∧ q.readsRecorded)
- (AggQueryIn.ProvSum is his t q).readsRecorded = q.readsRecorded
- (AggQueryIn.Retag h q).readsRecorded = q.readsRecorded
- (AggQueryIn.GammaTok is his ts fs a q keep).readsRecorded = (rd = (AggQueryIn.GammaTok is his ts fs a q keep).readsOuter ∧ q.readsRecorded)
- (AggQueryIn.Win P O o w t f q hrr dist keep).readsRecorded = (rd = (AggQueryIn.Win P O o w t f q hrr dist keep).readsOuter ∧ q.readsRecorded)
- (AggQueryIn.WinExpr P O o ws ts fs g q_1 keeps).readsRecorded = (rd = (AggQueryIn.WinExpr P O o ws ts fs g q_1 keeps).readsOuter ∧ q_1.readsRecorded)
Instances For
Dependency graph
No multi-frame window. WinExpr is the one operator of the
syntax that builds an aggregate column holding an expression rather than
an ordinary token, so the results proved only for ordinary tokens
exclude it with this – as the possible-world results exclude ProvSum
with noProvSum.
A result that reads an expression column through the four readings
AggExpr provides needs no such fence; the hom commutation asks instead
that the frames be read off the tuples
(AggQueryIn.framesContainSelf).
Equations
- (AggQueryIn.Rel x✝ s).noWinExpr = True
- (AggQueryIn.Hole x✝¹ s x✝).noWinExpr = True
- (AggQueryIn.Param pv x✝).noWinExpr = True
- AggQueryIn.Empty.noWinExpr = True
- (AggQueryIn.Proj ps q).noWinExpr = q.noWinExpr
- (AggQueryIn.Sel φ q hφ).noWinExpr = q.noWinExpr
- (q₁.Prod q₂).noWinExpr = (q₁.noWinExpr ∧ q₂.noWinExpr)
- (q₁.Apply q₂).noWinExpr = (q₁.noWinExpr ∧ q₂.noWinExpr)
- (q₁.Sum q₂).noWinExpr = (q₁.noWinExpr ∧ q₂.noWinExpr)
- q.Dedup.noWinExpr = q.noWinExpr
- (q₁.Diff a).noWinExpr = (q₁.noWinExpr ∧ a.noWinExpr)
- (AggQueryIn.Explode k h q).noWinExpr = q.noWinExpr
- (AggQueryIn.Mu s q₀ q₁).noWinExpr = (q₀.noWinExpr ∧ q₁.noWinExpr)
- (AggQueryIn.MuSet s q₀ q₁).noWinExpr = (q₀.noWinExpr ∧ q₁.noWinExpr)
- (AggQueryIn.Gamma is ts fs q keep ord).noWinExpr = q.noWinExpr
- (AggQueryIn.GammaScalar ts fs q ord).noWinExpr = q.noWinExpr
- (AggQueryIn.GammaNest is his p f q).noWinExpr = q.noWinExpr
- (AggQueryIn.ProvSum is his t q).noWinExpr = q.noWinExpr
- (AggQueryIn.Retag h q).noWinExpr = q.noWinExpr
- (AggQueryIn.GammaTok is his ts fs a q keep).noWinExpr = q.noWinExpr
- (AggQueryIn.Win P O o w t f q hrr dist keep).noWinExpr = q.noWinExpr
- (AggQueryIn.WinExpr P O o ws ts fs g q_1 keeps).noWinExpr = False
Instances For
Dependency graph
Every multi-frame window frames by the tuple. A window
expression lists its shared family by occurrence index, and a change of
annotation semiring re-sorts that index inside blocks of equal rows, so
a reading of the family that told two equal rows apart would not survive
the change. ValueFrame.ContainsSelf is what stops it telling them
apart: the frame contains its current row exactly when it contains its
peers, so membership is a test on the tuples
(ValueFrame.mem_of_containsSelf).
RANGE, the whole partition and the rows strictly before all satisfy
it; EXCLUDE CURRENT ROW and EXCLUDE TIES are exactly the frames that
do not (ValueFrame.not_containsSelf_excludeCurrent), and they are the
ones a multi-frame window needs the occurrences for. Nothing is asked of
a single-frame Win, whose token is read off the relation.
Equations
- (AggQueryIn.Rel x✝ s).framesContainSelf = True
- (AggQueryIn.Hole x✝¹ s x✝).framesContainSelf = True
- (AggQueryIn.Param pv x✝).framesContainSelf = True
- AggQueryIn.Empty.framesContainSelf = True
- (AggQueryIn.Proj ps q).framesContainSelf = q.framesContainSelf
- (AggQueryIn.Sel φ q hφ).framesContainSelf = q.framesContainSelf
- (q₁.Prod q₂).framesContainSelf = (q₁.framesContainSelf ∧ q₂.framesContainSelf)
- (q₁.Apply q₂).framesContainSelf = (q₁.framesContainSelf ∧ q₂.framesContainSelf)
- (q₁.Sum q₂).framesContainSelf = (q₁.framesContainSelf ∧ q₂.framesContainSelf)
- q.Dedup.framesContainSelf = q.framesContainSelf
- (q₁.Diff a).framesContainSelf = (q₁.framesContainSelf ∧ a.framesContainSelf)
- (AggQueryIn.Explode k h q).framesContainSelf = q.framesContainSelf
- (AggQueryIn.Mu s q₀ q₁).framesContainSelf = (q₀.framesContainSelf ∧ q₁.framesContainSelf)
- (AggQueryIn.MuSet s q₀ q₁).framesContainSelf = (q₀.framesContainSelf ∧ q₁.framesContainSelf)
- (AggQueryIn.Gamma is ts fs q keep ord).framesContainSelf = q.framesContainSelf
- (AggQueryIn.GammaScalar ts fs q ord).framesContainSelf = q.framesContainSelf
- (AggQueryIn.GammaNest is his p f q).framesContainSelf = q.framesContainSelf
- (AggQueryIn.ProvSum is his t q).framesContainSelf = q.framesContainSelf
- (AggQueryIn.Retag h q).framesContainSelf = q.framesContainSelf
- (AggQueryIn.GammaTok is his ts fs a q keep).framesContainSelf = q.framesContainSelf
- (AggQueryIn.Win P O o w t f q hrr dist keep).framesContainSelf = q.framesContainSelf
- (AggQueryIn.WinExpr P O o ws ts fs g q_1 keeps).framesContainSelf = ((∀ (l : Fin q), (ws l).ContainsSelf) ∧ q_1.framesContainSelf)
Instances For
Dependency graph
Only WinExpr and GammaNest build anything but an ordinary
token. Every aggregate column of every row a query without them
produces holds an ordinary token: the grouping and the window build
their tokens with AggTok.tok, a projection copies or post-composes one
– and AggTok.postcomp keeps the kind – and everything else carries
rows through or rebuilds them from annotated tuples. A multi-frame
window builds an expression and second-level aggregation a nested value,
which is why both are excluded here.
This is what lets a result proved only for an ordinary token keep its statement about rows: it gets “every token here is ordinary” from this lemma, with the two operators excluded on the query.
Dependency graph
The form for an environment holding no nested value at all.
Dependency graph
Kind conformance of the general evaluator.