The product from the apply, annotated #
q₁ × q₂ is the apply of q₁ with q₂ read under the ambient context
only, in every semiring: both build the row (u, v) annotated
α_u ⊗ β_v (evaluate_prodApply). Since an apply's left side may carry
aggregate columns, so may the factors, and nothing re-types a token.
In a recursive term whose hole is in the right factor the apply cannot
take that factor as its right side, which must be closed, so the two
factors are swapped and the columns put back by a projection
(AggQueryIn.prodSwap). A projection cashes the pending group factors of the
groups whose tokens it does not keep, so the rows it builds differ from
the product's in how their annotation is split between the concrete part
and the pending factors – never in what the annotation finalizes to. What
is preserved is therefore agreement up to finalization (AggQueryIn.FinEq):
the same columns, tokens included, and the same finalized annotations,
which every operator respects (the selection on an aggregate value through
GenAnn.finalize_sel, its superseded factors being absorbed by the
comparison) and which is all the annotated evaluation reads.
prodFree replaces each product, and generatesAnn_dedupProdFree says
the classes other than ε and × generate the annotated algebra.
Agreement up to finalization #
Two environments agree up to finalization, at a context arity: the same context there, and rounds whose rows finalize alike.
Equations
- EvalEnv.FinRel γ E E' = (E.ctxAt c γ = E'.ctxAt c γ ∧ ∀ (s : String) (n : ℕ), Multiset.map GenRow.fin (E.holes s n) = Multiset.map GenRow.fin (E'.holes s n))
Instances For
Dependency graph
Two queries agree up to finalization: on every instance, in every context, and in two environments agreeing up to finalization, the same rows with the same columns and the same finalized annotations.
Equations
- One or more equations did not get rendered due to their size.
Instances For
Dependency graph
Every operator respects it #
Agreement up to finalization at two given environments: what each operator makes of it, operator by operator.
Dependency graph
Substitution keeps the fences and the settling #
A column carried through, in any context #
A column carried through a projection whatever its kind – carryCol
in a context of any arity.
Equations
- carryColIn κ k = match h : κ k with | ColKind.reg => ProjColIn.term (TermGIn.index k h) | ColKind.agg => ProjColIn.token k h | ColKind.prov => ProjColIn.provTerm (TermGIn.provIndex k h)
Instances For
Dependency graph
The product as an apply #
Dependency graph
The product written with an apply: q₁ ⊳ q₂ with q₂ read under
the ambient context only. When the hole of a recursive term is in q₂,
which an apply's right side cannot hold, the factors are swapped and the
columns put back by a projection; a product with a hole on each side,
which no recursive term has, is left alone.
Equations
- One or more equations did not get rendered due to their size.
Instances For
Dependency graph
The product is the apply of its left factor with its right factor read under the ambient context, exactly.
Dependency graph
The product the other way round, its columns put back: the same rows with the same finalized annotations.
Dependency graph
The pass #
Every product replaced by its apply form.
Equations
- prodFree (AggQueryIn.Rel x✝ s) = AggQueryIn.Rel x✝ s
- prodFree (AggQueryIn.Hole x✝¹ s x✝) = AggQueryIn.Hole x✝¹ s x✝
- prodFree (AggQueryIn.Param pv x✝) = AggQueryIn.Param pv x✝
- prodFree AggQueryIn.Empty = AggQueryIn.Empty
- prodFree (AggQueryIn.Proj ps q) = AggQueryIn.Proj ps (prodFree q)
- prodFree (AggQueryIn.Sel φ q hφ) = AggQueryIn.Sel φ (prodFree q) hφ
- prodFree (q₁.Prod q₂) = prodAnn (prodFree q₁) (prodFree q₂)
- prodFree (q₁.Apply q₂) = (prodFree q₁).Apply (prodFree q₂)
- prodFree (q₁.Sum q₂) = (prodFree q₁).Sum (prodFree q₂)
- prodFree q.Dedup = (prodFree q).Dedup
- prodFree (q₁.Diff q₂) = (prodFree q₁).Diff (prodFree q₂)
- prodFree (AggQueryIn.Explode k h q) = AggQueryIn.Explode k h (prodFree q)
- prodFree (AggQueryIn.Retag h q) = AggQueryIn.Retag h (prodFree q)
- prodFree (AggQueryIn.Mu s q₀ q₁) = AggQueryIn.Mu s (prodFree q₀) (prodFree q₁)
- prodFree (AggQueryIn.MuSet s q₀ q₁) = AggQueryIn.MuSet s (prodFree q₀) (prodFree q₁)
- prodFree (AggQueryIn.Gamma is ts fs q keep ord) = AggQueryIn.Gamma is ts fs (prodFree q) keep ord
- prodFree (AggQueryIn.GammaScalar ts fs q ord) = AggQueryIn.GammaScalar ts fs (prodFree q) ord
- prodFree (AggQueryIn.GammaNest is his p g q) = AggQueryIn.GammaNest is his p g (prodFree q)
- prodFree (AggQueryIn.ProvSum is his t q) = AggQueryIn.ProvSum is his t (prodFree q)
- prodFree (AggQueryIn.GammaTok is his ts fs a q keep) = AggQueryIn.GammaTok is his ts fs a (prodFree q) keep
- prodFree (AggQueryIn.Win P O o w t g q hrr dist keep) = AggQueryIn.Win P O o w t g (prodFree q) hrr dist keep
- prodFree (AggQueryIn.WinExpr P O o ws ts fs g q_1 keeps) = AggQueryIn.WinExpr P O o ws ts fs g (prodFree q_1) keeps
Instances For
Dependency graph
What the pass keeps #
The sufficient half: ε and × are dispensable #
The classes other than ε and × generate the annotated algebra,
over every schema and every commutative m-semiring: each ε is a set
recursion (dedupFree), then each product the apply of its left factor
with its right factor read under the ambient context, swapped when the
right factor holds a recursive term's hole (prodFree). The second pass
keeps every row, its columns and its finalized annotation, which is all
the annotated evaluation reads.