ProvSQL C/C++ API
Adding support for provenance and uncertainty management to PostgreSQL databases
Loading...
Searching...
No Matches
DTree.cpp
Go to the documentation of this file.
1/**
2 * @file DTree.cpp
3 * @brief Implementation of the d-tree anytime interval-bounds engine.
4 */
5#include <algorithm>
6#include <chrono>
7#include <optional>
8#include <functional>
9#include <map>
10#include <set>
11#include <string>
12#include <type_traits>
13#include <unordered_map>
14#include <utility>
15#include <vector>
16
17// Keep the Boost-including headers ahead of the PostgreSQL block: port.h
18// #defines snprintf to pg_snprintf, which breaks Boost headers (>= 1.79)
19// whose inline code calls std::snprintf (boost/assert/source_location.hpp).
20#include "BooleanCircuit.h"
21#include "DTree.h"
22
23extern "C" {
24#include "provsql_utils.h" // provsql_interrupted
25#include "miscadmin.h" // check_stack_depth
26}
27#include "provsql_interrupt.h" // provsql_poll_interrupt
28
29namespace provsql {
30
31namespace {
32
33using Clauses = std::vector<std::set<gate_t> >;
34
35/**
36 * @brief Order-sensitive hash of a @e canonical clause set.
37 *
38 * The memo only ever sees clause sets that @c recurse has already
39 * subsumption-reduced and sorted, so two logically equal residual DNFs have an
40 * identical @c Clauses representation (same clause order, each clause a sorted
41 * @c std::set) and therefore hash identically. Collisions fall back to the
42 * vector/set @c operator== the @c unordered_map applies, so the hash needs only
43 * to be well-distributed, not perfect -- the lookup stays exact. This avoids
44 * a @c std::map whose @c O(log n) lookups would each run a lexicographic
45 * compare over @c vector<set<gate_t>> (a costly per-node key operation);
46 * the hash makes lookups average @c O(clause-set size).
47 */
48struct ClausesHash {
49 std::size_t operator()(const Clauses &cls) const
50 {
51 std::size_t h = 1469598103934665603ull; // FNV-1a offset basis
52 std::hash<gate_t> gh;
53 for(const auto &cl : cls) {
54 std::size_t ch = 1099511628211ull; // per-clause FNV prime seed
55 for(gate_t v : cl)
56 ch = ch * 31u + gh(v);
57 // boost::hash_combine-style mix so clause order matters and the
58 // per-clause hashes do not simply XOR-cancel.
59 h ^= ch + 0x9e3779b97f4a7c15ull + (h << 6) + (h >> 2);
60 }
61 return h;
62 }
63};
64
65/**
66 * @brief Shared recursion state: the circuit and the subproblem memo.
67 *
68 * The memo turns the Shannon/independence recursion from a tree into a shared
69 * DAG: distinct paths that reach the same residual DNF (very common on path- and
70 * cycle-shaped lineage) are computed once. Without it the recursion is
71 * exponential even on bounded treewidth; with it, the number of distinct
72 * residual clause sets is polynomial there, matching the paper's tractable-query
73 * behaviour.
74 *
75 * The key is the @e canonical clause set (subsumption-reduced, then sorted), and
76 * the value is the subproblem's @b exact probability. An entry is therefore
77 * sound to reuse for @e any request (an exact value satisfies any width target),
78 * but it is only ever WRITTEN on an exact request (@c max_width == 0), where the
79 * whole recursion is exact -- an early-stopped interval is budget-dependent and
80 * must not be cached. Hashed (@c ClausesHash) for average-constant lookup.
81 */
82struct DTreeContext {
83 const BooleanCircuit &c;
84 std::unordered_map<Clauses, double, ClausesHash> memo;
85 // Speculative-execution budget: count subproblems (recursion entries) and bail
86 // when they exceed @c budget, so the chooser re-ranks the d-tree at a higher
87 // cost and tries the next method. @c budget == 0 means unbounded. Deterministic (a function
88 // of the circuit), so the chosen method is reproducible.
89 unsigned long steps = 0;
90 unsigned long budget = 0;
91 // Wall-clock backstop to the step budget (see dtreeBounds); unset = none.
92 std::optional<std::chrono::steady_clock::time_point> deadline;
93};
94
95/** Throw past the step budget, or (checked every 256 steps) past the
96 * wall-clock deadline of @p ctx. */
97template<typename Ctx>
98void checkBudget(const Ctx &ctx)
99{
100 if(ctx.budget && ctx.steps > ctx.budget)
101 throw CircuitException("d-tree: cost budget exceeded");
102 if(ctx.deadline && (ctx.steps & 255) == 0
103 && std::chrono::steady_clock::now() > *ctx.deadline)
104 throw CircuitException("d-tree: time budget exceeded");
105}
106
107/** The deadline @p budget_ms from now, or none for 0. */
108std::optional<std::chrono::steady_clock::time_point> deadlineIn(double budget_ms)
109{
110 if(budget_ms <= 0.)
111 return std::nullopt;
112 return std::chrono::steady_clock::now()
113 + std::chrono::microseconds(static_cast<long long>(budget_ms * 1000.));
114}
115
116/**
117 * @brief Drop subsumed clauses from a monotone DNF.
118 *
119 * For a monotone DNF a clause is the conjunction of its (positive) literals, so
120 * if clause @c A is a subset of clause @c B then @c B implies @c A and
121 * @c A∨B ≡ A: the superset @c B is redundant. Keeping only the minimal clauses
122 * (and a single copy of duplicates) preserves the function and shrinks the work
123 * Shannon expansion generates. @c O(m^2) set-inclusion tests.
124 */
125void removeSubsumed(Clauses &clauses)
126{
127 // Ascending size, so a subsumer (subset) is always considered before any
128 // clause it could subsume.
129 std::sort(clauses.begin(), clauses.end(),
130 [](const std::set<gate_t> &a, const std::set<gate_t> &b) {
131 return a.size() < b.size();
132 });
133 Clauses kept;
134 kept.reserve(clauses.size());
135 for(auto &c : clauses) {
136 bool subsumed = false;
137 for(const auto &k : kept)
138 // k ⊆ c (k has size <= c by the sort), so c is subsumed by k.
139 if(std::includes(c.begin(), c.end(), k.begin(), k.end())) {
140 subsumed = true;
141 break;
142 }
143 if(!subsumed)
144 kept.push_back(std::move(c));
145 }
146 clauses = std::move(kept);
147}
148
149/**
150 * @brief Partition a DNF into independent-or components.
151 *
152 * Two clauses are connected when their supports share an input leaf; the
153 * connected components are sub-DNFs over disjoint variable sets, so the whole
154 * DNF is their independent disjunction. A single component means the
155 * disjunction does not split here. Union-find over the clause/variable
156 * incidence, @c O(m·avg-clause·α).
157 */
158std::vector<Clauses> components(const Clauses &clauses)
159{
160 const size_t m = clauses.size();
161 std::vector<size_t> parent(m);
162 for(size_t i = 0; i < m; ++i)
163 parent[i] = i;
164 std::function<size_t(size_t)> find = [&](size_t x) {
165 while(parent[x] != x) {
166 parent[x] = parent[parent[x]];
167 x = parent[x];
168 }
169 return x;
170 };
171 std::unordered_map<gate_t, size_t> owner; // first clause seen carrying a leaf
172 for(size_t i = 0; i < m; ++i)
173 for(gate_t v : clauses[i]) {
174 auto it = owner.find(v);
175 if(it == owner.end())
176 owner.emplace(v, i);
177 else
178 parent[find(i)] = find(it->second);
179 }
180 // Group clauses by component root, keeping a deterministic order.
181 std::map<size_t, Clauses> groups;
182 for(size_t i = 0; i < m; ++i)
183 groups[find(i)].push_back(clauses[i]);
184 std::vector<Clauses> out;
185 out.reserve(groups.size());
186 for(auto &kv : groups)
187 out.push_back(std::move(kv.second));
188 return out;
189}
190
191/// The variable appearing in the most clauses (ties broken by smallest gate id
192/// for reproducibility) -- the Shannon-expansion pivot.
193gate_t mostFrequentVar(const Clauses &clauses)
194{
195 std::map<gate_t, size_t> freq; // ordered for a deterministic tie-break
196 for(const auto &c : clauses)
197 for(gate_t v : c)
198 ++freq[v];
199 gate_t best{};
200 size_t best_count = 0;
201 bool found = false;
202 for(const auto &kv : freq)
203 if(!found || kv.second > best_count) { // strict '>' keeps the smallest id
204 best = kv.first;
205 best_count = kv.second;
206 found = true;
207 }
208 return best;
209}
210
211DTreeInterval recurse(DTreeContext &ctx, Clauses clauses, double max_width)
212{
213 check_stack_depth();
215 throw CircuitException("Interrupted");
216 ++ctx.steps;
217 checkBudget(ctx);
218
219 if(clauses.empty())
220 return {0., 0.}; // empty disjunction is false
221 for(const auto &cl : clauses)
222 if(cl.empty())
223 return {1., 1.}; // a clause with no literals is true, so the DNF is true
224
225 // Canonicalise (subsumption-reduce, then sort) so equivalent residual DNFs
226 // share a memo key.
227 removeSubsumed(clauses);
228 std::sort(clauses.begin(), clauses.end());
229
230 // An exact request keeps max_width == 0 through every decomposition (the ⊗
231 // split passes 0/k = 0, ⊕ passes it unchanged), so the whole recursion is
232 // exact and every result is cacheable; an approximate request never writes.
233 const bool exact = (max_width <= 0.);
234 if(exact) {
235 const auto it = ctx.memo.find(clauses);
236 if(it != ctx.memo.end())
237 return {it->second, it->second};
238 }
239
240 // Cheap certified interval; stop as soon as it is narrow enough.
241 double L, U;
242 ctx.c.dnfBounds(clauses, L, U);
243 if(U - L <= max_width) {
244 if(exact)
245 ctx.memo.emplace(clauses, L); // independent leaf: L == U, exact
246 return {L, U};
247 }
248
249 DTreeInterval res;
250 // Independent-or: recurse on each component with a 1/k share of the budget
251 // (the OR width is at most the sum of component widths) and combine.
252 std::vector<Clauses> comps = components(clauses);
253 if(comps.size() > 1) {
254 double prod_lower = 1., prod_upper = 1.;
255 const double sub_width = max_width / static_cast<double>(comps.size());
256 for(auto &comp : comps) {
257 DTreeInterval r = recurse(ctx, std::move(comp), sub_width);
258 prod_lower *= (1. - r.lower);
259 prod_upper *= (1. - r.upper);
260 }
261 res = {1. - prod_lower, 1. - prod_upper};
262 } else {
263 // Shannon expansion on the most frequent variable x: Pr = Pr[x]·Pr[Phi|x=1]
264 // + (1-Pr[x])·Pr[Phi|x=0]. For a monotone DNF the cofactors are, on x=1,
265 // every clause with x stripped of x (the literal is satisfied) and every
266 // clause without x unchanged; on x=0, only the clauses not containing x
267 // survive. The same width budget passes to both branches (the mixture
268 // width is at most the larger branch's).
269 const gate_t x = mostFrequentVar(clauses);
270 const double px = ctx.c.getProb(x);
271 Clauses pos, neg;
272 pos.reserve(clauses.size());
273 neg.reserve(clauses.size());
274 for(const auto &cl : clauses) {
275 if(cl.count(x)) {
276 std::set<gate_t> reduced = cl;
277 reduced.erase(x);
278 pos.push_back(std::move(reduced));
279 } else {
280 pos.push_back(cl);
281 neg.push_back(cl);
282 }
283 }
284 const DTreeInterval rp = recurse(ctx, std::move(pos), max_width);
285 const DTreeInterval rn = recurse(ctx, std::move(neg), max_width);
286 res = {px * rp.lower + (1. - px) * rn.lower,
287 px * rp.upper + (1. - px) * rn.upper};
288 }
289
290 if(exact)
291 ctx.memo.emplace(clauses, res.lower); // exact (res.lower == res.upper)
292 return res;
293}
294
295} // namespace
296
297DTreeInterval dtreeBounds(const BooleanCircuit &c, Clauses clauses,
298 double max_width, unsigned long budget,
299 unsigned long *steps_out, double budget_ms)
300{
301 DTreeContext ctx{c, {}};
302 ctx.budget = budget;
303 ctx.deadline = deadlineIn(budget_ms);
304 DTreeInterval r = recurse(ctx, std::move(clauses), max_width);
305 if(steps_out)
306 *steps_out = ctx.steps;
307 return r;
308}
309
310// ===========================================================================
311// General-circuit d-tree: the same anytime engine on the BooleanCircuit DAG
312// (AND / OR / NOT / IN), so it drops the monotone-DNF shape restriction.
313// ===========================================================================
314
315namespace {
316
317using Assignment = std::unordered_map<gate_t, bool>;
318
319/// Static cone of genuine variable inputs (probability strictly in (0,1)); the
320/// memo + the recursion state for the general-circuit d-tree.
321struct GenContext {
322 const BooleanCircuit &c;
323 std::unordered_map<gate_t, std::set<gate_t> > footprint;
324 std::unordered_map<std::string, double> exactMemo; // exact subproblem values
325 // Speculative-execution budget (see DTreeContext): subproblem count + cap.
326 unsigned long steps = 0;
327 unsigned long budget = 0;
328 std::optional<std::chrono::steady_clock::time_point> deadline;
329};
330
331inline unsigned long gid(gate_t g)
332{
333 return static_cast<unsigned long>(
334 static_cast<std::underlying_type<gate_t>::type>(g));
335}
336
337/// Variable-input cone of @p g (inputs with probability in (0,1)). Constant
338/// inputs (probability 0 / 1) carry no variable and are dropped. A multivalued
339/// (BID) block is rewritten to independent Booleans by the dispatcher before
340/// this method runs (d-tree's handlesMultivalued() is false), so a MULIN gate
341/// should never reach here; the throw is a defensive net rather than the
342/// applicability signal it once was.
343/// unordered_map references survive rehash, so holding a child's reference while
344/// inserting the parent is safe.
345const std::set<gate_t> &footprintOf(GenContext &ctx, gate_t g)
346{
347 auto it = ctx.footprint.find(g);
348 if(it != ctx.footprint.end())
349 return it->second;
350 /* One cone per gate: on a large circuit whose gates read many inputs (that
351 * of a recursion on cyclic data, for one), this is quadratic in time and
352 * memory, so stay interruptible and within provsql.max_memory. */
354 std::set<gate_t> s;
355 switch(ctx.c.getGateType(g)) {
356 case BooleanGate::IN: {
357 const double p = ctx.c.getProb(g);
358 if(p > 0.0 && p < 1.0)
359 s.insert(g);
360 break;
361 }
362 case BooleanGate::AND:
363 case BooleanGate::OR:
364 case BooleanGate::NOT:
365 for(gate_t ch : ctx.c.getWires(g)) {
366 const auto &cs = footprintOf(ctx, ch);
367 s.insert(cs.begin(), cs.end());
368 }
369 break;
370 default: // MULIN / MULVAR / UNDETERMINED
371 throw CircuitException(
372 "d-tree: multivalued / undetermined gate not supported on the general "
373 "circuit path");
374 }
375 return ctx.footprint.emplace(g, std::move(s)).first->second;
376}
377
378/// Whether every variable in @p g's cone is assigned by @p A (so @p g has a
379/// definite truth value).
380bool determined(GenContext &ctx, gate_t g, const Assignment &A)
381{
382 for(gate_t v : footprintOf(ctx, g))
383 if(A.find(v) == A.end())
384 return false;
385 return true;
386}
387
388/// Truth value of a fully-determined gate under @p A.
389bool evalDet(GenContext &ctx, gate_t g, const Assignment &A)
390{
391 switch(ctx.c.getGateType(g)) {
392 case BooleanGate::IN: {
393 auto it = A.find(g);
394 if(it != A.end())
395 return it->second;
396 return ctx.c.getProb(g) >= 1.0; // a constant input (prob 0 or 1)
397 }
398 case BooleanGate::NOT:
399 return !evalDet(ctx, ctx.c.getWires(g)[0], A);
400 case BooleanGate::AND:
401 for(gate_t ch : ctx.c.getWires(g))
402 if(!evalDet(ctx, ch, A))
403 return false;
404 return true;
405 case BooleanGate::OR:
406 for(gate_t ch : ctx.c.getWires(g))
407 if(evalDet(ctx, ch, A))
408 return true;
409 return false;
410 default:
411 throw CircuitException("d-tree: unsupported gate in evalDet");
412 }
413}
414
415/// Partition @p live into groups whose free-variable footprints are pairwise
416/// disjoint (independent sub-formulas), preserving a deterministic order.
417std::vector<std::vector<gate_t> > genComponents(
418 GenContext &ctx, const std::vector<gate_t> &live, const Assignment &A)
419{
420 const size_t m = live.size();
421 std::vector<size_t> parent(m);
422 for(size_t i = 0; i < m; ++i)
423 parent[i] = i;
424 std::function<size_t(size_t)> find = [&](size_t x) {
425 while(parent[x] != x) { parent[x] = parent[parent[x]]; x = parent[x]; }
426 return x;
427 };
428 std::unordered_map<gate_t, size_t> owner; // first live index carrying a free var
429 for(size_t i = 0; i < m; ++i)
430 for(gate_t v : footprintOf(ctx, live[i])) {
431 if(A.find(v) != A.end())
432 continue; // assigned: not a shared free variable
433 auto it = owner.find(v);
434 if(it == owner.end())
435 owner.emplace(v, i);
436 else
437 parent[find(i)] = find(it->second);
438 }
439 std::map<size_t, std::vector<gate_t> > groups;
440 for(size_t i = 0; i < m; ++i)
441 groups[find(i)].push_back(live[i]);
442 std::vector<std::vector<gate_t> > out;
443 out.reserve(groups.size());
444 for(auto &kv : groups)
445 out.push_back(std::move(kv.second));
446 return out;
447}
448
449/// The free variable shared by the most members of @p live (ties -> smallest
450/// gate id), the Shannon-expansion pivot.
451gate_t genPivot(GenContext &ctx, const std::vector<gate_t> &live,
452 const Assignment &A)
453{
454 std::map<gate_t, size_t> freq; // ordered for a deterministic tie-break
455 for(gate_t c : live)
456 for(gate_t v : footprintOf(ctx, c))
457 if(A.find(v) == A.end())
458 ++freq[v];
459 gate_t best{};
460 size_t best_count = 0;
461 bool found = false;
462 for(const auto &kv : freq)
463 if(!found || kv.second > best_count) {
464 best = kv.first;
465 best_count = kv.second;
466 found = true;
467 }
468 return best;
469}
470
471DTreeInterval genBound(GenContext &ctx, gate_t g, const Assignment &A);
472
473/// Cheap sound interval of @c op over @p children under @p A: independent
474/// components compose exactly; within a component AND uses a Bonferroni lower /
475/// min upper and OR a max lower / union upper. Generalises @c dnfBounds.
476DTreeInterval genBoundGroup(GenContext &ctx, BooleanGate op,
477 const std::vector<gate_t> &children,
478 const Assignment &A)
479{
480 auto comps = genComponents(ctx, children, A);
481 double L = (op == BooleanGate::AND) ? 1.0 : 1.0; // AND: prod L; OR: prod (1-L)
482 double U = 1.0;
483 for(const auto &comp : comps) {
484 double gL, gU;
485 if(comp.size() == 1) {
486 DTreeInterval b = genBound(ctx, comp[0], A);
487 gL = b.lower;
488 gU = b.upper;
489 } else if(op == BooleanGate::AND) {
490 double sumL = 0.0;
491 gU = 1.0;
492 for(gate_t c : comp) {
493 DTreeInterval b = genBound(ctx, c, A);
494 sumL += b.lower;
495 gU = std::min(gU, b.upper);
496 }
497 gL = sumL - (static_cast<double>(comp.size()) - 1.0); // Bonferroni
498 if(gL < 0.0) gL = 0.0;
499 } else { // OR
500 double sumU = 0.0;
501 gL = 0.0;
502 for(gate_t c : comp) {
503 DTreeInterval b = genBound(ctx, c, A);
504 sumU += b.upper;
505 gL = std::max(gL, b.lower);
506 }
507 gU = (sumU > 1.0) ? 1.0 : sumU; // union bound
508 }
509 if(op == BooleanGate::AND) { L *= gL; U *= gU; }
510 else { L *= (1.0 - gL); U *= (1.0 - gU); }
511 }
512 if(op == BooleanGate::AND)
513 return {L, U};
514 return {1.0 - L, 1.0 - U};
515}
516
517DTreeInterval genBound(GenContext &ctx, gate_t g, const Assignment &A)
518{
519 switch(ctx.c.getGateType(g)) {
520 case BooleanGate::IN: {
521 auto it = A.find(g);
522 if(it != A.end())
523 return {it->second ? 1.0 : 0.0, it->second ? 1.0 : 0.0};
524 double p = ctx.c.getProb(g);
525 if(p < 0.0) p = 0.0;
526 if(p > 1.0) p = 1.0;
527 return {p, p};
528 }
529 case BooleanGate::NOT: {
530 DTreeInterval b = genBound(ctx, ctx.c.getWires(g)[0], A);
531 return {1.0 - b.upper, 1.0 - b.lower};
532 }
533 case BooleanGate::AND:
534 case BooleanGate::OR:
535 return genBoundGroup(ctx, ctx.c.getGateType(g), ctx.c.getWires(g), A);
536 default:
537 throw CircuitException("d-tree: unsupported gate in genBound");
538 }
539}
540
541/// Key identifying an exact subproblem: the (op, child set, assignment over the
542/// children's footprint) it depends on. @p single distinguishes a one-gate
543/// problem from a group with the same id.
544std::string exactKey(GenContext &ctx, char tag, BooleanGate op,
545 const std::vector<gate_t> &gates, const Assignment &A)
546{
547 std::string k(1, tag);
548 k += (op == BooleanGate::AND) ? 'A' : 'O';
549 std::set<gate_t> footunion;
550 for(gate_t g : gates) {
551 k += ':';
552 k += std::to_string(gid(g));
553 const auto &fp = footprintOf(ctx, g);
554 footunion.insert(fp.begin(), fp.end());
555 }
556 k += '|';
557 for(gate_t v : footunion) { // std::set: ascending, canonical
558 auto it = A.find(v);
559 if(it != A.end()) {
560 k += std::to_string(gid(v));
561 k += it->second ? '=' : '#';
562 }
563 }
564 return k;
565}
566
567DTreeInterval genRefineGroup(GenContext &ctx, BooleanGate op,
568 const std::vector<gate_t> &children,
569 Assignment &A, double w);
570
571DTreeInterval genRefine(GenContext &ctx, gate_t g, Assignment &A, double w)
572{
573 check_stack_depth();
575 throw CircuitException("Interrupted");
576 ++ctx.steps;
577 checkBudget(ctx);
578
579 if(determined(ctx, g, A)) {
580 double v = evalDet(ctx, g, A) ? 1.0 : 0.0;
581 return {v, v};
582 }
583 if(w > 0.0) {
584 DTreeInterval b = genBound(ctx, g, A);
585 if(b.upper - b.lower <= w)
586 return b;
587 }
588 switch(ctx.c.getGateType(g)) {
589 case BooleanGate::NOT: {
590 DTreeInterval r = genRefine(ctx, ctx.c.getWires(g)[0], A, w);
591 return {1.0 - r.upper, 1.0 - r.lower};
592 }
593 case BooleanGate::IN: {
594 const double p = ctx.c.getProb(g); // a single free variable
595 return {p, p};
596 }
597 case BooleanGate::AND:
598 case BooleanGate::OR:
599 return genRefineGroup(ctx, ctx.c.getGateType(g), ctx.c.getWires(g), A, w);
600 default:
601 throw CircuitException("d-tree: unsupported gate in genRefine");
602 }
603}
604
605DTreeInterval genRefineGroup(GenContext &ctx, BooleanGate op,
606 const std::vector<gate_t> &children,
607 Assignment &A, double w)
608{
609 check_stack_depth();
611 throw CircuitException("Interrupted");
612 ++ctx.steps;
613 checkBudget(ctx);
614
615 // Drop children fixed by A (and short-circuit on an absorbing one).
616 std::vector<gate_t> live;
617 live.reserve(children.size());
618 for(gate_t c : children) {
619 if(determined(ctx, c, A)) {
620 bool v = evalDet(ctx, c, A);
621 if(op == BooleanGate::AND && !v) return {0.0, 0.0};
622 if(op == BooleanGate::OR && v) return {1.0, 1.0};
623 // AND-true / OR-false: the identity, drop it
624 } else {
625 live.push_back(c);
626 }
627 }
628 if(live.empty())
629 return (op == BooleanGate::AND) ? DTreeInterval{1.0, 1.0}
630 : DTreeInterval{0.0, 0.0};
631
632 const bool exact = (w <= 0.0);
633 std::sort(live.begin(), live.end());
634 std::string key;
635 if(exact) {
636 key = exactKey(ctx, 'G', op, live, A);
637 auto it = ctx.exactMemo.find(key);
638 if(it != ctx.exactMemo.end())
639 return {it->second, it->second};
640 }
641
642 DTreeInterval res;
643 auto comps = genComponents(ctx, live, A);
644 if(comps.size() > 1) {
645 const double w_sub = w / static_cast<double>(comps.size());
646 double L = 1.0, U = 1.0; // AND: prod; OR: prod of (1-.)
647 for(auto &comp : comps) {
648 DTreeInterval r = genRefineGroup(ctx, op, comp, A, w_sub);
649 if(op == BooleanGate::AND) { L *= r.lower; U *= r.upper; }
650 else { L *= (1.0 - r.lower); U *= (1.0 - r.upper); }
651 }
652 res = (op == BooleanGate::AND) ? DTreeInterval{L, U}
653 : DTreeInterval{1.0 - L, 1.0 - U};
654 } else if(live.size() == 1) {
655 res = genRefine(ctx, live[0], A, w);
656 } else {
657 if(w > 0.0) {
658 DTreeInterval b = genBoundGroup(ctx, op, live, A);
659 if(b.upper - b.lower <= w)
660 return b; // approximate: do not memoise an early-stopped interval
661 }
662 const gate_t x = genPivot(ctx, live, A);
663 const double px = ctx.c.getProb(x);
664 A[x] = true;
665 DTreeInterval r1 = genRefineGroup(ctx, op, live, A, w);
666 A[x] = false;
667 DTreeInterval r0 = genRefineGroup(ctx, op, live, A, w);
668 A.erase(x);
669 res = {px * r1.lower + (1.0 - px) * r0.lower,
670 px * r1.upper + (1.0 - px) * r0.upper};
671 }
672
673 if(exact)
674 ctx.exactMemo.emplace(key, res.lower); // exact: lower == upper
675 return res;
676}
677
678} // namespace
679
681 double max_width, unsigned long budget,
682 unsigned long *steps_out, double budget_ms)
683{
684 GenContext ctx{c, {}, {}};
685 ctx.budget = budget;
686 ctx.deadline = deadlineIn(budget_ms);
687 Assignment A;
688 DTreeInterval r = genRefine(ctx, root, A, max_width);
689 if(steps_out)
690 *steps_out = ctx.steps;
691 return r;
692}
693
694} // namespace provsql
Boolean provenance circuit with support for knowledge compilation.
BooleanGate
Gate types for a Boolean provenance circuit.
@ NOT
Logical negation of a single child gate.
@ OR
Logical disjunction of child gates.
@ AND
Logical conjunction of child gates.
@ IN
Input (variable) gate representing a base tuple.
gate_t
Strongly-typed gate identifier.
Definition Circuit.h:53
Anytime interval-bounds probability for monotone DNFs (d-trees).
Boolean circuit for provenance formula evaluation.
DTreeInterval dtreeBounds(const BooleanCircuit &c, Clauses clauses, double max_width, unsigned long budget, unsigned long *steps_out, double budget_ms)
Definition DTree.cpp:297
DTreeInterval dtreeBoundsCircuit(const BooleanCircuit &c, gate_t root, double max_width, unsigned long budget, unsigned long *steps_out, double budget_ms)
Certified probability interval of an arbitrary Boolean circuit, refined to a target width (the d-tree...
Definition DTree.cpp:680
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.
Core types, constants, and utilities shared across ProvSQL.
A certified probability interval lower <= Pr <= upper.
Definition DTree.h:30