The rewritten world's evaluator: tokens as ordinary column values #
ProvSQL evaluates rewritten plans over a value universe that contains,
next to the regular values and the provenance identifiers, the aggregate
tokens produced by its provsql_agg gate; the provsql_having gate then
reads a token and produces the predicate provenance of an aggregate
comparison. The formal counterpart is the evaluator AggQueryIn.evaluateRew
defined here: it runs a rewritten query (a AggQuery over the composite
value type T ⊕ K) over rows Tuple (GenValue (T ⊕ K) K) n – the
lifted-column carrier of the general evaluator, instantiated at the
composite value type – with the kind vector saying which columns hold
tokens.
- On the value-kinded operators the evaluator is the plain semantics
through the
inlembedding (Dedup,DiffandGammacollapse their statically all-regular rows to plain tuples, exactly as the general evaluator reads them throughGenRow.toAnnotated). AggQueryIn.GammaTokbuilds tokens: oneAggValue.ofGroupper(term, aggregate)pair over the group's occurrence sequence, whose annotations are the values of the explicit annotation term – in rewritten plans, the provenance column of the subquery – and writes the group-existence guardδ(⊕ occs)into itsprovoutput column.TermGIn.cmpAggis the cmp gate:TermGIn.evalRewinterprets it byAggValue.predProvOf, the primitive the rewriting's correctness is stated against, faithfully to ProvSQL's own gate-relative correctness.TermGIn.chiGateis the indicator gate aHAVINGpredicate needs for its regular atoms:TermGIn.evalRewinterprets it byHaving.chi, the characteristic valuepredsemgives such an atom. Having no kind constraint to keep it off plain columns, it is whatAggQueryIn.chiFreeexcludes below.
The rewriting rules built on this evaluator live downstream:
Provenance.AggQueryGroupRewriting (the bare grouping and the HAVING
site) and Provenance.AggQueryClosure (the compositional closure).
Terms and predicates in the rewritten world #
The annotation part of a composite value (𝟘 on data values: a
malformed provenance read carries no worlds).
Instances For
Dependency graph
Term evaluation in the rewritten world: as TermGIn.eval on the
value-reading constructors, with the cmpAgg gate interpreted by the
predicate provenance of the token against the comparison term, and the
chiGate gate by the characteristic value of its comparison.
Equations
- (TermGIn.const a).evalRew x✝¹ x✝ = a
- (TermGIn.outer k).evalRew x✝¹ x✝ = x✝ k
- (TermGIn.index k a).evalRew x✝¹ x✝ = AggValue.collapseSum (x✝¹ k)
- (TermGIn.provIndex k a).evalRew x✝¹ x✝ = AggValue.collapseSum (x✝¹ k)
- (TermGIn.cmpAgg k a op c_1).evalRew x✝¹ x✝ = match x✝¹ k with | Sum.inl val => Sum.inr 0 | Sum.inr a => Sum.inr (AggTok.predProvOf op (c_1.evalRew x✝¹ x✝) a)
- (TermGIn.chiGate op t₁ t₂).evalRew x✝¹ x✝ = Sum.inr (Having.chi op (t₁.evalRew x✝¹ x✝) (t₂.evalRew x✝¹ x✝))
- (t₁.add t₂).evalRew x✝¹ x✝ = t₁.evalRew x✝¹ x✝ + t₂.evalRew x✝¹ x✝
- (t₁.sub t₂).evalRew x✝¹ x✝ = t₁.evalRew x✝¹ x✝ - t₂.evalRew x✝¹ x✝
- (t₁.mul t₂).evalRew x✝¹ x✝ = t₁.evalRew x✝¹ x✝ * t₂.evalRew x✝¹ x✝
- (TermGIn.caseWhen op t₁ t₂ t₃ t₄).evalRew x✝¹ x✝ = if op.eval3 (t₁.evalRew x✝¹ x✝) (t₂.evalRew x✝¹ x✝) = Kleene.true then t₃.evalRew x✝¹ x✝ else t₄.evalRew x✝¹ x✝
- (t₁.coalesce t₂).evalRew x✝¹ x✝ = if ValueType.isNull (t₁.evalRew x✝¹ x✝) = true then t₂.evalRew x✝¹ x✝ else t₁.evalRew x✝¹ x✝
Instances For
Dependency graph
Projection-column evaluation in the rewritten world.
Equations
- (ProjColIn.term t).evalRew u γ = Sum.inl (t.evalRew u γ)
- (ProjColIn.token k a).evalRew u γ = u k
- (ProjColIn.aggTerm k a gf).evalRew u γ = Sum.map gf (AggTok.postcomp gf) (u k)
- (ProjColIn.aggTermOf k a t).evalRew u γ = Sum.map t.unary (AggTok.postcompTerm t) (u k)
- (ProjColIn.provTerm t).evalRew u γ = Sum.inl (t.evalRew u γ)
Instances For
Dependency graph
Three-valued evaluation of a predicate in the rewritten world (compared
tokens read through their deterministic collapse, as in
GenPredIn.eval3).
Equations
- (GenPredIn.cmp op t₁ t₂).evalRew3 x✝¹ x✝ = op.eval3 (t₁.evalRew x✝¹ x✝) (t₂.evalRew x✝¹ x✝)
- (GenPredIn.aggCmp k a op t).evalRew3 x✝¹ x✝ = op.eval3 (AggValue.collapseSum (x✝¹ k)) (t.evalRew x✝¹ x✝)
- (GenPredIn.aggRange k a op₁ t₁ op₂ t₂).evalRew3 x✝¹ x✝ = (op₁.eval3 (AggValue.collapseSum (x✝¹ k)) (t₁.evalRew x✝¹ x✝)).and (op₂.eval3 (AggValue.collapseSum (x✝¹ k)) (t₂.evalRew x✝¹ x✝))
- (φ.and ψ).evalRew3 x✝¹ x✝ = (φ.evalRew3 x✝¹ x✝).and (ψ.evalRew3 x✝¹ x✝)
- (φ.or ψ).evalRew3 x✝¹ x✝ = (φ.evalRew3 x✝¹ x✝).or (ψ.evalRew3 x✝¹ x✝)
- φ.not.evalRew3 x✝¹ x✝ = (φ.evalRew3 x✝¹ x✝).not
Instances For
Dependency graph
The rows a selection keeps in the rewritten world: those on which the predicate is true.
Equations
- φ.holdsRew u γ = (φ.evalRew3 u γ = Kleene.true)
Instances For
Dependency graph
Structural decidability of holdsRew.
Equations
- φ.decHoldsRew u γ = GenPredIn.decHoldsRew._aux_1 φ u γ
Instances For
Dependency graph
Equations
- φ.instDecidableHoldsRew γ u = φ.decHoldsRew u γ
Dependency graph
The reading a one-leaf expression of the rewritten world carries: the leaf's value, normalized through the data arm.
Every aggregate the rewriting emits is data-valued, being lifted from the
source's (SeqAggFunc.liftComposite), so the normalization is a no-op on
what actually arises. What it buys is that the column is equal to the
composite transport of the source's: AggExpr.toComposite lifts an
expression's own function the same way, and a bare projection would read
alike but not be the same data.
Equations
- AggExprFun.projComposite v = Sum.inl (Sum.elim id (fun (x : K) => 0) (v 0))
Instances For
Dependency graph
A filtered aggregate of a group, in the rewritten world: the
expression AggQueryIn.GammaTok builds for an aggregate carrying a
FILTER clause – one leaf over the whole group, the clause cutting only
what it reads – with the reading the composite transport carries.
Equations
- One or more equations did not get rendered due to their size.
Instances For
Dependency graph
The evaluator #
The rewritten world's evaluator: plain multiset semantics over
token-bearing rows. Value-kinded operators act through the inl
embedding; GammaTok builds tokens and the group guard; the gates
inside terms are interpreted by predProvOf and Having.chi.
Equations
- One or more equations did not get rendered due to their size.
- (AggQueryIn.Rel x✝² s).evaluateRew x✝¹ x✝ = match Database.find x✝² s x✝¹ with | none => 0 | some rn => Multiset.map (fun (t : Tuple (T ⊕ K) x✝²) (k : Fin x✝²) => Sum.inl (t k)) rn
- (AggQueryIn.Hole x✝³ s x✝²).evaluateRew x✝¹ x✝ = match Database.find x✝³ s x✝¹ with | none => 0 | some rn => Multiset.map (fun (t : Tuple (T ⊕ K) x✝³) (k : Fin x✝³) => Sum.inl (t k)) rn
- (AggQueryIn.Param pv x✝²).evaluateRew x✝¹ x✝ = {fun (k : Fin x✝³) => Sum.inl (Sum.elim id x✝ (pv k))}
- AggQueryIn.Empty.evaluateRew x✝¹ x✝ = 0
- (AggQueryIn.Proj ps q).evaluateRew x✝¹ x✝ = Multiset.map (fun (u : Tuple (GenValue (T ⊕ K) K) n_1) (j : Fin x✝³) => (ps j).evalRew u x✝) (q.evaluateRew x✝¹ x✝)
- (AggQueryIn.Sel φ q hφ).evaluateRew x✝¹ x✝ = Multiset.filter (fun (u : Tuple (GenValue (T ⊕ K) K) x✝⁴) => φ.holdsRew u x✝) (q.evaluateRew x✝¹ x✝)
- (AggQueryIn.Explode k a q).evaluateRew x✝¹ x✝ = q.evaluateRew x✝¹ x✝
- (q₁.Sum q₂).evaluateRew x✝¹ x✝ = q₁.evaluateRew x✝¹ x✝ + q₂.evaluateRew x✝¹ x✝
- (AggQueryIn.Retag h q).evaluateRew x✝¹ x✝ = q.evaluateRew x✝¹ x✝
Instances For
Dependency graph
Agreement with the plain semantics off the gates #
No token-building grouping: together with gate-freeness, this cuts
out the fragment on which the rewritten world's evaluator is the plain
semantics through the inl embedding.
Equations
- (AggQueryIn.Rel x✝ a).noGammaTok = True
- (AggQueryIn.Hole x✝¹ s x✝).noGammaTok = True
- (AggQueryIn.Param pv x✝).noGammaTok = True
- AggQueryIn.Empty.noGammaTok = True
- (AggQueryIn.Proj ps q).noGammaTok = q.noGammaTok
- (AggQueryIn.Sel φ q hφ).noGammaTok = q.noGammaTok
- (q₁.Prod q₂).noGammaTok = (q₁.noGammaTok ∧ q₂.noGammaTok)
- (q₁.Apply q₂).noGammaTok = (q₁.noGammaTok ∧ q₂.noGammaTok)
- (q₁.Sum q₂).noGammaTok = (q₁.noGammaTok ∧ q₂.noGammaTok)
- q.Dedup.noGammaTok = q.noGammaTok
- (q₁.Diff q₂).noGammaTok = (q₁.noGammaTok ∧ q₂.noGammaTok)
- (AggQueryIn.Explode k a q).noGammaTok = q.noGammaTok
- (AggQueryIn.Mu s q₀ q₁).noGammaTok = (q₀.noGammaTok ∧ q₁.noGammaTok)
- (AggQueryIn.MuSet s q₀ q₁).noGammaTok = (q₀.noGammaTok ∧ q₁.noGammaTok)
- (AggQueryIn.Gamma is ts fs q keep ord).noGammaTok = q.noGammaTok
- (AggQueryIn.GammaScalar ts fs q ord).noGammaTok = q.noGammaTok
- (AggQueryIn.GammaNest is his p f q).noGammaTok = q.noGammaTok
- (AggQueryIn.ProvSum is his t q).noGammaTok = q.noGammaTok
- (AggQueryIn.Retag h q).noGammaTok = q.noGammaTok
- (AggQueryIn.GammaTok is his ts fs a a_1 keep).noGammaTok = False
- (AggQueryIn.Win P O o w t f q a dist keep).noGammaTok = q.noGammaTok
- (AggQueryIn.WinExpr P O o ws ts fs g q_1 keeps).noGammaTok = q_1.noGammaTok
Instances For
Dependency graph
No indicator gate anywhere in a query's terms and predicates.
Equations
- (AggQueryIn.Rel x✝ a).chiFree = True
- (AggQueryIn.Hole x✝¹ s x✝).chiFree = True
- (AggQueryIn.Param pv x✝).chiFree = True
- AggQueryIn.Empty.chiFree = True
- (AggQueryIn.Proj ps q).chiFree = ((∀ (j : Fin x✝¹), (ps j).chiFree) ∧ q.chiFree)
- (AggQueryIn.Sel φ q hφ).chiFree = (φ.chiFree ∧ q.chiFree)
- (q₁.Prod q₂).chiFree = (q₁.chiFree ∧ q₂.chiFree)
- (q₁.Apply q₂).chiFree = (q₁.chiFree ∧ q₂.chiFree)
- (q₁.Sum q₂).chiFree = (q₁.chiFree ∧ q₂.chiFree)
- q.Dedup.chiFree = q.chiFree
- (q₁.Diff q₂).chiFree = (q₁.chiFree ∧ q₂.chiFree)
- (AggQueryIn.Explode k a q).chiFree = q.chiFree
- (AggQueryIn.Mu s q₀ q₁).chiFree = (q₀.chiFree ∧ q₁.chiFree)
- (AggQueryIn.MuSet s q₀ q₁).chiFree = (q₀.chiFree ∧ q₁.chiFree)
- (AggQueryIn.Gamma is ts fs q keep ord).chiFree = q.chiFree
- (AggQueryIn.GammaScalar ts fs q ord).chiFree = q.chiFree
- (AggQueryIn.GammaNest is his p f q).chiFree = (p.chiFree ∧ q.chiFree)
- (AggQueryIn.ProvSum is his t q).chiFree = (t.chiFree ∧ q.chiFree)
- (AggQueryIn.Retag h q).chiFree = q.chiFree
- (AggQueryIn.GammaTok is his ts fs a a_1 keep).chiFree = (a.chiFree ∧ a_1.chiFree)
- (AggQueryIn.Win P O o w t f q a dist keep).chiFree = q.chiFree
- (AggQueryIn.WinExpr P O o ws ts fs g q_1 keeps).chiFree = q_1.chiFree
Instances For
Dependency graph
Plain agreement. Off the token-building operator, the rewritten
world's evaluator is the plain semantics through the inl embedding.
Dependency graph
The fused predicate provenance under the composite embedding #
The rewritten site groups composite rows – the inl-embedded data with
the annotation appended as the provenance column – while the annotated
site groups the original annotated tuples. The fused predicate
provenance is invariant under this embedding: comparisons restrict along
inl, the lifted aggregate computes on the embedded values, and the
occurrence annotations are read off unchanged.
Lift a sequence aggregate to the composite domain (junk on the
annotation arm, faithful on inl-embedded values).
Instances For
Dependency graph
The same lift for an aggregate of a bag – a nested value's outer aggregate, which reads no sequence.
Equations
- NestedValue.liftComposite f s = Sum.inl (f (Multiset.map (Sum.elim id fun (x : K) => 0) s))
Instances For
Dependency graph
The classical rewriting stays off the token operators #
The classical rewriting emits no indicator gate: its terms are
column reads, their ⊗/⊖ combinations, and composite casts of the
source terms – the gate is introduced only by the HAVING site.
Dependency graph
The group sequence under the composite embedding #
The group sequence under the composite embedding: embedding the
relation and the key inl-wise embeds the group sequence. The embedding
is monotone for the sort's tie-break order (data columns compare on the
inl arm, the appended provenance column and the annotation both by the
alternative order), and sorted lists of the same multiset are unique.
Dependency graph
Reading a rewritten evaluation back as an annotated relation #
The rewritten world reads back as an annotated relation. Pairing the collapsed data columns of the rewritten evaluation of a classical rewriting with the annotation read off its provenance column recovers the composite embedding of the classical annotated semantics – the input the token-building groupings of the rewritten world consume.