ProvSQL C/C++ API
Adding support for provenance and uncertainty management to PostgreSQL databases
Loading...
Searching...
No Matches
semiring::Semiring< V > Class Template Referenceabstract

Abstract base class for (m-)semirings. More...

#include "Semiring.h"

Public Types

typedef V value_type
 The carrier type of this semiring.

Public Member Functions

virtual value_type zero () const =0
 Return the additive identity \(\mathbb{0}\).
virtual value_type one () const =0
 Return the multiplicative identity \(\mathbb{1}\).
virtual value_type plus (const std::vector< value_type > &v) const =0
 Apply the additive operation to a list of values.
virtual value_type times (const std::vector< value_type > &v) const =0
 Apply the multiplicative operation to a list of values.
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 monus (value_type x, value_type y) const =0
 Apply the monus (m-semiring difference) operation.
virtual value_type delta (value_type x) const =0
 Apply the \(\delta\) operator.
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 absorptive () const
 Return true if this semiring is absorptive ( \(\mathbb{1} \oplus a = \mathbb{1}\) for all \(a\)).
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.
virtual bool exact_equality () const
 Return true if equal decides equality of semiring elements.
virtual bool exclusive () const
 Return true if the semiring is exclusive: \(a \otimes (\mathbb{1} \ominus a) = \mathbb{0}\).
virtual bool mul_idempotent () const
 Return true if \(\otimes\) is idempotent: \(a \otimes a = a\).
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).
virtual bool mul_sub_left_distributive () const
 Return true if \(\otimes\) distributes over the monus on the left: \(a \otimes (b \ominus c) = (a \otimes b) \ominus (a \otimes c)\) for all \(a, b, c\).
virtual bool compatibleWithBooleanRewrite () const
 Return true if a semiring homomorphism BoolFunc(X) →+* S exists, so the safe-query (Boolean-rewrite) optimisation produces circuits that are semantically faithful when evaluated under this semiring.
virtual bool certifying () const
 Whether this semiring builds certified exclusive enumerations (see the three hooks below).
virtual bool independent_literal (const value_type &) const
 Whether v is an independent literal for certification purposes: a base Bernoulli variable (or a constant), so that distinct literals have disjoint supports and an AND over them is decomposable.
virtual value_type certified_world_term (const std::vector< value_type > &, const std::vector< value_type > &) const
 Build one complete world term: the conjunction of the present literals and the negations of the missing literals, certified decomposable.
virtual value_type certified_exclusive_plus (const std::vector< value_type > &) const
 Build the disjunction of pairwise-exclusive disjuncts, certified deterministic.

Detailed Description

template<typename V>
class semiring::Semiring< V >

Abstract base class for (m-)semirings.

Template Parameters
VThe carrier type (e.g. bool, unsigned, std::string).

Required operations

All pure-virtual methods must be implemented by concrete subclasses.

Optional operations

cmp(), semimod(), agg(), and value() have default implementations that throw SemiringException. Override them in subclasses that support these circuit gate types.

Absorptive semirings

A semiring is absorptive (i.e., \(\mathbb{1} \oplus a = \mathbb{1}\) for all \(a\)) iff absorptive() returns true. Absorptivity implies idempotency ( \(a \oplus a = a\)), which lets the circuit evaluator and the HAVING-semantics machinery deduplicate operands and short-circuit over the multiplicative identity. An absorptive semiring gets its existential MIN / MAX HAVING comparisons (MIN below, MAX above a constant) in a single scan instead of a world enumeration; when its \(\otimes\) also distributes over \(\ominus\) (mul_sub_left_distributive()), so do the other MIN / MAX comparisons.

Definition at line 118 of file Semiring.h.

Member Typedef Documentation

◆ value_type

template<typename V>
typedef V semiring::Semiring< V >::value_type

The carrier type of this semiring.

Definition at line 122 of file Semiring.h.

Constructor & Destructor Documentation

◆ ~Semiring()

