ProvSQL C/C++ API
Adding support for provenance and uncertainty management to PostgreSQL databases
Loading...
Searching...
No Matches
GenericCircuit.cpp
Go to the documentation of this file.
1/**
2 * @file GenericCircuit.cpp
3 * @brief GenericCircuit method implementations.
4 *
5 * Implements the virtual methods of @c GenericCircuit that override the
6 * @c Circuit<gate_type> base class:
7 * - @c addGate(): allocates a new gate and extends the @c prob vector.
8 * - @c setGate(gate_type): creates a new gate, registering it as an
9 * input gate when the type is @c gate_input or @c gate_update.
10 * - @c setGate(const uuid&, gate_type): same with UUID binding.
11 *
12 * The template method @c evaluate() is defined in @c GenericCircuit.hpp.
13 */
14#include "GenericCircuit.h"
15
16#include <functional>
17#include <unordered_set>
18
20{
21 auto id = Circuit::setGate(type);
22 if(type == gate_input || type==gate_update) {
23 inputs.insert(id);
24 }
25 return id;
26}
27
29{
30 auto id = Circuit::setGate(u, type);
31 if(type == gate_input || type==gate_update) {
32 inputs.insert(id);
33 }
34 return id;
35}
36
38{
39 auto id=Circuit::addGate();
40 prob.push_back(1);
41 return id;
42}
43
44#include <unordered_map>
45
47{
48 GenericCircuit &gc = *this;
49 const std::size_t n = gc.getNbGates();
50 bool ever = false; ///< Whether any phase mutated the circuit.
51
52 /* Wrap the three phases in an outer fixpoint loop. Phase 3's
53 * substitutions can re-expose identity wires to a parent that
54 * referenced the collapsed gate (a single-wire @c gate_times / plus
55 * whose sole wire was itself collapsed, a @c gate_zero absorber…),
56 * which is a fresh Phase-1 opportunity. @c createGenericCircuit
57 * loads gates in BFS-from-root order (parents before children), so a
58 * single pass through Phase 1 would propagate identity-collapse in
59 * the wrong direction anyway -- the outer loop handles both effects
60 * with the same machinery. Terminates after at most one iteration
61 * per DAG level. */
62
63 /* Cumulative @c gate -> final-target redirection accumulated across
64 * iterations. We do NOT mutate a collapsed gate to carry its
65 * target's content (the naive content-copy approach): for a target
66 * that is a shared @c gate_input that would duplicate the Bernoulli variable
67 * into an independent copy under the wrong UUID, over-counting the
68 * probability of every non-read-once circuit (a single shared edge
69 * in a recursive reachability lineage, say). Instead we rewire each
70 * parent's wire straight to the target, leaving the collapsed gate
71 * orphaned, and -- after the loop -- patch the UUID map so a gate
72 * resolved by UUID (notably the caller-supplied root) follows the
73 * collapse rather than landing on the orphan. */
74 std::unordered_map<gate_t, gate_t> redirect;
75
76 bool changed = true;
77 while (changed) {
78 changed = false;
79
80 /* Phase 1: drop identity wires in place. Multiplicative identity
81 * is @c gate_one (drop from @c gate_times); additive identity is
82 * @c gate_zero (drop from @c gate_plus). If every wire of a
83 * @c gate_plus / @c gate_times was the identity, the gate is left
84 * with an empty wire list: collapse it to the identity (empty sum
85 * is @c gate_zero, empty product is @c gate_one) by mutating the
86 * gate type in place. */
87 for (std::size_t i = 0; i < n; ++i) {
88 auto g = static_cast<gate_t>(i);
89 auto t = gc.getGateType(g);
90 if (t != gate_times && t != gate_plus) continue;
91 gate_type identity = (t == gate_times) ? gate_one : gate_zero;
92 auto &wires = gc.getWires(g);
93 std::vector<gate_t> kept;
94 kept.reserve(wires.size());
95 for (gate_t c : wires) {
96 if (gc.getGateType(c) != identity) kept.push_back(c);
97 }
98 if (kept.size() != wires.size()) {
99 wires = std::move(kept);
100 changed = true;
101 }
102 if (wires.empty()) {
103 gc.setGateType(g, identity);
104 changed = true;
105 }
106 }
107
108 /* Phase 2: build a substitution map for gates that should be
109 * collapsed to a single descendant after phase 1:
110 * - @c gate_times that still has a @c gate_zero wire ->
111 * substitute to that absorber (multiplicative zero is the
112 * universal absorber across semirings);
113 * - any @c gate_times / @c gate_plus left with exactly one wire
114 * -> substitute to that wire (identity collapse).
115 * The plus-with-one absorber rewrite is intentionally omitted:
116 * @c gate_one is the additive absorber only in idempotent
117 * semirings (Boolean, MinMax) and would silently change the
118 * semantics for @c Counting / @c Formula / etc. Already-redirected
119 * (orphaned) gates are skipped so the fixpoint terminates. */
120 std::unordered_map<gate_t, gate_t> subst;
121 for (std::size_t i = 0; i < n; ++i) {
122 auto g = static_cast<gate_t>(i);
123 if (redirect.count(g)) continue;
124 auto t = gc.getGateType(g);
125 if (t != gate_times && t != gate_plus) continue;
126 const auto &wires = gc.getWires(g);
127 if (t == gate_times) {
128 bool absorbed = false;
129 for (gate_t c : wires) {
130 if (gc.getGateType(c) == gate_zero) {
131 subst[g] = c;
132 absorbed = true;
133 break;
134 }
135 }
136 if (absorbed) continue;
137 }
138 if (wires.size() == 1) subst[g] = wires[0];
139 }
140 /* Resolve transitively so a chain of singleton wrappers maps to
141 * its bottom endpoint in one lookup, chasing both this iteration's
142 * substitutions and earlier ones recorded in @c redirect. */
143 for (auto &kv : subst) {
144 gate_t cur = kv.second;
145 while (subst.count(cur) || redirect.count(cur))
146 cur = subst.count(cur) ? subst[cur] : redirect[cur];
147 kv.second = cur;
148 }
149
150 /* Phase 3: rewire every gate's wires through @c subst so parents
151 * point straight at the collapse target. Shared leaves stay a
152 * single gate (no content-copy, no UUID-aliased duplicate in the
153 * @c inputs set), so probability evaluators see the correct number
154 * of independent variables. Collapsed gates are left orphaned. */
155 if (!subst.empty()) {
156 for (std::size_t i = 0; i < n; ++i) {
157 auto &wires = gc.getWires(static_cast<gate_t>(i));
158 for (gate_t &w : wires) {
159 auto it = subst.find(w);
160 if (it != subst.end()) {
161 w = it->second;
162 changed = true;
163 }
164 }
165 }
166 for (const auto &kv : subst) redirect[kv.first] = kv.second;
167 }
168 ever |= changed;
169 }
170
171 /* Patch the UUID map and the Boolean-assumption set so a gate
172 * resolved by UUID (Circuit::getGate, used for the root and the
173 * joint-circuit roots) follows the collapse instead of landing on an
174 * orphaned wrapper, and so a non-Boolean semiring still refuses on a
175 * circuit whose marked gate was collapsed away. */
176 if (!redirect.empty()) {
177 for (auto &kv : redirect) {
178 gate_t cur = kv.second;
179 while (redirect.count(cur)) cur = redirect[cur];
180 kv.second = cur;
181 }
182 for (const auto &kv : redirect) {
183 gate_t g = kv.first, target = kv.second;
184 pointName(g, target);
185 if (boolean_assumed_gates.count(g)) boolean_assumed_gates.insert(target);
186 if (absorptive_assumed_gates.count(g))
187 absorptive_assumed_gates.insert(target);
188 }
189 }
190
191 return ever;
192}
193
194void GenericCircuit::redirectGates(std::unordered_map<gate_t, gate_t> subst)
195{
196 if (subst.empty()) return;
197 for (auto &kv : subst) {
198 gate_t cur = kv.second;
199 while (subst.count(cur)) cur = subst[cur];
200 kv.second = cur;
201 }
202 const std::size_t n = getNbGates();
203 for (std::size_t i = 0; i < n; ++i)
204 for (gate_t &w : getWires(static_cast<gate_t>(i))) {
205 auto it = subst.find(w);
206 if (it != subst.end()) w = it->second;
207 }
208 for (const auto &kv : subst)
209 pointName(kv.first, kv.second);
210}
211
213{
214 GenericCircuit &gc = *this;
215 bool fired = false;
216 const std::size_t n = gc.getNbGates();
217 for (std::size_t i = 0; i < n; ++i) {
218 auto g = static_cast<gate_t>(i);
219 auto t = gc.getGateType(g);
220 if (t != gate_plus && t != gate_times) continue;
221
222 /* Which class of rule fired on this gate decides the side-band
223 * marker: the absorptive rules are sound in every absorptive
224 * semiring (1 + a = 1, hence a + a = a and a + ab = a), while
225 * times-idempotence and times-absorbs-plus genuinely need the
226 * Boolean interpretation (both fail in tropical). */
227 bool absorptive_rule_fired = false;
228 bool boolean_rule_fired = false;
229
230 /* Rule 1 : idempotence. a + a = a is absorptive
231 * (a + a*1 = a); a * a = a is Boolean-only (tropical: a + a = 2a).
232 * Drop repeated child wires preserving order of first
233 * occurrence. */
234 if (t == gate_plus || boolean_level) {
235 auto &wires = gc.getWires(g);
236 std::unordered_set<gate_t> seen;
237 std::vector<gate_t> deduped;
238 deduped.reserve(wires.size());
239 for (gate_t c : wires) {
240 if (seen.insert(c).second) deduped.push_back(c);
241 }
242 if (deduped.size() != wires.size()) {
243 wires = std::move(deduped);
244 if (t == gate_plus)
245 absorptive_rule_fired = true;
246 else
247 boolean_rule_fired = true;
248 }
249 }
250
251 /* Rule 2 : plus-with-one absorber (the defining absorptive
252 * identity 1 + a = 1). Collapse
253 * @c gate_plus(..., @c gate_one, ...) directly to @c gate_one,
254 * preserving @p g's UUID. */
255 if (t == gate_plus) {
256 bool has_one = false;
257 for (gate_t c : gc.getWires(g)) {
258 if (gc.getGateType(c) == gate_one) { has_one = true; break; }
259 }
260 if (has_one) {
261 gc.setGateType(g, gate_one);
262 gc.setWires(g, std::vector<gate_t>{});
263 infos.erase(g);
264 extra.erase(g);
265 absorptive_rule_fired = true;
266 }
267 }
268
269 /* Rule 3 : absorption.
270 * gate_plus (x, gate_times(x, y, ...), ...) -> gate_plus (x, ...)
271 * -- the defining absorptive identity a + ab = a;
272 * gate_times(x, gate_plus (x, y, ...), ...) -> gate_times(x, ...)
273 * -- the lattice dual, Boolean-only (tropical:
274 * x + min(x, y) != x in general).
275 * The absorbed times / plus child is dominated by its sibling
276 * @c x present in the parent's children set. Implemented as a
277 * single pass : build a set view of the parent's children, then
278 * drop every opposite-type child whose wires intersect that set.
279 * The set view captures the wires snapshot ; in case B2 already
280 * mutated @p g into @c gate_one above, @c t still holds the
281 * pre-mutation type so absorption skips correctly via the
282 * type-mismatch check at the top. The dominating literal @c x is
283 * often only exposed as a direct sibling after a single-wire
284 * collapse (a diagonal @c gate_times(x, x) deduped by B1 then
285 * rewritten to @c x by @c foldSemiringIdentities) : the joint
286 * fixpoint in @c foldBooleanIdentities re-runs this sweep after
287 * each collapse so the exposed literal is seen on the next pass. */
288 if (t == gate_plus || boolean_level) {
289 const gate_type opposite = (t == gate_plus) ? gate_times : gate_plus;
290 const auto &wires_now = gc.getWires(g);
291 if (wires_now.size() >= 2) {
292 std::unordered_set<gate_t> sibling_set(wires_now.begin(),
293 wires_now.end());
294 std::vector<gate_t> kept;
295 kept.reserve(wires_now.size());
296 bool dropped = false;
297 for (gate_t c : wires_now) {
298 if (gc.getGateType(c) == opposite) {
299 bool absorb = false;
300 for (gate_t w : gc.getWires(c)) {
301 if (w != c && sibling_set.count(w)) {
302 absorb = true;
303 break;
304 }
305 }
306 if (absorb) { dropped = true; continue; }
307 }
308 kept.push_back(c);
309 }
310 if (dropped) {
311 gc.setWires(g, std::move(kept));
312 if (t == gate_plus)
313 absorptive_rule_fired = true;
314 else
315 boolean_rule_fired = true;
316 }
317 }
318 }
319
320 if (absorptive_rule_fired)
322 if (boolean_rule_fired)
324 if (absorptive_rule_fired || boolean_rule_fired)
325 fired = true;
326 }
327 return fired;
328}
329
331{
332 /* Interleave the Boolean rule sweep with the semiring-safe collapse
333 * to a JOINT fixpoint. Running the Boolean rules to their own
334 * fixpoint and only THEN collapsing once would miss absorptions
335 * whose dominating literal is exposed by a collapse: a diagonal
336 * @c gate_times(x, x) is deduped to a single-wire @c gate_times by
337 * B1, but only @c foldSemiringIdentities rewrites that wrapper to
338 * @c x, so a later B3 pass would never see @c x as a sibling. Alternating until neither pass changes anything closes
339 * that gap and leaves a circuit on which no rule applies.
340 *
341 * Termination: every rule (idempotence, plus-with-one, absorption,
342 * identity-drop, single-wire / empty collapse, zero-absorber) strictly
343 * removes at least one wire or gate and none ever adds one, so the
344 * well-founded (gates, wires) measure decreases; the loop exits only
345 * when both passes report no change, i.e. no rule applies to any gate.
346 * Collapses propagate one DAG level per iteration, so the sweep count
347 * is O(circuit depth) and each sweep is linear in the circuit size. */
348 bool changed = true;
349 while (changed) {
350 changed = applyFoldRuleSweep(true);
351 changed |= foldSemiringIdentities();
352 }
353}
354
356{
357 /* Same joint fixpoint as foldBooleanIdentities, restricted to the
358 * rules sound in every absorptive semiring; see the header note. */
359 bool changed = true;
360 while (changed) {
361 changed = applyFoldRuleSweep(false);
362 changed |= foldSemiringIdentities();
363 }
364}
365
367{
368 const auto &w = getWires(sys);
369 if(w.size() % 2)
370 throw CircuitException("gate_fixsystem must have an even number of wires");
371 const std::size_t n = w.size() / 2;
372
373 std::unordered_map<gate_t, std::size_t> unknown;
374 for(std::size_t i = 0; i < n; ++i) {
375 if(getGateType(w[i]) != gate_fixvar)
376 throw CircuitException(
377 "The first half of a gate_fixsystem's wires must be its "
378 "gate_fixvar unknowns");
379 unknown.emplace(w[i], i);
380 }
381
382 /* Which gates depend on an unknown, as in solveFixSystem: an iterative
383 * post-order, another system's gate_fixpoint being a constant here. */
384 std::unordered_map<gate_t, bool> dep;
385 {
386 std::vector<gate_t> st;
387 for(std::size_t i = n; i < w.size(); ++i)
388 st.push_back(w[i]);
389 while(!st.empty()) {
390 const gate_t u = st.back();
391 if(dep.count(u)) { st.pop_back(); continue; }
392 const auto t = getGateType(u);
393 if(t == gate_fixvar) {
394 if(!unknown.count(u))
395 throw CircuitException(
396 "An unknown of another equation system occurs in this one");
397 dep.emplace(u, true);
398 st.pop_back();
399 continue;
400 }
401 if(t == gate_fixpoint) {
402 dep.emplace(u, false);
403 st.pop_back();
404 continue;
405 }
406 bool ready = true;
407 for(const auto &c : getWires(u))
408 if(!dep.count(c)) { st.push_back(c); ready = false; }
409 if(!ready) continue;
410 bool d = false;
411 for(const auto &c : getWires(u))
412 d = d || dep.at(c);
413 dep.emplace(u, d);
414 st.pop_back();
415 }
416 }
417
418 /* Linear form, kept symbolic: a disjunction of conjunctions for the
419 * constant part, and (unknown, conjunction) terms. Only the gates between
420 * an equation's root and its unknowns are visited, as in solveFixSystem. */
421 using Conj = std::vector<gate_t>;
422 struct Lin {
423 std::vector<Conj> c;
424 std::vector<std::pair<std::size_t, Conj> > terms;
425 };
426 std::unordered_map<gate_t, Lin> lin;
427 std::function<const Lin &(gate_t)> linear = [&](gate_t u) -> const Lin & {
428 auto it = lin.find(u);
429 if(it != lin.end())
430 return it->second;
431 Lin r;
432 const auto t = getGateType(u);
433 switch(t) {
434 case gate_fixvar:
435 r.terms.emplace_back(unknown.at(u), Conj{});
436 break;
437 case gate_plus:
438 for(const auto &c : getWires(u)) {
439 if(dep.at(c)) {
440 const Lin &l = linear(c);
441 r.c.insert(r.c.end(), l.c.begin(), l.c.end());
442 r.terms.insert(r.terms.end(), l.terms.begin(), l.terms.end());
443 } else
444 r.c.push_back(Conj{c});
445 }
446 break;
447 case gate_times: {
448 Conj k;
449 gate_t var = u;
450 for(const auto &c : getWires(u)) {
451 if(dep.at(c)) {
452 if(var != u)
453 throw CircuitRefusal(
454 PROVSQL_GAP, "recursion-nonlinear",
455 "This recursion's equations are not linear: a product "
456 "has two factors depending on the recursive relation");
457 var = c;
458 } else
459 k.push_back(c);
460 }
461 const Lin &l = linear(var);
462 for(const auto &conj : l.c) {
463 Conj e = conj;
464 e.insert(e.end(), k.begin(), k.end());
465 r.c.push_back(std::move(e));
466 }
467 for(const auto &[j, conj] : l.terms) {
468 Conj e = conj;
469 e.insert(e.end(), k.begin(), k.end());
470 r.terms.emplace_back(j, std::move(e));
471 }
472 break;
473 }
474 case gate_assumed:
475 case gate_project:
476 case gate_eq:
477 case gate_annotation:
478 r = linear(getWires(u)[0]);
479 break;
480 default:
481 throw CircuitRefusal(
482 PROVSQL_GAP, "recursion-nonlinear",
483 std::string("This recursion's equations are not linear "
484 "semiring expressions in the recursive relation "
485 "(gate of type ") + gate_type_name[t] +
486 " over it)");
487 }
488 return lin.emplace(u, std::move(r)).first->second;
489 };
490
491 FixSystemLinear out;
492 out.n = n;
493 out.b.resize(n);
494 out.in.resize(n);
495 out.out.resize(n);
496 for(std::size_t i = 0; i < n; ++i) {
497 const gate_t f = w[n + i];
498 if(dep.at(f)) {
499 const Lin &l = linear(f);
500 out.b[i] = l.c;
501 for(const auto &[j, conj] : l.terms) {
502 out.in[i].emplace_back(j, conj);
503 out.out[j].emplace_back(i, conj);
504 }
505 } else
506 out.b[i].push_back(Conj{f});
507 }
508 return out;
509}
gate_t
Strongly-typed gate identifier.
Definition Circuit.h:53
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::string uuid
Definition Circuit.h:175
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
virtual gate_t setGate(const uuid &u, gateType type)
Create or update the gate associated with UUID u.
Definition Circuit.hpp:187
void setGateType(gate_t g, gateType t)
Update the type of an existing gate.
Definition Circuit.h:223
void pointName(gate_t g, gate_t target)
Definition Circuit.hpp:111
std::vector< std::vector< gate_t > > wires
Definition Circuit.h:216
std::vector< gate_t >::size_type getNbGates() const
Return the total number of gates in the circuit.
Definition Circuit.h:252
virtual gate_t addGate()
Allocate a new gate with a default-initialised type.
Definition Circuit.hpp:168
void setWires(gate_t g, std::vector< gate_t > w)
Replace the wires of g with w.
std::map< gate_t, std::pair< unsigned, unsigned > > infos
Per-gate (info1, info2) annotations.
void markAbsorptiveAssumed(gate_t g)
Mark gate g as absorptive-assumed (in-memory side band).
bool foldSemiringIdentities()
Drop semiring identity wires and collapse single-wire gate_times / gate_plus to their lone non-identi...
void foldAbsorptiveIdentities()
Absorptive-rules-only variant of foldBooleanIdentities(): the joint fixpoint of the absorptive fold r...
std::map< gate_t, std::string > extra
Per-gate string extras.
gate_t addGate() override
Allocate a new gate with a default-initialised type.
std::set< gate_t > inputs
Set of input (leaf) gate IDs.
std::set< gate_t > absorptive_assumed_gates
Side-band absorptive-assumption marker set by the absorptive fold rules (plus-idempotence,...
std::vector< double > prob
Per-gate probability values.
FixSystemLinear linearizeFixSystem(gate_t sys) const
The equations of the gate_fixsystem sys, as linear forms over the gates that do not depend on its unk...
gate_t setGate(gate_type type) override
Allocate a new gate with type type and no UUID.
void markBooleanAssumed(gate_t g)
Mark gate g as Boolean-assumed (in-memory side band).
std::set< gate_t > boolean_assumed_gates
Side-band Boolean-assumption marker set by the Boolean-only fold rules ; an evaluator visiting a gate...
void redirectGates(std::unordered_map< gate_t, gate_t > subst)
Make every reference to a gate of subst point to its target instead.
bool applyFoldRuleSweep(bool boolean_level)
One pass of the fold rules over every gate_plus / gate_times.
void foldBooleanIdentities()
Apply the Boolean-only AND the absorptive simplification rules to gate_plus and gate_times,...
#define PROVSQL_GAP
const char * gate_type_name[]
Names of gate types.
@ gate_annotation
Transparent single-child wrapper carrying a query-level annotation in extra (inversion-free certifica...
@ gate_fixpoint
Component of the least solution of an equation system: one wire to a gate_fixsystem,...
@ gate_fixvar
Unknown of an equation system (see gate_fixsystem): a leaf standing for the solution of one equation,...
@ gate_assumed
Structural marker over a single child whose sub-circuit was computed under a Boolean-provenance assum...
In-memory provenance circuit with semiring-generic evaluation.
std::vector< std::vector< std::vector< gate_t > > > b
Constant part of each equation.
std::size_t n
Number of unknowns.
std::vector< std::vector< std::pair< std::size_t, std::vector< gate_t > > > > in
Terms of each equation.
std::vector< std::vector< std::pair< std::size_t, std::vector< gate_t > > > > out
Terms, by unknown read.