Data Models and Query Languages

2.1Chapter Thesis

Every data model - relational, document, graph - is an answer to a narrower question than it looks like it's answering. Not "how should data be structured" in the abstract, but "which access patterns should be cheap, and which relationships are we willing to make expensive to traverse."

You cannot evaluate a data model by reading its schema. You evaluate it by asking what a specific query costs to run against it - a join, a nested lookup, a graph walk - because that cost is fixed by the model, not by the query.

2.2First Principles

The impedance mismatch

Application code operates on graphs of in-memory objects with references to other objects. The relational model operates on flat tables with no native concept of a nested object - every one-to-many or many-to-many relationship has to be encoded as a separate table joined by foreign keys. The translation layer between these two shapes is the object-relational impedance mismatch, and it exists regardless of which side you blame for it.

Embedding vs. referencing

A document model resolves the mismatch differently: it lets you embed one-to-many data directly inside the parent document, trading the cost of a join for the cost of loading data you might not need and duplicating anything embedded in more than one place. Referencing - storing an ID and looking it up separately - reintroduces the join, just outside the database's own machinery.

Schema-on-write vs. schema-on-read

A relational schema is enforced at write time: an insert that doesn't match the schema is rejected before it lands. Document databases typically enforce structure at read time - the write always succeeds, and it's the reading code's job to handle whatever shape shows up. This isn't the absence of a schema; it's a decision about which side of the read/write boundary pays the cost of schema drift.

Graphs as a first-class relationship model

Both relational and document models treat many-to-many relationships as an exception to be joined or embedded around. A graph model - vertices and labeled edges - makes arbitrary, deeply nested relationships the default access pattern, at the cost of losing the tabular structure that makes aggregate queries over uniform records cheap.

2.3Mechanism

A relational join, at its simplest, is a nested loop: for every row in the outer table, scan the inner table for matching foreign keys. This is O(n × m) without an index. An index on the foreign key column turns the inner scan into a lookup, making the join closer to O(n log m) - which is exactly why the relational model can defer "which relationships matter" to query time: any foreign key can be indexed later.

A document read has no join step at all if the required data was embedded - it's a single lookup by primary key returning the whole subtree. The cost was paid earlier, at write time, in the form of whatever duplication embedding required.

A graph traversal (breadth-first search across edges) is fundamentally a different access pattern: cost scales with the number of edges actually walked, not with the size of any table, which is why graph databases outperform relational joins on deep, variable-length traversals but underperform on queries that touch every row uniformly.

2.4Build It Yourself

Two minimal implementations, side by side, to make the access pattern difference observable rather than theoretical: a document store with dotted-path queries, and a graph traversal over an adjacency list.

type Doc = Record<string, unknown>;

class DocumentStore {
  private docs = new Map<string, Doc>();

  put(id: string, doc: Doc): void {
    this.docs.set(id, doc);
  }

  // "address.city" style dotted-path lookup -
  // the entire point of embedding is a read like this
  // costing one map lookup, not a join.
  get(id: string, path: string): unknown {
    let node: unknown = this.docs.get(id);
    for (const key of path.split(".")) {
      if (node == null) return undefined;
      node = (node as Doc)[key];
    }
    return node;
  }
}

class Graph {
  private edges = new Map<string, string[]>();

  addEdge(from: string, to: string): void {
    const list = this.edges.get(from) ?? [];
    list.push(to);
    this.edges.set(from, list);
  }

  // cost is proportional to edges walked, not table size -
  // the exact opposite scaling behavior of a table scan.
  friendsOfFriends(start: string): string[] {
    const depth1 = this.edges.get(start) ?? [];
    const depth2 = new Set<string>();
    for (const friend of depth1) {
      for (const fof of this.edges.get(friend) ?? []) {
        if (fof !== start) depth2.add(fof);
      }
    }
    return [...depth2];
  }
}

2.5Failure Modes

2.6Tradeoffs

2.7Production Perspective

Production systems increasingly refuse to pick one model: a relational system of record, a document cache shaped for a specific read path, and a graph index for relationship queries often coexist over the same underlying facts, kept in sync by the derivation mechanisms covered in The Future of Data Systems. The choice of model per store is a query-shape decision, made independently for each consumer of the data - not a single, system-wide commitment.

2.8Related Concepts