Documentation

Provenance.AnnotatedDiffRow

The difference is necessary in the annotated algebra #

A set of classes that generates the annotated algebra contains −. The witness semiring is ℕ × ℕ, ℕ read on two instances at once (NatPair). The invariant is that, without a difference, every annotation a query builds is zero in one coordinate exactly where it is in the other (ZeroPat). That holds of sums and products, since ℕ has no zero divisors, of δ, which is the support map, and of the 𝟙 ⊖ s a world of an aggregate value is weighed with. It fails for a difference: R − S, with R holding a annotated (1, 3) and S holding it twice annotated (1, 1), gives (1, 3) ⊖ (2, 2) = (0, 1) (diff_mem_of_generatesAnn).

The invariant is stated for any property Q of annotations closed under those operations (AnnClosed), and proved of every annotation the evaluator builds – a row's, the occurrences' of the tokens it carries, and the predicate provenance of a selection on aggregate values (annIn_evaluate).

Two copies of ℕ #

ℕ read on two instances at once: pairs, with every operation componentwise.

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

    The two coordinates of a pair.

    Equations
    Instances For
      Dependency graph

      The second coordinate.

      Equations
      Instances For
        Dependency graph
        def NatPair.mk (u v : ℕ) :

        A pair from its coordinates.

        Equations
        Instances For
          Dependency graph
          theorem NatPair.ext {a b : NatPair} (h₁ : a.fst = b.fst) (h₂ : a.snd = b.snd) :
          a = b
          Dependency graph
          theorem NatPair.le_iff {a b : NatPair} :
          a ≤ b ↔ a.fst ≤ b.fst ∧ a.snd ≤ b.snd
          Dependency graph
          Dependency graph

          The support map, coordinate by coordinate.

          Equations
          Instances For
            Dependency graph
            theorem NatPair.natCast_eq (n : ℕ) :
            ↑n = mk n n
            Dependency graph
            @[instance_reducible]
            Equations
            • One or more equations did not get rendered due to their size.
            Dependency graph
            Dependency graph
            @[instance_reducible]
            Equations
            • One or more equations did not get rendered due to their size.
            Dependency graph

            The two coordinates vanish together.

            Equations
            Instances For
              Dependency graph

              Properties of annotations the operators keep, but for a difference #

              structure AnnClosed {K : Type} [CommSemiringWithMonus K] (Q : K → Prop) :

              A property of annotations every operator but the difference keeps: 𝟘, 𝟙, sums, products, δ, and 𝟙 ⊖ a.

              • zero : Q 0
              • one : Q 1
              • add (a b : K) : Q a → Q b → Q (a + b)
              • mul (a b : K) : Q a → Q b → Q (a * b)
              • delta (a : K) : Q a → Q (SemiringWithMonus.delta a)
              • one_sub (a : K) : Q a → Q (1 - a)
              Instances For
                Dependency graph

                The annotations a token carries #

                def AggValue.AnnsIn {T K : Type} (Q : K → Prop) (a : AggValue T K) :

                Every occurrence of an aggregate value is annotated within Q.

                Equations
                Instances For
                  Dependency graph
                  def AggExpr.AnnsIn {T K : Type} (Q : K → Prop) (e : AggExpr T K) :

                  Every occurrence of an aggregate expression is annotated within Q.

                  Equations
                  Instances For
                    Dependency graph
                    def NestInner.AnnsIn {T K : Type} (Q : K → Prop) (j : ℕ) :
                    NestInner T K j → Prop

                    Every annotation of an inner value, at every storey, is within Q.

                    Equations
                    Instances For
                      Dependency graph
                      def NestedValue.AnnsIn {T K : Type} (Q : K → Prop) (a : NestedValue T K) :

                      Every occurrence of a nested value, and every inner one at every storey, is annotated within Q.

                      Equations
                      Instances For
                        Dependency graph
                        def AggTok.AnnsIn {T K : Type} (Q : K → Prop) :
                        AggTok T K → Prop

                        Every annotation a token carries is within Q.

                        Equations
                        Instances For
                          Dependency graph

                          The predicate provenance #

                          Every annotation the evaluator builds #

                          def GenRow.AnnIn {T K : Type} (Q : K → Prop) {n : ℕ} (r : GenRow T K n) :

                          A row's annotations are within Q: its concrete part, its pending factors' occurrences, and every annotation the tokens it holds carry.

                          Equations
                          Instances For
                            Dependency graph
                            theorem annIn_evaluate {T : Type} [ValueType T] {K : Type} [CommSemiringWithMonus K] [DecidableEq K] [HasAltLinearOrder K] {Q : K → Prop} (hQ : AnnClosed Q) {d : AnnotatedDatabase T K} {S : Set OpKind} (hS : OpKind.diff ∉ S) {Θ : Set (SeqAggFunc T)} (hD : ∀ (k : ℕ) (t : String) (r : AnnotatedRelation T K k), AnnotatedDatabase.find k t d = some r → ∀ a ∈ r, Q a.2) {c n : ℕ} {κ : Fin n → ColKind} {l : List (String × ℕ)} (q : AggQueryIn T c n κ l) :
                            AggQueryIn.usesOnly S q → AggQueryIn.inSig Θ q → q.noExplode → ∀ (γ : Fin c → T) (E : EvalEnv T K), (∀ (k : Fin c) (a : AggTok T K), E.ctxAt c γ k = Sum.inr a → AggTok.AnnsIn Q a) → (∀ p ∈ l, ∀ r ∈ E.holes p.1 p.2, GenRow.AnnIn Q r) → ∀ r ∈ q.evaluate d γ E, GenRow.AnnIn Q r

                            Every annotation a query without a difference builds is within any Q the other operators keep, as soon as the instance's annotations, the context's tokens and the rounds the holes are bound to are.

                            Dependency graph

                            The witness #

                            The schema of two unary relations, R and S.

                            Equations
                            Instances For
                              Dependency graph

                              R − S.

                              Equations
                              Instances For
                                Dependency graph

                                The instance it tells apart from every query without a difference: R holds 0 annotated (1, 3), and S holds it twice, annotated (1, 1).

                                Equations
                                Instances For
                                  Dependency graph

                                  − is in every set generating the annotated algebra over ℕ × ℕ: without a difference, every annotation of a query's result is zero in one coordinate exactly where it is in the other, and R − S gives (0, 1) on dDiff.

                                  Dependency graph