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):
AggValue.realizedβ the positions of a token's occurrences realized by a valuation, andAggValue.specialize_evalconnecting the world-faithful readingspecializeto the per-world readingvalOnat the realized world;AggValue.predProv_eval_iffβ the token-level PQE bridge: under a valuation, the predicate provenance of a comparison against a token is true iff the realized group is non-empty and its aggregate value satisfies the comparison. This ishavingProv_eval_ifftransported to tokens; the Ο-aggregate case of the commutation reduces to it;GenRow.specializeTupleandgenRandomWorldβ the specialized reading of a row and the realized world of a general evaluation: the rows whose finalized annotation is true, with tokens specialized.
The positions of a token's occurrences realized by a valuation.
Instances For
Dependency graph
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
- AggTok.Realized v (AggTok.tok a) = (a.scalar = true β¨ (a.realized v).Nonempty)
- AggTok.Realized v (AggTok.nest a) = (a.realizedWorld fun (Ξ± : BoolFunc X) => Ξ± v).IsWorld a
- AggTok.Realized v (AggTok.expr e) = e.IsWorld (e.realizedWorld fun (Ξ± : BoolFunc X) => Ξ± v)
Instances For
Dependency graph
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.
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
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.
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
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
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
The specialized reading of a lifted value: regular values are themselves, a token aggregates its realized occurrences.
Equations
- GenValue.specializeAt v = Sum.elim id fun (a : AggTok T (BoolFunc X)) => AggTok.specialize (fun (Ξ± : BoolFunc X) => Ξ± v) a
Instances For
Dependency graph
The specialized reading of a row's tuple.
Equations
- GenRow.specializeTuple v u k = GenValue.specializeAt v (u k)
Instances For
Dependency graph
The realized world of a general evaluation: the rows whose finalized annotation is true under the valuation, with tokens specialized.
Equations
- genRandomWorld v R = Multiset.map (fun (r : GenRow T (BoolFunc X) n) => GenRow.specializeTuple v r.1) (Multiset.filter (fun (r : GenRow T (BoolFunc X) n) => r.2.finalize v = true) R)
Instances For
Dependency graph
Evaluation of factored annotations #
Truth of a group's existence guard under a valuation: some occurrence annotation is realized.
Instances For
Dependency graph
Equations
Dependency graph
Specialized readings under kind conformance #
The Ο-aggregate row lemma #
The annotation lists of the tokens compared by a predicate on a row
(the evaluator's compared).
Equations
- Ο.selCompared u = Multiset.filterMap (fun (k : Fin n) => match u k with | Sum.inl val => none | Sum.inr a => some a.annList) Ο.comparedCols.val
Instances For
Dependency graph
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
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.
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
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 #
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 #
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 #
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
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
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
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
The same for the DISTINCT reading.
Dependency graph
The random-world commutation #
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
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) #
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
- AggQueryIn.booleanProv q d = (Multiset.map (fun (r : GenRow T (BoolFunc X) n) => r.2.finalize) (AggQueryIn.evaluate q d)).sum
Instances For
Dependency graph
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
Probability that a random world of d satisfies the Boolean query
q (non-empty answer), over a tuple-independent probabilistic
database.
Equations
- AggQueryIn.booleanProb P q d = β v : X β Bool, if Multiset.card (AggQueryIn.evaluatePlain q (AnnotatedDatabase.randomWorld v d)) = 0 then 0 else P.valProb v
Instances For
Dependency graph
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
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
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
The marginal probability that t belongs to a random world's
answer.
Equations
- AggQueryIn.tupleProb P q d t = β v : X β Bool, if t β AggQueryIn.evaluatePlain q (AnnotatedDatabase.randomWorld v d) then P.valProb v else 0
Instances For
Dependency graph
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.