Embedding the classical query syntax into the general evaluator #
Query.toAgg embeds a non-aggregating classical query into the
kind-indexed general syntax AggQuery, over all-regular kinds:
terms, selection predicates and every operator translate one to one.
Query.toAgg_bridge proves the embedding faithful – the general
evaluator computes the classical annotated semantics – via a row-wise
invariant GenRow.Inv (regular data, finalized annotation) that absorbs
the bookkeeping differences of the factored annotations (a pending
multiset that stays empty, bases multiplied by empty products).
On top of the embedding, Query.toAggHaving_input reads the input
relation of a general HAVING site over an embedded subquery off the
classical query's annotated semantics, which is what the query-level
HAVING correctness results consume.
This module sits below the classical HAVING correctness files
(Provenance.HavingQueryCorrectness,
Provenance.HavingJoinCompositional) so that they can state their
theorems over the embedded general query directly, with no side
hypothesis. The compositional JOIN rewriting built on top of the
embedding lives in Provenance.AggQueryEmbedding.
Terms and selections over all-regular kinds #
A classical term, as a term over all-regular columns.
Equations
- (TermIn.const a).toGenReg = TermGIn.const a
- (#k).toGenReg = TermGIn.index k ⋯
- (t₁.add t₂).toGenReg = TermGIn.add t₁.toGenReg t₂.toGenReg
- (t₁.sub t₂).toGenReg = TermGIn.sub t₁.toGenReg t₂.toGenReg
- (t₁.mul t₂).toGenReg = TermGIn.mul t₁.toGenReg t₂.toGenReg
- (TermIn.caseWhen op t₁ t₂ t₃ t₄).toGenReg = TermGIn.caseWhen op t₁.toGenReg t₂.toGenReg t₃.toGenReg t₄.toGenReg
- (t₁.coalesce t₂).toGenReg = TermGIn.coalesce t₁.toGenReg t₂.toGenReg
Instances For
Dependency graph
A comparison atom, as a generalized regular atom.
Equations
- (BoolTerm.EQ t₁ t₂).toGenPred = GenPredIn.cmp CompOp.eq (TermIn.toGenReg t₁) (TermIn.toGenReg t₂)
- (BoolTerm.NE t₁ t₂).toGenPred = GenPredIn.cmp CompOp.ne (TermIn.toGenReg t₁) (TermIn.toGenReg t₂)
- (BoolTerm.LE t₁ t₂).toGenPred = GenPredIn.cmp CompOp.le (TermIn.toGenReg t₁) (TermIn.toGenReg t₂)
- (BoolTerm.LT t₁ t₂).toGenPred = GenPredIn.cmp CompOp.lt (TermIn.toGenReg t₁) (TermIn.toGenReg t₂)
- (BoolTerm.GE t₁ t₂).toGenPred = GenPredIn.cmp CompOp.ge (TermIn.toGenReg t₁) (TermIn.toGenReg t₂)
- (BoolTerm.GT t₁ t₂).toGenPred = GenPredIn.cmp CompOp.gt (TermIn.toGenReg t₁) (TermIn.toGenReg t₂)
- (BoolTerm.SYNEQ t₁ t₂).toGenPred = GenPredIn.cmp CompOp.syneq (TermIn.toGenReg t₁) (TermIn.toGenReg t₂)
- (BoolTerm.SYNNE t₁ t₂).toGenPred = GenPredIn.cmp CompOp.synne (TermIn.toGenReg t₁) (TermIn.toGenReg t₂)
Instances For
Dependency graph
A classical selection predicate, as a generalized predicate without
aggregate atoms (Selection.True becomes the tautology 𝟘 = 𝟘).
Equations
- (Selection.BT b).toGenPred = b.toGenPred
- φ.Not.toGenPred = GenPredIn.not φ.toGenPred
- (φ₁.And φ₂).toGenPred = GenPredIn.and φ₁.toGenPred φ₂.toGenPred
- (φ₁.Or φ₂).toGenPred = GenPredIn.or φ₁.toGenPred φ₂.toGenPred
- Selection.True.toGenPred = GenPredIn.cmp CompOp.eq (TermGIn.const 0) (TermGIn.const 0)
Instances For
Dependency graph
The embedding #
Appending all-regular kind vectors.
Dependency graph
The embedding of the non-aggregating fragment: every classical operator translates to its general counterpart, over all-regular kinds.
Equations
- (Query.Rel x s).toAgg x_3 = AggQueryIn.Rel x s
- (Π ts q).toAgg hq = AggQueryIn.castKind ⋯ (AggQueryIn.Proj (fun (j : Fin x) => ProjColIn.term (TermIn.toGenReg (ts j))) (q.toAgg ⋯))
- (σ φ q).toAgg hq = AggQueryIn.Sel φ.toGenPred (q.toAgg ⋯) ⋯
- (q₁.Prod q₂).toAgg hq = hn ▸ AggQueryIn.castKind ⋯ (AggQueryIn.Prod (q₁.toAgg ⋯) (q₂.toAgg ⋯))
- (q₁ ⊎ q₂).toAgg hq = AggQueryIn.Sum (q₁.toAgg ⋯) (q₂.toAgg ⋯)
- (ε q).toAgg hq = AggQueryIn.Dedup (q.toAgg ⋯)
- (q₁ - q₂).toAgg hq = AggQueryIn.Diff (q₁.toAgg ⋯) (q₂.toAgg ⋯)
- (Query.ProvSum a a_1 a_2).toAgg hq = ⋯.elim
- (Query.Having a a_1 a_2 a_3 a_4 a_5 a_6).toAgg hq = ⋯.elim
Instances For
Dependency graph
Faithfulness #
The row invariant of the embedding: regular data over the classical
tuple, a factored annotation finalizing to the classical one, and no
pending group factors (the embedding image contains no Gamma).
Equations
Instances For
Dependency graph
Faithfulness of the embedding: the general evaluator computes the classical annotated semantics on embedded queries.
Dependency graph
The embedding at the row level: the general evaluator on an embedded query produces exactly the embedded classical rows.
Dependency graph
The fused HAVING, in context #
The fused HAVING site over an embedded subquery: its input
relation is the classical subquery's annotated evaluation, so the closed
form AggQueryIn.havingSite_evaluateAnnotated specializes to the
classical setting with no side hypothesis.