template<typename V>
virtual semiring::Semiring< V >::~Semiring ( )
virtualdefault

Member Function Documentation

◆ absorptive()

template<typename V>
virtual bool semiring::Semiring< V >::absorptive ( ) const
inlinevirtual

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 in semiring::BestPath, semiring::Boolean, semiring::BoolExpr, semiring::IntervalUnion, semiring::Lukasiewicz, semiring::MinMax, semiring::Subset, semiring::TropicalNonneg, and semiring::Viterbi.

Definition at line 421 of file Semiring.h.

Here is the caller graph for this function:

◆ agg()

template<typename V>
virtual value_type semiring::Semiring< V >::agg ( AggregationOperator op,
const std::vector< value_type > & s )
inlinevirtual

Evaluate an aggregation gate.

Parameters
opThe aggregation function (COUNT, SUM, MIN…).
sList of child semiring values to aggregate.
Returns
The aggregated value.
Exceptions
SemiringExceptionif not overridden.

Reimplemented in semiring::Formula.

Definition at line 235 of file Semiring.h.

◆ arith()

template<typename V>
virtual value_type semiring::Semiring< V >::arith ( ArithmeticOperator op,
const std::vector< value_type > & children,
const std::string & extra ) const
inlinevirtual

Evaluate an arithmetic gate over scalar children (gate_arith).

Parameters
opThe arithmetic operation.
childrenThe values of the gate's wires (for PERCENTILE, interleaved [indicator, value] pairs).
extraThe gate's payload (the fraction for PERCENTILE, empty otherwise).
Returns
The result of the operation in this semiring.
Exceptions
SemiringExceptionif not overridden.

Reimplemented in semiring::Formula.

Definition at line 303 of file Semiring.h.

◆ categorical()

template<typename V>
virtual value_type semiring::Semiring< V >::categorical ( value_type key,
const std::vector< double > & probs,
const std::vector< std::string > & outcomes ) const
inlinevirtual

Evaluate a categorical mixture (gate_mixture over gate_mulinput outcomes).

Parameters
keyThe value of the mixture's key (its gate_input wire).
probsProbability of each outcome.
outcomesTextual payload of each outcome, parallel to probs.
Exceptions
SemiringExceptionif not overridden.

Reimplemented in semiring::Formula.

Definition at line 340 of file Semiring.h.

◆ certified_exclusive_plus()

template<typename V>
virtual value_type semiring::Semiring< V >::certified_exclusive_plus ( const std::vector< value_type > & ) const
inlinevirtual

Build the disjunction of pairwise-exclusive disjuncts, certified deterministic.

Only called when certifying() is true; the default throws.

Reimplemented in semiring::BoolExpr.

Definition at line 744 of file Semiring.h.

◆ certified_world_term()

template<typename V>
virtual value_type semiring::Semiring< V >::certified_world_term ( const std::vector< value_type > & ,
const std::vector< value_type > &  ) const
inlinevirtual

Build one complete world term: the conjunction of the present literals and the negations of the missing literals, certified decomposable.

Only called when certifying() is true; the default throws.

Reimplemented in semiring::BoolExpr.

Definition at line 732 of file Semiring.h.

◆ certifying()

template<typename V>
virtual bool semiring::Semiring< V >::certifying ( ) const
inlinevirtual

Whether this semiring builds certified exclusive enumerations (see the three hooks below).

The HAVING possible-worlds machinery (provsql_having) enumerates, for a comparison over a group aggregate, the complete valuations of the group's contributors that satisfy the predicate. Those disjuncts partition the worlds – the OR is deterministic and each world term an AND of literals over distinct contributors, decomposable – i.e., the enumeration is a d-DNNF by construction. A circuit-building semiring can persist that knowledge as the d-DNNF certificate (the same mark the bounded-treewidth reachability route emits), letting the linear certificate-aware evaluators handle the result; scalar semirings have nothing to mark.

Returns
false by default (the hooks below then go unused and the default constructions are used).

