Chapter 5. What State Must Be
To make State concrete without choosing a preferred data model, this chapter derives three requirements from properties of the web itself.
The three requirements
R1 — Universality. The web hosts every application domain there is or will be. Therefore State must encode arbitrary application state, with no domain structure baked in. (Source: the observable web. Try to name the domain the web is “for.”)
R2 — Coordination-free composition. The web has no central schema authority, by design; decentralization is what “world wide” means. Therefore state must be composable across independent parties who have never communicated. Composition without coordination has laws: it must accept any two states (checking compatibility is coordinating), in any order (agreeing an order is coordinating), with duplicates costing nothing (tracking copies is coordinating). And it preserves meaning only if the things composed are self-contained. A fact must carry its full meaning with it, because no surrounding structure survives a merge. Those four laws leave exactly one composition. That composition is set union, and Appendix B proves it:
State = 𝒫(Fact) merge = ∪ (5.1)State is a set of atomic facts, and two states, from any two parties, anywhere, compose by union. Union is order-free, idempotent, associative, and commutative, so it has every property that federation needs.
R3 — Global reference. A fact on one site can be about an entity described on another; the web’s entire point is that things link. Therefore names inside facts need global scope. The web possesses exactly one global naming system (I, the URIs from Chapter 1), and inventing a second one would itself violate R2 (two parties’ private naming schemes collide on merge). So references in facts are drawn from I. R3 asks only for global names; nothing requires that they dereference. They can, though, and that comes free with the construction: the naming system and the web’s address system are one. Chapter 19 confronts what that identification costs.
The one bridge
The scope of R2’s result, before anything is built on it. The merge laws govern composition’s mechanics: that any two states merge, without permission, in any order, at no cost. They do not promise that merged facts join — that two parties’ names for one turbine ever meet in a query. No data model can promise that: parties who never communicated have agreed on nothing, in every model ever proposed, and a requirement pretending otherwise would be a coordinator in disguise. A model does control two things: what an unjoined union already holds, and what a join requires once someone demands one. Chapter 18 takes that up, where federation stops being algebra and becomes deployment. Here it is enough to be exact about what R2 secures. It secures merge, completely, and it does not secure meaning across sources.
The passage from “no coordinator” to the merge laws is the one bridge in the derivation — the deliberate exception the Preface mentioned. I name it the Transposition Thesis. The web already enforces four rules on documents: anyone links to anything without asking, content arrives by any path and in any order, copies cost nothing and change nothing, and aggregators consume content outside its original arrangement. The thesis is that, applied to data instead of documents, the same four rules become the four merge laws, one for one: totality, order-freedom, idempotence, atomicity (B-2a–d, defined in Appendix B). The table below lays out the correspondence so that each of the four pairs can be checked on its own. The same laws were also derived from an unrelated direction: distributed-systems research, needing replicas to converge without coordination, derived them as theorems — the CRDT (conflict-free replicated data type) literature. Two fields with different motives reached the same algebra, so the merge laws are not a matter of taste.
| the document layer, deployed | the state layer, transposed |
|---|---|
| anyone links to anything; no one is asked | composition is total — no compatibility check (B-2a) |
| content arrives by any path; intermediaries reorder it freely | composition is order-free (B-2b) |
| copies are free and unmarked; the cache hit is the resource | composition is idempotent (B-2c) |
| aggregators consume content outside its original arrangement, without its publisher’s consent | no meaning survives in arrangement (B-2d) |
Each left cell is deployed and citable — RFC 9111 carries the middle two, AWWW’s global-identifiers principle the first, and the last is every search engine and feed reader in operation. Each right cell is a numbered condition in Appendix B; B.4 proves none is redundant. Appendix D carries the CRDT citation. State-based replication requires a join-semilattice, which means totality, order-freedom, and idempotence. That literature derives those three properties from replication pressure alone. The theorem that follows applies to the web only to the extent that this table holds.
The smallest fact
The question now is the smallest self-contained fact, and “smallest” is not an aesthetic preference. Every extra position in a fact is one more thing independent parties must agree on, and agreement is what R2 forbids. So minimality is R2 again, applied to the shape of the fact itself. When a genuine requirement justifies an extra position, the derivation will grant it; Chapter 9 does exactly that.
Prop. 5.2 (Arity). The minimal self-contained fact is a triple.
Argument — a pair cannot name its own relation: (employee42, “2026-07-08”) is hired-on, or fired-on, or born-on.
A 1-tuple (x) asserts nothing — it names without claiming. A pair (entity, value) asserts a relation but cannot say which relation; the meaning lives outside the fact, which R2 forbids. Three positions, (entity, attribute, value), is the first arity at which a fact names its own relation. And it is the last arity we need: any n-ary fact decomposes into triples by minting a fresh entity for the fact and attaching its n components as attributes. Minimality and universality pin the arity at exactly three. ∎
R3 forces the entity position into I. It forces the attribute position into I too, because attributes need global names just as much. Without global names, two sources cannot know they mean the same property, and R2 fails at the first merge. The value position is either a reference or an atomic literal. Write V for the literals:
Fact = I × I × (I ∪ V) (5.3)
State = 𝒫(I × I × (I ∪ V))Chapter 3‘s exhibit already wrote facts in this shape without saying so. The dashboard’s strip-2 block held one entity and two attributes: two facts, exactly. Written with ⟨·⟩ for a URI abbreviated to its fragment, they are (⟨…#panel-14⟩, title, "Current Power") and (⟨…#panel-14⟩, value, "15.5 kW"). Entity and attribute are in I, and the value is in V. That exhibit already showed the theorem. A state in this shape is also a directed labeled graph by construction: entity and value terms are nodes, and each fact is an edge from its entity to its value, labeled with its attribute. When a value is itself in I, the edge lands on a node that other facts describe; that is how two parties’ facts connect.
panel-14 type Panel panel-14 title "Current Power" panel-14 value "15.5 kW" panel-7 type Panel panel-7 title "Wind Speed" panel-7 value "8.2 m/s" farm name "Anholt Offshore" panel-14 partOf farm panel-7 partOf farm
panel-14 value "15.5 kW" panel-14 unit "kW" turbine-3 type Turbine turbine-3 label "A-03" turbine-3 feeds panel-14 farm operator "Ørsted A/S"
State; no coordinator was consulted(⟨…#panel-14⟩, type, ⟨…#Panel⟩) (⟨…#panel-14⟩, title, "Current Power") (⟨…#panel-14⟩, value, "15.5 kW") (⟨…#panel-7⟩, type, ⟨…#Panel⟩) (⟨…#panel-7⟩, title, "Wind Speed") (⟨…#panel-7⟩, value, "8.2 m/s") (⟨…#farm⟩, name, "Anholt Offshore") (⟨…#panel-14⟩, partOf, ⟨…#farm⟩) (⟨…#panel-7⟩, partOf, ⟨…#farm⟩) (⟨…#panel-14⟩, value, "15.5 kW") (⟨…#panel-14⟩, unit, "kW") (⟨…#turbine-3⟩, type, ⟨…#Turbine⟩) (⟨…#turbine-3⟩, label, "A-03") (⟨…#turbine-3⟩, feeds, ⟨…#panel-14⟩) (⟨…#farm⟩, operator, "Ørsted A/S")
State, as the graph it isInteractive exhibit (online edition): two parties who have never met. Edit either side, shuffle, duplicate. The union changes only when you add a genuinely new fact, and (5.1) is something you fail to break rather than something you believe. The graph panel draws the same state; delete the contractor’s feeds fact and it falls apart into one star per entity, then restore it and the stars join.
The uniqueness theorem
Theorem 5.4 (Uniqueness). Any arity-minimal state model satisfying R1–R3 is isomorphic to (5.3). (Proof: Appendix B. The proof is an assembly of 5.1–5.3: R2 forces the set-of-atomic-facts shape and union-merge; R1 with minimality forces arity three; R3 forces positions one and two into I.)
It sounds like rhetoric to claim that (5.3) is the only shape the web itself permits. Theorem 5.4 makes it exact: rejecting the conclusion means faulting a step of the proof (Appendix B lays the steps out for that attack) or rejecting a requirement, and each rejection has a name. Reject R1 and your model can’t host the web’s content. Reject R2 and your data needs a coordinator, which is a central schema authority, so you have built a silo. Reject R3 and your data cannot refer beyond itself, which is a silo again. Reject minimality and you widen the tuple, the one rejection left deliberately open; Chapter 9 takes it, adding a fourth requirement, attribution. Part IV will locate every alternative data model the industry runs on at one of the first three rejections.
Machine-checked. The spine of this chapter’s proofs — the union law, the arity bound, and this theorem’s assembly — is verified in Lean 4, a proof assistant, and the verification lives in the book’s repository. Appendix C reports what is checked and what must be assumed.
The selection algebra
We are not done deriving. S2 committed select to being the meaning of a term in a fixed language, and a language’s semantics is a set of operations over a carrier. The carrier is now fixed: 𝒫(Fact). What remains is the operations, and four are enough for everything the derivation builds on: match a fact pattern with variables; join matches; union alternatives; project variables out. Each is forced by a page you can point at (any master–detail page is a join; any search page is a pattern; any page merging two lists, events from either calendar, is a union; any list that shows a title per entity, and nothing else, is a projection). None of the four is expressible from the other three, so none can be dropped. Pages force more — comparisons, counts, order — and Part III’s deployed language has them; the derivation stops at four because nothing that follows depends on the rest. The algebra reappears in Part III under its deployed name; what a write can do to a fact-set is Chapter 7’s subject.
Run one join by hand. The dashboard’s operator holds panel-14 title "Current Power"; the turbine contractor (another party entirely) holds turbine-3 feeds panel-14. Merged, the pattern (triples written bare now, URIs still abbreviated, ? marking a variable)
?turbine feeds ?panel
?panel title ?namereturns one row (?turbine = turbine-3, ?panel = panel-14, ?name = "Current Power") and the row exists only because the two parties’ facts were merged first. One page exercises the whole algebra: match, join, and project.
?x binds?p type Panel ?p title ?t ?p value ?v
| ?p | ?t | ?v |
|---|---|---|
| ⟨…#panel-14⟩ | "Current Power" | "15.5 kW" |
| ⟨…#panel-7⟩ | "Wind Speed" | "8.2 m/s" |
Data — the sub-state the solutions touched(⟨…#panel-14⟩, type, ⟨…#Panel⟩) (⟨…#panel-14⟩, title, "Current Power") (⟨…#panel-14⟩, value, "15.5 kW") (⟨…#panel-7⟩, type, ⟨…#Panel⟩) (⟨…#panel-7⟩, title, "Wind Speed") (⟨…#panel-7⟩, value, "8.2 m/s")
Interactive exhibit (online edition): the algebra exercised — patterns with variables, joined and projected over the state merged above. One preset only answers because the merge happened: it joins the operator’s facts to the contractor’s.
The join also exposes a problem in the pipeline’s types. State is the graph that (5.3) built, and the pattern just walked it, crossing from the contractor’s facts to the operator’s along a reference, from feeds into panel-14 and on to its title. References point anywhere. But in Chapter 3 every stripped document was a tree. Somewhere between them, the shape must change. That is Chapter 6.