ProvSQL C/C++ API
Adding support for provenance and uncertainty management to PostgreSQL databases
Loading...
Searching...
No Matches
Expectation.h
Go to the documentation of this file.
1/**
2 * @file Expectation.h
3 * @brief Analytical expectation / variance / moment evaluator over RV circuits.
4 *
5 * Computes E[X], Var[X], raw moments E[X^k] and central moments
6 * E[(X - E[X])^k] over a sub-circuit rooted at a scalar gate
7 * (@c gate_value, @c gate_rv, or @c gate_arith), using closed-form
8 * formulas wherever the sub-DAG decomposes structurally and falling
9 * back to Monte Carlo (via @c monteCarloScalarSamples) when
10 * structural shortcuts cannot decide a sub-expression.
11 *
12 * Decomposition rules:
13 * - @c gate_value: literal, constant moments.
14 * - @c gate_rv: closed-form moments per @c RandomVariable.h.
15 * - @c gate_arith PLUS / MINUS / NEG: linearity of expectation always
16 * applies; variance and higher moments require structural
17 * independence of the children (their reachable @c gate_rv
18 * footprints must be pairwise disjoint).
19 * - @c gate_arith TIMES: requires structural independence; otherwise
20 * MC fallback.
21 * - @c gate_arith DIV: closed form when the divisor is a deterministic
22 * constant (@c gate_value), otherwise MC fallback.
23 *
24 * MC fallback is governed by the @c provsql.rv_mc_samples GUC:
25 * non-zero values pick the sample count; zero disables the fallback,
26 * causing the evaluator to throw rather than sample. This keeps a
27 * single knob shared with future RV-MC fallback paths (Priority 7's
28 * island decomposer).
29 */
30#ifndef PROVSQL_EXPECTATION_H
31#define PROVSQL_EXPECTATION_H
32
33#include <optional>
34
35#include "GenericCircuit.h"
36
37namespace provsql {
38
39/**
40 * @brief The quantity asked for has a value in no world (an aggregate over a
41 * group empty in every world of positive probability): SQL's NULL,
42 * which the SQL entry points return.
43 *
44 * Distinct from a NaN, which is a value (a float can hold one).
45 */
47{
48public:
49/** @brief Construct for the quantity @p what. */
50explicit NoValueException(const std::string &what)
51 : CircuitException(what + ": the value is defined in no world") {}
52};
53
54/**
55 * @brief Compute @f$E[X]@f$ (or @f$E[X \mid A]@f$ if @p event_root is set)
56 * over the scalar sub-circuit rooted at @p root.
57 *
58 * The conditional path requires that @p event_root be a @c gate_t in
59 * the same @c GenericCircuit as @p root -- typically the circuit was
60 * loaded via @c getJointCircuit so a shared @c gate_rv between root
61 * and event has one @c gate_t, which is what couples the MC sampler.
62 * When @p event_root is @c std::nullopt the unconditional path
63 * (existing analytical decomposition with MC fallback) is taken
64 * unchanged.
65 *
66 * @throws CircuitException on malformed circuits, unknown
67 * distribution kinds, when @c provsql.rv_mc_samples is 0
68 * and a sub-expression cannot be decomposed analytically,
69 * or when the conditional MC pass accepts too few samples
70 * (suggesting @c P(A) is very small or zero).
71 */
72double compute_expectation(const GenericCircuit &gc, gate_t root,
73 std::optional<gate_t> event_root = std::nullopt);
74
75/**
76 * @brief Compute the raw moment @f$E[X^k]@f$ (or @f$E[X^k \mid A]@f$
77 * if @p event_root is set) for @c k >= 0.
78 *
79 * @c k = 0 returns 1; @c k = 1 delegates to @c compute_expectation.
80 */
81double compute_raw_moment(const GenericCircuit &gc, gate_t root, unsigned k,
82 std::optional<gate_t> event_root = std::nullopt);
83
84/**
85 * @brief Compute the central moment @f$E[(X - E[X])^k]@f$
86 * (or @f$E[(X - E[X \mid A])^k \mid A]@f$ if @p event_root is set).
87 *
88 * @c k = 0 returns 1; @c k = 1 returns 0; @c k = 2 returns the
89 * variance. Higher orders are obtained by binomial
90 * expansion in terms of the raw moments returned by
91 * @c compute_raw_moment, which inherits the analytical / MC dispatch
92 * described above.
93 */
94double compute_central_moment(const GenericCircuit &gc, gate_t root, unsigned k,
95 std::optional<gate_t> event_root = std::nullopt);
96
97/**
98 * @brief Compute the p-quantile @f$F^{-1}(p)@f$ of the scalar rooted at
99 * @p root (of the truncated distribution if @p event_root is set).
100 *
101 * Requires @f$p \in [0, 1]@f$ (the caller validates); @c p = 0 / 1
102 * return the (truncated) support edges. Analytic for a bare
103 * @c gate_rv -- the family's elementary inverse CDF where one exists,
104 * the generic monotone-CDF bisection (@c numericQuantile) otherwise --
105 * and exact for a categorical mixture; compound scalar circuits fall
106 * back to the empirical Monte Carlo quantile (linear interpolation,
107 * the @c percentile_cont convention) at the @c provsql.rv_mc_samples
108 * budget, with the same conditional-acceptance guards as the moment
109 * estimators.
110 */
111double compute_quantile(const GenericCircuit &gc, gate_t root, double p,
112 std::optional<gate_t> event_root = std::nullopt);
113
114/**
115 * @brief Probability that the Boolean subcircuit rooted at @p boolRoot
116 * evaluates to @c true under the tuple-independent
117 * probabilistic-database model.
118 *
119 * Tries @c BooleanCircuit::independentEvaluation first; if that throws
120 * (e.g. the subcircuit is not read-once), falls
121 * back to Monte Carlo with @c provsql.rv_mc_samples samples. Used by
122 * the mixture moment evaluators for compound Boolean Bernoulli wires.
123 */
124double evaluateBooleanProbability(const GenericCircuit &gc, gate_t boolRoot);
125
126/**
127 * @brief Normalise conditioning in a scalar sub-circuit before evaluation.
128 *
129 * Peels a conditioned ROOT to its bare target and rewrites every buried
130 * @c gate_conditioned into a transparent passthrough, folding all collected
131 * evidence (and any pre-existing @p event_opt) into a single conditioning
132 * event left in @p event_opt. Returns the (possibly new) root so a stored
133 * "X | C" reaching a low-level RV entry point evaluates as the bare scalar
134 * conditioned on the folded event -- keeping the closed-form path available.
135 * No-op (returns @p root, leaves @p event_opt untouched) when there is no
136 * conditioning.
137 */
139 std::optional<gate_t> &event_opt);
140
141} // namespace provsql
142
143#endif // PROVSQL_EXPECTATION_H
gate_t
Strongly-typed gate identifier.
Definition Circuit.h:53
Semiring-agnostic in-memory provenance circuit.
virtual char const * what() const noexcept
Return the error message as a C-string.
Definition Circuit.h:396
CircuitException(const std::string &m)
Construct with a descriptive error message.
Definition Circuit.h:390
NoValueException(const std::string &what)
Construct for the quantity what.
Definition Expectation.h:50
double compute_raw_moment(const GenericCircuit &gc, gate_t root, unsigned k, std::optional< gate_t > event_root)
Compute the raw moment (or if event_root is set) for k >= 0.
double compute_quantile(const GenericCircuit &gc, gate_t root, double p, std::optional< gate_t > event_root)
Compute the p-quantile of the scalar rooted at root (of the truncated distribution if event_root is ...
gate_t lift_conditioning(GenericCircuit &gc, gate_t root, std::optional< gate_t > &event_opt)
Lift conditioning out of a scalar arithmetic expression.
double compute_central_moment(const GenericCircuit &gc, gate_t root, unsigned k, std::optional< gate_t > event_root)
Compute the central moment (or if event_root is set).
double evaluateBooleanProbability(const GenericCircuit &gc, gate_t boolRoot)
Probability that the Boolean subcircuit rooted at boolRoot evaluates to true under the tuple-independ...
double compute_expectation(const GenericCircuit &gc, gate_t root, std::optional< gate_t > event_root)
Compute (or if event_root is set) over the scalar sub-circuit rooted at root.