Documentation

Provenance.DerivedAnn

Annotations of the derived operators #

The annotations of the operators of Provenance.Derived follow from their definitions, being the annotations the basis gives the query each one abbreviates. Some are worth computing, because they are what the choice of definition is answerable for.

Intersection is the first. q₁ ∩ q₂ annotates a shared tuple by (⊕ α) ⊗ (⊕ β), the sums ranging over its copies on each side: the provenance of a conjunction of the two memberships. The other definition that comes to mind, ε(q₁ - (q₁ - q₂)), has the same rows and the same support over 𝔹, and annotates them by a difference of differences instead.

noncomputable def AggQueryIn.annSum {T K : Type} [CommSemiringWithMonus K] [DecidableEq K] [HasAltLinearOrder K] {n : ℕ} [ValueType T] (q : AggQuery T n (ColKind.allReg n)) (d : AnnotatedDatabase T K) (u : Tuple T n) :
K

The ⊕-sum of the annotations a query gives one tuple: what duplicate elimination accumulates on it.

Equations
Instances For
    Dependency graph
    def AnnotatedRelation.annSum {T K : Type} [CommSemiringWithMonus K] {n : ℕ} [ValueType T] (r : AnnotatedRelation T K n) (u : Tuple T n) :
    K

    The ⊕-sum of the annotations one tuple carries in an annotated relation.

    Equations
    Instances For
      Dependency graph

      Outer joins #

      noncomputable def AggQueryIn.matchAnn {T K : Type} [CommSemiringWithMonus K] [DecidableEq K] [HasAltLinearOrder K] [ValueTypeNull T] {n₁ n₂ : ℕ} (φ : GenPred T (ColKind.allReg (n₁ + n₂))) (q₁ : AggQuery T n₁ (ColKind.allReg n₁)) (q₂ : AggQuery T n₂ (ColKind.allReg n₂)) (d : AnnotatedDatabase T K) (u : Tuple T n₁) :
      K

      The ⊕-sum of the annotations of a row's matches, over the matches of every copy of its tuple – the difference the padded copy goes through is per tuple and syntactic.

      Equations
      • One or more equations did not get rendered due to their size.
      Instances For
        Dependency graph
        noncomputable def AggQueryIn.matchAnnRight {T K : Type} [CommSemiringWithMonus K] [DecidableEq K] [HasAltLinearOrder K] [ValueTypeNull T] {n₁ n₂ : ℕ} (φ : GenPred T (ColKind.allReg (n₁ + n₂))) (q₁ : AggQuery T n₁ (ColKind.allReg n₁)) (q₂ : AggQuery T n₂ (ColKind.allReg n₂)) (d : AnnotatedDatabase T K) (v : Tuple T n₂) :
        K

        The ⊕-sum of the annotations of the matches of a row of the right arm.

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

          Semijoin and antijoin #

          The ⊕-sum of every annotation of an annotated relation: the provenance of “there is a row here”, which is what an existential subquery asks for.

          Equations
          Instances For
            Dependency graph
            noncomputable def AggQueryIn.matchToken {T K : Type} [CommSemiringWithMonus K] [DecidableEq K] [HasAltLinearOrder K] [ValueType T] {k l : ℕ} (cnt : SeqAggFunc T) (kap : Fin l) (φ : GenPredIn T k (ColKind.allReg l)) (Q : AggQueryIn T k l (ColKind.allReg l)) (d : AnnotatedDatabase T K) (u : Tuple T k) :

            The token a match count builds on a row u of the left arm: the scalar count, over the column kap, of the rows of Q that φ matches u with. Its family is the count's, and records the values of u the count reads.

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

              What a semijoin and an antijoin annotate #

              The FILTER clause #

              The clause changes nothing about a group: the token carries all of its occurrences, so the group's key and its existence factor are those of all of them, and a filtered-out occurrence still witnesses it. What changes is the value the token takes in a world, and it changes there in the same way as over plain relations – the input policy drops what the clause nulls out, so the aggregate reads exactly the occurrences of that world the clause keeps.

              Why a null-keeping aggregate has to be told about the clause #

              On a null-skipping aggregate and on a count, FILTER is a term: nulling the rejected occurrences out and letting the input policy drop them is cutting them from the sequence (aggValOn_filterTerm_sqlOf, aggValOn_filterTerm_counting). On a null-keeping aggregate it is not a term, and here is why: such an aggregate reads the null as a value, so it reads the rejected occurrences too, and the clause has to cut the sequence itself (Having.aggValOnWhen).

              @[reducible, inline]

              The value domain of the counterexample: ℕ with a null adjoined.

              Equations
              Instances For
                Dependency graph

                A null-keeping aggregate: the length of the sequence, nulls included. This is ARRAY_AGG's input policy – every value is read – in the one shape a ValueType affords, there being no array in the domain: what the aggregate returns is how many values it was given.

                Equations
                Instances For
                  Dependency graph

                  A group of two occurrences, carrying the values 1 and 2.

                  Equations
                  Instances For
                    Dependency graph
                    @[reducible, inline]

                    The clause x = 1, which keeps the first occurrence and rejects the second.

                    Equations
                    Instances For
                      Dependency graph
                      @[reducible, inline]

                      Its right-hand side.

                      Equations
                      Instances For
                        Dependency graph

                        The token a filtered aggregation builds #

                        Constant relations, annotated #

                        The unit relation's row and each row of a constant relation carry 𝟙: a constant relation is part of the query, so no instance weighs it.