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 webs. 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 a thesis, not a theorem — like the Transposition Thesis, flagged where it stands and left unnumbered. Part IV returns to it. 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 included: canon’s sort is deliberately meaningless. An order that carries meaning — Chapter 3’s lead story — arrives as data and is honored by t, never smuggled in the sequence of blocks. That hardens Chapter 3’s concession into the promised law: if the order is a message, the order is data — and canon leaves it nowhere else to live. The historically hard case is facts about unnamed entities — an extension Chapter 9 motivates and prices. As of 2024 it has a standardized deterministic answer: a canonical labeling. Chapter 9 names the spec.

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 never a design choice for the figure — it was the canonical serialization, arrived at by stripping.

The three properties canon must have — deterministic, lossless, structure-free — are satisfiable, and cheaply:

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

Proof — sort lexicographically; unnamed entities pay Chapter 9’s bill.

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. ∎

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.

flowchart LR
    D(["Data — graph"]) -- "canon: deterministic, structure-free" --> C(["canonical tree"])
    C -- "⟦t⟧: the sole locus of structural choice" --> Tr(["Tree"])

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 a research problem; Chapter 9 brings the evidence. And with the crossing fixed, the read side is derived end to end — Definition 1.1 has one component left.