ProvSQL C/C++ API
Adding support for provenance and uncertainty management to PostgreSQL databases
Loading...
Searching...
No Matches
MonteCarloSampler.cpp
Go to the documentation of this file.
1/**
2 * @file MonteCarloSampler.cpp
3 * @brief Implementation of the RV-aware Monte Carlo sampler.
4 */
5#include "MonteCarloSampler.h"
6#include "Aggregation.h"
7#include "RandomVariable.h"
8#include "distributions/Distribution.h" // makeDistribution -> per-family sample()
9#include "RangeCheck.h" // collectRvConstraints
10#include "Circuit.hpp" // Circuit<>::getUUID, used on the circuit
11#include "provsql_interrupt.h" // provsql_poll_interrupt
12
13#include <algorithm>
14#include <cmath>
15#include <cstdint>
16#include <limits>
17#include <memory>
18#include <optional>
19#include <random>
20#include <stack>
21#include <stdexcept>
22#include <string>
23#include <unordered_map>
24#include <unordered_set>
25#include <variant>
26#include <vector>
27
28namespace provsql {
29
30std::mt19937_64 seedRng()
31{
32 std::mt19937_64 rng;
33 if(provsql_monte_carlo_seed != -1) {
34 rng.seed(static_cast<uint64_t>(provsql_monte_carlo_seed));
35 } else {
36 std::random_device rd;
37 rng.seed((static_cast<uint64_t>(rd()) << 32) | rd());
38 }
39 return rng;
40}
41
42namespace {
43
44/** @brief A comparison in this world: not true where a side has no value
45 * (SQL's NULL), and in PostgreSQL's order of floats (NaN equal to NaN and
46 * above every number) where both have one. */
47bool applyCmp(std::optional<double> lo, ComparisonOperator op,
48 std::optional<double> ro)
49{
50 if(!lo || !ro) return false;
51 const double l = *lo, r = *ro;
52 const bool lt = sql_less(l, r), gt = sql_less(r, l);
53 switch(op) {
54 case ComparisonOperator::LT: return lt;
55 case ComparisonOperator::LE: return !gt;
56 case ComparisonOperator::EQ: return !lt && !gt;
57 case ComparisonOperator::NE: return lt || gt;
58 case ComparisonOperator::GE: return !lt;
59 case ComparisonOperator::GT: return gt;
60 }
61 return false;
62}
63
64/// Recognise a point observation @c "Y = c": a @c gate_cmp with the @c EQ
65/// operator, one wire a bare @c gate_rv leaf @p leaf_out, the other a
66/// constant @c gate_value @p datum_out. This is the internal form of
67/// @c observe(Y, c) -- the conditioning-evidence interpretation of the
68/// equality, a likelihood weight by the leaf's density/mass at @c c (a
69/// continuous point event is measure-zero as a rejection interval, so this
70/// is the only meaningful reading of it as evidence). Returns @c false for
71/// an inequality, a non-leaf scalar, or a non-constant right side (those
72/// stay ordinary Boolean events).
73bool matchPointObservationCmp(const GenericCircuit &gc, gate_t g,
74 gate_t &leaf_out, double &datum_out)
75{
76 if(gc.getGateType(g) != gate_cmp) return false;
77 const auto &wires = gc.getWires(g);
78 if(wires.size() != 2) return false;
79 bool ok = false;
80 ComparisonOperator op = cmpOpFromOid(gc.getInfos(g).first, ok);
81 if(!ok || op != ComparisonOperator::EQ) return false;
82 auto try_side = [&](gate_t rv_side, gate_t const_side) {
83 if(gc.getGateType(rv_side) != gate_rv) return false;
84 if(gc.getGateType(const_side) != gate_value) return false;
85 try { datum_out = parseDoubleStrict(gc.getExtra(const_side)); }
86 catch(const CircuitException &) { return false; }
87 leaf_out = rv_side;
88 return true;
89 };
90 return try_side(wires[0], wires[1]) || try_side(wires[1], wires[0]);
91}
92
93/// Per-iteration sampler state shared between the Boolean and scalar
94/// recursions.
95class Sampler {
96public:
97 Sampler(const GenericCircuit &gc, std::mt19937_64 &rng)
98 : gc_(gc), rng_(rng), bool_stamp_(gc.getNbGates(), 0),
99 bool_value_(gc.getNbGates(), 0) {}
100
101 /// Reset per-iteration memo caches.
102 void resetIteration() {
103 scalar_cache_.clear();
104 // The Boolean memo and the equation systems' solutions are stamped with
105 // the iteration: a new one invalidates them all, without clearing or
106 // reallocating per world. On the (rare) wrap of the counter, reset the
107 // stamps.
108 if(++iteration_ == 0) {
109 std::fill(bool_stamp_.begin(), bool_stamp_.end(), 0);
110 for(auto &kv : fix_state_) {
111 std::fill(kv.second.reached.begin(), kv.second.reached.end(), 0);
112 kv.second.solved = 0;
113 }
114 iteration_ = 1;
115 }
116 }
117
118 bool evalBool(gate_t g);
119 /// The value of @p g in this world; empty where it has none (an
120 /// aggregate over no row, a NULL, a division by zero) -- a NaN is a
121 /// value, the one a float can hold.
122 std::optional<double> evalScalar(gate_t g);
123 double evalWeight(gate_t g);
124
125 /// Read the inputs from @p world instead of drawing them (enumeration
126 /// of the possible worlds); @c nullptr draws them again.
127 void fixInputs(const std::unordered_map<gate_t, bool> *world) {
128 fixed_ = world;
129 }
130
131private:
132 /// Build the per-draw Distribution for a (possibly latent) gate_rv leaf,
133 /// resolving wired parameters through evalScalar (so a shared latent
134 /// lands in scalar_cache_ and couples the callers), with the
135 /// parameter-domain guard. Outputs the resolved parameters in p1/p2.
136 std::unique_ptr<Distribution> buildRvDistribution(
137 gate_t leaf, const DistributionTemplate &tmpl, double &p1, double &p2);
138
139 const GenericCircuit &gc_;
140 std::mt19937_64 &rng_;
141 // Truth of each gate in this world, indexed by gate: valid where its stamp
142 // is the current iteration (see resetIteration), so that a world costs no
143 // hash-node allocation per gate.
144 unsigned iteration_ = 1;
145 std::vector<unsigned> bool_stamp_;
146 std::vector<char> bool_value_;
147 const char *boolMemo(gate_t g) const {
148 const auto i = static_cast<std::size_t>(g);
149 return i < bool_stamp_.size() && bool_stamp_[i] == iteration_
150 ? &bool_value_[i] : nullptr;
151 }
152 void setBoolMemo(gate_t g, bool v) {
153 const auto i = static_cast<std::size_t>(g);
154 if(i >= bool_stamp_.size()) {
155 bool_stamp_.resize(i + 1, 0);
156 bool_value_.resize(i + 1, 0);
157 }
158 bool_stamp_[i] = iteration_;
159 bool_value_[i] = v;
160 }
161 std::unordered_map<gate_t, std::optional<double>> scalar_cache_;
162 const std::unordered_map<gate_t, bool> *fixed_ = nullptr;
163 // Per-gate_rv Distribution, constructed once and reused across iterations
164 // (NOT cleared in resetIteration): sampling then never re-parses the spec
165 // or re-constructs the Distribution per draw.
166 std::unordered_map<gate_t, std::unique_ptr<Distribution>> dist_cache_;
167
168 /// An equation system met: its linear forms, read once, and the part of
169 /// its least solution explored in the current world, shared by all the
170 /// rows of the system (unknown @c i is known to hold where
171 /// <tt>reached[i] == solved</tt>, the iteration it was explored in; the
172 /// exploration resumes from @c queue at @c next). Kept across
173 /// iterations, buffers included.
174 struct FixState {
175 FixSystemLinear lin;
176 std::vector<std::size_t> seeds; ///< Unknowns with a constant part
177 std::vector<unsigned> reached;
178 std::vector<std::size_t> queue;
179 std::size_t next = 0;
180 unsigned solved = 0;
181 };
182 /// Whether unknown @p i of @p sys holds in this world: the least solution
183 /// is explored from the seeds only until it reaches @p i (or is complete).
184 bool fixUnknownHolds(gate_t sys, std::size_t i);
185 /// Whether every gate of @p conj is true in this world.
186 bool conjunctionHolds(const std::vector<gate_t> &conj);
187 std::unordered_map<gate_t, FixState> fix_state_;
188};
189
190bool Sampler::conjunctionHolds(const std::vector<gate_t> &conj)
191{
192 for(gate_t g : conj)
193 if(!evalBool(g))
194 return false;
195 return true;
196}
197
198bool Sampler::fixUnknownHolds(gate_t sys, std::size_t target)
199{
200 auto it = fix_state_.find(sys);
201 if(it == fix_state_.end()) {
202 FixState st;
203 st.lin = gc_.linearizeFixSystem(sys);
204 for(std::size_t i = 0; i < st.lin.n; ++i)
205 if(!st.lin.b[i].empty())
206 st.seeds.push_back(i);
207 st.reached.assign(st.lin.n, 0);
208 it = fix_state_.emplace(sys, std::move(st)).first;
209 }
210 FixState &st = it->second;
211 const FixSystemLinear &l = st.lin;
212 if(target >= l.n)
213 throw CircuitException("gate_fixpoint index out of range");
214
215 /* x_i = b_i | OR_j (a_ij & x_j) in a Boolean world: the least solution is
216 * the set of unknowns reachable from those whose constant part holds,
217 * along the terms whose coefficient holds. It is explored breadth-first,
218 * only as far as the unknown asked for, and resumed for another one of the
219 * same world. A coefficient is only evaluated when its unknown is
220 * reached, so the inputs it reads are drawn lazily, consistently with the
221 * rest of the world through the memo. */
222 const unsigned now = iteration_;
223 auto &reached = st.reached;
224 auto &queue = st.queue;
225 if(st.solved != now) {
226 st.solved = now;
227 queue.clear();
228 st.next = 0;
229 for(const std::size_t i : st.seeds)
230 for(const auto &conj : l.b[i])
231 if(conjunctionHolds(conj)) {
232 reached[i] = now;
233 queue.push_back(i);
234 break;
235 }
236 }
237 while(reached[target] != now && st.next < queue.size()) {
238 if((st.next & 4095) == 0)
240 const std::size_t j = queue[st.next++];
241 for(const auto &[i, conj] : l.out[j])
242 if(reached[i] != now && conjunctionHolds(conj)) {
243 reached[i] = now;
244 queue.push_back(i);
245 }
246 }
247 return reached[target] == now;
248}
249
250bool Sampler::evalBool(gate_t g)
251{
252 if(const char *m = boolMemo(g)) return *m;
253
254 bool result = false;
255 const auto type = gc_.getGateType(g);
256 const auto &wires = gc_.getWires(g);
257
258 switch(type) {
259 case gate_input:
260 case gate_update:
261 {
262 if(fixed_ != nullptr) {
263 result = fixed_->at(g);
264 break;
265 }
266 std::uniform_real_distribution<double> u(0.0, 1.0);
267 result = u(rng_) < gc_.getProb(g);
268 break;
269 }
270 case gate_plus:
271 result = false;
272 for(gate_t c : wires) {
273 if(evalBool(c)) { result = true; break; }
274 }
275 break;
276 case gate_times:
277 result = true;
278 for(gate_t c : wires) {
279 if(!evalBool(c)) { result = false; break; }
280 }
281 break;
282 case gate_monus:
283 if(wires.size() != 2)
284 throw CircuitException("gate_monus must have exactly two children");
285 result = evalBool(wires[0]) && !evalBool(wires[1]);
286 break;
287 case gate_zero:
288 result = false;
289 break;
290 case gate_one:
291 result = true;
292 break;
293 case gate_cmp:
294 {
295 if(wires.size() != 2)
296 throw CircuitException("gate_cmp must have exactly two children");
297 bool ok;
298 ComparisonOperator op = cmpOpFromOid(gc_.getInfos(g).first, ok);
299 if(!ok)
300 throw CircuitException(
301 "gate_cmp: unsupported operator OID " +
302 std::to_string(gc_.getInfos(g).first));
303 result = applyCmp(evalScalar(wires[0]), op, evalScalar(wires[1]));
304 break;
305 }
306 case gate_mulinput:
307 throw CircuitException(
308 "Monte Carlo over circuits containing gate_mulinput "
309 "is not yet supported on the RV path");
310 case gate_delta:
311 // δ-semiring operator: identity on the Boolean semiring, so the
312 // sampled truth value is just the wrapped child's. Showed up
313 // when conditioning on a row's provenance() in an aggregate
314 // query (HAVING / GROUP BY paths can splice δ over the
315 // semimod's k-side).
316 if(wires.size() != 1)
317 throw CircuitException("gate_delta must have exactly one child");
318 result = evalBool(wires[0]);
319 break;
320 case gate_assumed:
321 // Structural Boolean-rewrite marker: identity on the Boolean
322 // semiring, so the sampled truth value is the wrapped child's.
323 // The marker exists to refuse non-Boolean-compat evaluation; MC
324 // sampling for probability is always Boolean-compat.
325 if(wires.size() != 1)
326 throw CircuitException(
327 "gate_assumed must have exactly one child");
328 result = evalBool(wires[0]);
329 break;
330 case gate_annotation:
331 // Transparent annotation wrapper (inversion-free certificate / order
332 // key): identity, so the sampled truth value is the wrapped child's.
333 if(wires.size() != 1)
334 throw CircuitException("gate_annotation must have exactly one child");
335 result = evalBool(wires[0]);
336 break;
337 case gate_project:
338 case gate_eq:
339 // Where-provenance wrappers: identity on the Boolean semiring.
340 if(wires.empty())
341 throw CircuitException("a projection or equality gate needs a child");
342 result = evalBool(wires[0]);
343 break;
344 case gate_fixpoint:
345 {
346 // A row of a recursion on cyclic data: one unknown of the least
347 // solution of its equation system, solved in this world.
348 if(wires.size() != 1 || gc_.getGateType(wires[0]) != gate_fixsystem)
349 throw CircuitException(
350 "gate_fixpoint must have exactly one child, a gate_fixsystem");
351 const unsigned idx = gc_.getInfos(g).first;
352 if(idx < 1)
353 throw CircuitException("gate_fixpoint index out of range");
354 result = fixUnknownHolds(wires[0], idx - 1);
355 break;
356 }
357 default:
358 throw CircuitException(
359 "Unsupported gate type in Boolean evaluation: " +
360 std::string(gate_type_name[type]));
361 }
362
363 setBoolMemo(g, result);
364 return result;
365}
366
367std::optional<double> Sampler::evalScalar(gate_t g)
368{
369 auto it = scalar_cache_.find(g);
370 if(it != scalar_cache_.end()) return it->second;
371
372 std::optional<double> result = 0.0;
373 const auto type = gc_.getGateType(g);
374 const auto &wires = gc_.getWires(g);
375
376 switch(type) {
377 case gate_value:
378 /* The NULL value (a NULL branch of a CASE): undefined, as an aggregate
379 * over no row */
380 if(gc_.getUUID(g) == PROVSQL_GATE_NULL_UUID)
381 result = std::nullopt;
382 else
383 result = parseDoubleStrict(gc_.getExtra(g));
384 break;
385 case gate_rv:
386 {
387 // Fast path: an all-literal leaf builds its Distribution once and
388 // reuses it across iterations (dist_cache_ is never reset), so
389 // sampling never re-parses the spec. A latent (parametric) leaf,
390 // whose parameters are wire references resolved per iteration,
391 // bypasses that cache: its distribution changes every draw.
392 auto dit = dist_cache_.find(g);
393 if(dit != dist_cache_.end()) {
394 result = dit->second->sample(rng_);
395 break;
396 }
397 auto tmpl = parse_distribution_template(gc_.getExtra(g));
398 if(!tmpl)
399 throw CircuitException(
400 "Malformed gate_rv extra: " + gc_.getExtra(g));
401 if(!tmpl->parametric()) {
402 DistributionSpec spec{tmpl->family, tmpl->p1.literal, tmpl->p2.literal};
403 dit = dist_cache_.emplace(g, makeDistribution(spec)).first;
404 result = dit->second->sample(rng_);
405 break;
406 }
407 // Parametric leaf: resolve each wired parameter from the gate's
408 // wires via evalScalar (so a latent shared across leaves lands in
409 // scalar_cache_ and couples them), then build the family instance
410 // for this draw's parameters. The (double,double) factory and the
411 // Distribution interface are untouched -- only the parameters'
412 // source changes.
413 double p1, p2;
414 result = buildRvDistribution(g, *tmpl, p1, p2)->sample(rng_);
415 break;
416 }
417 case gate_arith:
418 {
419 if(wires.empty())
420 throw CircuitException("gate_arith must have at least one child");
421 auto op = static_cast<provsql_arith_op>(gc_.getInfos(g).first);
422 // Arithmetic is strict: an operand with no value in this world leaves
423 // the result without one. PERCENTILE reads its wires itself (a row
424 // with no value is skipped there, as SQL skips a NULL).
425 std::vector<double> v;
426 if(op != PROVSQL_ARITH_PERCENTILE) {
427 v.reserve(wires.size());
428 bool undefined = false;
429 for(gate_t c : wires) {
430 auto x = evalScalar(c);
431 if(!x) { undefined = true; break; }
432 v.push_back(*x);
433 }
434 if(undefined) {
435 result = std::nullopt;
436 break;
437 }
438 }
439 switch(op) {
441 {
442 double r = 0.0;
443 for(double x : v) r += x;
444 result = r;
445 break;
446 }
448 {
449 double r = 1.0;
450 for(double x : v) r *= x;
451 result = r;
452 break;
453 }
455 if(wires.size() != 2)
456 throw CircuitException("gate_arith MINUS must be binary");
457 result = v[0] - v[1];
458 break;
461 {
462 if(wires.size() != 2)
463 throw CircuitException(
464 std::string("gate_arith ")
465 + (op == PROVSQL_ARITH_DIV ? "DIV" : "INTDIV")
466 + " must be binary");
467 const double num = v[0];
468 const double den = v[1];
469 // A divisor that is zero in THIS world leaves the world without a
470 // value, as SQL leaves the query without a result there: the draw is
471 // a missing observation and the moment is taken over the worlds that
472 // do have one, exactly as for an aggregate with no contributing row.
473 // Dividing anyway gave an infinity that swallowed the estimate --
474 // expected(sum(a)/sum(b)) came back Infinity for data whose divisor
475 // cancels in one world only, where the same division under a HAVING
476 // answers over the other worlds (having_semantics declines this one).
477 // The moment estimators skip a world with no value.
478 if(den == 0.0)
479 result = std::nullopt;
480 else if(op == PROVSQL_ARITH_INTDIV)
481 result = std::trunc(num / den);
482 else
483 result = num / den;
484 break;
485 }
487 if(wires.size() != 1)
488 throw CircuitException("gate_arith NEG must be unary");
489 result = -v[0];
490 break;
492 // n-ary order statistic: max over the sampled children. Shared
493 // base RVs stay coupled through scalar_cache_, so max(x, y) with x,y
494 // over the same leaf draws them jointly (correct correlation).
495 // In PostgreSQL's order of floats, where NaN is the greatest.
496 {
497 double r = v[0];
498 for(std::size_t i = 1; i < v.size(); ++i)
499 if(sql_less(r, v[i])) r = v[i];
500 result = r;
501 break;
502 }
504 {
505 double r = v[0];
506 for(std::size_t i = 1; i < v.size(); ++i)
507 if(sql_less(v[i], r)) r = v[i];
508 result = r;
509 break;
510 }
512 {
513 if(wires.size() != 2)
514 throw CircuitException("gate_arith POW must be binary");
515 const double base = v[0];
516 const double expo = v[1];
517 result = std::pow(base, expo);
518 // std::pow is real-valued except for a negative base with a
519 // non-integer exponent. A NaN there is a domain violation,
520 // not an undefined world: raise with the fix rather than let
521 // the moment estimators silently drop the draw as a missing
522 // observation (which would report a biased, implicitly
523 // conditioned answer). A NaN operand (a NaN in the data) gives
524 // NaN, as in SQL.
525 if(std::isnan(*result) && !std::isnan(base) && !std::isnan(expo))
526 throw CircuitException(
527 "pow: negative base drawn with a non-integer exponent ("
528 + std::to_string(base) + " ^ " + std::to_string(expo)
529 + "); restrict the base to be non-negative, e.g. "
530 "pow(greatest(x, 0), p)");
531 break;
532 }
533 case PROVSQL_ARITH_LN:
534 {
535 if(wires.size() != 1)
536 throw CircuitException("gate_arith LN must be unary");
537 const double x = v[0];
538 // Same rationale as POW: a negative draw is a domain
539 // violation, raised rather than silently conditioned away.
540 // x = 0 legitimately yields -Infinity (a boundary value of
541 // probability zero for continuous arguments).
542 if(x < 0.0)
543 throw CircuitException(
544 "ln: negative draw (" + std::to_string(x)
545 + "); ln is only defined on [0, +Infinity) -- "
546 "restrict the argument's support");
547 result = std::log(x);
548 break;
549 }
551 if(wires.size() != 1)
552 throw CircuitException("gate_arith EXP must be unary");
553 result = std::exp(v[0]);
554 break;
556 {
557 // SQL round(v) / round(v, d): half away from zero, as numeric
558 // rounding is, and to d digits where a second wire gives d. The
559 // value is read per world, so the rounding applies to the value the
560 // world has, never to an expectation (rounding does not commute
561 // with it, which is why the moment evaluators sample it).
562 if(wires.empty() || wires.size() > 2)
563 throw CircuitException("gate_arith ROUND takes one or two wires");
564 const double x = v[0];
565 if(wires.size() == 1) {
566 result = std::round(x);
567 } else {
568 const double d = v[1];
569 if(std::isnan(x) || std::isnan(d)) { result = x + d; break; }
570 const double f = std::pow(10.0, d);
571 result = std::round(x * f) / f;
572 }
573 break;
574 }
576 if(wires.size() != 1)
577 throw CircuitException("gate_arith FLOOR must be unary");
578 result = std::floor(v[0]);
579 break;
581 if(wires.size() != 1)
582 throw CircuitException("gate_arith CEIL must be unary");
583 result = std::ceil(v[0]);
584 break;
586 if(wires.size() != 1)
587 throw CircuitException("gate_arith ABS must be unary");
588 result = std::fabs(v[0]);
589 break;
591 if(wires.size() != 1)
592 throw CircuitException("gate_arith ASFLOAT8 must be unary");
593 result = v[0]; /* already a double */
594 break;
596 if(wires.size() != 1)
597 throw CircuitException("gate_arith ASFLOAT4 must be unary");
598 result = static_cast<double>(static_cast<float>(v[0]));
599 break;
601 {
602 // Continuous percentile (SQL percentile_cont) over the group's
603 // rows: wires are interleaved [ind_1, x_1, ..., ind_n, x_n],
604 // the fraction is text-encoded in extra. Per draw, the values
605 // whose 0/1 presence indicator draws 1 are sorted and linearly
606 // interpolated at the fraction, NULL values skipped and NaN
607 // sorted last as SQL does; a draw with no present value has no
608 // value (skipped by the moment estimators like an empty-group
609 // avg).
610 if(wires.size() < 2 || wires.size() % 2 != 0)
611 throw CircuitException(
612 "gate_arith PERCENTILE must have interleaved "
613 "indicator/value wires");
614 double fraction;
615 try {
616 fraction = std::stod(gc_.getExtra(g));
617 } catch(const std::exception &) {
618 throw CircuitException(
619 "Malformed gate_arith PERCENTILE extra (expected the "
620 "fraction): " + gc_.getExtra(g));
621 }
622 std::vector<double> members;
623 for(std::size_t i = 0; i < wires.size(); i += 2) {
624 const auto present = evalScalar(wires[i]);
625 if(present && *present >= 0.5) {
626 const auto x = evalScalar(wires[i + 1]);
627 if(x)
628 members.push_back(*x);
629 }
630 }
631 if(members.empty()) {
632 result = std::nullopt;
633 break;
634 }
635 std::sort(members.begin(), members.end(), sql_less<double>);
636 const double pos = fraction * (members.size() - 1);
637 const std::size_t lo = static_cast<std::size_t>(pos);
638 const double frac = pos - static_cast<double>(lo);
639 result = (lo + 1 < members.size())
640 ? members[lo] + frac * (members[lo + 1] - members[lo])
641 : members[lo];
642 break;
643 }
644 default:
645 throw CircuitException(
646 "Unknown gate_arith operator tag: " +
647 std::to_string(static_cast<unsigned>(op)));
648 }
649 break;
650 }
651 case gate_agg:
652 {
653 // HAVING-style aggregate evaluated per MC iteration: walk the
654 // gate_semimod children, keep the rows whose k_gate fires in
655 // this world, push their value into a reusable Aggregator,
656 // return the finalised scalar. Closes the priority-4-era gap
657 // that made `WHERE rv > 0 GROUP BY x HAVING count(*) > 1`
658 // structural-only (see continuous_selection.sql section G).
659 //
660 // Type plan: we evaluate every numeric path in float8 to stay
661 // inside evalScalar's return type. COUNT is normalised by
662 // makeAggregator to SumAgg<long>, so each kept row contributes its
663 // value gate cast to long: that gate is 1 for an ordinary row and 0
664 // for a NULL one (count(x) does not count NULLs), so the sum of the
665 // kept values is exactly count(*) / count(x) -- faithful with no
666 // nullability check. SUM / AVG / MIN / MAX consume the value via
667 // evalScalar directly. Empty groups finalise to NONE; what that
668 // means depends on the aggregate and on whether the aggregation is
669 // scalar or grouped -- see the NONE arm below.
671 getAggregationOperator(gc_.getInfos(g).first);
672 std::unique_ptr<Aggregator> agg =
676 if(!agg)
677 throw CircuitException(
678 "gate_agg: makeAggregator returned null for op " +
679 std::to_string(static_cast<int>(op)));
680 for(gate_t child : wires) {
681 if(gc_.getGateType(child) != gate_semimod) continue;
682 const auto &sm = gc_.getWires(child);
683 if(sm.size() != 2) continue;
684 if(!evalBool(sm[0])) continue;
685 // A row whose value is NULL contributes nothing, as in SQL.
686 const auto x = evalScalar(sm[1]);
687 if(!x) continue;
689 agg->add(AggValue(static_cast<long>(*x)));
690 } else {
691 agg->add(AggValue(*x));
692 }
693 }
694 AggValue r = agg->finalize();
695 switch(r.getType()) {
696 case ValueType::INT:
697 result = static_cast<double>(std::get<long>(r.v));
698 break;
699 case ValueType::FLOAT:
700 result = std::get<double>(r.v);
701 break;
702 case ValueType::NONE:
703 // No contributor survived this iteration -- either no row of the
704 // group is present in this world, or every contributed value was
705 // NULL. SUM / AVG / MIN / MAX are then SQL NULL: no value, which
706 // no enclosing gate_cmp holds on (the truth value of a comparison
707 // against NULL) and which the moment averagers in Expectation skip
708 // as a missing observation, making those estimators conditional on
709 // the worlds where the aggregate is defined.
710 //
711 // COUNT has no NULL to report -- an empty set genuinely counts 0 --
712 // but 0 is the right answer only where a row exists to carry it.
713 // A scalar aggregation always yields its single row, empty input
714 // included, so 0 it is. For a grouped aggregation an empty group
715 // is no row at all: the possible-world semantics excludes that
716 // world (having_semantics.hpp enumerates from world 1, and
717 // RangeCheck rewrites a trivially-true count comparison to the
718 // group-existence gate rather than to gate_one). Reporting 0
719 // there would let a true-on-zero predicate such as
720 // `count(*) <= k` hold in a world that contributes no row,
721 // inflating the estimate by the probability that the group is
722 // empty; no value keeps the enclosing comparison false, which is
723 // how this sampler declines a world.
725 (gc_.getInfos(g).second & PROVSQL_AGG_SCALAR_FLAG) != 0)
726 result = 0.0;
727 else
728 result = std::nullopt;
729 break;
730 default:
731 throw CircuitException(
732 "gate_agg: unsupported aggregate result ValueType in MC");
733 }
734 break;
735 }
736 case gate_semimod:
737 {
738 // Bare semimod root (the user pinned one of an agg's per-row
739 // contributions): interpret as a Bernoulli-weighted scalar
740 // value · 1_{k fires}. When the Boolean k child does not fire
741 // in this world, the row contributes nothing -- return 0.0
742 // (the additive identity), which matches the per-iteration
743 // role semimod plays inside gate_agg above. This makes
744 // semimod a legal scalar root for rv_sample / rv_moment /
745 // rv_histogram alongside agg.
746 const auto &wires = gc_.getWires(g);
747 if(wires.size() != 2)
748 throw CircuitException(
749 "gate_semimod must have exactly two children "
750 "[k_gate, value_gate]");
751 result = evalBool(wires[0]) ? evalScalar(wires[1])
752 : std::optional<double>(0.0);
753 break;
754 }
755 case gate_mixture:
756 {
757 // Two shapes of gate_mixture share this case:
758 //
759 // - Classic 3-wire: [p_token, x_token, y_token]. Draw the
760 // Bernoulli via evalBool, which handles gate_input by
761 // sampling uniform(0,1) < get_prob and memoises on
762 // the Boolean memo; two mixtures sharing the same p_token
763 // therefore see the same draw, and any unrelated Boolean
764 // parent of p_token stays in sync.
765 //
766 // - Categorical N-wire: [key, mul_1, ..., mul_n]. Built
767 // directly by the @c provsql.categorical SQL constructor;
768 // each mul_i carries its probability in set_prob and its
769 // outcome value in extra.
770 // We draw a single uniform[0,1) per block, walk the
771 // cumulative probabilities to pick a mulinput, and stash the
772 // Boolean truth values into the Boolean memo so any downstream
773 // Boolean consumer of the mulinputs (independentEvaluation,
774 // OR/AND parents) sees a consistent sampled outcome.
775 if(gc_.isCategoricalMixture(g)) {
776 std::uniform_real_distribution<double> u(0.0, 1.0);
777 const double r = u(rng_);
778 double cum = 0.0;
779 // Default to the last mulinput in case floating-point cumulative
780 // sums leave us shy of 1.0 by a few ULPs.
781 std::size_t chosen = wires.size() - 1;
782 for(std::size_t i = 1; i < wires.size(); ++i) {
783 cum += gc_.getProb(wires[i]);
784 if(r < cum) { chosen = i; break; }
785 }
786 for(std::size_t i = 1; i < wires.size(); ++i) {
787 setBoolMemo(wires[i], i == chosen);
788 }
789 result = parseDoubleStrict(gc_.getExtra(wires[chosen]));
790 break;
791 }
792 if(wires.size() != 3)
793 throw CircuitException(
794 "gate_mixture must have exactly three children "
795 "[p_token, x_token, y_token]");
796 result = evalBool(wires[0]) ? evalScalar(wires[1])
797 : evalScalar(wires[2]);
798 break;
799 }
800 case gate_case:
801 {
802 // Guarded selection [g_1, v_1, ..., g_k, v_k, default] (2k+1 wires):
803 // first-match on the current draw. Evaluating the guards through
804 // evalBool and the values through evalScalar in the same iteration
805 // keeps shared base RVs coupled (a value and a guard over the same leaf
806 // draw jointly), which is exactly why gate_case beats a mixture-of-
807 // conditioned lowering that would resample and lose the correlation.
808 const auto &wires = gc_.getWires(g);
809 if(wires.empty())
810 throw CircuitException(
811 "gate_case must have at least one child (the default)");
812 const std::size_t k = wires.size() / 2;
813 bool matched = false;
814 for(std::size_t i = 0; i < k; ++i) {
815 if(evalBool(wires[2 * i])) {
816 result = evalScalar(wires[2 * i + 1]);
817 matched = true;
818 break;
819 }
820 }
821 if(!matched)
822 result = evalScalar(wires.back()); // the default value
823 break;
824 }
825 default:
826 throw CircuitException(
827 "Unsupported gate type in scalar evaluation: " +
828 std::string(gate_type_name[type]));
829 }
830
831 scalar_cache_[g] = result;
832 return result;
833}
834
835std::unique_ptr<Distribution> Sampler::buildRvDistribution(
836 gate_t leaf, const DistributionTemplate &tmpl, double &p1, double &p2)
837{
838 const auto &w = gc_.getWires(leaf);
839 auto resolve = [&](const DistributionParam &p) {
840 if(p.wire_slot < 0) return p.literal;
841 const auto x = evalScalar(w[p.wire_slot]);
842 if(!x)
843 throw CircuitException(
844 "gate_rv " + std::string(tmpl.family->name)
845 + ": a parameter has no value in a drawn world (a NULL, or "
846 "an aggregate over no row)");
847 return *x;
848 };
849 p1 = resolve(tmpl.p1);
850 p2 = resolve(tmpl.p2);
851 auto dist = tmpl.family->factory(p1, p2);
852 // Parameter-domain policy: a drawn parameter may fall outside the
853 // family's domain (a sampled scale/rate/shape <= 0). Do NOT silently
854 // drop such a draw -- that implicitly truncates the prior and biases
855 // every downstream moment (same reasoning as the gate_arith POW / LN
856 // guards). integrationRange() returns false exactly when the parameters
857 // are degenerate/out-of-domain, so it is the family-agnostic validity
858 // gate; raise a specific, actionable error.
859 double dlo, dhi;
860 if(!dist->integrationRange(dlo, dhi))
861 throw CircuitException(
862 "gate_rv " + std::string(tmpl.family->name)
863 + ": a parameter drawn outside the family's domain "
864 "(e.g. a scale/rate/shape <= 0: got "
865 + std::to_string(p1) + ", " + std::to_string(p2)
866 + "); put a positive-support prior on it, e.g. "
867 "gamma / lognormal");
868 return dist;
869}
870
871double Sampler::evalWeight(gate_t g)
872{
873 const auto type = gc_.getGateType(g);
874 const auto &wires = gc_.getWires(g);
875 switch(type) {
876 case gate_times: {
877 // Evidence conjunction: the product of the children's weights.
878 // Short-circuit on a zero factor (a rejected Boolean event or a
879 // datum outside a leaf's support) -- the particle is dead.
880 double w = 1.0;
881 for(gate_t c : wires) {
882 w *= evalWeight(c);
883 if(w == 0.0) return 0.0;
884 }
885 return w;
886 }
887 case gate_observe: {
888 // Continuous-density evidence: the observed leaf's pdf at the datum.
889 // Resolving the leaf's (possibly latent) parameters through
890 // evalScalar populates scalar_cache_, so a latent shared with the
891 // queried root couples the weight and the value.
892 if(wires.size() != 1)
893 throw CircuitException(
894 "gate_observe must have exactly one child (the observed leaf)");
895 const gate_t leaf = wires[0];
896 if(gc_.getGateType(leaf) != gate_rv)
897 throw CircuitException(
898 "gate_observe child must be a gate_rv leaf");
899 const double d = parseDoubleStrict(gc_.getExtra(g));
900 auto tmpl = parse_distribution_template(gc_.getExtra(leaf));
901 if(!tmpl)
902 throw CircuitException(
903 "gate_observe: malformed observed gate_rv extra: "
904 + gc_.getExtra(leaf));
905 double p1, p2;
906 return buildRvDistribution(leaf, *tmpl, p1, p2)->pdf(d);
907 }
908 case gate_cmp: {
909 // A point observation "Y = c" on a bare RV leaf is likelihood
910 // evidence (the internal form of observe(Y, c)): weight by the
911 // leaf's density / mass at c -- pdf for a continuous leaf, pmf for a
912 // discrete one (pdf() returns the pmf). Any other cmp (inequality,
913 // non-leaf, non-constant) is an ordinary Boolean event: 0/1 weight.
914 gate_t leaf;
915 double datum;
916 if(matchPointObservationCmp(gc_, g, leaf, datum)) {
917 auto tmpl = parse_distribution_template(gc_.getExtra(leaf));
918 if(tmpl) {
919 double p1, p2;
920 return buildRvDistribution(leaf, *tmpl, p1, p2)->pdf(datum);
921 }
922 }
923 return evalBool(g) ? 1.0 : 0.0;
924 }
925 default:
926 // Any other subtree is a Boolean conditioning event: a 0/1 weight,
927 // which is exactly rejection conditioning -- so a purely Boolean
928 // evidence tree through evalWeight reproduces
929 // monteCarloConditionalScalarSamples.
930 return evalBool(g) ? 1.0 : 0.0;
931 }
932}
933
934} // namespace
935
936double monteCarloRV(const GenericCircuit &gc, gate_t root, unsigned samples)
937{
938 std::mt19937_64 rng = seedRng();
939 Sampler sampler(gc, rng);
940
941 unsigned success = 0;
942 for(unsigned i = 0; i < samples; ++i) {
943 sampler.resetIteration();
944 if(sampler.evalBool(root))
945 ++success;
946
948 throw CircuitException(
949 "Interrupted after " + std::to_string(i + 1) + " samples");
950 }
951 return success * 1.0 / samples;
952}
953
955 double eps, double delta,
956 unsigned long max_samples,
957 unsigned long &samples_used,
958 bool &reached_target)
959{
960 samples_used = 0;
961 reached_target = false;
962 if(max_samples == 0)
963 return 0.;
964
965 // DKLR stopping threshold on the success count -- the S=1 Bernoulli case of
966 // BooleanCircuit::karpLubyStopping: draw whole-circuit worlds until the
967 // success count reaches Y1 and return Y1/N, a relative (eps,delta) estimate
968 // of Pr[root]; N adapts to the true Pr[root] (expected Y1/Pr[root]).
969 const double e = std::exp(1.0);
970 const double Y = 4.0 * (e - 2.0) * std::log(2.0 / delta) / (eps * eps);
971 const double Y1 = 1.0 + (1.0 + eps) * Y;
972
973 std::mt19937_64 rng = seedRng();
974 Sampler sampler(gc, rng);
975
976 unsigned long success = 0;
977 for(unsigned long s = 0; s < max_samples; ++s) {
978 sampler.resetIteration();
979 if(sampler.evalBool(root)) {
980 ++success;
981 if(static_cast<double>(success) >= Y1) {
982 samples_used = s + 1;
983 reached_target = true;
984 return Y1 / static_cast<double>(samples_used);
985 }
986 }
988 throw CircuitException(
989 "Interrupted after " + std::to_string(s + 1) + " samples");
990 }
991
992 // Cap reached before the threshold: the relative target is not met, so return
993 // the plain unbiased mean over the spent budget.
994 samples_used = max_samples;
995 return static_cast<double>(success) / static_cast<double>(max_samples);
996}
997
998std::vector<double> monteCarloJointDistribution(
999 const GenericCircuit &gc,
1000 const std::vector<gate_t> &cmps,
1001 unsigned samples)
1002{
1003 const unsigned k = cmps.size();
1004 if (k == 0)
1005 throw CircuitException(
1006 "monteCarloJointDistribution: empty cmps list");
1007 if (k > 30)
1008 throw CircuitException(
1009 "monteCarloJointDistribution: too many cmps in island ("
1010 + std::to_string(k) + " > 30)");
1011
1012 std::mt19937_64 rng = seedRng();
1013 Sampler sampler(gc, rng);
1014
1015 const std::size_t nb_outcomes = std::size_t{1} << k;
1016 std::vector<unsigned> counts(nb_outcomes, 0);
1017
1018 for (unsigned i = 0; i < samples; ++i) {
1019 sampler.resetIteration();
1020 std::size_t w = 0;
1021 for (unsigned j = 0; j < k; ++j) {
1022 if (sampler.evalBool(cmps[j])) w |= (std::size_t{1} << j);
1023 }
1024 ++counts[w];
1026 throw CircuitException(
1027 "Interrupted after " + std::to_string(i + 1) + " samples");
1028 }
1029
1030 std::vector<double> probs(nb_outcomes);
1031 for (std::size_t w = 0; w < nb_outcomes; ++w)
1032 probs[w] = counts[w] * 1.0 / samples;
1033 return probs;
1034}
1035
1036std::vector<std::optional<double>> monteCarloScalarSamples(
1037 const GenericCircuit &gc, gate_t root, unsigned samples)
1038{
1039 std::mt19937_64 rng = seedRng();
1040 Sampler sampler(gc, rng);
1041
1042 std::vector<std::optional<double>> out;
1043 out.reserve(samples);
1044 for(unsigned i = 0; i < samples; ++i) {
1045 sampler.resetIteration();
1046 out.push_back(sampler.evalScalar(root));
1047
1049 throw CircuitException(
1050 "Interrupted after " + std::to_string(i + 1) + " samples");
1051 }
1052 return out;
1053}
1054
1055std::vector<double>
1056definedDraws(const std::vector<std::optional<double>> &samples)
1057{
1058 std::vector<double> out;
1059 out.reserve(samples.size());
1060 for(const auto &x : samples)
1061 if(x) out.push_back(*x);
1062 return out;
1063}
1064
1065/** @brief The Boolean inputs the worlds of @p root (and @p event) range over,
1066 * or @c nullopt when another random source, an input without a probability,
1067 * or more than @p max_inputs inputs make the enumeration inapplicable. */
1068static std::optional<std::vector<gate_t>>
1070 std::optional<gate_t> event, unsigned max_inputs)
1071{
1072 std::vector<gate_t> inputs;
1073 std::unordered_set<gate_t> seen;
1074 std::stack<gate_t> todo;
1075 todo.push(root);
1076 if(event) todo.push(*event);
1077 while(!todo.empty()) {
1078 gate_t g = todo.top();
1079 todo.pop();
1080 if(!seen.insert(g).second) continue;
1081 switch(gc.getGateType(g)) {
1082 case gate_input:
1083 case gate_update:
1084 if(std::isnan(gc.getProb(g))) return std::nullopt;
1085 inputs.push_back(g);
1086 break;
1087 case gate_rv:
1088 case gate_mixture:
1089 case gate_observe:
1090 case gate_mulinput:
1091 return std::nullopt;
1092 default:
1093 break;
1094 }
1095 if(inputs.size() > max_inputs) return std::nullopt;
1096 for(gate_t c : gc.getWires(g)) todo.push(c);
1097 }
1098 return inputs;
1099}
1100
1101std::optional<double>
1103 unsigned max_inputs)
1104{
1105 auto inputs_opt = enumerableInputs(gc, root, std::nullopt, max_inputs);
1106 if(!inputs_opt) return std::nullopt;
1107 const std::vector<gate_t> &inputs = *inputs_opt;
1108
1109 std::mt19937_64 rng; /* unused: every input is fixed */
1110 Sampler sampler(gc, rng);
1111 std::unordered_map<gate_t, bool> world;
1112 sampler.fixInputs(&world);
1113 double total = 0.0;
1114 const std::uint64_t n_worlds = std::uint64_t(1) << inputs.size();
1115 for(std::uint64_t w = 0; w < n_worlds; ++w) {
1116 double p = 1.0;
1117 for(std::size_t i = 0; i < inputs.size(); ++i) {
1118 const bool present = (w >> i) & 1;
1119 const double pi = gc.getProb(inputs[i]);
1120 world[inputs[i]] = present;
1121 p *= present ? pi : 1.0 - pi;
1122 }
1123 if(p == 0.0) continue;
1124 sampler.resetIteration();
1125 if(sampler.evalBool(root))
1126 total += p;
1127
1129 throw CircuitException("Interrupted after " + std::to_string(w + 1) +
1130 " worlds");
1131 }
1132 return total;
1133}
1134
1135std::optional<std::vector<std::pair<double, std::optional<double>>>>
1137 std::optional<gate_t> event, unsigned max_inputs)
1138{
1139 auto inputs_opt = enumerableInputs(gc, root, event, max_inputs);
1140 if(!inputs_opt) return std::nullopt;
1141 const std::vector<gate_t> &inputs = *inputs_opt;
1142
1143 std::mt19937_64 rng; /* unused: every input is fixed */
1144 Sampler sampler(gc, rng);
1145 std::unordered_map<gate_t, bool> world;
1146 sampler.fixInputs(&world);
1147 std::vector<std::pair<double, std::optional<double>>> out;
1148 const std::uint64_t n_worlds = std::uint64_t(1) << inputs.size();
1149 for(std::uint64_t w = 0; w < n_worlds; ++w) {
1150 double p = 1.0;
1151 for(std::size_t i = 0; i < inputs.size(); ++i) {
1152 const bool present = (w >> i) & 1;
1153 const double pi = gc.getProb(inputs[i]);
1154 world[inputs[i]] = present;
1155 p *= present ? pi : 1.0 - pi;
1156 }
1157 if(p == 0.0) continue;
1158 sampler.resetIteration();
1159 if(event && !sampler.evalBool(*event)) continue;
1160 out.emplace_back(p, sampler.evalScalar(root));
1161
1163 throw CircuitException("Interrupted after " + std::to_string(w + 1) +
1164 " worlds");
1165 }
1166 return out;
1167}
1168
1169std::pair<std::vector<std::optional<double>>,
1170 std::vector<std::optional<double>>>
1172 gate_t root_b, unsigned samples)
1173{
1174 std::mt19937_64 rng = seedRng();
1175 Sampler sampler(gc, rng);
1176
1177 std::vector<std::optional<double>> out_a, out_b;
1178 out_a.reserve(samples);
1179 out_b.reserve(samples);
1180 for(unsigned i = 0; i < samples; ++i) {
1181 sampler.resetIteration();
1182 /* Both roots are evaluated within the same iteration, so a gate_rv /
1183 * gate_input leaf reachable from both shares its per-iteration draw:
1184 * the pair (a_i, b_i) is a draw from the JOINT distribution, which is
1185 * the whole point (mutual information over the marginals alone would
1186 * be identically zero). */
1187 out_a.push_back(sampler.evalScalar(root_a));
1188 out_b.push_back(sampler.evalScalar(root_b));
1189
1191 throw CircuitException(
1192 "Interrupted after " + std::to_string(i + 1) + " samples");
1193 }
1194 return {std::move(out_a), std::move(out_b)};
1195}
1196
1198 const GenericCircuit &gc, gate_t root, gate_t event_root, unsigned samples)
1199{
1200 std::mt19937_64 rng = seedRng();
1201 Sampler sampler(gc, rng);
1202
1204 out.attempted = 0;
1205 out.accepted.reserve(samples);
1206
1207 for(unsigned i = 0; i < samples; ++i) {
1208 sampler.resetIteration();
1209 /* Evaluate the indicator FIRST: this populates the Boolean memo AND
1210 * scalar_cache_ for every gate_rv / gate_input that the event
1211 * touches, so the subsequent evalScalar(root) reads the same
1212 * draws. Shared gate_t leaves between root and event_root are
1213 * therefore correctly coupled across the indicator and the
1214 * value. */
1215 if(sampler.evalBool(event_root)) {
1216 out.accepted.push_back(sampler.evalScalar(root));
1217 }
1218 ++out.attempted;
1219
1221 throw CircuitException(
1222 "Interrupted after " + std::to_string(i + 1) + " samples");
1223 }
1224 return out;
1225}
1226
1228 const GenericCircuit &gc, gate_t root_a, gate_t root_b,
1229 gate_t event_root, unsigned samples)
1230{
1231 std::mt19937_64 rng = seedRng();
1232 Sampler sampler(gc, rng);
1233
1235 out.attempted = 0;
1236 out.xs.reserve(samples);
1237 out.ys.reserve(samples);
1238
1239 for(unsigned i = 0; i < samples; ++i) {
1240 sampler.resetIteration();
1241 /* Indicator first (populating the per-iteration caches), then both
1242 * values against the same caches: shared leaves couple across the
1243 * event and the two roots, per monteCarloConditionalScalarSamples. */
1244 if(sampler.evalBool(event_root)) {
1245 out.xs.push_back(sampler.evalScalar(root_a));
1246 out.ys.push_back(sampler.evalScalar(root_b));
1247 }
1248 ++out.attempted;
1249
1251 throw CircuitException(
1252 "Interrupted after " + std::to_string(i + 1) + " samples");
1253 }
1254 return out;
1255}
1256
1257std::optional<std::vector<double>>
1259 gate_t event_root, unsigned n)
1260{
1261 auto m = matchTruncatedSingleRv(gc, root, event_root);
1262 if (!m) return std::nullopt;
1263
1264 /* Per-family rejection-free scheme (Distribution::sampleTruncated);
1265 * a family without one (Erlang: needs the inverse regularised
1266 * incomplete gamma) returns nullopt and the MC-rejection fallback
1267 * handles it. */
1268 std::mt19937_64 rng = seedRng();
1269 return makeDistribution(m->spec)->sampleTruncated(rng, m->lo, m->hi, n);
1270}
1271
1273 const GenericCircuit &gc, gate_t root, gate_t evidence, unsigned samples)
1274{
1275 std::mt19937_64 rng = seedRng();
1276 Sampler sampler(gc, rng);
1277
1279 out.particles.reserve(samples);
1280
1281 for(unsigned i = 0; i < samples; ++i) {
1282 sampler.resetIteration();
1283 /* Evaluate the evidence FIRST: this fills scalar_cache_ for every
1284 * latent the evidence touches, so the subsequent evalScalar(root)
1285 * reads the same latent draw -- coupling the weight and the value. */
1286 const double w = sampler.evalWeight(evidence);
1287 ++out.attempted;
1288 if(w > 0.0) {
1289 /* A draw where the root has no value is a missing observation: it
1290 * weighs in the evidence, not in the posterior statistics. */
1291 const auto x = sampler.evalScalar(root);
1292 if(x)
1293 out.particles.push_back({*x, w});
1294 out.weight_sum += w;
1295 out.weight_sq_sum += w * w;
1296 }
1297 /* A zero-weight draw contributes 0 to every weighted sum but still
1298 * counts in `attempted`, so evidence() = weight_sum / attempted is the
1299 * marginal likelihood P(data). */
1300
1302 throw CircuitException(
1303 "Interrupted after " + std::to_string(i + 1) + " samples");
1304 }
1305 return out;
1306}
1307
1308double importanceEvidence(const GenericCircuit &gc, gate_t evidence,
1309 unsigned samples)
1310{
1311 if(samples == 0) return 0.0;
1312 std::mt19937_64 rng = seedRng();
1313 Sampler sampler(gc, rng);
1314
1315 double sw = 0.0;
1316 for(unsigned i = 0; i < samples; ++i) {
1317 sampler.resetIteration();
1318 sw += sampler.evalWeight(evidence);
1320 throw CircuitException(
1321 "Interrupted after " + std::to_string(i + 1) + " samples");
1322 }
1323 return sw / static_cast<double>(samples);
1324}
1325
1326std::vector<double> posteriorResample(const WeightedPosterior &post,
1327 unsigned n)
1328{
1329 std::vector<double> out;
1330 if(post.particles.empty() || post.weight_sum <= 0.0) return out;
1331 /* Cumulative weights for inverse-CDF resampling. */
1332 std::vector<double> cum;
1333 cum.reserve(post.particles.size());
1334 double c = 0.0;
1335 for(const auto &pw : post.particles) { c += pw.second; cum.push_back(c); }
1336
1337 std::mt19937_64 rng = seedRng();
1338 std::uniform_real_distribution<double> u(0.0, c);
1339 out.reserve(n);
1340 for(unsigned i = 0; i < n; ++i) {
1341 const double r = u(rng);
1342 auto it = std::lower_bound(cum.begin(), cum.end(), r);
1343 std::size_t idx = static_cast<std::size_t>(it - cum.begin());
1344 if(idx >= post.particles.size()) idx = post.particles.size() - 1;
1345 out.push_back(post.particles[idx].first);
1346 }
1347 return out;
1348}
1349
1351{
1352 std::unordered_set<gate_t> seen;
1353 std::stack<gate_t> stack;
1354 stack.push(root);
1355 while(!stack.empty()) {
1356 gate_t g = stack.top();
1357 stack.pop();
1358 if(!seen.insert(g).second) continue;
1359 // Either an explicit gate_observe, or a point observation "Y = c" on a
1360 // bare RV leaf (the equality-conditioning form) -- both are density /
1361 // mass likelihood evidence the importance-sampling path must weight
1362 // rather than reject.
1363 gate_t leaf;
1364 double datum;
1365 if(gc.getGateType(g) == gate_observe
1366 || matchPointObservationCmp(gc, g, leaf, datum))
1367 return true;
1368 for(gate_t c : gc.getWires(g)) stack.push(c);
1369 }
1370 return false;
1371}
1372
1374{
1375 /* A multivalued input (a block of repair_key) is not sampled here: such a
1376 * circuit keeps the Boolean expansion, which rewrites the blocks. */
1377 bool fixpoint = false;
1378 std::unordered_set<gate_t> seen;
1379 std::stack<gate_t> stack;
1380 stack.push(root);
1381 while(!stack.empty()) {
1382 gate_t g = stack.top();
1383 stack.pop();
1384 if(!seen.insert(g).second) continue;
1385 const auto t = gc.getGateType(g);
1386 if(t == gate_mulinput)
1387 return false;
1388 if(t == gate_fixpoint)
1389 fixpoint = true;
1390 for(gate_t c : gc.getWires(g)) stack.push(c);
1391 }
1392 return fixpoint;
1393}
1394
1396{
1397 std::unordered_set<gate_t> seen;
1398 std::stack<gate_t> stack;
1399 stack.push(root);
1400 while(!stack.empty()) {
1401 gate_t g = stack.top();
1402 stack.pop();
1403 if(!seen.insert(g).second) continue;
1404 auto type = gc.getGateType(g);
1405 // A continuous random variable is signalled by a gate_rv leaf or a
1406 // gate_mixture root. gate_arith is NOT itself an RV marker: it is also
1407 // arithmetic over aggregates (resolved by provsql_having's possible-worlds
1408 // enumeration). A genuine RV arithmetic gate_arith still reaches its
1409 // gate_rv leaves through the child walk below, so it is caught.
1410 if(type == gate_rv || type == gate_mixture)
1411 return true;
1412 for(gate_t c : gc.getWires(g)) stack.push(c);
1413 }
1414 return false;
1415}
1416
1418{
1419 // True iff a gate_agg survives the probability pre-passes AND every surviving
1420 // one is sample-faithful: SUM / AVG / MIN / MAX / COUNT -- all the aggregates
1421 // the sampler's gate_agg arm reproduces exactly. That arm pushes each kept
1422 // contributor's value into the matching Aggregator: the value gate is the
1423 // row's contribution (the summed term for SUM; the 0/1 indicator for COUNT,
1424 // 0 for a NULL row so count(x) does not count NULLs; the compared value for
1425 // AVG / MIN / MAX), so NULL rows are handled and an empty group finalises to
1426 // the value the exact HAVING evaluator uses (0 for SUM / COUNT, NaN ->
1427 // comparison false for AVG / MIN / MAX). An aggregate that bailed the exact
1428 // evaluators (whose threshold-lineage expansion would otherwise not terminate
1429 // for a large-magnitude / large-support aggregate) is then estimated by direct
1430 // world sampling: the apx-safe corner of the HAVING trichotomy (Re & Suciu).
1431 // gate_arith over such aggregates is covered (its gate_agg leaves are reached
1432 // by the walk). The explicit switch rejects any future aggregate operator the
1433 // sampler does not yet handle.
1434 std::unordered_set<gate_t> seen;
1435 std::stack<gate_t> stack;
1436 stack.push(root);
1437 bool any = false;
1438 while(!stack.empty()) {
1439 gate_t g = stack.top();
1440 stack.pop();
1441 if(!seen.insert(g).second) continue;
1442 if(gc.getGateType(g) == gate_agg) {
1443 switch(getAggregationOperator(gc.getInfos(g).first)) {
1449 any = true;
1450 break;
1451 default: // an aggregate the sampler lacks: not routed
1452 return false;
1453 }
1454 }
1455 for(gate_t c : gc.getWires(g)) stack.push(c);
1456 }
1457 return any;
1458}
1459
1461{
1462 // True iff a gate_semimod carries an aggregate-valued M side: the
1463 // contribution of a row whose value is itself an aggregate result (an avg of
1464 // a count, a max of a sum, an aggregate of an arithmetic expression over
1465 // aggregates -- provenance_semimod_nested). Such a value is one per
1466 // possible world, not a constant read off a gate_value, so every closed form
1467 // declines it and the Boolean view of the comparison cannot be built: only
1468 // an evaluator that reads a value per world (this sampler, or the exact
1469 // enumeration of the worlds of the inputs) resolves it.
1470 std::unordered_set<gate_t> seen;
1471 std::stack<gate_t> stack;
1472 stack.push(root);
1473 while(!stack.empty()) {
1474 gate_t g = stack.top();
1475 stack.pop();
1476 if(!seen.insert(g).second) continue;
1477 if(gc.getGateType(g) == gate_semimod) {
1478 const auto &w = gc.getWires(g);
1479 if(w.size() == 2 && gc.getGateType(w[1]) != gate_value)
1480 return true;
1481 }
1482 for(gate_t c : gc.getWires(g)) stack.push(c);
1483 }
1484 return false;
1485}
1486
1487} // namespace provsql
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.
std::unique_ptr< Aggregator > makeAggregator(AggregationOperator op, ValueType t)
Create a concrete Aggregator for the given operator and value type.
Typed aggregation value, operator, and aggregator abstractions.
AggregationOperator
SQL aggregation functions tracked by ProvSQL.
Definition Aggregation.h:52
@ MAX
MAX → input type.
Definition Aggregation.h:56
@ COUNT
COUNT(*) or COUNT(expr) → integer.
Definition Aggregation.h:53
@ SUM
SUM → integer or float.
Definition Aggregation.h:54
@ MIN
MIN → input type.
Definition Aggregation.h:55
@ AVG
AVG → float.
Definition Aggregation.h:57
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
bool sql_less(T a, T b)
The order PostgreSQL gives numbers: for floats, NaN equals NaN and is greater than every other value ...
bool sql_less< double >(double a, double b)
sql_less for double, with PostgreSQL's place for NaN.
@ INT
Signed 64-bit integer.
@ NONE
No value (NULL).
@ FLOAT
Double-precision float.
gate_t
Strongly-typed gate identifier.
Definition Circuit.h:53
Out-of-line template method implementations for Circuit<gateType>.
Per-family polymorphic view over a continuous gate_rv distribution (§F.1 class hierarchy).
Monte Carlo sampling over a GenericCircuit, RV-aware.
Continuous random-variable helpers (distribution parsing, moments).
Support-based bound check for continuous-RV comparators.
Exception type thrown by circuit operations on invalid input.
Definition Circuit.h:382
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
uuid getUUID(gate_t g) const
Return the UUID string associated with gate g.
Definition Circuit.hpp:65
bool isCategoricalMixture(gate_t g) const
Test whether g is a categorical-form gate_mixture (the explicit provsql.categorical output).
FixSystemLinear linearizeFixSystem(gate_t sys) const
The equations of the gate_fixsystem sys, as linear forms over the gates that do not depend on its unk...
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.
std::optional< std::vector< std::pair< double, std::optional< double > > > > enumerateScalarWorlds(const GenericCircuit &gc, gate_t root, std::optional< gate_t > event, unsigned max_inputs)
The possible worlds of a circuit whose only random sources are Boolean inputs: the exact alternative ...
std::vector< std::optional< double > > monteCarloScalarSamples(const GenericCircuit &gc, gate_t root, unsigned samples)
Sample a scalar sub-circuit samples times and return the draws.
double importanceEvidence(const GenericCircuit &gc, gate_t evidence, unsigned samples)
Marginal likelihood P(data) of evidence: the mean raw importance weight over samples prior draws.
std::optional< double > enumerateBooleanProbability(const GenericCircuit &gc, gate_t root, unsigned max_inputs)
The probability of root, exactly, over the possible worlds of the circuit as it is: the alternative t...
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::vector< double > posteriorResample(const WeightedPosterior &post, unsigned n)
Sampling-importance-resampling: draw n posterior samples from a weighted particle set (proportional t...
double parseDoubleStrict(const std::string &s)
Strictly parse s as a double.
std::vector< double > monteCarloJointDistribution(const GenericCircuit &gc, const std::vector< gate_t > &cmps, unsigned samples)
Estimate the joint distribution of cmps via Monte Carlo.
bool circuitHasNestedAggValue(const GenericCircuit &gc, gate_t root)
Whether a contribution of an aggregate is itself an aggregate result (a gate_semimod whose M side is ...
double monteCarloRVStopping(const GenericCircuit &gc, gate_t root, double eps, double delta, unsigned long max_samples, unsigned long &samples_used, bool &reached_target)
Whole-circuit (eps,delta)-relative probability via the Dagum-Karp-Luby-Ross stopping rule.
std::unique_ptr< Distribution > makeDistribution(const DistributionSpec &spec)
Construct the per-family Distribution for a parsed spec.
std::mt19937_64 seedRng()
The shared Monte Carlo generator, seeded from the provsql.monte_carlo_seed GUC (-1 = non-deterministi...
bool circuitHasUnresolvedSampleableAgg(const GenericCircuit &gc, gate_t root)
Whether a surviving gate_agg exists and every one is sample-faithful (SUM / AVG / MIN / MAX / COUNT –...
static std::optional< std::vector< gate_t > > enumerableInputs(const GenericCircuit &gc, gate_t root, std::optional< gate_t > event, unsigned max_inputs)
The Boolean inputs the worlds of root (and event) range over, or nullopt when another random source,...
ConditionalScalarSamples monteCarloConditionalScalarSamples(const GenericCircuit &gc, gate_t root, gate_t event_root, unsigned samples)
Rejection-sample root conditioned on event_root.
bool circuitHasFixpoint(const GenericCircuit &gc, gate_t root)
Whether a gate_fixpoint (a row of a recursion on cyclic data) is reachable from root.
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...
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 monteCarloRV(const GenericCircuit &gc, gate_t root, unsigned samples)
Run Monte Carlo on a circuit that may contain gate_rv leaves.
std::optional< std::vector< double > > try_truncated_closed_form_sample(const GenericCircuit &gc, gate_t root, gate_t event_root, unsigned n)
Try to draw n exact samples from the conditional distribution of root given event_root via closed-for...
WeightedPosterior importanceSampleConditional(const GenericCircuit &gc, gate_t root, gate_t evidence, unsigned samples)
Self-normalised importance sampling of root given evidence.
std::optional< TruncatedSingleRv > matchTruncatedSingleRv(const GenericCircuit &gc, gate_t root, std::optional< gate_t > event_root)
Detect a closed-form, optionally-truncated single-RV shape.
std::vector< double > definedDraws(const std::vector< std::optional< double > > &samples)
The draws of samples that have a value, in order.
bool circuitHasRV(const GenericCircuit &gc, gate_t root)
Walk the circuit reachable from root looking for any gate_rv.
bool circuitHasObserve(const GenericCircuit &gc, gate_t root)
Whether the circuit reachable from root contains a gate_observe – the signal that a conditioning even...
int provsql_monte_carlo_seed
Seed for the Monte Carlo sampler; -1 means non-deterministic (std::random_device); controlled by the ...
Definition provsql.c:125
bool provsql_interrupted
Set by provsql_sigint_handler: this backend received a cancel.
Definition provsql.c:111
Cancellation of the long C++ evaluation loops.
void provsql_poll_interrupt()
Throw where an evaluation is to stop, its query cancelled.
const char * gate_type_name[]
Names of gate types.
provsql_arith_op
Arithmetic operator tags used by gate_arith.
@ PROVSQL_ARITH_PERCENTILE
continuous percentile (order-statistic aggregate): wires are interleaved [ind_1, x_1,...
@ PROVSQL_ARITH_DIV
binary, child0 / child1
@ PROVSQL_ARITH_ASFLOAT8
unary, child0 as double precision
@ PROVSQL_ARITH_LN
unary, natural logarithm of child0 (a negative draw raises at evaluation)
@ PROVSQL_ARITH_ROUND
child0 rounded half away from zero, to child1 decimal digits where a second child is given (SQL round...
@ PROVSQL_ARITH_PLUS
n-ary, sum of children
@ PROVSQL_ARITH_POW
binary, child0 ^ child1 (real branch only: a negative base drawn with a non-integer exponent raises a...
@ PROVSQL_ARITH_ABS
unary, |child0|
@ PROVSQL_ARITH_FLOOR
unary, greatest integer <= child0
@ 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_CEIL
unary, least integer >= child0
@ PROVSQL_ARITH_EXP
unary, e^child0
@ PROVSQL_ARITH_TIMES
n-ary, product of children
@ PROVSQL_ARITH_MIN
n-ary, min of children (order statistic; least / min aggregate)
@ PROVSQL_ARITH_MAX
n-ary, max of children (order statistic; greatest / max aggregate)
@ PROVSQL_ARITH_ASFLOAT4
unary, child0 as real reads it
@ gate_observe
Latent-variable observation (likelihood-weighting evidence): one wire → an observed bare gate_rv leaf...
@ gate_rv
Continuous random-variable leaf (extra encodes distribution).
@ gate_case
N-ary guarded selection over scalar (RV) children: wires are [guard_1, value_1, .....
@ gate_annotation
Transparent single-child wrapper carrying a query-level annotation in extra (inversion-free certifica...
@ gate_fixpoint
Component of the least solution of an equation system: one wire to a gate_fixsystem,...
@ gate_fixsystem
Linear equation system x_i = f_i(x) of a recursive query, one equation per derived tuple: wires [x_1,...
@ gate_mixture
Probabilistic mixture: three wires [p_token (gate_input Bernoulli), x_token, y_token]; samples x when...
@ gate_arith
n-ary arithmetic gate over scalar-valued children (info1 holds operator tag)
@ gate_assumed
Structural marker over a single child whose sub-circuit was computed under a Boolean-provenance assum...
#define PROVSQL_GATE_NULL_UUID
UUID of the constant value gate standing for the NULL value, the result of gate_null().
#define PROVSQL_AGG_SCALAR_FLAG
Scalar-aggregation flag, stored in the upper bit of a gate_agg's info2 (whose low 31 bits hold the ag...
ValueType getType() const
Return the runtime type tag of this value.
std::variant< long, double, bool, std::string, std::vector< long >, std::vector< double >, std::vector< bool >, std::vector< std::string > > v
The variant holding the actual value.
std::vector< std::vector< std::vector< gate_t > > > b
Constant part of each equation.
std::size_t n
Number of unknowns.
std::vector< std::vector< std::pair< std::size_t, std::vector< gate_t > > > > out
Terms, by unknown read.
Outcome of a conditional coupled-pair Monte Carlo pass: xs[i] / ys[i] are the two roots' values from ...
std::vector< std::optional< double > > xs
std::vector< std::optional< double > > ys
Outcome of a conditional Monte Carlo sampling pass.
std::vector< std::optional< double > > accepted
Outcome of a likelihood-weighting (importance-sampling) pass.
double weight_sq_sum
Sum of w^2 over all attempted draws.
unsigned attempted
Number of prior draws.
std::vector< std::pair< double, double > > particles
(x, w) with w > 0.
double weight_sum
Sum of w over all attempted draws.