ProvSQL C/C++ API
Adding support for provenance and uncertainty management to PostgreSQL databases
Loading...
Searching...
No Matches
CollapsedAggMoment.cpp
Go to the documentation of this file.
1/**
2 * @file CollapsedAggMoment.cpp
3 * @brief Rao-Blackwellised (collapsed) moments of a correlated COUNT / SUM,
4 * and the exact posterior of a latent conditioned on such a count.
5 *
6 * The recurring shape in latent-variable relational models is an aggregate
7 * over probabilistically-selected rows whose selection events are coupled by
8 * a small shared latent:
9 *
10 * C = COUNT/SUM over rows i of [ eps_i op g_i(b) ]
11 *
12 * where @c eps_i is a per-row independent random-variable leaf, @c b is a
13 * shared continuous latent that every row references, and @c g_i(b) is an
14 * expression in @c b (plus per-row constants). The exact moment path
15 * enumerates @c n^k row tuples and evaluates a joint probability for each --
16 * @c O(n^2) pair-probabilities for the variance, which does not scale.
17 *
18 * Conditional on @c b, the indicators are INDEPENDENT (the only coupling is
19 * through @c b), so this collapses to a 1-D quadrature over @c b: at each node
20 * the per-row success probability @c q_i(b) = Pr[eps_i op g_i(b)] is a
21 * closed-form CDF, and the count's conditional law is the elementary
22 * sum-of-independent-Bernoulli (Poisson-binomial) distribution. Cost
23 * @c O(G·n) (moments) / @c O(G·n^2) (pmf) -- milliseconds where the exact path
24 * took minutes -- and exact up to the quadrature (no sampling).
25 *
26 * The same collapse yields the EXACT posterior of a latent @c R conditioned on
27 * a discrete rv @c Y(R) equalling the count: @c P(C=j) is the collapsed pmf,
28 * and @c E[R^k|C] is a 1-D quadrature over @c R weighted by the likelihood
29 * @c L(r)=Σ_j P(C=j) pmf_Y(j;θ(r)) -- replacing a degenerating importance
30 * sampler with a closed quadrature.
31 *
32 * Scope (returns @c std::nullopt, i.e. "fall back", on any mismatch): a
33 * @c COUNT / @c SUM @c gate_agg whose per-row indicators reduce to
34 * @c "(constant Bernoullis) AND (one gate_cmp)", the cmp comparing a bare
35 * per-row @c gate_rv leaf against an expression over exactly ONE shared
36 * continuous latent leaf. Everything else declines.
37 */
38#include "CollapsedAggMoment.h"
39
40#include "CircuitFromMMap.h"
41#include "RandomVariable.h"
42#include "Aggregation.h" // AggregationOperator, ComparisonOperator
43#include "distributions/Distribution.h" // makeDistribution
44#include "Circuit.h"
45#include "provsql_utils_cpp.h" // uuid2string
46
47extern "C" {
48#include "postgres.h"
49#include "fmgr.h"
50#include "utils/uuid.h"
51#include "utils/array.h"
52#include "catalog/pg_type.h"
53#include "provsql_utils.h"
54#include "provsql_error.h"
55}
56
57#include <cmath>
58#include <functional>
59#include <map>
60#include <set>
61#include <vector>
62#include <limits>
63#include <memory>
64#include <optional>
65#include <unordered_map>
66#include <unordered_set>
67#include <vector>
68#include "provsql_interrupt.h"
69
70namespace provsql {
71
72namespace {
73
74constexpr double kNaN = std::numeric_limits<double>::quiet_NaN();
75constexpr int kGrid = 400; ///< quadrature nodes (shared latent and posterior)
76
77/// Collect the @c gate_rv leaves reachable from @p g (the RV footprint).
78void collectRvLeaves(const GenericCircuit &gc, gate_t g,
79 std::unordered_set<gate_t> &out)
80{
81 std::unordered_set<gate_t> seen;
82 std::vector<gate_t> stack{g};
83 while (!stack.empty()) {
84 gate_t x = stack.back(); stack.pop_back();
85 if (!seen.insert(x).second) continue;
86 if (gc.getGateType(x) == gate_rv) { out.insert(x); continue; }
87 for (gate_t c : gc.getWires(x)) stack.push_back(c);
88 }
89}
90
91/// Evaluate a deterministic scalar expression at @p bval, where the only
92/// random leaf allowed is @p var (set to @p bval). Returns NaN on any
93/// unexpected gate, which aborts the collapse. Used both for the shared-side
94/// link expression g_i(b) and for a latent leaf's parameter expression θ(r).
95double evalWithVar(const GenericCircuit &gc, gate_t g, gate_t var, double val)
96{
97 switch (gc.getGateType(g)) {
98 case gate_rv:
99 return (g == var) ? val : kNaN;
100 case gate_value:
101 try { return parseDoubleStrict(gc.getExtra(g)); }
102 catch (const CircuitException &) { return kNaN; }
103 case gate_arith: {
104 const auto op = static_cast<provsql_arith_op>(gc.getInfos(g).first);
105 const auto &w = gc.getWires(g);
106 auto ev = [&](gate_t c) { return evalWithVar(gc, c, var, val); };
107 switch (op) {
108 case PROVSQL_ARITH_PLUS: {
109 double s = 0.0; for (gate_t c : w) s += ev(c); return s;
110 }
111 case PROVSQL_ARITH_TIMES: {
112 double p = 1.0; for (gate_t c : w) p *= ev(c); return p;
113 }
115 return (w.size() == 2) ? ev(w[0]) - ev(w[1]) : kNaN;
116 // A zero divisor leaves the world without a value rather than an
117 // infinity, the answer every other evaluator gives it.
119 return (w.size() == 2 && ev(w[1]) != 0.0) ? ev(w[0]) / ev(w[1])
120 : kNaN;
122 return (w.size() == 2 && ev(w[1]) != 0.0)
123 ? std::trunc(ev(w[0]) / ev(w[1])) : kNaN;
125 return (w.size() == 1) ? -ev(w[0]) : kNaN;
126 default:
127 return kNaN;
128 }
129 }
130 default:
131 return kNaN;
132 }
133}
134
135/// Resolve @p g to an affine form `slope·var + intercept` over the same ops
136/// @c evalWithVar handles, or std::nullopt when it is not affine in @p var
137/// (a genuinely non-linear b-dependence, or an unsupported gate). A structural
138/// (not sampled) decomposition, so it never mis-classifies a non-linear link.
139/// In a shared-side link expression the only rv leaf present is @p var, so a
140/// @c gate_rv other than @p var cannot occur (it declines defensively anyway).
141std::optional<std::pair<double, double>>
142affineInVar(const GenericCircuit &gc, gate_t g, gate_t var)
143{
144 using R = std::optional<std::pair<double, double>>;
145 switch (gc.getGateType(g)) {
146 case gate_rv:
147 return (g == var) ? R({1.0, 0.0}) : std::nullopt;
148 case gate_value:
149 try { return R({0.0, parseDoubleStrict(gc.getExtra(g))}); }
150 catch (const CircuitException &) { return std::nullopt; }
151 case gate_arith: {
152 const auto op = static_cast<provsql_arith_op>(gc.getInfos(g).first);
153 const auto &w = gc.getWires(g);
154 switch (op) {
155 case PROVSQL_ARITH_PLUS: {
156 double s = 0.0, c = 0.0;
157 for (gate_t ch : w) {
158 auto a = affineInVar(gc, ch, var);
159 if (!a) return std::nullopt;
160 s += a->first; c += a->second;
161 }
162 return R({s, c});
163 }
164 case PROVSQL_ARITH_TIMES: {
165 double s = 0.0, c = 1.0; // running affine product (starts at 1)
166 for (gate_t ch : w) {
167 auto a = affineInVar(gc, ch, var);
168 if (!a) return std::nullopt;
169 // (s·x + c)·(a.s·x + a.c) is affine only if a factor is constant.
170 if (s != 0.0 && a->first != 0.0) return std::nullopt;
171 const double ns = s * a->second + c * a->first;
172 c = c * a->second;
173 s = ns;
174 }
175 return R({s, c});
176 }
177 case PROVSQL_ARITH_MINUS: {
178 if (w.size() != 2) return std::nullopt;
179 auto a = affineInVar(gc, w[0], var), b = affineInVar(gc, w[1], var);
180 if (!a || !b) return std::nullopt;
181 return R({a->first - b->first, a->second - b->second});
182 }
183 case PROVSQL_ARITH_NEG: {
184 if (w.size() != 1) return std::nullopt;
185 auto a = affineInVar(gc, w[0], var);
186 if (!a) return std::nullopt;
187 return R({-a->first, -a->second});
188 }
189 case PROVSQL_ARITH_DIV: {
190 if (w.size() != 2) return std::nullopt;
191 auto a = affineInVar(gc, w[0], var), b = affineInVar(gc, w[1], var);
192 if (!a || !b) return std::nullopt;
193 if (b->first != 0.0 || b->second == 0.0) return std::nullopt;
194 return R({a->first / b->second, a->second / b->second});
195 }
196 default:
197 return std::nullopt;
198 }
199 }
200 default:
201 return std::nullopt;
202 }
203}
204
205/// One recognised per-row term: q_i(b) = bern · Pr[eps_i op_i g_i(b)].
206struct Term {
207 const DistributionFamily *family; ///< eps_i family (for the CDF)
208 double p1, p2; ///< eps_i parameters
209 gate_t shared_side; ///< g_i(b) expression gate
210 ComparisonOperator op; ///< comparison, oriented "eps_i op g_i"
211 double bern; ///< product of the constant Bernoulli inputs
212 double value; ///< v_i (1 for COUNT; the summed value for SUM)
213
214 // Precomputed, b-invariant, so the O(G·n) grid loop touches no gate: the
215 // eps_i distribution is built once (its parameters are constant), and the
216 // shared-side link g_i(b) is resolved to an affine form slope·b + intercept
217 // whenever it is affine in the shared latent (the common alpha_i + b link),
218 // sparing the per-node evalWithVar walk and its std::map gate lookups.
219 std::shared_ptr<Distribution> dist; ///< family->factory(p1, p2), cached
220 bool affine = false; ///< g_i(b) = slope·b + intercept
221 double slope = 0.0, intercept = 0.0; ///< valid iff affine
222};
223
224/// The recognised collapse: the shared latent, its distribution and quadrature
225/// window, and the oriented per-row terms.
226struct CollapsePlan {
228 gate_t shared;
229 std::unique_ptr<Distribution> shared_dist;
230 double lo, hi;
231 std::vector<Term> terms;
232};
233
234/// Reduce an indicator k-gate to (Bernoulli product, the single gate_cmp).
235/// Returns false if it is not "(constant inputs) AND (one cmp)".
236bool reduceIndicator(const GenericCircuit &gc, gate_t k_gate,
237 double &bern, gate_t &cmp_out)
238{
239 bern = 1.0;
240 bool have_cmp = false;
241 std::vector<gate_t> stack{k_gate};
242 while (!stack.empty()) {
243 gate_t g = stack.back(); stack.pop_back();
244 switch (gc.getGateType(g)) {
245 case gate_times:
246 for (gate_t c : gc.getWires(g)) stack.push_back(c);
247 break;
248 case gate_one:
249 break;
250 case gate_input:
251 case gate_update: {
252 const double p = gc.getProb(g);
253 if (std::isnan(p)) return false;
254 bern *= p;
255 break;
256 }
257 case gate_cmp:
258 if (have_cmp) return false; // only a single comparison supported
259 cmp_out = g;
260 have_cmp = true;
261 break;
262 default:
263 return false;
264 }
265 }
266 return have_cmp;
267}
268
270{
271 switch (op) {
276 default: return op; // EQ / NE symmetric
277 }
278}
279
280/// Recognise the shared-latent COUNT / SUM shape at @p agg and build the plan.
281std::optional<CollapsePlan>
282buildCollapsePlan(const GenericCircuit &gc, gate_t agg)
283{
284 if (gc.getGateType(agg) != gate_agg) return std::nullopt;
285 const AggregationOperator aop = getAggregationOperator(gc.getInfos(agg).first);
287 return std::nullopt;
288
289 const auto &children = gc.getWires(agg);
290 if (children.empty()) return std::nullopt;
291
292 struct Raw {
293 double bern, value;
294 gate_t a, b;
296 };
297 std::vector<Raw> raws;
298 raws.reserve(children.size());
299 std::unordered_map<gate_t, unsigned> leaf_rows;
300
301 for (gate_t sm : children) {
302 if (gc.getGateType(sm) != gate_semimod) return std::nullopt;
303 const auto &smw = gc.getWires(sm);
304 if (smw.size() != 2) return std::nullopt;
305 if (gc.getGateType(smw[1]) != gate_value) return std::nullopt;
306 double value;
307 try { value = parseDoubleStrict(gc.getExtra(smw[1])); }
308 catch (const CircuitException &) { return std::nullopt; }
309
310 double bern;
311 gate_t cmp = static_cast<gate_t>(0);
312 if (!reduceIndicator(gc, smw[0], bern, cmp)) return std::nullopt;
313 const auto &cw = gc.getWires(cmp);
314 if (cw.size() != 2) return std::nullopt;
315 bool ok = false;
316 ComparisonOperator op = cmpOpFromOid(gc.getInfos(cmp).first, ok);
317 if (!ok) return std::nullopt;
318
319 raws.push_back({bern, value, cw[0], cw[1], op});
320
321 std::unordered_set<gate_t> rowleaves;
322 collectRvLeaves(gc, cmp, rowleaves);
323 for (gate_t l : rowleaves) ++leaf_rows[l];
324 }
325
326 gate_t shared = static_cast<gate_t>(0);
327 unsigned nb_shared = 0;
328 for (const auto &[leaf, rows] : leaf_rows)
329 if (rows > 1) { shared = leaf; ++nb_shared; }
330 if (nb_shared != 1) return std::nullopt;
331
332 auto shared_spec = parse_distribution_spec(gc.getExtra(shared));
333 if (!shared_spec) return std::nullopt;
334 auto shared_dist = makeDistribution(*shared_spec);
335 double lo, hi;
336 if (!shared_dist->integrationRange(lo, hi) || !(hi > lo)) return std::nullopt;
337
338 std::vector<Term> terms;
339 terms.reserve(raws.size());
340 for (const auto &r : raws) {
341 std::unordered_set<gate_t> fa, fb;
342 collectRvLeaves(gc, r.a, fa);
343 collectRvLeaves(gc, r.b, fb);
344
345 gate_t per_row = static_cast<gate_t>(0),
346 shared_side = static_cast<gate_t>(0);
347 ComparisonOperator op = r.op;
348 auto is_per_row = [&](gate_t side, const std::unordered_set<gate_t> &f) {
349 return gc.getGateType(side) == gate_rv && side != shared && f.size() == 1;
350 };
351 auto is_shared_side = [&](const std::unordered_set<gate_t> &f) {
352 return f.empty() || (f.size() == 1 && f.count(shared));
353 };
354 if (is_per_row(r.a, fa) && is_shared_side(fb)) {
355 per_row = r.a; shared_side = r.b;
356 } else if (is_per_row(r.b, fb) && is_shared_side(fa)) {
357 per_row = r.b; shared_side = r.a; op = flipOp(op);
358 } else {
359 return std::nullopt;
360 }
362 return std::nullopt;
363
364 auto spec = parse_distribution_spec(gc.getExtra(per_row));
365 if (!spec) return std::nullopt;
366 Term term{spec->family, spec->p1, spec->p2, shared_side, op,
367 r.bern, r.value};
368 term.dist = std::shared_ptr<Distribution>(
369 spec->family->factory(spec->p1, spec->p2));
370 if (auto aff = affineInVar(gc, shared_side, shared)) {
371 term.affine = true;
372 term.slope = aff->first;
373 term.intercept = aff->second;
374 }
375 terms.push_back(std::move(term));
376 }
377
378 CollapsePlan plan;
379 plan.aop = aop;
380 plan.shared = shared;
381 plan.shared_dist = std::move(shared_dist);
382 plan.lo = lo;
383 plan.hi = hi;
384 plan.terms = std::move(terms);
385 return plan;
386}
387
388/// The trapezoidal quadrature grid over a latent's distribution, weighted by
389/// its pdf and renormalised to unit mass (removing discretisation bias).
390struct Grid { std::vector<double> node, weight; };
391std::optional<Grid> pdfGrid(const Distribution &d, double lo, double hi)
392{
393 if (!(hi > lo)) return std::nullopt;
394 const double dx = (hi - lo) / (kGrid - 1);
395 Grid grid;
396 grid.node.resize(kGrid);
397 grid.weight.resize(kGrid);
398 double wsum = 0.0;
399 for (int gi = 0; gi < kGrid; ++gi) {
400 grid.node[gi] = lo + gi * dx;
401 double w = d.pdf(grid.node[gi]);
402 if (std::isnan(w) || w < 0.0) w = 0.0;
403 if (gi == 0 || gi == kGrid - 1) w *= 0.5;
404 grid.weight[gi] = w;
405 wsum += w;
406 }
407 if (!(wsum > 0.0)) return std::nullopt;
408 for (double &w : grid.weight) w /= wsum;
409 return grid;
410}
411
412/// Per-row success probabilities q_i(b) at a shared-latent value @p b.
413/// Returns false if any term's link expression / CDF is undefined.
414bool perNodeProbs(const GenericCircuit &gc, const CollapsePlan &plan,
415 double b, std::vector<double> &q)
416{
417 q.clear();
418 q.reserve(plan.terms.size());
419 for (const auto &t : plan.terms) {
420 // Affine links resolve with no gate access; the rest keep the walk.
421 const double c = t.affine ? std::fma(t.slope, b, t.intercept)
422 : evalWithVar(gc, t.shared_side, plan.shared, b);
423 if (std::isnan(c)) return false;
424 double F = t.dist->cdf(c);
425 if (std::isnan(F)) return false;
426 if (F < 0.0) F = 0.0; else if (F > 1.0) F = 1.0;
427 double qi;
428 switch (t.op) {
429 case ComparisonOperator::LT:
430 case ComparisonOperator::LE: qi = F; break;
431 case ComparisonOperator::GT:
432 case ComparisonOperator::GE: qi = 1.0 - F; break;
433 default: return false;
434 }
435 qi *= t.bern;
436 if (qi < 0.0) qi = 0.0; else if (qi > 1.0) qi = 1.0;
437 q.push_back(qi);
438 }
439 return true;
440}
441
442/// Poisson-binomial pmf of Σ Bernoulli(q_i) on {0, ..., q.size()}.
443std::vector<double> poissonBinomialPmf(const std::vector<double> &q)
444{
445 std::vector<double> pmf(q.size() + 1, 0.0);
446 pmf[0] = 1.0;
447 std::size_t filled = 0;
448 for (double qi : q) {
449 // Fold in Bernoulli(qi): pmf'[j] = pmf[j](1-qi) + pmf[j-1] qi, updated in
450 // place descending so each pmf[j-1] is still the pre-fold value.
451 for (std::size_t j = filled + 1; j >= 1; --j)
452 pmf[j] = pmf[j] * (1.0 - qi) + pmf[j - 1] * qi;
453 pmf[0] *= (1.0 - qi);
454 ++filled;
455 }
456 return pmf;
457}
458
459/// The count pmf P(C=j) via the collapse: 1-D quadrature over the shared
460/// latent of the conditional Poisson-binomial. COUNT only (unit per-row
461/// values), so the sum is a plain count.
462std::optional<std::vector<double>>
463aggCollapsedPmf(const GenericCircuit &gc, gate_t agg)
464{
465 auto plan = buildCollapsePlan(gc, agg);
466 if (!plan) return std::nullopt;
467 // A count is a COUNT agg, or equivalently a SUM whose per-row values are all
468 // 1 (the count-lift shape). Either way the per-tuple contribution is 1, so
469 // the Poisson-binomial pmf is the count distribution.
470 for (const auto &t : plan->terms)
471 if (t.value != 1.0) return std::nullopt;
472
473 auto grid = pdfGrid(*plan->shared_dist, plan->lo, plan->hi);
474 if (!grid) return std::nullopt;
475
476 const std::size_t n = plan->terms.size();
477 std::vector<double> pmf(n + 1, 0.0);
478 std::vector<double> q;
479 for (int gi = 0; gi < kGrid; ++gi) {
480 if (!perNodeProbs(gc, *plan, grid->node[gi], q)) return std::nullopt;
481 const std::vector<double> pb = poissonBinomialPmf(q);
482 const double w = grid->weight[gi];
483 for (std::size_t j = 0; j <= n; ++j) pmf[j] += w * pb[j];
484 }
485 return pmf;
486}
487
488} // namespace
489
490std::optional<std::pair<double, double>>
492{
493 auto plan = buildCollapsePlan(gc, agg);
494 if (!plan) return std::nullopt;
495
496 auto grid = pdfGrid(*plan->shared_dist, plan->lo, plan->hi);
497 if (!grid) return std::nullopt;
498
499 double m1 = 0.0, m2 = 0.0;
500 std::vector<double> q;
501 for (int gi = 0; gi < kGrid; ++gi) {
502 if (!perNodeProbs(gc, *plan, grid->node[gi], q)) return std::nullopt;
503 double mean_b = 0.0, var_b = 0.0; // E[C|b], Var[C|b] (independent given b)
504 for (std::size_t i = 0; i < plan->terms.size(); ++i) {
505 const double v = plan->terms[i].value, qi = q[i];
506 mean_b += v * qi;
507 var_b += v * v * qi * (1.0 - qi);
508 }
509 const double w = grid->weight[gi];
510 m1 += w * mean_b;
511 m2 += w * (var_b + mean_b * mean_b);
512 }
513 return std::make_pair(m1, m2);
514}
515
516std::optional<double>
517aggCollapsedRawMoment(const GenericCircuit &gc, gate_t agg, unsigned k)
518{
519 if (k == 0) return 1.0;
520 if (k > 2) return std::nullopt;
521 // Both moments share the whole load / plan / grid pass; variance() consumes
522 // them together through agg_collapsed_moments so a readout that needs E[C]
523 // and E[C^2] pays for one traversal, not two.
524 auto m = aggCollapsedRawMoments(gc, agg);
525 if (!m) return std::nullopt;
526 return (k == 1) ? m->first : m->second;
527}
528
529std::optional<double>
531 gate_t event, unsigned k)
532{
533 if (k == 0) return 1.0;
534 if (k > 2) return std::nullopt;
535 if (gc.getGateType(target) != gate_rv) return std::nullopt;
536 if (gc.getGateType(event) != gate_cmp) return std::nullopt;
537
538 bool ok = false;
539 const ComparisonOperator eop = cmpOpFromOid(gc.getInfos(event).first, ok);
540 if (!ok || eop != ComparisonOperator::EQ) return std::nullopt;
541 const auto &ew = gc.getWires(event);
542 if (ew.size() != 2) return std::nullopt;
543
544 // Identify the discrete rv Y(target) side and the count agg C side.
545 gate_t ygate = static_cast<gate_t>(0), cagg = static_cast<gate_t>(0);
546 for (int i = 0; i < 2; ++i) {
547 const gate_t s = ew[i], o = ew[1 - i];
548 if (gc.getGateType(s) == gate_rv && gc.getGateType(o) == gate_agg) {
549 ygate = s; cagg = o; break;
550 }
551 }
552 if (ygate == static_cast<gate_t>(0)) return std::nullopt;
553
554 // Y must be a discrete family whose parameter subtree references target.
555 auto ytmpl = parse_distribution_template(gc.getExtra(ygate));
556 if (!ytmpl) return std::nullopt;
557 if (!ytmpl->family->factory(1.0, 1.0)->isDiscrete()) return std::nullopt;
558 // Y's parameter subtrees are its wires; descend into them (collectRvLeaves
559 // stops at the gate_rv Y itself) to confirm the parameter references target.
560 std::unordered_set<gate_t> yfoot;
561 for (gate_t w : gc.getWires(ygate)) collectRvLeaves(gc, w, yfoot);
562 if (!yfoot.count(target)) return std::nullopt;
563
564 // The correlated count's pmf via the collapse.
565 auto Cpmf = aggCollapsedPmf(gc, cagg);
566 if (!Cpmf) return std::nullopt;
567
568 // R's prior and quadrature window.
569 auto rspec = parse_distribution_spec(gc.getExtra(target));
570 if (!rspec) return std::nullopt;
571 auto rdist = makeDistribution(*rspec);
572 double rlo, rhi;
573 if (!rdist->integrationRange(rlo, rhi)) return std::nullopt;
574 auto rgrid = pdfGrid(*rdist, rlo, rhi);
575 if (!rgrid) return std::nullopt;
576
577 const auto &ywires = gc.getWires(ygate);
578 auto resolveParam = [&](const DistributionParam &p, double r) -> double {
579 if (p.wire_slot < 0) return p.literal;
580 if (static_cast<std::size_t>(p.wire_slot) >= ywires.size()) return kNaN;
581 return evalWithVar(gc, ywires[p.wire_slot], target, r);
582 };
583
584 // Posterior quadrature over R: E[R^k|C] = ∫ r^k f_R L / ∫ f_R L,
585 // L(r) = Σ_j P(C=j) pmf_Y(j; θ(r)).
586 const std::size_t J = Cpmf->size();
587 double Z = 0.0, N1 = 0.0, N2 = 0.0;
588 for (int gi = 0; gi < kGrid; ++gi) {
589 const double r = rgrid->node[gi];
590 const double p1v = resolveParam(ytmpl->p1, r);
591 const double p2v = resolveParam(ytmpl->p2, r);
592 if (std::isnan(p1v)) return std::nullopt;
593 auto ydist = ytmpl->family->factory(p1v, std::isnan(p2v) ? 0.0 : p2v);
594 double L = 0.0;
595 bool degenerate = false;
596 for (std::size_t j = 0; j < J; ++j) {
597 const double pj = (*Cpmf)[j];
598 if (pj <= 0.0) continue;
599 const double pmfy = ydist->pdf(static_cast<double>(j));
600 if (std::isnan(pmfy)) { degenerate = true; break; }
601 L += pj * pmfy;
602 }
603 // A degenerate Y at this node (e.g. a boundary parameter such as
604 // Poisson(0) at R = 0) contributes nothing: such nodes sit at the
605 // prior's support edge, where f_R already vanishes, so skipping them
606 // leaves the quadrature exact.
607 if (degenerate) continue;
608 const double w = rgrid->weight[gi];
609 Z += w * L;
610 N1 += w * r * L;
611 N2 += w * r * r * L;
612 }
613 if (!(Z > 0.0)) return std::nullopt;
614 return (k == 1) ? (N1 / Z) : (N2 / Z);
615}
616
617} // namespace provsql
618
619extern "C" {
620
621PG_FUNCTION_INFO_V1(agg_collapsed_moment);
622
623/**
624 * @brief SQL: agg_collapsed_moment(token uuid, k integer) -> float8
625 *
626 * The collapsed raw moment @c E[C^k] of a correlated COUNT / SUM, or @c NULL
627 * when the circuit does not match the recognised shared-latent pattern (the
628 * caller then falls back to the exact enumeration). @c k in @c {1, 2}.
629 */
630Datum agg_collapsed_moment(PG_FUNCTION_ARGS)
631{
632 try {
633 provsql_interrupt_scope interrupt_scope;
634 pg_uuid_t *token = PG_GETARG_UUID_P(0);
635 const int32 k = PG_GETARG_INT32(1);
636 if (k < 0)
637 provsql_error("agg_collapsed_moment: k must be non-negative (got %d)", k);
638 auto gc = getGenericCircuit(*token);
639 gate_t root = gc.getGate(uuid2string(*token));
640 auto r = provsql::aggCollapsedRawMoment(gc, root,
641 static_cast<unsigned>(k));
642 if (!r.has_value())
643 PG_RETURN_NULL();
644 return Float8GetDatum(*r);
645 } catch (const std::exception &e) {
647 provsql_error("agg_collapsed_moment: %s", e.what());
648 } catch (...) {
650 provsql_error("agg_collapsed_moment: unknown exception");
651 }
652 PG_RETURN_NULL();
653}
654
655PG_FUNCTION_INFO_V1(agg_collapsed_moments);
656
657/**
658 * @brief SQL: agg_collapsed_moments(token uuid) -> float8[] {E[C], E[C^2]}
659 *
660 * Both collapsed raw moments from a single circuit load and plan build, or
661 * @c NULL when the shared-latent pattern does not match. @c variance() calls
662 * this so a mean+variance readout traverses the circuit once, not twice (the
663 * load and plan build dominate once the grid loop is arithmetic-only).
664 */
665Datum agg_collapsed_moments(PG_FUNCTION_ARGS)
666{
667 try {
668 provsql_interrupt_scope interrupt_scope;
669 pg_uuid_t *token = PG_GETARG_UUID_P(0);
670 auto gc = getGenericCircuit(*token);
671 gate_t root = gc.getGate(uuid2string(*token));
672 auto m = provsql::aggCollapsedRawMoments(gc, root);
673 if (!m.has_value())
674 PG_RETURN_NULL();
675 Datum elems[2] = { Float8GetDatum(m->first), Float8GetDatum(m->second) };
676 ArrayType *arr = construct_array(elems, 2, FLOAT8OID,
677 sizeof(float8), FLOAT8PASSBYVAL, 'd');
678 PG_RETURN_ARRAYTYPE_P(arr);
679 } catch (const std::exception &e) {
681 provsql_error("agg_collapsed_moments: %s", e.what());
682 } catch (...) {
684 provsql_error("agg_collapsed_moments: unknown exception");
685 }
686 PG_RETURN_NULL();
687}
688
689PG_FUNCTION_INFO_V1(agg_row_components);
690
691/**
692 * @brief SQL: agg_row_components(token uuid) -> integer[]
693 *
694 * For each contribution of the aggregate gate @p token, in the order of its
695 * children, the number of its independence component: two contributions
696 * share a component when their tokens reach a common source of randomness,
697 * directly or through others -- an input or update gate, a multivalued
698 * input (whose block key, its first wire, the other alternatives of the
699 * block reach too), or a random-variable leaf (with the parameters of a
700 * latent one). Contributions of different components are independent, so
701 * the probability of a conjunction of them is the product of theirs, which
702 * is what lets @c agg_raw_moment compute a variance from one probability
703 * per row instead of one per pair. @c NULL for a gate that is not an
704 * aggregation.
705 */
706Datum agg_row_components(PG_FUNCTION_ARGS)
707{
708 try {
709 provsql_interrupt_scope interrupt_scope;
710 pg_uuid_t *token = PG_GETARG_UUID_P(0);
711 auto gc = getGenericCircuit(*token);
712 gate_t root = gc.getGate(uuid2string(*token));
713 if (gc.getGateType(root) != gate_agg)
714 PG_RETURN_NULL();
715 const auto &rows = gc.getWires(root);
716 const size_t n = rows.size();
717
718 /* Union-find over the rows, joined through the sources they reach */
719 std::vector<size_t> parent(n);
720 for (size_t i = 0; i < n; ++i) parent[i] = i;
721 std::function<size_t(size_t)> find = [&](size_t x) {
722 while (parent[x] != x) { parent[x] = parent[parent[x]]; x = parent[x]; }
723 return x;
724 };
725 std::map<gate_t, size_t> owner; /* a source -> a row reaching it */
726 for (size_t i = 0; i < n; ++i) {
727 gate_t row = rows[i];
728 /* A semimod contribution: [token, value]; the value is a constant */
729 gate_t tok = (gc.getGateType(row) == gate_semimod &&
730 !gc.getWires(row).empty())
731 ? gc.getWires(row)[0] : row;
732 std::set<gate_t> seen;
733 std::vector<gate_t> stack{tok};
734 while (!stack.empty()) {
735 gate_t g = stack.back(); stack.pop_back();
736 if (!seen.insert(g).second) continue;
737 const auto t = gc.getGateType(g);
738 if (t == gate_input || t == gate_update || t == gate_mulinput ||
739 t == gate_rv) {
740 auto it = owner.find(g);
741 if (it == owner.end())
742 owner.emplace(g, i);
743 else
744 parent[find(i)] = find(it->second);
745 }
746 for (gate_t c : gc.getWires(g))
747 stack.push_back(c);
748 }
749 }
750
751 /* Components numbered from 1 in the order of their first row */
752 std::map<size_t, int32> number;
753 std::vector<Datum> elems(n);
754 for (size_t i = 0; i < n; ++i) {
755 size_t r = find(i);
756 auto it = number.find(r);
757 if (it == number.end())
758 it = number.emplace(r, static_cast<int32>(number.size() + 1)).first;
759 elems[i] = Int32GetDatum(it->second);
760 }
761 ArrayType *arr = construct_array(elems.data(), static_cast<int>(n),
762 INT4OID, sizeof(int32), true, 'i');
763 PG_RETURN_ARRAYTYPE_P(arr);
764 } catch (const std::exception &e) {
766 provsql_error("agg_row_components: %s", e.what());
767 } catch (...) {
769 provsql_error("agg_row_components: unknown exception");
770 }
771 PG_RETURN_NULL();
772}
773
774} // extern "C"
ComparisonOperator cmpOpFromOid(Oid op_oid, bool &ok)
Map a PostgreSQL comparison-operator OID to a ComparisonOperator.
AggregationOperator getAggregationOperator(Oid oid)
Map a PostgreSQL aggregate function OID to an AggregationOperator.
Typed aggregation value, operator, and aggregator abstractions.
AggregationOperator
SQL aggregation functions tracked by ProvSQL.
Definition Aggregation.h:52
@ COUNT
COUNT(*) or COUNT(expr) → integer.
Definition Aggregation.h:53
@ SUM
SUM → integer or float.
Definition Aggregation.h:54
ComparisonOperator
SQL comparison operators used in gate_cmp circuit gates.
Definition Aggregation.h:40
@ LT
Less than (<).
Definition Aggregation.h:44
@ GT
Greater than (>).
Definition Aggregation.h:46
@ LE
Less than or equal (<=).
Definition Aggregation.h:43
@ NE
Not equal (<>).
Definition Aggregation.h:42
@ GE
Greater than or equal (>=).
Definition Aggregation.h:45
GenericCircuit getGenericCircuit(pg_uuid_t token)
Build a GenericCircuit from the mmap store rooted at token.
Build in-memory circuits from the mmap-backed persistent store.
Generic directed-acyclic-graph circuit template and gate identifier.
gate_t
Strongly-typed gate identifier.
Definition Circuit.h:53
Datum agg_collapsed_moments(PG_FUNCTION_ARGS)
SQL: agg_collapsed_moments(token uuid) -> float8[] {E[C], E[C^2]}.
Datum agg_row_components(PG_FUNCTION_ARGS)
SQL: agg_row_components(token uuid) -> integer[].
Datum agg_collapsed_moment(PG_FUNCTION_ARGS)
SQL: agg_collapsed_moment(token uuid, k integer) -> float8.
Rao-Blackwellised (collapsed) evaluation of a correlated COUNT / SUM and of a latent conditioned on s...
Per-family polymorphic view over a continuous gate_rv distribution (§F.1 class hierarchy).
Continuous random-variable helpers (distribution parsing, moments).
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
gate_t getGate(const uuid &u)
Return (or create) the gate associated with UUID u.
Definition Circuit.hpp:50
std::string getExtra(gate_t g) const
Return the string extra for gate g.
double getProb(gate_t g) const
Return the probability for gate g.
std::pair< unsigned, unsigned > getInfos(gate_t g) const
Return the integer annotation pair for gate g.
Abstract per-family continuous distribution.
The SIGINT handler installed for the lifetime of the object, the previous one restored as it ends (a ...
std::optional< double > aggCollapsedRawMoment(const GenericCircuit &gc, gate_t agg, unsigned k)
Collapsed raw moment E[C^k] of a correlated COUNT / SUM agg, or std::nullopt when the circuit does no...
double parseDoubleStrict(const std::string &s)
Strictly parse s as a double.
std::optional< std::pair< double, double > > aggCollapsedRawMoments(const GenericCircuit &gc, gate_t agg)
std::unique_ptr< Distribution > makeDistribution(const DistributionSpec &spec)
Construct the per-family Distribution for a parsed spec.
std::optional< double > collapsedConditionalMoment(const GenericCircuit &gc, gate_t target, gate_t event, unsigned k)
Collapsed exact posterior raw moment E[R^k | Y = C] for a latent target R conditioned (through the eq...
std::optional< DistributionSpec > parse_distribution_spec(const std::string &s)
Parse the on-disk text encoding of a gate_rv distribution.
std::optional< DistributionTemplate > parse_distribution_template(const std::string &s)
Parse the on-disk text encoding of a gate_rv distribution, keeping wired (token) parameters as wire r...
constexpr double kNaN
Uniform error-reporting macros for ProvSQL.
#define provsql_error(fmt,...)
Report a fatal ProvSQL error and abort the current transaction.
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_op
Arithmetic operator tags used by gate_arith.
@ PROVSQL_ARITH_DIV
binary, child0 / child1
@ PROVSQL_ARITH_PLUS
n-ary, sum of children
@ PROVSQL_ARITH_NEG
unary, -child0
@ PROVSQL_ARITH_INTDIV
binary, child0 / child1 truncated toward zero: SQL's division of two integers
@ PROVSQL_ARITH_MINUS
binary, child0 - child1
@ 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)
string uuid2string(pg_uuid_t uuid)
Format a pg_uuid_t as a std::string.
C++ utility functions for UUID manipulation.
One parameter slot of a gate_rv, either a literal or a wire.
double literal
Value when wire_slot < 0.
int wire_slot
>= 0: resolve from the gate's wires[wire_slot].