Documentation

Provenance.AnnotatedApproxRows

The necessity rows up to ≈ #

Annotated results are compared up to ≈: rows annotated 𝟘 are dropped, and so are the occurrences annotated 𝟘 inside aggregate values. GeneratesAnnZ is GeneratesAnn with that comparison in place of equality, so a set generating up to ≈ need not reproduce the rows a query annotates 𝟘. This module proves the rows of the annotated basis against it.

annEpsOps_isBasis_in_class_approx is the basis theorem up to ≈ over the class AnnBasisClass, which holds đ”č, ℕ and ℕ[x, y]: the nine classes generate (generatesAnnZ_annEpsOps_of_class, the constructions agreeing with their source row by row up to finalization), and no proper subset does (annEpsOps_minimal_in_class_approx).

Plain settling on the realized world #

theorem AggQueryIn.settlesAt_randomWorld {T : Type} [ValueType T] {X : Type} [Fintype X] [DecidableEq X] [HasAltLinearOrder (BoolFunc X)] {c n : ℕ} {Îș : Fin n → ColKind} (q : AggQueryIn T c n Îș) (hq : q.noProvSum) (hh : q.hygienic) (hwk : q.wellKinded (ColKind.allReg c) HoleKinds.empty) (d : AnnotatedDatabase T (BoolFunc X)) (v : X → Bool) {Îł : Fin c → T} (hr : q.AnnSettlesAt d Îł { }) :

The closed form: an empty environment.

Dependency graph

The comparison up to ≈ #

noncomputable def GenRow.zeroTuple {T : Type} [ValueType T] {K : Type} [CommSemiringWithMonus K] [DecidableEq K] {n : ℕ} (u : Tuple (GenValue T K) n) :
Tuple T n

A row's tuple with the occurrences annotated 𝟘 dropped: each aggregate column read in the world of its occurrences annotated otherwise.

Equations
Instances For
    Dependency graph
    noncomputable def GenRow.zeroNorm {T : Type} [ValueType T] {K : Type} [CommSemiringWithMonus K] [DecidableEq K] {n : ℕ} (R : Multiset (GenRow T K n)) :

    An evaluation up to ≈: its rows annotated otherwise than 𝟘, with the occurrences annotated 𝟘 dropped from their aggregate values.

    Equations
    Instances For
      Dependency graph
      theorem GenRow.exists_finalize_of_zeroNorm {T : Type} [ValueType T] {K : Type} [CommSemiringWithMonus K] [DecidableEq K] {n : ℕ} {A B : Multiset (GenRow T K n)} (h : zeroNorm A = zeroNorm B) {r : GenRow T K n} (hr : r ∈ B) (hz : r.2.finalize ≠ 0) :
      ∃ r' ∈ A, r'.2.finalize = r.2.finalize

      A row annotated otherwise than 𝟘 on one side has a row of the same annotation on the other.

      Dependency graph

      A set of classes generates the annotated algebra up to ≈: every query of the whole algebra in the minimal universe is matched over the set, by a query of the same fragment, whose result agrees with the source's up to ≈ wherever the source settles. The Boolean support of an evaluation is the plain evaluation of the realized world (AggQueryIn.genRandomWorld_evaluate), which is how the rows inherited from the plain basis transfer.

      Equations
      • One or more equations did not get rendered due to their size.
      Instances For
        Dependency graph

        The inherited rows, through the Boolean support #

        @[reducible, inline]
        abbrev BoolNone :

        đ”č, as Boolean functions of no variable: ÎŽ is the identity, and an annotation is 𝟘 exactly where it is false.

        Equations
        Instances For
          Dependency graph
          Dependency graph
          theorem generatesAtNoExplode_of_generatesAnnZ {T : Type} [ValueType T] {sch : Schema} {cnt : SeqAggFunc T} {S : Set OpKind} (h : GeneratesAnnZ T BoolNone sch cnt S) {n : ℕ} {Îș : Fin n → ColKind} (q : AggQuery T n Îș) (hf : AggQueryIn.liftFaithful q) (ha : AggQueryIn.noExplode q) (hwk : AggQueryIn.wellKinded q (ColKind.allReg 0) HoleKinds.empty) :
          GeneratesAtNoExplode T sch cnt S q

          The transfer to the plain semantics, up to ≈: a set generating the annotated algebra over đ”č up to ≈ generates, plainly and without reading aggregate columns as keys, every faithful query. Over đ”č the rows ≈ keeps are the realized world of an evaluation, which is the plain evaluation of the realized world (AggQueryIn.genRandomWorld_evaluate), and an instance annotated 𝟙 realizes itself.

          Dependency graph

          The rows up to ≈ #

          The basis up to ≈ #

          theorem annEpsOps_minimal_in_class_approx {S : Set OpKind} (hS : S ⊆ annEpsOps) (h : ∀ (K : Type) [inst : CommSemiringWithMonus K] [inst_1 : DecidableEq K] [inst_2 : HasAltLinearOrder K], AnnBasisClass K → ∀ (sch : Schema), GeneratesAnnZ ℕ K sch SeqAggFunc.count S) :

          No proper subset of the nine classes generates the annotated algebra up to ≈ over every semiring of the class, with the counting aggregate: đ”č carries the rows inherited from the plain basis, ℕ the Δ row and ℕ[x, y] the difference's.

          Dependency graph

          The positive half up to ≈ #

          The nine classes generate the annotated algebra up to ≈ over every semiring of the class: the constructions agree with their source row by row up to finalization (exists_annEpsOps_match), which is what ≈ reads.

          Dependency graph
          theorem annEpsOps_isBasis_in_class_approx :
          (∀ (K : Type) [inst : CommSemiringWithMonus K] [inst_1 : DecidableEq K] [inst_2 : HasAltLinearOrder K], AnnBasisClass K → ∀ (sch : Schema), GeneratesAnnZ ℕ K sch SeqAggFunc.count annEpsOps) ∧ ∀ S ⊆ annEpsOps, (∀ (K : Type) [inst : CommSemiringWithMonus K] [inst_1 : DecidableEq K] [inst_2 : HasAltLinearOrder K], AnnBasisClass K → ∀ (sch : Schema), GeneratesAnnZ ℕ K sch SeqAggFunc.count S) → S = annEpsOps

          The annotated basis theorem up to ≈, over the class: the nine classes generate the annotated algebra up to ≈ over every semiring of AnnBasisClass, and no proper subset of them does over all of those semirings.

          Dependency graph