Documentation

Provenance.AnnotatedApplyRow

The apply row up to ā‰ˆ with occurrence identity #

Annotated results are compared up to ā‰ˆ, equality up to rows annotated šŸ˜: rows annotated šŸ˜ and occurrences annotated šŸ˜ are dropped, and what is left is equal up to a one-to-one renaming of the occurrences, which keeps which aggregate values share which occurrences. GeneratesAnnZ reads an aggregate value only through its value; this module compares aggregate values through their occurrences, using the identities the evaluator stamps on them (AggValue.oids, AggExpr.oids).

An ordinary token with its occurrences annotated šŸ˜ dropped, together with their identities, and its family forgotten.

Equations
  • One or more equations did not get rendered due to their size.
Instances For
    Dependency graph
    def AggValue.renameOids {T K : Type} (Ļ„ : OccId T → OccId T) (a : AggValue T K) :

    The identities of a token's occurrences renamed.

    Equations
    Instances For
      Dependency graph
      def FamId.renameFamily {T : Type} (Ļ• : ā„• Ɨ List T Ɨ List (T āŠ• FamId T) → ā„• Ɨ List T Ɨ List (T āŠ• FamId T)) :
      FamId T → FamId T

      A family identifier with its family renamed by Ļ•: the column and the terms applied since are kept, so two identifiers of one family stay of one family.

      Equations
      Instances For
        Dependency graph
        def AggExpr.zeqNorm {T K : Type} [CommSemiringWithMonus K] [DecidableEq K] (Ļ„ : OccId T → OccId T) (φ : FamId T → FamId T) (e : AggExpr T K) :

        An aggregate expression read up to ā‰ˆ: its occurrences annotated šŸ˜ dropped together with their identities, the others' identities renamed by Ļ„, and its family by φ.

        Equations
        • One or more equations did not get rendered due to their size.
        Instances For
          Dependency graph
          def NestInner.zeqNorm {T K : Type} [CommSemiringWithMonus K] [DecidableEq K] (Ļ„ : OccId T → OccId T) (Ļ• : ā„• Ɨ List T Ɨ List (T āŠ• FamId T) → ā„• Ɨ List T Ɨ List (T āŠ• FamId T)) (j : ā„•) :
          NestInner T K j → NestInner T K j

          What an occurrence of a nested value reads, up to ā‰ˆ: at every storey the occurrences annotated šŸ˜ dropped, the identities of the expressions' occurrences renamed by Ļ„, and the families renamed by Ļ•.

          Equations
          Instances For
            Dependency graph
            def NestedValue.zeqNorm {T K : Type} [CommSemiringWithMonus K] [DecidableEq K] (Ļ„ : OccId T → OccId T) (Ļ• : ā„• Ɨ List T Ɨ List (T āŠ• FamId T) → ā„• Ɨ List T Ɨ List (T āŠ• FamId T)) (a : NestedValue T K) :

            A nested value read up to ā‰ˆ: its occurrences annotated šŸ˜ dropped, what the others read normalized at every storey, and its family renamed.

            Equations
            • One or more equations did not get rendered due to their size.
            Instances For
              Dependency graph
              def GenValue.zeqNorm {T K : Type} [CommSemiringWithMonus K] [DecidableEq K] (Ļ„ : OccId T → OccId T) (Ļ• : ā„• Ɨ List T Ɨ List (T āŠ• FamId T) → ā„• Ɨ List T Ɨ List (T āŠ• FamId T)) :
              GenValue T K → GenValue T K

              A column value read up to ā‰ˆ, its occurrence identities renamed by Ļ„ and its families by Ļ•. An ordinary token and an expression are read by their occurrences annotated otherwise than šŸ˜, their identities saying which occurrences they share with other values, and their families forgotten. A nested value is read the same way at every storey of what its occurrences read; its own occurrences carry no identity, and which ones two nested values share is said by their families, which are renamed rather than forgotten.

              Equations
              Instances For
                Dependency graph
                def GenRow.zeqNorm {T K : Type} [CommSemiringWithMonus K] [DecidableEq K] {n : ā„•} (Ļ„ : OccId T → OccId T) (Ļ• : ā„• Ɨ List T Ɨ List (T āŠ• FamId T) → ā„• Ɨ List T Ɨ List (T āŠ• FamId T)) (R : Multiset (GenRow T K n)) :

                A result read up to ā‰ˆ: its rows annotated otherwise than šŸ˜, each column read by GenValue.zeqNorm Ļ„ Ļ•, with its annotation.

                Equations
                Instances For
                  Dependency graph
                  def GenRow.zeqRen {T K : Type} [CommSemiringWithMonus K] [DecidableEq K] {n : ā„•} (R R' : Multiset (GenRow T K n)) :

                  Two results equivalent up to ā‰ˆ: equal once the rows and occurrences annotated šŸ˜ are dropped, up to a one-to-one renaming of the occurrences and one of the families.

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

                    A set of classes generates the annotated algebra up to ā‰ˆ with occurrence identity: GeneratesAnnZ with GenRow.zeqRen in place of GenRow.zeroNorm.

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

                      Hitting the occurrences annotated y #

                      The bound behind the row: in a query with no apply, every ordinary token holding an occurrence annotated y holds one whose identity lies in a set Z whose size depends on the query and not on the instance.

                      def AggValue.HitBy {T K : Type} (y : K) (Z : Finset (OccId T)) (a : AggValue T K) :

                      Z hits the token's occurrences annotated y: if it holds one, it holds one whose identity is in Z.

                      Equations
                      Instances For
                        Dependency graph
                        def GenValue.TokHit {T K : Type} (y : K) (Z : Finset (OccId T)) (v : GenValue T K) :

                        The same of a column value: every ordinary token it holds is hit.

                        Equations
                        Instances For
                          Dependency graph

                          The bound, through every operator #

                          theorem AggQueryIn.exists_hit {T K : Type} [ValueType T] [CommSemiringWithMonus K] [DecidableEq K] [HasAltLinearOrder K] (y : K) {S : Set OpKind} (hS : OpKind.apply āˆ‰ S) {Θ : Set (SeqAggFunc T)} {Bd : T → K → Prop} (hB : BdClosed Bd) (Fv V : Finset T) (hyV : āˆ€ v āˆ‰ Fv, Bd v y → v ∈ V) {c n : ā„•} {Īŗ : Fin n → ColKind} {l : List (String Ɨ ā„•)} (q : AggQueryIn T c n Īŗ l) :
                          usesOnly S q → inSig Θ q → q.noExplode → āˆ€ {ρc : Fin c → ColKind} {HK : HoleKinds}, q.wellKinded ρc HK → (āˆ€ x ∈ q.allConsts, x ∈ Fv) → ∃ (B : ā„•), āˆ€ (d : AnnotatedDatabase T K), (āˆ€ (m : ā„•) (s : String) (r : AnnotatedRelation T K m), AnnotatedDatabase.find m s d = some r → āˆ€ a ∈ r, TupBd (fun (x : T) => x ∈ Fv) Bd (a.1, a.2)) → āˆ€ (γ : Fin c → T) (C : Tuple (GenValue T K) c), (āˆ€ (k : Fin c), γ k ∈ Fv) → (āˆ€ (k : Fin c) (v : T), C k = Sum.inl v → v ∈ Fv) → ∃ (Z : Finset (OccId T)), Z.card ≤ B ∧ āˆ€ (Zā‚€ : Finset (OccId T)) (E : EvalEnv T K), E.ctxAt c γ = C → (āˆ€ (k : Fin c), GenValue.TokHit y Zā‚€ (C k)) → (āˆ€ p ∈ l, āˆ€ r ∈ E.holes p.1 p.2, āˆ€ (k : Fin p.2), GenValue.TokHit y Zā‚€ (r.1 k)) → āˆ€ r ∈ q.evaluate d γ E, āˆ€ (k : Fin n), GenValue.TokHit y (Zā‚€ ∪ Z) (r.1 k)

                          Without an apply, the ordinary tokens holding an occurrence annotated y are hit by a set of identities of size bounded by the query, uniformly over the instances whose relations are within a bound closed under the operations (BdClosed), where a value bounded by y and not a constant lies in V.

                          Dependency graph

                          The witness #

                          @[reducible, inline]
                          abbrev BoolXY :

                          Boolean functions of two variables: y (true) and x (false). Ī“ is the identity, and the two variables are incomparable.

                          Equations
                          Instances For
                            Dependency graph
                            Dependency graph
                            def yv :

                            The variable annotating the one row of S.

                            Equations
                            Instances For
                              Dependency graph
                              def xv :

                              The variable annotating every row of R.

                              Equations
                              Instances For
                                Dependency graph

                                The instance of size n: R holds 2 to n + 1, each annotated x, and S holds 1, annotated y.

                                Equations
                                Instances For
                                  Dependency graph
                                  def applyRight :
                                  AggQueryIn ā„• 1 1 fun (x : Fin 1) => ColKind.agg

                                  The right side: the count of the rows of S below the parameter.

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

                                    R ⊳ γ_āˆ…[count](Ļ•_{#1 < u}(S)).

                                    Equations
                                    Instances For
                                      Dependency graph

                                      The row #

                                      The apply row, up to ā‰ˆ with occurrence identity: a set of classes generating the annotated algebra up to ā‰ˆ, over Boolean functions of two variables, holds the apply. The source R ⊳ γ_āˆ…[count](Ļ•_{#1 < u}(S)) gives each parameter its own occurrence of the row of S, annotated y; a query without an apply hits all its occurrences annotated y with a set of identities bounded by the query (AggQueryIn.exists_hit), so it cannot keep n of them apart for n past that bound.

                                      Dependency graph

                                      The basis theorem up to ā‰ˆ with occurrence identity #

                                      ā‰ˆ with occurrence identity is finer than ā‰ˆ by value, so the rows up to ā‰ˆ transfer; the constructions agree with their source row by row, identities included, so the positive half holds with no renaming; and the apply row says that no set of classes does without the apply.

                                      theorem GeneratesAnnRen.toGeneratesAnnZ {T K : Type} [ValueType T] [CommSemiringWithMonus K] [DecidableEq K] [HasAltLinearOrder K] {sch : Schema} {cnt : SeqAggFunc T} {S : Set OpKind} (h : GeneratesAnnRen T K sch cnt S) :
                                      GeneratesAnnZ T K sch cnt S

                                      Generation up to ā‰ˆ with occurrence identity is generation up to ā‰ˆ by value.

                                      Dependency graph
                                      theorem annEpsOps_isBasis_in_class_ren :
                                      (āˆ€ (K : Type) [inst : CommSemiringWithMonus K] [inst_1 : DecidableEq K] [inst_2 : HasAltLinearOrder K], AnnBasisClass K → āˆ€ (sch : Schema), GeneratesAnnRen ā„• K sch SeqAggFunc.count annEpsOps) ∧ (āˆ€ S āŠ† annEpsOps, (āˆ€ (K : Type) [inst : CommSemiringWithMonus K] [inst_1 : DecidableEq K] [inst_2 : HasAltLinearOrder K], AnnBasisClass K → āˆ€ (sch : Schema), GeneratesAnnRen ā„• K sch SeqAggFunc.count S) → S = annEpsOps) ∧ āˆ€ (S : Set OpKind), (āˆ€ (K : Type) [inst : CommSemiringWithMonus K] [inst_1 : DecidableEq K] [inst_2 : HasAltLinearOrder K], AnnBasisClass K → āˆ€ (sch : Schema), GeneratesAnnRen ā„• K sch SeqAggFunc.count S) → OpKind.apply ∈ S

                                      The annotated basis theorem up to ā‰ˆ with occurrence identity, over the class: the nine classes generate the annotated algebra up to ā‰ˆ with occurrence identity over every semiring of AnnBasisClass, no proper subset of them does over all of those semirings, and no set of classes does without the apply.

                                      Dependency graph