ProvSQL C/C++ API
Adding support for provenance and uncertainty management to PostgreSQL databases
Loading...
Searching...
No Matches
shapley.cpp
Go to the documentation of this file.
1/**
2 * @file shapley.cpp
3 * @brief SQL functions for Shapley and Banzhaf power-index computation.
4 *
5 * Implements two SQL-callable functions:
6 * - @c provsql.shapley(token, variable, method, args): Shapley value of
7 * a given input gate (tuple) in the provenance circuit rooted at @p token.
8 * - @c provsql.shapley_all_vars(token, method, args): Shapley values for
9 * all input gates simultaneously (more efficient than calling @c shapley()
10 * once per variable).
11 *
12 * The @p method argument selects the d-DNNF construction:
13 * - empty / @c "default" / @c "auto": cost-select the cheapest route via the
14 * probability catalog's chooser.
15 * - @c "tree-decomposition": exact, polynomial if treewidth ≤ @c MAX_TREEWIDTH.
16 * - @c "interpret-as-dd": direct interpretation of the circuit as a d-DNNF.
17 * - @c "compilation": external knowledge compiler, named in @p args
18 * (@c "d4", @c "c2d", …); empty @p args picks the highest-preference one.
19 *
20 * Banzhaf power index computation is exposed via the same internal helper
21 * (@c shapley_internal with @c banzhaf=true), called by the
22 * @c provsql.banzhaf() SQL function defined in the SQL layer.
23 */
24extern "C" {
25#include "postgres.h"
26#include "fmgr.h"
27#include "catalog/pg_type.h"
28#include "utils/tuplestore.h"
29#include "utils/uuid.h"
30#include "executor/spi.h"
31#include "provsql_shmem.h"
32#include "provsql_utils.h"
33
34PG_FUNCTION_INFO_V1(shapley);
35PG_FUNCTION_INFO_V1(shapley_all_vars);
36}
37
38#include "c_cpp_compatibility.h"
39#include "BooleanCircuit.h"
40#include "ProbabilityMethod.h"
41#include "GenericCircuit.h"
42#include "Circuit.hpp"
43#include <unordered_map>
44#include "provsql_utils_cpp.h"
46#include "CircuitFromMMap.h"
47#include "tool_registry_sync.h"
48#include <fstream>
49#include "provsql_interrupt.h"
50
51using namespace std;
52
53/**
54 * @brief Core implementation for Shapley and Banzhaf index computation.
55 * @param token UUID of the root provenance gate.
56 * @param variable UUID of the input gate whose index is to be computed.
57 * @param method d-DNNF compilation method.
58 * @param args Additional arguments for the compilation method.
59 * @param banzhaf If @c true, compute the Banzhaf index instead of Shapley.
60 * @return The Shapley (or Banzhaf) value of @p variable.
61 */
62static double shapley_internal
63 (pg_uuid_t token, pg_uuid_t variable, const std::string &method, const std::string &args, bool banzhaf)
64{
65 /* A conditioned token (X | C) is refused: Shapley / Banzhaf are linear in
66 * their value function, whereas P(X|C) = P(X∧C)/P(C) is a non-linear ratio,
67 * so the conditional indices are not a combination of the unconditioned
68 * ones and have no implementation here. Detect the conditioned root and
69 * raise a Shapley-specific message rather than the generic semiring-refusal
70 * thrown deeper in the Boolean-circuit build. */
73 provsql_unsupported(PROVSQL_OUT_OF_SCOPE, "shapley-conditional", "shapley/banzhaf: conditional Shapley / Banzhaf values are "
74 "not supported -- a conditioned token (X | C) cannot be "
75 "passed to shapley() / banzhaf(). Compute the index on the "
76 "unconditioned token, or use probability_evaluate for the "
77 "conditional probability P(X|C)");
78 gate_t root;
79 std::unordered_map<gate_t, gate_t> gc_to_bc;
80 BooleanCircuit c = getBooleanCircuit(gc, token, root, gc_to_bc);
81
83 provsql_error("Computing Shapley/Banzhaf values is ill-defined for circuits with multivalued (mulinput) gates");
84
85 if(c.getGateType(c.getGate(uuid2string(variable))) != BooleanGate::IN)
86 return 0.;
87
88 // Default / "auto": cost-select the d-D construction (interpret-as-dd /
89 // tree-decomposition / compilation) via the probability catalog's chooser;
90 // any other method (tree-decomposition / interpret-as-dd / compilation, the
91 // latter with a compiler name in `args`) is taken by name.
92 dDNNF dd = (method.empty() || method == "default" || method == "auto")
93 ? provsql::makeDDAuto(c, root)
94 : c.makeDD(root, method, args);
95
96 dd.makeSmooth();
97 if(!banzhaf)
99
100 auto var_gate=dd.getGate(uuid2string(variable));
101
102 double result;
103
104 if(!banzhaf)
105 result = dd.shapley(var_gate);
106 else
107 result = dd.banzhaf(var_gate);
108
109 return result;
110}
111
112/** @brief PostgreSQL-callable wrapper for shapley() and banzhaf(). */
113Datum shapley(PG_FUNCTION_ARGS)
114{
115 provsql_sync_tool_registry(); // honour persisted tool-registry overrides
116 try {
117 provsql_interrupt_scope interrupt_scope;
118 if(PG_ARGISNULL(0) || PG_ARGISNULL(1))
119 PG_RETURN_NULL();
120
121 Datum token = PG_GETARG_DATUM(0);
122 Datum variable = PG_GETARG_DATUM(1);
123
124 std::string method;
125 if(!PG_ARGISNULL(2)) {
126 text *t = PG_GETARG_TEXT_P(2);
127 method = string(VARDATA(t),VARSIZE(t)-VARHDRSZ);
128 }
129
130 std::string args;
131 if(!PG_ARGISNULL(3)) {
132 text *t = PG_GETARG_TEXT_P(3);
133 args = string(VARDATA(t),VARSIZE(t)-VARHDRSZ);
134 }
135
136 bool banzhaf = false;
137 if(!PG_ARGISNULL(4)) {
138 banzhaf = PG_GETARG_BOOL(4);
139 }
140
141 PG_RETURN_FLOAT8(shapley_internal(*DatumGetUUIDP(token), *DatumGetUUIDP(variable), method, args, banzhaf));
142 } catch(const std::exception &e) {
144 provsql_error("shapley: %s", e.what());
145 } catch(...) {
147 provsql_error("shapley: Unknown exception");
148 }
149
150 PG_RETURN_NULL();
151}
152
153/** @brief PostgreSQL-callable wrapper for shapley_all_vars() set-returning function. */
154Datum shapley_all_vars(PG_FUNCTION_ARGS)
155{
156 ReturnSetInfo *rsinfo = (ReturnSetInfo *) fcinfo->resultinfo;
157
158 MemoryContext per_query_ctx = rsinfo->econtext->ecxt_per_query_memory;
159 MemoryContext oldcontext = MemoryContextSwitchTo(per_query_ctx);
160
161 TupleDesc tupdesc = rsinfo->expectedDesc;
162 Tuplestorestate *tupstore = tuplestore_begin_heap(rsinfo->allowedModes & SFRM_Materialize_Random, false, work_mem);
163
164 rsinfo->returnMode = SFRM_Materialize;
165 rsinfo->setResult = tupstore;
166
167 /* One value per variable, each a pass over the d-DNNF: a cancel stops
168 * between two of them (and in the compilation) */
169 if(!PG_ARGISNULL(0)) try {
170 provsql_interrupt_scope interrupt_scope;
171 pg_uuid_t token = *DatumGetUUIDP(PG_GETARG_DATUM(0));
172
173 std::string method;
174 if(!PG_ARGISNULL(1)) {
175 text *t = PG_GETARG_TEXT_P(1);
176 method = string(VARDATA(t),VARSIZE(t)-VARHDRSZ);
177 }
178
179 std::string args;
180 if(!PG_ARGISNULL(2)) {
181 text *t = PG_GETARG_TEXT_P(2);
182 args = string(VARDATA(t),VARSIZE(t)-VARHDRSZ);
183 }
184
185 bool banzhaf = false;
186 if(!PG_ARGISNULL(3)) {
187 banzhaf = PG_GETARG_BOOL(3);
188 }
189
190
192 if(gc.getGateType(gc.getGate(uuid2string(token))) == gate_conditioned)
193 provsql_unsupported(PROVSQL_OUT_OF_SCOPE, "shapley-conditional", "shapley/banzhaf: conditional Shapley / Banzhaf values are "
194 "not supported -- a conditioned token (X | C) cannot be "
195 "passed to shapley() / banzhaf(). Compute the index on the "
196 "unconditioned token, or use probability_evaluate for the "
197 "conditional probability P(X|C)");
198 gate_t root;
199 std::unordered_map<gate_t, gate_t> gc_to_bc;
200 BooleanCircuit c = getBooleanCircuit(gc, token, root, gc_to_bc);
201
202 if(c.hasMultivaluedGates())
203 provsql_error("Computing Shapley/Banzhaf values is ill-defined for circuits with multivalued (mulinput) gates");
204
205 dDNNF dd = (method.empty() || method == "default" || method == "auto")
206 ? provsql::makeDDAuto(c, root)
207 : c.makeDD(root, method, args);
208 dd.makeSmooth();
209 if(!banzhaf)
211
212 for(auto &v_circuit_gate: c.getInputs()) {
214 auto var_uuid_string = c.getUUID(v_circuit_gate);
215 auto var_gate=dd.getGate(var_uuid_string);
216 pg_uuid_t *uuidp = reinterpret_cast<pg_uuid_t*>(palloc(UUID_LEN));
217 *uuidp = string2uuid(var_uuid_string);
218
219 double result;
220
221 if(!banzhaf)
222 result = dd.shapley(var_gate);
223 else
224 result = dd.banzhaf(var_gate);
225
226 Datum values[2] = {
227 UUIDPGetDatum(uuidp), Float8GetDatum(result)
228 };
229 bool nulls[sizeof(values)] = {0, 0};
230
231 tuplestore_putvalues(tupstore, tupdesc, values, nulls);
232 }
233 } catch(const std::exception &e) {
235 provsql_error("shapley_all_vars: %s", e.what());
236 } catch(...) {
238 provsql_error("shapley_all_vars: Unknown exception");
239 }
240
241 MemoryContextSwitchTo(oldcontext);
242
243 PG_RETURN_NULL();
244}
Boolean provenance circuit with support for knowledge compilation.
@ AND
Logical conjunction of child gates.
@ IN
Input (variable) gate representing a base tuple.
BooleanCircuit getBooleanCircuit(GenericCircuit &gc, pg_uuid_t token, gate_t &gate, std::unordered_map< gate_t, gate_t > &gc_to_bc)
Build a BooleanCircuit from an already-loaded GenericCircuit.
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.
gate_t
Strongly-typed gate identifier.
Definition Circuit.h:53
Out-of-line template method implementations for Circuit<gateType>.
Semiring-agnostic in-memory provenance circuit.
Catalog of probability-evaluation methods (Strategy + registry).
Fix macro conflicts between PostgreSQL headers and the C++ STL/Boost.
Boolean circuit for provenance formula evaluation.
const std::set< gate_t > & getInputs() const
Return the set of input (IN) gate IDs.
dDNNF makeDD(gate_t g, const std::string &method, const std::string &args) const
Dispatch to the appropriate d-DNNF construction method.
bool hasMultivaluedGates() const
Return true if the circuit contains any MULIN gates.
gateType getGateType(gate_t g) const
Return the type of gate g.
Definition Circuit.h:301
uuid getUUID(gate_t g) const
Return the UUID string associated with gate g.
Definition Circuit.hpp:65
gate_t getGate(const uuid &u)
Return (or create) the gate associated with UUID u.
Definition Circuit.hpp:50
A d-DNNF circuit supporting exact probabilistic and game-theoretic evaluation.
Definition dDNNF.h:71
void makeSmooth()
Make the d-DNNF smooth.
Definition dDNNF.cpp:61
void makeGatesBinary(BooleanGate type)
Rewrite all n-ary AND/OR gates into binary trees.
Definition dDNNF.cpp:108
double shapley(gate_t var) const
Compute the Shapley value of input gate var.
Definition dDNNF.cpp:526
double banzhaf(gate_t var) const
Compute the Banzhaf power index of input gate var.
Definition dDNNF.cpp:554
The SIGINT handler installed for the lifetime of the object, the previous one restored as it ends (a ...
Constructs a d-DNNF from a Boolean circuit and its tree decomposition.
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...
#define PROVSQL_OUT_OF_SCOPE
#define provsql_error(fmt,...)
Report a fatal ProvSQL error and abort the current transaction.
#define provsql_unsupported(scope, tag, fmt,...)
Refuse a query ProvSQL cannot track, and abort the 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.
void provsql_poll_interrupt()
Throw where an evaluation is to stop, its query cancelled.
Shared-memory segment and inter-process pipe management.
Core types, constants, and utilities shared across ProvSQL.
@ gate_conditioned
Conditioning marker with two children [target, evidence]: measure-only, probability_evaluate returns ...
pg_uuid_t string2uuid(const string &source)
Parse a UUID string into a pg_uuid_t.
string uuid2string(pg_uuid_t uuid)
Format a pg_uuid_t as a std::string.
C++ utility functions for UUID manipulation.
static double shapley_internal(pg_uuid_t token, pg_uuid_t variable, const std::string &method, const std::string &args, bool banzhaf)
Core implementation for Shapley and Banzhaf index computation.
Definition shapley.cpp:63
Datum shapley(PG_FUNCTION_ARGS)
PostgreSQL-callable wrapper for shapley() and banzhaf().
Definition shapley.cpp:113
Datum shapley_all_vars(PG_FUNCTION_ARGS)
PostgreSQL-callable wrapper for shapley_all_vars() set-returning function.
Definition shapley.cpp:154
void provsql_sync_tool_registry()
Rebuild the in-memory registry as "compiled seed overlaid with the provsql.tool_overrides rows"...
Reload the in-memory external-tool registry from its persistent overrides.