Documentation

Provenance.JointFamily

Two occurrence families as one #

What a predicate reading two aggregate values annotates is the ⊕ over the worlds of the union of the two families it reads. The families of two tokens are indexed separately – Fin m and Fin n – so the union has to be built. Having.catAnn concatenates the two annotation functions into one family on Fin (m + n), Having.leftFam and Having.rightFam are the two parts inside it, and Having.catWorld pairs a world of each into a world of the concatenation, leftPart and rightPart reading them back.

The reindexing lemmas say that reading a part of the concatenation is reading the family it came from (relAnn_catWorld_left and its right twin), and they need nothing of K. From them, a world of the union carries the product of its two halves' annotations exactly where K is complemented (worldAnn_catWorld) – so the split form in which a two-family reading is usually written is the union reading there, and need not be elsewhere.

def Having.catAnn {K : Type} {m n : ℕ} (α : Fin m → K) (β : Fin n → K) :
Fin (m + n) → K

The concatenation of two occurrence families: m + n occurrences, the first m of the left family and the last n of the right.

Equations
Instances For
    Dependency graph
    def Having.leftFam (m n : ℕ) :
    Finset (Fin (m + n))

    The left family inside the concatenation.

    Equations
    Instances For
      Dependency graph
      def Having.rightFam (m n : ℕ) :
      Finset (Fin (m + n))

      The right family inside the concatenation.

      Equations
      Instances For
        Dependency graph
        def Having.catWorld {m n : ℕ} (W₁ : Finset (Fin m)) (W₂ : Finset (Fin n)) :
        Finset (Fin (m + n))

        A world of each family, as one world of the concatenation.

        Equations
        Instances For
          Dependency graph
          def Having.leftPart {m n : ℕ} (W : Finset (Fin (m + n))) :

          The left half of a world of the concatenation.

          Equations
          Instances For
            Dependency graph
            def Having.rightPart {m n : ℕ} (W : Finset (Fin (m + n))) :

            The right half of a world of the concatenation.

            Equations
            Instances For
              Dependency graph
              @[simp]
              theorem Having.leftPart_catWorld {m n : ℕ} (W₁ : Finset (Fin m)) (W₂ : Finset (Fin n)) :
              leftPart (catWorld W₁ W₂) = W₁
              Dependency graph
              @[simp]
              theorem Having.rightPart_catWorld {m n : ℕ} (W₁ : Finset (Fin m)) (W₂ : Finset (Fin n)) :
              rightPart (catWorld W₁ W₂) = W₂
              Dependency graph
              @[simp]
              theorem Having.catWorld_parts {m n : ℕ} (W : Finset (Fin (m + n))) :
              Dependency graph
              def Having.catWorldEquiv (m n : ℕ) :
              Finset (Fin m) × Finset (Fin n) ≃ Finset (Fin (m + n))

              The worlds of the concatenation are the pairs of worlds.

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

                The joint reading of a test of two tokens #

                def Having.jointPair {K : Type} [CommSemiringWithMonus K] {T : Type} (a b : AggValue T K) (P : T → T → Kleene) :
                K

                What a predicate reading two aggregate values annotates: the ⊕ over the worlds of the union of the two families – those meeting each grouped one, a scalar token being exempt as always – of the world's annotation times the truth of the test there.

                This is the definition; the structural rules ∧ ↦ ⊗ and ∨ ↦ ⊕ compute it where the m-semiring's properties license them.

                Equations
                • One or more equations did not get rendered due to their size.
                Instances For
                  Dependency graph
                  theorem Having.jointPair_and_const {K : Type} [CommSemiringWithMonus K] {T : Type} (a b : AggValue T K) (c : Kleene) (P : T → T → Kleene) :
                  (jointPair a b fun (x y : T) => c.and (P x y)) = (if c = Kleene.true then 1 else 0) * jointPair a b P

                  A test that does not depend on the world factors out of the joint reading. A regular atom is such a test – it reads no occurrence family, so its truth is the same in every world – so conjoining one to a predicate multiplies the predicate's provenance by 𝟙 or by 𝟘 and changes nothing else. This is why a selection on regular columns standing between two aggregate selections neither changes a family nor contributes to the annotation of a row that survives it.

                  Dependency graph

                  Two columns from two different groupings #

                  Everything here reads the two families as disjoint – jointPair sums over the worlds of their concatenation, where the two halves are chosen independently. That is the joint reading when the families genuinely are disjoint, which is what two columns coming from two different groupings give; it is not the joint reading when the families coincide. Two aggregates of one group are one family, the sequence of occurrences alone making it (AggValue.annList_ofGroup), and reading them as two independent families counts a world once per half – over ℕ, 4 where the one-family reading gives 2 (natRange_jointPair_ne).

                  So the factorization below is about columns from different groupings, and says nothing about a conjunction of tests on two aggregates of one group, which needs exclusivity and an idempotent ⊗ (AggValue.predProvOf_mul_predProvOf) and fails over ℕ.

                  theorem Having.jointPair_and {K : Type} [CommSemiringWithMonus K] {T : Type} [ValueType T] [DecidableEq K] (hc : complemented K) (a b : AggValue T K) (P Q : T → Kleene) :
                  (jointPair a b fun (x y : T) => (P x).and (Q y)) = a.predProvOfWith P * b.predProvOfWith Q

                  Two one-column tests read jointly factorize over disjoint families, K being complemented. The disjointness is in jointPair itself, so this is a statement about two families that genuinely are disjoint and not about two columns of one group.

                  Dependency graph
                  theorem Having.altProvPair_eq_mul {K : Type} [CommSemiringWithMonus K] {T : Type} [ValueType T] [DecidableEq K] (hc : complemented K) (a b : AggValue T K) (v₁ v₂ : T) :
                  (jointPair a b fun (x y : T) => (CompOp.syneq.eval3 x v₁).and (CompOp.syneq.eval3 y v₂)) = a.altProv v₁ * b.altProv v₂

                  Where the two columns come from different groupings, the single atom comparing the tuple (a, b) with (v₁, v₂) is the two columns read one after the other, K being complemented: [a ≐ v₁] ⊗ [b ≐ v₂]. Where they come from one grouping their families coincide and this does not apply; there the tuple atom is a definition and the column-by-column product is a different value.

                  Dependency graph
                  theorem Having.jointPair_self_eq_mul {K : Type} [CommSemiringWithMonus K] {T : Type} [ValueType T] [DecidableEq K] (hc : complemented K) (a : AggValue T K) (P Q : T → Kleene) :
                  (jointPair a a fun (x y : T) => (P x).and (Q y)) = a.predProvOfWith P * a.predProvOfWith Q

                  Reading one family as two independent halves is exactly the column-by-column product. Instantiating the factorization at a = b says it: where a conjunction's two tests are read over one family split in two, what comes out is the product of the two one-test readings. So the gap between the tuple atom and the column-by-column reading, within one grouping, is the gap between a conjunction over one family and the product of its atoms – which needs exclusivity and an idempotent ⊗ (AggValue.predProvOf_mul_predProvOf) and fails over ℕ.

                  Three constructs that look unrelated in SQL meet the same identity: a range atom against its two bounds, two selections against one selection on their conjunction, and two aggregate key columns against the atom on their tuple. They fail together, at 4 against 2, or not at all.

                  Dependency graph

                  When the existence factors do absorb the ∨ rule #

                  ChainFive shows an idempotent ⊕ is not enough and δ = id is necessary. For two singleton grouped families the two hypotheses together are enough, and the statement is pure algebra: with δ the identity each existence factor is its family's own annotation, so the reported row is α ⊗ β ⊗ (α⊗[P] ⊕ β⊗[Q]) and the joint one α ⊗ β ⊗ [P ∨ Q], the single world of the union carrying α ⊗ β.

                  Each hypothesis does an identifiable job. Where one test holds the reported row repeats that side's annotation – α ⊗ β ⊗ α – and ⊗-idempotence collapses it, which δ = id supplies for free from the axiom δ(x) ⊗ x = x. Where both hold it carries two copies of α ⊗ β, and ⊕-idempotence collapses those. Where neither holds both sides are 𝟘. What is not covered is families of several occurrences, where the complement factors are no longer trivial.

                  theorem Having.row_absorb_singleton {K : Type} [CommSemiringWithMonus K] (hmul : mulIdempotent K) (hadd : idempotent K) (α β : K) (p q : Kleene) :
                  α * β * ((α * if p = Kleene.true then 1 else 0) + β * if q = Kleene.true then 1 else 0) = α * β * if p.or q = Kleene.true then 1 else 0

                  The row-level absorption for two singleton grouped families.

                  Dependency graph