Reimplemented in semiring::BoolExpr.

Definition at line 707 of file Semiring.h.

◆ cmp()

template<typename V>
virtual value_type semiring::Semiring< V >::cmp ( value_type s1,
ComparisonOperator op,
value_type s2 ) const
inlinevirtual

Evaluate a comparison gate.

Parameters
s1Left operand.
opComparison operator.
s2Right operand.
Returns
Result of the comparison in this semiring.
Exceptions
SemiringExceptionif not overridden.

Reimplemented in semiring::Formula.

Definition at line 211 of file Semiring.h.

◆ commutative()

template<typename V>
virtual bool semiring::Semiring< V >::commutative ( ) const
inlinevirtual

Return true if \(\otimes\) is commutative ( \(a \otimes b = b \otimes a\) for all \(a, b\)).

A product gate keeps its factors in the order of the query (the order of the FROM clause for a join), which a non-commutative semiring reads as it is: the regular expressions of Regex concatenate words in that order. The equations of a recursive query then have the recursive relation on a definite side of each coefficient; Gaussian elimination (GenericCircuit::solveFixSystem) needs it on the same side throughout, and refuses a non-commutative semiring otherwise.

Returns
true by default; override to return false.

Reimplemented in semiring::BestPath, semiring::Regex, and semiring::TropicalPaths.

Definition at line 487 of file Semiring.h.

◆ compatibleWithBooleanRewrite()

template<typename V>
virtual bool semiring::Semiring< V >::compatibleWithBooleanRewrite ( ) const
inlinevirtual

Return true if a semiring homomorphism BoolFunc(X) →+* S exists, so the safe-query (Boolean-rewrite) optimisation produces circuits that are semantically faithful when evaluated under this semiring.

The compiled-semiring dispatcher consults this predicate before evaluating a circuit whose root gate carries PROVSQL_ROOT_TAG_BOOLEAN_REWRITE. Returning false on a tagged circuit raises CircuitException.

Defaults to false: a new semiring whose author has not yet verified the homomorphism is fail-closed by construction. Subclasses with a verified homomorphism (currently Boolean, BoolExpr, Formula, and IntervalUnion) override to return true. The justification (Lean-proof reference) belongs in a comment next to each override; see the src/semiring/ headers.

Reimplemented in semiring::Boolean, semiring::BoolExpr, semiring::Counting, semiring::Formula, semiring::How, semiring::IntervalUnion, semiring::Lukasiewicz, semiring::MinMax, semiring::Subset, semiring::Tropical, semiring::Viterbi, semiring::Which, and semiring::Why.

Definition at line 685 of file Semiring.h.

◆ conditioned()

template<typename V>
virtual value_type semiring::Semiring< V >::conditioned ( const std::vector< value_type > & children) const
inlinevirtual

Evaluate a conditioning marker (gate_conditioned).

Parameters
childrenThe gate's wires: [target, evidence] for the value-level (random-variable) form, [target, evidence, joint] for the Boolean-event one, where joint is the materialised times(target, evidence).
Exceptions
SemiringExceptionif not overridden.

Reimplemented in semiring::Formula.

Definition at line 392 of file Semiring.h.

◆ define()

template<typename V>
virtual void semiring::Semiring< V >::define ( const value_type & unknown,
const value_type & rhs ) const
inlinevirtual

Record the equation unknown = rhs.

Parameters
unknownA value returned by symbolic_unknown.
rhsIts right-hand side, over unknowns of the same kind.

Reimplemented in semiring::Formula.

Definition at line 564 of file Semiring.h.

◆ delta()

◆ equal()

template<typename V>
virtual bool semiring::Semiring< V >::equal ( const value_type & a,
const value_type & b ) const
inlinevirtual

Equality of the semiring elements two values denote.

== on value_type by default; overridden where a value is a handle on the element, not the element itself (a multirange Datum passed by reference, compared by its contents).

Reimplemented in semiring::IntervalUnion.

Definition at line 577 of file Semiring.h.

