Documentation

Provenance.AggQueryProbability

Possible-world foundations for the general evaluator #

The token-level ingredients of the random-world commutation for AggQueryIn.evaluate over 𝔹[X] (the general-evaluator counterpart of randomWorld_evaluateAnnotated, whose target statement is

genRandomWorld v (q.evaluate d) = q.evaluatePlain (d.randomWorld v)

– under a valuation v, specializing the general evaluation's surviving rows is the plain evaluation of the realized world):

def AggValue.realized {T X : Type} (a : AggValue T (BoolFunc X)) (v : X β†’ Bool) :

The positions of a token's occurrences realized by a valuation.

Equations
Instances For
    Dependency graph
    def AggTok.Realized {T : Type} [ValueType T] {X : Type} (v : X β†’ Bool) :
    AggTok T (BoolFunc X) β†’ Prop

    Whether an aggregate column's group is realized under a valuation – what guardedness asserts of every grouped column of a row. On an ordinary token that is a realized occurrence, unless the token is scalar; on a nested value and on an expression it is that the occurrences the valuation keeps are a world of it, which exempts a scalar reading in the same way.

    Equations
    Instances For
      Dependency graph
      theorem AggValue.specialize_eval {T X : Type} (a : AggValue T (BoolFunc X)) (v : X β†’ Bool) :
      (a.specialize fun (Ξ± : BoolFunc X) => Ξ± v) = a.valOn (a.realized v)

      The world-faithful reading under a valuation is the per-world reading at the realized world.

      Dependency graph

      A token read over its distinct values #

      The merged token reads one occurrence per class, annotated by the βŠ• of the class's members and ordered by the domain. Under a valuation it therefore reads the classes the world holds, in that world's own order, and its reading is the distinct aggregate of the realized occurrences – with no condition on the aggregate, which is what the order being a function of the values buys.

      theorem AggValue.specialize_mergeByValue {T : Type} [ValueType T] {X : Type} (a : AggValue T (BoolFunc X)) (v : X β†’ Bool) :
      (a.mergeByValue.specialize fun (Ξ± : BoolFunc X) => Ξ± v) = a.agg.distinct (List.map Prod.fst (List.filter (fun (o : T Γ— BoolFunc X) => o.2 v) a.occs))

      A merged token specializes to the distinct aggregate of the realized occurrences. Restricting to a world keeps the classes the world holds, in the order the domain gives their values, which is that world's own order.

      Dependency graph
      theorem AggValue.predProv_eval_iff {T : Type} [ValueType T] {X : Type} [Fintype X] [DecidableEq X] (a : AggValue T (BoolFunc X)) (op : CompOp) (c : T) (v : X β†’ Bool) :
      a.predProv op c v = true ↔ (a.realized v).Nonempty ∧ op.eval3 (a.specialize fun (Ξ± : BoolFunc X) => Ξ± v) c = Kleene.true

      The token-level PQE bridge. Under a valuation v, the predicate provenance of ⟨token⟩ op c is true iff the token's realized group is non-empty and its specialized aggregate value satisfies the comparison. The Οƒ-aggregate case of the random-world commutation reduces to this.

      Dependency graph

      The joint reading of two families, and the row it annotates #

      Over 𝔹[X] a valuation picks one world of a family – the occurrences it realizes – and the joint reading of two families is therefore true at a valuation exactly when each family's own realized world is a world of it and the test holds on the two values read there (AggValue.jointPair_eval_iff).

      That is what makes the row reading exact here, at every family size: the row an implementation reports is Ξ΄(β₁) βŠ— Ξ΄(Ξ²β‚‚) βŠ— (p₁ βŠ• pβ‚‚), which over 𝔹[X] is [T₁ β‰  βˆ…] ∧ [Tβ‚‚ β‰  βˆ…] ∧ (Οˆβ‚ ∨ Οˆβ‚‚) once each p_i's own existence guard is absorbed into the factor already beside it, and the joint reading is the same conjunction (AggValue.row_agree_of_delta_id). Ξ΄ being the identity is what the two Ξ΄ factors contribute, and it is a property of this semiring and not of its being a Boolean algebra: the indicator is a legal Ξ΄ on any Boolean algebra too, and over 𝔹 the two cannot be told apart.

      theorem AggValue.jointPair_eval_iff {T : Type} [ValueType T] {X : Type} [Fintype X] [DecidableEq X] (a b : AggValue T (BoolFunc X)) (R : T β†’ T β†’ Kleene) (v : X β†’ Bool) :
      Having.jointPair a b R v = true ↔ (a.scalar = true ∨ (a.realized v).Nonempty) ∧ (b.scalar = true ∨ (b.realized v).Nonempty) ∧ R (a.specialize fun (Ξ± : BoolFunc X) => Ξ± v) (b.specialize fun (Ξ± : BoolFunc X) => Ξ± v) = Kleene.true

      The joint reading over 𝔹[X]: true at a valuation exactly when each grouped family has a realized occurrence and the test holds on the two values the valuation reads.

      Dependency graph
      theorem AggValue.row_agree_of_delta_id {T : Type} [ValueType T] {X : Type} [Fintype X] [DecidableEq X] (a b : AggValue T (BoolFunc X)) (P Q : T β†’ Kleene) (ha : a.scalar = false) (hb : b.scalar = false) :
      SemiringWithMonus.delta (βˆ‘ i : Fin a.occs.length, a.anns i) * SemiringWithMonus.delta (βˆ‘ j : Fin b.occs.length, b.anns j) * (a.predProvWith P + b.predProvWith Q) = Having.jointPair a b fun (x y : T) => (P x).or (Q y)

      The row is exact over 𝔹[X], at every family size: for two grouped families, the row an implementation reports – the two groups' existence factors times the structural βŠ• of the two sides – is the joint reading of the disjunction.

      Each side's predicate provenance already carries its own family's existence, so the Ξ΄ factors absorb it and both readings come to β€œboth groups exist, and one of the two tests holds in the world the valuation picks”. Ξ΄ being the identity here is what lets the factors do that: chain_row_ne is the same statement failing where Ξ΄ collapses a group, in a semiring whose βŠ• is idempotent, so idempotence is not the condition.

      Dependency graph
      theorem NestedValue.World.ann_eval_iff {T : Type} [ValueType T] {X : Type} [Fintype X] [DecidableEq X] {a : NestedValue T (BoolFunc X)} {W : World T (BoolFunc X) a.lev} (hW : IsWorldOf a W) (v : X β†’ Bool) :
      W.ann v = true ↔ W = a.realizedWorld fun (Ξ± : BoolFunc X) => Ξ± v

      Only the realized world holds: over 𝔹[X] a world of a nested value is annotated true under a valuation exactly when it is the world the valuation cuts out – which is what makes the world sum a reading of one world.

      Dependency graph
      noncomputable def GenValue.specializeAt {T : Type} [ValueType T] {X : Type} (v : X β†’ Bool) :
      GenValue T (BoolFunc X) β†’ T

      The specialized reading of a lifted value: regular values are themselves, a token aggregates its realized occurrences.

      Equations
      Instances For
        Dependency graph
        noncomputable def GenRow.specializeTuple {T : Type} [ValueType T] {X : Type} {n : β„•} (v : X β†’ Bool) (u : Tuple (GenValue T (BoolFunc X)) n) :
        Tuple T n

        The specialized reading of a row's tuple.

        Equations
        Instances For
          Dependency graph
          noncomputable def genRandomWorld {T : Type} [ValueType T] {X : Type} {n : β„•} (v : X β†’ Bool) (R : Multiset (GenRow T (BoolFunc X) n)) :

          The realized world of a general evaluation: the rows whose finalized annotation is true under the valuation, with tokens specialized.

          Equations
          Instances For
            Dependency graph

            Evaluation of factored annotations #

            def annGuard {X : Type} (l : List (BoolFunc X)) (v : X β†’ Bool) :

            Truth of a group's existence guard under a valuation: some occurrence annotation is realized.

            Equations
            Instances For
              Dependency graph
              @[instance_reducible]
              instance instDecidableAnnGuard {X : Type} (l : List (BoolFunc X)) (v : X β†’ Bool) :
              Equations
              Dependency graph

              Specialized readings under kind conformance #

              The Οƒ-aggregate row lemma #

              def GenPredIn.selCompared {T K' : Type} [AddCommMonoid K'] {c n : β„•} {ΞΊ : Fin n β†’ ColKind} (Ο† : GenPredIn T c ΞΊ) (u : Tuple (GenValue T K') n) :

              The annotation lists of the tokens compared by a predicate on a row (the evaluator's compared).

              Equations
              Instances For
                Dependency graph
                def GenPredIn.selComparedScalar {T K' : Type} [AddCommMonoid K'] {c n : β„•} {ΞΊ : Fin n β†’ ColKind} (Ο† : GenPredIn T c ΞΊ) (u : Tuple (GenValue T K') n) :

                The compared tokens read in the scalar convention. A comparison against one of these entails no group's existence – it holds in the empty world – so its presence blocks the supersede whatever occurrences it carries.

                Equations
                • One or more equations did not get rendered due to their size.
                Instances For
                  Dependency graph
                  def GenPredIn.selPending {T K' : Type} [AddCommMonoid K'] [DecidableEq K'] {c n : β„•} {ΞΊ : Fin n β†’ ColKind} (Ο† : GenPredIn T c ΞΊ) (u : Tuple (GenValue T K') n) (p : Multiset (List K')) :

                  The pending factors after a Οƒ with aggregate atoms (the evaluator's update, definitionally).

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

                    The joint reading over 𝔹[X] #

                    Under a valuation exactly one world of each family is annotated true – the occurrences the valuation keeps – so the joint reading of a predicate holds exactly when the predicate holds of the values the row takes in those worlds, which are the specialized ones.

                    theorem GenPredIn.predsem_eval_iff {T : Type} [ValueType T] {X : Type} [Fintype X] [DecidableEq X] {c n : β„•} {ΞΊ : Fin n β†’ ColKind} (Ο† : GenPredIn T c ΞΊ) {Ξ³ : Fin c β†’ T} (neg : Bool) (u : Tuple (GenValue T (BoolFunc X)) n) (hconf : βˆ€ (k : Fin n), (u k).kindOf = (ΞΊ k).base) (v : X β†’ Bool) (hg : βˆ€ k ∈ Ο†.comparedCols, βˆ€ (a : AggTok T (BoolFunc X)), u k = Sum.inr a β†’ AggTok.Realized v a) :

                    Predicate provenance evaluation, under existence guards. On a kind-conformant row all of whose compared groups are realized non-empty, the predicate provenance is true iff the (polarity-adjusted) plain predicate holds on the specialized tuple.

                    Dependency graph
                    theorem GenPredIn.entails_guard {T : Type} [ValueType T] {X : Type} [Fintype X] [DecidableEq X] {c n : β„•} {ΞΊ : Fin n β†’ ColKind} (Ο† : GenPredIn T c ΞΊ) {Ξ³ : Fin c β†’ T} (neg : Bool) (u : Tuple (GenValue T (BoolFunc X)) n) (v : X β†’ Bool) (β„“β‚€ : List (BoolFunc X)) (huni : βˆ€ k ∈ Ο†.comparedCols, βˆ€ (a : AggTok T (BoolFunc X)), u k = Sum.inr a β†’ a.scalar = false ∧ a.annList = β„“β‚€) (hent : Ο†.entailsExistence neg = true) (hp : Ο†.predsem neg u Ξ³ v = true) :
                    annGuard β„“β‚€ v

                    Existence entailment extracts the guard. When a predicate entails existence and all its compared tokens carry the annotation list β„“β‚€, a true predicate provenance realizes β„“β‚€.

                    Dependency graph

                    Finalize algebra (any m-semiring) #

                    The row-level Οƒ lemmas #

                    theorem GenPredIn.sel_finalize_eval_iff {T : Type} [ValueType T] {X : Type} [Fintype X] [DecidableEq X] {c n : β„•} {ΞΊ : Fin n β†’ ColKind} (Ο† : GenPredIn T c ΞΊ) {Ξ³ : Fin c β†’ T} (u : Tuple (GenValue T (BoolFunc X)) n) (b : BoolFunc X) (p : Multiset (List (BoolFunc X))) (v : X β†’ Bool) (hconf : βˆ€ (k : Fin n), (u k).kindOf = (ΞΊ k).base) (hguard : { base := b, pending := p }.finalize v = true β†’ βˆ€ (k : Fin n) (a : AggTok T (BoolFunc X)), u k = Sum.inr a β†’ AggTok.Realized v a) :
                    { base := b * Ο†.predsemJ false u Ξ³, pending := Ο†.selPending u p }.finalize v = true ↔ { base := b, pending := p }.finalize v = true ∧ Ο†.holdsPlain (GenRow.specializeTuple v u) Ξ³

                    The Οƒ-aggregate row lemma. On a kind-conformant, guarded row, the updated annotation is realized iff the original annotation is realized and the plain predicate holds on the specialized tuple.

                    Dependency graph

                    The guardedness invariant #

                    def EvalEnv.Guarded {T : Type} [ValueType T] {X : Type} (E : EvalEnv T (BoolFunc X)) (v : X β†’ Bool) :

                    An environment is guarded at a valuation: every row of a round it binds that the valuation realizes has its tokens realized, and so has every token of its context.

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

                      Realized-world plumbing #

                      The Gamma case helpers #

                      theorem tokenOfWhen_filter_agg {T : Type} [ValueType T] {X : Type} [HasAltLinearOrder (BoolFunc X)] {c n' m' p' : β„•} (P : Tuple (Fin n') m') (O : Tuple (Fin n') p') (o : OrderSpec p') (w : ValueFrame T p') (t : TermIn T c n') (f g : SeqAggFunc T) (keep : Tuple T n' β†’ Bool) (R : AnnotatedRelation T (BoolFunc X) n') {x : AnnotatedTuple T (BoolFunc X) n'} (hx : x ∈ R) (v : X β†’ Bool) {Ξ³ : Fin c β†’ T} (hc : x.2 v = true) :
                      g (List.map Prod.fst (List.filter (fun (q : T Γ— BoolFunc X) => q.2 v) (ValueFrame.tokenOfWhen P O o w t f keep R x Ξ³).occs)) = ValueFrame.windowValueWhen P O o w t g keep (randomWorld v R) x.1 Ξ³

                      A filtered window token is world-faithful. Under a valuation it reads as the plain filtered aggregate the realized world gives its row: the clause cuts the frame by the rows and the valuation cuts it by the annotations, the two cuts commute, and both readings are sorted by the clause so only the values matter (OrderSpec.map_eq_of_sorted).

                      Dependency graph
                      theorem tokenOf_specialize {T : Type} [ValueType T] {X : Type} [HasAltLinearOrder (BoolFunc X)] {c n' m' p' : β„•} (P : Tuple (Fin n') m') (O : Tuple (Fin n') p') (o : OrderSpec p') (w : ValueFrame T p') (t : TermIn T c n') (f : SeqAggFunc T) (R : AnnotatedRelation T (BoolFunc X) n') {x : AnnotatedTuple T (BoolFunc X) n'} (hx : x ∈ R) (v : X β†’ Bool) {Ξ³ : Fin c β†’ T} (hc : x.2 v = true) :
                      ((ValueFrame.tokenOf P O o w t f R x Ξ³).specialize fun (Ξ± : BoolFunc X) => Ξ± v) = ValueFrame.windowValue P O o w t f (randomWorld v R) x.1 Ξ³

                      A token specializes to the aggregate of the realized frame: the case of tokenOf_filter_agg where the aggregate applied is the token's own.

                      Dependency graph
                      theorem tokenOfDist_specialize {T : Type} [ValueType T] {X : Type} [HasAltLinearOrder (BoolFunc X)] {c n' m' p' : β„•} (P : Tuple (Fin n') m') (O : Tuple (Fin n') p') (o : OrderSpec p') (w : ValueFrame T p') (t : TermIn T c n') (f : SeqAggFunc T) (dist : Bool) (R : AnnotatedRelation T (BoolFunc X) n') {x : AnnotatedTuple T (BoolFunc X) n'} (hx : x ∈ R) (v : X β†’ Bool) {Ξ³ : Fin c β†’ T} (hc : x.2 v = true) :
                      ((ValueFrame.tokenOfDist P O o w t f dist R x Ξ³).specialize fun (Ξ± : BoolFunc X) => Ξ± v) = ValueFrame.windowValue P O o w t (if dist = true then f.distinct else f) (randomWorld v R) x.1 Ξ³

                      The same for a token read over the frame's distinct values: it specializes to the distinct aggregate of the realized frame, with no condition on the aggregate.

                      Dependency graph
                      theorem exprOfWhen_specialize {T : Type} [ValueType T] {X : Type} [HasAltLinearOrder (BoolFunc X)] {c n' m' p' q' : β„•} (P : Tuple (Fin n') m') (O : Tuple (Fin n') p') (o : OrderSpec p') (ws : Fin q' β†’ ValueFrame T p') (ts : Fin q' β†’ TermIn T c n') (fs : Fin q' β†’ SeqAggFunc T) (g : (Fin q' β†’ T) β†’ T) (keeps : Fin q' β†’ Option (Selection T n')) (r : OccFam (AnnotatedTuple T (BoolFunc X) n')) (i : Fin r.size) (v : X β†’ Bool) {Ξ³ : Fin c β†’ T} (hc : (r.row i).2 v = true) :
                      ((ValueFrame.exprOfWhen P O o ws ts fs g keeps r i Ξ³).specialize fun (Ξ± : BoolFunc X) => Ξ± v) = g fun (l : Fin q') => ValueFrame.windowValueOpt P O o (ws l) (ts l) (fs l) (keeps l) (randomWorld v r.toMultiset) (r.row i).1 Ξ³

                      A filtered multi-frame window's column is world-faithful too. Each leaf reads its own frame cut down by its own clause and to the realized rows, which is the plain window value the realized world gives the row: a clause tests the row, and restricting the relation to a world does not move a row.

                      Dependency graph
                      theorem tokenOfDistWhen_specialize {T : Type} [ValueType T] {X : Type} [HasAltLinearOrder (BoolFunc X)] {c n' m' p' : β„•} (P : Tuple (Fin n') m') (O : Tuple (Fin n') p') (o : OrderSpec p') (w : ValueFrame T p') (t : TermIn T c n') (f : SeqAggFunc T) (dist : Bool) (keep : Tuple T n' β†’ Bool) (R : AnnotatedRelation T (BoolFunc X) n') {x : AnnotatedTuple T (BoolFunc X) n'} (hx : x ∈ R) (v : X β†’ Bool) {Ξ³ : Fin c β†’ T} (hc : x.2 v = true) :
                      ((ValueFrame.tokenOfDistWhen P O o w t f dist keep R x Ξ³).specialize fun (Ξ± : BoolFunc X) => Ξ± v) = ValueFrame.windowValueWhen P O o w t (if dist = true then f.distinct else f) keep (randomWorld v R) x.1 Ξ³

                      The same for the DISTINCT reading.

                      Dependency graph

                      The random-world commutation #

                      theorem AggQueryIn.genRandomWorld_evaluate_env {T : Type} [ValueType T] {X : Type} [Fintype X] [DecidableEq X] [HasAltLinearOrder (BoolFunc X)] {c n : β„•} {ΞΊ : Fin n β†’ ColKind} {l : List (String Γ— β„•)} (q : AggQueryIn T c n ΞΊ l) :
                      q.noProvSum β†’ q.hygienic β†’ βˆ€ {ρc : Fin c β†’ ColKind} {HK : HoleKinds}, q.wellKinded ρc HK β†’ βˆ€ (d : AnnotatedDatabase T (BoolFunc X)) (v : X β†’ Bool) {Ξ³ : Fin c β†’ T} (E : EvalEnv T (BoolFunc X)) (D : Database T) (N : Set String), E.Kinded Ξ³ ρc HK β†’ E.Guarded v β†’ (βˆ€ (n' : β„•), βˆ€ s' βˆ‰ N, Database.find n' s' D = Database.find n' s' (AnnotatedDatabase.randomWorld v d)) β†’ (βˆ€ s' ∈ N, noMention s' q) β†’ (βˆ€ p ∈ l, Database.find p.2 p.1 D = some (genRandomWorld v (E.holes p.1 p.2))) β†’ q.AnnSettlesAt d Ξ³ E β†’ genRandomWorld v (q.evaluate d Ξ³ E) = q.evaluatePlain D (GenRow.specializeTuple v (E.ctxAt c Ξ³))

                      Random-world commutation for the general evaluator (over 𝔹[X]): specializing the realized rows of the general annotated evaluation is the plain evaluation of the realized world. The Οƒ-aggregate case is the row lemma GenPredIn.sel_finalize_eval_iff under the conformance and guardedness invariants; the Gamma case rests on groupSeq_randomWorld; the multi-frame window on exprOf_specialize, which says its column reads in a world what the plain window reads of that world – so the operator asks nothing of its frames or of its aggregates here.

                      Second-level aggregation is covered too, at every storey: the group's pending factor is realized exactly when one of its rows is, so the keys that survive are the realized world's keys, and the token's realized world keeps those rows and reads each in the world the valuation cuts out of the row's own column, a nested column included (specialize_nestOfGroup, off GenValue.specialize_innerAt): a nested world decides each inner occurrence once, whatever its storey.

                      This is the form under an environment: the plain query is read in the context the realized world gives the environment's (an aggregate parameter reads, in a world, the value the world gives it, which is what the leaf AggQueryIn.Param carries), and in an instance binding each recursive name to the realized world of the round the environment binds it to. A term reads a parameter as a plain value only where it is not aggregate (AggQueryIn.wellKinded), so the two readings of the context agree there.

                      Dependency graph
                      theorem AggQueryIn.genRandomWorld_evaluate {T : Type} [ValueType T] {X : Type} [Fintype X] [DecidableEq X] [HasAltLinearOrder (BoolFunc X)] {c n : β„•} {ΞΊ : Fin n β†’ ColKind} (q : AggQueryIn T c n ΞΊ) (hq : q.noProvSum) (hh : q.hygienic) (hwk : q.wellKinded (ColKind.allReg c) HoleKinds.empty) (d : AnnotatedDatabase T (BoolFunc X)) (v : X β†’ Bool) {Ξ³ : Fin c β†’ T} (hr : q.AnnSettlesAt d Ξ³ { }) :

                      Random-world commutation for the general evaluator, for a query read with nothing bound: the realized world of the annotated evaluation is the plain evaluation of the realized world of the instance.

                      Dependency graph

                      Unrestricted probabilistic query evaluation (PQE) #

                      noncomputable def AggQueryIn.booleanProv {T : Type} [ValueType T] {X : Type} [HasAltLinearOrder (BoolFunc X)] {n : β„•} {ΞΊ : Fin n β†’ ColKind} (q : AggQuery T n ΞΊ) (d : AnnotatedDatabase T (BoolFunc X)) :

                      The Boolean provenance of a general query: the βŠ•-sum of the finalized annotations of its rows – true in a world iff some row is realized.

                      Equations
                      Instances For
                        Dependency graph
                        theorem AggQueryIn.booleanProv_eval_iff {T : Type} [ValueType T] {X : Type} [Fintype X] [DecidableEq X] [HasAltLinearOrder (BoolFunc X)] {n : β„•} {ΞΊ : Fin n β†’ ColKind} (q : AggQuery T n ΞΊ) (hq : noProvSum q) (hh : hygienic q) (hwk : wellKinded q (ColKind.allReg 0) HoleKinds.empty) (d : AnnotatedDatabase T (BoolFunc X)) (hr : AnnSettlesAt q d (fun (x : Fin 0) => 0) { }) (v : X β†’ Bool) :

                        Pointwise PQE bridge, general form: the Boolean provenance of a general query is true in a world iff the plain evaluation of that world is non-empty. Immediate from the random-world commutation.

                        Dependency graph
                        noncomputable def AggQueryIn.booleanProb {T : Type} [ValueType T] {X : Type} [Fintype X] [DecidableEq X] {n : β„•} {ΞΊ : Fin n β†’ ColKind} (P : ProbAssignment X) (q : AggQuery T n ΞΊ) (d : AnnotatedDatabase T (BoolFunc X)) :

                        Probability that a random world of d satisfies the Boolean query q (non-empty answer), over a tuple-independent probabilistic database.

                        Equations
                        Instances For
                          Dependency graph
                          theorem AggQueryIn.boolean_pqe {T : Type} [ValueType T] {X : Type} [Fintype X] [DecidableEq X] [HasAltLinearOrder (BoolFunc X)] {n : β„•} {ΞΊ : Fin n β†’ ColKind} (P : ProbAssignment X) (q : AggQuery T n ΞΊ) (hq : noProvSum q) (hh : hygienic q) (hwk : wellKinded q (ColKind.allReg 0) HoleKinds.empty) (d : AnnotatedDatabase T (BoolFunc X)) (hr : AnnSettlesAt q d (fun (x : Fin 0) => 0) { }) :

                          Unrestricted probabilistic query evaluation. For any general query – aggregate comparisons anywhere, through joins, projections, unions and further selections – over a tuple-independent probabilistic database, the probability that a random world satisfies the Boolean query equals the probability of its Boolean provenance. This removes the top-level restriction of the fused booleanHaving_pqe.

                          Dependency graph
                          noncomputable def AggQueryIn.tupleProv {T : Type} [ValueType T] {X : Type} [HasAltLinearOrder (BoolFunc X)] {n : β„•} (q : AggQuery T n (ColKind.allReg n)) (d : AnnotatedDatabase T (BoolFunc X)) (t : Tuple T n) :

                          The provenance of a tuple t in a general query with all-regular output: the βŠ•-sum of the finalized annotations of the rows whose data part is t.

                          Equations
                          • One or more equations did not get rendered due to their size.
                          Instances For
                            Dependency graph
                            theorem AggQueryIn.tupleProv_eval_iff {T : Type} [ValueType T] {X : Type} [Fintype X] [DecidableEq X] [HasAltLinearOrder (BoolFunc X)] {n : β„•} (q : AggQuery T n (ColKind.allReg n)) (hq : noProvSum q) (hh : hygienic q) (hwk : wellKinded q (ColKind.allReg 0) HoleKinds.empty) (d : AnnotatedDatabase T (BoolFunc X)) (hr : AnnSettlesAt q d (fun (x : Fin 0) => 0) { }) (t : Tuple T n) (v : X β†’ Bool) :

                            Pointwise tuple-marginal bridge: the provenance of t is true in a world iff t belongs to the plain evaluation of that world.

                            Dependency graph
                            noncomputable def AggQueryIn.tupleProb {T : Type} [ValueType T] {X : Type} [Fintype X] [DecidableEq X] {n : β„•} (P : ProbAssignment X) (q : AggQuery T n (ColKind.allReg n)) (d : AnnotatedDatabase T (BoolFunc X)) (t : Tuple T n) :

                            The marginal probability that t belongs to a random world's answer.

                            Equations
                            Instances For
                              Dependency graph
                              theorem AggQueryIn.tuple_pqe {T : Type} [ValueType T] {X : Type} [Fintype X] [DecidableEq X] [HasAltLinearOrder (BoolFunc X)] {n : β„•} (P : ProbAssignment X) (q : AggQuery T n (ColKind.allReg n)) (hq : noProvSum q) (hh : hygienic q) (hwk : wellKinded q (ColKind.allReg 0) HoleKinds.empty) (d : AnnotatedDatabase T (BoolFunc X)) (hr : AnnSettlesAt q d (fun (x : Fin 0) => 0) { }) (t : Tuple T n) :
                              tupleProb P q d t = P.funcProb (tupleProv q d t)

                              Unrestricted tuple-marginal PQE: for a general query with all-regular output over a tuple-independent probabilistic database, the marginal probability of an answer tuple is the probability of its provenance. This is the general-evaluator counterpart of the classical intensional-PQE theorem ProbAssignment.theorem_12, with aggregate comparisons allowed anywhere in the query.

                              Dependency graph