ProvSQL C/C++ API
Adding support for provenance and uncertainty management to PostgreSQL databases
Loading...
Searching...
No Matches
semiring::BoolExpr Class Reference

Provenance-as-Boolean-circuit semiring. More...

#include "BoolExpr.h"

Inheritance diagram for semiring::BoolExpr:
Collaboration diagram for semiring::BoolExpr:

Public Member Functions

 BoolExpr (BooleanCircuit &bc)
 Construct a BoolExpr semiring over the given circuit.
value_type zero () const override
 Return the additive identity \(\mathbb{0}\).
value_type one () const override
 Return the multiplicative identity \(\mathbb{1}\).
value_type plus (const std::vector< value_type > &vec) const override
 Apply the additive operation to a list of values.
value_type times (const std::vector< value_type > &vec) const override
 Apply the multiplicative operation to a list of values.
virtual value_type monus (value_type x, value_type y) const override
 Apply the monus (m-semiring difference) operation.
value_type delta (value_type x) const override
 Apply the \(\delta\) operator.
virtual bool exclusive () const override
 Exclusive: \(a \otimes (\mathbb{1} \ominus a) = \mathbb{0}\) (Lean BoolFunc.exclusive).
virtual bool mul_idempotent () const override
 \(\otimes\) is idempotent (Lean BoolFunc.mulIdempotent).
virtual bool absorptive () const override
 Return true if this semiring is absorptive ( \(\mathbb{1} \oplus a = \mathbb{1}\) for all \(a\)).
virtual bool exact_equality () const override
 Return true if equal decides equality of semiring elements.
virtual bool mul_sub_left_distributive () const override
 \(\otimes\) distributes over \(\ominus\) in the free Boolean-function algebra the circuit denotes, so the HAVING MIN / MAX comparisons take the single-scan closed form whenever the enumeration is not being certified.
virtual bool compatibleWithBooleanRewrite () const override
 BoolExpr is the free Boolean-circuit construction; the evaluation map to Bool at any valuation is an m-semiring homomorphism, so the safe-query Boolean rewrite preserves semantics.
virtual bool certifying () const override
 BoolExpr persists the d-DNNF certificate on the HAVING possible-worlds enumerations it builds (deterministic ORs over decomposable world terms), so the certificate-aware evaluators (independentEvaluation, interpretAsDD) handle the resulting circuits linearly.
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 empty AND / OR): distinct such gates have disjoint supports, so ANDs over them are decomposable.
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, marked decomposable (pairwise-distinct independent literals have disjoint supports).
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.
Public Member Functions inherited from semiring::Semiring< gate_t >
virtual value_type plus_of (const std::vector< const value_type * > &v) const
 plus over the values v points to, read in place.
virtual value_type times_of (const std::vector< const value_type * > &v) const
 times over the values v points to, read in place (see plus_of).
virtual value_type cmp (value_type s1, ComparisonOperator op, value_type s2) const
 Evaluate a comparison gate.
virtual value_type semimod (value_type x, value_type s) const
 Apply a semimodule scalar multiplication.
virtual value_type agg (AggregationOperator op, const std::vector< value_type > &s)
 Evaluate an aggregation gate.
virtual value_type value (const std::string &s) const
 Interpret a literal string as a semiring value.
virtual value_type unmapped_input (const std::string &uuid) const
 Value of a variable leaf (gate_input / gate_mulinput) that the provenance mapping does not name.
virtual value_type rv (const std::string &spec, const std::vector< value_type > &params) const
 Evaluate a continuous random-variable leaf (gate_rv).
virtual value_type arith (ArithmeticOperator op, const std::vector< value_type > &children, const std::string &extra) const
 Evaluate an arithmetic gate over scalar children (gate_arith).
virtual value_type mixture (value_type p, value_type x, value_type y) const
 Evaluate a Bernoulli mixture (gate_mixture, three wires).