Here is the caller graph for this function:

◆ exact_equality()

template<typename V>
virtual bool semiring::Semiring< V >::exact_equality ( ) const
inlinevirtual

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 in semiring::BoolExpr, semiring::Formula, semiring::Regex, and semiring::TropicalPaths.

Definition at line 594 of file Semiring.h.

Here is the caller graph for this function:

◆ exclusive()

template<typename V>
virtual bool semiring::Semiring< V >::exclusive ( ) const
inlinevirtual

Return true if the semiring is exclusive: \(a \otimes (\mathbb{1} \ominus a) = \mathbb{0}\).

Equivalently \(a \otimes (\mathbb{1} \ominus (a \oplus b)) = \mathbb{0}\), the form the worlds of a family take: a world's annotation and the absence of what it holds cancel. Lean exclusive.

Returns
false by default; override to return true only with a proof.

Reimplemented in semiring::Boolean, semiring::BoolExpr, semiring::Counting, semiring::IntervalUnion, semiring::Subset, and semiring::Which.

Definition at line 608 of file Semiring.h.

Here is the caller graph for this function:

◆ guarded_case()

template<typename V>
virtual value_type semiring::Semiring< V >::guarded_case ( const std::vector< value_type > & children) const
inlinevirtual

Evaluate a guarded selection (gate_case).

Parameters
childrenThe gate's wires, [guard_1, value_1, …, guard_k, value_k, default] (odd length), with first-match semantics.
Exceptions
SemiringExceptionif not overridden.

Reimplemented in semiring::Formula.

Definition at line 359 of file Semiring.h.

◆ has_star()

template<typename V>
virtual bool semiring::Semiring< V >::has_star ( ) const
inlinevirtual

Return true if star computes \(a^* = \mathbb{1} \oplus a \oplus a^2 \oplus \cdots\).

With a star, a cyclic linear equation system has its least solution computed by Gaussian elimination (node elimination; Ramusat, Maniu & Senellart, EDBT 2021, after Lehmann 1977), in a semiring that is not absorptive: counting extended with \(\infty\), min-plus with \(-\infty\), why- and which-provenance.

The default holds for an idempotent semiring with exact equality, whose star the default star iterates to, the partial sums only growing; they stop where the carrier has finitely many elements above \(\mathbb{1}\) reachable from \(a\) (sets of sets of input tuples, ...).

Reimplemented in semiring::Counting, semiring::Regex, semiring::Tropical, and semiring::TropicalPaths.

Definition at line 507 of file Semiring.h.

Here is the call graph for this function:

◆ idempotent()

template<typename V>
virtual bool semiring::Semiring< V >::idempotent ( ) const
inlinevirtual

Return true if this semiring is idempotent ( \(a \oplus a = a\) for all \(a\)).

Absorptivity implies idempotence, so the default forwards to absorptive(); override to return true in a semiring that is idempotent without being absorptive (why- and which-provenance, where \(\oplus\) is set union).

The HAVING machinery (provsql_having in having_semantics.hpp) uses it for the monotone comparisons, those whose valid worlds are closed under supersets (MIN below, MAX above a constant, COUNT above a constant, SUM above a constant over non-negative values, bool_or = true, bool_and = false): over such a family the monus factors cancel from the possible-world sum, which is then the plain \(\oplus\)-sum of the products of the present annotations (Lean Having.witness_identity in provenance-lean/Provenance/Having.lean, which assumes idempotence only). The enumeration stays exhaustive; absorptivity is what further collapses it to the minimal worlds.

Returns
absorptive() by default; override to return true only with a proof (the Lean *.idempotent lemmas).

Reimplemented in semiring::Regex, semiring::TropicalPaths, semiring::Which, and semiring::Why.

Definition at line 449 of file Semiring.h.

Here is the call graph for this function:
Here is the caller graph for this function:

◆ independent_literal()

template<typename V>
virtual bool semiring::Semiring< V >::independent_literal ( const value_type & ) const
inlinevirtual

