The basis of the annotated semantics: the statement and the inherited rows #
A set of classes generates the annotated algebra over a semiring K
(GeneratesAnn) when every query of the whole algebra in the minimal
universe that reads no aggregate column as a key is matched, over the
same classes, by a query of the same kinds whose annotated evaluation
agrees with it on every K-instance wherever the query's recursions
settle there (AggQueryIn.AnnSettlesAt). The equality is of the bags of
annotated tuples the two queries emit, tokens collapsed and group
factors cashed (AggQueryIn.evaluateAnnotated); it is finer than
equality up to rows annotated ๐ (GeneratesAnnZ), so a set that
generates here generates there.
What transfers from the plain classification, for every semiring at
once: the data part of the annotated evaluation is the plain evaluation
of the query stripped of its aggregate selections and differences
(AggQueryIn.evaluateAnnotated_toPlain), and the recursions settle
annotated exactly when the stripped query's do plain
(AggQueryIn.settlesAt_stripAgg_of_annSettlesAt,
AggQueryIn.annSettlesAt_of_settlesAt). So a set generating the
annotated algebra generates, in the plain semantics, every query with
nothing to strip (generatesAtNoExplode_of_generatesAnn), which every
witness of the plain rows is: โ
, ฮ , ฮณ, ฮผ^โ, win, ฯ and one
of ร/apply are in every set generating the annotated algebra over
โ with the counting aggregate (required_mem_of_generatesAnn). The
selection row holds outright here, the alternatives being out of the
language. The trivial generating set is every class
(generatesAnn_plainRecOps); the smaller ones are the next step.
A plain instance, annotated ๐ #
Every tuple annotated ๐.
Instances For
Dependency graph
Every tuple of every relation annotated ๐.
Equations
Instances For
Dependency graph
Queries with nothing to strip #
A query whose annotated reading of a plain instance is faithful to
its plain reading: no selection on an aggregate value and no
difference, so stripAgg removes nothing and the data part of the
annotated evaluation is the plain evaluation of the query itself; and no
set recursion, whose annotated rounds may go on changing annotations
where its plain rounds have settled. Every witness of the plain rows is
one.
Equations
- (AggQueryIn.Rel xโ a).liftFaithful = True
- (AggQueryIn.Hole xโยน s xโ).liftFaithful = True
- (AggQueryIn.Param pv xโ).liftFaithful = True
- AggQueryIn.Empty.liftFaithful = True
- (AggQueryIn.Proj ps q).liftFaithful = q.liftFaithful
- (AggQueryIn.Sel ฯ q hฯ).liftFaithful = (ฯ.hasAggAtom = false โง q.liftFaithful)
- (qโ.Prod qโ).liftFaithful = (qโ.liftFaithful โง qโ.liftFaithful)
- (qโ.Apply qโ).liftFaithful = (qโ.liftFaithful โง qโ.liftFaithful)
- (qโ.Sum qโ).liftFaithful = (qโ.liftFaithful โง qโ.liftFaithful)
- q.Dedup.liftFaithful = q.liftFaithful
- (a.Diff a_1).liftFaithful = False
- (AggQueryIn.Explode k a q).liftFaithful = q.liftFaithful
- (AggQueryIn.Retag h q).liftFaithful = q.liftFaithful
- (AggQueryIn.Mu s qโ qโ).liftFaithful = (qโ.liftFaithful โง qโ.liftFaithful)
- (AggQueryIn.MuSet s a a_1).liftFaithful = False
- (AggQueryIn.Gamma is ts fs q keep ord).liftFaithful = q.liftFaithful
- (AggQueryIn.GammaScalar ts fs q ord).liftFaithful = q.liftFaithful
- (AggQueryIn.GammaNest is his p f q).liftFaithful = q.liftFaithful
- (AggQueryIn.GammaTok is his ts fs a q keep).liftFaithful = q.liftFaithful
- (AggQueryIn.ProvSum is his t q).liftFaithful = q.liftFaithful
- (AggQueryIn.Win P O o w t f q a dist keep).liftFaithful = q.liftFaithful
- (AggQueryIn.WinExpr P O o ws ts fs g q_1 keeps).liftFaithful = q_1.liftFaithful
Instances For
Dependency graph
What stripping keeps #
The settling of the recursions, annotated and plain #
The closed form: settling annotated at d is settling plain, stripped,
at its data part.
Dependency graph
The closed form.
Dependency graph
The generation of the annotated algebra #
A set of classes generates the annotated algebra over K: every
query of the whole algebra in the minimal universe, over the schema,
well-kinded and reading no aggregate column as a key, is matched by a
well-kinded query over the classes, of the same kinds, reading none either, whose
annotated evaluation settles and agrees with the query's on every
K-instance at which the query's does. The equality is of the bags of
annotated tuples (AggQueryIn.evaluateAnnotated), finer than
equality up to rows annotated ๐.
Equations
- One or more equations did not get rendered due to their size.
Instances For
Dependency graph
Every class generates, trivially: the query is its own match.
Dependency graph
Dependency graph
The transfer to the plain semantics: a set generating the annotated
algebra over K generates, plainly and without reading aggregate columns
as keys, every faithful query โ the matching query, stripped of its
aggregate selections and differences, reads a plain instance annotated
๐ as the query does, on the data part.
Dependency graph
The witnesses are faithful #
The inherited rows #
What every set generating the annotated algebra contains, over
โ with the counting aggregate and over every commutative m-semiring:
โ
, ฮ , ฮณ, ฮผ^โ, win, ฯ, and one of ร and the apply โ the
plain rows, inherited through the data part, with the selection row no
longer a disjunction.