Lesson 2: Data Models and Query Languages

Lesson 0002 — 55 min read

Data models are perhaps the most important part of developing software — they shape not only how the code is written, but how you think about the problem. This chapter is the deep foundation for every system design decision you'll ever make. It covers the full landscape: relational vs document, SQL vs NoSQL, declarative vs imperative queries, and graph models with their query languages.

The Layered Abstraction of Data Models

Most applications are built by layering one data model on top of another. Each layer hides the complexity of the one below it:

Each layer's abstraction lets different people work together effectively — the database vendor writes the storage engine, you write the application, and neither needs to understand the other's internals. Every data model embodies assumptions about how it will be used. Some operations become easy, some become impossible. Some transformations feel natural, some feel awkward.

Relational Model vs Document Model

The Relational Model

Proposed by Edgar Codd in 1970. Data is organized into relations (tables), each an unordered collection of tuples (rows). The relational model's revolutionary idea: hide the internal representation behind a clean interface. Before SQL, developers had to think deeply about internal storage details.

Relational databases dominated from the mid-1980s for ~25-30 years. Their roots were in business data processing: transaction processing (sales, banking, airline reservations) and batch processing (payroll, invoicing). But they generalized remarkably well to online publishing, social networking, ecommerce, and gaming.

The Birth of NoSQL

NoSQL emerged in the 2010s (the term started as a Twitter hashtag for a 2009 meetup on open-source, nonrelational databases). Driving forces:

The likely outcome: polyglot persistence — relational databases will continue alongside a broad variety of nonrelational datastores, each used where it fits best.

The Object-Relational Mismatch (Impedance Mismatch)

Most application code is object-oriented. Data in tables is rows and columns. The translation layer between them is called an impedance mismatch. ORM frameworks (ActiveRecord, Hibernate) reduce the boilerplate but can't completely hide the differences.

The canonical example: a LinkedIn résumé (Figure 2-1). One user has multiple positions, multiple education entries, multiple contact methods — a one-to-many tree structure.

Three ways to model this in SQL:

Many-to-One and Many-to-Many Relationships

In the résumé JSON, why are region_id and industry_id stored as IDs, not plain text? Because of normalization:

• Consistent style and spelling across profiles
• Avoiding ambiguity (multiple cities with the same name)
• Ease of updating — name stored once, change propagates everywhere
• Localization — standardized lists can be translated
• Better search — can encode hierarchy (Seattle is in Washington)

Using an ID means the human-meaningful text is stored in one place, and everything else references it. No duplication → no inconsistency risk. This is normalization.

But normalization introduces many-to-one relationships (many people live in one region). These don't fit the document model well. Relational databases handle them naturally with joins. Document databases have weak join support — you either denormalize (and risk inconsistency) or emulate joins in application code (multiple queries, slower).

Are Document Databases Repeating History?

This exact debate happened before. In the 1970s, IBM's IMS used the hierarchical model — data as a tree of records nested within records, remarkably similar to today's JSON model. It had the same strengths (good for one-to-many) and weaknesses (many-to-many was difficult, no joins).

Two solutions emerged to fix the hierarchical model's limitations:

The Network Model (CODASYL)

• Generalized the hierarchy: a record could have multiple parents
• Used access paths — like programming-language pointers stored on disk
• To query, you "navigated" by following paths from a root record
• In many-to-many relationships, multiple paths could lead to the same record; the programmer had to keep them all in their head
• Changing the data model meant rewriting lots of hand-written query code

The Relational Model

• Data laid out "in the open": a relation is just a collection of tuples
• No labyrinthine nested structures, no complicated access paths
• The query optimizer automatically chooses access paths and join order
• To query in new ways: just declare a new index — queries automatically use it
• The optimizer is built once and benefits all applications

Document databases reverted to the hierarchical model for one aspect — storing nested records within their parent. But they handle many-to-one and many-to-many relationships the same way as relational databases: using unique identifiers resolved at read time via joins or follow-up queries. They did not follow the CODASYL path.

Relational vs Document: Practical Decision Factors

