Rewriting a bare grouping: aggregate results as output values #
The HAVING site rewriting of Provenance.AggQueryHavingRewriting covers
the case where the aggregate tokens of a grouping are consumed by a
comparison gate and never leave the site. This module covers the
complementary – and, in SQL, far more common – case: a bare
GROUP BY whose aggregate columns flow onward as ordinary output
columns.
Rule (R5) is the classical counterpart. Carrying it over the classical
syntax took a whole new value domain – data, annotation and K-tensor
monomials, quotiented – together with its own evaluator. In the general
framework no new value domain is needed: the rewritten
world's evaluator already has aggregate tokens as ordinary column
values, and AggQueryIn.GammaTok – ProvSQL's provsql_agg – already
materializes exactly the token that the general evaluator's Gamma
produces. What is needed is the correspondence at token level: the
statement of AggQueryIn.rewriting_valid folds an annotated relation
into composite rows through AnnotatedRelation.toComposite, which reads
tokens through their deterministic collapse and therefore cannot express
a token-bearing output.
GenRow.toCompositeRow supplies that embedding: data columns go through
Sum.inl, token columns are transported by AggValue.toComposite (values
embedded in the composite domain, occurrence annotations unchanged), and
the row's finalized annotation is appended as the provenance column. On
token-free rows it agrees with AnnotatedRelation.toComposite
(GenRow.toCompositeRow_of_reg), so the statement below genuinely
extends the compositional rewriting correctness rather than sitting
beside it.
AggQueryIn.gammaRew_valid is then the (R5) analogue: for a classical
subquery, the general evaluator's grouping – tokens and pending
group-existence factor included – is computed by the rewritten
token-building grouping over the classically rewritten subquery, with the
group guard δ(⊕ U) landing in the provenance column.
Tokens in the composite domain #
Transport the identity of an aggregate value to the composite value
domain: the key's and the parameters' values are embedded by Sum.inl.
The terms applied to the value are dropped: the rewritten world's columns
apply functions to the data arm (ProjColIn.aggTerm), not terms, so its
values record none, and the rewriting is an equality of rows.
Equations
- (FamId.mk l k p c terms).toComposite = FamId.mk l (List.map Sum.inl k) (FamId.paramsToComposite p) c []
Instances For
Dependency graph
The parameters of a family, transported.
Equations
Instances For
Dependency graph
Transport a symbolic aggregate token to the composite value domain:
the aggregated values are embedded by Sum.inl, the aggregate function is
lifted, and the occurrence annotations are unchanged.
Equations
Instances For
Dependency graph
Lift the function of an aggregate expression to the composite domain,
as SeqAggFunc.liftComposite lifts an aggregate: junk on the annotation
arm, faithful on inl-embedded values.
Equations
Instances For
Dependency graph
Embedding the occurrence values leaves the family's length, hence the index type of a world, where it was.
Dependency graph
Transport an aggregate expression to the composite domain: the
occurrence values are embedded by Sum.inl, the leaf aggregates and the
expression's own function are lifted, and the occurrence annotations and
the leaf readings are unchanged.
Equations
- One or more equations did not get rendered due to their size.
Instances For
Dependency graph
Hence the value in a world is the embedding of the value there.
Dependency graph
The expression a filtered aggregate of a group builds transports
too: the clause of the rewritten world is the source's read on the
embedded row, which Selection.castToAnnotatedTuple keeps, so the
occurrences, their annotations and their clause flags all agree.
Dependency graph
Transport an inner value to the composite value domain, storey by
storey: an expression as AggExpr.toComposite does, a node with its
outer aggregate lifted and its occurrences transported.
Equations
- One or more equations did not get rendered due to their size.
- NestInner.toComposite 0 e = AggExpr.toComposite e
- NestInner.toComposite j.succ (Sum.inl x_2) = Sum.inl (NestInner.toComposite j x_2)
Instances For
Dependency graph
Transport a nested value to the composite value domain: its inner values the same way, each family keeping its occurrences.
Equations
- One or more equations did not get rendered due to their size.
Instances For
Dependency graph
Transport a token to the composite value domain. A nested token transports its inner values the same way, and an expression its shared occurrences, its leaf aggregates and its own function.
Equations
Instances For
Dependency graph
Transport a lifted column value to the composite domain.
Equations
- GenValue.toComposite (Sum.inl v) = Sum.inl (Sum.inl v)
- GenValue.toComposite (Sum.inr a) = Sum.inr a.toComposite
Instances For
Dependency graph
The token-aware composite embedding of a general row: every column transported to the composite domain, with the row's finalized annotation appended as the provenance column.
Equations
- r.toCompositeRow = Fin.append (fun (k : Fin n) => (r.1 k).toComposite) fun (x : Fin 1) => Sum.inl (Sum.inr r.2.finalize)
Instances For
Dependency graph
On token-free rows the token-aware embedding is the embedding used by
the classical and HAVING-site rewriting correctness statements: the
inl-image of the composite encoding of the finalized annotated tuple.
Dependency graph
Coordinates of the token-aware embedding #
The rewritten bare grouping #
The kind vector of a rewritten Gamma output: the group keys, the
aggregate tokens, and the provenance column carrying the group guard.
Equations
- ColKind.gammaRewKinds n₁ n₂ = Fin.append (ColKind.gammaKinds n₁ n₂) fun (x : Fin 1) => ColKind.prov
Instances For
Dependency graph
The kind vector produced by the token-building grouping over a
rewritten subquery is the rewritten Gamma kind vector, whatever
rewritten schema the subquery carries: all that is asked of it is that
the key columns be regular, which they are in a rewriting of an
all-regular query.
Dependency graph
The rewritten grouping over an arbitrary rewritten subquery: the
same provsql_agg grouping as AggQueryIn.gammaRew, reading the
occurrence annotations off the subquery's provenance column, but over
any query of the rewritten world that computes the subquery's rows –
not only the classical rewriting of a classical one. This is what makes
the rule compositional: a GROUP BY whose input is itself a grouping
(its aggregate column cashed by a projection, which is what the kind
discipline asks) is rewritten by composing the two.
Equations
- One or more equations did not get rendered due to their size.
Instances For
Dependency graph
The rewritten bare grouping: ProvSQL's provsql_agg grouping over
the classically rewritten subquery, reading the occurrence annotations
off the subquery's provenance column. The output carries the group keys,
one aggregate token per (term, aggregate) pair, and the group-existence
guard δ(⊕ U) in the provenance column.
It is AggQueryIn.gammaRewOf over the classical rewriting of the
subquery; the general form takes any query of the rewritten world that
computes the subquery's rows.
Equations
- AggQueryIn.gammaRew is ts fs qg hq lab rd = AggQueryIn.gammaRewOf is ts fs ⋯ ⋯ (AggQueryIn.rewriting qg hq) (fun (x : Fin n₂) => none) lab rd
Instances For
Dependency graph
Correctness #
Correctness of the bare-grouping rewriting, compositionally – the general framework's rule (R5) over any rewritten subquery: what is asked of the subquery is only that the rewritten world's query compute its rows, as the pairs of a plain tuple and the annotation its provenance column carries. The grouping itself is the same.
Dependency graph
Correctness of the bare-grouping rewriting – the general framework's rule (R5): for a classical subquery, the general evaluator's grouping, embedded row-wise into the composite domain (tokens included, finalized annotation appended), is computed by the rewritten world's token-building grouping over the classically rewritten subquery.
Dependency graph
The gate reads a transported token unchanged #
The predicate provenance under the token transport: comparing a
transported token against an embedded value is the original comparison.
The token transport preserves lengths and annotations, lifts the
aggregate faithfully on embedded values, and comparisons restrict along
inl.
Dependency graph
Dependency graph
The same length, named by the transported expression's own family.
Dependency graph
Hence a transported world is a world exactly when it was one.
Dependency graph
Hence a comparison against an embedded constant.