The bases of the recursion-free algebra in the minimal universe #
The recursion-free half of the classification, in the scope of the whole
algebra's (Provenance.RecursionBases): queries of the algebra with no
recursion, in the minimal universe đ(â
, {count}), generated by classes
with no recursion either. The rows are the whole algebra's at the same
witnesses, all recursion-free, with â added: without a recursion it has
nothing to be derived from.
Generation of the recursion-free algebra: every query with no
recursion, over the schema and in the signature with cnt as its only
aggregate, is matched by one over S, defined and equal wherever it
is.
Equations
- GeneratesOnRF T sch cnt S = â {n : â} {Îș : Fin n â ColKind} (q : AggQuery T n Îș), AggQueryIn.usesOnly plainOps q â GeneratesAt T sch cnt S q
Instances For
Dependency graph
â is in every basis of the recursion-free algebra whose classes
hold no recursion: without it every answer on the all-empty instance has
at most one row, and the union of the unit with itself has two.
Dependency graph
The difference in place of the selection #
{a, b} by a union: {a} and what of {b} is not a.
Equations
- DiffBasis.pairU a b = (DiffBasis.param1 a).Sum ((DiffBasis.param1 b).Diff (DiffBasis.param1 a))
Instances For
Dependency graph
Dependency graph
A selection by its test, decorrelated #
The classes a test uses, {a, b} built by a union.
Instances For
Dependency graph
A selection on a closed query without Ï and without the apply:
the test of the predicate, decorrelated over the distinct rows of the
query, holds the rows the predicate keeps, and two differences keep the
query's rows that are among them. The test uses no product and no apply,
so its decorrelation needs neither Ï nor Δ.
Dependency graph
The pass to â
, Î , Ï, â, Îł, win and one of Ă and the apply #
The recursion-free pass: a query with no recursion, over the
classes U, in a signature holding a counting aggregate, over a schema, is
matched by one with all-regular columns over S, in the signature, over
the schema, defined and equal wherever the source is. S holds â
, Î ,
â, Îł, win, one of Ï and â (both â and Ă where it has no Ï),
and one of Ă and the apply (the apply, and Ï, where U has the
apply).
- a product stays one where
ShasĂ, and becomes an apply otherwise; - a difference stays one where
Shasâ, and becomes theNOT INform otherwise; - a selection stays one where
ShasÏ, and is otherwise kept by its test, decorrelated over the distinct rows of its input â which needs the query closed, hence no apply inU; - a duplicate elimination becomes a grouping, and a window stays a window.
Where
ShasĂandÏ, every parameter leaf of the result is regular, which is what its decorrelation asks.
Dependency graph
The four candidate bases #
{â
, Î , Ï, apply, â, Îł, win}.
Equations
Instances For
Dependency graph
{â
, Î , Ï, Ă, â, Îł, win}.
Equations
Instances For
Dependency graph
{â
, Î , â, apply, â, Îł, win}.
Equations
Instances For
Dependency graph
{â
, Î , â, Ă, â, Îł, win}.
Equations
Instances For
Dependency graph
{â
, Î , â, apply, â, Îł, win} generates the recursion-free algebra
in the minimal universe: the match over {â
, Î , Ï, apply, â, Îł, win},
each selection then an apply of its test, {a, b} built by a union.
Dependency graph
The product in place of the apply #
The classes the decorrelation lands in, windows and groupings kept.
Equations
Instances For
Dependency graph
The classification #
Dependency graph
The generating sets of the recursion-free algebra in the minimal
universe, among the classes with no recursion, over â with the
counting aggregate: exactly the supersets of one of the four bases â â
,
Î , â, Îł, win, with Ï or â and with Ă or the apply, every
pairing. With recursion {â, Ă} is not one (not_generatesOnRec_prodDiff):
Ï or the apply is what a recursive term needs to drop a row.