ProvSQL C/C++ API
Adding support for provenance and uncertainty management to PostgreSQL databases
Loading...
Searching...
No Matches
RvCovariance.cpp
Go to the documentation of this file.
1/**
2 * @file RvCovariance.cpp
3 * @brief Single-pass covariance / correlation readouts over RV circuits.
4 *
5 * Backs the SQL @c covariance(x, y[, prov]) and @c correlation(x, y[, prov])
6 * readouts. The definitional decomposition
7 * @f$Cov(X, Y) = E[XY] - E[X]\,E[Y]@f$ is kept for the exact cases (every
8 * factor decomposes analytically, so the subtraction is closed-form), but
9 * the Monte Carlo fallback deliberately does NOT go through it: estimating
10 * @c E[XY] and the two means from three independent sampling passes and
11 * subtracting puts the estimator's noise on the scale of
12 * @f$E[X]\,E[Y]@f$ -- the product of the means -- rather than of the
13 * covariance itself, a catastrophic cancellation when the means dominate
14 * the coupling. Instead a single coupled pass draws @f$(x_i, y_i)@f$ pairs
15 * from the joint circuit (shared stochastic leaves produce one draw per
16 * iteration that both roots observe) and returns the plain sample
17 * covariance @f$\tfrac1n \sum (x_i - \bar x)(y_i - \bar y)@f$, whose noise
18 * scales with @f$\sqrt{(\sigma_X^2 \sigma_Y^2 + Cov^2)/n}@f$.
19 *
20 * @c correlation reads @f$Cov@f$, @f$\sigma_X@f$ and @f$\sigma_Y@f$ off the
21 * SAME pass, instead of stacking five independent MC estimates.
22 */
23#include "CircuitFromMMap.h"
24#include "Expectation.h"
25#include "MonteCarloSampler.h"
26#include "provsql_utils_cpp.h"
27
28extern "C" {
29#include "postgres.h"
30#include "fmgr.h"
31#include "utils/uuid.h"
32#include "provsql_utils.h"
33#include "provsql_error.h"
34
35PG_FUNCTION_INFO_V1(rv_covariance);
36PG_FUNCTION_INFO_V1(rv_correlation);
37}
38
39#include <cmath>
40#include <limits>
41#include <optional>
42#include <set>
43#include <string>
44#include <vector>
45#include "provsql_interrupt.h"
46
47namespace provsql {
48
49namespace {
50
51/* Stochastic leaves reachable from g, as in InformationTheory.cpp's
52 * structural-independence shortcut: gate_value constants are shared by
53 * v5-keying and carry no randomness, so they are not collected. */
54void collectStochasticLeaves(const GenericCircuit &gc, gate_t g,
55 std::set<gate_t> &out, std::set<gate_t> &seen)
56{
57 if (!seen.insert(g).second) return;
58 const auto t = gc.getGateType(g);
59 if (t == gate_rv || t == gate_input || t == gate_mulinput)
60 out.insert(g);
61 for (gate_t c : gc.getWires(g))
62 collectStochasticLeaves(gc, c, out, seen);
63}
64
65std::set<gate_t> stochasticLeaves(const GenericCircuit &gc, gate_t g)
66{
67 std::set<gate_t> out, seen;
68 collectStochasticLeaves(gc, g, out, seen);
69 return out;
70}
71
72bool disjointFrom(const std::set<gate_t> &a, const std::set<gate_t> &b)
73{
74 for (gate_t l : a)
75 if (b.count(l)) return false;
76 return true;
77}
78
79/* Scoped MC-fallback disable for the analytic attempt: with
80 * provsql.rv_mc_samples forced to 0 every evaluator below throws instead
81 * of sampling, so "no CircuitException" == "the result is closed-form". */
82struct McDisabledGuard {
83 int saved;
84 McDisabledGuard() : saved(provsql_rv_mc_samples) { provsql_rv_mc_samples = 0; }
85 ~McDisabledGuard() { provsql_rv_mc_samples = saved; }
86};
87
88/* In-memory product gate over the two roots, for the exact
89 * E[XY] - E[X]E[Y] path. The persistent store is never mutated. */
90gate_t makeProductGate(GenericCircuit &gc, gate_t a, gate_t b)
91{
93 auto &w = gc.getWires(g);
94 w.push_back(a);
95 w.push_back(b);
97 return g;
98}
99
100/* Mirrors Expectation.cpp's mc_samples_or_throw: throw when the GUC
101 * disables the fallback, emit the approximation-transparency NOTICE at
102 * the same verbosity tier otherwise. */
103unsigned mc_samples_or_throw(const std::string &what)
104{
105 const int n = provsql_rv_mc_samples;
106 if (n <= 0) {
107 throw CircuitException(
108 what + " could not be decomposed analytically and "
109 "provsql.rv_mc_samples = 0 disables the Monte Carlo fallback");
110 }
111 if (provsql_verbose >= 5)
113 "%s: no closed form found; estimating by Monte Carlo over %d samples "
114 "(an approximation, not an exact moment) -- set provsql.rv_mc_samples = 0 "
115 "to require an exact result instead", what.c_str(), n);
116 return static_cast<unsigned>(n);
117}
118
119/* Acceptance guard for the conditional pass, mirroring Expectation.cpp's
120 * check_acceptance_or_throw (0-of-N = infeasible event, otherwise a
121 * max(attempted/1000, 5) floor against enormous-variance estimates). */
122void check_acceptance_or_throw(std::size_t accepted, unsigned attempted,
123 const std::string &what)
124{
125 if (accepted == 0) {
126 throw CircuitException(
127 what + ": conditioning event is infeasible (0 of " +
128 std::to_string(attempted) + " Monte Carlo samples satisfied it)");
129 }
130 unsigned floor = attempted / 1000;
131 if (floor < 5) floor = 5;
132 if (accepted < floor) {
133 throw CircuitException(
134 what + ": conditional MC accepted only " + std::to_string(accepted) +
135 " out of " + std::to_string(attempted) +
136 " samples (need >= " + std::to_string(floor) +
137 "); raise provsql.rv_mc_samples or tighten the event.");
138 }
139}
140
141/* Sample covariance and the two sample variances from one coupled pass.
142 * Population (1/n) normalisation, matching the central-moment MC
143 * convention in Expectation.cpp. Pairs with a member that has no value
144 * (e.g. an empty-group aggregate) are excluded; with none left, the
145 * statistics have no value (NoValueException). */
146struct CovStats {
147 double cov;
148 double var_x;
149 double var_y;
150};
151
152CovStats mcCovStats(const GenericCircuit &gc, gate_t x, gate_t y,
153 std::optional<gate_t> event, const std::string &what)
154{
155 const unsigned n = mc_samples_or_throw(what);
156
157 std::vector<std::optional<double>> xs, ys;
158 if (event) {
159 auto cs = monteCarloConditionalScalarPairSamples(gc, x, y, *event, n);
160 check_acceptance_or_throw(cs.xs.size(), cs.attempted, what);
161 xs = std::move(cs.xs);
162 ys = std::move(cs.ys);
163 } else {
164 std::tie(xs, ys) = monteCarloScalarPairSamples(gc, x, y, n);
165 }
166
167 double sum_x = 0.0, sum_y = 0.0;
168 std::size_t m = 0;
169 /* A draw where either has no value is a missing observation of the pair;
170 * a NaN (in the data) is a value and propagates. */
171 for (std::size_t i = 0; i < xs.size(); ++i) {
172 if (!xs[i] || !ys[i]) continue;
173 sum_x += *xs[i];
174 sum_y += *ys[i];
175 ++m;
176 }
177 if (m == 0)
178 throw NoValueException(what);
179 const double mean_x = sum_x / static_cast<double>(m);
180 const double mean_y = sum_y / static_cast<double>(m);
181
182 double cov = 0.0, var_x = 0.0, var_y = 0.0;
183 for (std::size_t i = 0; i < xs.size(); ++i) {
184 if (!xs[i] || !ys[i]) continue;
185 const double dx = *xs[i] - mean_x;
186 const double dy = *ys[i] - mean_y;
187 cov += dx * dy;
188 var_x += dx * dx;
189 var_y += dy * dy;
190 }
191 const double dm = static_cast<double>(m);
192 return {cov / dm, var_x / dm, var_y / dm};
193}
194
195/* Exact E[XY] - E[X]E[Y] (and, when @p need_vars, the two variances),
196 * attempted with the MC fallback disabled: std::nullopt means some factor
197 * has no closed form and the caller should take the single coupled pass
198 * instead of stacking independent estimates. */
199std::optional<CovStats> tryAnalyticCovStats(GenericCircuit &gc, gate_t x,
200 gate_t y,
201 std::optional<gate_t> event,
202 bool need_vars)
203{
204 McDisabledGuard guard;
205 try {
206 CovStats s{0.0, 0.0, 0.0};
207 const double ex = compute_expectation(gc, x, event);
208 const double ey = compute_expectation(gc, y, event);
209 const gate_t prod = makeProductGate(gc, x, y);
210 const double exy = compute_expectation(gc, prod, event);
211 s.cov = exy - ex * ey;
212 if (need_vars) {
213 s.var_x = compute_central_moment(gc, x, 2, event);
214 s.var_y = compute_central_moment(gc, y, 2, event);
215 }
216 return s;
217 } catch (const CircuitException &) {
218 return std::nullopt;
219 }
220}
221
222} // namespace
223
224/**
225 * @brief @f$Cov(X, Y)@f$ (or @f$Cov(X, Y \mid E)@f$) over a joint circuit.
226 *
227 * Exact tiers first: a variance readout when the two roots coincide, an
228 * exact @c 0 when the roots' stochastic-leaf footprints are structurally
229 * independent (given the event), and the closed-form
230 * @f$E[XY] - E[X]\,E[Y]@f$ when every factor decomposes analytically.
231 * Otherwise one coupled Monte Carlo pass at the @c provsql.rv_mc_samples
232 * budget.
233 */
235 std::optional<gate_t> event)
236{
237 x = lift_conditioning(gc, x, event);
238 y = lift_conditioning(gc, y, event);
239
240 /* Cov(X, X) = Var(X): route to the central-moment evaluator (closed
241 * form where the variance has one; single-root MC otherwise) instead
242 * of a product gate over a shared root, which never decomposes. */
243 if (x == y)
244 return compute_central_moment(gc, x, 2, event);
245
246 /* Structural independence: X independent of (Y, E) -- or symmetrically
247 * Y of (X, E) -- gives Cov(X, Y | E) = 0 exactly, whatever the
248 * factors' moments look like. */
249 {
250 auto lx = stochasticLeaves(gc, x);
251 auto ly = stochasticLeaves(gc, y);
252 std::set<gate_t> le;
253 if (event) le = stochasticLeaves(gc, *event);
254 const bool x_indep = disjointFrom(lx, ly) && disjointFrom(lx, le);
255 const bool y_indep = disjointFrom(ly, lx) && disjointFrom(ly, le);
256 if (x_indep || y_indep)
257 return 0.0;
258 }
259
260 if (auto s = tryAnalyticCovStats(gc, x, y, event, false))
261 return s->cov;
262
263 return mcCovStats(gc, x, y, event, "covariance").cov;
264}
265
266/**
267 * @brief Pearson @f$\rho(X, Y) = Cov(X, Y) / (\sigma_X \sigma_Y)@f$
268 * (conditioned on @p event when set).
269 *
270 * Same exact tiers as @c computeCovariance; on the Monte Carlo path the
271 * covariance and BOTH standard deviations are read off one coupled pass.
272 * @c std::nullopt when either variance is @c 0 (or the statistics are
273 * undefined): correlation with a degenerate variable has no value, and
274 * the SQL binding maps this to @c NULL.
275 */
276std::optional<double> computeCorrelation(GenericCircuit &gc, gate_t x,
277 gate_t y,
278 std::optional<gate_t> event)
279{
280 x = lift_conditioning(gc, x, event);
281 y = lift_conditioning(gc, y, event);
282
283 if (x == y) {
284 const double var = compute_central_moment(gc, x, 2, event);
285 if (std::isnan(var) || var <= 0.0) return std::nullopt;
286 return 1.0;
287 }
288
289 {
290 auto lx = stochasticLeaves(gc, x);
291 auto ly = stochasticLeaves(gc, y);
292 std::set<gate_t> le;
293 if (event) le = stochasticLeaves(gc, *event);
294 const bool x_indep = disjointFrom(lx, ly) && disjointFrom(lx, le);
295 const bool y_indep = disjointFrom(ly, lx) && disjointFrom(ly, le);
296 if (x_indep || y_indep) {
297 const double var_x = compute_central_moment(gc, x, 2, event);
298 const double var_y = compute_central_moment(gc, y, 2, event);
299 if (std::isnan(var_x) || std::isnan(var_y) ||
300 var_x <= 0.0 || var_y <= 0.0)
301 return std::nullopt;
302 return 0.0;
303 }
304 }
305
306 CovStats s{};
307 if (auto exact = tryAnalyticCovStats(gc, x, y, event, true))
308 s = *exact;
309 else
310 s = mcCovStats(gc, x, y, event, "correlation");
311
312 if (std::isnan(s.var_x) || std::isnan(s.var_y) ||
313 s.var_x <= 0.0 || s.var_y <= 0.0)
314 return std::nullopt;
315 return s.cov / std::sqrt(s.var_x * s.var_y);
316}
317
318} // namespace provsql
319
320/* ------------------------------------------------------------------
321 * SQL-callable entry points, mirroring rv_moment's plumbing.
322 * ------------------------------------------------------------------ */
323
324/**
325 * @brief SQL: rv_covariance(x uuid, y uuid, prov uuid) -> float8
326 */
327Datum rv_covariance(PG_FUNCTION_ARGS)
328{
329 try {
330 provsql_interrupt_scope interrupt_scope;
331 pg_uuid_t *x = PG_GETARG_UUID_P(0);
332 pg_uuid_t *y = PG_GETARG_UUID_P(1);
333 pg_uuid_t *prov = PG_GETARG_UUID_P(2);
334
335 std::vector<gate_t> gates;
336 auto gc = getJointCircuit({*x, *y, *prov}, gates);
337
338 /* gate_one event = unconditional after load-time simplification. */
339 std::optional<gate_t> event_opt;
340 if (gc.getGateType(gates[2]) != gate_one)
341 event_opt = gates[2];
342
343 return Float8GetDatum(
344 provsql::computeCovariance(gc, gates[0], gates[1], event_opt));
345 } catch (const provsql::NoValueException &) {
346 /* Defined in no world: SQL's NULL. */
348 PG_RETURN_NULL();
349 } catch (const std::exception &e) {
351 provsql_error("rv_covariance: %s", e.what());
352 } catch (...) {
354 provsql_error("rv_covariance: unknown exception");
355 }
356 PG_RETURN_NULL();
357}
358
359/**
360 * @brief SQL: rv_correlation(x uuid, y uuid, prov uuid) -> float8
361 *
362 * Returns SQL @c NULL for a degenerate (zero-variance) argument, matching
363 * the @c NULLIF convention of the former SQL-level definition.
364 */
365Datum rv_correlation(PG_FUNCTION_ARGS)
366{
367 try {
368 provsql_interrupt_scope interrupt_scope;
369 pg_uuid_t *x = PG_GETARG_UUID_P(0);
370 pg_uuid_t *y = PG_GETARG_UUID_P(1);
371 pg_uuid_t *prov = PG_GETARG_UUID_P(2);
372
373 std::vector<gate_t> gates;
374 auto gc = getJointCircuit({*x, *y, *prov}, gates);
375
376 std::optional<gate_t> event_opt;
377 if (gc.getGateType(gates[2]) != gate_one)
378 event_opt = gates[2];
379
380 auto rho =
381 provsql::computeCorrelation(gc, gates[0], gates[1], event_opt);
382 if (!rho)
383 PG_RETURN_NULL();
384 return Float8GetDatum(*rho);
385 } catch (const provsql::NoValueException &) {
386 /* Defined in no world: SQL's NULL. */
388 PG_RETURN_NULL();
389 } catch (const std::exception &e) {
391 provsql_error("rv_correlation: %s", e.what());
392 } catch (...) {
394 provsql_error("rv_correlation: unknown exception");
395 }
396 PG_RETURN_NULL();
397}
GenericCircuit getJointCircuit(const std::vector< pg_uuid_t > &tokens, std::vector< gate_t > &gates)
Multi-root variant of getJointCircuit.
Build in-memory circuits from the mmap-backed persistent store.
gate_t
Strongly-typed gate identifier.
Definition Circuit.h:53
Analytical expectation / variance / moment evaluator over RV circuits.
Monte Carlo sampling over a GenericCircuit, RV-aware.
Datum rv_covariance(PG_FUNCTION_ARGS)
SQL: rv_covariance(x uuid, y uuid, prov uuid) -> float8.
Datum rv_correlation(PG_FUNCTION_ARGS)
SQL: rv_correlation(x uuid, y uuid, prov uuid) -> float8.
std::vector< gate_t > & getWires(gate_t g)
Return a mutable reference to the child-wire list of gate g.
Definition Circuit.h:311
gateType getGateType(gate_t g) const
Return the type of gate g.
Definition Circuit.h:301
void setInfos(gate_t g, unsigned info1, unsigned info2)
Set the integer annotation pair for gate g.
gate_t setGate(gate_type type) override
Allocate a new gate with type type and no UUID.
The quantity asked for has a value in no world (an aggregate over a group empty in every world of pos...
Definition Expectation.h:47
The SIGINT handler installed for the lifetime of the object, the previous one restored as it ends (a ...
gate_t lift_conditioning(GenericCircuit &gc, gate_t root, std::optional< gate_t > &event_opt)
Lift conditioning out of a scalar arithmetic expression.
double computeCovariance(GenericCircuit &gc, gate_t x, gate_t y, std::optional< gate_t > event)
(or ) over a joint circuit.
std::pair< std::vector< std::optional< double > >, std::vector< std::optional< double > > > monteCarloScalarPairSamples(const GenericCircuit &gc, gate_t root_a, gate_t root_b, unsigned samples)
Coupled per-iteration draws of two scalar roots.
std::optional< double > computeCorrelation(GenericCircuit &gc, gate_t x, gate_t y, std::optional< gate_t > event)
Pearson (conditioned on event when set).
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).
ConditionalScalarPairSamples monteCarloConditionalScalarPairSamples(const GenericCircuit &gc, gate_t root_a, gate_t root_b, gate_t event_root, unsigned samples)
Rejection-sample the PAIR (root_a, root_b) conditioned on event_root.
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.
int provsql_verbose
Verbosity level; controlled by the provsql.verbose_level GUC.
Definition provsql.c:115
int provsql_rv_mc_samples
Default sample count for analytical-evaluator MC fallbacks; 0 disables fallback (callers raise instea...
Definition provsql.c:126
Uniform error-reporting macros for ProvSQL.
#define provsql_error(fmt,...)
Report a fatal ProvSQL error and abort the current transaction.
#define provsql_notice(fmt,...)
Emit a ProvSQL informational notice (execution continues).
void provsql_cancel_if_interrupted(void)
Raise PG's cancel if the evaluation stopped for one; nothing otherwise.
Cancellation of the long C++ evaluation loops.
Core types, constants, and utilities shared across ProvSQL.
@ PROVSQL_ARITH_TIMES
n-ary, product of children
@ gate_rv
Continuous random-variable leaf (extra encodes distribution).
@ gate_arith
n-ary arithmetic gate over scalar-valued children (info1 holds operator tag)
C++ utility functions for UUID manipulation.