Documentation

Provenance.AggValueCongr

Congruence of predicate provenance under tie-block permutations #

The occurrence payload of an aggregate token is produced by Having.havingGroup, which sorts the group by the canonical order on the tuple part and breaks ties on equal tuple parts by an arbitrary fixed order on the annotations. Pushing a semiring homomorphism through the annotated database can therefore reorder the payload – but only within blocks of occurrences with equal tuple parts, hence equal aggregated-term values.

This file proves that the predicate provenance of a token is invariant under exactly such reorderings. The invariance is genuinely limited to tie blocks: for an order-sensitive aggregate, exchanging two occurrences of equal value across an occurrence of a different value changes the predicate provenance.

Tie-block permutations #

inductive TiePerm {α : Type} (eqv : α → α → Prop) :
List α → List α → Prop

Permutations generated by transposing adjacent elements related by eqv: the guarded analogue of List.Perm, whose swap constructor requires the exchanged elements to be related. For eqv the equality of sort keys, this captures exactly the reorderings a sort with an arbitrary tie-break can introduce.

Instances For
    Dependency graph

    Sorted permutations are tie-block permutations #

    A sort determines a list up to a tie-block permutation as soon as the relation it sorts by is total and transitive and its ties are exactly equality of some key. The canonical case is key x ≤ key y for a key into a linear order, but a window's frame is sorted by its ORDER BY, which is not of that shape: it reads the order columns in the clause's direction and null placement, and breaks the clause's ties by the canonical order.

    theorem tiePerm_of_perm_of_sorted {α κ : Type} [DecidableEq α] [LinearOrder κ] (key : α → κ) {l₁ l₂ : List α} (hperm : l₁.Perm l₂) (hs₁ : List.Pairwise (fun (x y : α) => key x ≤ key y) l₁) (hs₂ : List.Pairwise (fun (x y : α) => key x ≤ key y) l₂) :
    TiePerm (fun (x y : α) => key x = key y) l₁ l₂

    Two lists that are permutations of each other and both sorted by the key key differ only by a tie-block permutation on key equality: the sort order determines everything except the arrangement inside blocks of equal keys.

    Dependency graph

    Position bookkeeping for the world split #

    The recursion form of predicate provenance #

    def AggValue.predProvAux {T K : Type} [CommSemiringWithMonus K] (f : SeqAggFunc T) (P : T → Kleene) :
    List T → K → Bool → List (T × K) → K

    Recursion form of the predicate provenance of a token: acc accumulates the values of the occurrences kept so far, ex the sum of the annotations of the occurrences discarded so far, and started records whether an occurrence has been kept (worlds must end up non-empty). Keeping an occurrence contributes its annotation as a factor; discarding it moves its annotation into the pending 𝟙 ⊖ Σ factor materialized at the end of the list.

    Equations
    Instances For
      Dependency graph

      The predicate provenance of a token is its recursion form.

      Dependency graph
      theorem AggValue.predProv_congr {T K : Type} [ValueType T] [CommSemiringWithMonus K] [DecidableEq K] {a b : AggValue T K} (hagg : a.agg = b.agg) (h : TiePerm (fun (p q : T × K) => p.1 = q.1) a.occs b.occs) (op : CompOp) (c : T) :
      a.predProv op c = b.predProv op c

      The comparison case.

      Dependency graph
      theorem AggValue.vals_congr {T K : Type} [ValueType T] {a b : AggValue T K} (hagg : a.agg = b.agg) (hsc : a.scalar = b.scalar) (h : TiePerm (fun (p q : T × K) => p.1 = q.1) a.occs b.occs) :
      a.vals = b.vals

      Tie-block permutation changes no value the token takes: its swaps exchange occurrences of equal value, so the list of values is untouched and AggValue.vals reads only that.

      Dependency graph

      The several-leaf recursion #

      predProvAux walks the occurrence family of one token, carrying the values kept so far. An aggregate expression reads several leaves over one shared family, each on its own part of a world, so the walk carries one accumulator per leaf and keeps an occurrence only for the leaves that read it. The world condition becomes per leaf as well: a world must meet the part of the family each grouped leaf reads.

      The occurrence list carries, per occurrence, the value each leaf reads there, the annotation, and which leaves read it – which is AggExpr's occs together with reads, in the form a recursion over the list can use. Since an AggExpr's occurrences carry their leaf flags, AggExpr.leafSeq_eq_filter is the shape the walk reads, and predProvWith_eq_exprProvAux specializes the walk to AggExpr.predProvWith.

      def AggExpr.exprProvAux {T K : Type} [CommSemiringWithMonus K] {q : ℕ} (aggs : Fin q → SeqAggFunc T) (sc : Fin q → Bool) (g : (Fin q → T) → T) (P : T → Kleene) :
      (Fin q → List T) → K → (Fin q → Bool) → List ((Fin q → T) × K × (Fin q → Bool) × (Fin q → Bool)) → K

      The several-leaf counterpart of AggValue.predProvAux: acc l the values leaf l has kept, ex the annotations discarded so far, and started l whether leaf l has kept an occurrence.

      Equations
      Instances For
        Dependency graph