ProvSQL C/C++ API
Adding support for provenance and uncertainty management to PostgreSQL databases
Loading...
Searching...
No Matches
DTree.h
Go to the documentation of this file.
1/**
2 * @file DTree.h
3 * @brief Anytime interval-bounds probability for monotone DNFs (d-trees).
4 *
5 * Implements the recursive half of Olteanu, Huang & Koch, "Approximate
6 * Confidence Computation in Probabilistic Databases" (ICDE 2010): the cheap
7 * leaf bound @c BooleanCircuit::dnfBounds is refined by two decompositions --
8 * independent-or (connected components of the clause graph) and Shannon
9 * expansion (on the most frequent variable) -- until the certified interval is
10 * narrow enough, or exactly (interval width 0).
11 *
12 * The recursion operates purely on the @e clause-support sets of a monotone
13 * DNF: a clause is the conjunction of its positive input leaves, so the DNF is
14 * the list of those leaf sets, and every decomposition (component split, Shannon
15 * cofactor) maps a DNF to DNFs of the same representation.
16 */
17#ifndef DTREE_H
18#define DTREE_H
19
20#include <set>
21#include <vector>
22
23#include "Circuit.h" // gate_t
24
25class BooleanCircuit;
26
27namespace provsql {
28
29/// A certified probability interval @c lower <= Pr <= upper.
31 double lower;
32 double upper;
33};
34
35/**
36 * @brief Certified probability interval of a monotone DNF, refined to a target
37 * width (Olteanu-Huang-Koch d-tree).
38 *
39 * Refines @c BooleanCircuit::dnfBounds by independent-or decomposition and
40 * Shannon expansion until @c upper-lower <= @p max_width, propagating the width
41 * budget so the returned interval honours it: through Shannon the same budget
42 * passes to both cofactors (the mixture width is at most the larger branch's),
43 * through an independent-or of @c k components each gets @c max_width/k (the OR
44 * width is at most the sum of the component widths). @p max_width == 0 forces
45 * exact compilation (@c lower == upper).
46 *
47 * @param c Circuit owning the input marginals (@c getProb).
48 * @param clauses The DNF as per-clause input-leaf supports (consumed).
49 * @param max_width Absolute target for @c upper-lower (0 = exact).
50 * @param budget Subproblem (recursion-step) ceiling; 0 = unbounded. On
51 * overrun a @c CircuitException is thrown so the caller's
52 * cost-based chooser escalates to another method.
53 * @param steps_out If non-null, receives the number of recursion steps taken
54 * (for cost calibration).
55 * @return A sound interval with @c lower <= Pr[clauses] <= upper.
56 * @param budget_ms Wall-clock ceiling in ms, a backstop to @p budget where a
57 * subproblem costs far more than its calibration (heavily
58 * shared circuits); 0 = none. Throws past it.
59 */
61 std::vector<std::set<gate_t> > clauses,
62 double max_width, unsigned long budget = 0,
63 unsigned long *steps_out = nullptr,
64 double budget_ms = 0.);
65
66/**
67 * @brief Certified probability interval of an @e arbitrary Boolean circuit,
68 * refined to a target width (the d-tree generalised off monotone DNF).
69 *
70 * Same anytime engine as @c dtreeBounds, but recursing on the circuit DAG
71 * (@c AND / @c OR / @c NOT / @c IN) instead of a flat monotone-DNF clause set,
72 * so it applies to negation (@c EXCEPT / @c monus, encoded @c A AND NOT B),
73 * nested @c AND / @c OR (e.g. a CNF-shaped circuit), and arbitrary sharing.
74 *
75 * The cheap leaf bound generalises @c dnfBounds soundly to any gate: an
76 * independent-component split (children with disjoint free-variable footprints
77 * compose exactly), then a Bonferroni lower / min upper for @c AND, a max lower
78 * / union upper for @c OR, and a flip @c [1-U,1-L] for @c NOT. It is refined by
79 * independent-component decomposition and Shannon expansion on the most frequent
80 * shared free variable until @c upper-lower <= @p max_width (0 = exact). Every
81 * step keeps @c lower <= Pr <= upper (Shannon is an exact mixture; independence
82 * is over disjoint input cones, never overclaimed).
83 *
84 * Throws @c CircuitException on a multivalued (@c MULIN / @c MULVAR) or
85 * @c UNDETERMINED gate in the cone of @p root, so the caller falls back to
86 * another method on BID circuits.
87 *
88 * @param c Circuit (gate types, wiring, input marginals).
89 * @param root Root gate whose probability interval is computed.
90 * @param max_width Absolute target for @c upper-lower (0 = exact).
91 * @param budget Subproblem (recursion-step) ceiling; 0 = unbounded. On
92 * overrun a @c CircuitException is thrown so the caller's
93 * cost-based chooser escalates to another method.
94 * @param steps_out If non-null, receives the number of recursion steps taken
95 * (for cost calibration).
96 * @return A sound interval with @c lower <= Pr[root] <= upper.
97 * @param budget_ms Wall-clock ceiling in ms, a backstop to @p budget where a
98 * subproblem costs far more than its calibration (heavily
99 * shared circuits); 0 = none. Throws past it.
100 */
102 double max_width, unsigned long budget = 0,
103 unsigned long *steps_out = nullptr,
104 double budget_ms = 0.);
105
106} // namespace provsql
107
108#endif
Generic directed-acyclic-graph circuit template and gate identifier.
gate_t
Strongly-typed gate identifier.
Definition Circuit.h:53
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
A certified probability interval lower <= Pr <= upper.
Definition DTree.h:30