Documentation

Provenance.Normalize

Normalizing a chain of selections #

Under the joint reading a predicate's provenance is one ⊕ over the worlds of the union of the families it reads, so σ_{ψ₁ ∧ ψ₂} is one sum where σ_{ψ₁} ∘ σ_{ψ₂} is a product of two. The two agree exactly where the conjunction decomposes, and over ℕ on one family they do not – 4 against 2 (natRangeToken_mul_ne_and). So HAVING p AND q and a WHERE p around a HAVING q of the same grouping, which a SQL user would call one query, would denote different things.

They are made to agree by reading a chain as one predicate: AggQueryIn.normalize merges adjacent selections, and a query is read as evaluate (normalize q). AggQueryIn.normalize_chainFree says the result has no selection directly above a selection, and AggQueryIn.normalize_id_of_chainFree that normalizing changes nothing where there was no chain.

The equality this buys is up to impossible rows and not of relations, for the reason AggQueryIn.evaluate_Sel_reg_absorb gives: a selection with an aggregate atom keeps its failing rows annotated 𝟘 where a regular one removes them, so merging a regular selection into the predicate below it keeps rows the chain had dropped.

def AggQueryIn.normalize {T : Type} {c n : ℕ} {κ : Fin n → ColKind} {l : List (String × ℕ)} :
AggQueryIn T c n κ l → AggQueryIn T c n κ l

Merge adjacent selections: σ_φ(σ_ψ(q)) becomes σ_{φ ∧ ψ}(q), recursively, so that a maximal chain becomes one selection on the conjunction of its predicates, in the order they were written.

Equations
Instances For
    Dependency graph
    def AggQueryIn.chainFree {T : Type} {c n : ℕ} {κ : Fin n → ColKind} {l : List (String × ℕ)} :
    AggQueryIn T c n κ l → Prop

    No selection directly above a selection: the shape a normalized query has, and the shape on which a chain and its merge cannot differ because there is no chain.

    Equations
    Instances For
      Dependency graph
      theorem AggQueryIn.normalize_chainFree {T : Type} {c n : ℕ} {κ : Fin n → ColKind} {l : List (String × ℕ)} (q : AggQueryIn T c n κ l) :

      Normalizing leaves no chain.

      Dependency graph
      theorem AggQueryIn.normalize_id_of_chainFree {T : Type} {c n : ℕ} {κ : Fin n → ColKind} {l : List (String × ℕ)} (q : AggQueryIn T c n κ l) :

      Normalizing changes nothing where there was no chain, so it is idempotent and imposes nothing on a query already in normal form.

      Dependency graph

      What the merge does to the pending factors #

      The concrete parts of a chain and of its merge always agree: both multiply the two predicates' provenances in, and K is commutative. The pending parts are the question, since the supersede test runs once per selection in a chain and once on the union of the compared columns in the merge. Over one family they agree exactly, with nothing asked of K: each test reduces to “drop that family's factor”, and dropping it twice is dropping it once.

      @[reducible, inline]
      abbrev GenPredIn.comparedLists {T K : Type} [CommSemiringWithMonus K] {c n : ℕ} {κ : Fin n → ColKind} (χ : GenPredIn T c κ) (u : Tuple (GenValue T K) n) :

      The annotation lists the compared tokens of a predicate carry on a row – what the evaluator's supersede test compares.

      Equations
      Instances For
        Dependency graph
        @[reducible, inline]
        abbrev GenPredIn.comparedScalarLists {T K : Type} [CommSemiringWithMonus K] {c n : ℕ} {κ : Fin n → ColKind} (χ : GenPredIn T c κ) (u : Tuple (GenValue T K) n) :

        Those of the scalar compared tokens, which block the supersede.

        Equations
        • One or more equations did not get rendered due to their size.
        Instances For
          Dependency graph
          def GenPredIn.ReadsOne {T K : Type} [CommSemiringWithMonus K] {c n : ℕ} {κ : Fin n → ColKind} (χ : GenPredIn T c κ) (u : Tuple (GenValue T K) n) (ℓ : List K) :

          A predicate reads one family on a row: every column it compares holds a grouped token, and they all carry the same annotation list.

          Equations
          Instances For
            Dependency graph
            theorem Having.supersede_test_iff {K : Type} {S L : Multiset (List K)} {ℓ : List K} (hsc : S = 0) (hnz : L ≠ 0) (hall : ∀ x ∈ L, x = ℓ) (l : List K) :
            ¬(S = 0 ∧ L ≠ 0 ∧ ∀ l' ∈ L, l' = l) ↔ l ≠ ℓ

            The supersede test says “drop that family's factor” when the compared lists are all one list and none of them is scalar. Stated on bare multisets so that it unifies with whatever the evaluator's clause has built.

            Dependency graph