Semiring.h File Reference

Abstract semiring interface for provenance evaluation. More...

#include <vector>
#include <string>
#include "../Aggregation.h"

Include dependency graph for Semiring.h:

This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Classes
class	semiring::SemiringException
	Exception thrown when a semiring operation is not supported. More...
class	semiring::Semiring< V >
	Abstract base class for (m-)semirings. More...

Namespaces
namespace	semiring

Detailed Description

Abstract semiring interface for provenance evaluation.

ProvSQL evaluates provenance circuits over arbitrary (m-)semirings. This header defines the abstract base class semiring::Semiring<V> that every concrete semiring must implement.

A semiring \((S, \oplus, \otimes, \mathbb{0}, \mathbb{1})\) consists of:

• A carrier set \(S\) (the value_type).
• An additive operation \(\oplus\) with identity \(\mathbb{0}\).
• A multiplicative operation \(\otimes\) with identity \(\mathbb{1}\).

An m-semiring additionally provides:

• A monus operation \(\ominus\) used for set-difference queries.
• A \(\delta\) operator.

Optional operations (comparison, semimodule scalar multiplication, aggregation, and value literals) are provided by subclasses that support them; the base class throws SemiringException for all of these.

Concrete implementations live in the same semiring/ directory: Boolean.h, Counting.h, Formula.h, Why.h, BoolExpr.h.

Definition in file Semiring.h.