Whether v is an independent literal for certification purposes: a base Bernoulli variable (or a constant), so that distinct literals have disjoint supports and an AND over them is decomposable.

Only consulted when certifying() is true.

Returns
false by default.

Reimplemented in semiring::BoolExpr.

Definition at line 721 of file Semiring.h.

◆ mixture()

template<typename V>
virtual value_type semiring::Semiring< V >::mixture ( value_type p,
value_type x,
value_type y ) const
inlinevirtual

Evaluate a Bernoulli mixture (gate_mixture, three wires).

Parameters
pThe Bernoulli event's value.
xThe value taken when the event holds.
yThe value taken otherwise.
Exceptions
SemiringExceptionif not overridden.

Reimplemented in semiring::Formula.

Definition at line 322 of file Semiring.h.

◆ monus()

template<typename V>
virtual value_type semiring::Semiring< V >::monus ( value_type x,
value_type y ) const
pure virtual

◆ mul_idempotent()

template<typename V>
virtual bool semiring::Semiring< V >::mul_idempotent ( ) const
inlinevirtual

Return true if \(\otimes\) is idempotent: \(a \otimes a = a\).

Not to be confused with idempotent(), which is about \(\oplus\). Lean mulIdempotent.

Returns
false by default; override to return true only with a proof.

Reimplemented in semiring::Boolean, semiring::BoolExpr, semiring::IntervalUnion, semiring::Subset, and semiring::Which.

Definition at line 621 of file Semiring.h.

Here is the caller graph for this function:

◆ mul_sub_left_distributive()

template<typename V>
virtual bool semiring::Semiring< V >::mul_sub_left_distributive ( ) const
inlinevirtual

Return true if \(\otimes\) distributes over the monus on the left: \(a \otimes (b \ominus c) = (a \otimes b) \ominus (a \otimes c)\) for all \(a, b, c\).

Together with absorptivity, this is the hypothesis under which the HAVING machinery (provsql_having in having_semantics.hpp) may replace the possible-world enumeration of a non-existential MIN / MAX comparison (MIN above, MAX below a constant, or either equal to one) by its single-scan closed form (Lean Having.minScan_correct / Having.maxScan_correct in provenance-lean/Provenance/HavingMinMax.lean); the existential comparisons need absorptivity alone (Lean Having.sum_ann_meet in provenance-lean/Provenance/Having.lean). Holds in the Boolean, counting, tropical, Viterbi, Łukasiewicz and interval-union semirings; fails in the security (min-max) semiring, which is absorptive but not distributive, and in Why / Which / How.

Returns
false by default; override to return true only with a proof (the Lean *.mul_sub_left_distributive lemmas).

Reimplemented in semiring::BestPath, semiring::Boolean, semiring::BoolExpr, semiring::Counting, semiring::IntervalUnion, semiring::Lukasiewicz, semiring::Subset, semiring::Tropical, and semiring::Viterbi.

Definition at line 663 of file Semiring.h.

◆ observe()

template<typename V>
virtual value_type semiring::Semiring< V >::observe ( value_type child,
const std::string & datum ) const
inlinevirtual

Evaluate a latent-variable observation (gate_observe).

Parameters
childThe observed leaf's value.
datumThe observed value, as text.
Exceptions
SemiringExceptionif not overridden.

Reimplemented in semiring::Formula.

Definition at line 374 of file Semiring.h.

◆ one()

template<typename V>
virtual value_type semiring::Semiring< V >::one ( ) const
pure virtual

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

Returns
The one element of the semiring.

Implemented in semiring::BestPath, semiring::Boolean, semiring::BoolExpr, semiring::Counting, semiring::Formula, semiring::How, semiring::IntervalUnion, semiring::Lukasiewicz, semiring::MinMax, semiring::Regex, semiring::Subset, semiring::Tropical, semiring::TropicalPaths, semiring::Viterbi, semiring::Which, and semiring::Why.

Here is the caller graph for this function:

