ProvSQL C/C++ API
Adding support for provenance and uncertainty management to PostgreSQL databases
Loading...
Searching...
No Matches
nonzero.cpp
Go to the documentation of this file.
1/**
2 * @file nonzero.cpp
3 * @brief SQL function @c provsql.true_nonzero() – structural universal-zero
4 * test backing the default mode of @c provsql.nonzero().
5 *
6 * Decides whether a circuit is *provably* the semiring zero – zero in every
7 * m-semiring under every leaf valuation – by the sound structural rules:
8 * @c gate_zero; a ⊗ with a zero factor; a ⊕ (or δ, or a transparent
9 * single-child wrapper) all of whose children are zero; a ⊖ whose left
10 * operand is zero; a semimod whose provenance side is zero. Comparison
11 * gates are resolved through the Boolean-abstraction pipeline (the same
12 * @c provsql_having world enumeration every evaluator applies): a @c cmp
13 * whose satisfying-world set is empty is the empty disjunction, i.e. zero
14 * in every semiring, and surfaces in the Boolean circuit as a childless OR
15 * (the @c BoolExpr semiring's @c zero()). Everything else – input gates,
16 * undecided probabilistic comparisons, mixtures, conditioning – blocks the
17 * proof: the verdict is then @c true (not provably zero), never a dropped
18 * row.
19 *
20 * Exact zero-ness in the free m-semiring is the word problem for the
21 * m-semiring axioms, whose decidability is open; drop-only-on-proof is the
22 * specified contract, so a sound under-approximation is exactly right.
23 */
24extern "C"
25{
26#include "postgres.h"
27#include "fmgr.h"
28#include "utils/uuid.h"
29#include "provsql_utils.h"
30}
31
32#include <exception>
33#include <unordered_map>
34
35#include "BooleanCircuit.h"
36#include "CircuitFromMMap.h"
37#include "GenericCircuit.h"
38#include "provsql_utils_cpp.h"
39#include "provsql_interrupt.h"
40
41extern "C"
42{
43PG_FUNCTION_INFO_V1(true_nonzero);
44}
45
46/**
47 * @brief Structural proof of universal zero-ness of @p g, memoized over the
48 * DAG.
49 *
50 * @param gc The loaded circuit (post the load-time simplification
51 * passes, so RangeCheck-decided RV comparisons are already
52 * constants).
53 * @param g Gate to test.
54 * @param bc Boolean abstraction of @p gc, when it could be built;
55 * used only to read comparison gates' world-set emptiness.
56 * @param gc_to_bc Gate map into @p bc.
57 * @param memo Verdict cache (the circuit is a DAG).
58 */
59static bool provably_zero(
60 const GenericCircuit &gc, gate_t g,
61 const BooleanCircuit *bc,
62 const std::unordered_map<gate_t, gate_t> *gc_to_bc,
63 std::unordered_map<gate_t, bool> &memo)
64{
65 auto it = memo.find(g);
66 if(it != memo.end())
67 return it->second;
68 memo[g] = false; // provisional: blocks pathological cycles safely
69
70 const auto &w = gc.getWires(g);
71 bool z = false;
72
73 switch(gc.getGateType(g)) {
74 case gate_zero:
75 z = true;
76 break;
77
78 case gate_plus:
79 // The empty ⊕ is 0; any non-zero child blocks the proof.
80 z = true;
81 for(auto child : w)
82 if(!provably_zero(gc, child, bc, gc_to_bc, memo)) {
83 z = false;
84 break;
85 }
86 break;
87
88 case gate_times:
89 for(auto child : w)
90 if(provably_zero(gc, child, bc, gc_to_bc, memo)) {
91 z = true;
92 break;
93 }
94 break;
95
96 case gate_monus:
97 // 0 ⊖ x = 0 in every m-semiring; nothing else is provable here
98 // (x ⊖ x is folded to gate_zero by the load-time simplifier).
99 z = !w.empty() && provably_zero(gc, w[0], bc, gc_to_bc, memo);
100 break;
101
102 case gate_delta: // δ(0) = 0
103 case gate_project: // transparent single-child wrappers
104 case gate_annotation:
105 case gate_assumed:
106 z = !w.empty() && provably_zero(gc, w[0], bc, gc_to_bc, memo);
107 break;
108
109 case gate_semimod:
110 // value ⊛ K with K = 0 is the semimodule zero; wires are [K, value].
111 z = !w.empty() && provably_zero(gc, w[0], bc, gc_to_bc, memo);
112 break;
113
114 case gate_cmp:
115 // Resolved through the Boolean abstraction: the cmp's specified
116 // semantics is the disjunction over its satisfying worlds, and the
117 // empty disjunction (the BoolExpr semiring's zero(), a childless OR)
118 // is zero in every semiring. Each term of a non-empty disjunction is
119 // satisfiable by construction, so a non-childless expansion is never
120 // universally zero on its own.
121 if(bc && gc_to_bc) {
122 auto jt = gc_to_bc->find(g);
123 if(jt != gc_to_bc->end() &&
124 bc->getGateType(jt->second) == BooleanGate::OR &&
125 bc->getWires(jt->second).empty())
126 z = true;
127 }
128 break;
129
130 default:
131 // Inputs, values, mulinputs, undecided RV comparisons, mixtures,
132 // conditioning, arithmetic…: not provably zero.
133 break;
134 }
135
136 memo[g] = z;
137 return z;
138}
139
140/** @brief PostgreSQL-callable wrapper: the default mode of provsql.nonzero(). */
141Datum true_nonzero(PG_FUNCTION_ARGS)
142{
143 if(PG_ARGISNULL(0))
144 PG_RETURN_BOOL(true); // NULL token ≡ the neutral 1 ≠ 0
145
146 try {
147 provsql_interrupt_scope interrupt_scope;
148 pg_uuid_t token = *DatumGetUUIDP(PG_GETARG_DATUM(0));
150 gate_t root = gc.getGate(uuid2string(token));
151
152 // The Boolean abstraction is built only to decide comparison gates'
153 // world-set emptiness; on circuits it cannot express (an undecided
154 // probabilistic comparison, a mixture…) the comparison gates simply
155 // stay opaque and the proof works around them.
156 bool has_cmp = false;
157 for(gate_t i{0}; i < gc.getNbGates() && !has_cmp; ++i)
158 has_cmp = (gc.getGateType(i) == gate_cmp);
159
160 bool have_bc = false;
161 gate_t broot;
162 std::unordered_map<gate_t, gate_t> gc_to_bc;
164 if(has_cmp) {
165 try {
166 bc = getBooleanCircuit(gc, token, broot, gc_to_bc);
167 have_bc = true;
168 } catch(const std::exception &) {
169 // fall through with opaque cmp gates
170 }
171 }
172
173 std::unordered_map<gate_t, bool> memo;
174 bool zero = provably_zero(gc, root,
175 have_bc ? &bc : nullptr,
176 have_bc ? &gc_to_bc : nullptr,
177 memo);
178 PG_RETURN_BOOL(!zero);
179 } catch(const std::exception &e) {
181 provsql_error("nonzero: %s", e.what());
182 } catch(...) {
184 provsql_error("nonzero: Unknown exception");
185 }
186
187 PG_RETURN_NULL(); // unreachable: provsql_error does not return
188}
Boolean provenance circuit with support for knowledge compilation.
@ OR
Logical disjunction of child gates.
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
Semiring-agnostic in-memory provenance circuit.
Boolean circuit for provenance formula evaluation.
std::vector< gate_t > & getWires(gate_t g)
Return a mutable reference to the child-wire list of gate g.
Definition Circuit.h:311
gateType getGateType(gate_t g) const
Return the type of gate g.
Definition Circuit.h:301
gate_t getGate(const uuid &u)
Return (or create) the gate associated with UUID u.
Definition Circuit.hpp:50
std::vector< gate_t >::size_type getNbGates() const
Return the total number of gates in the circuit.
Definition Circuit.h:252
The SIGINT handler installed for the lifetime of the object, the previous one restored as it ends (a ...
static bool provably_zero(const GenericCircuit &gc, gate_t g, const BooleanCircuit *bc, const std::unordered_map< gate_t, gate_t > *gc_to_bc, std::unordered_map< gate_t, bool > &memo)
Structural proof of universal zero-ness of g, memoized over the DAG.
Definition nonzero.cpp:59
Datum true_nonzero(PG_FUNCTION_ARGS)
PostgreSQL-callable wrapper: the default mode of provsql.nonzero().
Definition nonzero.cpp:141
#define provsql_error(fmt,...)
Report a fatal ProvSQL error and abort the current 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.
Core types, constants, and utilities shared across ProvSQL.
@ gate_annotation
Transparent single-child wrapper carrying a query-level annotation in extra (inversion-free certifica...
@ gate_assumed
Structural marker over a single child whose sub-circuit was computed under a Boolean-provenance assum...
string uuid2string(pg_uuid_t uuid)
Format a pg_uuid_t as a std::string.
C++ utility functions for UUID manipulation.