Data-part adequacy of the general evaluator #
Forgetting the annotations of the general annotated evaluation of a query yields the plain (classical) evaluation of the stripped query on the plain database:
(q.evaluateAnnotated d).toPlain = q.stripAgg.evaluatePlain d.toPlain
This generalizes Query.evaluateAnnotated_toPlain to the kind-indexed
syntax. The stripping removes differences (annotated Diff never removes
tuple slots) and aggregate-atom selections (the annotated evaluator keeps
classically-failing rows annotated 𝟘, as ProvSQL emits them); on the
remaining operators the data parts agree tuple for tuple, the aggregate
tokens contributing through their deterministic collapse reading:
- terms, projection columns and predicates evaluated on a lifted tuple
agree with their plain readings on the collapsed tuple
(
TermGIn.eval_eq_evalPlain,ProjColIn.collapseSum_eval,GenPredIn.holds_iff_holdsPlain); - the group sequence of the fused semantics projects onto the plain group
sequence (
havingGroup_map_fst): both are sorted lists of the same multiset of tuples, sorted by the same order on the tuple part – the annotation tie-break ofhavingGroupis invisible after projection; - one output row of
Gammaper group key, whose aggregate columns collapse to the plain aggregates of the whole group.
Plain readings through collapse #
A term over regular columns evaluates on a lifted tuple as its plain reading on the collapsed tuple.
Dependency graph
A projection column collapses on a lifted tuple to its plain reading on the collapsed tuple.
Dependency graph
A predicate holds on a lifted tuple iff its plain reading holds on the collapsed tuple.
Dependency graph
Multiset helpers #
The group-sequence bridge #
The data parts of the fused group sequence form the plain group
sequence: both are lists of the same multiset of tuples, sorted by the
canonical order on tuples – havingGroup's annotation tie-break is
invisible after projection.
Dependency graph
The adequacy theorem #
Per-instance settling of the annotated recursions #
AggQueryIn.recSettles asks every recursion to settle on every instance,
which a recursion on cyclic data never does. The data-part adequacy needs
only that the recursions the evaluation at one instance runs settle
there, in the manner of the plain AggQueryIn.SettlesAt.
The annotated evaluation at (d, γ) runs only recursions that
settle: at a bag recursion the round function vanishes on the empty
round and the rounds from the base reach an empty one, at a set
recursion the iterations repeat; the subqueries settle at the instances
they are read at – a body at every round and at the empty round, an
apply's right side at every row of its left.
Equations
- One or more equations did not get rendered due to their size.
- (AggQueryIn.Rel x✝³ a).AnnSettlesAt x✝² x✝¹ x✝ = True
- (AggQueryIn.Hole x✝⁴ s x✝³).AnnSettlesAt x✝² x✝¹ x✝ = True
- (AggQueryIn.Param pv x✝³).AnnSettlesAt x✝² x✝¹ x✝ = True
- AggQueryIn.Empty.AnnSettlesAt x✝² x✝¹ x✝ = True
- (AggQueryIn.Proj ps q).AnnSettlesAt x✝² x✝¹ x✝ = q.AnnSettlesAt x✝² x✝¹ x✝
- (AggQueryIn.Sel φ q hφ).AnnSettlesAt x✝² x✝¹ x✝ = q.AnnSettlesAt x✝² x✝¹ x✝
- (q₁.Prod q₂).AnnSettlesAt x✝² x✝¹ x✝ = (q₁.AnnSettlesAt x✝² x✝¹ x✝ ∧ q₂.AnnSettlesAt x✝² x✝¹ x✝)
- (q₁.Sum q₂).AnnSettlesAt x✝² x✝¹ x✝ = (q₁.AnnSettlesAt x✝² x✝¹ x✝ ∧ q₂.AnnSettlesAt x✝² x✝¹ x✝)
- q.Dedup.AnnSettlesAt x✝² x✝¹ x✝ = q.AnnSettlesAt x✝² x✝¹ x✝
- (q₁.Diff q₂).AnnSettlesAt x✝² x✝¹ x✝ = (q₁.AnnSettlesAt x✝² x✝¹ x✝ ∧ q₂.AnnSettlesAt x✝² x✝¹ x✝)
- (AggQueryIn.Explode k a q).AnnSettlesAt x✝² x✝¹ x✝ = q.AnnSettlesAt x✝² x✝¹ x✝
- (AggQueryIn.Retag h q).AnnSettlesAt x✝² x✝¹ x✝ = q.AnnSettlesAt x✝² x✝¹ x✝
- (AggQueryIn.Gamma is ts fs q keep ord).AnnSettlesAt x✝² x✝¹ x✝ = q.AnnSettlesAt x✝² x✝¹ x✝
- (AggQueryIn.GammaScalar ts fs q ord).AnnSettlesAt x✝² x✝¹ x✝ = q.AnnSettlesAt x✝² x✝¹ x✝
- (AggQueryIn.GammaNest is his p f q).AnnSettlesAt x✝² x✝¹ x✝ = q.AnnSettlesAt x✝² x✝¹ x✝
- (AggQueryIn.GammaTok is his ts fs a q keep).AnnSettlesAt x✝² x✝¹ x✝ = q.AnnSettlesAt x✝² x✝¹ x✝
- (AggQueryIn.ProvSum is his t q).AnnSettlesAt x✝² x✝¹ x✝ = q.AnnSettlesAt x✝² x✝¹ x✝
- (AggQueryIn.Win P O o w t f q a dist keep).AnnSettlesAt x✝² x✝¹ x✝ = q.AnnSettlesAt x✝² x✝¹ x✝
- (AggQueryIn.WinExpr P O o ws ts fs g q_1 keeps).AnnSettlesAt x✝² x✝¹ x✝ = q_1.AnnSettlesAt x✝² x✝¹ x✝
Instances For
Dependency graph
The data part of the annotated evaluation is the plain evaluation of the stripped query, for a query read with nothing bound but the database: a well-kinded, hygienic query with no explosion, wherever its recursions settle.