ProvSQL C/C++ API
Adding support for provenance and uncertainty management to PostgreSQL databases
Loading...
Searching...
No Matches
GenericCircuit.h
Go to the documentation of this file.
1/**
2 * @file GenericCircuit.h
3 * @brief Semiring-agnostic in-memory provenance circuit.
4 *
5 * @c GenericCircuit is an in-memory directed acyclic graph whose gate
6 * types use the PostgreSQL @c gate_type enumeration. It is built from
7 * the persistent mmap representation (via @c createGenericCircuit() /
8 * @c getGenericCircuit()) and then evaluated over an arbitrary semiring
9 * using the @c evaluate() template method.
10 *
11 * Beyond the gate/wire data inherited from @c Circuit<gate_type>,
12 * @c GenericCircuit tracks:
13 * - Per-gate integer annotation pairs (@c info1, @c info2) used by
14 * aggregation and semimodule gates.
15 * - Per-gate variable-length string extras (e.g. label strings for
16 * @c gate_value gates).
17 * - A probability vector for probabilistic evaluation.
18 * - The set of input gate IDs (for semiring evaluation traversal).
19 *
20 * The circuit is Boost-serialisable, which is used when sending it as
21 * a blob to an external knowledge-compiler process.
22 */
23#ifndef GENERIC_CIRCUIT_H
24#define GENERIC_CIRCUIT_H
25
26#include <map>
27#include <memory>
28#include <type_traits>
29
30#include <boost/archive/binary_oarchive.hpp>
31#include <boost/serialization/unordered_map.hpp>
32#include <boost/serialization/map.hpp>
33#include <boost/serialization/set.hpp>
34#include <boost/serialization/vector.hpp>
35
36#include "Circuit.hpp"
37#include "semiring/Semiring.h"
38
39extern "C" {
40#include "provsql_utils.h"
41}
42
43/**
44 * @brief In-memory provenance circuit with semiring-generic evaluation.
45 *
46 * Gate types are the PostgreSQL @c gate_type values. The circuit is
47 * constructed from the persistent mmap store and then evaluated in-memory.
48 */
49/**
50 * @brief The equations of a @c gate_fixsystem as linear Boolean forms.
51 *
52 * Equation @c i reads @f$x_i = b_i \vee \bigvee_j (a_{ij} \wedge x_j)@f$,
53 * where @f$b_i@f$ and every coefficient @f$a_{ij}@f$ are given by gates
54 * of the circuit that do not depend on the unknowns: @c b[i] lists the
55 * conjunctions whose disjunction is @f$b_i@f$, and @c in[i] the pairs
56 * @c (j, conjunction), an empty conjunction being true. @c out holds the
57 * same terms indexed by @c j. Built by @c linearizeFixSystem, for the
58 * evaluators that solve the system in one world at a time (the Monte Carlo
59 * sampler) or estimate the size of its Boolean expansion.
60 */
62 std::size_t n = 0; ///< Number of unknowns
63 std::vector<std::vector<std::vector<gate_t> > > b; ///< Constant part of each equation
64 std::vector<std::vector<std::pair<std::size_t, std::vector<gate_t> > > > in; ///< Terms of each equation
65 std::vector<std::vector<std::pair<std::size_t, std::vector<gate_t> > > > out; ///< Terms, by unknown read
66};
67
68class GenericCircuit : public Circuit<gate_type>
69{
70private:
71std::map<gate_t, std::pair<unsigned,unsigned> > infos; ///< Per-gate (info1, info2) annotations
72std::map<gate_t, std::string> extra; ///< Per-gate string extras
73std::set<gate_t> inputs; ///< Set of input (leaf) gate IDs
74std::vector<double> prob; ///< Per-gate probability values
75std::set<gate_t> boolean_assumed_gates; ///< Side-band Boolean-assumption marker set by the Boolean-only fold rules ; an evaluator visiting a gate in this set refuses to proceed under a semiring that does not admit a homomorphism from Boolean functions. In-memory only ; never persisted to mmap. Distinct from the @c gate_assumed enum (used by the safe-query rewriter to encode the same restriction at the persistent layer).
76std::set<gate_t> absorptive_assumed_gates; ///< Side-band absorptive-assumption marker set by the absorptive fold rules (plus-idempotence, plus-with-one absorber, plus-absorbs-times -- sound in every absorptive semiring) ; an evaluator visiting a gate in this set refuses unless the semiring is absorptive or tolerates the (stronger) Boolean rewrite. In-memory only.
77
78public:
79/**
80 * @brief Equation systems solved by @c evaluate, with their solutions.
81 *
82 * Each entry pairs a @c gate_fixsystem with a @c std::vector of the
83 * evaluated semiring's values, type-erased: the caller that instantiated
84 * @c evaluate knows the type and reads it back, to cache the solution of
85 * every component at once (see @c provenance_evaluate_compiled).
86 * In-memory only.
87 */
88mutable std::vector<std::pair<gate_t, std::shared_ptr<void> > > solved_systems;
89
90public:
91/**
92 * @brief Return a placeholder debug string (not intended for display).
93 * @param g Gate identifier (unused).
94 * @return Fixed placeholder string @c "<GenericCircuit>".
95 */
96virtual std::string toString(gate_t g) const override {
97 return "<GenericCircuit>";
98}
99
100/**
101 * @brief Set the integer annotation pair for gate @p g.
102 * @param g Gate identifier.
103 * @param info1 First annotation integer.
104 * @param info2 Second annotation integer.
105 */
106void setInfos(gate_t g, unsigned info1, unsigned info2)
107{
108 infos[g]=std::make_pair(info1, info2);
109}
110
111/**
112 * @brief Return the integer annotation pair for gate @p g.
113 * @param g Gate identifier.
114 * @return @c {info1, info2}, or @c {-1,-1} if not set.
115 */
116std::pair<unsigned,unsigned> getInfos(gate_t g) const
117{
118 auto it = infos.find(g);
119 if(it==infos.end())
120 return std::make_pair(-1, -1);
121 return it->second;
122}
123
124/**
125 * @brief Attach a string extra to gate @p g.
126 * @param g Gate identifier.
127 * @param ex String to store.
128 */
129void setExtra(gate_t g, const std::string &ex)
130{
131 extra[g]=ex;
132}
133
134/**
135 * @brief Return the string extra for gate @p g.
136 * @param g Gate identifier.
137 * @return The stored string, or empty if not set.
138 */
139std::string getExtra(gate_t g) const
140{
141 auto it = extra.find(g);
142 if(it==extra.end())
143 return "";
144 else
145 return it->second;
146}
147
148/** @copydoc Circuit::addGate() */
149gate_t addGate() override;
150/** @copydoc Circuit::setGate(gateType) */
151gate_t setGate(gate_type type) override;
152/** @copydoc Circuit::setGate(const uuid&, gateType) */
153gate_t setGate(const uuid &u, gate_type type) override;
154/**
155 * @brief Set the type of the existing gate @p g, as @c setGate does for a
156 * UUID, without looking the UUID up.
157 */
158void setGate(gate_t g, gate_type type) {
159 setGateType(g, type);
160 if(type == gate_input || type == gate_update)
161 inputs.insert(g);
162}
163
164/**
165 * @brief Return the set of input (leaf) gates.
166 * @return Const reference to the set of input gate identifiers.
167 */
168const std::set<gate_t> &getInputs() const {
169 return inputs;
170}
171
172/**
173 * @brief The UUIDs a provenance mapping can label: those of the input
174 * gates, and of the @c mulinput gates, each value of a multivalued
175 * input (from @c repair_key) being a row of its own.
176 */
177std::vector<std::string> getMappableUUIDs() const {
178 std::vector<std::string> r;
179 for(auto x : inputs)
180 r.push_back(getUUID(x));
181 for(std::size_t i = 0; i < getNbGates(); ++i)
182 if(getGateType(static_cast<gate_t>(i)) == gate_mulinput)
183 r.push_back(getUUID(static_cast<gate_t>(i)));
184 return r;
185}
186
187/**
188 * @brief Set the probability for gate @p g.
189 * @param g Gate identifier.
190 * @param p Probability in [0, 1].
191 */
192void setProb(gate_t g, double p) {
193 prob[static_cast<std::underlying_type<gate_t>::type>(g)]=p;
194}
195
196/**
197 * @brief Return the probability for gate @p g.
198 * @param g Gate identifier.
199 * @return The stored probability.
200 */
201double getProb(gate_t g) const {
202 return prob[static_cast<std::underlying_type<gate_t>::type>(g)];
203}
204
205/**
206 * @brief Replace a @c gate_cmp by a constant Boolean leaf
207 * (@c gate_one for @p p == 1, @c gate_zero for @p p == 0)
208 * or by a Bernoulli @c gate_input for any other @p p.
209 *
210 * Used by peephole pruning passes when a comparator's probability is
211 * provably 0, 1, or a closed-form value. Distinguishing the
212 * 0 / 1 case from the fractional case matters because non-probabilistic
213 * semirings (e.g. @c sr_formula, @c sr_counting) have well-defined
214 * @c zero() / @c one() values but no notion of "Bernoulli with
215 * probability @c p" &ndash; an unknown @c gate_input would default
216 * to @c semiring.one() in every semiring (per
217 * @c GenericCircuit::evaluate), which is wrong for an
218 * always-false comparator. Using @c gate_zero / @c gate_one
219 * directly is universally correct: every semiring knows its
220 * identities.
221 *
222 * Fractional probabilities are still encoded as @c gate_input + a
223 * probability so probability evaluators (MC, independent, treedec,
224 * d-DNNF, d4) can consume them, but only those evaluators handle
225 * non-trivial probabilities meaningfully. Such resolutions should
226 * therefore be confined to passes invoked from a probability
227 * context (not the universal @c getGenericCircuit-time pass).
228 *
229 * Operates on the in-memory circuit only; the persistent mmap store
230 * is never mutated. Children that become orphaned are not reaped
231 * here.
232 */
233void resolveCmpToBernoulli(gate_t g, double p) {
234 if (p == 0.0) {
236 } else if (p == 1.0) {
238 } else {
240 setProb(g, p);
241 inputs.insert(g);
242 }
243 getWires(g).clear();
244 infos.erase(g);
245 extra.erase(g);
246}
247
248/**
249 * @brief Replace a @c gate_cmp by a @c gate_plus over the given
250 * per-row K-gates (the OR of the agg's row-presence
251 * indicators).
252 *
253 * Used by the probability-side always-true HAVING rewriter
254 * (@c runHavingAlwaysTrueRewriter): when a HAVING predicate is
255 * provably true on the agg's value-interval, the cmp value equals
256 * "the group is non-empty" -- the OR over the agg's K-gates -- not
257 * @c gate_one, which would over-credit the empty world (see
258 * @c decideAggVsConstCmp's doc comment).
259 *
260 * Sound for absorptive semirings where @c gate_plus is idempotent
261 * OR (probability, Boolean, formula, why, which, max-min, max-max);
262 * the call site lives in the probability-evaluate pre-pass for
263 * that reason, mirroring @c resolveCmpToBernoulli with a fractional
264 * probability.
265 *
266 * Same wire/info/extra clearing as @c resolveCmpToBernoulli. No
267 * special-casing for @c ks of size 1: a single-child @c gate_plus is
268 * structurally redundant but semantically equivalent to that child
269 * in every semiring.
270 */
271void resolveCmpToPlusOfKGates(gate_t g, const std::vector<gate_t> &ks) {
273 auto &w = getWires(g);
274 w.clear();
275 w.reserve(ks.size());
276 for (gate_t k : ks) w.push_back(k);
277 infos.erase(g);
278 extra.erase(g);
279}
280
281/**
282 * @brief Replace an arbitrary gate (typically @c gate_times) by
283 * @c gate_zero.
284 *
285 * Used by RangeCheck's joint-conjunction pass when an AND of cmps
286 * over a shared RV constrains its support to an empty interval:
287 * since @c gate_zero is the multiplicative absorber in every
288 * semiring, replacing a @c gate_times with it is universally sound,
289 * and orphans the conjuncts (their effects are now unreachable
290 * from the root, regardless of what each individual cmp would
291 * resolve to).
292 *
293 * The wires, infos and extra fields are cleared so the gate is a
294 * proper leaf. Operates on the in-memory circuit only.
295 */
298 getWires(g).clear();
299 infos.erase(g);
300 extra.erase(g);
301}
302
303/**
304 * @brief Rewrite a gate as @c gate_one, the event that holds in every world.
305 *
306 * Used by @c runConstantCmpDecider for a comparison between two constants
307 * that holds. Same clearing as @c resolveGateToZero.
308 */
311 getWires(g).clear();
312 infos.erase(g);
313 extra.erase(g);
314}
315
316/**
317 * @brief Rewrite an arbitrary gate as a @c gate_value carrying the
318 * textual extra @p s.
319 *
320 * Used by the @c HybridEvaluator simplifier when a @c gate_arith
321 * subtree constant-folds to a scalar. Same wire/info/extra clearing
322 * as @c resolveCmpToBernoulli &ndash; the old children become
323 * orphans relative to @p g. @p s is interpreted by the consumer
324 * via @c parseDoubleStrict (or analogous routines), so it must be
325 * a canonical textual representation that round-trips through
326 * @c std::stod. Operates on the in-memory circuit only.
327 */
328void resolveToValue(gate_t g, const std::string &s) {
330 getWires(g).clear();
331 infos.erase(g);
332 extra[g] = s;
333}
334
335/**
336 * @brief Rewrite an arbitrary gate as a @c gate_rv carrying the
337 * distribution-spec extra @p s.
338 *
339 * Used by the @c HybridEvaluator simplifier when a linear
340 * combination of independent normals (or i.i.d. exponentials with
341 * the same rate) collapses to a single closed-form distribution.
342 * @p s must be a textual encoding parseable by
343 * @c parse_distribution_spec. Same wire/info clearing as
344 * @c resolveCmpToBernoulli. Operates on the in-memory circuit only.
345 */
346void resolveToRv(gate_t g, const std::string &s) {
348 getWires(g).clear();
349 infos.erase(g);
350 extra[g] = s;
351}
352
353/**
354 * @brief Replace a @c gate_conditioned @p g by a transparent passthrough to
355 * its @p target child (a single-child @c gate_arith @c PLUS, i.e. the
356 * sum of one operand = the operand itself).
357 *
358 * Used by the conditional-moment evaluator to lift conditioning out of a
359 * scalar arithmetic expression: @c "f(X|A, Y|B)" becomes @c "f(X, Y)" with the
360 * evidence @c A, @c B collected separately and conjoined into the root
361 * conditioning event. The passthrough REFERENCES @p target (it does not copy
362 * it), so a shared @c gate_rv keeps a single sampled draw. Operates on the
363 * in-memory circuit only.
364 */
367 auto &w = getWires(g);
368 w.clear();
369 w.push_back(target);
371 extra.erase(g);
372}
373
374/**
375 * @brief Make every reference to a gate of @p subst point to its target
376 * instead.
377 *
378 * Rewires each wire whose child is a key of @p subst to the
379 * corresponding target (followed transitively, so a target that is
380 * itself redirected leads to the end of the chain), and moves the UUID
381 * of each redirected gate to its target, so that @c getGate on that
382 * UUID -- a root resolved after the rewrite -- also lands on the target.
383 * The redirected gates are left in place, orphaned. Unlike a content
384 * copy, the target keeps its single identity: a shared @c gate_rv still
385 * gets one draw per Monte Carlo iteration, a shared input still counts
386 * once. Operates on the in-memory circuit only.
387 *
388 * @param subst Map from each redirected gate to its target.
389 */
390void redirectGates(std::unordered_map<gate_t, gate_t> subst);
391
392/**
393 * @brief Drop semiring identity wires and collapse single-wire
394 * @c gate_times / @c gate_plus to their lone non-identity
395 * child; collapse a @c gate_times containing a @c gate_zero
396 * wire to that absorber.
397 *
398 * Universal rewrite: the multiplicative identity (@c gate_one), the
399 * additive identity (@c gate_zero), and the multiplicative absorber
400 * (@c gate_zero) hold across every provsql semiring, so a single
401 * pass after @c RangeCheck is sound for every downstream consumer
402 * (probability_evaluate, to_provxml, view_circuit, Studio's
403 * simplified subgraph). Does NOT apply the additive absorber
404 * rewrite (@c plus-with-one): @c gate_one only absorbs in
405 * idempotent semirings (Boolean, MinMax), so applying it
406 * unconditionally would silently change the semantics for
407 * @c Counting / @c Formula / etc.
408 *
409 * A collapsed gate is not mutated to carry its target's content;
410 * instead every parent wire is rewired straight to the target and the
411 * UUID-to-@c gate_t map is re-pointed so a gate resolved by UUID
412 * (notably the caller-supplied root) follows the collapse. This keeps
413 * a shared leaf a single gate: copying a shared @c gate_input's
414 * content into the collapsed gate under a fresh UUID would mint an
415 * independent duplicate of that Bernoulli variable and over-count the
416 * probability of any non-read-once circuit.
417 *
418 * Operates on the in-memory circuit only; the persistent mmap store
419 * is never touched. Gated alongside @c RangeCheck by
420 * @c provsql.simplify_on_load.
421 *
422 * @return @c true if any phase mutated the circuit (so callers, notably
423 * @c foldBooleanIdentities, can drive a joint fixpoint).
424 */
426
427/**
428 * @brief Apply the Boolean-only AND the absorptive simplification rules
429 * to @c gate_plus and @c gate_times, to a joint fixpoint with
430 * @c foldSemiringIdentities.
431 *
432 * The rule set splits by the semiring class that justifies each rule:
433 *
434 * - @b Absorptive @b rules (sound in every absorptive semiring,
435 * i.e. whenever @f$1 \oplus a = 1@f$; gates marked
436 * absorptive-assumed):
437 * plus-idempotence @c gate_plus(a, a, b) → @c gate_plus(a, b)
438 * (@f$a \oplus a = a \oplus a \cdot 1 = a@f$);
439 * plus-with-one absorber @c gate_plus(…, @c gate_one, …) →
440 * @c gate_one; plus-absorbs-times
441 * @c gate_plus(x, gate_times(x, y, …), …) → @c gate_plus(x, …)
442 * (@f$a \oplus a b = a@f$, the defining identity).
443 * - @b Boolean-only @b rules (gates marked Boolean-assumed):
444 * times-idempotence @c gate_times(a, a, b) → @c gate_times(a, b)
445 * (fails in tropical: @f$a + a = 2a@f$); times-absorbs-plus
446 * @c gate_times(x, gate_plus(x, y, …), …) → @c gate_times(x, …)
447 * (the lattice dual, also unsound in tropical).
448 *
449 * Operates on the in-memory @c GenericCircuit only ; the persistent
450 * mmap store is never mutated, and the gate's UUID-to-@c gate_t
451 * mapping survives so callers indexing by the original UUID still
452 * find it. Interleaves the rule sweep (@c applyFoldRuleSweep) with
453 * @c foldSemiringIdentities to a JOINT fixpoint, so an absorption
454 * whose dominating literal is only exposed by a single-wire collapse
455 * still fires; the result is a circuit on which no enabled rule
456 * applies.
457 */
459
460/**
461 * @brief Absorptive-rules-only variant of @c foldBooleanIdentities():
462 * the joint fixpoint of the absorptive fold rules with
463 * @c foldSemiringIdentities, leaving the Boolean-only rules
464 * (times-idempotence, times-absorbs-plus) unapplied. Used at
465 * circuit-load time under the @c 'absorptive' provenance class.
466 */
468
469/**
470 * @brief One pass of the fold rules over every @c gate_plus /
471 * @c gate_times.
472 *
473 * Helper for the joint-fixpoint loops : applies each enabled rule in
474 * place, marking touched gates absorptive- or Boolean-assumed
475 * according to which rule fired, and reports whether any rule fired so
476 * the caller knows whether to iterate. Not a fixpoint on its own (it
477 * does a single sweep).
478 *
479 * @param boolean_level Also apply the Boolean-only rules.
480 * @return @c true if any rule fired during the sweep.
481 */
482bool applyFoldRuleSweep(bool boolean_level);
483
484/**
485 * @brief Mark gate @p g as Boolean-assumed (in-memory side band).
486 * Visited by every @c evaluate<S> traversal : if @p g is in
487 * the set, the visit checks @c S::compatibleWithBooleanRewrite
488 * and throws a @c CircuitException otherwise.
489 */
491
492/** @brief Report whether @p g carries the Boolean-assumption flag. */
494 return boolean_assumed_gates.count(g) > 0;
495}
496
497/**
498 * @brief Mark gate @p g as absorptive-assumed (in-memory side band).
499 * Visited by every @c evaluate<S> traversal : if @p g is in
500 * the set, the visit requires @c S::absorptive() or
501 * @c S::compatibleWithBooleanRewrite() (a semiring tolerating
502 * the stronger Boolean rewrite tolerates the weaker absorptive
503 * one) and throws a @c CircuitException otherwise.
504 */
506
507/** @brief Report whether @p g carries the absorptive-assumption flag. */
509 return absorptive_assumed_gates.count(g) > 0;
510}
511
512/**
513 * @brief Replace the wires of @p g with @p w.
514 *
515 * Used by the @c HybridEvaluator simplifier's identity-element drop
516 * to remove constant-zero wires from a @c PLUS gate (or constant-one
517 * wires from a @c TIMES gate) without changing the gate's type.
518 * Dropped children become orphans relative to @p g.
519 */
520void setWires(gate_t g, std::vector<gate_t> w) {
521 getWires(g) = std::move(w);
522}
523
524/**
525 * @brief Rewrite an arbitrary gate as a @c gate_plus over @p w.
526 *
527 * Used by the @c HybridEvaluator multi-cmp island decomposer when
528 * a comparator from a shared-island group is rewritten as the OR
529 * of the joint-table @c gate_mulinput leaves where the comparator's
530 * bit is set. Clears infos and extra and installs the new wires.
531 */
532void resolveToPlus(gate_t g, std::vector<gate_t> w) {
534 getWires(g) = std::move(w);
535 infos.erase(g);
536 extra.erase(g);
537}
538
539/**
540 * @brief Rewrite a gate as the @c gate_case over @p w (guards and values,
541 * then the default).
542 *
543 * Used by @c CaseCmpExpander to hoist a guarded selection out of the
544 * arithmetic a comparison reads. Clears infos and extra (an arithmetic
545 * gate's recorded value no longer applies) and installs the new wires.
546 */
547void resolveToCase(gate_t g, std::vector<gate_t> w) {
549 getWires(g) = std::move(w);
550 infos.erase(g);
551 extra.erase(g);
552}
553
554/**
555 * @brief Allocate a fresh @c gate_input gate carrying probability
556 * @p p, with a unique synthetic UUID so subsequent
557 * @c BooleanCircuit conversion does not collide multiple
558 * no-UUID inputs onto the same gate.
559 *
560 * The synthetic UUID is derived from the freshly-assigned gate id;
561 * it is not a real v4 UUID (does not match the @c xxxxxxxx-...
562 * format) and exists only for in-memory uniqueness during the
563 * probability_evaluate pipeline. The gate is added to @c inputs
564 * so the conversion's first loop maps it into @c BooleanCircuit's
565 * @c gc_to_bc.
566 *
567 * @param p Probability for the new input.
568 * @return The id of the new gate.
569 */
571 gate_t id = addGate();
573 setProb(id, p);
574 std::string u = "dec-in-" + std::to_string(static_cast<size_t>(id));
575 bindName(id, u);
576 inputs.insert(id);
577 return id;
578}
579
580/**
581 * @brief Allocate a fresh @c gate_mulinput gate with key @p key,
582 * probability @p p, and value index @p value_index.
583 *
584 * Used by the joint-table decomposer to materialise one Bernoulli
585 * outcome of a 2^k-way categorical distribution over a shared
586 * continuous island. All mulinputs in one joint table share the
587 * same @p key (the block anchor returned by @c addAnonymousInputGate);
588 * @p value_index is stored in @c info1 so
589 * @c BooleanCircuit::independentEvaluation can group / dedup
590 * MULIN references at OR sites. A unique synthetic UUID is
591 * minted for the same reason as @c addAnonymousInputGate.
592 */
594 unsigned value_index) {
595 gate_t id = addGate();
597 setProb(id, p);
598 setInfos(id, value_index, 0);
599 getWires(id).push_back(key);
600 std::string u = "dec-mul-" + std::to_string(static_cast<size_t>(id));
601 bindName(id, u);
602 return id;
603}
604
605/**
606 * @brief Allocate a fresh @c gate_arith gate with operator tag @p op
607 * and the given @p wires.
608 *
609 * Used by the @c HybridEvaluator simplifier's mixture-lift rule when
610 * pushing a @c PLUS / @c TIMES inside a mixture's two scalar branches:
611 * each branch needs a fresh @c gate_arith child carrying the lifted
612 * operation, and those children must round-trip through downstream
613 * @c getUUID / @c getGate lookups (Studio's simplified subgraph,
614 * @c to_provxml). A unique synthetic UUID is minted for the same
615 * reason as @c addAnonymousInputGate.
616 */
618 std::vector<gate_t> wires_) {
619 gate_t id = addGate();
621 setInfos(id, static_cast<int>(op), 0);
622 getWires(id) = std::move(wires_);
623 std::string u = "dec-arith-" + std::to_string(static_cast<size_t>(id));
624 bindName(id, u);
625 return id;
626}
627
628/**
629 * @brief Allocate a fresh gate of type @p type over @p wires_.
630 *
631 * The general form of the @c addAnonymous* helpers, for a pass that
632 * builds a small expression of ordinary gates rather than one leaf:
633 * @c CaseCmpExpander builds the @c gate_plus / @c gate_times /
634 * @c gate_monus / @c gate_cmp of a guarded selection's expansion this
635 * way. A unique synthetic UUID is minted for the same reason as
636 * @c addAnonymousInputGate; the caller sets @c infos / @c extra itself
637 * where the gate type carries them.
638 */
639gate_t addAnonymousGate(gate_type type, std::vector<gate_t> wires_) {
640 gate_t id = addGate();
641 setGateType(id, type);
642 getWires(id) = std::move(wires_);
643 std::string u = "dec-gate-" + std::to_string(static_cast<size_t>(id));
644 bindName(id, u);
645 return id;
646}
647
648/**
649 * @brief Allocate a fresh @c gate_value gate carrying the textual
650 * scalar @p text.
651 *
652 * Used by the @c HybridEvaluator simplifier's PLUS coefficient
653 * aggregation rule: when same-RV terms in a @c PLUS gate are merged
654 * into <tt>arith(TIMES, value:a_total, Z)</tt> per RV, each
655 * coefficient @c a_total needs a fresh @c gate_value to feed the
656 * synthetic @c TIMES. @p text must be a canonical text form that
657 * round-trips through @c parseDoubleStrict (the simplifier already
658 * formats with precision 17). A unique synthetic UUID is minted for
659 * the same reason as @c addAnonymousInputGate.
660 */
661gate_t addAnonymousValueGate(const std::string &text) {
662 gate_t id = addGate();
664 setExtra(id, text);
665 std::string u = "dec-value-" + std::to_string(static_cast<size_t>(id));
666 bindName(id, u);
667 return id;
668}
669
670/**
671 * @brief Rewrite @p g in place as a @c gate_mixture over the wires
672 * @c [p_token, x_token, y_token].
673 *
674 * Used by the @c HybridEvaluator simplifier's mixture-lift rule when
675 * a @c gate_arith containing a single @c gate_mixture child is pushed
676 * inside the mixture's branches: the outer arith gate is rewritten in
677 * place as the lifted mixture, preserving its UUID and the
678 * non-mixture-aware code paths that already hold references to it.
679 * The @p p_token is reused verbatim so Bernoulli identity is
680 * preserved across the rewrite; the @p x_token and @p y_token are
681 * the freshly-minted arith children built via
682 * @c addAnonymousArithGate.
683 */
685 gate_t x_token, gate_t y_token) {
687 std::vector<gate_t> w;
688 w.reserve(3);
689 w.push_back(p_token);
690 w.push_back(x_token);
691 w.push_back(y_token);
692 getWires(g) = std::move(w);
693 infos.erase(g);
694 extra.erase(g);
695}
696
697/**
698 * @brief Allocate a fresh @c gate_mulinput labelled with a numeric
699 * outcome value carried in @c extra.
700 *
701 * Variant of @c addAnonymousMulinputGate used by the categorical
702 * mixture lowering: the mulinput's @c info1 still holds the ordinal
703 * @p value_index for @c independentEvaluation's dedup, and the
704 * outcome's numeric label is stored in @c extra so the evaluator-side
705 * categorical-mixture handlers can read it as a @c float8.
706 */
708 unsigned value_index,
709 const std::string &value_text) {
710 gate_t id = addAnonymousMulinputGate(key, p, value_index);
711 setExtra(id, value_text);
712 return id;
713}
714
715/**
716 * @brief Rewrite @p g in place as a categorical-form @c gate_mixture
717 * over @p wires (@c [key, mul_1, ..., mul_n]).
718 *
719 * Used by the explicit @c provsql.categorical constructor (built at
720 * SQL-call time, not by the simplifier): the @c gate_mixture type is
721 * reused with @c N > 3 wires, where @c wires[0] is a fresh
722 * @c gate_input "key" anchor (its own probability is irrelevant: the
723 * categorical mass is on the mulinputs) and @c wires[1..n] are
724 * @c gate_mulinput leaves sharing that key. Every @c gate_mixture
725 * handler downstream branches on <tt>wires.size() == 3</tt> for the
726 * classic <tt>[p_token, x_token, y_token]</tt> shape vs the
727 * categorical shape; the latter is what unlocks closed-form CDF /
728 * cmp evaluation via @c AnalyticEvaluator.
729 */
730void resolveToCategoricalMixture(gate_t g, std::vector<gate_t> wires_) {
732 getWires(g) = std::move(wires_);
733 infos.erase(g);
734 extra.erase(g);
735}
736
737/**
738 * @brief Test whether @p g is a categorical-form @c gate_mixture
739 * (the explicit @c provsql.categorical output).
740 *
741 * Returns true iff @p g is a @c gate_mixture whose wires are
742 * @c [key, mul_1, ..., mul_n] with @p n &ge; 1: @c wires[0] a
743 * @c gate_input key anchor, and every subsequent wire a
744 * @c gate_mulinput. The classic mixture shape
745 * @c [p_token, x_token, y_token] returns false (one or both of
746 * @c wires[1..2] are not @c gate_mulinput).
747 */
749{
750 if (getGateType(g) != gate_mixture) return false;
751 const auto &w = getWires(g);
752 if (w.size() < 2) return false;
753 if (getGateType(w[0]) != gate_input) return false;
754 for (std::size_t i = 1; i < w.size(); ++i) {
755 if (getGateType(w[i]) != gate_mulinput) return false;
756 }
757 return true;
758}
759
760/**
761 * @brief Boost serialisation support.
762 * @param ar Boost archive (input or output).
763 * @param version Archive version (unused).
764 */
765template<class Archive>
766void serialize (Archive & ar, const unsigned int version)
767{
768 ar & uuid2id;
769 ar & id2uuid;
770 ar & name_kind;
771 ar & name2id;
772 ar & id2name;
773 ar & gates;
774 ar & wires;
775 ar & infos;
776 ar & extra;
777 ar & inputs;
778 ar & prob;
779}
780
783
784/**
785 * @brief Evaluate the sub-circuit rooted at gate @p g over semiring @p semiring.
786 *
787 * Performs a post-order traversal from @p g, mapping each input gate to
788 * its semiring value via @p provenance_mapping, and combining the results
789 * using the semiring operations.
790 *
791 * Every computed gate is memoised into @p provenance_mapping (a gate's
792 * semiring value is a pure function of the gate, so reuse is always
793 * sound): shared sub-DAGs are evaluated once, and gate-creating
794 * semirings (BoolExpr, formula) preserve the sharing structurally.
795 * After the call the mapping therefore covers every visited gate, not
796 * only the pre-seeded inputs.
797 *
798 * @tparam S A concrete @c semiring::Semiring subclass.
799 * @param g Root gate of the sub-circuit to evaluate.
800 * @param provenance_mapping Map from input gate IDs to semiring values;
801 * also serves as the memoisation table.
802 * @param semiring Semiring instance providing @c zero(), @c one(),
803 * @c plus(), @c times(), etc.
804 * @return The semiring value of the circuit at gate @p g,
805 * as stored in @p provenance_mapping: a copy is
806 * the caller's to make, or not (a formula may
807 * be large).
808 */
809template<typename S, std::enable_if_t<std::is_base_of_v<semiring::Semiring<typename S::value_type>, S>, int> = 0>
810const typename S::value_type &evaluate(gate_t g, std::unordered_map<gate_t, typename S::value_type> &provenance_mapping, S semiring) const;
811
812/**
813 * @brief The equations of the @c gate_fixsystem @p sys, as linear forms
814 * over the gates that do not depend on its unknowns.
815 *
816 * The same reading as @c solveFixSystem's, kept symbolic: the coefficients
817 * are gates to evaluate, not semiring values, so that an evaluator can solve
818 * the system in each sampled world. Throws the same refusals on a
819 * recursion that is not linear.
820 *
821 * @param sys The @c gate_fixsystem gate.
822 * @return Its linear forms.
823 */
825
826/**
827 * @brief Least solution of the equation system of a @c gate_fixsystem.
828 *
829 * The system, x_i = f_i(x), is linear (PostgreSQL forbids a recursive
830 * reference appearing twice in the recursive term): each f_i is read as
831 * b_i ⊕ ⨁_j l_ij ⊗ x_j ⊗ r_ij, where b_i and the l_ij, r_ij (the factors
832 * before and after the unknown, apart for a semiring that does not
833 * commute) are evaluated in @p semiring like any other sub-circuit, which
834 * makes x the path provenance, from a virtual source, of the graph with an
835 * edge j → i of weight l_ij ⊗ · ⊗ r_ij. The system is solved one strongly
836 * connected component at a time, in topological order; an acyclic part is
837 * exact in every semiring. A cyclic component is solved by Dijkstra when
838 * @p semiring is absorptive and selective, by value iteration when it is
839 * only absorptive (a derivation repeating a tuple is absorbed by a shorter
840 * one, so the iteration converges), by Gaussian elimination when it has a
841 * star, and kept as named equations by a rendering semiring (formula); it
842 * is refused otherwise, its least solution being an infinite sum. Gaussian
843 * elimination in a non-commutative semiring needs every unknown on the same
844 * side of its coefficients, and refuses the component otherwise.
845 *
846 * @param sys The @c gate_fixsystem gate.
847 * @param provenance_mapping As in @c evaluate, for the sub-circuits that
848 * do not depend on the unknowns.
849 * @param semiring Semiring instance.
850 * @return The solution, one value per unknown, in wire
851 * order.
852 */
853template<typename S, std::enable_if_t<std::is_base_of_v<semiring::Semiring<typename S::value_type>, S>, int> = 0>
854std::vector<typename S::value_type> solveFixSystem(gate_t sys, std::unordered_map<gate_t, typename S::value_type> &provenance_mapping, S semiring) const;
855
856};
857
858#endif /* GENERIC_CIRCUIT_H */
gate_t
Strongly-typed gate identifier.
Definition Circuit.h:53
Out-of-line template method implementations for Circuit<gateType>.
Abstract semiring interface for provenance evaluation.
std::vector< unsigned char > name_kind
Definition Circuit.h:190
std::string uuid
Definition Circuit.h:175
std::vector< gate_t > & getWires(gate_t g)
Definition Circuit.h:311
gate_type getGateType(gate_t g) const
Definition Circuit.h:301
std::unordered_map< gate_uuid, gate_t, gate_uuid_hash > uuid2id
Definition Circuit.h:188
std::unordered_map< gate_t, std::string > id2name
Definition Circuit.h:192
void setGateType(gate_t g, gate_type t)
Definition Circuit.h:223
std::vector< gate_type > gates
Definition Circuit.h:215
std::vector< gate_uuid > id2uuid
Definition Circuit.h:189
uuid getUUID(gate_t g) const
Definition Circuit.hpp:65
std::vector< std::vector< gate_t > > wires
Definition Circuit.h:216
void bindName(gate_t g, const gate_uuid &u)
Definition Circuit.hpp:78
std::vector< gate_t >::size_type getNbGates() const
Definition Circuit.h:252
std::unordered_map< std::string, gate_t > name2id
Definition Circuit.h:191
void resolveToPlus(gate_t g, std::vector< gate_t > w)
Rewrite an arbitrary gate as a gate_plus over w.
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.
void resolveToCategoricalMixture(gate_t g, std::vector< gate_t > wires_)
Rewrite g in place as a categorical-form gate_mixture over wires ([key, mul_1, ......
void resolveGateToZero(gate_t g)
Replace an arbitrary gate (typically gate_times) by gate_zero.
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.
std::vector< std::pair< gate_t, std::shared_ptr< void > > > solved_systems
Equation systems solved by evaluate, with their solutions.
void markAbsorptiveAssumed(gate_t g)
Mark gate g as absorptive-assumed (in-memory side band).
void resolveCmpToPlusOfKGates(gate_t g, const std::vector< gate_t > &ks)
Replace a gate_cmp by a gate_plus over the given per-row K-gates (the OR of the agg's row-presence in...
void resolveGateToOne(gate_t g)
Rewrite a gate as gate_one, the event that holds in every world.
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.
gate_t addAnonymousMulinputGateWithValue(gate_t key, double p, unsigned value_index, const std::string &value_text)
Allocate a fresh gate_mulinput labelled with a numeric outcome value carried in extra.
void resolveToRv(gate_t g, const std::string &s)
Rewrite an arbitrary gate as a gate_rv carrying the distribution-spec extra s.
bool foldSemiringIdentities()
Drop semiring identity wires and collapse single-wire gate_times / gate_plus to their lone non-identi...
void resolveToCase(gate_t g, std::vector< gate_t > w)
Rewrite a gate as the gate_case over w (guards and values, then the default).
void foldAbsorptiveIdentities()
Absorptive-rules-only variant of foldBooleanIdentities(): the joint fixpoint of the absorptive fold r...
void resolveToMixture(gate_t g, gate_t p_token, gate_t x_token, gate_t y_token)
Rewrite g in place as a gate_mixture over the wires [p_token, x_token, y_token].
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.
gate_t addAnonymousArithGate(provsql_arith_op op, std::vector< gate_t > wires_)
Allocate a fresh gate_arith gate with operator tag op and the given wires.
gate_t addAnonymousValueGate(const std::string &text)
Allocate a fresh gate_value gate carrying the textual scalar text.
void serialize(Archive &ar, const unsigned int version)
Boost serialisation support.
friend class dDNNFTreeDecompositionBuilder
std::set< gate_t > absorptive_assumed_gates
Side-band absorptive-assumption marker set by the absorptive fold rules (plus-idempotence,...
std::vector< std::string > getMappableUUIDs() const
The UUIDs a provenance mapping can label: those of the input gates, and of the mulinput gates,...
bool isCategoricalMixture(gate_t g) const
Test whether g is a categorical-form gate_mixture (the explicit provsql.categorical output).
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...
void setInfos(gate_t g, unsigned info1, unsigned info2)
Set the integer annotation pair for gate g.
std::string getExtra(gate_t g) const
Return the string extra for gate g.
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...
gate_t addAnonymousGate(gate_type type, std::vector< gate_t > wires_)
Allocate a fresh gate of type type over wires_.
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.
void resolveCmpToBernoulli(gate_t g, double p)
Replace a gate_cmp by a constant Boolean leaf (gate_one for p == 1, gate_zero for p == 0) or by a Ber...
void redirectGates(std::unordered_map< gate_t, gate_t > subst)
Make every reference to a gate of subst point to its target instead.
gate_t addAnonymousInputGate(double p)
Allocate a fresh gate_input gate carrying probability p, with a unique synthetic UUID so subsequent B...
friend class boost::serialization::access
const std::set< gate_t > & getInputs() const
Return the set of input (leaf) gates.
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.
void liftConditionedToTarget(gate_t g, gate_t target)
Replace a gate_conditioned g by a transparent passthrough to its target child (a single-child gate_ar...
void setExtra(gate_t g, const std::string &ex)
Attach a string extra to gate g.
virtual std::string toString(gate_t g) const override
Return a placeholder debug string (not intended for display).
gate_t addAnonymousMulinputGate(gate_t key, double p, unsigned value_index)
Allocate a fresh gate_mulinput gate with key key, probability p, and value index value_index.
bool applyFoldRuleSweep(bool boolean_level)
One pass of the fold rules over every gate_plus / gate_times.
void resolveToValue(gate_t g, const std::string &s)
Rewrite an arbitrary gate as a gate_value carrying the textual extra s.
void setGate(gate_t g, gate_type type)
Set the type of the existing gate g, as setGate does for a UUID, without looking the UUID up.
void foldBooleanIdentities()
Apply the Boolean-only AND the absorptive simplification rules to gate_plus and gate_times,...
void setProb(gate_t g, double p)
Set the probability for gate g.
Core types, constants, and utilities shared across ProvSQL.
provsql_arith_op
Arithmetic operator tags used by gate_arith.
@ PROVSQL_ARITH_PLUS
n-ary, sum of children
@ 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_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)
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.