ProvSQL C/C++ API
Adding support for provenance and uncertainty management to PostgreSQL databases
Loading...
Searching...
No Matches
BoolExpr.h
Go to the documentation of this file.
1/**
2 * @file semiring/BoolExpr.h
3 * @brief Boolean-expression (lineage formula) semiring.
4 *
5 * The @c BoolExpr semiring represents provenance as a Boolean circuit
6 * rather than a scalar value. Each semiring value is a @c gate_t
7 * identifier inside a shared @c BooleanCircuit. The semiring operations
8 * create new gates in that circuit:
9 *
10 * - @c zero() → a fresh OR gate with no children (always @c false)
11 * - @c one() → a fresh AND gate with no children (always @c true)
12 * - @c plus() → an OR gate whose children are the operands
13 * - @c times() → an AND gate whose children are the operands
14 * - @c monus() → an AND gate combining @f$x@f$ with a NOT of @f$y@f$
15 * - @c delta() → identity
16 *
17 * The result of evaluating a circuit over this semiring is the root gate
18 * of a new Boolean circuit that encodes the provenance formula. This
19 * circuit can then be compiled to a d-DNNF for probability computation.
20 *
21 * The semiring is absorptive: duplicate children of OR/AND gates are
22 * deduplicated during gate construction.
23 *
24 * @see https://provsql.org/lean-docs/Provenance/Semirings/BoolFunc.html
25 * Lean 4 verified instance (@c BoolFunc): the algebraic counterpart
26 * of Boolean circuits, with proofs of @c BoolFunc.absorptive,
27 * @c BoolFunc.idempotent, and @c BoolFunc.mul_sub_left_distributive.
28 */
29#ifndef BOOLEXPR_H
30#define BOOLEXPR_H
31
32#include <map>
33#include <set>
34#include <string>
35#include <vector>
36#include <algorithm>
37#include "Semiring.h"
38#include "../BooleanCircuit.h"
39
40namespace semiring {
41/**
42 * @brief Provenance-as-Boolean-circuit semiring.
43 *
44 * The carrier type is @c gate_t (a gate identifier in @c BooleanCircuit).
45 * Evaluating the provenance circuit over this semiring constructs a new
46 * Boolean circuit expressing the provenance formula.
47 */
48class BoolExpr : public Semiring<gate_t> {
49using value_t = gate_t; ///< Carrier type: a gate ID in the target BooleanCircuit
50
51BooleanCircuit &c; ///< The Boolean circuit being constructed
52const gate_t ZERO; ///< Pre-allocated zero gate (OR with no children)
53const gate_t ONE; ///< Pre-allocated one gate (AND with no children)
54
55public:
56/**
57 * @brief Construct a BoolExpr semiring over the given circuit.
58 * @param bc The Boolean circuit in which semiring operations create new gates.
59 */
60BoolExpr(BooleanCircuit &bc) : c(bc), ZERO(c.setGate(BooleanGate::OR)), ONE(c.setGate(BooleanGate::AND)) {
61}
62
63value_type zero() const override {
64 return ZERO;
65}
66
67value_type one() const override {
68 return ONE;
69}
70
71value_type plus(const std::vector<value_type> &vec) const override {
72 if(vec.empty())
73 return ZERO;
74
75 auto g = c.setGate(BooleanGate::OR);
76
77 std::set<gate_t> seen;
78 for (const auto &h : vec) {
79 if(seen.find(h)!=seen.end())
80 continue;
81 seen.insert(h);
82 c.addWire(g, h);
83 }
84 return g;
85}
86
87value_type times(const std::vector<value_type> &vec) const override {
88 if(vec.empty())
89 return ONE;
90
91 auto g = c.setGate(BooleanGate::AND);
92
93 std::set<gate_t> seen;
94 for (const auto &h : vec) {
95 if(seen.find(h)!=seen.end())
96 continue;
97 seen.insert(h);
98 c.addWire(g, h);
99 }
100 return g;
101}
102
103virtual value_type monus(value_type x, value_type y) const override {
104 auto g2 = c.setGate(BooleanGate::NOT);
105 c.addWire(g2,y);
106
107 if(x==ONE)
108 return g2;
109 else {
110 auto g1 = c.setGate(BooleanGate::AND);
111 c.addWire(g1,x);
112 c.addWire(g1,g2);
113 return g1;
114 }
115}
116
117value_type delta(value_type x) const override {
118 return x;
119}
120/** @brief Exclusive: @f$a \otimes (\mathbb{1} \ominus a) = \mathbb{0}@f$
121 * (Lean @c BoolFunc.exclusive). */
122virtual bool exclusive() const override {
123 return true;
124}
125/** @brief @f$\otimes@f$ is idempotent (Lean @c BoolFunc.mulIdempotent). */
126virtual bool mul_idempotent() const override {
127 return true;
128}
129
130virtual bool absorptive() const override {
131 return true;
132}
133virtual bool exact_equality() const override {
134 return false;
135}
136/**
137 * @brief @f$\otimes@f$ distributes over @f$\ominus@f$ in the free
138 * Boolean-function algebra the circuit denotes, so the HAVING
139 * @c MIN / @c MAX comparisons take the single-scan closed form
140 * whenever the enumeration is not being certified.
141 *
142 * Lean: @c Provenance.Semirings.BoolFunc.mul_sub_left_distributive.
143 */
144virtual bool mul_sub_left_distributive() const override {
145 return true;
146}
147/**
148 * @brief @c BoolExpr is the free Boolean-circuit construction; the
149 * evaluation map to @c Bool at any valuation is an m-semiring
150 * homomorphism, so the safe-query Boolean rewrite preserves
151 * semantics. Lean: @c BoolFunc is the algebraic counterpart;
152 * the relevant theorems live in
153 * @c Provenance.Semirings.BoolFunc and
154 * @c Provenance.Semirings.Bool.homomorphism_to_BoolFunc.
155 */
156virtual bool compatibleWithBooleanRewrite() const override {
157 return true;
158}
159
160/**
161 * @brief @c BoolExpr persists the d-DNNF certificate on the HAVING
162 * possible-worlds enumerations it builds (deterministic ORs over
163 * decomposable world terms), so the certificate-aware evaluators
164 * (@c independentEvaluation, @c interpretAsDD) handle the
165 * resulting circuits linearly.
166 */
167virtual bool certifying() const override {
168 return true;
169}
170
171/**
172 * @brief A gate qualifies as an independent literal when it is a base
173 * Bernoulli input, or a constant (the empty AND / OR): distinct
174 * such gates have disjoint supports, so ANDs over them are
175 * decomposable. Derived contributors (internal sub-circuits,
176 * @c mulinput literals whose block siblings are correlated) do
177 * not qualify.
178 */
179virtual bool independent_literal(const value_type &g) const override {
180 const auto t = c.getGateType(g);
181 if (t == BooleanGate::IN)
182 return true;
183 return (t == BooleanGate::AND || t == BooleanGate::OR) &&
184 c.getWires(g).empty();
185}
186
187/**
188 * @brief One complete world: AND of the @p present literals and of
189 * NOT-gates over the @p missing ones, marked decomposable
190 * (pairwise-distinct independent literals have disjoint
191 * supports). The negations are De Morgan-expanded per literal
192 * -- rather than the @c monus(one, plus(missing)) form the
193 * uncertified construction uses -- so the whole term lies
194 * inside one certified island and the sharing of contributors
195 * across the (mutually exclusive) world terms is licensed by
196 * the certificate. NOT-gates are cached per literal: the same
197 * contributor is negated in up to half the worlds.
198 */
200 const std::vector<value_type> &present,
201 const std::vector<value_type> &missing) const override {
202 if (missing.empty() && present.size() == 1)
203 return present[0];
204 auto g = c.setGate(BooleanGate::AND);
205 c.setInfo(g, DNNF_CERT_INFO);
206 for (const auto &h : present)
207 c.addWire(g, h);
208 for (const auto &h : missing) {
209 auto it = not_cache.find(h);
210 if (it == not_cache.end()) {
211 auto n = c.setGate(BooleanGate::NOT);
212 c.addWire(n, h);
213 it = not_cache.emplace(h, n).first;
214 }
215 c.addWire(g, it->second);
216 }
217 return g;
218}
219
220/**
221 * @brief Deterministic OR over pairwise-exclusive world terms, marked
222 * with the d-DNNF certificate. No child deduplication: distinct
223 * complete worlds yield structurally distinct terms.
224 */
226 const std::vector<value_type> &vec) const override {
227 if (vec.size() == 1)
228 return vec[0];
229 auto g = c.setGate(BooleanGate::OR);
230 c.setInfo(g, DNNF_CERT_INFO);
231 for (const auto &h : vec)
232 c.addWire(g, h);
233 return g;
234}
235
236private:
237/** @brief Per-literal NOT gates of @c certified_world_term (shared across world terms). */
238mutable std::map<gate_t, gate_t> not_cache;
239};
240}
241
242#endif // BOOLEXPR_H
@ OR
Boolean OR aggregate.
Definition Aggregation.h:59
@ AND
Boolean AND aggregate.
Definition Aggregation.h:58
Boolean provenance circuit with support for knowledge compilation.
constexpr unsigned DNNF_CERT_INFO
d-DNNF certificate value for the (gate-type-specific) per-gate info field.
BooleanGate
Gate types for a Boolean provenance circuit.
@ NOT
Logical negation of a single child gate.
@ OR
Logical disjunction of child gates.
@ AND
Logical conjunction of child gates.
@ IN
Input (variable) gate representing a base tuple.
gate_t
Strongly-typed gate identifier.
Definition Circuit.h:53
Abstract semiring interface for provenance evaluation.
Boolean circuit for provenance formula evaluation.
BoolExpr(BooleanCircuit &bc)
Construct a BoolExpr semiring over the given circuit.
Definition BoolExpr.h:60
virtual bool independent_literal(const value_type &g) const override
A gate qualifies as an independent literal when it is a base Bernoulli input, or a constant (the empt...
Definition BoolExpr.h:179
value_type plus(const std::vector< value_type > &vec) const override
Apply the additive operation to a list of values.
Definition BoolExpr.h:71
const gate_t ZERO
Pre-allocated zero gate (OR with no children).
Definition BoolExpr.h:52
value_type delta(value_type x) const override
Apply the operator.
Definition BoolExpr.h:117
value_type one() const override
Return the multiplicative identity .
Definition BoolExpr.h:67
std::map< gate_t, gate_t > not_cache
Per-literal NOT gates of certified_world_term (shared across world terms).
Definition BoolExpr.h:238
virtual bool exact_equality() const override
Return true if equal decides equality of semiring elements.
Definition BoolExpr.h:133
virtual value_type monus(value_type x, value_type y) const override
Apply the monus (m-semiring difference) operation.
Definition BoolExpr.h:103
BooleanCircuit & c
The Boolean circuit being constructed.
Definition BoolExpr.h:51
value_type zero() const override
Return the additive identity .
Definition BoolExpr.h:63
virtual bool compatibleWithBooleanRewrite() const override
BoolExpr is the free Boolean-circuit construction; the evaluation map to Bool at any valuation is an ...
Definition BoolExpr.h:156
virtual value_type certified_world_term(const std::vector< value_type > &present, const std::vector< value_type > &missing) const override
One complete world: AND of the present literals and of NOT-gates over the missing ones,...
Definition BoolExpr.h:199
virtual bool mul_sub_left_distributive() const override
distributes over in the free Boolean-function algebra the circuit denotes, so the HAVING MIN / MAX c...
Definition BoolExpr.h:144
virtual bool exclusive() const override
Exclusive: (Lean BoolFunc.exclusive).
Definition BoolExpr.h:122
gate_t value_t
Carrier type: a gate ID in the target BooleanCircuit.
Definition BoolExpr.h:49
const gate_t ONE
Pre-allocated one gate (AND with no children).
Definition BoolExpr.h:53
virtual value_type certified_exclusive_plus(const std::vector< value_type > &vec) const override
Deterministic OR over pairwise-exclusive world terms, marked with the d-DNNF certificate.
Definition BoolExpr.h:225
virtual bool absorptive() const override
Return true if this semiring is absorptive ( for all ).
Definition BoolExpr.h:130
virtual bool certifying() const override
BoolExpr persists the d-DNNF certificate on the HAVING possible-worlds enumerations it builds (determ...
Definition BoolExpr.h:167
value_type times(const std::vector< value_type > &vec) const override
Apply the multiplicative operation to a list of values.
Definition BoolExpr.h:87
virtual bool mul_idempotent() const override
is idempotent (Lean BoolFunc.mulIdempotent).
Definition BoolExpr.h:126
Abstract base class for (m-)semirings.
Definition Semiring.h:119