Documentation

Provenance.AnnotatedBasis

The basis of the annotated semantics: the statement and the inherited rows #

A set of classes generates the annotated algebra over a semiring K (GeneratesAnn) when every query of the whole algebra in the minimal universe that reads no aggregate column as a key is matched, over the same classes, by a query of the same kinds whose annotated evaluation agrees with it on every K-instance wherever the query's recursions settle there (AggQueryIn.AnnSettlesAt). The equality is of the bags of annotated tuples the two queries emit, tokens collapsed and group factors cashed (AggQueryIn.evaluateAnnotated); it is finer than equality up to rows annotated ๐Ÿ˜ (GeneratesAnnZ), so a set that generates here generates there.

What transfers from the plain classification, for every semiring at once: the data part of the annotated evaluation is the plain evaluation of the query stripped of its aggregate selections and differences (AggQueryIn.evaluateAnnotated_toPlain), and the recursions settle annotated exactly when the stripped query's do plain (AggQueryIn.settlesAt_stripAgg_of_annSettlesAt, AggQueryIn.annSettlesAt_of_settlesAt). So a set generating the annotated algebra generates, in the plain semantics, every query with nothing to strip (generatesAtNoExplode_of_generatesAnn), which every witness of the plain rows is: โˆ…, ฮ , ฮณ, ฮผ^โŠŽ, win, ฯƒ and one of ร—/apply are in every set generating the annotated algebra over โ„• with the counting aggregate (required_mem_of_generatesAnn). The selection row holds outright here, the alternatives being out of the language. The trivial generating set is every class (generatesAnn_plainRecOps); the smaller ones are the next step.

A plain instance, annotated ๐Ÿ™ #

Every tuple annotated ๐Ÿ™.

Equations
Instances For
    Dependency graph

    Every tuple of every relation annotated ๐Ÿ™.

    Equations
    Instances For
      Dependency graph

      Queries with nothing to strip #

      def AggQueryIn.liftFaithful {T : Type} {c n : โ„•} {ฮบ : Fin n โ†’ ColKind} {l : List (String ร— โ„•)} :
      AggQueryIn T c n ฮบ l โ†’ Prop

      A query whose annotated reading of a plain instance is faithful to its plain reading: no selection on an aggregate value and no difference, so stripAgg removes nothing and the data part of the annotated evaluation is the plain evaluation of the query itself; and no set recursion, whose annotated rounds may go on changing annotations where its plain rounds have settled. Every witness of the plain rows is one.

      Equations
      Instances For
        Dependency graph

        What stripping keeps #

        The settling of the recursions, annotated and plain #

        theorem AggQueryIn.settlesAt_stripAgg_of_annSettlesAt {T : Type} [ValueType T] {K : Type} [CommSemiringWithMonus K] [DecidableEq K] [HasAltLinearOrder K] {c n : โ„•} {ฮบ : Fin n โ†’ ColKind} (q : AggQueryIn T c n ฮบ) (hq : q.noExplode) (hh : q.hygienic) (hwk : q.wellKinded (ColKind.allReg c) HoleKinds.empty) (d : AnnotatedDatabase T K) (ฮณ : Fin c โ†’ T) (hr : q.AnnSettlesAt d ฮณ { }) :

        The closed form: settling annotated at d is settling plain, stripped, at its data part.

        Dependency graph
        theorem AggQueryIn.annSettlesAt_of_settlesAt {T : Type} [ValueType T] {K : Type} [CommSemiringWithMonus K] [DecidableEq K] [HasAltLinearOrder K] {c n : โ„•} {ฮบ : Fin n โ†’ ColKind} (q : AggQueryIn T c n ฮบ) (hf : q.liftFaithful) (hq : q.noExplode) (hh : q.hygienic) (hwk : q.wellKinded (ColKind.allReg c) HoleKinds.empty) (d : AnnotatedDatabase T K) (ฮณ : Fin c โ†’ T) (hr : q.SettlesAt d.toPlain ฮณ) :
        q.AnnSettlesAt d ฮณ { }

        The closed form.

        Dependency graph

        The generation of the annotated algebra #

        A set of classes generates the annotated algebra over K: every query of the whole algebra in the minimal universe, over the schema, well-kinded and reading no aggregate column as a key, is matched by a well-kinded query over the classes, of the same kinds, reading none either, whose annotated evaluation settles and agrees with the query's on every K-instance at which the query's does. The equality is of the bags of annotated tuples (AggQueryIn.evaluateAnnotated), finer than equality up to rows annotated ๐Ÿ˜.

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

          Every class generates, trivially: the query is its own match.

          Dependency graph
          theorem GeneratesAnn.mono {T : Type} [ValueType T] {K : Type} [CommSemiringWithMonus K] [DecidableEq K] [HasAltLinearOrder K] {sch : Schema} {cnt : SeqAggFunc T} {S S' : Set OpKind} (hSS : S โІ S') (h : GeneratesAnn T K sch cnt S) :
          GeneratesAnn T K sch cnt S'
          Dependency graph
          theorem generatesAtNoExplode_of_generatesAnn {T : Type} [ValueType T] {K : Type} [CommSemiringWithMonus K] [DecidableEq K] [HasAltLinearOrder K] {sch : Schema} {cnt : SeqAggFunc T} {S : Set OpKind} (h : GeneratesAnn T K sch cnt S) {n : โ„•} {ฮบ : Fin n โ†’ ColKind} (q : AggQuery T n ฮบ) (hf : AggQueryIn.liftFaithful q) (ha : AggQueryIn.noExplode q) (hwk : AggQueryIn.wellKinded q (ColKind.allReg 0) HoleKinds.empty) :
          GeneratesAtNoExplode T sch cnt S q

          The transfer to the plain semantics: a set generating the annotated algebra over K generates, plainly and without reading aggregate columns as keys, every faithful query โ€“ the matching query, stripped of its aggregate selections and differences, reads a plain instance annotated ๐Ÿ™ as the query does, on the data part.

          Dependency graph

          The witnesses are faithful #

          The inherited rows #

          What every set generating the annotated algebra contains, over โ„• with the counting aggregate and over every commutative m-semiring: โˆ…, ฮ , ฮณ, ฮผ^โŠŽ, win, ฯƒ, and one of ร— and the apply โ€“ the plain rows, inherited through the data part, with the selection row no longer a disjunction.

          Dependency graph