Documentation

Provenance.FragQueryMeta

The fragment semantics under homomorphisms, over 𝔹 and over ℕ #

Three readings of the closed-form annotated semantics FragQueryIn.sem, each an induction over the syntax, and together what the extensionality theorem of Provenance.Extensionality needs.

Pushing a function through the annotations #

def AnnotatedRelation.mapAnn {T K K' : Type} (f : K → K') {n : ℕ} (r : AnnotatedRelation T K n) :

The annotations of a relation, read through a function.

Equations
Instances For
    Dependency graph
    def AnnotatedDatabase.mapAnn {T K K' : Type} (f : K → K') (d : AnnotatedDatabase T K) :

    The annotations of a database, read through a function.

    Equations
    Instances For
      Dependency graph
      theorem AnnotatedDatabase.find_mapAnn {T K K' : Type} (f : K → K') (n : ℕ) (s : String) (d : AnnotatedDatabase T K) :

      find commutes with reading the annotations through a function.

      Dependency graph
      theorem AnnotatedRelation.map_fst_mapAnn {T K K' : Type} (f : K → K') {n : ℕ} (r : AnnotatedRelation T K n) :
      Multiset.map Prod.fst (mapAnn f r) = Multiset.map Prod.fst (have this := r; this)

      The tuples of a relation are untouched.

      Dependency graph
      theorem AnnotatedRelation.annSum_mapAnn {T : Type} [ValueType T] {K : Type} [CommSemiringWithMonus K] {K' : Type} [CommSemiringWithMonus K'] [DecidableEq K'] (h : K →+* K') {n : ℕ} (r : AnnotatedRelation T K n) (u : Tuple T n) :
      (mapAnn (⇑h) r).annSum u = h (r.annSum u)

      The ⊕-sum of the annotations of a tuple, through a semiring homomorphism.

      Dependency graph

      The ⊕-sum of all the annotations, through a semiring homomorphism.

      Dependency graph
      theorem AnnotatedRelation.filter_mapAnn {T K K' : Type} (f : K → K') {n : ℕ} (r : AnnotatedRelation T K n) (P : Tuple T n → Prop) [DecidablePred P] :
      Multiset.filter (fun (p : AnnotatedTuple T K' n) => P p.1) (mapAnn f r) = mapAnn f (Multiset.filter (fun (p : AnnotatedTuple T K n) => P p.1) r)

      A filter on the tuples passes under the pushforward.

      Dependency graph
      def FragQueryIn.hasMonus {T : Type} [ValueType T] {c n : ℕ} :
      FragQueryIn T c n → Prop

      Whether a query uses the monus: a difference or an antijoin somewhere.

      Equations
      Instances For
        Dependency graph
        theorem FragQueryIn.not_hasMonus_of_level1 {T : Type} [ValueType T] {c n : ℕ} (q : FragQueryIn T c n) :
        q.level1 → ¬q.hasMonus

        A query of F₁ uses no monus.

        Dependency graph

        Homomorphisms #

        theorem FragQueryIn.sem_mapAnn {T : Type} [ValueType T] {K : Type} [CommSemiringWithMonus K] {K' : Type} [CommSemiringWithMonus K'] [DecidableEq K'] (h : K →+* K') {c n : ℕ} (q : FragQueryIn T c n) :
        (q.hasMonus → ∀ (x y : K), h (x - y) = h x - h y) → ∀ (d : AnnotatedDatabase T K) (γ : Fin c → T), q.sem (AnnotatedDatabase.mapAnn (⇑h) d) γ = AnnotatedRelation.mapAnn (⇑h) (q.sem d γ)

        The semantics commutes with a semiring homomorphism that preserves the monus where the query uses one.

        Dependency graph

        Over 𝔹: the support #

        find commutes with taking the support.

        Dependency graph
        theorem AnnotatedRelation.mem_support {T : Type} {n : ℕ} (r : AnnotatedRelation T Bool n) (u : Tuple T n) :
        u ∈ r.support ↔ ∃ p ∈ have this := r; this, p.1 = u ∧ p.2 = true

        Membership in the support: some copy of the tuple is annotated true.

        Dependency graph

        Over 𝔹, the ⊕-sum of the annotations of a tuple is true exactly when the tuple is in the support.

        Dependency graph

        Over 𝔹, the ⊕-sum of all the annotations is true exactly when the support is non-empty.

        Dependency graph
        theorem FragQueryIn.mem_support_sem {T : Type} [ValueType T] {c n : ℕ} (q : FragQueryIn T c n) (d : AnnotatedDatabase T Bool) (γ : Fin c → T) (u : Tuple T n) :
        u ∈ (q.sem d γ).support ↔ u ∈ have this := q.semPlain d.support γ; this

        Support adequacy over 𝔹, for the whole fragment: a tuple is in the support of the annotated result exactly when it is in the plain result of the support of the instance.

        Dependency graph

        Over ℕ: annotations as multiplicities #

        An ℕ-annotated relation, unfolded: each copy of a tuple is repeated as many times as its annotation says.

        Equations
        Instances For
          Dependency graph

          An ℕ-annotated database, unfolded relation by relation.

          Equations
          Instances For
            Dependency graph

            find commutes with unfolding.

            Dependency graph

            The multiplicity of a tuple in the unfolding is the ⊕-sum of its annotations.

            Dependency graph
            theorem FragQueryIn.semPlain_unfold {T : Type} [ValueType T] {c n : ℕ} (q : FragQueryIn T c n) :
            q.level0 → ∀ (d : AnnotatedDatabase T ℕ) (γ : Fin c → T), q.semPlain d.unfold γ = (q.sem d γ).unfold

            Adequacy in ℕ with multiplicities, on F₀: the plain semantics of the unfolded instance is the unfolded annotated semantics. A product multiplies multiplicities, a union adds them, and the other operators of F₀ carry them along.

            Dependency graph