The union from the bag recursion, annotated #
q₁ ⊎ q₂ is two bag recursions over one driver row (sumByMuK), as in
the plain semantics (AggQueryIn.sumByMu), now over operands of any
kinds: a round of a bag recursion carries aggregate columns, read through
the environment the evaluator binds its name in. The driver row's
aggregate columns hold a padding token (a count over the empty relation),
which the construction never reads and drops with the driver.
The rows the construction emits are the operands' rows, each with its
columns and its finalized annotation – the projections that re-tag a row
cash its pending group factors, so the agreement is up to finalization
(AggQueryIn.FinEq), which is all the annotated evaluation reads.
A query reads the environment's rounds only at its holes #
The construction, over operands of any kinds #
The kinds of a tagged row: a regular tag, then the row's own kinds.
Equations
Instances For
Dependency graph
The columns of a row with a constant tag prepended, the row's own columns carried through whatever their kinds.
Equations
- AggQueryIn.withTagColsK κ t = Fin.cons (ProjColIn.term (TermGIn.const t)) fun (i : Fin k) => carryColIn κ i
Instances For
Dependency graph
Dependency graph
A relation with the tag t prepended to every row.
Equations
- AggQueryIn.withTagK t q = AggQueryIn.castKind ⋯ (AggQueryIn.Proj (AggQueryIn.withTagColsK κ t) q)
Instances For
Dependency graph
A padding column of kind κ i over a row of aggregate columns: a
constant where the kind holds a value, the row's own token where it holds
an aggregate.
Equations
- AggQueryIn.padColK κ i = match κ i with | ColKind.reg => ProjColIn.term (TermGIn.const 0) | ColKind.agg => ProjColIn.token i ⋯ | ColKind.prov => ProjColIn.provTerm (TermGIn.const 0)
Instances For
Dependency graph
Dependency graph
The driver row: tag t, the other columns padding – a token of
the count of the empty relation where the kind is aggregate.
Equations
- One or more equations did not get rendered due to their size.
Instances For
Dependency graph
Dependency graph
Dependency graph
The columns a round's rows are projected to: the tag p₁, then the
columns of the right factor past its tag, carried through.
Equations
- AggQueryIn.roundColsK κ p₁ = Fin.cons (ProjColIn.term (TermGIn.const p₁)) fun (i : Fin k) => carryColIn (Fin.append (AggQueryIn.tagKind κ) (AggQueryIn.tagKind κ)) (Fin.natAdd (k + 1) i.succ)
Instances For
Dependency graph
Dependency graph
The selection keeping the pairs whose two tags agree.
Equations
- AggQueryIn.sameTagK κ = GenPredIn.cmp CompOp.syneq (TermGIn.index (Fin.castAdd (k + 1) 0) ⋯) (TermGIn.index (Fin.natAdd (k + 1) 0) ⋯)
Instances For
Dependency graph
A round of the construction: the rows of the recursive relation
carrying Z's tag each read Z, whose rows are re-tagged p₁.
Equations
- One or more equations did not get rendered due to their size.
Instances For
Dependency graph
The selection dropping the rows tagged p₀.
Equations
- AggQueryIn.notTagK κ p₀ = (GenPredIn.cmp CompOp.syneq (TermGIn.index 0 ⋯) (TermGIn.const p₀)).not
Instances For
Dependency graph
The columns past the tag.
Equations
Instances For
Dependency graph
Dependency graph
⊎ from two bag recursions, over operands of any kinds: s₁
binds the recursion listing q₁'s rows behind the driver, s₂ the one
adding q₂'s. The phases are 0 and ValueType.nonzero.
Equations
- One or more equations did not get rendered due to their size.
Instances For
Dependency graph
What the construction computes, up to finalization #
A row with a regular tag prepended.
Equations
- AggQueryIn.tagG t u = Fin.cons (Sum.inl t) u
Instances For
Dependency graph
An empty relation of any kinds #
An empty relation of any kinds: the driver row, dropped. Unlike
AggQueryIn.emptyOf, whose parameter leaf reads constants, its aggregate
columns hold tokens, so it is well-kinded at every kind vector.
Equations
- AggQueryIn.emptyK κ cnt = AggQueryIn.castKind ⋯ (AggQueryIn.Proj (AggQueryIn.unwithTagColsK κ) (AggQueryIn.Sel (AggQueryIn.notTagK κ 0) (AggQueryIn.driverK κ cnt 0) ⋯))
Instances For
Dependency graph
What the construction keeps #
The two recursions, given a split body #
The operators a recursive body may sit under distribute over ⊎ #
The pass: every ⊎ replaced by the construction #
As in the plain semantics (AggQueryIn.exists_sumFree_aux), a ⊎ on the
recursive path of a body cannot be replaced where it stands; the body is
instead the sum of a body with the non-recursive side of every such ⊎
dropped and a closed query, up to finalization. At a bag recursion that
settles the closed query is empty; at a set recursion it moves into the
base.
What the pass keeps of a query, besides its value: the classes
of S, the restriction on recursive terms, the signature, the absence of
an explosion, the kinds, well-formedness over a schema declaring none of
the fresh names, the names (its own, or fresh ones), and the names it does
not mention (fresh ones aside).
- usesOnly : AggQueryIn.usesOnly S q'
- hygienic : q'.hygienic
- inSig : AggQueryIn.inSig Θ q'
- over (sch : Schema) : (∀ (i : ℕ), sch.decl (f i) = none) → overSchema sch q → overSchema sch q'
Instances For
Dependency graph
A closed query matched: wherever it settles, in two environments agreeing up to finalization, the match settles and gives the same rows up to finalization.
Equations
- One or more equations did not get rendered due to their size.
Instances For
Dependency graph
A body split: wherever it settles, the body is the sum of the first query and the closed second one, up to finalization.
Equations
- One or more equations did not get rendered due to their size.
Instances For
Dependency graph
A match for every annotation semiring at once: the construction reads no annotation, so one query serves them all.
Equations
- q.ClosedMatchU q' = ∀ {K : Type} [inst : CommSemiringWithMonus K] [inst_1 : DecidableEq K] [inst_2 : HasAltLinearOrder K], q.ClosedMatch q'
Instances For
Dependency graph
A body split for every annotation semiring at once.
Equations
- q.BodySplitU q' qC = ∀ {K : Type} [inst : CommSemiringWithMonus K] [inst_1 : DecidableEq K] [inst_2 : HasAltLinearOrder K], q.BodySplit q' qC
Instances For
Dependency graph
The pass, both halves at once. For every query over the classes
of S and ⊎ (restricted recursions, the signature Θ holding the count
the construction pads with) and every injective supply of names the query
does not use: a query with no ⊎, keeping what SumFreeAnnOf lists and
matching the query wherever it settles; and, for a body reading the name
s once, a body still reading it once and a closed query the body is the
sum of. The operands of a ⊎ may carry aggregate columns.
Dependency graph
⊎ is dispensable in the annotated algebra #
ε, × and ⊎ are dispensable in the annotated algebra, over
every schema and every commutative m-semiring: each ε is a set
recursion (dedupFree), each product an apply (prodFree), and then each
⊎ the union by two bag recursions over a driver row
(AggQueryIn.sumByMuK), whose operands may carry aggregate columns, the
rounds of a bag recursion being bound in the environment. A ⊎ on the
recursive path of a body is distributed out of it first, its closed side
moving into the base of a set recursion and vanishing at a bag recursion
that settles (AggQueryIn.exists_sumFreeAnn_aux). Every row, its columns
and its finalized annotation are kept, which is all the annotated
evaluation reads.