You have built five annotation systems with five propagation rules. They are the same shape. This chapter shows why, and collapses them into one framework.
By now you have implemented five annotations — completeness, additivity, grain, confidence, and guarantee — each with a composition rule for joins, a rule for projections, and a gate for aggregation. If you look at the code, you will notice they share a structure: an element per tuple (or per result set), a way to combine elements when tuples meet in a join, and a “zero” element that kills the result.
This is not a coincidence. There is a framework from 2007 that explains it, and using it will let you replace five hand-written propagators with one generic evaluator parameterized by an algebra. The framework is provenance semirings (Green, Karvounarakis and Tannen, PODS 2007).
A commutative semiring \((K, +, \cdot, 0, 1)\) is a set \(K\) with two operations:
That’s it. No subtraction required (it’s a semiring). The natural numbers \((\mathbb{N}, +, \cdot, 0, 1)\) are the canonical example.
Annotate each tuple in a base relation with an element of \(K\). Then evaluate the query using the relational operations, with the annotations following along:
| Relational operation | Annotation operation | Intuition |
|---|---|---|
| Union (alternative ways to derive a tuple) | \(+\) (add the annotations) | “This tuple can be derived via path A or path B” |
| Join (combine tuples from different sources) | \(\cdot\) (multiply the annotations) | “This tuple requires both inputs” |
| Tuple not derivable | \(0\) | “This tuple doesn’t exist in the result” |
| Base tuple with no restriction | \(1\) | “This tuple is unconditionally present” |
Algebraic uniformity
The same relational evaluation machinery produces different things when you change the semiring:
Annotate with polynomials once, and specialize the same annotation into multiplicity, or clearance level, or confidence, or cost, as needed.
Let’s map each of our annotations to the semiring framework:
Both union and join take the meet (weakest wins). This is a degenerate semiring where addition and multiplication are the same operation — a bounded semilattice. That’s fine; lattices are semirings.
When a tuple can be derived via two paths (union), take the more confident one (max). When it requires both inputs (join), take the less confident one (min). Zero means “no confidence at all.” One means “deterministic.”
This is the tropical max-min semiring (also called the Viterbi semiring in the provenance literature), and it is exactly our confidence propagation rule from Chapter 4.
Another lattice-as-semiring. This is exactly the access control semiring from Karvounarakis and Green’s 2012 survey: annotations are clearance levels, and a view for a user at level \(c\) contains exactly the tuples at level \(c' \le c\).
Grain doesn’t fit the semiring framework as cleanly. Grain is a property of the result set, not of individual tuples. It interacts with the semiring through a side condition: before applying aggregation, check that the result-set grain is compatible with the measure’s declared grain. This is a guard rather than a propagated annotation.
Similarly, additivity is a property of measures (columns in the schema), not of tuples. It interacts with the query plan through the same guard mechanism: before applying an aggregation function, check that the function is compatible with the measure’s additivity class.
So of our five annotations, three are true semiring instances (completeness, confidence, guarantee) and two are type-level guards (grain, additivity). The semiring framework unifies the first three; the guard mechanism handles the other two. This is cleaner than five completely independent systems.
from abc import ABC, abstractmethod
from typing import TypeVar, Generic
K = TypeVar("K")
class Semiring(ABC, Generic[K]):
@abstractmethod
def zero(self) -> K: ...
@abstractmethod
def one(self) -> K: ...
@abstractmethod
def plus(self, a: K, b: K) -> K:
"""Union: alternative derivations."""
...
@abstractmethod
def times(self, a: K, b: K) -> K:
"""Join: combined requirements."""
...
def is_zero(self, a: K) -> bool:
return a == self.zero()
class ConfidenceSemiring(Semiring[float]):
def zero(self) -> float:
return 0.0
def one(self) -> float:
return 1.0
def plus(self, a: float, b: float) -> float:
return max(a, b) # best alternative
def times(self, a: float, b: float) -> float:
return min(a, b) # weakest link
class CompletenessLevel:
EXACT = 4; SAMPLED = 3; TOP_K = 2; TRUNCATED = 1; UNKNOWN = 0
class CompletenessSemiring(Semiring[int]):
def zero(self) -> int:
return CompletenessLevel.UNKNOWN
def one(self) -> int:
return CompletenessLevel.EXACT
def plus(self, a: int, b: int) -> int:
return min(a, b) # weakest wins
def times(self, a: int, b: int) -> int:
return min(a, b) # weakest wins
class AnnotatedTuple(Generic[K]):
"""A tuple carrying a semiring annotation."""
def __init__(self, data: dict, annotation: K):
self.data = data
self.annotation = annotation
def join(self, other: "AnnotatedTuple[K]", semiring: Semiring[K]) -> "AnnotatedTuple[K]":
merged_data = {**self.data, **other.data}
merged_ann = semiring.times(self.annotation, other.annotation)
return AnnotatedTuple(merged_data, merged_ann)
def annotated_join(left: list[AnnotatedTuple[K]],
right: list[AnnotatedTuple[K]],
key: str,
semiring: Semiring[K]) -> list[AnnotatedTuple[K]]:
"""Join two annotated relations on a shared key."""
result = []
right_index = {}
for r in right:
right_index.setdefault(r.data[key], []).append(r)
for l in left:
for r in right_index.get(l.data[key], []):
joined = l.join(r, semiring)
if not semiring.is_zero(joined.annotation):
result.append(joined)
return result
The same annotated_join function, instantiated with ConfidenceSemiring(), propagates confidence. Instantiated with CompletenessSemiring(), it propagates completeness. One implementation, multiple semantics.
In practice, you want to carry all annotations simultaneously. The product of semirings is itself a semiring:
\[ (K_1 \times K_2 \times K_3, +_\times, \cdot_\times, (0_1, 0_2, 0_3), (1_1, 1_2, 1_3)) \]where operations are applied component-wise. This means you can define:
@dataclass(frozen=True)
class FullAnnotation:
completeness: int
confidence: float
guarantee: int
def times(self, other: "FullAnnotation") -> "FullAnnotation":
return FullAnnotation(
completeness=min(self.completeness, other.completeness),
confidence=min(self.confidence, other.confidence),
guarantee=min(self.guarantee, other.guarantee),
)
def plus(self, other: "FullAnnotation") -> "FullAnnotation":
return FullAnnotation(
completeness=min(self.completeness, other.completeness),
confidence=max(self.confidence, other.confidence),
guarantee=min(self.guarantee, other.guarantee),
)
def is_zero(self) -> bool:
"""Any component at zero means the tuple is dead."""
return (self.completeness == 0 or
self.confidence == 0.0 or
self.guarantee == 0)
The zero element is reached when any component hits its zero. This is the right behavior: a tuple that has zero confidence, OR unknown completeness, OR no authorization guarantee, should be treated as absent from the result.
A tuple is derived from two base tuples via a join. The left tuple has annotation (exact, 0.95, full). The right has (top_k, 1.0, partial). What is the joined tuple’s annotation? Is it usable in a negation (anti-join)?
Apply times component-wise: completeness = min(exact, top_k) = top_k. Confidence = min(0.95, 1.0) = 0.95. Guarantee = min(full, partial) = partial. Result: (top_k, 0.95, partial). Not usable in negation: guarantee is partial, and the negation gate requires full.
There is a known limitation, and it lands exactly where you’d expect.
Semiring provenance does not handle set difference cleanly (Geerts, Poggi and Tannen, TaPP 2013). The reason: difference is negation, and negation requires an additive inverse (\(-x\) such that \(x + (-x) = 0\)), which a semiring by definition does not have. You would need a ring, not a semiring.
This is not a technicality. It is exactly where the permission model broke in Chapter 5. Anti-joins (set difference) over partially-visible data fabricate absences. The formal framework and the practical failure mode break at precisely the same operator.
The engineering consequence: set difference is handled by the guard mechanism, not by the semiring. Before computing a difference, the validator checks the guarantee annotation on both inputs. If either is not full, the operation is rejected. This is not elegant — it’s a special case. But it is correct, and the alternative (extending to a full ring) requires negative annotations whose semantics for access control are unclear.
Why not a ring?
A ring adds additive inverses: for every \(x\), there exists \(-x\) with \(x + (-x) = 0\). For bag semantics, this would mean negative multiplicities (tuples that “cancel out” other tuples). For access control, it would mean... what? A clearance level that cancels another clearance level? The semantics become unclear.
The provenance community’s solution: define difference only for specific semirings where it makes sense (e.g., the integers, where bag-difference is subtraction), and leave it undefined for others. Our solution: reject difference unless the guard conditions are met. Same outcome, different framing.
The complete picture of how annotations flow through a query plan:
class AnnotatedEvaluator:
def __init__(self, semiring: Semiring, guards: list[Guard]):
self.semiring = semiring
self.guards = guards
def evaluate(self, plan: QueryPlan) -> AnnotatedResult:
match plan:
case Scan(table, annotations):
return self.scan(table, annotations)
case Join(left, right, key):
l = self.evaluate(left)
r = self.evaluate(right)
return self.join(l, r, key)
case Union(left, right):
l = self.evaluate(left)
r = self.evaluate(right)
return self.union(l, r)
case Difference(left, right):
l = self.evaluate(left)
r = self.evaluate(right)
# GUARD: check before computing
for guard in self.guards:
error = guard.check_difference(l, r)
if error:
return Rejection(error)
return self.difference(l, r)
case Aggregate(input, function, groups):
inp = self.evaluate(input)
# GUARD: check aggregation legality
for guard in self.guards:
error = guard.check_aggregation(inp, function, groups)
if error:
return Rejection(error)
return self.aggregate(inp, function, groups)
def join(self, left, right, key):
# Semiring multiplication on annotations
return annotated_join(left.tuples, right.tuples, key, self.semiring)
The pattern: semirings propagate, guards reject. The semiring handles the smooth, compositional cases (join, union, projection). The guards handle the discontinuous cases (aggregation legality, negation soundness) where the operation must be blocked rather than annotated.
Verify that the confidence semiring \(([0,1], \max, \min, 0, 1)\) satisfies the semiring axioms: (1) \(\max\) is commutative and associative with identity 0; (2) \(\min\) is commutative and associative with identity 1; (3) \(\min\) distributes over \(\max\); (4) \(\min(0, x) = 0\) for all x. Which of these is hardest to verify?
(1) \(\max(a,b) = \max(b,a)\) ✓. \(\max(a, \max(b,c)) = \max(\max(a,b),c)\) ✓. \(\max(a, 0) = a\) ✓. (2) \(\min(a,b) = \min(b,a)\) ✓. Associativity ✓. \(\min(a, 1) = a\) ✓. (3) Distributivity: \(\min(a, \max(b,c)) = \max(\min(a,b), \min(a,c))\). This is the hardest — verify by cases: if \(a \le b \le c\), LHS = \(a\), RHS = \(\max(a, a) = a\) ✓. If \(b \le a \le c\), LHS = \(a\), RHS = \(\max(b, a) = a\) ✓. If \(b \le c \le a\), LHS = \(c\), RHS = \(\max(b, c) = c\) ✓. (4) \(\min(0, x) = 0\) ✓ since 0 is the minimum of [0,1]. All four hold.
ProductSemiring that carries completeness, confidence, and guarantee simultaneously. Implement annotated_join and annotated_union using the product semiring, and verify that the results match your earlier per-annotation implementations on the same test cases.AnnotatedEvaluator with two guards: (a) the negation guard (rejects anti-join when guarantee is not full), and (b) the aggregation guard (rejects AVG over non-exact completeness, rejects SUM of non-additive measures). Run it against a 5-node query plan and show the rejection messages.