ProvSQL C/C++ API
Adding support for provenance and uncertainty management to PostgreSQL databases
Loading...
Searching...
No Matches
CertifiedDDMaterialize.cpp
Go to the documentation of this file.
1/**
2 * @file CertifiedDDMaterialize.cpp
3 * @brief Implementation of certified-d-D materialisation into the store.
4 *
5 * See @c CertifiedDDMaterialize.h. Extracted from the reachability
6 * compiler's SQL glue so the joint-width UCQ compiler shares the same
7 * content-addressed materialisation (and so probability / Shapley /
8 * expectation all go through the standard @c probability_evaluate path on
9 * the materialised token).
10 */
11extern "C" {
12#include "postgres.h"
13#include "miscadmin.h"
14#include "utils/uuid.h"
15
16#include "provsql_utils.h"
17#include "provsql_mmap.h"
18}
19
21#include "BooleanCircuit.h"
22#include "provsql_utils_cpp.h"
23
24#include <algorithm>
25#include <cstdint>
26#include <string>
27#include <unordered_set>
28#include <vector>
29
30namespace {
31
32/**
33 * @brief Minimal SHA-1 (RFC 3174), used for RFC 4122 version-5 UUIDs: the
34 * compression of one 64-byte block into @p h.
35 *
36 * Self-contained so the content addressing builds on every supported
37 * PostgreSQL version.
38 */
39void sha1_block(uint32_t h[5], const unsigned char *block)
40{
41 uint32_t w[80];
42 for (int i = 0; i < 16; ++i)
43 w[i] = (static_cast<uint32_t>(block[4*i]) << 24) |
44 (static_cast<uint32_t>(block[4*i + 1]) << 16) |
45 (static_cast<uint32_t>(block[4*i + 2]) << 8) |
46 static_cast<uint32_t>(block[4*i + 3]);
47 for (int i = 16; i < 80; ++i) {
48 const uint32_t v = w[i-3] ^ w[i-8] ^ w[i-14] ^ w[i-16];
49 w[i] = (v << 1) | (v >> 31);
50 }
51 uint32_t a = h[0], b = h[1], c = h[2], d = h[3], e = h[4];
52 for (int i = 0; i < 80; ++i) {
53 uint32_t f, k;
54 if (i < 20) {
55 f = (b & c) | (~b & d);
56 k = 0x5A827999u;
57 } else if (i < 40) {
58 f = b ^ c ^ d;
59 k = 0x6ED9EBA1u;
60 } else if (i < 60) {
61 f = (b & c) | (b & d) | (c & d);
62 k = 0x8F1BBCDCu;
63 } else {
64 f = b ^ c ^ d;
65 k = 0xCA62C1D6u;
66 }
67 const uint32_t tmp = ((a << 5) | (a >> 27)) + f + e + k + w[i];
68 e = d;
69 d = c;
70 c = (b << 30) | (b >> 2);
71 b = a;
72 a = tmp;
73 }
74 h[0] += a; h[1] += b; h[2] += c; h[3] += d; h[4] += e;
75}
76
77void sha1(const unsigned char *data, std::size_t len, unsigned char out[20])
78{
81 provsql_sha1_update(&ctx, data, len);
82 provsql_sha1_final(&ctx, out);
83}
84
85} // namespace
86
88{
89 static const uint32_t init[5] = {0x67452301u, 0xEFCDAB89u, 0x98BADCFEu,
90 0x10325476u, 0xC3D2E1F0u};
91 std::copy(init, init + 5, ctx->h);
92 ctx->len = 0;
93 ctx->used = 0;
94}
95
97 const unsigned char *data, size_t len)
98{
99 ctx->len += len;
100 if (ctx->used > 0) {
101 const std::size_t take = std::min(len, sizeof(ctx->block) - ctx->used);
102 std::copy(data, data + take, ctx->block + ctx->used);
103 ctx->used += take;
104 data += take;
105 len -= take;
106 if (ctx->used < sizeof(ctx->block))
107 return;
108 sha1_block(ctx->h, ctx->block);
109 ctx->used = 0;
110 }
111 for (; len >= sizeof(ctx->block); data += 64, len -= 64)
112 sha1_block(ctx->h, data);
113 std::copy(data, data + len, ctx->block);
114 ctx->used = len;
115}
116
118 unsigned char out[20])
119{
120 const uint64_t bits = ctx->len * 8;
121 unsigned char pad[72] = {0x80};
122 /* 0x80, zeros up to 56 mod 64, then the length in bits, big-endian */
123 const std::size_t npad = (ctx->used < 56 ? 56 : 120) - ctx->used;
124 for (int i = 0; i < 8; ++i)
125 pad[npad + i] = static_cast<unsigned char>(bits >> (8 * (7 - i)));
126 provsql_sha1_update(ctx, pad, npad + 8);
127 for (int i = 0; i < 5; ++i) {
128 out[4*i] = static_cast<unsigned char>(ctx->h[i] >> 24);
129 out[4*i + 1] = static_cast<unsigned char>(ctx->h[i] >> 16);
130 out[4*i + 2] = static_cast<unsigned char>(ctx->h[i] >> 8);
131 out[4*i + 3] = static_cast<unsigned char>(ctx->h[i]);
132 }
133}
134
135extern "C" void provsql_sha1(const unsigned char *data, size_t len,
136 unsigned char out[20])
137{
138 sha1(data, len, out);
139}
140
141pg_uuid_t provsqlUuidV5(const std::string &name)
142{
143 // uuid_ns_provsql() = 920d4f02-8718-5319-9532-d4ab83a64489
144 static const unsigned char ns[16] = {
145 0x92, 0x0d, 0x4f, 0x02, 0x87, 0x18, 0x53, 0x19,
146 0x95, 0x32, 0xd4, 0xab, 0x83, 0xa6, 0x44, 0x89
147 };
148 std::vector<unsigned char> data(16 + name.size());
149 std::copy(ns, ns + 16, data.begin());
150 std::copy(name.begin(), name.end(), data.begin() + 16);
151 unsigned char digest[20];
152 sha1(data.data(), data.size(), digest);
153 pg_uuid_t u;
154 std::copy(digest, digest + 16, u.data);
155 u.data[6] = static_cast<unsigned char>((u.data[6] & 0x0F) | 0x50);
156 u.data[8] = static_cast<unsigned char>((u.data[8] & 0x3F) | 0x80);
157 return u;
158}
159
160std::unordered_map<gate_t, pg_uuid_t, hash_gate_t> materializeCertifiedDD(
161 const dDNNF &dd, const std::vector<gate_t> &roots, provsql_route route)
162{
163 std::unordered_map<gate_t, pg_uuid_t, hash_gate_t> uuid_of;
164 /* Tokens this backend has already materialised, across calls: the
165 * store is append-only, so a create this backend has sent once never
166 * needs re-sending. Per-backend, bounded. */
167 static std::unordered_set<std::string> created;
168 constexpr std::size_t kCreatedCap = 4u << 20;
169 if (created.size() > kCreatedCap)
170 created.clear();
171 pg_uuid_t one_uuid;
172 bool have_one = false;
173
174 const auto ensureOne = [&]() {
175 if (!have_one) {
178 0, NULL);
179 have_one = true;
180 }
181 return one_uuid;
182 };
183 const auto createOnce = [&](const pg_uuid_t &token, gate_type type,
184 const std::vector<pg_uuid_t> &children,
185 bool certified) {
186 const std::string key = uuid2string(token);
187 if (!created.insert(key).second)
188 return;
189 /* The certificate goes with the gate, in one
190 * unanswered message: any route certifying
191 * this shape records the same thing. */
193 &token, type,
194 static_cast<unsigned>(children.size()),
195 children.empty() ? NULL : children.data(),
196 certified, DNNF_CERT_INFO, 0, NULL);
197 };
198
199 std::vector<gate_t> stack(roots);
200 while (!stack.empty()) {
201 CHECK_FOR_INTERRUPTS();
202 const gate_t g = stack.back();
203 if (uuid_of.find(g) != uuid_of.end()) {
204 stack.pop_back();
205 continue;
206 }
207
208 const auto t = dd.getGateType(g);
209
210 if (t == BooleanGate::IN || t == BooleanGate::MULIN) {
211 const std::string tok = dd.getUUID(g);
212 if (!tok.empty() && tok[0] == '\x01') {
213 // A synthetic stick-breaking coin: the joint-width compiler
214 // introduces these when it expands a repair_key / BID exclusion
215 // block into shared independent events; they carry a probability
216 // but no store UUID. Materialise each as an independent
217 // gate_input with that probability. The UUID is content-addressed
218 // on the synthetic token, which names the block and the split
219 // inside it (see UCQJointCompiler::emitInput), so the coins shared
220 // by a block's values collapse to one store gate -- that sharing
221 // is the mutual exclusion -- while coins of different blocks, or
222 // of the same block with different masses, stay apart.
223 const pg_uuid_t token = provsqlUuidV5(tok);
224 if (created.insert(uuid2string(token)).second) {
226 double existing = 0.;
227 if (provsql_internal_set_prob(&token, dd.getProb(g), &existing)
229 provsql_error("stick-breaking coin %s already carries "
230 "probability %g, not the %g this compilation "
231 "needs: two distinct coins hashed to one gate",
232 uuid2string(token).c_str(), existing,
233 dd.getProb(g));
234 }
235 uuid_of[g] = token;
236 } else {
237 // Existing tokens (the leaf provenance): never re-created.
238 uuid_of[g] = string2uuid(tok);
239 }
240 stack.pop_back();
241 continue;
242 }
243
244 bool ready = true;
245 for (const auto &c : dd.getWires(g))
246 if (uuid_of.find(c) == uuid_of.end()) {
247 stack.push_back(c);
248 ready = false;
249 }
250 if (!ready)
251 continue;
252
253 const bool certified = dd.isDNNFCertified(g);
254 pg_uuid_t token;
255
256 switch (t) {
257 case BooleanGate::NOT:
258 {
259 const pg_uuid_t child = uuid_of[dd.getWires(g)[0]];
260 const pg_uuid_t one = ensureOne();
261 token = provsqlUuidV5("monus" + uuid2string(one) + uuid2string(child));
262 createOnce(token, gate_monus, {one, child}, false);
263 }
264 break;
265
266 case BooleanGate::AND:
267 case BooleanGate::OR:
268 {
269 const auto &wires = dd.getWires(g);
270 if (wires.empty()) {
271 if (t == BooleanGate::AND)
272 token = ensureOne();
273 else {
275 createOnce(token, gate_zero, {}, false);
276 }
277 } else if (wires.size() == 1) {
278 token = uuid_of[wires[0]];
279 } else {
280 std::vector<std::string> texts;
281 texts.reserve(wires.size());
282 for (const auto &c : wires)
283 texts.push_back(uuid2string(uuid_of[c]));
284 std::sort(texts.begin(), texts.end());
285 std::string name = (t == BooleanGate::AND ? "times{" : "plus{");
286 for (std::size_t i = 0; i < texts.size(); ++i) {
287 if (i)
288 name += ",";
289 name += texts[i];
290 }
291 name += "}";
292 token = provsqlUuidV5(name);
293 std::vector<pg_uuid_t> children;
294 children.reserve(wires.size());
295 for (const auto &c : wires)
296 children.push_back(uuid_of[c]);
297 createOnce(token, t == BooleanGate::AND ? gate_times : gate_plus,
298 children, certified);
299 }
300 }
301 break;
302
303 default:
304 provsql_error("materializeCertifiedDD: unsupported gate type");
305 throw std::runtime_error("unreachable");
306 }
307
308 uuid_of[g] = token;
309 stack.pop_back();
310 }
311
312 /* Name the producing route on each materialised root, so the probability
313 * dispatcher can report the route as its own evaluation method instead of
314 * the generic 'independent'. The name goes on a transparent annotation
315 * wrapper of the root, "route:<name>", not on the root itself: a root is
316 * addressed by its shape, and another route, or the ordinary rewriting,
317 * may build the same gate; the wrapper's address hashes the name, so it
318 * records nothing that does not follow from its address. Only a certified
319 * multi-wire AND/OR root is wrapped: a root that collapsed to a bare leaf
320 * token, to a shared constant or to a single child is not a gate this
321 * materialisation owns. The map then points the root at its wrapper. */
322 if (route != PROVSQL_ROUTE_NONE)
323 for (const auto &r : roots) {
324 const auto t = dd.getGateType(r);
325 if ((t != BooleanGate::AND && t != BooleanGate::OR)
326 || dd.getWires(r).size() < 2 || !dd.isDNNFCertified(r))
327 continue;
328 const auto it = uuid_of.find(r);
329 if (it != uuid_of.end())
330 it->second = wrapRoute(it->second, route);
331 }
332
333 return uuid_of;
334}
335
337{
338 static std::unordered_set<std::string> created;
339 constexpr std::size_t kCreatedCap = 1u << 20;
340 if (created.size() > kCreatedCap)
341 created.clear();
342
343 const std::string text = std::string("route:") + provsql_route_name(route);
344 const pg_uuid_t token =
345 provsqlUuidV5("annotation" + uuid2string(child) + text);
346 if (created.insert(uuid2string(token)).second)
348 false, 0, 0, text.c_str());
349 return token;
350}
351
353{
354 static std::unordered_set<std::string> created;
355 constexpr std::size_t kCreatedCap = 1u << 20;
356 if (created.size() > kCreatedCap)
357 created.clear();
358
359 const pg_uuid_t token =
360 provsqlUuidV5("assumedabsorptive" + uuid2string(child));
361 if (created.insert(uuid2string(token)).second) {
362 /* The route tag, not the assumption kind, is what identifies this as the
363 * reachability compiler's output (see provsql_route). */
366 "absorptive");
367 }
368 return token;
369}
Boolean provenance circuit with support for knowledge compilation.
constexpr unsigned DNNF_CERT_INFO
d-DNNF certificate value for the (gate-type-specific) per-gate info field.
@ 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.
@ MULIN
Multivalued-input gate (one of several options).
pg_uuid_t wrapRoute(const pg_uuid_t &child, provsql_route route)
Wrap a materialised root in a transparent annotation naming the route that produced it,...
std::unordered_map< gate_t, pg_uuid_t, hash_gate_t > materializeCertifiedDD(const dDNNF &dd, const std::vector< gate_t > &roots, provsql_route route)
Materialise (the reachable part of) a certified d-D into the mmap store.
void provsql_sha1(const unsigned char *data, size_t len, unsigned char out[20])
SHA-1 of len bytes of data (RFC 3174).
pg_uuid_t wrapAssumedAbsorptive(const pg_uuid_t &child)
Wrap a materialised root in the 'absorptive' assumption marker and return the wrapper's UUID.
pg_uuid_t provsqlUuidV5(const std::string &name)
RFC 4122 version-5 UUID in the ProvSQL namespace.
void provsql_sha1_final(provsql_sha1_ctx *ctx, unsigned char out[20])
The SHA-1 of all the bytes given to ctx.
void provsql_sha1_init(provsql_sha1_ctx *ctx)
Start an incremental SHA-1.
void provsql_sha1_update(provsql_sha1_ctx *ctx, const unsigned char *data, size_t len)
Hash len more bytes of data.
Content-addressed materialisation of a certified d-D into the mmap provenance store.
gate_t
Strongly-typed gate identifier.
Definition Circuit.h:53
bool isDNNFCertified(gate_t g) const
Is gate g certified by the d-DNNF per-gate marking?
double getProb(gate_t g) const
Return the probability stored for gate g.
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
uuid getUUID(gate_t g) const
Return the UUID string associated with gate g.
Definition Circuit.hpp:65
A d-DNNF circuit supporting exact probabilistic and game-theoretic evaluation.
Definition dDNNF.h:71
#define provsql_error(fmt,...)
Report a fatal ProvSQL error and abort the current transaction.
void provsql_internal_create_gate(const pg_uuid_t *token, gate_type type, unsigned nb_children, const pg_uuid_t *children_data)
Internal entry point behind create_gate(): cache + worker IPC.
void provsql_internal_create_gate_with(const pg_uuid_t *token, gate_type type, unsigned nb_children, const pg_uuid_t *children, bool has_infos, unsigned info1, unsigned info2, const char *extra)
Create a gate together with its infos and its text, in one message that is not answered.
provsql_set_prob_result provsql_internal_set_prob(const pg_uuid_t *token, double prob, double *existing)
Write a gate's probability from in-extension C/C++ code.
Background worker and IPC primitives for mmap-backed circuit storage.
@ PROVSQL_SET_PROB_ALREADY_SET
Holds a different value; refused.
Core types, constants, and utilities shared across ProvSQL.
#define PROVSQL_GATE_ZERO_UUID
UUID of the semiring zero gate: the result of the SQL function gate_zero(), created with the extensio...
#define PROVSQL_GATE_ONE_UUID
UUID of the semiring one gate, the result of gate_one().
@ 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...
provsql_route
Tags identifying the planner-time route that produced a circuit.
@ PROVSQL_ROUTE_NONE
No route rewrite: ordinary lineage.
@ PROVSQL_ROUTE_REACHABILITY
Recursive-reachability compiler (src/reachability_evaluate.cpp).
static const char * provsql_route_name(provsql_route route)
The name of a route, as the probability dispatcher reports it and as the annotation wrapper of a mate...
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.
The state of an incremental SHA-1: the digest of a text given in pieces, without holding it whole (th...
uint64_t len
Bytes hashed so far.
unsigned char block[64]
The bytes not yet hashed, short of a block.
size_t used
How many of block are used.
uint32_t h[5]
Hash state.