Documentation

Provenance.AggQueryAdequacy

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:

Plain readings through collapse #

theorem TermGIn.eval_eq_evalPlain {T : Type} [ValueType T] {K : Type} {c n : ℕ} {κ : Fin n → ColKind} (t : TermGIn T c κ) (u : Tuple (GenValue T K) n) {γ : Fin c → T} :

A term over regular columns evaluates on a lifted tuple as its plain reading on the collapsed tuple.

Dependency graph
theorem ProjColIn.collapseSum_eval {T : Type} [ValueType T] {K : Type} {c n : ℕ} {κ : Fin n → ColKind} (p : ProjColIn T c κ) (u : Tuple (GenValue T K) n) {γ : Fin c → T} :

A projection column collapses on a lifted tuple to its plain reading on the collapsed tuple.

Dependency graph
theorem GenPredIn.holds_iff_holdsPlain {T : Type} [ValueType T] {K : Type} {c n : ℕ} {κ : Fin n → ColKind} (φ : GenPredIn T c κ) (u : Tuple (GenValue T K) n) {γ : Fin c → T} :

A predicate holds on a lifted tuple iff its plain reading holds on the collapsed tuple.

Dependency graph

Multiset helpers #

The group-sequence bridge #

theorem havingGroup_map_fst {T : Type} [ValueType T] {K : Type} [CommSemiringWithMonus K] [HasAltLinearOrder K] {m n₁ : ℕ} (is : Tuple (Fin m) n₁) (r : AnnotatedRelation T K m) (g : Tuple T n₁) :

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.

def AggQueryIn.AnnSettlesAt {T : Type} [ValueType T] {K : Type} [CommSemiringWithMonus K] [DecidableEq K] [HasAltLinearOrder K] {c n : ℕ} {κ : Fin n → ColKind} {l : List (String × ℕ)} :
AggQueryIn T c n κ l → AnnotatedDatabase T K → (Fin c → T) → EvalEnv T K → Prop

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
Instances For
    Dependency graph
    theorem AggQueryIn.evaluateAnnotated_toPlain {T : Type} [ValueType T] {K : Type} [CommSemiringWithMonus K] [DecidableEq K] [HasAltLinearOrder K] {c n : ℕ} {κ : Fin n → ColKind} (q : AggQueryIn T c n κ) (hq : q.noExplode) (hh : q.hygienic) (hwk : q.wellKinded (ColKind.allReg c) HoleKinds.empty) (d : AnnotatedDatabase T K) {γ : Fin c → T} (hr : q.AnnSettlesAt d γ { }) :

    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.

    Dependency graph