Module com.darkcollective.relix.provenance
Package com.darkcollective.relix.provenance

Interface Semiring<K>

Type Parameters:
K - the annotation type carried by each tuple
All Known Implementing Classes:
BooleanSemiring, CountingSemiring, PathCostSemiring, PolynomialSemiring, SecurityLattice, TropicalSemiring
public interface Semiring<K>
A commutative semiring (K, ⊕, ⊗, 0, 1) — the pluggable extension point of the provenance / K-relation framework.

In a K-relation every tuple is annotated with an element of K, and each positive-algebra operator is defined by these operations: union and projection combine alternative derivations with ⊕; join and product combine joint requirements with ⊗; selection multiplies a tuple's annotation by 1 (keep) or 0 (drop); and the annotation 0 means the tuple is absent. Choosing the semiring chooses the feature — existence, multiplicity, lineage, trust level, or shortest path — without changing any operator code.

An implementation must satisfy the commutative-semiring laws for every a, b, c ∈ K:

  • ⊕ is associative and commutative, with identity 0: plus(a, zero()) == a;
  • ⊗ is associative and commutative, with identity 1: times(a, one()) == a;
  • 0 annihilates ⊗: times(a, zero()) == zero();
  • ⊗ distributes over ⊕: times(a, plus(b, c)) == plus(times(a, b), times(a, c)).

Implementations are expected to be immutable and stateless (the built-ins are singletons). Equality is by the annotation values of K, not by the Semiring instance.

See Also:

  • Method Summary

    Modifier and Type
    Method
    Description
    default K
    base(BaseTuple tuple)
    Returns the annotation a base tuple lifts to.
    K
    one()
    Returns the multiplicative identity 1.
    K
    plus(K a, K b)
    Combines two annotations with ⊕ — the way alternative derivations of the same tuple (union, projection) are merged.
    K
    times(K a, K b)
    Combines two annotations with ⊗ — the way the joint requirements of a tuple (join, product) are merged.
    K
    zero()
    Returns the additive identity 0.

  • Method Details

    • zero

      K zero()
      Returns the additive identity 0. It is the identity of plus(K, K) and the annihilator of times(K, K), and denotes an absent tuple.
      Returns:
      the additive identity 0

    • one

      K one()
      Returns the multiplicative identity 1. It is the identity of times(K, K).
      Returns:
      the multiplicative identity 1

    • plus

      K plus(K a, K b)
      Combines two annotations with ⊕ — the way alternative derivations of the same tuple (union, projection) are merged. Associative and commutative, with identity zero().
      Parameters:
      a - the first annotation
      b - the second annotation
      Returns:
      a ⊕ b

    • times

      K times(K a, K b)
      Combines two annotations with ⊗ — the way the joint requirements of a tuple (join, product) are merged. Associative and commutative, with identity one(), annihilated by zero().
      Parameters:
      a - the first annotation
      b - the second annotation
      Returns:
      a ⊗ b

    • base

      default K base(BaseTuple tuple)
      Returns the annotation a base tuple lifts to. This is how a semiring reads the data: the engine hands over each leaf tuple and the semiring says what it is worth.

      The default lifts every base tuple to one(), which is correct for any semiring whose annotation does not depend on the data — boolean existence and the security lattice, whose answers are decided entirely by how derivations combine. Override it to read BaseTuple.weight() (a cost, a multiplicity, a probability) or to mint a per-occurrence token from BaseTuple.source() and BaseTuple.ordinal() (a route, a lineage variable).

      A semiring that reads a weight must decide for itself what an absent one means, because the two defensible answers differ: one() leaves the tuple neutral, while a fixed constant makes an unweighted graph a defined special case rather than a degenerate one.

      Parameters:
      tuple - the base tuple; never null
      Returns:
      the tuple's base annotation; never null