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

Enum Class PolynomialSemiring

java.lang.Object
java.lang.Enum<PolynomialSemiring>
com.darkcollective.relix.provenance.PolynomialSemiring
All Implemented Interfaces:
Semiring<Polynomial>, Serializable, Comparable<PolynomialSemiring>, Constable
public enum PolynomialSemiring extends Enum<PolynomialSemiring> implements Semiring<Polynomial>
The provenance-polynomial semiring ℕ[X] — full why-provenance (which input tuples produced a result, and how they were combined), after Green, Karvounarakis & Tannen (PODS 2007). It is the free commutative semiring on the set of provenance variables: the most informative annotation, from which every other semiring (count, boolean, trust, cost) is recovered by evaluating the polynomial under it.

Each base-tuple occurrence is lifted to its own variable x (a degree-one Polynomial). Then ⊕ is polynomial addition (alternative derivations become separate monomials, with like terms' coefficients added), and ⊗ is polynomial multiplication (a joint derivation multiplies its inputs' monomials and coefficients). 0 is the empty polynomial; 1 the constant polynomial 1.

Bounded representation (the degraded mode)

Polynomials can blow up — a dense join multiplies term counts. To stay bounded, every operation that would leave more than MAX_MONOMIALS distinct monomials keeps the smallest MAX_MONOMIALS of them (in Monomial's deterministic order) and marks the result truncated. Truncation is a sound under-approximation (the surviving terms are real derivations) and is contagious (any operation touching a truncated polynomial yields a truncated result).

Below the cap the full commutative-semiring contract holds. At and beyond it the two operations diverge, because capping is a selection and only one of them is one. ⊕ keeps the smallest MAX_MONOMIALS monomials of a union, and the smallest n of a union does not depend on how the union was bracketed — so ⊕ stays associative however far past the cap it goes. ⊗ caps each intermediate product, so which monomials survive depends on which pair was multiplied first, and (a ⊗ b) ⊗ c and a ⊗ (b ⊗ c) can select different terms. Both are sound under-approximations and both report truncated; they are simply not the same approximation.

Polynomial.truncated() is a record of the derivation rather than of the polynomial: it says some operation along the way hit the cap, so two polynomials with identical terms, reached by different routes, can disagree on it.

  • Enum Constant Details

  • Field Details

    • MAX_MONOMIALS

      public static final int MAX_MONOMIALS
      Maximum distinct monomials retained before a result is truncated.
      See Also:

  • Method Details

    • values

      public static PolynomialSemiring[] values()
      Returns an array containing the constants of this enum class, in the order they are declared.
      Returns:
      an array containing the constants of this enum class, in the order they are declared

    • valueOf

      public static PolynomialSemiring valueOf(String name)
      Returns the enum constant of this class with the specified name. The string must match exactly an identifier used to declare an enum constant in this class. (Extraneous whitespace characters are not permitted.)
      Parameters:
      name - the name of the enum constant to be returned.
      Returns:
      the enum constant with the specified name
      Throws:
      IllegalArgumentException - if this enum class has no constant with the specified name
      NullPointerException - if the argument is null

    • variable

      public static Polynomial variable(String name)
      Returns the single-variable polynomial x. Convenience for the lift of a base-tuple occurrence to its provenance variable.
      Parameters:
      name - the variable label (by convention <relation>#<ordinal>)
      Returns:
      the single-variable polynomial x

    • variable

      public static Polynomial variable(SourceRef ref)
      Returns the single-variable polynomial x for a structured source. The lift of a base-tuple occurrence to its provenance variable, carrying the occurrence's captured columns so the lineage is machine-actionable.
      Parameters:
      ref - the structured source identity; never null
      Returns:
      the single-variable polynomial x for a structured source

    • zero

      public Polynomial zero()
      Description copied from interface: Semiring
      Returns the additive identity 0. It is the identity of Semiring.plus(K, K) and the annihilator of Semiring.times(K, K), and denotes an absent tuple.
      Specified by:
      zero in interface Semiring<Polynomial>
      Returns:
      the additive identity 0

    • one

      public Polynomial one()
      Description copied from interface: Semiring
      Returns the multiplicative identity 1. It is the identity of Semiring.times(K, K).
      Specified by:
      one in interface Semiring<Polynomial>
      Returns:
      the multiplicative identity 1

    • plus

      public Polynomial plus(Polynomial a, Polynomial b)
      Description copied from interface: Semiring
      Combines two annotations with ⊕ — the way alternative derivations of the same tuple (union, projection) are merged. Associative and commutative, with identity Semiring.zero().
      Specified by:
      plus in interface Semiring<Polynomial>
      Parameters:
      a - the first annotation
      b - the second annotation
      Returns:
      a ⊕ b

    • times

      public Polynomial times(Polynomial a, Polynomial b)
      Description copied from interface: Semiring
      Combines two annotations with ⊗ — the way the joint requirements of a tuple (join, product) are merged. Associative and commutative, with identity Semiring.one(), annihilated by Semiring.zero().
      Specified by:
      times in interface Semiring<Polynomial>
      Parameters:
      a - the first annotation
      b - the second annotation
      Returns:
      a ⊗ b

    • base

      public Polynomial base(BaseTuple tuple)
      Returns a fresh variable standing for this base-tuple occurrence. Lineage is the one built-in semiring that reads a tuple's identity rather than its weight: the variable is named <source>#<ordinal> and carries that occurrence's column values, which is what makes it addressable back to the row that produced it rather than merely nameable.
      Specified by:
      base in interface Semiring<Polynomial>
      Parameters:
      tuple - the base tuple; never null
      Returns:
      a fresh variable standing for this base-tuple occurrence