ProvSQL C/C++ API
Adding support for provenance and uncertainty management to PostgreSQL databases
Loading...
Searching...
No Matches
GenericCircuit.hpp
Go to the documentation of this file.
1/**
2 * @file GenericCircuit.hpp
3 * @brief Template implementation of @c GenericCircuit::evaluate().
4 *
5 * Provides the out-of-line definition of the @c evaluate() template method
6 * declared in @c GenericCircuit.h. This file must be included (directly
7 * or transitively) by any translation unit that instantiates
8 * @c GenericCircuit::evaluate<S>() for a specific semiring type @c S.
9 *
10 * The @c evaluate() method performs a post-order traversal of the sub-circuit
11 * rooted at gate @p g, looking up input-gate values from @p provenance_mapping
12 * and combining them using the semiring operations:
13 *
14 * | Gate type | Semiring operation |
15 * |-------------|-------------------------------|
16 * | gate_input | lookup in @p provenance_mapping (else @c unmapped_input) |
17 * | gate_plus | @c semiring.plus(children) |
18 * | gate_times | @c semiring.times(children) |
19 * | gate_monus | @c semiring.monus(left, right) |
20 * | gate_delta | @c semiring.delta(child) |
21 * | gate_cmp | @c semiring.cmp(left, op, right)|
22 * | gate_semimod| @c semiring.semimod(x, s) |
23 * | gate_agg | @c semiring.agg(op, children) |
24 * | gate_value | @c semiring.value(string) |
25 * | gate_one | @c semiring.one() |
26 * | gate_zero | @c semiring.zero() |
27 * | gate_rv | @c semiring.rv(spec, params) |
28 * | gate_arith | @c semiring.arith(op, children, extra) |
29 * | gate_mixture| @c semiring.mixture(p, x, y) / @c semiring.categorical(…) |
30 * | gate_case | @c semiring.guarded_case(children) |
31 * | gate_observe| @c semiring.observe(child, datum) |
32 * | gate_conditioned | @c semiring.conditioned(children) |
33 *
34 * The last six are measure-carrier gates with no algebraic reading: the
35 * @c Semiring base class refuses them, and only the symbolic @c Formula
36 * pseudo-semiring overrides the hooks (to render them rather than
37 * interpret them).
38 */
39#include "GenericCircuit.h"
40#include "FixSystemGraph.h"
41
42#include <deque>
43#include <map>
44#include <set>
45#include <functional>
46#include <queue>
47
48extern "C" {
49#include "utils/lsyscache.h"
50#include "miscadmin.h" // check_stack_depth
51#include "provsql_interrupt.h"
52}
53
54template<typename S, std::enable_if_t<std::is_base_of_v<semiring::Semiring<typename S::value_type>, S>, int> >
55const typename S::value_type &GenericCircuit::evaluate(gate_t g, std::unordered_map<gate_t, typename S::value_type> &provenance_mapping, S semiring) const
56{
57 /* Iterative post-order evaluation with @p provenance_mapping doubling as
58 * the memoisation table. Provenance circuits can be as deep as the data
59 * (a recursive fixpoint's times/plus chain, the decomposition-aligned
60 * reachability circuits of path-like graphs), so recursion on wires
61 * would overflow the C stack -- the previous implementation turned that
62 * into a "stack depth limit exceeded" error at a few thousand levels;
63 * the explicit stack removes the ceiling altogether. Every computed
64 * gate is memoised (a gate's semiring value is a pure function of the
65 * gate), so shared sub-DAGs are evaluated once and gate-creating
66 * semirings (BoolExpr, formula) preserve the sharing structurally. */
67 std::vector<gate_t> stack{g};
68 /* Equation systems already solved in this evaluation, one value per
69 * unknown: every gate_fixpoint over the same system reads from it. */
70 std::unordered_map<gate_t, std::vector<typename S::value_type> > systems;
71
72 while(!stack.empty()) {
73 const gate_t u = stack.back();
75
76 /* The side-band assumption checks run BEFORE the memoisation
77 * lookup: input leaves are preloaded into @p provenance_mapping
78 * from the mapping table, and a fold collapse can redirect a
79 * marked gate onto such a leaf -- the marker must still refuse
80 * incompatible semirings there. */
81
82 /* In-memory Boolean-assumption marker (set by
83 * @c foldBooleanIdentities on gates whose wires were rewritten
84 * under a Boolean-only rule). Mirrors the @c gate_assumed
85 * structural-marker check below but applies to gates that keep
86 * their original type (the rule mutated their wires in place ;
87 * the persistent mmap was not touched). Same compatibility
88 * predicate, same failure mode. */
89 if(isBooleanAssumed(u) && !semiring.compatibleWithBooleanRewrite())
90 throw CircuitException(
91 "The requested semiring does not admit a homomorphism "
92 "from Boolean functions; this gate's wires were rewritten "
93 "under a Boolean-only rule (times-idempotence or "
94 "times-absorbs-plus, applied under the 'boolean' "
95 "provenance class) and the evaluation is unsound under "
96 "this semiring. Re-run under a more general provenance "
97 "class, or pick a Boolean-compatible semiring (boolean, "
98 "boolexpr, formula, ...).");
99
100 /* In-memory absorptive-assumption marker (set by the absorptive
101 * fold rules: plus-idempotence, plus-with-one absorber,
102 * plus-absorbs-times). Sound in every absorptive semiring; a
103 * semiring tolerating the stronger Boolean rewrite tolerates this
104 * weaker, Boolean-function-preserving one as well. */
105 if(isAbsorptiveAssumed(u) && !semiring.absorptive()
106 && !semiring.compatibleWithBooleanRewrite())
107 throw CircuitException(
108 "The requested semiring is not absorptive; this gate's "
109 "wires were rewritten under an absorptive rule "
110 "(plus-idempotence, plus-with-one absorber or "
111 "plus-absorbs-times, applied under the 'absorptive' or "
112 "'boolean' provenance class) and the evaluation is "
113 "unsound under this semiring. Re-run under the "
114 "'semiring' provenance class, or pick an absorptive "
115 "semiring (probability, boolean, nonnegative "
116 "tropical, ...).");
117
118 if(provenance_mapping.find(u) != provenance_mapping.end()) {
119 stack.pop_back();
120 continue;
121 }
122
123 const auto t = getGateType(u);
124
125 /* Leaves. */
126 switch(t) {
127 case gate_one:
128 case gate_update:
129 provenance_mapping.emplace(u, semiring.one());
130 stack.pop_back();
131 continue;
132 case gate_input:
133 case gate_mulinput:
134 // A variable leaf the provenance mapping did not name. By default
135 // it contributes no provenance (the semiring's one); a rendering
136 // semiring overrides unmapped_input to identify it instead.
137 provenance_mapping.emplace(u, semiring.unmapped_input(getUUID(u)));
138 stack.pop_back();
139 continue;
140 case gate_zero:
141 provenance_mapping.emplace(u, semiring.zero());
142 stack.pop_back();
143 continue;
144 case gate_value:
145 provenance_mapping.emplace(u, semiring.value(getExtra(u)));
146 stack.pop_back();
147 continue;
148 case gate_assumed:
149 /* Structural assumption marker: the wrapped sub-circuit was
150 * computed under the assumption named by the gate's label (the
151 * extra string; a gate stored without a label defaults to
152 * 'boolean'). Identity for semirings satisfying
153 * the assumption; fatal for the rest, since otherwise we would
154 * silently return a value the semiring's semantics does not
155 * justify.
156 *
157 * - 'boolean': the sub-circuit only preserves the Boolean
158 * function of the lineage (e.g. the safe-query rewrite
159 * collapses derivation multiplicities into a single witness);
160 * sound for semirings admitting a homomorphism from Boolean
161 * functions.
162 * - 'absorptive': the sub-circuit only represents the
163 * absorptive (Sorp) quotient of the recursive provenance --
164 * compiled by the bounded-treewidth reachability route (whose world
165 * enumeration surfaces exactly the minimal derivation
166 * supports); longer derivations are absorbed in any
167 * absorptive semiring but genuinely missing for the rest
168 * (Deutch, Milo, Roy & Tannen, ICDT 2014). */
169 {
170 const std::string assumption = getExtra(u);
171 if(assumption.empty() || assumption == "boolean") {
172 if(!semiring.compatibleWithBooleanRewrite())
173 throw CircuitException(
174 "The requested semiring does not admit a homomorphism "
175 "from Boolean functions; the wrapped sub-circuit was "
176 "computed under a Boolean-provenance assumption "
177 "(typically by the safe-query rewrite, "
178 "provenance class 'boolean') and the evaluation is "
179 "unsound under this semiring. Re-run the query under "
180 "a more general provenance class, or pick a "
181 "Boolean-compatible semiring (boolean, boolexpr, "
182 "formula, ...).");
183 } else if(assumption == "absorptive") {
184 if(semiring.absorptive() && !semiring.commutative())
185 throw CircuitRefusal(
186 PROVSQL_GAP, "absorptive-noncommutative",
187 "The wrapped sub-circuit only represents the absorptive "
188 "quotient of a recursive query's provenance (fixpoint "
189 "truncation or compiled reachability circuit), whose "
190 "products are not in the order of the query, and the "
191 "requested semiring is not commutative. Re-run the "
192 "query under the 'semiring' provenance class.");
193 /* The absorptive quotient determines the Boolean function of
194 * the lineage, so a semiring tolerating the stronger Boolean
195 * rewrite tolerates it too -- in practice Formula, which
196 * serialises the circuit rather than evaluating it, and so
197 * renders the truncated or compiled structure faithfully. */
198 if(!semiring.absorptive() && !semiring.compatibleWithBooleanRewrite())
199 throw CircuitException(
200 "The requested semiring is not absorptive; the "
201 "wrapped sub-circuit only represents the absorptive "
202 "quotient of a recursive query's provenance "
203 "(fixpoint truncation or compiled reachability "
204 "circuit), so its value is only defined for "
205 "absorptive semirings (probability, boolean, "
206 "nonnegative tropical, ...) and for formula, "
207 "which renders it as it is. Counting and why-provenance of such a "
208 "recursion are genuinely infinite: a tuple derived "
209 "through itself gains a derivation per round, which "
210 "cyclic data does and so does a null-padded row that "
211 "re-derives itself or a projection onto constants, on "
212 "acyclic data.");
213 /* CAVEAT: absorptive() is a coarser gate than the compiled
214 * reachability route's actual soundness condition. That route
215 * materialises its world enumeration with genuine negation: each
216 * absent edge surfaces as monus(one, edge) (BooleanGate::NOT
217 * lowered to gate_monus; see ReachabilityCompiler.cpp and
218 * CertifiedDDMaterialize.cpp). The absorptive-quotient value
219 * comes out right only because, in every absorptive semiring we
220 * currently ship, (i) monus(one, x) is the times-neutral 'one' on
221 * a present-priced leaf, so the negative literals do not perturb
222 * the path-products, and (ii) any world a negative literal would
223 * kill is dominated by an edge-superset of equal value, hence
224 * absorbed. semiring.absorptive() checks NEITHER property. A
225 * future or user-defined absorptive m-semiring whose monus(one, .)
226 * is not the times-neutral, or whose monus is not
227 * "drop-if-dominated", would pass this gate yet read those
228 * monus(one, edge) gates with a value the path-sum argument does
229 * not justify -- a silently wrong result. If such a semiring is
230 * added, strengthen this guard (e.g. assert monus(one, x) == one
231 * for present-priced leaves, or add a dedicated capability flag)
232 * rather than relying on absorptive() alone. (Truncated cyclic
233 * recursion, the other 'absorptive' producer, ships only minimal
234 * derivations and carries no such negation, so it is unaffected.) */
235 } else
236 throw CircuitException(
237 "Unknown assumption marker '" + assumption + "'");
238 }
239 break;
240 case gate_fixpoint: {
241 /* A component of the least solution of an equation system: solved
242 * once per evaluation, for the whole system, without visiting the
243 * system's wires as an ordinary sub-circuit (its unknowns have no
244 * value of their own). */
245 const auto &w = getWires(u);
246 if(w.size() != 1 || getGateType(w[0]) != gate_fixsystem)
247 throw CircuitException(
248 "gate_fixpoint must have exactly one child, a gate_fixsystem");
249 auto it = systems.find(w[0]);
250 if(it == systems.end()) {
251 it = systems.emplace(
252 w[0], solveFixSystem(w[0], provenance_mapping, semiring)).first;
253 solved_systems.emplace_back(
254 w[0], std::make_shared<std::vector<typename S::value_type> >(it->second));
255 }
256 const unsigned idx = getInfos(u).first;
257 if(idx < 1 || idx > it->second.size())
258 throw CircuitException("gate_fixpoint index out of range");
259 provenance_mapping.emplace(u, it->second[idx-1]);
260 stack.pop_back();
261 continue;
262 }
263 case gate_fixvar:
264 case gate_fixsystem:
265 throw CircuitException(
266 "An equation system or one of its unknowns has no value of "
267 "its own; it is read through a gate_fixpoint");
268 case gate_cmp:
269 {
270 bool ok;
271 cmpOpFromOid(getInfos(u).first, ok);
272 if(!ok)
273 throw CircuitException(
274 "Comparison operator OID " +
275 std::to_string(getInfos(u).first) +
276 " not supported");
277 break;
278 }
279 default:
280 break;
281 }
282
283 /* Internal gate: make sure every child is computed first. */
284 {
285 bool ready = true;
286 for(const auto &c : getWires(u))
287 if(provenance_mapping.find(c) == provenance_mapping.end()) {
288 stack.push_back(c);
289 ready = false;
290 }
291 if(!ready)
292 continue;
293 }
294
295 const auto childValue = [&](int i) -> const typename S::value_type & {
296 return provenance_mapping.at(getWires(u)[i]);
297 };
298
299 switch(t) {
300 case gate_plus:
301 case gate_times:
302 case gate_monus: {
303 /* The children's values read in place: a formula's may be large */
304 using V = typename S::value_type;
305 std::vector<const V *> children;
306 for(const auto &c : getWires(u))
307 children.push_back(&provenance_mapping.at(c));
308 /* Drop the children equal to @p e */
309 const auto drop = [&children](const V &e) {
310 children.erase(std::remove_if(children.begin(), children.end(),
311 [&e](const V *x) { return *x == e; }),
312 children.end());
313 };
314 if(t==gate_plus) {
315 drop(semiring.zero());
316 provenance_mapping.emplace(u, semiring.plus_of(children));
317 } else if(t==gate_times) {
318 const V zero = semiring.zero();
319 if(std::any_of(children.begin(), children.end(),
320 [&zero](const V *x) { return *x == zero; }))
321 provenance_mapping.emplace(u, zero);
322 else {
323 drop(semiring.one());
324 provenance_mapping.emplace(u, semiring.times_of(children));
325 }
326 } else {
327 if(*children[0]==semiring.zero() || *children[0]==*children[1])
328 provenance_mapping.emplace(u, semiring.zero());
329 else
330 provenance_mapping.emplace(u, semiring.monus(*children[0], *children[1]));
331 }
332 break;
333 }
334
335 case gate_delta:
336 provenance_mapping.emplace(u, semiring.delta(childValue(0)));
337 break;
338
339 case gate_project:
340 case gate_eq:
341 case gate_annotation:
342 case gate_assumed:
343 // Where-provenance gates, the transparent annotation wrapper and the
344 // (compatibility-checked above) Boolean-assumption marker: identity
345 // for every admissible semiring. The annotation's extra string is
346 // inert metadata at evaluation time.
347 provenance_mapping.emplace(u, childValue(0));
348 break;
349
350 case gate_cmp:
351 {
352 bool ok;
353 ComparisonOperator op = cmpOpFromOid(getInfos(u).first, ok);
354 provenance_mapping.emplace(u, semiring.cmp(childValue(0), op, childValue(1)));
355 break;
356 }
357
358 case gate_semimod:
359 provenance_mapping.emplace(u, semiring.semimod(childValue(0), childValue(1)));
360 break;
361
362 case gate_agg:
363 {
364 auto infos = getInfos(u);
365
367
368 std::vector<typename S::value_type> vec;
369 for(const auto &c : getWires(u))
370 vec.push_back(provenance_mapping.at(c));
371 provenance_mapping.emplace(u, semiring.agg(op, vec));
372 break;
373 }
374
375 case gate_conditioned: {
376 /* Conditioning marker: P(·|C) requires a normalising division that
377 * no general semiring provides (m-semirings have monus, not a
378 * multiplicative inverse). A conditioned token is evaluable only
379 * in the measure interpretation (probability_evaluate, special-
380 * cased at the root, or the random-variable / agg_token
381 * distribution evaluators); the base-class hook refuses it for
382 * every semiring but the symbolic Formula, which renders the
383 * marker instead of interpreting it. */
384 std::vector<typename S::value_type> vec;
385 for(const auto &c : getWires(u))
386 vec.push_back(provenance_mapping.at(c));
387 provenance_mapping.emplace(u, semiring.conditioned(vec));
388 break;
389 }
390
391 case gate_mobius: {
392 /* The signed Möbius combination is a probability-only shortcut layered
393 * over the normal provenance: the gate carries the literal lineage as a
394 * designated child marked "L:<uuid>" in extra. Every non-probability
395 * evaluator (this semiring path, hence Shapley / Banzhaf / PROV export)
396 * is TRANSPARENT to that lineage, so the token behaves like the ordinary
397 * provenance of the query. A nested gate_mobius (an inner
398 * inclusion-exclusion step) carries no lineage: its value is never used
399 * (the root passes through to the top lineage), but it must not throw, so
400 * it falls back to its first child. */
401 const std::string ex = getExtra(u);
402 gate_t lineage = u; // sentinel: not found
403 const std::string key = "L:";
404 std::size_t p = ex.find(key);
405 if(p != std::string::npos) {
406 std::size_t e = ex.find(' ', p);
407 const std::string luid =
408 ex.substr(p + key.size(),
409 e == std::string::npos ? std::string::npos : e - p - key.size());
410 for(const auto &c : getWires(u))
411 if(getUUID(c) == luid) { lineage = c; break; }
412 }
413 if(lineage != u)
414 provenance_mapping.emplace(u, provenance_mapping.at(lineage));
415 else
416 provenance_mapping.emplace(u, childValue(0));
417 break;
418 }
419
420 case gate_case: {
421 /* Guarded selection over scalar (RV) children: a value chosen by the
422 * first satisfied guard event. This is a measure/RV-carrier operation
423 * (the guards are probabilistic events, the values random variables), not
424 * a semiring one -- evaluable only through the random-variable / measure
425 * evaluators (expected / variance / support / probability / sample),
426 * exactly like gate_rv and gate_arith over RVs. */
427 std::vector<typename S::value_type> vec;
428 for(const auto &c : getWires(u))
429 vec.push_back(provenance_mapping.at(c));
430 provenance_mapping.emplace(u, semiring.guarded_case(vec));
431 break;
432 }
433
434 /* The measure-carrier gates below have no algebraic reading either:
435 * their base-class hooks refuse them for every proper semiring, and
436 * Formula overrides them to render the sub-circuit symbolically. */
437 case gate_rv: {
438 /* A gate_rv is a leaf unless one of its distribution parameters is
439 * wired ("$i" in the extra encoding), which makes it a compound
440 * (latent-variable) leaf over the values of its wires. */
441 std::vector<typename S::value_type> params;
442 for(const auto &c : getWires(u))
443 params.push_back(provenance_mapping.at(c));
444 provenance_mapping.emplace(u, semiring.rv(getExtra(u), params));
445 break;
446 }
447
448 case gate_arith: {
449 bool ok;
450 ArithmeticOperator op = arithOpFromTag(getInfos(u).first, ok);
451 if(!ok)
452 throw CircuitException(
453 "Arithmetic operator tag " +
454 std::to_string(getInfos(u).first) +
455 " not supported");
456 std::vector<typename S::value_type> vec;
457 for(const auto &c : getWires(u))
458 vec.push_back(provenance_mapping.at(c));
459 provenance_mapping.emplace(u, semiring.arith(op, vec, getExtra(u)));
460 break;
461 }
462
463 case gate_mixture: {
464 const auto &w = getWires(u);
465 if(isCategoricalMixture(u)) {
466 /* [key, mul_1, …, mul_n]: each outcome's probability lives in the
467 * mulinput's prob and its value in the mulinput's extra (those
468 * leaves evaluate to one() on their own, so the payload has to be
469 * read off the gate here). */
470 std::vector<double> probs;
471 std::vector<std::string> outcomes;
472 for(std::size_t i = 1; i < w.size(); ++i) {
473 probs.push_back(getProb(w[i]));
474 outcomes.push_back(getExtra(w[i]));
475 }
476 provenance_mapping.emplace(
477 u, semiring.categorical(childValue(0), probs, outcomes));
478 } else {
479 if(w.size() != 3)
480 throw CircuitException(
481 "gate_mixture must have exactly three children "
482 "[p_token, x_token, y_token]");
483 provenance_mapping.emplace(
484 u, semiring.mixture(childValue(0), childValue(1), childValue(2)));
485 }
486 break;
487 }
488
489 case gate_observe: {
490 const auto &w = getWires(u);
491 if(w.size() != 1)
492 throw CircuitException(
493 "gate_observe must have exactly one child (the observed leaf)");
494 provenance_mapping.emplace(u, semiring.observe(childValue(0), getExtra(u)));
495 break;
496 }
497
498 default:
499 throw CircuitException("Invalid gate type for semiring evaluation");
500 }
501
502 /* A rendering (formula) writes out a sub-circuit shared by several
503 * gates at each of them, and may grow exponentially with the circuit:
504 * stop as it passes what PostgreSQL can return, not after; and check
505 * the memory budget after a large value, whose gate may be the last
506 * (the root), with no poll to follow. */
507 if constexpr(std::is_same_v<typename S::value_type, std::string>) {
508 const std::size_t size = provenance_mapping.at(u).size();
510 size,
511 "the formula is too large to return (over 1 GB): a sub-circuit "
512 "shared by several gates is written out at each of them");
513 if(provsql_max_memory > 0 && size >= (std::size_t(1) << 20))
515 }
516
517 stack.pop_back();
518 }
519
520 return provenance_mapping.at(g);
521}
522
523template<typename S, std::enable_if_t<std::is_base_of_v<semiring::Semiring<typename S::value_type>, S>, int> >
524std::vector<typename S::value_type> GenericCircuit::solveFixSystem(gate_t sys, std::unordered_map<gate_t, typename S::value_type> &provenance_mapping, S semiring) const
525{
526 using V = typename S::value_type;
527
528 const auto &w = getWires(sys);
529 if(w.size() % 2)
530 throw CircuitException("gate_fixsystem must have an even number of wires");
531 const std::size_t n = w.size() / 2;
532
533 std::unordered_map<gate_t, std::size_t> unknown;
534 for(std::size_t i = 0; i < n; ++i) {
535 if(getGateType(w[i]) != gate_fixvar)
536 throw CircuitException(
537 "The first half of a gate_fixsystem's wires must be its "
538 "gate_fixvar unknowns");
539 unknown.emplace(w[i], i);
540 }
541
542 const V zero = semiring.zero(), one = semiring.one();
543 const auto plus2 = [&](const V &a, const V &b) -> V {
544 if(semiring.equal(a, zero)) return b;
545 if(semiring.equal(b, zero)) return a;
546 return semiring.plus(std::vector<V>{a, b});
547 };
548 const auto times2 = [&](const V &a, const V &b) -> V {
549 if(semiring.equal(a, zero) || semiring.equal(b, zero)) return zero;
550 if(semiring.equal(a, one)) return b;
551 if(semiring.equal(b, one)) return a;
552 return semiring.times(std::vector<V>{a, b});
553 };
554 /* l ⊗ x ⊗ r, in this order: ⊗ need not commute. */
555 const auto times3 = [&](const V &l, const V &x, const V &r) -> V {
556 return times2(times2(l, x), r);
557 };
558
559 /* Which gates depend on an unknown: an iterative post-order, since the
560 * sub-circuits that do not (the input tokens' own provenance) can be as
561 * deep as the data. Another system's gate_fixpoint is a constant here;
562 * an unknown of another system cannot occur. */
563 std::unordered_map<gate_t, bool> dep;
564 {
565 std::vector<gate_t> st;
566 for(std::size_t i = n; i < w.size(); ++i)
567 st.push_back(w[i]);
568 while(!st.empty()) {
569 const gate_t u = st.back();
570 if(dep.count(u)) { st.pop_back(); continue; }
571 const auto t = getGateType(u);
572 if(t == gate_fixvar) {
573 if(!unknown.count(u))
574 throw CircuitException(
575 "An unknown of another equation system occurs in this one");
576 dep.emplace(u, true);
577 st.pop_back();
578 continue;
579 }
580 if(t == gate_fixpoint) {
581 dep.emplace(u, false);
582 st.pop_back();
583 continue;
584 }
585 bool ready = true;
586 for(const auto &c : getWires(u))
587 if(!dep.count(c)) { st.push_back(c); ready = false; }
588 if(!ready) continue;
589 bool d = false;
590 for(const auto &c : getWires(u))
591 d = d || dep.at(c);
592 dep.emplace(u, d);
593 st.pop_back();
594 }
595 }
596
597 /* Linear form b ⊕ ⨁_j l_j ⊗ x_j ⊗ r_j of a gate that depends on the
598 * unknowns, the factors on either side of an unknown kept apart, as ⊗
599 * need not commute. Only the gates between an equation's root and its
600 * unknowns are visited here, a part of the circuit as shallow as the
601 * recursive term itself, so the recursion is bounded by the query, not
602 * the data. */
603 struct Term {
604 std::size_t j;
605 V l, r;
606 };
607 struct Lin {
608 V c;
609 std::vector<Term> terms;
610 };
611 std::unordered_map<gate_t, Lin> lin;
612 std::function<const Lin &(gate_t)> linear = [&](gate_t u) -> const Lin & {
613 auto it = lin.find(u);
614 if(it != lin.end())
615 return it->second;
616
617 if(isBooleanAssumed(u) && !semiring.compatibleWithBooleanRewrite())
618 throw CircuitException(
619 "The requested semiring does not admit a homomorphism from "
620 "Boolean functions; a gate of this recursion's equations was "
621 "rewritten under a Boolean-only rule");
622 if(isAbsorptiveAssumed(u) && !semiring.absorptive()
623 && !semiring.compatibleWithBooleanRewrite())
624 throw CircuitException(
625 "The requested semiring is not absorptive; a gate of this "
626 "recursion's equations was rewritten under an absorptive rule");
627
628 Lin r{zero, {}};
629 const auto t = getGateType(u);
630 switch(t) {
631 case gate_fixvar:
632 r.terms.push_back(Term{unknown.at(u), one, one});
633 break;
634
635 case gate_plus:
636 for(const auto &c : getWires(u)) {
637 if(dep.at(c)) {
638 const Lin &l = linear(c);
639 r.c = plus2(r.c, l.c);
640 r.terms.insert(r.terms.end(), l.terms.begin(), l.terms.end());
641 } else
642 r.c = plus2(r.c, evaluate(c, provenance_mapping, semiring));
643 }
644 break;
645
646 case gate_times: {
647 /* The factors before the unknown, and those after it. */
648 V kl = one, kr = one;
649 gate_t var = u;
650 for(const auto &c : getWires(u)) {
651 if(dep.at(c)) {
652 if(var != u)
653 throw CircuitRefusal(
654 PROVSQL_GAP, "recursion-nonlinear",
655 "This recursion's equations are not linear: a product "
656 "has two factors depending on the recursive relation");
657 var = c;
658 } else if(var == u)
659 kl = times2(kl, evaluate(c, provenance_mapping, semiring));
660 else
661 kr = times2(kr, evaluate(c, provenance_mapping, semiring));
662 }
663 const Lin &l = linear(var);
664 if(!semiring.equal(kl, zero) && !semiring.equal(kr, zero)) {
665 r.c = times3(kl, l.c, kr);
666 for(const auto &t : l.terms)
667 r.terms.push_back(Term{t.j, times2(kl, t.l), times2(t.r, kr)});
668 }
669 break;
670 }
671
672 case gate_assumed: {
673 const std::string assumption = getExtra(u);
674 if((assumption.empty() || assumption == "boolean")
675 && !semiring.compatibleWithBooleanRewrite())
676 throw CircuitException(
677 "The requested semiring does not admit a homomorphism from "
678 "Boolean functions; part of this recursion's equations was "
679 "computed under a Boolean-provenance assumption");
680 if(assumption == "absorptive" && semiring.absorptive() &&
681 !semiring.commutative())
682 throw CircuitRefusal(
683 PROVSQL_GAP, "absorptive-noncommutative",
684 "Part of this recursion's equations was computed under an "
685 "absorptive assumption, whose products are not in the "
686 "order of the query, and the requested semiring is not "
687 "commutative. Re-run the query under the 'semiring' "
688 "provenance class.");
689 if(assumption == "absorptive" && !semiring.absorptive()
690 && !semiring.compatibleWithBooleanRewrite())
691 throw CircuitException(
692 "The requested semiring is not absorptive; part of this "
693 "recursion's equations was computed under an absorptive "
694 "assumption");
695 r = linear(getWires(u)[0]);
696 break;
697 }
698
699 case gate_project:
700 case gate_eq:
701 case gate_annotation:
702 r = linear(getWires(u)[0]);
703 break;
704
705 default:
706 throw CircuitRefusal(
707 PROVSQL_GAP, "recursion-nonlinear",
708 std::string("This recursion's equations are not linear "
709 "semiring expressions in the recursive relation "
710 "(gate of type ") + gate_type_name[t] +
711 " over it)");
712 }
713 return lin.emplace(u, std::move(r)).first->second;
714 };
715
716 /* x_i = b[i] ⊕ ⨁ l ⊗ x_j ⊗ r over in[i] = {(j, l, r)}; out[j] holds
717 * the same terms, indexed by i. */
718 std::vector<V> b(n, zero);
719 std::vector<std::vector<Term> > in(n), out(n);
720 for(std::size_t i = 0; i < n; ++i) {
721 const gate_t f = w[n + i];
722 if(dep.at(f)) {
723 const Lin &l = linear(f);
724 b[i] = l.c;
725 for(const auto &t : l.terms)
726 if(!semiring.equal(t.l, zero) && !semiring.equal(t.r, zero)) {
727 in[i].push_back(t);
728 out[t.j].push_back(Term{i, t.l, t.r});
729 }
730 } else
731 b[i] = evaluate(f, provenance_mapping, semiring);
732 }
733
734 /* Strongly connected components of the dependency graph j -> i, in
735 * solving order. */
736 std::vector<std::vector<std::size_t> > comps;
737 {
738 std::vector<std::vector<std::size_t> > adj(n);
739 for(std::size_t j = 0; j < n; ++j)
740 for(const auto &e : out[j])
741 adj[j].push_back(e.j);
742 comps = fixSystemComponents(adj);
743 }
744
745 std::vector<V> x(n, zero);
746 std::vector<std::size_t> comp_of(n);
747 for(std::size_t c = 0; c < comps.size(); ++c)
748 for(const auto v : comps[c])
749 comp_of[v] = c;
750
751 /* Better-than in the natural order of an absorptive, selective
752 * semiring: a ⊕ b = a, with a ≠ b. */
753 const auto better = [&](const V &a, const V &b) -> bool {
754 return !semiring.equal(a, b) && semiring.equal(plus2(a, b), a);
755 };
756
757 for(std::size_t ci = 0; ci < comps.size(); ++ci) {
759 const auto &comp = comps[ci];
760
761 /* What flows into the component: b, and the components already
762 * solved. */
763 std::vector<V> entry;
764 entry.reserve(comp.size());
765 bool cyclic = comp.size() > 1;
766 for(const auto i : comp) {
767 V v = b[i];
768 for(const auto &t : in[i]) {
769 if(comp_of[t.j] != ci)
770 v = plus2(v, times3(t.l, x[t.j], t.r));
771 else
772 cyclic = true; // a self-loop makes a singleton cyclic too
773 }
774 entry.push_back(v);
775 }
776
777 if(!cyclic) {
778 /* A tuple not derived through itself: its equation is its value,
779 * exact in every semiring. */
780 x[comp[0]] = entry[0];
781 continue;
782 }
783
784 if(semiring.symbolic()) {
785 /* A rendering semiring: the component's tuples become named unknowns,
786 * and their equations are recorded with them. */
787 for(const auto i : comp)
788 x[i] = semiring.symbolic_unknown(i + 1);
789 for(std::size_t k = 0; k < comp.size(); ++k) {
790 V v = entry[k];
791 for(const auto &t : in[comp[k]])
792 if(comp_of[t.j] == ci)
793 v = plus2(v, times3(t.l, x[t.j], t.r));
794 semiring.define(x[comp[k]], v);
795 }
796 continue;
797 }
798
799 if(!semiring.absorptive()) {
800 if(!semiring.has_star())
801 throw CircuitRefusal(
802 PROVSQL_DELIBERATE, "recursion-cycle-no-value",
803 "This recursion's equations are cyclic (a tuple is derived "
804 "through itself), and the requested semiring is neither "
805 "absorptive nor gives the sum of the powers of a value: the "
806 "least solution is an infinite sum it has no value for.");
807
808 /* Gaussian elimination with star needs every unknown on the same
809 * side of its coefficient: x_i = ⨁ a ⊗ x_j ⊕ e (left-linear), or
810 * x_i = ⨁ x_j ⊗ a ⊕ e (right-linear), which is left-linear in the
811 * semiring with ⊗ reversed, of the same star. An unknown between two
812 * factors, or a mix of both sides, makes the derivations a
813 * context-free language, with no closed form by star. In a
814 * commutative semiring, the side does not matter. */
815 bool right = false;
816 if(!semiring.commutative()) {
817 bool left_ok = true, right_ok = true;
818 for(const auto i : comp)
819 for(const auto &t : in[i])
820 if(comp_of[t.j] == ci) {
821 left_ok = left_ok && semiring.equal(t.r, one);
822 right_ok = right_ok && semiring.equal(t.l, one);
823 }
824 if(!left_ok && !right_ok)
825 throw CircuitRefusal(
826 PROVSQL_GAP, "recursion-two-sided",
827 "This recursion's equations put the recursive relation "
828 "between factors, or on both sides of them, and the "
829 "requested semiring is not commutative: its least "
830 "solution is not given by the star of a value. Write the "
831 "recursive relation at the same place of every recursive "
832 "FROM clause (first, or last).");
833 right = !left_ok;
834 }
835 /* a ⊗ b, or b ⊗ a in the reversed semiring. */
836 const auto mul = [&](const V &a, const V &b) -> V {
837 return right ? times2(b, a) : times2(a, b);
838 };
839
840 /* Gaussian elimination with star (node elimination; Ramusat, Maniu &
841 * Senellart, EDBT 2021, after Lehmann 1977): x_v = a_vv* ⊗ (⨁ a_vj
842 * x_j ⊕ e_v) is substituted into the equations reading x_v, one
843 * unknown at a time, then the unknowns are read back in reverse
844 * order. Each step eliminates the unknown adding the fewest new
845 * coefficients, which follows the component's width where it is
846 * small. */
847 const std::size_t k = comp.size();
848 std::unordered_map<std::size_t, std::size_t> at;
849 for(std::size_t p = 0; p < k; ++p)
850 at.emplace(comp[p], p);
851 std::vector<std::map<std::size_t, V> > row(k);
852 std::vector<std::set<std::size_t> > col(k);
853 std::vector<V> e(entry);
854 for(std::size_t p = 0; p < k; ++p)
855 for(const auto &t : in[comp[p]]) {
856 if(comp_of[t.j] != ci)
857 continue;
858 const V a = semiring.commutative() ? times2(t.l, t.r)
859 : right ? t.r : t.l;
860 const std::size_t q = at.at(t.j);
861 auto it = row[p].find(q);
862 row[p][q] = it == row[p].end() ? a : plus2(it->second, a);
863 col[q].insert(p);
864 }
865
866 std::vector<char> gone(k, 0);
867 std::vector<std::size_t> order;
868 for(std::size_t step = 0; step < k; ++step) {
870 std::size_t v = k, best = 0;
871 for(std::size_t p = 0; p < k; ++p) {
872 if(gone[p])
873 continue;
874 const std::size_t cost = row[p].size() * col[p].size();
875 if(v == k || cost < best) {
876 v = p;
877 best = cost;
878 }
879 }
880 V loop = zero;
881 auto self = row[v].find(v);
882 if(self != row[v].end()) {
883 loop = self->second;
884 row[v].erase(self);
885 col[v].erase(v);
886 }
887 const V s = semiring.star(loop);
888 for(auto &[j, b] : row[v])
889 b = mul(s, b);
890 e[v] = mul(s, e[v]);
891 for(const auto p : std::vector<std::size_t>(col[v].begin(), col[v].end())) {
892 if(gone[p] || p == v)
893 continue;
894 const V c = row[p].at(v);
895 row[p].erase(v);
896 for(const auto &[j, b] : row[v]) {
897 auto it = row[p].find(j);
898 const V t = mul(c, b);
899 row[p][j] = it == row[p].end() ? t : plus2(it->second, t);
900 col[j].insert(p);
901 }
902 e[p] = plus2(e[p], mul(c, e[v]));
903 }
904 gone[v] = 1;
905 order.push_back(v);
906 }
907 for(std::size_t r = order.size(); r-- > 0; ) {
908 const std::size_t v = order[r];
909 V val = e[v];
910 for(const auto &[j, b] : row[v])
911 val = plus2(val, mul(b, x[comp[j]]));
912 x[comp[v]] = val;
913 }
914 continue;
915 }
916
917 std::unordered_map<std::size_t, std::size_t> pos;
918 for(std::size_t k = 0; k < comp.size(); ++k) {
919 pos.emplace(comp[k], k);
920 x[comp[k]] = entry[k];
921 }
922
923 if(semiring.selective() && semiring.exact_equality()) {
924 /* Dijkstra from the entry values: in an absorptive semiring
925 * extending a derivation never improves it, so with a selective plus
926 * the best unsettled value is final (Ramusat, Maniu & Senellart,
927 * EDBT 2021). */
928 const auto worse = [&](const std::pair<V, std::size_t> &p,
929 const std::pair<V, std::size_t> &q) {
930 return better(q.first, p.first);
931 };
932 std::priority_queue<std::pair<V, std::size_t>,
933 std::vector<std::pair<V, std::size_t> >,
934 decltype(worse)> heap(worse);
935 std::vector<char> settled(comp.size(), 0);
936 for(const auto i : comp)
937 if(!semiring.equal(x[i], zero))
938 heap.emplace(x[i], i);
939 while(!heap.empty()) {
940 auto [v, j] = heap.top();
941 heap.pop();
942 const std::size_t pj = pos.at(j);
943 if(settled[pj] || !semiring.equal(v, x[j]))
944 continue;
945 settled[pj] = 1;
946 for(const auto &t : out[j]) {
947 const std::size_t i = t.j;
948 if(comp_of[i] != ci || settled[pos.at(i)])
949 continue;
950 const V w = plus2(x[i], times3(t.l, x[j], t.r));
951 if(!semiring.equal(w, x[i])) {
952 x[i] = w;
953 heap.emplace(w, i);
954 }
955 }
956 }
957 } else if(semiring.exact_equality()) {
958 /* Value iteration with a work list (Mohri's generic single-source
959 * algorithm, the residual being superfluous in an idempotent
960 * semiring): a value only moves towards the solution, and
961 * absorption cuts every derivation repeating a tuple, so the
962 * iteration converges. The bound only guards against a semiring
963 * declaring absorption it does not have. */
964 std::size_t nedges = 0;
965 for(const auto i : comp)
966 nedges += in[i].size();
967 const std::size_t bound = (comp.size() + 1) * (nedges + 1);
968 std::size_t steps = 0;
969 std::vector<char> queued(comp.size(), 0);
970 std::deque<std::size_t> queue;
971 for(const auto i : comp)
972 if(!semiring.equal(x[i], zero)) {
973 queue.push_back(i);
974 queued[pos.at(i)] = 1;
975 }
976 while(!queue.empty()) {
978 const std::size_t j = queue.front();
979 queue.pop_front();
980 queued[pos.at(j)] = 0;
981 for(const auto &t : out[j]) {
982 const std::size_t i = t.j;
983 if(comp_of[i] != ci)
984 continue;
985 if(++steps > bound)
986 throw CircuitException(
987 "Value iteration over this recursion's equations does "
988 "not converge; the semiring does not behave "
989 "absorptively");
990 const V w = plus2(x[i], times3(t.l, x[j], t.r));
991 if(!semiring.equal(w, x[i])) {
992 x[i] = w;
993 if(!queued[pos.at(i)]) {
994 queue.push_back(i);
995 queued[pos.at(i)] = 1;
996 }
997 }
998 }
999 }
1000 } else {
1001 /* Values whose equality cannot be tested (gates of a circuit being
1002 * built, ...): run the rounds absorption guarantees to suffice.
1003 * Round r covers the derivations entering the component and taking
1004 * at most r steps inside it; one repeating a tuple is absorbed by
1005 * the shorter one skipping the repetition, and a step-wise
1006 * repetition-free one takes at most |comp| - 1 steps. */
1007 for(std::size_t r = 1; r < comp.size(); ++r) {
1009 std::vector<V> next(entry);
1010 for(std::size_t k = 0; k < comp.size(); ++k)
1011 for(const auto &t : in[comp[k]])
1012 if(comp_of[t.j] == ci)
1013 next[k] = plus2(next[k], times3(t.l, x[t.j], t.r));
1014 for(std::size_t k = 0; k < comp.size(); ++k)
1015 x[comp[k]] = next[k];
1016 }
1017 }
1018 }
1019 return x;
1020}
ArithmeticOperator arithOpFromTag(unsigned tag, bool &ok)
Map a gate_arith operator tag to an ArithmeticOperator.
ComparisonOperator cmpOpFromOid(Oid op_oid, bool &ok)
Map a PostgreSQL comparison-operator OID to a ComparisonOperator.
AggregationOperator getAggregationOperator(Oid oid)
Map a PostgreSQL aggregate function OID to an AggregationOperator.
AggregationOperator
SQL aggregation functions tracked by ProvSQL.
Definition Aggregation.h:52
ComparisonOperator
SQL comparison operators used in gate_cmp circuit gates.
Definition Aggregation.h:40
ArithmeticOperator
Arithmetic operations carried by gate_arith circuit gates.
Definition Aggregation.h:75
gate_t
Strongly-typed gate identifier.
Definition Circuit.h:53
Strongly connected components of the dependency graph of an equation system (a recursive query,...
std::vector< std::vector< std::size_t > > fixSystemComponents(const std::vector< std::vector< std::size_t > > &out)
Strongly connected components of a directed graph, in the order in which equations along its edges ca...
Semiring-agnostic in-memory provenance circuit.
Exception type thrown by circuit operations on invalid input.
Definition Circuit.h:382
A refusal by design, or a known gap, rather than an error.
Definition Circuit.h:409
std::vector< gate_t > & getWires(gate_t g)
Definition Circuit.h:311
gate_type getGateType(gate_t g) const
Definition Circuit.h:301
uuid getUUID(gate_t g) const
Definition Circuit.hpp:65
std::vector< typename S::value_type > solveFixSystem(gate_t sys, std::unordered_map< gate_t, typename S::value_type > &provenance_mapping, S semiring) const
Least solution of the equation system of a gate_fixsystem.
std::map< gate_t, std::pair< unsigned, unsigned > > infos
Per-gate (info1, info2) annotations.
std::vector< std::pair< gate_t, std::shared_ptr< void > > > solved_systems
Equation systems solved by evaluate, with their solutions.
const S::value_type & evaluate(gate_t g, std::unordered_map< gate_t, typename S::value_type > &provenance_mapping, S semiring) const
Evaluate the sub-circuit rooted at gate g over semiring semiring.
bool isCategoricalMixture(gate_t g) const
Test whether g is a categorical-form gate_mixture (the explicit provsql.categorical output).
std::string getExtra(gate_t g) const
Return the string extra for gate g.
double getProb(gate_t g) const
Return the probability for gate g.
bool isAbsorptiveAssumed(gate_t g) const
Report whether g carries the absorptive-assumption flag.
bool isBooleanAssumed(gate_t g) const
Report whether g carries the Boolean-assumption flag.
std::pair< unsigned, unsigned > getInfos(gate_t g) const
Return the integer annotation pair for gate g.
int provsql_max_memory
Memory, in MB, that the evaluations of a statement may add to the backend's resident set,...
Definition provsql.c:131
#define PROVSQL_GAP
#define PROVSQL_DELIBERATE
What kind of limit a refusal or a freezing is.
void provsql_check_result_size(size_t bytes, const char *message)
Throw if a text value of bytes is past what PostgreSQL can hold in a value (1 GB),...
void provsql_check_memory(void)
Throw if the evaluations of the statement have made the backend's resident memory grow by more than p...
Cancellation of the long C++ evaluation loops.
void provsql_poll_interrupt()
Throw where an evaluation is to stop, its query cancelled.
const char * gate_type_name[]
Names of gate types.
@ gate_observe
Latent-variable observation (likelihood-weighting evidence): one wire → an observed bare gate_rv leaf...
@ gate_rv
Continuous random-variable leaf (extra encodes distribution).
@ gate_case
N-ary guarded selection over scalar (RV) children: wires are [guard_1, value_1, .....
@ gate_annotation
Transparent single-child wrapper carrying a query-level annotation in extra (inversion-free certifica...
@ gate_mobius
Signed Möbius combination: a MEASURE-only gate carrying one integer coefficient per child (in extra,...
@ gate_fixpoint
Component of the least solution of an equation system: one wire to a gate_fixsystem,...
@ gate_conditioned
Conditioning marker with two children [target, evidence]: measure-only, probability_evaluate returns ...
@ gate_fixsystem
Linear equation system x_i = f_i(x) of a recursive query, one equation per derived tuple: wires [x_1,...
@ gate_fixvar
Unknown of an equation system (see gate_fixsystem): a leaf standing for the solution of one equation,...
@ gate_mixture
Probabilistic mixture: three wires [p_token (gate_input Bernoulli), x_token, y_token]; samples x when...
@ gate_arith
n-ary arithmetic gate over scalar-valued children (info1 holds operator tag)
@ gate_assumed
Structural marker over a single child whose sub-circuit was computed under a Boolean-provenance assum...