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

The counting semiring over unsigned. More...

#include "Counting.h"

Inheritance diagram for semiring::Counting:
Collaboration diagram for semiring::Counting:

Public Member Functions

virtual value_type zero () const override
 Return the additive identity \(\mathbb{0}\).
virtual value_type one () const override
 Return the multiplicative identity \(\mathbb{1}\).
virtual value_type plus (const std::vector< value_type > &v) const override
 Apply the additive operation to a list of values.
virtual value_type times (const std::vector< value_type > &v) 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.
virtual bool has_star () const override
 \(0^* = 1\); any other count repeats without end.
virtual value_type star (const value_type &a) const override
 \(a^*\), the sum of the powers of a.
virtual 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 Nat.exclusive); \(\otimes\) is not idempotent (Nat.not_mulIdempotent).
virtual bool mul_sub_left_distributive () const override
 \(\otimes\) distributes over \(\ominus\) (truncated subtraction on the naturals).
virtual bool compatibleWithBooleanRewrite () const override
 No semiring homomorphism BoolFunc(X) →+* ℕ exists: any such map would force 1 + a = 1 in ℕ (from var + 1 = 1 in BoolFunc), contradicting the non-absorptivity of ℕ.
value_type parse_leaf (const char *v) const
Public Member Functions inherited from semiring::Semiring< unsigned >
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 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 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 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 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.

Static Public Attributes

static constexpr value_type INFINITE = std::numeric_limits<value_type>::max()
 \(\infty\): the count of a tuple derived through a cycle.

Additional Inherited Members

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

Detailed Description

The counting semiring over unsigned.

Each gate evaluates to the number of distinct derivations of the corresponding sub-formula.

Definition at line 42 of file Counting.h.

Member Function Documentation

◆ compatibleWithBooleanRewrite()

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

No semiring homomorphism BoolFunc(X) →+* ℕ exists: any such map would force 1 + a = 1 in ℕ (from var + 1 = 1 in BoolFunc), contradicting the non-absorptivity of ℕ.

The safe-query Boolean rewrite is therefore unsound under the counting semiring (read-once factoring loses derivation multiplicities). Inherits the false default from Semiring; this override exists for documentation.

Lean: Provenance.Semirings.Nat.no_hom_from_BoolFunc (provenance-lean/Provenance/Semirings/Nat.lean).

Reimplemented from semiring::Semiring< unsigned >.

Definition at line 132 of file Counting.h.

◆ delta()

virtual value_type semiring::Counting::delta ( value_type x) const
inlineoverridevirtual

Apply the \(\delta\) operator.

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

Implements semiring::Semiring< unsigned >.

Definition at line 99 of file Counting.h.

◆ exclusive()

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

Exclusive: \(a \otimes (\mathbb{1} \ominus a) = \mathbb{0}\) (Lean Nat.exclusive); \(\otimes\) is not idempotent (Nat.not_mulIdempotent).

Reimplemented from semiring::Semiring< unsigned >.

Definition at line 106 of file Counting.h.

◆ has_star()

virtual bool semiring::Counting::has_star ( ) const
inlineoverridevirtual

\(0^* = 1\); any other count repeats without end.

Reimplemented from semiring::Semiring< unsigned >.

Definition at line 93 of file Counting.h.

◆ monus()

virtual value_type semiring::Counting::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< unsigned >.

Definition at line 86 of file Counting.h.

◆ mul_sub_left_distributive()

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

\(\otimes\) distributes over \(\ominus\) (truncated subtraction on the naturals).

Recorded for completeness: the HAVING single-scan closed form also needs absorptivity, which the counting semiring lacks.

Lean: Provenance.Semirings.Nat.mul_sub_left_distributive.

Reimplemented from semiring::Semiring< unsigned >.

Definition at line 117 of file Counting.h.

◆ one()

virtual value_type semiring::Counting::one ( ) const
inlineoverridevirtual

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

Returns
The one element of the semiring.

Implements semiring::Semiring< unsigned >.

Definition at line 53 of file Counting.h.

◆ parse_leaf()

value_type semiring::Counting::parse_leaf ( const char * v) const
inline

Definition at line 135 of file Counting.h.

◆ plus()

virtual value_type semiring::Counting::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< unsigned >.

Definition at line 56 of file Counting.h.

◆ star()

virtual value_type semiring::Counting::star ( const value_type & a) const
inlineoverridevirtual

\(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 from semiring::Semiring< unsigned >.

Definition at line 96 of file Counting.h.

◆ times()

virtual value_type semiring::Counting::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< unsigned >.

Definition at line 69 of file Counting.h.

◆ zero()

virtual value_type semiring::Counting::zero ( ) const
inlineoverridevirtual

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

Returns
The zero element of the semiring.

Implements semiring::Semiring< unsigned >.

Definition at line 50 of file Counting.h.

Member Data Documentation

◆ INFINITE

value_type semiring::Counting::INFINITE = std::numeric_limits<value_type>::max()
staticconstexpr

\(\infty\): the count of a tuple derived through a cycle.

\(0 \cdot \infty = 0\), and \(\infty\) absorbs every other sum and product. A finite count reaching it is an overflow, refused.

Definition at line 48 of file Counting.h.


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