50#include "utils/uuid.h"
51#include "utils/array.h"
52#include "catalog/pg_type.h"
65#include <unordered_map>
66#include <unordered_set>
74constexpr double kNaN = std::numeric_limits<double>::quiet_NaN();
75constexpr int kGrid = 400;
78void collectRvLeaves(
const GenericCircuit &gc,
gate_t g,
79 std::unordered_set<gate_t> &out)
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;
95double evalWithVar(
const GenericCircuit &gc,
gate_t g,
gate_t var,
double val)
99 return (g == var) ? val :
kNaN;
102 catch (
const CircuitException &) {
return kNaN; }
106 auto ev = [&](
gate_t c) {
return evalWithVar(gc, c, var, val); };
109 double s = 0.0;
for (
gate_t c : w) s += ev(c);
return s;
112 double p = 1.0;
for (
gate_t c : w) p *= ev(c);
return p;
115 return (w.size() == 2) ? ev(w[0]) - ev(w[1]) :
kNaN;
119 return (w.size() == 2 && ev(w[1]) != 0.0) ? ev(w[0]) / ev(w[1])
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;
141std::optional<std::pair<double, double>>
142affineInVar(
const GenericCircuit &gc,
gate_t g,
gate_t var)
144 using R = std::optional<std::pair<double, double>>;
147 return (g == var) ? R({1.0, 0.0}) : std::nullopt;
150 catch (
const CircuitException &) {
return std::nullopt; }
156 double s = 0.0, c = 0.0;
158 auto a = affineInVar(gc, ch, var);
159 if (!a)
return std::nullopt;
160 s += a->first; c += a->second;
165 double s = 0.0, c = 1.0;
167 auto a = affineInVar(gc, ch, var);
168 if (!a)
return std::nullopt;
170 if (s != 0.0 && a->first != 0.0)
return std::nullopt;
171 const double ns = s * a->second + c * a->first;
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});
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});
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});
207 const DistributionFamily *family;
219 std::shared_ptr<Distribution> dist;
221 double slope = 0.0, intercept = 0.0;
229 std::unique_ptr<Distribution> shared_dist;
231 std::vector<Term> terms;
236bool reduceIndicator(
const GenericCircuit &gc,
gate_t k_gate,
237 double &bern,
gate_t &cmp_out)
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();
252 const double p = gc.
getProb(g);
253 if (std::isnan(p))
return false;
258 if (have_cmp)
return false;
281std::optional<CollapsePlan>
282buildCollapsePlan(
const GenericCircuit &gc,
gate_t agg)
289 const auto &children = gc.
getWires(agg);
290 if (children.empty())
return std::nullopt;
297 std::vector<Raw> raws;
298 raws.reserve(children.size());
299 std::unordered_map<gate_t, unsigned> leaf_rows;
301 for (
gate_t sm : children) {
304 if (smw.size() != 2)
return std::nullopt;
308 catch (
const CircuitException &) {
return std::nullopt; }
312 if (!reduceIndicator(gc, smw[0], bern, cmp))
return std::nullopt;
314 if (cw.size() != 2)
return std::nullopt;
317 if (!ok)
return std::nullopt;
319 raws.push_back({bern, value, cw[0], cw[1], op});
321 std::unordered_set<gate_t> rowleaves;
322 collectRvLeaves(gc, cmp, rowleaves);
323 for (
gate_t l : rowleaves) ++leaf_rows[l];
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;
333 if (!shared_spec)
return std::nullopt;
336 if (!shared_dist->integrationRange(lo, hi) || !(hi > lo))
return std::nullopt;
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);
346 shared_side =
static_cast<gate_t>(0);
348 auto is_per_row = [&](
gate_t side,
const std::unordered_set<gate_t> &f) {
351 auto is_shared_side = [&](
const std::unordered_set<gate_t> &f) {
352 return f.empty() || (f.size() == 1 && f.count(shared));
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);
365 if (!spec)
return std::nullopt;
366 Term term{spec->family, spec->p1, spec->p2, shared_side, op,
368 term.dist = std::shared_ptr<Distribution>(
369 spec->family->factory(spec->p1, spec->p2));
370 if (
auto aff = affineInVar(gc, shared_side, shared)) {
372 term.slope = aff->first;
373 term.intercept = aff->second;
375 terms.push_back(std::move(term));
380 plan.shared = shared;
381 plan.shared_dist = std::move(shared_dist);
384 plan.terms = std::move(terms);
390struct Grid { std::vector<double> node, weight; };
391std::optional<Grid> pdfGrid(
const Distribution &d,
double lo,
double hi)
393 if (!(hi > lo))
return std::nullopt;
394 const double dx = (hi - lo) / (kGrid - 1);
396 grid.node.resize(kGrid);
397 grid.weight.resize(kGrid);
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;
407 if (!(wsum > 0.0))
return std::nullopt;
408 for (
double &w : grid.weight) w /= wsum;
414bool perNodeProbs(
const GenericCircuit &gc,
const CollapsePlan &plan,
415 double b, std::vector<double> &q)
418 q.reserve(plan.terms.size());
419 for (
const auto &t : plan.terms) {
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;
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;
436 if (qi < 0.0) qi = 0.0;
else if (qi > 1.0) qi = 1.0;
443std::vector<double> poissonBinomialPmf(
const std::vector<double> &q)
445 std::vector<double> pmf(q.size() + 1, 0.0);
447 std::size_t filled = 0;
448 for (
double qi : q) {
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);
462std::optional<std::vector<double>>
463aggCollapsedPmf(
const GenericCircuit &gc,
gate_t agg)
465 auto plan = buildCollapsePlan(gc, agg);
466 if (!plan)
return std::nullopt;
470 for (
const auto &t : plan->terms)
471 if (t.value != 1.0)
return std::nullopt;
473 auto grid = pdfGrid(*plan->shared_dist, plan->lo, plan->hi);
474 if (!grid)
return std::nullopt;
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];
490std::optional<std::pair<double, double>>
493 auto plan = buildCollapsePlan(gc, agg);
494 if (!plan)
return std::nullopt;
496 auto grid = pdfGrid(*plan->shared_dist, plan->lo, plan->hi);
497 if (!grid)
return std::nullopt;
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;
504 for (std::size_t i = 0; i < plan->terms.size(); ++i) {
505 const double v = plan->terms[i].value, qi = q[i];
507 var_b += v * v * qi * (1.0 - qi);
509 const double w = grid->weight[gi];
511 m2 += w * (var_b + mean_b * mean_b);
513 return std::make_pair(m1, m2);
519 if (k == 0)
return 1.0;
520 if (k > 2)
return std::nullopt;
525 if (!m)
return std::nullopt;
526 return (k == 1) ? m->first : m->second;
533 if (k == 0)
return 1.0;
534 if (k > 2)
return std::nullopt;
541 const auto &ew = gc.
getWires(event);
542 if (ew.size() != 2)
return std::nullopt;
546 for (
int i = 0; i < 2; ++i) {
547 const gate_t s = ew[i], o = ew[1 - i];
549 ygate = s; cagg = o;
break;
552 if (ygate ==
static_cast<gate_t>(0))
return std::nullopt;
556 if (!ytmpl)
return std::nullopt;
557 if (!ytmpl->family->factory(1.0, 1.0)->isDiscrete())
return std::nullopt;
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;
565 auto Cpmf = aggCollapsedPmf(gc, cagg);
566 if (!Cpmf)
return std::nullopt;
570 if (!rspec)
return std::nullopt;
573 if (!rdist->integrationRange(rlo, rhi))
return std::nullopt;
574 auto rgrid = pdfGrid(*rdist, rlo, rhi);
575 if (!rgrid)
return std::nullopt;
577 const auto &ywires = gc.
getWires(ygate);
580 if (
static_cast<std::size_t
>(p.
wire_slot) >= ywires.size())
return kNaN;
581 return evalWithVar(gc, ywires[p.
wire_slot], target, 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);
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; }
607 if (degenerate)
continue;
608 const double w = rgrid->weight[gi];
613 if (!(Z > 0.0))
return std::nullopt;
614 return (k == 1) ? (N1 / Z) : (N2 / Z);
635 const int32 k = PG_GETARG_INT32(1);
637 provsql_error(
"agg_collapsed_moment: k must be non-negative (got %d)", k);
641 static_cast<unsigned>(k));
644 return Float8GetDatum(*r);
645 }
catch (
const std::exception &e) {
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) {
715 const auto &rows = gc.
getWires(root);
716 const size_t n = rows.size();
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]; }
725 std::map<gate_t, size_t> owner;
726 for (
size_t i = 0; i < n; ++i) {
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;
740 auto it = owner.find(g);
741 if (it == owner.end())
744 parent[find(i)] = find(it->second);
752 std::map<size_t, int32> number;
753 std::vector<Datum> elems(n);
754 for (
size_t i = 0; i < n; ++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);
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) {
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.
@ COUNT
COUNT(*) or COUNT(expr) → integer.
@ SUM
SUM → integer or float.
ComparisonOperator
SQL comparison operators used in gate_cmp circuit gates.
@ LE
Less than or equal (<=).
@ GE
Greater than or equal (>=).
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.
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.
gateType getGateType(gate_t g) const
Return the type of gate g.
gate_t getGate(const uuid &u)
Return (or create) the gate associated with UUID u.
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...
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].