virtual value_type categorical (value_type key, const std::vector< double > &probs, const std::vector< std::string > &outcomes) const
 Evaluate a categorical mixture (gate_mixture over gate_mulinput outcomes).
virtual value_type guarded_case (const std::vector< value_type > &children) const
 Evaluate a guarded selection (gate_case).
virtual value_type observe (value_type child, const std::string &datum) const
 Evaluate a latent-variable observation (gate_observe).
virtual value_type conditioned (const std::vector< value_type > &children) const
 Evaluate a conditioning marker (gate_conditioned).
virtual ~Semiring ()=default
virtual bool idempotent () const
 Return true if this semiring is idempotent ( \(a \oplus a = a\) for all \(a\)).
virtual bool selective () const
 Return true if \(\oplus\) is selective (for all \(a, b\), \(a \oplus b \in \{a, b\}\)).
virtual bool commutative () const
 Return true if \(\otimes\) is commutative ( \(a \otimes b = b \otimes a\) for all \(a, b\)).
virtual bool has_star () const
 Return true if star computes \(a^* = \mathbb{1} \oplus a \oplus a^2 \oplus \cdots\).
virtual value_type star (const value_type &a) const
 \(a^*\), the sum of the powers of a.
virtual bool symbolic () const
 Return true if the semiring can name an unknown and record an equation over it (symbolic_unknown, define).
virtual value_type symbolic_unknown (std::size_t position) const
 A fresh unknown, as a value.
virtual void define (const value_type &unknown, const value_type &rhs) const
 Record the equation unknown = rhs.
virtual bool equal (const value_type &a, const value_type &b) const
 Equality of the semiring elements two values denote.
bool product_is_joint () const
 Whether the product of the predicate provenances of two conditions over one family of occurrences is the provenance of their conjunction (and their sum that of their disjunction).

Private Types

using value_t = gate_t
 Carrier type: a gate ID in the target BooleanCircuit.

Private Attributes

BooleanCircuit & c
 The Boolean circuit being constructed.
const gate_t ZERO
 Pre-allocated zero gate (OR with no children).
const gate_t ONE
 Pre-allocated one gate (AND with no children).
std::map< gate_t, gate_t > not_cache
 Per-literal NOT gates of certified_world_term (shared across world terms).

Additional Inherited Members

Public Types inherited from semiring::Semiring< gate_t >
typedef gate_t value_type
 The carrier type of this semiring.

Detailed Description

Provenance-as-Boolean-circuit semiring.

The carrier type is gate_t (a gate identifier in BooleanCircuit). Evaluating the provenance circuit over this semiring constructs a new Boolean circuit expressing the provenance formula.

Definition at line 48 of file BoolExpr.h.

Member Typedef Documentation

◆ value_t

Carrier type: a gate ID in the target BooleanCircuit.

Definition at line 49 of file BoolExpr.h.

Constructor & Destructor Documentation

◆ BoolExpr()

semiring::BoolExpr::BoolExpr ( BooleanCircuit & bc)
inline

Construct a BoolExpr semiring over the given circuit.

Parameters
bcThe Boolean circuit in which semiring operations create new gates.

Definition at line 60 of file BoolExpr.h.

Member Function Documentation

◆ absorptive()

virtual bool semiring::BoolExpr::absorptive ( ) const
inlineoverridevirtual

Return true if this semiring is absorptive ( \(\mathbb{1} \oplus a = \mathbb{1}\) for all \(a\)).

When true, the circuit evaluator and HAVING-semantics machinery may exploit the resulting idempotency ( \(a \oplus a = a\), implied by absorptivity) to deduplicate children of plus gates and to short-circuit over the multiplicative identity.

A semiring that does not commute (commutative()) is absorptive on both sides of a product: \(a \oplus a \otimes b = a \oplus b \otimes a = a\), which the absorptive folds of the circuit rely on. Circuits built under an 'absorptive' assumption marker do not keep the order of the query, and require a commutative semiring as well.

