The compositional closure of the rewriting rules #
ProvSQL rewrites whole queries in which classical blocks, GROUP BY … HAVING blocks and bare GROUP BY blocks occur as subqueries. The
relation AggQueryIn.RewritesTo below closes the three base rewritings –
the classical rules (AggQueryIn.rewritingOf), the HAVING site
(AggQueryIn.havingPredRew, the aggregate-exposing shape ProvSQL actually
emits, for an arbitrary Boolean combination of aggregate comparisons) and
the bare grouping (AggQueryIn.gammaRew) – under the operators that may sit
above them, and
AggQueryIn.rewritesTo_valid extends the correctness to every query so
obtained.
Token-bearing outputs #
The base rules do not share an output shape: a classical or HAVING
block produces all-regular data columns, whereas a bare grouping produces
aggregate-token columns. The relation is therefore indexed by the
rewritten query's own kind vector, and correctness is stated at the token
level, through GenRow.toCompositeRow. On all-regular outputs this
specializes to the all-regular statement, AggQueryIn.rewritesTo_valid_reg.
The natural rewritten kind vector of a query of kinds κ is
ColKind.rewKindsOf κ – the source kinds followed by the provenance
column. Casting terms, predicates and projection columns into it is
uniform: a column keeps its kind, so no all-regular hypothesis is
needed anywhere (TermGIn.castRew and friends), unlike the composite casts
of the classical rewriting. The gate TermGIn.cmpAgg, whose generic
semantics is the junk value 𝟘, casts to that constant.
Scope #
Selection, projection and union close over arbitrary kinds – in
particular over a bare grouping, which is the SELECT … FROM (GROUP BY …)
shape. Deduplication closes over any subquery whose output is
all-regular, which is what the kind discipline permits: the rewritten
rule AggQueryIn.dedupRew is ProvSQL's ε (group by the data columns,
⊕-sum the provenance column), proven correct against an arbitrary
rewritten subquery rather than only against rewriting's output.
Product closes over arbitrary kinds too. Reassembling a join needs a
projection column whose kind is read off the operand's kind vector –
ProjColIn.copy, which dispatches on that kind – and its faithfulness
needs the operands' rows to conform; that comes for free from the
subderivations, since their rows are embeddings of rows of the general
evaluator, which conforms by AggQueryIn.evaluate_conform.
Difference closes as well (AggQueryIn.diffRew).
The grouping itself closes over an arbitrary rewritten subquery
(AggQueryIn.RewritesTo.gammaOf, off AggQueryIn.gammaRewOf_valid): what
the rule asks of its input is only that some query of the rewritten world
compute its rows, not that it be classical. A clause rides into it unchanged
(Selection.castToAnnotatedTuple reads the data columns, which the
embedding keeps), so a filtered grouping is covered as well
(AggQueryIn.rewritesTo_gamma_filter). This is what covers a
GROUP BY whose input is itself a grouping – the kind discipline asking
the inner aggregate column to be read out first, as SQL does with a
SELECT key, count(*) AS c subquery – which
AggQueryIn.rewritesTo_gamma_gamma exhibits and the classical gamma
rule cannot reach. The selection with an aggregate atom closes over an
arbitrary rewritten subquery too (AggQueryIn.RewritesTo.selAgg, off
AggQueryIn.selAggRew_valid), so a HAVING need not sit on the grouping
it reads: AggQueryIn.rewritesTo_having_over_gamma puts one over a
grouping of a grouping. Both selection rules are stated where ProvSQL's
gate algebra is the joint reading the evaluator computes
(GenPredIn.gateExact). Its provenance column is the gate term times the
row's own provenance column, with no entailment test – where the
predicate entails the group's existence the evaluator drops the pending
factor and the gate term absorbs the guard left in the column instead
(GenPredIn.predsem_absorb_prod, exactly for the factors whose family
the predicate compares, which is what the evaluator's supersede filter
selects). The entailment test of the fused site
(GenPredIn.siteProvTerm) is therefore an optimization – ProvSQL's
having_entails_group_existence – and not what makes the rewriting
correct; the fused rule stays because it is the shape ProvSQL emits.
So the closure is complete for the operators the kind discipline admits
above a grouping, and for a grouping and a HAVING above anything the
closure reaches. What is outside it is a difference above a grouping,
which the kinds already forbid, and the operators this layer gives no
rewriting rule: the windows, the apply, the two recursions and the
alternatives. For the apply, the recursions and the alternatives there is
a reason in the shape of the rewritten plan, recorded with
AggQueryIn.classical. For the windows there is none: ProvSQL does
rewrite them, and what is absent here is a specification of that
rewriting, which this library does not give. So the
window rules are out of scope rather than impossible.
The rewritten kind vector #
The rewritten kind vector of a query of kinds κ: the source kinds,
followed by the provenance column.
Equations
- ColKind.rewKindsOf κ = Fin.append κ fun (x : Fin 1) => ColKind.prov
Instances For
Dependency graph
Dependency graph
Dependency graph
On all-regular kinds the uniform rewritten kind vector agrees
pointwise with the classical rewriting's ColKind.rewKinds.
Dependency graph
Uniform casts into the rewritten world #
A term over the source kinds, read on the rewritten schema: every
column keeps its kind and its position, so no all-regular hypothesis is
needed. The gate, whose generic semantics is the junk value 𝟘, casts to
that constant.
Equations
- (TermGIn.const a).castRew = TermGIn.const (Sum.inl a)
- (TermGIn.index k h).castRew = TermGIn.index (Fin.castAdd 1 k) ⋯
- (TermGIn.provIndex k h).castRew = TermGIn.provIndex (Fin.castAdd 1 k) ⋯
- (TermGIn.cmpAgg k a a_1 a_2).castRew = TermGIn.const (Sum.inl 0)
- (TermGIn.chiGate a a_1 a_2).castRew = TermGIn.const (Sum.inl 0)
- (t₁.add t₂).castRew = TermGIn.add t₁.castRew t₂.castRew
- (t₁.sub t₂).castRew = TermGIn.sub t₁.castRew t₂.castRew
- (t₁.mul t₂).castRew = TermGIn.mul t₁.castRew t₂.castRew
- (TermGIn.caseWhen op t₁ t₂ t₃ t₄).castRew = TermGIn.caseWhen op t₁.castRew t₂.castRew t₃.castRew t₄.castRew
- (t₁.coalesce t₂).castRew = TermGIn.coalesce t₁.castRew t₂.castRew
Instances For
Dependency graph
An aggregate-atom-free predicate is unnecessary here: the cast is total, aggregate atoms comparing a token's deterministic reading.
Equations
- (GenPredIn.cmp op t₁ t₂).castRew = GenPredIn.cmp op t₁.castRew t₂.castRew
- (GenPredIn.aggCmp k h op t).castRew = GenPredIn.aggCmp (Fin.castAdd 1 k) ⋯ op t.castRew
- (GenPredIn.aggRange k h op₁ t₁ op₂ t₂).castRew = GenPredIn.aggRange (Fin.castAdd 1 k) ⋯ op₁ t₁.castRew op₂ t₂.castRew
- (φ.and ψ).castRew = GenPredIn.and φ.castRew ψ.castRew
- (φ.or ψ).castRew = GenPredIn.or φ.castRew ψ.castRew
- φ.not.castRew = GenPredIn.not φ.castRew
Instances For
Dependency graph
A projection column, read on the rewritten schema.
Equations
- (ProjColIn.term t).castRew = ProjColIn.term t.castRew
- (ProjColIn.token k h).castRew = ProjColIn.token (Fin.castAdd 1 k) ⋯
- (ProjColIn.aggTerm k h gf).castRew = ProjColIn.aggTerm (Fin.castAdd 1 k) ⋯ (Sum.map gf id)
- (ProjColIn.aggTermOf k h t).castRew = ProjColIn.aggTerm (Fin.castAdd 1 k) ⋯ (Sum.map t.unary id)
- (ProjColIn.provTerm t).castRew = ProjColIn.provTerm t.castRew
Instances For
Dependency graph
Dependency graph
The casts evaluate faithfully #
A data column of a rewritten kind vector, positionally.
Dependency graph
Copying a column of unknown kind #
Copy the i-th column verbatim, whatever its kind: a regular or
provenance column is read as a value term, a token column is a verbatim
token copy. This is the projection column a join reassembly needs, since
the operand's kind vector is not statically known there.
Equations
- ProjColIn.copy i = match h : κ' i with | ColKind.reg => ProjColIn.term (TermGIn.index i h) | ColKind.agg => ProjColIn.token i h | ColKind.prov => ProjColIn.provTerm (TermGIn.provIndex i h)
Instances For
Dependency graph
Kind conformance of the token-aware embedding: a row conforming
to κ embeds to one conforming to ColKind.rewKindsOf κ.
Dependency graph
HAVING predicates as gate terms #
The HAVING site rewriting of Provenance.AggQueryHavingRewriting takes
one aggregate comparison. An arbitrary Boolean combination of atoms is
just as expressible: the predicate provenance predsem is ∧ ↦ ⊗,
∨ ↦ ⊕ and ¬ pushed to the atoms by De Morgan duality with operator
complementation, and the rewritten world's terms have mul, add and
the two gates – provsql_having for an aggregate atom, the indicator
gate for a regular one. GenPredIn.gateTerm is that translation; it is
faithful for an arbitrary predicate (GenPredIn.gateTerm_evalRew), the
gates being the primitives the correctness is relative to.
Regular atoms do change the fate of the group guard. An aggregate atom's
predicate provenance ranges over non-empty worlds only, so it supersedes
the guard; a regular atom's χ does not entail the group's existence
(GenPredIn.entailsExistence), and mixing one in can leave the whole
predicate non-entailing – count(*) > 5 ∨ city = 'Paris' fires in worlds
where the group is empty. The site rewriting therefore keeps the guard as
a factor in that case (GenPredIn.siteProvTerm), reproducing what the
general evaluator does with the pending group factor.
No range atom. A range compares one token against two terms at
once, and there is no gate for that: provsql_having carries a single
comparison. The site rewriting is therefore stated on range-free
predicates, and a range emitted as the product of two gates denotes
the product of the two atoms' provenances, which is the range's own
⊕-sum only where AggValue.predProvOf_mul_predProvOf applies.
What the emitted term denotes and what an evaluator computes from it are
two questions, and ProvSQL answers the second one outside the circuit,
as its implementation shows. Its gate is
gate_cmp, two wires and one operator, with no range form, and the
rewriter turns ∧ into provenance_times and ∨ into
provenance_plus over one gate per atom – which is exactly the algebra
of GenPredIn.gateTerm. Evaluation then recognizes a times or plus whose
children are conditions over one contributor family, rebuilds their
Boolean tree, enumerates that family's worlds once (bounded, a couple
of dozen contributors) and keeps a world iff the whole predicate holds
there; a conjunction bounding one count(*) from both sides has the
closed form S_C ⊖ S_{D+1}, which is this library's
Having.G_eq_S_monus_S, where that lemma's hypotheses hold. The plain
product is accepted as the answer only in a semiring where product is
the joint reading (exclusive with idempotent product); where joint
resolution does not apply the system falls back to the product and warns
that it is not the provenance of the combination.
So the fence is faithful to the circuit, which is what gateTerm
translates into, and the joint reading – what the evaluator computes,
GenPredIn.predsemJ – lives in the evaluation pass. The rewriting's
correctness is therefore stated where the two agree
(GenPredIn.gateExact). Lifting that means modeling the pass – a Boolean combination of cmpAgg
atoms over one token's family, read in one world, which is what
AggValue.predProvOfAnd and Provenance.JointFamily already are
semantically – and not adding a gate.
Equations
Instances For
Dependency graph
Where the gate algebra is the joint reading: one aggregate
comparison, under a conjunction of comparisons. ProvSQL's circuit reads a
predicate structurally – a conjunction as a product of gates, a
disjunction as a sum – while a selection reads the columns of one family
in one world (GenPredIn.predsemJ). The two agree on this fragment
(GenPredIn.predsemJ_eq_predsem) and not beyond it: a disjunction of two
comparisons that both hold is read 𝟙 ⊕ 𝟙 by the gates and 𝟙 in the
world.
Equations
- (GenPredIn.aggCmp k a a_1 a_2).gateExact = true
- ((GenPredIn.cmp a a_1 a_2).and ψ).gateExact = ψ.gateExact
- GenPredIn.gateExact x✝ = false
Instances For
Dependency graph
On the fragment the gate algebra is the joint reading.
Dependency graph
A predicate all of whose atoms are aggregate comparisons.
Equations
Instances For
Dependency graph
An aggregate-only predicate entails its groups' existence, whatever the polarity: every atom does, and both connectives preserve that.
Dependency graph
The predicate provenance as a rewritten term: the predsem
algebra – aggregate atoms to provsql_having gates, regular atoms to
indicator gates, ∧ ↦ ⊗, ∨ ↦ ⊕, ¬ pushed down with operator
complementation.
Equations
- One or more equations did not get rendered due to their size.
- (GenPredIn.cmp op t₁ t₂).gateTerm x✝ = TermGIn.chiGate (if x✝ = true then op.negate else op) t₁.castRew t₂.castRew
- (GenPredIn.aggCmp k h op t).gateTerm x✝ = TermGIn.cmpAgg (Fin.castAdd 1 k) ⋯ (if x✝ = true then op.negate else op) t.castRew
- (φ.and ψ).gateTerm x✝ = if x✝ = true then TermGIn.add (φ.gateTerm x✝) (ψ.gateTerm x✝) else TermGIn.mul (φ.gateTerm x✝) (ψ.gateTerm x✝)
- (φ.or ψ).gateTerm x✝ = if x✝ = true then TermGIn.mul (φ.gateTerm x✝) (ψ.gateTerm x✝) else TermGIn.add (φ.gateTerm x✝) (ψ.gateTerm x✝)
- φ.not.gateTerm x✝ = φ.gateTerm !x✝
Instances For
Dependency graph
The gate term computes the predicate provenance, for an arbitrary predicate: relative to the two gate primitives, which is exactly the sense in which ProvSQL's own rewriting is correct.
What the row is asked is that no aggregate column hold a nested token
(GenRow.NoNested): the provsql_having gate reads the transported
column, and the transport is faithful for an ordinary token
(AggValue.predProvOf_toComposite) and for an expression – a window's,
or a filtered aggregate's – by AggExpr.predProv_toComposite. A nested
token's transport has no such lemma yet.
Dependency graph
The general HAVING site #
The provenance column of a rewritten HAVING site: the
predicate's gate term, times the group-existence guard δ(⊕ U) – which
the rewritten grouping has left in the provenance column – unless the
predicate already entails the group's existence, in which case the gate
term supersedes it. This is ProvSQL's having_entails_group_existence
test: the supersede of the δ gate is licensed exactly when every world
the predicate accepts has the group non-empty.
Equations
- GenPredIn.siteProvTerm φ = if GenPredIn.entailsExistence φ false = true then GenPredIn.gateTerm φ false else TermGIn.mul (GenPredIn.gateTerm φ false) (TermGIn.provIndex (Fin.last (n₁ + n₂)) ⋯)
Instances For
Dependency graph
The output columns of a general HAVING site: the group keys and the
aggregate tokens copied verbatim, and the predicate's provenance term in
the provenance column.
Equations
- AggQueryIn.havingPredCols φ j = if hj : ↑j < n₁ + n₂ then ProjColIn.copy (Fin.castAdd 1 ⟨↑j, hj⟩) else ProjColIn.provTerm (GenPredIn.siteProvTerm φ)
Instances For
Dependency graph
The site's output columns have exactly the rewritten Gamma kinds.
Dependency graph
The rewritten HAVING site, for an arbitrary predicate: the
token-building grouping of AggQueryIn.gammaRew, with a projection keeping
the group keys and the aggregate tokens and replacing the group-existence
guard by the predicate's provenance term – the gate term alone when the
predicate entails the group's existence, the gate term times the guard
otherwise.
Equations
- AggQueryIn.havingPredRew is ts fs φ qg hq lab rd = AggQueryIn.Retag ⋯ (AggQueryIn.Proj (AggQueryIn.havingPredCols φ) (AggQueryIn.gammaRew is ts fs qg hq lab rd))
Instances For
Dependency graph
Duplicate elimination in the rewritten world #
The rewritten duplicate elimination: ProvSQL's ε rule – group by
the data columns and ⊕-sum the provenance column – applied to an
arbitrary rewritten subquery, as AggQueryIn.rewriting does for the
classical fragment.
Equations
- AggQueryIn.dedupRew q' = AggQueryIn.Retag ⋯ (AggQueryIn.ProvSum (fun (k : Fin n) => Fin.castAdd 1 k) ⋯ (TermGIn.provIndex (Fin.last n) ⋯) q')
Instances For
Dependency graph
Correctness of the rewritten duplicate elimination, for an arbitrary rewritten subquery.
Dependency graph
Products of token-bearing blocks #
The reassembly columns of a rewritten product: the two operands' data columns copied verbatim (whatever their kinds), and the product of the two provenance columns.
Equations
- One or more equations did not get rendered due to their size.
Instances For
Dependency graph
The reassembly columns have the rewritten kinds of the product.
Dependency graph
The rewritten product, over operands of arbitrary kinds: the two rewritten blocks joined, the data columns reassembled by kind-preserving copies, and the provenance columns multiplied.
Equations
- AggQueryIn.prodRew q₁' q₂' = AggQueryIn.Retag ⋯ (AggQueryIn.Proj (AggQueryIn.prodRewCols κ₁ κ₂) (AggQueryIn.Prod q₁' q₂'))
Instances For
Dependency graph
Correctness of the rewritten product, for arbitrary operand kinds: conformance of the operands' rows makes the kind-dispatched column copies faithful.
Dependency graph
Difference in the rewritten world #
The general evaluator keeps every row of the left operand, rewriting its
annotation to α ⊖ Σβ – the monus against the ⊕-sum of the matching
rows on the right. ProvSQL's rewriting encodes that missing left outer
join as a union of two branches: rows whose data part is absent from
the right operand keep their annotation, rows whose data part is present
are joined against the per-key sums and subtract them. The rewritten
world's TermGIn.sub supplies the monus directly, so both branches are
plain projections of joins, and the two semijoin identities of
Provenance.QueryRewriting reduce them to filters of the left operand.
The data columns of a rewritten block, as an all-regular query: the provenance column dropped.
Equations
- AggQueryIn.diffKeyProj q = AggQueryIn.Retag ⋯ (AggQueryIn.Proj (fun (j : Fin n) => ProjColIn.term (TermGIn.index (Fin.castAdd 1 j) ⋯)) q)
Instances For
Dependency graph
The output columns of the unmatched branch: the left block copied verbatim, provenance column included.
Equations
- AggQueryIn.diffColsU j = if hj : ↑j < n then ProjColIn.term (TermGIn.index (Fin.castAdd n (Fin.castAdd 1 ⟨↑j, hj⟩)) ⋯) else ProjColIn.provTerm (TermGIn.provIndex (Fin.castAdd n (Fin.last n)) ⋯)
Instances For
Dependency graph
The output columns of the matched branch: the left block's data columns, and the monus of the two provenance columns.
Equations
- One or more equations did not get rendered due to their size.
Instances For
Dependency graph
Dependency graph
Dependency graph
The unmatched branch: left rows whose data part is among the surviving keys, keeping their annotation.
Equations
- One or more equations did not get rendered due to their size.
Instances For
Dependency graph
The matched branch: left rows joined against the per-key ⊕-sums,
subtracting them.
Equations
- One or more equations did not get rendered due to their size.
Instances For
Dependency graph
The rewritten difference.
Equations
- One or more equations did not get rendered due to their size.
Instances For
Dependency graph
The classical rewriting at the uniform kind vector #
The classical rewriting, retagged to ColKind.rewKindsOf κ.
AggQueryIn.rewriting targets ColKind.rewKinds n – the per-index
if k < n form – which is only pointwise equal to the uniform
Fin.append κ prov the congruences below consume. Retagging once here
(semantically the identity) lets a congruence sit directly above the
classical base rule instead of threading an explicit retag step.
Equations
- AggQueryIn.rewritingOf q hq = AggQueryIn.Retag ⋯ (AggQueryIn.rewriting q hq)
Instances For
Dependency graph
The general selection with an aggregate atom #
The provenance column of a rewritten selection whose predicate compares an aggregate column, over an arbitrary rewritten subquery: the predicate's gate term times the row's own provenance column.
No entailment test is needed here, unlike at the fused site
(GenPredIn.siteProvTerm): where the predicate entails the group's
existence the evaluator drops the pending factor, and the gate term
absorbs the δ-guard it left in the provenance column instead
(GenPredIn.predsem_absorb_prod). So multiplying by the column is right
in both cases, and the test is only the optimization ProvSQL performs.
Equations
Instances For
Dependency graph
The output columns of a rewritten selection: every data column copied verbatim, whatever its kind, and the predicate's provenance term in the provenance column.
Equations
- AggQueryIn.selAggCols φ j = if hj : ↑j < n then ProjColIn.copy (Fin.castAdd 1 ⟨↑j, hj⟩) else ProjColIn.provTerm (GenPredIn.selProvTerm φ)
Instances For
Dependency graph
They have the rewritten kinds of the source.
Dependency graph
The rewritten selection with an aggregate atom, over an arbitrary rewritten subquery: keep every data column and replace the provenance column by the predicate's provenance term.
Equations
- AggQueryIn.selAggRew φ q' = AggQueryIn.Retag ⋯ (AggQueryIn.Proj (AggQueryIn.selAggCols φ) q')
Instances For
Dependency graph
Correctness of the general selection rewriting, relative to the
gate primitives: for a predicate on which the gate algebra is the joint
reading (GenPredIn.gateExact), over any rewritten subquery that
computes the input's rows. The data columns are
copied, and in the provenance column the gate term multiplies the row's
finalized annotation, which is the evaluator's own update by
GenAnn.finalize_sel – the superseded pending factors being exactly the
ones the gate term absorbs.
Dependency graph
The grouping's hypothesis, off a rewriting of its input: a rewritten query that computes the subquery's rows computes, in particular, the pairs the token-building grouping reads.
Dependency graph
The closure #
The compositional closure of the rewriting rules: the three base
rewritings – classical blocks, fused HAVING sites and bare groupings –
composed under union, selection, projection, deduplication, product and
difference, with the kind-retagging of AggQueryIn.Retag available to
adapt a subderivation's output kinds. The HAVING-site rule
havingPred keeps the group keys and the aggregate tokens as output
columns and admits any predicate with an aggregate atom.
- classical {T : Type} [ValueType T] {K : Type} [CommSemiringWithMonus K] [HasAltLinearOrder K] {n : ℕ} {κ : Fin n → ColKind} (q : AggQuery T n κ) (hq : AggQueryIn.classical q) : RewritesTo q (rewritingOf q hq)
- gamma {T : Type} [ValueType T] {K : Type} [CommSemiringWithMonus K] [HasAltLinearOrder K] {lab m n₁ n₂ : ℕ} {rd : Fin 0 → Bool} (is : Tuple (Fin m) n₁) (ts : Tuple (Term T m) n₂) (fs : Tuple (SeqAggFunc T) n₂) (qg : AggQuery T m (ColKind.allReg m)) (hq : AggQueryIn.classical qg) : (Gamma is ts fs qg).RewritesTo (gammaRew is ts fs qg hq lab rd)
- gammaOf {T : Type} [ValueType T] {K : Type} [CommSemiringWithMonus K] [HasAltLinearOrder K] {lab m n₁ n₂ : ℕ} {rd : Fin 0 → Bool} {qg : AggQuery T m (ColKind.allReg m)} {q' : AggQuery (T ⊕ K) (m + 1) (ColKind.rewKindsOf (ColKind.allReg m))} (is : Tuple (Fin m) n₁) (ts : Tuple (Term T m) n₂) (fs : Tuple (SeqAggFunc T) n₂) (keep : Fin n₂ → Option (Selection T m)) : RewritesTo qg q' → (Gamma is ts fs qg keep).RewritesTo (gammaRewOf is ts fs ⋯ ⋯ q' keep lab rd)
- havingPred {T : Type} [ValueType T] {K : Type} [CommSemiringWithMonus K] [HasAltLinearOrder K] {lab m n₁ n₂ : ℕ} {rd : Fin 0 → Bool} (is : Tuple (Fin m) n₁) (ts : Tuple (Term T m) n₂) (fs : Tuple (SeqAggFunc T) n₂) (φ : GenPred T (ColKind.gammaKinds n₁ n₂)) (hφ : GenPredIn.hasAggAtom φ = true) (hrf : GenPredIn.gateExact φ = true) (qg : AggQuery T m (ColKind.allReg m)) (hq : AggQueryIn.classical qg) : (Sel φ (Gamma is ts fs qg) ⋯).RewritesTo (havingPredRew is ts fs φ qg hq lab rd)
- retag {T : Type} [ValueType T] {K : Type} [CommSemiringWithMonus K] [HasAltLinearOrder K] {n : ℕ} {κ : Fin n → ColKind} {κ' κ'' : Fin (n + 1) → ColKind} {q : AggQuery T n κ} {q' : AggQuery (T ⊕ K) (n + 1) κ'} (h : ∀ (k : Fin (n + 1)), (κ' k).base = (κ'' k).base) : RewritesTo q q' → RewritesTo q (Retag h q')
- sum {T : Type} [ValueType T] {K : Type} [CommSemiringWithMonus K] [HasAltLinearOrder K] {n : ℕ} {κ : Fin n → ColKind} {κ' : Fin (n + 1) → ColKind} {q₁ q₂ : AggQuery T n κ} {q₁' q₂' : AggQuery (T ⊕ K) (n + 1) κ'} : RewritesTo q₁ q₁' → RewritesTo q₂ q₂' → (Sum q₁ q₂).RewritesTo (Sum q₁' q₂')
- dedup {T : Type} [ValueType T] {K : Type} [CommSemiringWithMonus K] [HasAltLinearOrder K] {n : ℕ} {q : AggQuery T n (ColKind.allReg n)} {q' : AggQuery (T ⊕ K) (n + 1) (ColKind.rewKindsOf (ColKind.allReg n))} : RewritesTo q q' → (Dedup q).RewritesTo (dedupRew q')
- diff {T : Type} [ValueType T] {K : Type} [CommSemiringWithMonus K] [HasAltLinearOrder K] {n : ℕ} {q₁ q₂ : AggQuery T n (ColKind.allReg n)} {q₁' q₂' : AggQuery (T ⊕ K) (n + 1) (ColKind.rewKindsOf (ColKind.allReg n))} : RewritesTo q₁ q₁' → RewritesTo q₂ q₂' → (Diff q₁ q₂).RewritesTo (diffRew q₁' q₂')
- sel {T : Type} [ValueType T] {K : Type} [CommSemiringWithMonus K] [HasAltLinearOrder K] {n : ℕ} {κ : Fin n → ColKind} {q : AggQuery T n κ} {q' : AggQuery (T ⊕ K) (n + 1) (ColKind.rewKindsOf κ)} (φ : GenPred T κ) (hφ : GenPredIn.hasAggAtom φ = false) : RewritesTo q q' → (Sel φ q ⋯).RewritesTo (Sel (GenPredIn.castRew φ) q' ⋯)
- selAgg {T : Type} [ValueType T] {K : Type} [CommSemiringWithMonus K] [HasAltLinearOrder K] {n : ℕ} {κ : Fin n → ColKind} {q : AggQuery T n κ} {q' : AggQuery (T ⊕ K) (n + 1) (ColKind.rewKindsOf κ)} (φ : GenPred T κ) (hφ : GenPredIn.hasAggAtom φ = true) (hrf : GenPredIn.gateExact φ = true) (hnn : noGammaNest q) : RewritesTo q q' → (Sel φ q ⋯).RewritesTo (selAggRew φ q')
- proj {T : Type} [ValueType T] {K : Type} [CommSemiringWithMonus K] [HasAltLinearOrder K] {n m : ℕ} {κ : Fin n → ColKind} {q : AggQuery T n κ} {q' : AggQuery (T ⊕ K) (n + 1) (ColKind.rewKindsOf κ)} (ps : Tuple (ProjCol T κ) m) : RewritesTo q q' → (Proj ps q).RewritesTo (Retag ⋯ (Proj (fun (j : Fin (m + 1)) => if hj : ↑j < m then ProjColIn.castRew (ps ⟨↑j, hj⟩) else ProjColIn.provTerm (TermGIn.provIndex (Fin.last n) ⋯)) q'))
- prod {T : Type} [ValueType T] {K : Type} [CommSemiringWithMonus K] [HasAltLinearOrder K] {n₁ n₂ : ℕ} {κ₁ : Fin n₁ → ColKind} {κ₂ : Fin n₂ → ColKind} {q₁ : AggQuery T n₁ κ₁} {q₂ : AggQuery T n₂ κ₂} {q₁' : AggQuery (T ⊕ K) (n₁ + 1) (ColKind.rewKindsOf κ₁)} {q₂' : AggQuery (T ⊕ K) (n₂ + 1) (ColKind.rewKindsOf κ₂)} : RewritesTo q₁ q₁' → RewritesTo q₂ q₂' → (Prod q₁ q₂).RewritesTo (prodRew q₁' q₂')
Instances For
Dependency graph
A filtered grouping is in the closure. count(*) FILTER (WHERE p)
over a classical subquery rewrites like any other grouping: the clause
rides into the rewritten plan unchanged
(Selection.castToAnnotatedTuple), its aggregate's column becoming an
expression over the whole group on both sides
(AggExpr.ofGroupWhen_toComposite).
Dependency graph
A grouping over a grouping is in the closure. The kind
discipline asks the inner aggregate column to be read out first – here by
a projection of terms, which is what SELECT key, count(*) AS c followed
by a grouping of c does in SQL – and the two grouping rules then
compose through AggQueryIn.RewritesTo.gammaOf, which the classical
gamma rule alone cannot do: its subquery has to be classical, and a
grouping is not.
Dependency graph
A HAVING over a grouping of a grouping is in the closure. Two
rules the closure did not have before reach it: the grouping over an
arbitrary rewriting (gammaOf) and the selection with an aggregate atom
over an arbitrary rewriting (selAgg). The fused site rule cannot – its
input has to be classical – and the aggregate-free sel rule cannot
either, the predicate comparing a token.
Dependency graph
Whole-query correctness of the compositional rewriting: along the closure, the general evaluator's rows, embedded token-aware into the composite domain, are exactly the rewritten world's evaluation.
Dependency graph
On an all-regular source the correctness specializes to the shape of
the classical and HAVING-site statements: the annotated semantics,
folded into composite tuples and embedded by inl.