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

Subsets of the labels of an enum type, as a 64-bit mask. More...

#include "Subset.h"

Inheritance diagram for semiring::Subset:
Collaboration diagram for semiring::Subset:

Public Types

enum class  Mode { SUBSET , CLEARANCE , CONSENT }
 How a mapping value is read (see the file comment). More...
Public Types inherited from semiring::Semiring< uint64_t >
typedef uint64_t value_type
 The carrier type of this semiring.

Public Member Functions

 Subset (Oid enum_type_oid, Mode mode_)
const std::vector< Oid > & label_oids () const
 The labels, in enumsortorder.
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 value_type delta (value_type x) const override
 Apply the \(\delta\) operator.
virtual bool absorptive () const override
 Return true if this semiring is absorptive ( \(\mathbb{1} \oplus a = \mathbb{1}\) for all \(a\)).
virtual bool exclusive () const override
 Return true if the semiring is exclusive: \(a \otimes (\mathbb{1} \ominus a) = \mathbb{0}\).
virtual bool mul_idempotent () const override
 Return true if \(\otimes\) is idempotent: \(a \otimes a = a\).
virtual bool mul_sub_left_distributive () const override
 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 override
 A Boolean algebra receives a homomorphism from the Boolean functions, so the safe-query rewriting is sound here.
value_type parse_leaf (const char *str) const
 Parse a mapping value: a single label, or an array of labels.
Public Member Functions inherited from semiring::Semiring< uint64_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.
virtual bool exact_equality () const
 Return true if equal decides equality of semiring elements.
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 uint64_t UNRESTRICTED = uint64_t(1) << 63
 The bit of the unrestricted world, in CONSENT mode.

Private Member Functions

uint64_t bit_of (Oid label) const

Private Attributes

Oid enum_oid
Mode mode
EnumLabels labels
uint64_t universe
Oid in_func
Oid array_in_func
Oid typioparam
Oid array_typioparam

Detailed Description

Subsets of the labels of an enum type, as a 64-bit mask.

Definition at line 95 of file Subset.h.

Member Enumeration Documentation

◆ Mode

enum class semiring::Subset::Mode
strong

How a mapping value is read (see the file comment).

Enumerator
SUBSET 
CLEARANCE 
CONSENT 

Definition at line 99 of file Subset.h.

Constructor & Destructor Documentation

◆ Subset()

semiring::Subset::Subset ( Oid enum_type_oid,
Mode mode_ )
inline

Definition at line 119 of file Subset.h.

Member Function Documentation

◆ absorptive()

virtual bool semiring::Subset::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< uint64_t >.

Definition at line 166 of file Subset.h.

◆ bit_of()

uint64_t semiring::Subset::bit_of ( Oid label) const
inlineprivate

Definition at line 111 of file Subset.h.

Here is the caller graph for this function:

◆ compatibleWithBooleanRewrite()

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

A Boolean algebra receives a homomorphism from the Boolean functions, so the safe-query rewriting is sound here.

Reimplemented from semiring::Semiring< uint64_t >.

Definition at line 180 of file Subset.h.

◆ delta()

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

Apply the \(\delta\) operator.

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

Implements semiring::Semiring< uint64_t >.

Definition at line 163 of file Subset.h.

◆ exclusive()

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

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 from semiring::Semiring< uint64_t >.

Definition at line 169 of file Subset.h.

◆ label_oids()

const std::vector< Oid > & semiring::Subset::label_oids ( ) const
inline

The labels, in enumsortorder.

Definition at line 140 of file Subset.h.

◆ monus()

virtual value_type semiring::Subset::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< uint64_t >.

Definition at line 160 of file Subset.h.

◆ mul_idempotent()

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

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 from semiring::Semiring< uint64_t >.

Definition at line 172 of file Subset.h.

◆ mul_sub_left_distributive()

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

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 from semiring::Semiring< uint64_t >.

Definition at line 175 of file Subset.h.

◆ one()

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

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

Returns
The one element of the semiring.

Implements semiring::Semiring< uint64_t >.

Definition at line 147 of file Subset.h.

◆ parse_leaf()

value_type semiring::Subset::parse_leaf ( const char * str) const
inline

Parse a mapping value: a single label, or an array of labels.

In CLEARANCE mode a single label stands for itself and every label above it; in CONSENT mode the unrestricted element is added to every value.

Definition at line 191 of file Subset.h.

Here is the call graph for this function:

◆ plus()

virtual value_type semiring::Subset::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< uint64_t >.

Definition at line 150 of file Subset.h.

◆ times()

virtual value_type semiring::Subset::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< uint64_t >.

Definition at line 155 of file Subset.h.

◆ zero()

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

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

Returns
The zero element of the semiring.

Implements semiring::Semiring< uint64_t >.

Definition at line 144 of file Subset.h.

Member Data Documentation

◆ array_in_func

Oid semiring::Subset::array_in_func
private

Definition at line 109 of file Subset.h.

◆ array_typioparam

Oid semiring::Subset::array_typioparam
private

Definition at line 109 of file Subset.h.

◆ enum_oid

Oid semiring::Subset::enum_oid
private

Definition at line 105 of file Subset.h.

◆ in_func

Oid semiring::Subset::in_func
private

Definition at line 109 of file Subset.h.

◆ labels

EnumLabels semiring::Subset::labels
private

Definition at line 107 of file Subset.h.

◆ mode

Mode semiring::Subset::mode
private

Definition at line 106 of file Subset.h.

◆ typioparam

Oid semiring::Subset::typioparam
private

Definition at line 109 of file Subset.h.

◆ universe

uint64_t semiring::Subset::universe
private

Definition at line 108 of file Subset.h.

◆ UNRESTRICTED

uint64_t semiring::Subset::UNRESTRICTED = uint64_t(1) << 63
staticconstexpr

The bit of the unrestricted world, in CONSENT mode.

Definition at line 102 of file Subset.h.


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