Schema Flexibility: Schema-on-Read vs Schema-on-Write

Data Locality for Queries

A document is usually stored as a single continuous string (JSON, XML, BSON). Fetching the entire document means one disk seek, one read — storage locality. This is a significant performance advantage when you need large parts of the document together.

However:

• If you only need a small portion, the DB still loads the entire document — wasteful on large documents
• Updates typically rewrite the entire document (unless the encoded size doesn't change)
• Recommendation: keep documents fairly small and avoid writes that increase size

Google's Spanner offers similar locality in a relational model via interleaved tables. Oracle's multi-table index cluster tables and Bigtable's column-family concept serve similar purposes.

Convergence of Document and Relational

The two models are becoming more similar over time:

• PostgreSQL (9.3+), MySQL (5.7+), IBM DB2 (10.5+) support JSON documents with querying and indexing
• RethinkDB supports relational-like joins
• MongoDB drivers can resolve references (client-side joins)

The future is hybrid: databases that can handle document-like data and also perform relational queries, letting applications use the combination that fits their needs.

Query Languages for Data

Declarative vs Imperative

The CSS analogy

Kleppmann illustrates this with a brilliant non-database example: highlighting a selected navigation item on a webpage. In CSS (declarative):

li.selected > p { background-color: blue; }

In JavaScript/DOM (imperative), the equivalent is ~15 lines of loops, conditionals, and attribute-setting — and it's wrong because removing the class doesn't automatically remove the highlight. CSS automatically detects when the selector no longer applies and adjusts. This captures exactly why declarative languages win for databases: they limit what you can express, giving the system room to optimize and maintain invariants.

MapReduce

MapReduce is neither fully declarative nor fully imperative — it's a hybrid. The query logic is expressed with snippets of code (map and reduce functions), called by a processing framework.

The shark-counting example — three approaches:

SELECT date_trunc('month', observation_timestamp)
  AS observation_month,
  SUM(num_animals) AS total_animals
FROM observations
WHERE family = 'Sharks'
GROUP BY observation_month;

db.observations.mapReduce(
  function map() {
    var year = this.observationTimestamp.getFullYear();
    var month = this.observationTimestamp.getMonth() + 1;
    emit(year + "-" + month, this.numAnimals);
  },
  function reduce(key, values) {
    return Array.sum(values);
  },
  { query: { family: "Sharks" },
    out: "monthlySharkReport" }
);

db.observations.aggregate([
  { $match: { family: "Sharks" } },
  { $group: {
    _id: {
      year:  { $year:  "$observationTimestamp" },
      month: { $month: "$observationTimestamp" }
    },
    totalAnimals: { $sum: "$numAnimals" }
  }}
]);

MapReduce's map and reduce functions must be pure functions — no side effects, no additional DB queries. This allows the framework to run them anywhere, in any order, and retry on failure. But writing two carefully coordinated JS functions is harder than writing one SQL query, and the optimizer has less room to improve performance.

Graph-Like Data Models

When many-to-many relationships are very common, graphs become the most natural representation. A graph has vertices (nodes/entities) and edges (relationships/arcs).

Graphs are powerful because they can store completely different types of objects in a single datastore with a consistent model. The example in Figure 2-5 shows Lucy and Alain — people, cities, states, countries, continents all in one graph with WITHIN, BORN_IN, and LIVES_IN edges.

Property Graphs

Each vertex:

• Unique identifier
• Set of outgoing edges
• Set of incoming edges
• Collection of properties (key-value pairs)

Each edge:

• Unique identifier
• Tail vertex (start)
• Head vertex (end)
• Label (type of relationship)
• Collection of properties (key-value pairs)

Implemented by: Neo4j, Titan, InfiniteGraph. The model can be represented as two relational tables (vertices + edges, Example 2-2):

CREATE TABLE vertices (
  vertex_id   integer PRIMARY KEY,
  properties  json
);
CREATE TABLE edges (
  edge_id     integer PRIMARY KEY,
  tail_vertex integer REFERENCES vertices (vertex_id),
  head_vertex integer REFERENCES vertices (vertex_id),
  label       text,
  properties  json
);
CREATE INDEX edges_tails ON edges (tail_vertex);
CREATE INDEX edges_heads ON edges (head_vertex);

Key aspects:

1. Any vertex can connect to any other vertex — no schema restriction
2. Efficient traversal both forward and backward (indexes on tail and head)
3. Different edge labels let you store different relationship types in one graph

Cypher Query Language (Neo4j)

Cypher is a declarative query language for property graphs. Named after the character in The Matrix. Uses ASCII-art arrow notation to describe graph patterns.

Inserting data (Example 2-3):

CREATE
  (NAmerica:Location {name:'North America', type:'continent'}),
  (USA:Location      {name:'United States', type:'country'}),
  (Idaho:Location    {name:'Idaho',         type:'state'}),
  (Lucy:Person       {name:'Lucy'}),
  (Idaho) -[:WITHIN]->  (USA)  -[:WITHIN]-> (NAmerica),
  (Lucy)  -[:BORN_IN]-> (Idaho)

Query: find people who emigrated from US to Europe (Example 2-4):

MATCH
  (person) -[:BORN_IN]->  () -[:WITHIN*0..]->
    (us:Location {name:'United States'}),
  (person) -[:LIVES_IN]-> () -[:WITHIN*0..]->
    (eu:Location {name:'Europe'})
RETURN person.name

The :WITHIN*0.. syntax means "follow WITHIN edges zero or more times" — like the * in a regex. This handles the variable-depth hierarchy (a city is WITHIN a state, which is WITHIN a country, which is WITHIN a continent).

Graph Queries in SQL (Recursive CTEs)

The same query in SQL (Example 2-5) requires recursive common table expressions — 29 lines instead of 4:

WITH RECURSIVE
  in_usa(vertex_id) AS (
    SELECT vertex_id FROM vertices
    WHERE properties->>'name' = 'United States'
    UNION
    SELECT edges.tail_vertex FROM edges
    JOIN in_usa ON edges.head_vertex = in_usa.vertex_id
    WHERE edges.label = 'within'
  ),
  in_europe(vertex_id) AS (
    SELECT vertex_id FROM vertices
    WHERE properties->>'name' = 'Europe'
    UNION
    SELECT edges.tail_vertex FROM edges
    JOIN in_europe ON edges.head_vertex = in_europe.vertex_id
    WHERE edges.label = 'within'
  ),
  born_in_usa(vertex_id) AS (
    SELECT edges.tail_vertex FROM edges
    JOIN in_usa ON edges.head_vertex = in_usa.vertex_id
    WHERE edges.label = 'born_in'
  ),
  lives_in_europe(vertex_id) AS (
    SELECT edges.tail_vertex FROM edges
    JOIN in_europe ON edges.head_vertex = in_europe.vertex_id
    WHERE edges.label = 'lives_in'
  )
SELECT vertices.properties->>'name' FROM vertices
JOIN born_in_usa   ON vertices.vertex_id = born_in_usa.vertex_id
JOIN lives_in_europe ON vertices.vertex_id = lives_in_europe.vertex_id;

Triple-Stores and SPARQL

The triple-store model is mostly equivalent to property graphs, using different vocabulary. All information is stored as three-part statements: (subject, predicate, object).

Each triple is like one fact: (Jim, likes, bananas). Subject = vertex. Object = either a primitive value (property) or another vertex (edge). Predicate = property key or edge label.

Turtle format (human-readable RDF)

@prefix : <urn:example:>.

_:lucy     a       :Person.
_:lucy     :name   "Lucy".
_:lucy     :bornIn _:idaho.
_:idaho    a       :Location.
_:idaho    :name   "Idaho".
_:idaho    :type   "state".
_:idaho    :within _:usa.

Semicolons let you say multiple things about the same subject, making it more readable:

_:lucy  a :Person;  :name "Lucy";         :bornIn _:idaho.
_:idaho a :Location; :name "Idaho";        :type "state"; :within _:usa.
_:usa   a :Location; :name "United States"; :type "country"; :within _:namerica.

RDF and the Semantic Web

RDF was designed for internet-wide data exchange. Predicates are URIs (e.g., <http://my-company.com/namespace#within>), so different datasets can be combined without naming conflicts.

The semantic web vision: websites publish machine-readable data, allowing automatic combination into a "web of data." Overhyped in the early 2000s, but the technology (RDF, SPARQL, triple-stores) remains useful for internal applications regardless.

SPARQL Query Language

SPARQL ("sparkle") predates Cypher and inspired Cypher's pattern matching. The same emigrants query is even more concise:

PREFIX : <urn:example:>
SELECT ?personName
WHERE {
  ?person :name ?personName.
  ?person :bornIn  / :within* / :name "United States".
  ?person :livesIn / :within* / :name "Europe".
}

The / operator is SPARQL's path syntax: :bornIn / :within* means "follow a :bornIn edge, then zero or more :within edges" — equivalent to Cypher's -[:BORN_IN]-> () -[:WITHIN*0..]->.

Graph Databases vs the Network Model (CODASYL)

At first glance, CODASYL's network model looks like modern graph databases. They differ in critical ways:

The Foundation: Datalog

Datalog is older (1980s academic research) and less well-known but provides the foundation that Cypher and SPARQL build upon. Used in Datomic and Cascalog.

Instead of a triple (subject, predicate, object), Datalog writes predicate(subject, object):

name(namerica, 'North America').
type(namerica, continent).
name(usa, 'United States').
type(usa, country).
within(usa, namerica).
name(idaho, 'Idaho').
type(idaho, state).
within(idaho, usa).
name(lucy, 'Lucy').
born_in(lucy, idaho).

Queries are built from rules that define new predicates derived from data or from other rules:

within_recursive(Location, Name) :-
  name(Location, Name).                              /* Rule 1 */
within_recursive(Location, Name) :-
  within(Location, Via),                             /* Rule 2 */
  within_recursive(Via, Name).

migrated(Name, BornIn, LivingIn) :-
  name(Person, Name),                                /* Rule 3 */
  born_in(Person, BornLoc),
  within_recursive(BornLoc, BornIn),
  lives_in(Person, LivingLoc),
  within_recursive(LivingLoc, LivingIn).

?- migrated(Who, 'United States', 'Europe').
/* Who = 'Lucy'. */

Rules can refer to other rules, including recursively. Complex queries are built up a small piece at a time — like composing functions. The Datalog approach requires a different kind of thinking: you define what is true rather than how to find the answer. The system figures out the computation.

Interview Synthesis

Chapter 2 gives you the framework to answer the most common opening question in system design interviews: "Would you use SQL or NoSQL for this?"

Your decision tree:

1. What does the data look like?

   • Tree-structured, self-contained, loaded at once (a profile, a blog post, a product catalog) → Document model (MongoDB, CouchDB)
   • Highly interconnected with many-to-many relationships (social graph, organizational hierarchy, recommendation network) → Graph model (Neo4j, Datomic)
   • Tabular with well-defined relationships, need joins and integrity → Relational model (PostgreSQL, MySQL)

2. Does the schema change frequently?

   • Yes, and data is heterogeneous → Schema-on-read (document DB)
   • Stable, uniform structure → Schema-on-write (relational DB) — schema enforcement is a feature, not a bug

3. What are the query patterns?

   • Read entire entities, few joins → Document DB (locality advantage)
   • Variable-depth traversals ("find all sub-locations of this location") → Graph DB or SQL recursive CTE
   • Ad-hoc aggregations and reporting → SQL (mature optimizer, rich analytic functions)

Primary source: Kleppmann, M. (2017). Designing Data-Intensive Applications, Chapter 2: “Data Models and Query Languages.” O'Reilly Media.
Code examples adapted from: Figures 2-1 through 2-6 in the same chapter.
Recommended supplement: Stonebraker & Hellerstein (2005). “What Goes Around Comes Around.” Readings in Database Systems, 4th ed., MIT Press.

Questions? Ask your agent — you can follow up on any concept, quiz answer, or how this applies to a specific FAANG interview question.