Normalizing a chain of selections #
Under the joint reading a predicate's provenance is one ⊕ over the
worlds of the union of the families it reads, so σ_{ψ₁ ∧ ψ₂} is one
sum where σ_{ψ₁} ∘ σ_{ψ₂} is a product of two. The two agree exactly
where the conjunction decomposes, and over ℕ on one family they do
not – 4 against 2 (natRangeToken_mul_ne_and). So HAVING p AND q
and a WHERE p around a HAVING q of the same grouping, which a SQL
user would call one query, would denote different things.
They are made to agree by reading a chain as one predicate:
AggQueryIn.normalize merges adjacent selections, and a query is read
as evaluate (normalize q). AggQueryIn.normalize_chainFree says the
result has no selection directly above a selection, and
AggQueryIn.normalize_id_of_chainFree that normalizing changes nothing
where there was no chain.
The equality this buys is up to impossible rows and not of relations,
for the reason AggQueryIn.evaluate_Sel_reg_absorb gives: a selection
with an aggregate atom keeps its failing rows annotated 𝟘 where a
regular one removes them, so merging a regular selection into the
predicate below it keeps rows the chain had dropped.
Merge adjacent selections: σ_φ(σ_ψ(q)) becomes σ_{φ ∧ ψ}(q),
recursively, so that a maximal chain becomes one selection on the
conjunction of its predicates, in the order they were written.
Equations
- (AggQueryIn.Rel x✝ s).normalize = AggQueryIn.Rel x✝ s
- (AggQueryIn.Hole x✝¹ s x✝).normalize = AggQueryIn.Hole x✝¹ s x✝
- (AggQueryIn.Param pv x✝).normalize = AggQueryIn.Param pv x✝
- AggQueryIn.Empty.normalize = AggQueryIn.Empty
- (AggQueryIn.Proj ps q).normalize = AggQueryIn.Proj ps q.normalize
- (AggQueryIn.Sel φ q hφ).normalize = match q.normalize with | AggQueryIn.Sel ψ q' hψ => AggQueryIn.Sel (φ.and ψ) q' ⋯ | q' => AggQueryIn.Sel φ q' hφ
- (q₁.Prod q₂).normalize = q₁.normalize.Prod q₂.normalize
- (q₁.Apply q₂).normalize = q₁.normalize.Apply q₂.normalize
- (q₁.Sum q₂).normalize = q₁.normalize.Sum q₂.normalize
- q.Dedup.normalize = q.normalize.Dedup
- (q₁.Diff q₂).normalize = q₁.normalize.Diff q₂.normalize
- (AggQueryIn.Explode k h q).normalize = AggQueryIn.Explode k h q.normalize
- (AggQueryIn.Mu s q₀ q₁).normalize = AggQueryIn.Mu s q₀.normalize q₁.normalize
- (AggQueryIn.MuSet s q₀ q₁).normalize = AggQueryIn.MuSet s q₀.normalize q₁.normalize
- (AggQueryIn.Gamma is ts fs q keep ord).normalize = AggQueryIn.Gamma is ts fs q.normalize keep ord
- (AggQueryIn.GammaScalar ts fs q ord).normalize = AggQueryIn.GammaScalar ts fs q.normalize ord
- (AggQueryIn.GammaNest is his p f q).normalize = AggQueryIn.GammaNest is his p f q.normalize
- (AggQueryIn.ProvSum is his t q).normalize = AggQueryIn.ProvSum is his t q.normalize
- (AggQueryIn.Retag h q).normalize = AggQueryIn.Retag h q.normalize
- (AggQueryIn.GammaTok is his ts fs a q keep).normalize = AggQueryIn.GammaTok is his ts fs a q.normalize keep
- (AggQueryIn.Win P O o w t f q hrr dist keep).normalize = AggQueryIn.Win P O o w t f q.normalize hrr dist keep
- (AggQueryIn.WinExpr P O o ws ts fs g q_1 keeps).normalize = AggQueryIn.WinExpr P O o ws ts fs g q_1.normalize keeps
Instances For
Dependency graph
No selection directly above a selection: the shape a normalized query has, and the shape on which a chain and its merge cannot differ because there is no chain.
Equations
- (AggQueryIn.Rel x✝ a).chainFree = True
- (AggQueryIn.Hole x✝¹ s x✝).chainFree = True
- (AggQueryIn.Param pv x✝).chainFree = True
- AggQueryIn.Empty.chainFree = True
- (AggQueryIn.Proj ps q).chainFree = q.chainFree
- (AggQueryIn.Sel φ (AggQueryIn.Sel φ_1 a hφ) hφ_1).chainFree = False
- (AggQueryIn.Sel φ q hφ).chainFree = q.chainFree
- (q₁.Prod q₂).chainFree = (q₁.chainFree ∧ q₂.chainFree)
- (q₁.Apply q₂).chainFree = (q₁.chainFree ∧ q₂.chainFree)
- (q₁.Sum q₂).chainFree = (q₁.chainFree ∧ q₂.chainFree)
- q.Dedup.chainFree = q.chainFree
- (q₁.Diff q₂).chainFree = (q₁.chainFree ∧ q₂.chainFree)
- (AggQueryIn.Explode k a q).chainFree = q.chainFree
- (AggQueryIn.Mu s q₀ q₁).chainFree = (q₀.chainFree ∧ q₁.chainFree)
- (AggQueryIn.MuSet s q₀ q₁).chainFree = (q₀.chainFree ∧ q₁.chainFree)
- (AggQueryIn.Gamma is ts fs q keep ord).chainFree = q.chainFree
- (AggQueryIn.GammaScalar ts fs q ord).chainFree = q.chainFree
- (AggQueryIn.GammaNest is his p f q).chainFree = q.chainFree
- (AggQueryIn.ProvSum is his t q).chainFree = q.chainFree
- (AggQueryIn.Retag h q).chainFree = q.chainFree
- (AggQueryIn.GammaTok is his ts fs a q keep).chainFree = q.chainFree
- (AggQueryIn.Win P O o w t f q a dist keep).chainFree = q.chainFree
- (AggQueryIn.WinExpr P O o ws ts fs g q_1 keeps).chainFree = q_1.chainFree
Instances For
Dependency graph
Normalizing leaves no chain.
Dependency graph
Normalizing changes nothing where there was no chain, so it is idempotent and imposes nothing on a query already in normal form.
Dependency graph
What the merge does to the pending factors #
The concrete parts of a chain and of its merge always agree: both
multiply the two predicates' provenances in, and K is commutative.
The pending parts are the question, since the supersede test runs once
per selection in a chain and once on the union of the compared columns
in the merge. Over one family they agree exactly, with nothing asked
of K: each test reduces to “drop that family's factor”, and dropping
it twice is dropping it once.
The annotation lists the compared tokens of a predicate carry on a row – what the evaluator's supersede test compares.
Equations
- χ.comparedLists u = Multiset.filterMap (fun (k : Fin n) => match u k with | Sum.inl val => none | Sum.inr a => some a.annList) χ.comparedCols.val
Instances For
Dependency graph
Those of the scalar compared tokens, which block the supersede.
Equations
- One or more equations did not get rendered due to their size.
Instances For
Dependency graph
A predicate reads one family on a row: every column it compares holds a grouped token, and they all carry the same annotation list.
Equations
Instances For
Dependency graph
The supersede test says “drop that family's factor” when the compared lists are all one list and none of them is scalar. Stated on bare multisets so that it unifies with whatever the evaluator's clause has built.