Chapter 6. From Graph to Tree

Chapter 5 closed on a mismatch of shapes; the pipeline’s types locate it. State and Data are graphs, facts whose references form arbitrary many-to-many structures. Tree and Doc are trees. Documents are hierarchical, and so is human reading. The pipeline crosses from graph to tree exactly once, inside arrange.

In the world. The tension this chapter resolves is older than the web. In 1945 Vannevar Bush blamed our trouble finding anything on “the artificiality of systems of indexing”: records “filed alphabetically or numerically,” found “by tracing it down from subclass to subclass.” The mind, he wrote, instead “operates by association.” Ted Nelson put the same objection in capitals in 1974: “EVERYTHING IS DEEPLY INTERTWINGLED. In an important sense there are no ‘subjects’ at all.” Both were describing a graph and refusing the tree. This chapter keeps both. The association is what State is. The tree is only what a document must become to cross the wire and be read.

Every web framework in history is a strategy for this one crossing. That is an observation you can verify against the deployed web, and Part IV verifies it, framework by framework. But the crossing is not yet well-defined. Graph-to-tree serialization is a relation, not a function: one graph, many trees (orderings, nestings, groupings). Yet Chapter 4 typed arrange as a function without saying where the choice among the trees lives. The fix is canonicalization:

arrange = ⟦t⟧ ∘ canon
canon : Data → Tree      deterministic, lossless, structure-free
⟦t⟧   : Tree → Tree      t — the sole locus of graph→tree structural choice

canon’s output is the graph in bare tree form — one block per entity, sorted, no nesting, no sugar. All structural decisions (what nests under what, what becomes a section versus a sidebar) move into the declarative term t, where S2 can hold.

Display order is one of those structural decisions, and it gets the strictest handling: canon sorts blocks by a fixed key that means nothing. The order of the blocks is therefore determined by the facts alone, and an order determined by the facts cannot encode a choice about them: two editors holding the same facts get the same block order, whichever story each meant to lead. If the order is a choice, like the front page’s lead story in Chapter 3, it must be stated as one more fact (this article, prominence one); the two editors now hold different facts, and t, reading them, gives each front page its own lead. Chapter 3 made exactly this concession and promised the law; here it is: if the order is a message, the order is data. The historically hard case is facts about unnamed entities: canon’s sort key is built from names, and a nameless entity offers none. As of 2024 the case has a standardized deterministic answer, a canonical labeling, which manufactures the missing names. Chapter 9 explains why the model admits unnamed entities at all, what admitting them costs, and names the spec.

Four nodes drawn once as a graph and twice as trees: d has two parents in the graph, each tree nests d under a different parent, and the other parent's edge becomes a dashed reference

One graph, many trees: d can nest under only one parent (the other edge survives as a reference) and siblings take an order the graph never fixed. These are the choices the crossing must make somewhere: canon makes none of them, t makes all of them.

And you have already seen canon’s output. Strip 2 is it: the dashboard reduced to sorted blocks, one per panel, title and value beneath. The exhibit’s format was the canonical serialization, arrived at by stripping, not a design choice.

canon needs three properties (deterministic, lossless, structure-free), and all three are satisfiable, cheaply:

Prop. 6.1. A canon with all three properties exists.

Proof — sort lexicographically; unnamed entities need Chapter 9’s labeling.

For ground states (states whose entities all carry names) order the facts lexicographically by their three positions and emit one block per entity. The map is a function because a total order on tuples exists. It is lossless because the fact set is recoverable by reading the blocks back. It is structure-free because the order is defined by the facts alone, never by their provenance or grouping. States with unnamed entities need a canonical labeling first; that labeling exists, is standardized, and Chapter 9 states its cost. ∎

facts, in arrival order
farm name "Anholt Offshore"
farm operator "Ørsted A/S"
panel-14 partOf farm
panel-14 title "Current Power"
panel-14 type Panel
panel-14 unit "kW"
panel-14 value "15.5 kW"
panel-7 partOf farm
panel-7 title "Wind Speed"
panel-7 type Panel
panel-7 value "8.2 m/s"
turbine-3 feeds panel-14
turbine-3 label "A-03"
turbine-3 type Turbine
canon — one block per entity, sorted, no nesting
⟨…#farm⟩
    name · "Anholt Offshore"
    operator · "Ørsted A/S"

⟨…#panel-14⟩
    partOf · ⟨…#farm⟩
    title · "Current Power"
    type · ⟨…#Panel⟩
    unit · "kW"
    value · "15.5 kW"

⟨…#panel-7⟩
    partOf · ⟨…#farm⟩
    title · "Wind Speed"
    type · ⟨…#Panel⟩
    value · "8.2 m/s"

⟨…#turbine-3⟩
    feeds · ⟨…#panel-14⟩
    label · "A-03"
    type · ⟨…#Turbine⟩
canon is a function of the atoms alone — not of their order, grouping, or provenance.

Interactive exhibit (online edition): shuffle the input as many times as patience allows. canon does not move. Change a fact and it moves exactly as far as the fact requires.

The graph→tree crossing. A relation (one graph, many trees) becomes a function followed by a term: canon chooses nothing, t chooses everything.

The seam is not an unsolved research problem, and Chapter 9 presents the evidence for that. And with the crossing fixed, the read side is derived end to end — Definition 1.1 has one component left.