13#include <unordered_map>
33using Clauses = std::vector<std::set<gate_t> >;
49 std::size_t operator()(
const Clauses &cls)
const
51 std::size_t h = 1469598103934665603ull;
53 for(
const auto &cl : cls) {
54 std::size_t ch = 1099511628211ull;
56 ch = ch * 31u + gh(v);
59 h ^= ch + 0x9e3779b97f4a7c15ull + (h << 6) + (h >> 2);
83 const BooleanCircuit &c;
84 std::unordered_map<Clauses, double, ClausesHash> memo;
89 unsigned long steps = 0;
90 unsigned long budget = 0;
92 std::optional<std::chrono::steady_clock::time_point> deadline;
98void checkBudget(
const Ctx &ctx)
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");
108std::optional<std::chrono::steady_clock::time_point> deadlineIn(
double budget_ms)
112 return std::chrono::steady_clock::now()
113 + std::chrono::microseconds(
static_cast<long long>(budget_ms * 1000.));
125void removeSubsumed(Clauses &clauses)
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();
134 kept.reserve(clauses.size());
135 for(
auto &c : clauses) {
136 bool subsumed =
false;
137 for(
const auto &k : kept)
139 if(std::includes(c.begin(), c.end(), k.begin(), k.end())) {
144 kept.push_back(std::move(c));
146 clauses = std::move(kept);
158std::vector<Clauses> components(
const Clauses &clauses)
160 const size_t m = clauses.size();
161 std::vector<size_t> parent(m);
162 for(
size_t i = 0; i < m; ++i)
164 std::function<size_t(
size_t)> find = [&](
size_t x) {
165 while(parent[x] != x) {
166 parent[x] = parent[parent[x]];
171 std::unordered_map<gate_t, size_t> owner;
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())
178 parent[find(i)] = find(it->second);
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));
193gate_t mostFrequentVar(
const Clauses &clauses)
195 std::map<gate_t, size_t> freq;
196 for(
const auto &c : clauses)
200 size_t best_count = 0;
202 for(
const auto &kv : freq)
203 if(!found || kv.second > best_count) {
205 best_count = kv.second;
211DTreeInterval recurse(DTreeContext &ctx, Clauses clauses,
double max_width)
215 throw CircuitException(
"Interrupted");
221 for(
const auto &cl : clauses)
227 removeSubsumed(clauses);
228 std::sort(clauses.begin(), clauses.end());
233 const bool exact = (max_width <= 0.);
235 const auto it = ctx.memo.find(clauses);
236 if(it != ctx.memo.end())
237 return {it->second, it->second};
242 ctx.c.dnfBounds(clauses, L, U);
243 if(U - L <= max_width) {
245 ctx.memo.emplace(clauses, L);
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) {
258 prod_lower *= (1. - r.lower);
259 prod_upper *= (1. - r.upper);
261 res = {1. - prod_lower, 1. - prod_upper};
269 const gate_t x = mostFrequentVar(clauses);
270 const double px = ctx.c.getProb(x);
272 pos.reserve(clauses.size());
273 neg.reserve(clauses.size());
274 for(
const auto &cl : clauses) {
276 std::set<gate_t> reduced = cl;
278 pos.push_back(std::move(reduced));
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};
291 ctx.memo.emplace(clauses, res.lower);
298 double max_width,
unsigned long budget,
299 unsigned long *steps_out,
double budget_ms)
301 DTreeContext ctx{c, {}};
303 ctx.deadline = deadlineIn(budget_ms);
304 DTreeInterval r = recurse(ctx, std::move(clauses), max_width);
306 *steps_out = ctx.steps;
317using Assignment = std::unordered_map<gate_t, bool>;
323 std::unordered_map<gate_t, std::set<gate_t> > footprint;
324 std::unordered_map<std::string, double> exactMemo;
326 unsigned long steps = 0;
327 unsigned long budget = 0;
328 std::optional<std::chrono::steady_clock::time_point> deadline;
331inline unsigned long gid(
gate_t g)
333 return static_cast<unsigned long>(
334 static_cast<std::underlying_type<gate_t>::type
>(g));
345const std::set<gate_t> &footprintOf(GenContext &ctx,
gate_t g)
347 auto it = ctx.footprint.find(g);
348 if(it != ctx.footprint.end())
355 switch(ctx.c.getGateType(g)) {
357 const double p = ctx.c.getProb(g);
358 if(p > 0.0 && p < 1.0)
365 for(
gate_t ch : ctx.c.getWires(g)) {
366 const auto &cs = footprintOf(ctx, ch);
367 s.insert(cs.begin(), cs.end());
371 throw CircuitException(
372 "d-tree: multivalued / undetermined gate not supported on the general "
375 return ctx.footprint.emplace(g, std::move(s)).first->second;
380bool determined(GenContext &ctx,
gate_t g,
const Assignment &A)
382 for(
gate_t v : footprintOf(ctx, g))
383 if(A.find(v) == A.end())
389bool evalDet(GenContext &ctx,
gate_t g,
const Assignment &A)
391 switch(ctx.c.getGateType(g)) {
396 return ctx.c.getProb(g) >= 1.0;
399 return !evalDet(ctx, ctx.c.getWires(g)[0], A);
401 for(
gate_t ch : ctx.c.getWires(g))
402 if(!evalDet(ctx, ch, A))
406 for(
gate_t ch : ctx.c.getWires(g))
407 if(evalDet(ctx, ch, A))
411 throw CircuitException(
"d-tree: unsupported gate in evalDet");
417std::vector<std::vector<gate_t> > genComponents(
418 GenContext &ctx,
const std::vector<gate_t> &live,
const Assignment &A)
420 const size_t m = live.size();
421 std::vector<size_t> parent(m);
422 for(
size_t i = 0; i < m; ++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]; }
428 std::unordered_map<gate_t, size_t> owner;
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())
433 auto it = owner.find(v);
434 if(it == owner.end())
437 parent[find(i)] = find(it->second);
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));
451gate_t genPivot(GenContext &ctx,
const std::vector<gate_t> &live,
454 std::map<gate_t, size_t> freq;
456 for(
gate_t v : footprintOf(ctx, c))
457 if(A.find(v) == A.end())
460 size_t best_count = 0;
462 for(
const auto &kv : freq)
463 if(!found || kv.second > best_count) {
465 best_count = kv.second;
477 const std::vector<gate_t> &children,
480 auto comps = genComponents(ctx, children, A);
483 for(
const auto &comp : comps) {
485 if(comp.size() == 1) {
495 gU = std::min(gU, b.upper);
497 gL = sumL - (
static_cast<double>(comp.size()) - 1.0);
498 if(gL < 0.0) gL = 0.0;
505 gL = std::max(gL, b.lower);
507 gU = (sumU > 1.0) ? 1.0 : sumU;
510 else { L *= (1.0 - gL); U *= (1.0 - gU); }
514 return {1.0 - L, 1.0 - U};
519 switch(ctx.c.getGateType(g)) {
523 return {it->second ? 1.0 : 0.0, it->second ? 1.0 : 0.0};
524 double p = ctx.c.getProb(g);
531 return {1.0 - b.upper, 1.0 - b.lower};
535 return genBoundGroup(ctx, ctx.c.getGateType(g), ctx.c.getWires(g), A);
537 throw CircuitException(
"d-tree: unsupported gate in genBound");
544std::string exactKey(GenContext &ctx,
char tag,
BooleanGate op,
545 const std::vector<gate_t> &gates,
const Assignment &A)
547 std::string k(1, tag);
549 std::set<gate_t> footunion;
552 k += std::to_string(gid(g));
553 const auto &fp = footprintOf(ctx, g);
554 footunion.insert(fp.begin(), fp.end());
557 for(
gate_t v : footunion) {
560 k += std::to_string(gid(v));
561 k += it->second ?
'=' :
'#';
568 const std::vector<gate_t> &children,
569 Assignment &A,
double w);
575 throw CircuitException(
"Interrupted");
579 if(determined(ctx, g, A)) {
580 double v = evalDet(ctx, g, A) ? 1.0 : 0.0;
585 if(b.upper - b.lower <= w)
588 switch(ctx.c.getGateType(g)) {
590 DTreeInterval r = genRefine(ctx, ctx.c.getWires(g)[0], A, w);
591 return {1.0 - r.upper, 1.0 - r.lower};
594 const double p = ctx.c.getProb(g);
599 return genRefineGroup(ctx, ctx.c.getGateType(g), ctx.c.getWires(g), A, w);
601 throw CircuitException(
"d-tree: unsupported gate in genRefine");
606 const std::vector<gate_t> &children,
607 Assignment &A,
double w)
611 throw CircuitException(
"Interrupted");
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);
632 const bool exact = (w <= 0.0);
633 std::sort(live.begin(), live.end());
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};
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;
647 for(
auto &comp : comps) {
650 else { L *= (1.0 - r.lower); U *= (1.0 - r.upper); }
654 }
else if(live.size() == 1) {
655 res = genRefine(ctx, live[0], A, w);
659 if(b.upper - b.lower <= w)
662 const gate_t x = genPivot(ctx, live, A);
663 const double px = ctx.c.getProb(x);
669 res = {px * r1.lower + (1.0 - px) * r0.lower,
670 px * r1.upper + (1.0 - px) * r0.upper};
674 ctx.exactMemo.emplace(key, res.lower);
681 double max_width,
unsigned long budget,
682 unsigned long *steps_out,
double budget_ms)
684 GenContext ctx{c, {}, {}};
686 ctx.deadline = deadlineIn(budget_ms);
690 *steps_out = ctx.steps;
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.
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)
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...
bool provsql_interrupted
Set by provsql_sigint_handler: this backend received a cancel.
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.