Regression bridges for the general evaluator #
The fused HAVING operator is recovered from the decomposed general
syntax: on its fragment – one aggregate comparison directly above the
grouping – the general evaluator σ_ψ ∘ Gamma computes exactly the fused
semantics in closed form (AggQueryIn.havingSite_evaluateAnnotated).
Row by row, the pending group factor introduced by Gamma is superseded
by the predicate provenance of the comparison (the token's predProv,
which is the fused Having.havingProv by AggValue.predProv_ofGroup),
and the data part collapses to the whole-group aggregate values.
Every theorem about the fused semantics – the possible-world collapses of
Provenance.HavingSemantics, the query-level correctness results – is
therefore stated directly against the general evaluator, with this closed
form as the working lemma; no separate fused evaluator is needed. The
kind transport AggQueryIn.castKind is transparent to evaluation
(AggQueryIn.evaluate_castKind).
A term over the group key, embedded as a term over the key columns of
a Gamma output.
Equations
- TermIn.toGenKey n₂ (TermIn.const a) = TermGIn.const a
- TermIn.toGenKey n₂ #k = TermGIn.index (Fin.castAdd n₂ k) ⋯
- TermIn.toGenKey n₂ (t₁.add t₂) = TermGIn.add (TermIn.toGenKey n₂ t₁) (TermIn.toGenKey n₂ t₂)
- TermIn.toGenKey n₂ (t₁.sub t₂) = TermGIn.sub (TermIn.toGenKey n₂ t₁) (TermIn.toGenKey n₂ t₂)
- TermIn.toGenKey n₂ (t₁.mul t₂) = TermGIn.mul (TermIn.toGenKey n₂ t₁) (TermIn.toGenKey n₂ t₂)
- TermIn.toGenKey n₂ (TermIn.caseWhen op t₁ t₂ t₃ t₄) = TermGIn.caseWhen op (TermIn.toGenKey n₂ t₁) (TermIn.toGenKey n₂ t₂) (TermIn.toGenKey n₂ t₃) (TermIn.toGenKey n₂ t₄)
- TermIn.toGenKey n₂ (t₁.coalesce t₂) = TermGIn.coalesce (TermIn.toGenKey n₂ t₁) (TermIn.toGenKey n₂ t₂)
Instances For
Dependency graph
The annotation list of a group token is the group's annotation list.
Dependency graph
The fused aggregate comparison, as a generalized selection atom on a
Gamma output: the l-th token column compared against a term over the
group key.
Equations
- GenPredIn.fusedCmp op l s = GenPredIn.aggCmp (Fin.natAdd n₁ l) ⋯ op (TermIn.toGenKey n₂ s)
Instances For
Dependency graph
The fused HAVING site as a general query: one aggregate comparison
directly above the grouping.
Equations
- AggQueryIn.havingSite is ts fs op l s qg = AggQueryIn.Sel (GenPredIn.fusedCmp op l s) (AggQueryIn.Gamma is ts fs qg) ⋯
Instances For
Dependency graph
Closed form of the fused HAVING site. On its fragment – one
aggregate comparison directly above the grouping – the general evaluator
produces one row per group key of the subquery, carrying the key followed
by the whole-group aggregate values and annotated by the predicate
provenance Having.havingProv of the group's occurrence sequence. This
is what makes the fused site a theorem rather than a semantics of its
own: the pending group factor introduced by Gamma is superseded by the
comparison's predicate provenance, and the data part collapses to the
whole-group aggregate values.
Dependency graph
A predicate over two groups keeps both groups' factors #
The general evaluator drops a pending group factor only where every
compared token carries that group's annotation list. A predicate reading
two groups therefore removes nothing: both factors stay pending, and
GenAnn.finalize cashes them into the row's annotation.
This is what keeps the ⊕ of a disjunction from ever being read on its
own. The predicate provenance of φ₁ ∨ φ₂ over two groups can be
non-𝟘 in worlds where neither group is read at all – 𝔹 with both
disjuncts on ⊤ is the instance – and it is the factors the row keeps
that make the row's annotation 𝟘 there.
Dependency graph
The disjunction of two aggregate atoms over two groups keeps both
group factors. The instance of AggQueryIn.evaluate_Sel_of_two_groups
the ∨ rule is about: the row's annotation is the disjunction's ⊕
times every group's pending factor, never the ⊕ alone.
Dependency graph
A projection that keeps every group's tokens changes nothing #
The projection clause cashes the pending factors of the groups whose token columns it drops. Where it drops none – a reordering, a renaming, anything keeping every token column a pending factor belongs to – the concrete part and the pending part come through untouched, so such a projection standing inside a chain of aggregate selections changes neither the families the chain reads nor the annotation it builds.
Dependency graph
Equality up to impossible rows #
A tuple annotated 𝟘 holds in no world, so an implementation is free
to drop it. Two annotated relations that agree after that removal say
the same thing about every world, and some equalities between query
spellings hold only in that sense.
Dropping the impossible rows: what is left of an annotated
relation when the tuples annotated 𝟘 – those in no world – are
removed. (Not AnnotatedRelation.support, which is the 𝔹-specific
data-part reading of Provenance.SupportAdequacy.)
Equations
- r.dropZero = Multiset.filter (fun (p : AnnotatedTuple T K n) => p.2 ≠ 0) r
Instances For
Dependency graph
Equality up to impossible rows.
This drops 𝟘-annotated tuples only. It is stated on annotated
relations, where that is all there is to drop: GenRow.toAnnotated
collapses every aggregate column through GenRow.plainTuple, so a
finalized relation carries no aggregate value and hence no occurrence
annotation. A coarser equivalence that also dropped the 𝟘-annotated
occurrences inside aggregate values would differ from this one on
GenRows, which still carry their tokens, and coincide with it on
everything evaluateAnnotated returns.
Instances For
Dependency graph
A regular selection may be absorbed into the aggregate predicate below it – up to impossible rows, and not up to equality of relations.
A selection whose predicate has an aggregate atom keeps every row,
annotating the failing ones 𝟘; a selection on regular columns removes
them. So the chain and the single selection on the conjunction give the
same annotation to every row the regular test keeps, and part on the
rows it rejects: gone on one side, present annotated 𝟘 on the other.
They therefore have the same support and are not the same relation,
which is the equality a normalization rewriting a chain into one
predicate can claim and the one it cannot.
Dependency graph
Guard absorption and the finalize identities #
These belong to the evaluator, not to any particular metatheorem: an
existence-entailing predicate provenance absorbs the δ-guard of the
group it compares, which is what licenses the evaluator's supersede of a
pending factor, and the finalize identities say what the three row
transformations do to the factored annotation. The homomorphism layer and
the rewriting closure both read them.
Guard absorption #
The first substantive use of the delta_absorb axiom: an
existence-entailing predicate provenance algebraically absorbs its
group's δ-guard. Every monomial of the possible-world sum contains
some occurrence annotation of the group (the worlds are non-empty), and
delta_absorb lets that occurrence swallow δ of the whole group
sum.
The comparison case.
Dependency graph
Guard absorption for entailing predicates: when a predicate
entails existence and all its compared tokens carry the annotation list
ℓ₀, its predicate provenance absorbs δ(⊕ℓ₀).
Dependency graph
An existence-entailing predicate provenance absorbs the δ-guards of
any collection of pending factors, each of which is the occurrence list of
every compared token.
Dependency graph
Selection finalize identity. On each side separately, the
annotation produced by an aggregate-atom selection finalizes to the
predicate provenance times the input's finalized annotation: kept pending
factors commute out, and each superseded factor is absorbed by the
predicate provenance, every world it is read in meeting the superseded
group. The compared-lists multiset C is abstract; what is used is that
every compared token's occurrence list belongs to it and that each of its
lists comes from a compared token.