◆ plus()

template<typename V>
virtual value_type semiring::Semiring< V >::plus ( const std::vector< value_type > & v) const
pure virtual

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\).

Implemented in semiring::BestPath, semiring::Boolean, semiring::BoolExpr, semiring::Counting, semiring::Formula, semiring::How, semiring::IntervalUnion, semiring::Lukasiewicz, semiring::MinMax, semiring::Regex, semiring::Subset, semiring::Tropical, semiring::TropicalPaths, semiring::Viterbi, semiring::Which, and semiring::Why.

Here is the caller graph for this function:

◆ plus_of()

template<typename V>
virtual value_type semiring::Semiring< V >::plus_of ( const std::vector< const value_type * > & v) const
inlinevirtual

plus over the values v points to, read in place.

GenericCircuit::evaluate passes the values of a gate's children this way rather than copied into a vector. The default copies them and calls plus; a semiring whose values may be large (Formula) overrides it.

Parameters
vOrdered list of pointers to the operands.
Returns
\(v_0 \oplus v_1 \oplus \cdots\).

Reimplemented in semiring::Formula.

Definition at line 162 of file Semiring.h.

Here is the call graph for this function:

◆ product_is_joint()

template<typename V>
bool semiring::Semiring< V >::product_is_joint ( ) const
inline

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).

The provenance of a selection on aggregates is a sum over the worlds of the family they read. Taken condition by condition and multiplied, it is that sum exactly when the semiring is exclusive with an idempotent \(\otimes\) (Lean predProvOf_mul_predProvOf): the HAVING machinery then keeps the conditions apart, with their closed forms, and resolves them jointly otherwise (provsql_having). Counting is exclusive, and its \(\otimes\) is not idempotent.

Definition at line 638 of file Semiring.h.

Here is the call graph for this function:

◆ rv()

template<typename V>
virtual value_type semiring::Semiring< V >::rv ( const std::string & spec,
const std::vector< value_type > & params ) const
inlinevirtual

Evaluate a continuous random-variable leaf (gate_rv).

Parameters
specThe gate's distribution encoding ("normal:2.5,0.5"), where a parameter written "$i" is wired rather than literal (a latent / compound leaf).
paramsThe values of the gate's wires, indexed as the "$i" references; empty for an all-literal leaf.
Returns
The leaf's value in this semiring.
Exceptions
SemiringExceptionif not overridden.

Reimplemented in semiring::Formula.

Definition at line 282 of file Semiring.h.

◆ selective()

template<typename V>
virtual bool semiring::Semiring< V >::selective ( ) const
inlinevirtual

Return true if \(\oplus\) is selective (for all \(a, b\), \(a \oplus b \in \{a, b\}\)).

