Every Data System That Won Was a One-Line Algebra Bet

There is a story no one tells about data infrastructure. Not the engineering story — everyone tells that one. The mathematical story. Every system that defined an era made a single algebraic commitment. The commitment determined what the system could guarantee. Everything else — the APIs, the ecosystem, the vendor pitch — was a consequence.

Here is the story, told correctly.

Relational Model (1970): Closed algebra over multisets → arbitrary query composition

Excel (1985): DAG + topological sort → reactive dataflow on a single machine

MapReduce (2004): Commutative monoid → fault-tolerant horizontal scaling

BigTable (2006): Injective map (row, col, t) → value → versioned sparse storage without joins

Provenance Semirings (2007): Semiring over derivation polynomials → auditable lineage of every output tuple

Dremel (2010): Bijection: nested record ↔ columnar encoding → lossless shredding of semi-structured data

Kafka (2011): Totally ordered append-only log → exactly-once replay and distributed state recovery

Spark (2012): Join semi-lattice + pure-function lineage DAG → recomputation replaces replication

DBSP (2022): Abelian group with differentiation operator D → stream processing becomes calculus

Read the table vertically. Each row is a generation choosing one algebraic property and sacrificing the others.

Codd chose closure: the result of any query on relations is a relation. This made composition free. It also assumed a single machine.

The moment data crossed machine boundaries, closure broke. MapReduce recovered correctness by restricting computation to a commutative monoid — associativity lets you regroup across partitions, commutativity lets you ignore arrival order. Fault tolerance fell out of the algebra. What you lost: iteration, joins, multi-step state. Dean and Ghemawat traded expressiveness for a proof that partial failures cannot corrupt results.

Excel is the system no one puts in this lineage, which is an error. The recalculation engine is a dependency DAG with topological sort — a reactive dataflow computer deployed to a billion machines three decades before “dataflow” entered the distributed systems vocabulary. Every cell is a node. Every formula is an edge. Dirty-flag propagation through topological order is incremental computation. DBSP is, in a precise sense, the mathematical completion of what Excel started heuristically.

Spark’s move was subtle. RDDs are elements of a join semi-lattice — immutable, partially ordered by a lineage DAG of pure functions. Purity gives idempotency. Idempotency gives free recomputation. Zaharia’s insight: if the lineage graph is the recovery mechanism, you never need to write intermediate state to disk. This recovered iteration without surrendering fault tolerance.

BigTable and Dremel made dual bets. BigTable chose an injective map — the three-tuple key guarantees every value is uniquely addressable, which makes range scans and versioning natural but renders joins structurally inexpressible. Dremel inverted the problem: a bijection between nested records and flat columnar encodings (via repetition and definition levels) that is provably lossless. The guarantee is reconstruction — you can always reassemble the original record from its shredded columns.

Kafka’s contribution was recognizing that a total order is the minimal structure for exactly-once semantics. An append-only log with monotonic offsets makes replay deterministic. Kreps did not invent the log. He identified its algebraic sufficiency for distributed state synchronization.

The provenance semirings of Green, Karvounarakis, and Tannen (PODS 2007) are the least known and most important entry in the table. They annotate each output tuple not with a boolean (”is this in the result?”) but with a polynomial in a semiring that records every derivation path. This is the algebraic structure for why, not just what — the foundation of explainable data pipelines. Almost no one outside the database theory community has read this paper. Almost everyone building ML pipelines needs it.

DBSP — Database Stream Processor — is the current frontier. It is a theory and runtime for incremental view maintenance: the problem of keeping a materialized query result up to date as the underlying data changes, without recomputing from scratch. Budiu, Chajed, McSherry, Ryzhyk, and Tannen (VLDB 2023) observed that if your data values live in an abelian group — meaning addition has inverses, so deletions are negative insertions — you can define a differentiation operator D over streams, where D(s)t = s_t − s{t−1}. The update to a query’s output is the derivative of the query applied to the update of its input. Incremental view maintenance becomes the chain rule. This is not a metaphor. It is a formal isomorphism between stream processing and differential calculus over groups.

The pattern is not progress. It is trade-offs made explicit through algebra.

Every generation chose one property to enforce and paid for it by surrendering another. Closure but not distribution. Distribution but not composition. Composition but not incrementality. Incrementality but not provenance.

The history of data systems is not a history of engineering. It is a history of which algebraic guarantee you were willing to pay for.