Documentation

Provenance.SelRow

The selection row: σ is the only operator reading the order #

A well-kinded query of the minimal universe (AggQueryIn.wellKinded: a term reads a parameter as a plain value only where it is not aggregate) that uses no selection and never reads an aggregate column as a key (AggQueryIn.noExplode) is order-blind: its regular columns commute with every injective map of the values that fixes the query's constants and the zero the aggregate columns are read as, whatever the map does to the order. Nothing but a selection reads the order into a regular column, a key or a difference: the windows and the ordered aggregations read it, but into an aggregate column, which such a query never reads back.

The commutation is AggQueryIn.evaluatePlain_orderBlind, the faithfulness commutation of Provenance.Genericity with the order dropped from the map and the selection dropped from the syntax, and stated on the regular reading ColKind.readTuple of the rows. The witness is σ_{#1<#2}(S): on the one-row instance {(a, b)} with a < b it keeps the row, on {(b, a)} it keeps nothing, and the swap of a and b carries one instance to the other (ltWitness_breaks). So no selection-free query expresses it (ltWitness_not_expressible), and σ is in every basis whose produced queries read no aggregate column as a key (sel_mem_of_generatesOnRecNoExplode).

The regular reading of a row #

The commutation #

theorem AggQueryIn.evaluatePlain_orderBlind {T : Type} [ValueType T] {Θ : Set (SeqAggFunc T)} {S : Set OpKind} (hsel : OpKind.sel ∉ S) {c n : ℕ} {κ : Fin n → ColKind} {l : List (String × ℕ)} (q : AggQueryIn T c n κ l) :
usesOnly S q → inSig Θ q → q.noExplode → q.hygienic → ∀ {ρc : Fin c → ColKind} {HK : HoleKinds}, q.wellKinded ρc HK → ∀ {τ : T → T}, Function.Injective τ → τ 0 = 0 → ∀ (D D' : Database T) (γ γ' : Fin c → T), (∀ p ∈ q.leaves, (p.2, p.1) ∉ l → Database.find p.1 p.2 D' = Option.map (Relation.mapVals τ) (Database.find p.1 p.2 D)) → (∀ p ∈ l, noMention p.1 q) → (∀ p ∈ l, Option.map (fun (r : Multiset (Tuple T p.2)) => Multiset.map (ColKind.readTuple (HK p.1 p.2)) r) (Database.find p.2 p.1 D') = Option.map (fun (r : Multiset (Tuple T p.2)) => Multiset.map (fun (u : Fin p.2 → T) => τ ∘ u) (Multiset.map (ColKind.readTuple (HK p.1 p.2)) r)) (Database.find p.2 p.1 D)) → (∀ (k : Fin c), (ρc k).base ≠ ColKind.agg → γ' k = τ (γ k)) → (∀ a ∈ q.allConsts, τ a = a) → Multiset.map (ColKind.readTuple κ) (q.evaluatePlain D' γ') = Multiset.map (fun (u : Fin n → T) => τ ∘ u) (Multiset.map (ColKind.readTuple κ) (q.evaluatePlain D γ))

Order-blindness: a well-kinded query with no selection, reading no aggregate column as a key, in a signature with no function on values, commutes on its regular columns with every injective map of the values that fixes 0 and its constants – whatever the map does to the order. The aggregate columns are read as 0 on both sides (ColKind.readTuple), being the only place the order enters. The instance hypotheses are those of AggQueryIn.evaluatePlain_faithful: the leaves of D' are those of D mapped, except at the holes, whose rounds may carry aggregate columns and are asked to agree on their regular reading only; and the two contexts agree, up to the map, at the parameters that are not aggregate, which are the only ones a term reads as a plain value (AggQueryIn.wellKinded). An aggregate parameter is read by the leaf AggQueryIn.Param alone, into an aggregate column.

Dependency graph

The witness #

def dPair (a b : ℕ) :

The one-row instance S = {(a, b)}.

Equations
Instances For
    Dependency graph

    σ_{#1<#2}(S), the witness: the one selection whose atom reads the order.

    Equations
    Instances For
      Dependency graph
      theorem ltWitness_breaks {a b : ℕ} (hab : a < b) :

      The witness breaks order-blindness: the swap of a < b carries {(a, b)} to {(b, a)}, where it keeps nothing.

      Dependency graph

      No selection-free query expresses the witness. A query over ℕ with no selection, reading no aggregate column as a key or as an apply's parameter, in a signature with no function on values, is not plain-equivalent to σ_{#1<#2}(S): on two fresh values a < b it answers alike, up to the swap, on {(a, b)} and on {(b, a)}, and the witness does not.

      Dependency graph

      The row #

      def GeneratesAtNoExplode (T : Type) [ValueType T] (sch : Schema) (cnt : SeqAggFunc T) (S : Set OpKind) {n : ℕ} {κ : Fin n → ColKind} (q : AggQuery T n κ) :

      Generation with no aggregate column read as a key: the whole-algebra generation predicate (GeneratesOnRec) with the produced query also asked to be noExplode and well-kinded. This is the scope of the annotated generation, where the alternatives are not an operator of the source language; over it the selection is in every basis, which the plain construction putting − in place of σ (basisRecDiffOps_isBasis) escapes only by reading aggregate columns as keys. An apply's right side reading an aggregate column of its left side as a plain value would escape it the same way – a window's rank read as a parameter compares two values against a constant with a difference – and well-kindedness is what refuses that reading: an aggregate parameter is read by the leaf AggQueryIn.Param, into an aggregate column.

      Equations
      • One or more equations did not get rendered due to their size.
      Instances For
        Dependency graph
        def GeneratesOnRecNoExplode (T : Type) [ValueType T] (sch : Schema) (cnt : SeqAggFunc T) (S : Set OpKind) :

        The alternatives-free generation of every query of the algebra.

        Equations
        Instances For
          Dependency graph

          The selection row, in the scope where no aggregate column is read as a key: σ is in every generating set.

          Dependency graph

          The selection row, in the scope where no aggregate column is read as a key: σ is in every generating set.

          Dependency graph