In an idempotent semiring this is the same as a total natural order; in general it is stronger (the counting semiring has a total natural order, but \(a + b\) is neither \(a\) nor \(b\)). In a selective absorptive semiring (a selective dioid, in Gondran & Minoux's terms), the least solution of a cyclic equation system (a recursive query, see GenericCircuit::solveFixSystem) is found by Dijkstra's algorithm, generalised to semirings (Ramusat, Maniu & Senellart, EDBT 2021): absorption makes extending a derivation never improve it, and selectivity lets the best unsettled value be final.

Returns
false by default; override to return true.

Reimplemented in semiring::BestPath, semiring::Boolean, semiring::Lukasiewicz, semiring::MinMax, semiring::Tropical, and semiring::Viterbi.

Definition at line 469 of file Semiring.h.

◆ semimod()

template<typename V>
virtual value_type semiring::Semiring< V >::semimod ( value_type x,
value_type s ) const
inlinevirtual

Apply a semimodule scalar multiplication.

Parameters
xProvenance value.
sScalar value.
Returns
\(x * s\) in the semimodule.
Exceptions
SemiringExceptionif not overridden.

Reimplemented in semiring::Formula.

Definition at line 223 of file Semiring.h.

◆ star()

template<typename V>
virtual value_type semiring::Semiring< V >::star ( const value_type & a) const
inlinevirtual

\(a^*\), the sum of the powers of a.

By default, iterates \(s \leftarrow \mathbb{1} \oplus a \otimes s\) from \(\mathbb{1}\) until it stops changing, which an idempotent semiring with finitely many partial sums ensures.

Reimplemented in semiring::BestPath, semiring::Counting, semiring::Regex, semiring::Tropical, and semiring::TropicalPaths.

Definition at line 518 of file Semiring.h.

Here is the call graph for this function:

◆ symbolic()

template<typename V>
virtual bool semiring::Semiring< V >::symbolic ( ) const
inlinevirtual

Return true if the semiring can name an unknown and record an equation over it (symbolic_unknown, define).

A symbolic semiring renders the provenance rather than evaluating it; where a recursion derives a tuple through itself, the least solution of its equations is an infinite sum, which such a semiring renders as the equations themselves (see GenericCircuit::solveFixSystem).

Returns
false by default; override, with the two methods below.

Reimplemented in semiring::Formula.

Definition at line 540 of file Semiring.h.

◆ symbolic_unknown()

template<typename V>
virtual value_type semiring::Semiring< V >::symbolic_unknown ( std::size_t position) const
inlinevirtual

A fresh unknown, as a value.

Parameters
position1-based position of the unknown among its system's unknowns: the index a gate_fixpoint reading it stores in info1, and the name ProvSQL Studio gives it, so a rendering can use the same name.
Returns
the unknown; throws by default.

Reimplemented in semiring::Formula.

Definition at line 553 of file Semiring.h.

◆ times()

template<typename V>
virtual value_type semiring::Semiring< V >::times ( const std::vector< value_type > & v) const
pure virtual

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\).

Implemented in semiring::BestPath, semiring::Boolean, semiring::BoolExpr, semiring::Counting, semiring::Formula, semiring::How, semiring::IntervalUnion, semiring::Lukasiewicz, semiring::MinMax, semiring::Regex, semiring::Subset, semiring::Tropical, semiring::TropicalPaths, semiring::Viterbi, semiring::Which, and semiring::Why.

Here is the caller graph for this function:

◆ times_of()

template<typename V>
virtual value_type semiring::Semiring< V >::times_of ( const std::vector< const value_type * > & v) const
inlinevirtual

times over the values v points to, read in place (see plus_of).

Parameters
vOrdered list of pointers to the operands.
Returns
\(v_0 \otimes v_1 \otimes \cdots\).

Reimplemented in semiring::Formula.

Definition at line 177 of file Semiring.h.

Here is the call graph for this function:

◆ unmapped_input()

template<typename V>
virtual value_type semiring::Semiring< V >::unmapped_input ( const std::string & uuid) const
inlinevirtual

Value of a variable leaf (gate_input / gate_mulinput) that the provenance mapping does not name.

The absent-mapping convention: such a leaf contributes no provenance, i.e. the multiplicative identity, which is what every proper semiring wants and what this default returns. A semiring that renders the circuit rather than evaluating it overrides this to identify the leaf instead – \(\mathbb{1}\) would not merely be anonymous there, it would be absorbed by the enclosing times and take the structure with it. BooleanCircuit::toString does the same for the Boolean-expression rendering (its x<id> fallback).

Parameters
uuidThe leaf gate's UUID, in canonical text form.

Reimplemented in semiring::Formula.

Definition at line 267 of file Semiring.h.

Here is the call graph for this function:

◆ value()

template<typename V>
virtual value_type semiring::Semiring< V >::value ( const std::string & s) const
inlinevirtual

Interpret a literal string as a semiring value.

Used for gate_value gates whose payload is a string.

Parameters
sLiteral string.
Returns
The corresponding semiring value.
Exceptions
SemiringExceptionif not overridden.

Reimplemented in semiring::Formula.

Definition at line 248 of file Semiring.h.

◆ zero()


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