Package com.darkcollective.relix.provenance
A K-relation annotates every tuple with an element of a commutative
semiring (K, ⊕, ⊗, 0, 1); each positive-algebra operator is then defined
by the semiring operations — union/projection combine alternative derivations
with ⊕, join/product combine joint requirements with ⊗,
selection multiplies by 1 (keep) or 0 (drop), and 0
means "absent". Choosing the semiring chooses the feature: set semantics, bag
multiplicity, why-provenance lineage, security/trust levels, and
shortest-path / weighted closure all fall out of one mechanism.
This package provides the Semiring
extension point and the cheap fixed-size built-ins
(BooleanSemiring,
CountingSemiring,
TropicalSemiring,
SecurityLattice). It is the algebra
only — threading the annotations through the relix operators is
relix-processor's job.
- See Also:
-
ClassDescriptionA base tuple as a
Semiringcan read it — the engine's row reduced to the two things an annotation can be built from: which tuple this is, and what it weighs.The boolean semiring(𝔹, ∨, ∧, false, true)— plain set semantics (a tuple is present or absent).The counting semiring(ℕ, +, ×, 0, 1)— bag semantics (row multiplicity) and, over a weighted closure, path counting.A monomial in the polynomial-lineage semiringℕ[X]— a product ofprovenance variableswith positive integer exponents (a multiset of variables).ASemiringtogether with the names it answers to and a line describing it — one entry in the registry a--provenancerequest is resolved against.An element of the cheapest-route semiringPathCostSemiring— a path's minimumcostand the set of co-cheapestroutesthat achieve it.The cheapest-route semiring((ℝ ∪ {+∞}) × ℘(Route), ⊕, ⊗, (+∞, ∅), (0, {ε}))— the combined cost-and-witness algebra: a single weighted closure run carries both a path's cheapest cost and the route(s) achieving it.A provenance polynomial — an element of the lineage semiringℕ[X].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).A provenance variable — the token identifying one base-tuple occurrence in the polynomial-lineage semiringℕ[X](after Green, Karvounarakis & Tannen, PODS 2007).One derivation (path) carried by the cheapest-route semiringPathCostSemiring— the set of edge tokens traversed.The security / access-control lattice semiring overSecurityLevel(min, max)— propagates a confidentiality (clearance) level through a query so each output tuple carries the level at which it may be released.A confidentiality / clearance level, ordered from least to most restrictive — the carrier of theSecurityLatticesemiring.Semiring<K>A commutative semiring(K, ⊕, ⊗, 0, 1)— the pluggable extension point of the provenance / K-relation framework.Which semirings are installed — the bundled six plus every one a discoveredSemiringLibraryoffers, resolved by name.A provider of semirings — the extension point through which an annotation algebra the engine has never heard of becomes something a query can ask for by name.Resolves aSemiringby name — the lookup the surfacing layer uses to turn a--provenance=<name>request into a concrete semiring without the caller hard-wiring the singletons.A structured, machine-readable identity for one base-tuple occurrence — the data aProvenanceVariablecarries so a consuming tool can pinpoint which row of which relation a lineage variable stands for.The tropical (min-plus) semiring(ℝ ∪ {+∞}, min, +, +∞, 0)— the cheapest-derivation algebra, i.e.