Returns
false by default; override to return true.

Reimplemented from semiring::Semiring< gate_t >.

Definition at line 130 of file BoolExpr.h.

◆ certified_exclusive_plus()

virtual value_type semiring::BoolExpr::certified_exclusive_plus ( const std::vector< value_type > & vec) const
inlineoverridevirtual

Deterministic OR over pairwise-exclusive world terms, marked with the d-DNNF certificate.

No child deduplication: distinct complete worlds yield structurally distinct terms.

Reimplemented from semiring::Semiring< gate_t >.

Definition at line 225 of file BoolExpr.h.

◆ certified_world_term()

virtual value_type semiring::BoolExpr::certified_world_term ( const std::vector< value_type > & present,
const std::vector< value_type > & missing ) const
inlineoverridevirtual

One complete world: AND of the present literals and of NOT-gates over the missing ones, marked decomposable (pairwise-distinct independent literals have disjoint supports).

The negations are De Morgan-expanded per literal – rather than the monus(one, plus(missing)) form the uncertified construction uses – so the whole term lies inside one certified island and the sharing of contributors across the (mutually exclusive) world terms is licensed by the certificate. NOT-gates are cached per literal: the same contributor is negated in up to half the worlds.

Reimplemented from semiring::Semiring< gate_t >.

Definition at line 199 of file BoolExpr.h.

◆ certifying()

virtual bool semiring::BoolExpr::certifying ( ) const
inlineoverridevirtual

BoolExpr persists the d-DNNF certificate on the HAVING possible-worlds enumerations it builds (deterministic ORs over decomposable world terms), so the certificate-aware evaluators (independentEvaluation, interpretAsDD) handle the resulting circuits linearly.

Reimplemented from semiring::Semiring< gate_t >.

Definition at line 167 of file BoolExpr.h.

◆ compatibleWithBooleanRewrite()

virtual bool semiring::BoolExpr::compatibleWithBooleanRewrite ( ) const
inlineoverridevirtual

BoolExpr is the free Boolean-circuit construction; the evaluation map to Bool at any valuation is an m-semiring homomorphism, so the safe-query Boolean rewrite preserves semantics.

Lean: BoolFunc is the algebraic counterpart; the relevant theorems live in Provenance.Semirings.BoolFunc and Provenance.Semirings.Bool.homomorphism_to_BoolFunc.

Reimplemented from semiring::Semiring< gate_t >.

Definition at line 156 of file BoolExpr.h.

◆ delta()

value_type semiring::BoolExpr::delta ( value_type x) const
inlineoverridevirtual

Apply the \(\delta\) operator.

Parameters
xInput value.
Returns
\(\delta(x)\).

Implements semiring::Semiring< gate_t >.

Definition at line 117 of file BoolExpr.h.

◆ exact_equality()

virtual bool semiring::BoolExpr::exact_equality ( ) const
inlineoverridevirtual

Return true if equal decides equality of semiring elements.

False for a carrier that is a handle on a structure built during evaluation (a gate of the Boolean circuit BoolExpr builds, whose equivalence with another is intractable to decide) or a syntactic rendering (Formula): two equal elements may then compare unequal. The equation-system solver iterates to a fixpoint only where it can tell that one is reached, and otherwise runs the number of rounds absorption guarantees to suffice.

Returns
true by default; override to return false.

Reimplemented from semiring::Semiring< gate_t >.

Definition at line 133 of file BoolExpr.h.

◆ exclusive()

virtual bool semiring::BoolExpr::exclusive ( ) const
inlineoverridevirtual

Exclusive: \(a \otimes (\mathbb{1} \ominus a) = \mathbb{0}\) (Lean BoolFunc.exclusive).

Reimplemented from semiring::Semiring< gate_t >.

Definition at line 122 of file BoolExpr.h.

◆ independent_literal()

virtual bool semiring::BoolExpr::independent_literal ( const value_type & g) const
inlineoverridevirtual

