The algebra of citations (Foundations, part 7)
Part 7 of Foundations: why every answer — even a computed one — can carry its receipts, and the theory that guarantees it.
Citations are easy when the answer is one stored fact: point at the fact. They get interesting when the answer is computed — a count, a set intersection, an "earliest," a roll-up across a whole document. What does it even mean to cite a number you derived from forty facts? Most systems answer: nothing. Here's the number. The provenance evaporates exactly when the answer got complicated enough to need it.
Database theory got there first — again. Green, Karvounarakis, and Tannen (2007) unified years of lineage research with one beautiful move: tag every base fact, define how tags combine when facts are joined (both were needed) and when alternatives union (either sufficed), and query answers come out annotated with polynomials over their sources. They called it the provenance semiring framework. The polynomial is the citation — it says which facts contributed and how: jointly or alternatively, once or repeatedly.
Here's the part that matters for building: this composes through any computation assembled from the right algebraic pieces. Filters, joins, unions, aggregations — define each one as a structure-preserving map and provenance threads through automatically. Citations stop being a per-feature chore you can forget. They become a property of the algebra. You can't forget to implement citations for your new operation, because the operation's definition is its citation behavior. I love results like this — the kind where doing it right is also doing it once.
What it looks like from the outside
Ask "how many distinct cities did I visit in 2024?" and you get: 7 — from these 11 mentions, deduplicated to these 7 identities, each with its source span. Ask
an intersection — "films that won Best Picture and are in my watchlist" — and
every member arrives with both justifications. Ask something long and
compositional and the evidence comes back as a tree: each step citing the step
below it, all the way down to bytes in your documents.
Two working rules keep the receipts real instead of decorative:
No anonymous merging. Whenever facts combine, the result keeps back-pointers to its contributors. A deduplicated set remembers what it deduplicated. A "latest value" remembers what it superseded. And then a mechanical check enforces it — every merge either carries its contributors or explicitly justifies why not. Trust the algebra, verify the code.
Bounded work is labeled work. Real systems cap searches for speed. Fine — but a cap may bound effort, never truth. If a scan got cut short, the result says so. An incomplete search can never dress up as "searched everything, found nothing." A citation that silently omits "…as far as I looked" isn't a citation.
Notice how this snaps together with part 3: certain answers tell you when you may speak. Provenance polynomials are what you hand over when you do. Honesty about whether; receipts for what. The math has been sitting there since 2007, waiting for memory systems to take it literally. So we did.