Part 7 of Foundations: how computed answers can retain their receipts, and where the underlying theory has boundaries.
Citations are easy when the answer is one stored fact. You point at the fact and you are done. 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? Returning the bare number is easy. Retaining the derivation through a more complicated computation takes deliberate design.
By the mid-2000s this had become a small mess. Several groups had built provenance machinery, and they did not agree: one tracked which source tuples witnessed a result, another which locations a value was copied from, others propagated confidence scores or counted derivations. Each was reasonable. Each had its own formalism. Nobody could say how they related.
Todd Green, Grigoris Karvounarakis and Val Tannen resolved that in 2007 with provenance semirings, and the resolution is the kind that makes you sit back. The competing notions were not rivals at all. They were the same construction run at different settings. A semiring, in case the word is new to you, is a set with two operations that behave like addition and multiplication and cooperate the way you would hope; the details matter less than what you can do with one. Annotate each base fact with an element of a semiring, propagate the annotations through the query, and which semiring you pick decides which flavour of provenance falls out. Confidence, counting, witnesses, lineage. One mechanism, several dials.
The core idea is book-keeping. Tag each base fact. When facts are used together, combine their tags the multiplicative way; when two different derivations would each suffice, combine them the additive way. For the relational positive-query setting in the paper, answers can be annotated with polynomials over their sources: a compact account of derivation structure. A polynomial is not, by itself, a reader-facing bibliography, and it says nothing about whether the source is trustworthy.
That qualification matters. The base semiring treatment covers a specific query class. Aggregation, difference, recursion, and other operations need additional semantics, and later work provides several extensions rather than one universal answer. For a product, every supported operation therefore needs an explicit provenance contract and tests that its implementation honors that contract.
It also matters that "provenance" is not one thing. Peter Buneman, Sanjeev Khanna and Wang-Chiew Tan's earlier why-and-where characterization drew a distinction that is easy to lose in a product conversation: why provenance identifies the witnesses that justify a result, while where provenance identifies the locations a value was copied from. James Cheney, Laura Chiticariu and Wang-Chiew Tan's survey lays why, how and where against each other in full.
That taxonomy is worth carrying around, because a user asking "where did this come from?" is usually asking a why question and will be dissatisfied by a where answer. And when the real question is "how do I know that follows?", neither will do. That one wants how-provenance, the derivation itself, which is the strictest of the three and the one a proof-carrying answer has to supply. Pointing at the cell a number was copied out of is not the same as showing what made the number correct. A system that returns the first while sounding like it returned the second is being subtly dishonest.
From derivation to interface#
Here is an illustrative question to make that concrete: "How many distinct cities did I visit in 2024?" A clear response would connect the count to the deduplicated identities, and each identity to the mentions that supported it. For an intersection such as "films that won Best Picture that are also in my watchlist," each result needs evidence for both conditions. The visual below shows that intended evidence shape. It is an illustration, not a benchmark result or a screenshot of the unreleased product.
Two working rules keep the receipts real instead of decorative.
No anonymous merging. When claims combine, the result should retain a derivation link to its contributors. A deduplicated set needs a record of the mentions it collapsed; a selected current value needs a record of the alternatives or prior versions considered. In CleverMemory this is a design requirement that is in validation, not a public claim that every operation has already passed that gate.
Bounded work must be labeled. Real systems cap searches, and a cap on effort cannot establish corpus-wide absence. If a search was incomplete, its status belongs in the result. Otherwise a correct citation to the inspected evidence can still support an incorrect claim about everything that was searched.
This connects back to part 3: certain-answer semantics addresses when the evidence warrants an answer, while provenance explains how the supporting derivation can travel with it. CleverMemory draws on both ideas. Each supported operation has a provenance contract and tests that exercise it.
The target is worth stating plainly, because it is the whole reason for the algebra: an answer should retain its exact evidence and where that evidence came from, not a paraphrase of them and not a pointer that has drifted. A citation that survives a join is the difference between a system that can show its work and one that can only assure you it did some.
Next: the page itself. Why the row, column, and heading around a number are part of what the number claims, and what gets deleted when a document is flattened to plain text.