A gate qualifies as an independent literal when it is a base Bernoulli input, or a constant (the empty AND / OR): distinct such gates have disjoint supports, so ANDs over them are decomposable.

Derived contributors (internal sub-circuits, mulinput literals whose block siblings are correlated) do not qualify.

Reimplemented from semiring::Semiring< gate_t >.

Definition at line 179 of file BoolExpr.h.

◆ monus()

virtual value_type semiring::BoolExpr::monus ( value_type x,
value_type y ) const
inlineoverridevirtual

Apply the monus (m-semiring difference) operation.

Parameters
xMinuend.
ySubtrahend.
Returns
\(x \ominus y\).

Implements semiring::Semiring< gate_t >.

Definition at line 103 of file BoolExpr.h.

◆ mul_idempotent()

virtual bool semiring::BoolExpr::mul_idempotent ( ) const
inlineoverridevirtual

\(\otimes\) is idempotent (Lean BoolFunc.mulIdempotent).

Reimplemented from semiring::Semiring< gate_t >.

Definition at line 126 of file BoolExpr.h.

◆ mul_sub_left_distributive()

virtual bool semiring::BoolExpr::mul_sub_left_distributive ( ) const
inlineoverridevirtual

\(\otimes\) distributes over \(\ominus\) in the free Boolean-function algebra the circuit denotes, so the HAVING MIN / MAX comparisons take the single-scan closed form whenever the enumeration is not being certified.

Lean: Provenance.Semirings.BoolFunc.mul_sub_left_distributive.

Reimplemented from semiring::Semiring< gate_t >.

Definition at line 144 of file BoolExpr.h.

◆ one()

value_type semiring::BoolExpr::one ( ) const
inlineoverridevirtual

Return the multiplicative identity \(\mathbb{1}\).

Returns
The one element of the semiring.

Implements semiring::Semiring< gate_t >.

Definition at line 67 of file BoolExpr.h.

◆ plus()

value_type semiring::BoolExpr::plus ( const std::vector< value_type > & v) const
inlineoverridevirtual

Apply the additive operation to a list of values.

Parameters
vOrdered list of operands (empty list should return zero()).
Returns
\(v_0 \oplus v_1 \oplus \cdots\).

Implements semiring::Semiring< gate_t >.

Definition at line 71 of file BoolExpr.h.

◆ times()

value_type semiring::BoolExpr::times ( const std::vector< value_type > & v) const
inlineoverridevirtual

Apply the multiplicative operation to a list of values.

Parameters
vOrdered list of operands (empty list should return one()).
Returns
\(v_0 \otimes v_1 \otimes \cdots\).

Implements semiring::Semiring< gate_t >.

Definition at line 87 of file BoolExpr.h.

◆ zero()

value_type semiring::BoolExpr::zero ( ) const
inlineoverridevirtual

Return the additive identity \(\mathbb{0}\).

Returns
The zero element of the semiring.

Implements semiring::Semiring< gate_t >.

Definition at line 63 of file BoolExpr.h.

Member Data Documentation

◆ c

BooleanCircuit& semiring::BoolExpr::c
private

The Boolean circuit being constructed.

Definition at line 51 of file BoolExpr.h.

◆ not_cache

std::map<gate_t, gate_t> semiring::BoolExpr::not_cache
mutableprivate

Per-literal NOT gates of certified_world_term (shared across world terms).

Definition at line 238 of file BoolExpr.h.

◆ ONE

const gate_t semiring::BoolExpr::ONE
private

Pre-allocated one gate (AND with no children).

Definition at line 53 of file BoolExpr.h.

◆ ZERO

const gate_t semiring::BoolExpr::ZERO
private

Pre-allocated zero gate (OR with no children).

Definition at line 52 of file BoolExpr.h.


The documentation for this class was generated from the following file:
  • /home/pierre/git/software/provsql/src/semiring/BoolExpr.h