ProvSQL C/C++ API
Adding support for provenance and uncertainty management to PostgreSQL databases
Loading...
Searching...
No Matches
ProbabilityMethod.h
Go to the documentation of this file.
1/**
2 * @file ProbabilityMethod.h
3 * @brief Catalog of probability-evaluation methods (Strategy + registry).
4 *
5 * Each probability-evaluation algorithm is a first-class @c ProbabilityMethod
6 * object that declares its own guarantee, applicability and (eventually) cost,
7 * instead of that knowledge being smeared across a string-switch dispatcher.
8 * The @c MethodCatalog is the registry the dispatcher in
9 * @c probability_evaluate.cpp consults: a named request resolves through
10 * @c byName(); the default (empty-method) request runs @c chooseAndRun(), the
11 * cost-based chooser, as its @c Exact-tolerance instance: a uniform-cost search
12 * over the default-chain methods that the tolerance admits.
13 *
14 * This header carries only the public interface. The concrete method classes,
15 * the @c EvalContext that threads the per-evaluation circuit state, and the
16 * catalog registration all live in @c probability_evaluate.cpp, where the
17 * file-local evaluation helpers they need are in scope.
18 *
19 * The design (the method-catalog / three-path chooser) is documented at
20 * length in @c doc/source/dev/probability-evaluation.rst.
21 */
22#ifndef PROVSQL_PROBABILITY_METHOD_H
23#define PROVSQL_PROBABILITY_METHOD_H
24
25#include <memory>
26#include <string>
27#include <vector>
28
29// d-DNNF artifact (defined in dDNNF.h). The d-D-producing methods can return it
30// via buildDD(), and the catalog's chooseAndBuildDD / makeDDAuto cost-select a
31// construction route and return the artifact for the default request of shapley
32// and banzhaf -- the same selection the probability chooser already makes among
33// interpret-as-dd / tree-decomposition / compilation. compile_to_ddnnf and
34// ddnnf_stats keep the external-compilation default, through makeDDByName.
35class dDNNF;
36class BooleanCircuit;
37class GenericCircuit;
38enum class gate_t : size_t;
39
40namespace provsql {
41
42/**
43 * @brief The contract the user grants -- the "path".
44 *
45 * @c Exact is tolerance @c (0,0); @c Relative promises @c (1±epsilon) with
46 * confidence @c 1-delta; @c Additive promises @c |p̂-p| <= epsilon with the same
47 * confidence. Admissible method sets nest @c Exact ⊂ @c Relative ⊂ @c Additive.
48 *
49 * The tolerance drives method selection on the auto-chooser's path: only the
50 * methods whose guarantee is at least as tight as the request are admissible,
51 * and their estimated costs may depend on it. Named methods dispatch by name.
52 */
54
55struct Tolerance {
57 double epsilon = 0.;
58 double delta = 0.;
59};
60
61/**
62 * @brief A circuit feature a method's cost/applicability estimate depends on,
63 * but that is not free to acquire.
64 *
65 * Acquiring a feature has a cost (modelled by @c EvalContext::featureCost), and
66 * the chooser acquires one lazily only when no already-known method is cheaper
67 * than acquiring it -- so a feature costing more than the cheapest ready method
68 * is never computed: a read-once circuit runs @c independent without
69 * @c TreewidthProxy. @c DnfShape costs less than @c independent, so it is
70 * computed first. Free/O(1) features (\#inputs, an inversion-free certificate)
71 * are not modelled here -- they are read eagerly.
72 *
73 * @c DnfShape is a linear @c dnfShape walk. @c TreewidthProxy is a cheap
74 * (@c O(V+E)) degeneracy lower bound on the circuit's treewidth that gates
75 * @c tree-decomposition's cost -- it rules the method out when the bound already
76 * exceeds the build's limit, while the bounded-treewidth build can still fail
77 * implicitly when the bound is inconclusive.
78 */
80
81/// Per-evaluation circuit state threaded to a method's @c evaluate (defined in
82/// @c probability_evaluate.cpp, where the Boolean/Generic circuit machinery is
83/// in scope).
84struct EvalContext;
85
86/**
87 * @brief Strategy interface: one concrete subclass per probability method.
88 *
89 * @c evaluate throws @c CircuitException when the method cannot be applied to
90 * the circuit; @c chooseAndRun relies on that to move on to the next-cheapest
91 * method, while @c byName lets it propagate (an explicitly named method
92 * reports the failure instead of silently falling back).
93 */
95public:
96 virtual ~ProbabilityMethod() = default;
97
98 /// Stable identifier used for @c byName lookup and the
99 /// @c provsql.last_eval_method report.
100 virtual std::string name() const = 0;
101
102 /// Which user-facing path this method can serve.
103 virtual ToleranceKind guaranteeKind() const = 0;
104
105 /// True iff this method participates in the auto-chooser's portfolio (vs being
106 /// reachable only @c byName).
107 virtual bool inDefaultChain() const { return false; }
108
109 /// True iff the method's guarantee holds with CERTAINTY (no failure
110 /// probability). The exact methods and the d-tree's certified interval are
111 /// deterministic; the (eps,delta) samplers are not. A request with delta == 0
112 /// ("deterministic") admits only deterministic methods -- the samplers cannot
113 /// honour it (their sample count is proportional to ln(1/delta), so delta = 0
114 /// is infeasible, and their cost model masks this by falling back to a finite
115 /// delta). For delta > 0 the samplers stay admissible but their cost grows as
116 /// delta shrinks, so the chooser already migrates to the (delta-independent)
117 /// d-tree well before delta reaches 0.
118 virtual bool isDeterministic() const { return true; }
119
120 /// Features the method's @c estimatedCost / @c applicable need acquired before
121 /// they are meaningful (empty = a free estimate). The chooser will not call
122 /// @c estimatedCost / @c applicable until these are acquired, and acquires
123 /// them lazily per the cost rule above.
124 virtual std::vector<Feature> requiredFeatures() const { return {}; }
125
126 /// Heuristic estimate of this method's cost on the current circuit (lower is
127 /// cheaper). Only called once @c requiredFeatures are acquired. The chooser sorts admissible portfolio members by this and tries
128 /// them cheapest-first -- there is deliberately NO fixed ordinal: the order
129 /// emerges from the estimates, and a calibrated cost model can later replace
130 /// the heuristic bodies without touching the chooser. Only consulted for
131 /// portfolio members; by-name-only methods keep the default.
132 virtual double estimatedCost(const EvalContext &, const Tolerance &) const
133 { return 0.; }
134
135 /// Cheap admissibility check for the portfolio (e.g. an inversion-free
136 /// certificate must be present, or a 2^N method's N is within a sanity
137 /// bound). @c byName ignores it.
138 virtual bool applicable(const EvalContext &, const Tolerance &) const
139 { return true; }
140
141 /// True iff the method evaluates the *raw* circuit, including multivalued
142 /// (BID / @c gate_mulinput) gates, and must therefore NOT have them rewritten
143 /// to independent Booleans first. The dispatcher rewrites multivalued gates
144 /// (@c EvalContext::ensureMultivaluedRewritten) before every method that
145 /// returns @c false, so a Boolean-only method needs no per-@c evaluate rewrite
146 /// of its own and a new one is BID-correct by default. Only @c "independent"
147 /// and the three route methods, which run the same sweep, override this: they
148 /// interpret a @c mulinput block natively (summing the mutually-exclusive
149 /// alternatives) to keep the exact disjoint-OR structure the rewrite would
150 /// dissolve. (Methods gated to TID-only circuits -- the
151 /// DNF samplers via @c Feature::DnfShape, @c inversion-free via its
152 /// certificate -- never see a @c mulinput, so the central rewrite is a no-op
153 /// for them and they keep the default.)
154 virtual bool handlesMultivalued() const { return false; }
155
156 /// Run the method, returning the probability. May mutate @p ctx (build the
157 /// Boolean view lazily, trigger the multivalued rewrite, set the reported
158 /// method name).
159 virtual double evaluate(EvalContext &ctx, const Tolerance &tol) const = 0;
160
161 /// True iff this method constructs a d-DNNF artifact (and so can serve the
162 /// makeDD route-chooser via @c buildDD). The three d-D constructors --
163 /// interpret-as-dd, tree-decomposition, compilation -- override this; the
164 /// scalar methods (independent, possible-worlds, the samplers, the d-tree)
165 /// do not. This is the @c producesDD() portfolio @c chooseAndBuildDD ranks.
166 virtual bool producesDD() const { return false; }
167
168 /// Build the d-DNNF this method constructs (only when @c producesDD()).
169 /// @c evaluate() of a d-D method is exactly @c buildDD(ctx).probabilityEvaluation(),
170 /// so the cost/route logic stays single-sourced. Sets @c ctx.actual_method.
171 virtual dDNNF buildDD(EvalContext &ctx) const;
172};
173
174/**
175 * @brief Registry of @c ProbabilityMethod objects.
176 *
177 * Mirrors the external-tool registry: adding a method is a new subclass plus one
178 * @c registerMethod call -- the dispatcher never changes (open/closed).
179 */
181public:
182 /// The process-wide catalog, lazily populated with the built-in methods.
183 static const MethodCatalog &instance();
184
185 void registerMethod(std::unique_ptr<ProbabilityMethod> m);
186
187 /// Exact match on @c name(); nullptr if absent.
188 const ProbabilityMethod *byName(const std::string &name) const;
189
190 /// Run the auto-chooser for @p tol: the portfolio methods admissible for the
191 /// tolerance and @c applicable, sorted cheapest-first by @c estimatedCost and
192 /// tried until one succeeds. The costliest method's exception propagates (the
193 /// portfolio is exhausted).
194 double chooseAndRun(EvalContext &ctx, const Tolerance &tol) const;
195
196 /// The d-DNNF analogue of @c chooseAndRun: cost-select among the
197 /// @c producesDD() portfolio (interpret-as-dd / tree-decomposition /
198 /// compilation) with the same uniform-cost search and speculative budget, and
199 /// return the chosen d-DNNF artifact (rather than a probability). This is the
200 /// makeDD route optimizer -- the same selection the probability chooser makes
201 /// among these routes, surfaced for the d-D-artifact callers.
202 dDNNF chooseAndBuildDD(EvalContext &ctx, const Tolerance &tol) const;
203
204private:
205 std::vector<std::unique_ptr<ProbabilityMethod>> methods_;
206};
207
208/// Cost-select a d-DNNF construction route for gate @p g of Boolean circuit
209/// @p c and build it -- the default makeDD route. A thin entry point over
210/// @c MethodCatalog::chooseAndBuildDD that builds the @c EvalContext from the
211/// Boolean view alone (the d-D portfolio needs no generic-circuit state); the
212/// callers that have a method/compiler request route the empty / "default" /
213/// "auto" case here and keep @c BooleanCircuit::makeDD for the named routes
214/// (tree-decomposition / interpret-as-dd / compilation, plus makeDD's own
215/// internal interpret -> tree-decomposition -> compiler fallback chain).
217
218/**
219 * @brief Probability of the Boolean function rooted at @p root in @p gc --
220 * THE single entry point over the method portfolio.
221 *
222 * @c getBooleanCircuit builds the Boolean view (HAVING semantics + BoolExpr
223 * translation); the empty / "default" / "exact" @p method then runs the
224 * cost-ordered auto-chooser (@c MethodCatalog::chooseAndRun), while a named
225 * method dispatches @c byName. Every caller that needs "the probability of
226 * a Boolean subcircuit" -- the top-level @c probability_evaluate and the
227 * moment evaluator's mixture weights alike -- routes through here, so the
228 * Boolean-view build and the method portfolio are single-sourced. @p gc's
229 * comparators should already be resolved (see @c resolveComparators in
230 * @c ComparatorResolution.h) for an exact result.
231 *
232 * When the Boolean view cannot be built (the circuit carries random
233 * variables, or a large sampleable HAVING aggregate under an approximate
234 * request), the probability is delegated to the tolerance-appropriate
235 * generic-circuit estimator: the Dagum-Karp-Luby-Ross stopping rule for a
236 * @c Relative request, fixed-sample @c monteCarloRV for @c Additive, and --
237 * for an @c Exact request with @p mc_fallback -- @c monteCarloRV at the
238 * @c provsql.rv_mc_samples budget (the moment path's residual comparators).
239 *
240 * @param gc the circuit holding the sub-circuit to evaluate.
241 * @param root the gate whose probability is computed.
242 * @param method "" / "default" / "exact" runs the auto-chooser; any other
243 * name dispatches that method @c byName.
244 * @param args method arguments (tolerance strings, compiler names).
245 * @param inv_free_cert whether an inversion-free certificate is present
246 * (unlocks the inversion-free method in the portfolio).
247 * @param tol the guarantee requested of the portfolio and of the
248 * no-Boolean-view estimator: @c Exact (default), @c Relative, @c Additive.
249 * @param mc_fallback for an @c Exact request only: when true, a circuit with
250 * no Boolean view is estimated by @c monteCarloRV instead of raising (the
251 * moment path opts in; @c probability_evaluate's exact arm passes false so
252 * an unresolved RV comparator surfaces its diagnostic).
253 * @param actual_method_out if non-null, receives the method actually run
254 * (for @c provsql.last_eval_method reporting).
255 */
257 const std::string &method = "",
258 const std::string &args = "",
259 bool inv_free_cert = false,
260 const Tolerance &tol = Tolerance{},
261 bool mc_fallback = true,
262 std::string *actual_method_out = nullptr);
263
264} // namespace provsql
265
266#endif // PROVSQL_PROBABILITY_METHOD_H
gate_t
Strongly-typed gate identifier.
Definition Circuit.h:53
Boolean circuit for provenance formula evaluation.
A d-DNNF circuit supporting exact probabilistic and game-theoretic evaluation.
Definition dDNNF.h:71
Registry of ProbabilityMethod objects.
const ProbabilityMethod * byName(const std::string &name) const
Exact match on name(); nullptr if absent.
std::vector< std::unique_ptr< ProbabilityMethod > > methods_
double chooseAndRun(EvalContext &ctx, const Tolerance &tol) const
Run the auto-chooser for tol: the portfolio methods admissible for the tolerance and applicable,...
void registerMethod(std::unique_ptr< ProbabilityMethod > m)
static const MethodCatalog & instance()
The process-wide catalog, lazily populated with the built-in methods.
dDNNF chooseAndBuildDD(EvalContext &ctx, const Tolerance &tol) const
The d-DNNF analogue of chooseAndRun: cost-select among the producesDD() portfolio (interpret-as-dd / ...
Strategy interface: one concrete subclass per probability method.
virtual dDNNF buildDD(EvalContext &ctx) const
Build the d-DNNF this method constructs (only when producesDD()).
virtual double estimatedCost(const EvalContext &, const Tolerance &) const
Heuristic estimate of this method's cost on the current circuit (lower is cheaper).
virtual bool inDefaultChain() const
True iff this method participates in the auto-chooser's portfolio (vs being reachable only byName).
virtual ~ProbabilityMethod()=default
virtual bool applicable(const EvalContext &, const Tolerance &) const
Cheap admissibility check for the portfolio (e.g.
virtual bool isDeterministic() const
True iff the method's guarantee holds with CERTAINTY (no failure probability).
virtual ToleranceKind guaranteeKind() const =0
Which user-facing path this method can serve.
virtual double evaluate(EvalContext &ctx, const Tolerance &tol) const =0
Run the method, returning the probability.
virtual std::vector< Feature > requiredFeatures() const
Features the method's estimatedCost / applicable need acquired before they are meaningful (empty = a ...
virtual bool producesDD() const
True iff this method constructs a d-DNNF artifact (and so can serve the makeDD route-chooser via buil...
virtual bool handlesMultivalued() const
True iff the method evaluates the raw circuit, including multivalued (BID / gate_mulinput) gates,...
virtual std::string name() const =0
Stable identifier used for byName lookup and the provsql.last_eval_method report.
double booleanSubcircuitProbability(GenericCircuit &gc, gate_t root, const std::string &method, const std::string &args, bool inv_free_cert, const Tolerance &tol, bool mc_fallback, std::string *actual_method_out)
Probability of the Boolean function rooted at root in gc – THE single entry point over the method por...
Feature
A circuit feature a method's cost/applicability estimate depends on, but that is not free to acquire.
ToleranceKind
The contract the user grants – the "path".
dDNNF makeDDAuto(BooleanCircuit &c, gate_t g)
Cost-select a d-DNNF construction route for gate g of Boolean circuit c and build it – the default ma...
Per-evaluation circuit state threaded to a method's evaluate().