Data models are the most consequential decision in a piece of software. They shape not only how data is stored but how everyone involved thinks about the problem, because every layer of a system is a model of the layer below: application objects model the real world, JSON or tables model those objects, bytes on disk model the tables, and electrical currents model the bytes. Pick a model that fits the shape of your data and the queries become obvious; pick one that fights it and you will write translation code forever.

This chapter compares the three general-purpose models you will meet in practice (relational, document, graph), explains the recurring argument about schemas, contrasts declarative and imperative query languages, and tells a historical story (the 1970s network model) that keeps repeating itself. Interviewers love to ask "SQL or NoSQL?"; the right answer is always a question about relationships and access patterns, and this chapter gives you the vocabulary to ask it.

In one minute

• The relational model (Codd, 1970) stores data in tables of tuples and hides the storage layout behind a declarative query language. It won because the query optimizer, not the application, decides how to access the data.
• Document databases (MongoDB, CouchDB, RethinkDB, Espresso) store self-contained JSON-like trees. They shine for one-to-many tree-shaped data with good locality, and struggle with many-to-one and many-to-many relationships because joins are weak or absent.
• The object-relational mismatch (impedance mismatch) is the translation layer between application objects and rows; ORMs reduce it but do not remove it.
• Normalize by referring to things by ID, not by human-meaningful string: IDs never need to change, strings do, and duplicated strings drift.
• Schema-on-write (relational) enforces structure when data is stored; schema-on-read (document) interprets structure when data is read. The latter is useful when records are heterogeneous or the structure is set by an external system, not a license to skip design.
• Declarative languages (SQL, Cypher, SPARQL, Datalog) say what you want; imperative code says how. Declarative queries are easier to optimize and to parallelize, which is why MongoDB moved from map-reduce to the aggregation pipeline.
• Graph models (property graphs with Cypher; triple stores with SPARQL; Datalog) fit data dominated by many-to-many relationships, especially when traversals of variable depth are common.
• The 1970s CODASYL network model supported many-to-many relationships but forced application code to follow hand-chosen access paths. Document databases risk repeating that mistake; graph databases avoid it because any vertex can be referenced directly and queries are declarative.

Why the data model matters

Layers of models

Every application is built by layering one data model on top of another. Application developers look at the real world and model it as objects, data structures and APIs. To store those structures they express them in a general-purpose model: JSON or XML documents, tables in a relational database, or a graph. The database engineers who built the storage engine chose how to represent that model as bytes in memory, on disk or on the network, so it can be queried, searched and manipulated. At still lower levels, hardware engineers represent bytes as electrical currents, pulses of light or magnetic fields.

Each layer hides the complexity of the layer below behind a clean model, letting different groups of people (database vendors and application developers, say) work together effectively. The choice of model has a profound effect on what the software above it can do easily and what it can do only with great difficulty.

The contenders

The best-known model today is the relational one proposed by Edgar Codd in 1970: data is organized into relations (tables), each an unordered collection of tuples (rows). It was a theoretical proposal doubted at the time, but by the mid-1980s relational database management systems (RDBMS) and SQL had become the standard for storing and querying data with a regular structure. They were designed for business data processing (transaction processing such as sales, banking and airline reservations; batch processing such as invoicing and payroll), and they generalized far beyond that into web publishing, games, social networks and SaaS. Competing models in the 1970s and 1980s were the hierarchical and network models; object databases came and went in the late 1980s and early 1990s; XML databases appeared around 2000. None dislodged the relational model.

The latest challenger, since roughly 2010, is NoSQL. The name was a catchy Twitter hashtag for a 2009 meetup and has since been reinterpreted as "Not Only SQL". The book lists the driving forces:

• A need for greater scalability than relational databases could easily achieve, including very large datasets and very high write throughput.
• A widespread preference for free and open source software over commercial database products.
• Specialized query operations that are not well supported by the relational model.
• Frustration with the restrictiveness of relational schemas and a desire for a more dynamic and expressive data model.

Different applications have different requirements, so the likely future is polyglot persistence: relational databases used alongside a broad variety of non-relational stores, each chosen for the part of the problem it fits.

Relational model versus document model

The object-relational mismatch

Most application development today is done in object-oriented languages, and there is an awkward translation layer between objects in the application code and the relational model of tables, rows and columns. This disconnect is sometimes called an impedance mismatch, a term borrowed from electrical engineering. Object-relational mapping (ORM) frameworks such as ActiveRecord and Hibernate reduce the amount of boilerplate, but they cannot completely hide the difference between the two models.

The book's example is a LinkedIn-style résumé. A user has one name and one summary but many positions, many education entries and many contact details: a one-to-many relationship, forming a tree. The relational model offers three ways to store it:

1. Normalized: separate tables for positions, education and contact info, each row holding a foreign key to the user. The traditional approach; retrieving the full profile requires several queries or a messy multi-way join.
2. Structured datatypes inside a row: later SQL standards added multi-valued columns and XML support, and PostgreSQL, MySQL, Oracle, IBM DB2 and SQL Server all support JSON documents in a column with querying and indexing inside them.
3. Encode as a blob: store the positions as a JSON or XML string in a text column and let the application parse it. The database cannot query or index inside the blob.

A JSON document stores the whole résumé as one self-contained tree, which is a better fit for this data than a schema with many tables. Document-oriented databases such as MongoDB, RethinkDB, CouchDB and Espresso (LinkedIn's) are built around that representation. The JSON representation has better locality: fetching a profile is one query, one lookup, instead of several queries or a join. The one-to-many relationships are explicit in the tree structure.

Many-to-one and many-to-many relationships

The résumé has two fields, region_id and industry_id, stored as IDs rather than as plain text strings such as "Greater Seattle Area" and "Philanthropy". There are good reasons to use a standardized list of options with IDs rather than free text:

• Consistent style and spelling across profiles.
• No ambiguity between cities with the same name.
• Ease of updating: if the name changes (a city is renamed), you change one row.
• Localization support: the standardized list can be translated into the user's language.
• Better search: a region can be encoded as part of a geography, so a search for philanthropists in Washington state can match a profile in Seattle.

The underlying principle is normalization: anything meaningful to humans may need to change at some point, and if that information is duplicated, every copy must be updated, with the risk of write overhead and inconsistencies. An ID, by contrast, never needs to change because it is meaningless to humans. Removing such duplication is what database normalization is about.

Normalizing in this way requires many-to-one relationships: many people live in one region, many people work in one industry. In a relational database it is normal to refer to rows in other tables by ID because joins are easy. In a document database, joins are not needed for one-to-many tree structures, and support for joins is often weak. If the database does not support joins, you emulate them in application code by making multiple queries. The region and industry lists are small and slow-changing, so an application can keep them in memory; but the work of making the join has shifted from the database to the application.

Data also tends to become more interconnected as features are added. The book extends the résumé example in two ways: make organizations and schools entities rather than strings (so an organization page can list its employees), and add recommendations, where one user writes a recommendation that appears on another's profile with the recommender's current name and photo. Both introduce many-to-many relationships. In the document model, the data inside each dotted-line rectangle (a résumé) can be grouped into one document, but references to organizations, schools and other users need to be references, and those references require joins when queried.

Are document databases repeating history?

The debate about how to represent many-to-many relationships is older than NoSQL. The most popular database for business data processing in the 1970s was IBM's Information Management System (IMS), originally developed for stock-keeping in the Apollo program. IMS used the hierarchical model, which looks remarkably like the JSON model used by document databases today: all data was a tree of records nested within records. Like document databases, it worked well for one-to-many relationships and made many-to-many relationships difficult, with no join support. Developers had to decide whether to duplicate (denormalize) data or manually resolve references between records. Two models were proposed to fix this: the network model and the relational model.

The network model was standardized by the Conference on Data Systems Languages (CODASYL) committee and implemented by several vendors. It generalized the hierarchical model: a record could have multiple parents instead of exactly one, which allowed many-to-many relationships. The links between records were not foreign keys but more like pointers in a programming language (while still being stored on disk). The only way to access a record was to follow a path from a root record along these chains of links, called an access path.

In the simplest case an access path is like traversing a linked list: start at the head, look at one record at a time until you find the one you want. But in a world of many-to-many relationships, several different paths can lead to the same record, and a programmer working with the network model had to keep track of all these paths in their head. A query in CODASYL was performed by moving a cursor through the database, iterating over lists of records and following access paths. If a record had multiple parents, the application code had to keep track of all the various relationships. Even CODASYL committee members admitted this was like navigating around an n-dimensional data space.

Manual access-path selection made the most efficient use of the very limited hardware of the 1970s, but it made the code for querying and updating the database complicated and inflexible. Changing the access paths meant going through a lot of handwritten query code and rewriting it. Hierarchical and network models alike made the application programmer the query planner.

The relational model, by contrast, laid out all the data in the open: a relation is simply a collection of tuples. There are no labyrinthine nested structures, no complicated access paths to follow if you want to look at the data. You can read any or all of the rows in a table, selecting those that match an arbitrary condition. You read a particular row by designating some columns as a key and matching on those. You can insert a new row into any table without worrying about foreign key relationships to and from other tables. (The relational model does have foreign keys, but they are a constraint on data, not a navigation mechanism.)

Access paths still exist in a relational database, as indexes and join algorithms, but the query optimizer chooses them automatically, not the application developer. If you want to query your data in new ways, you declare a new index and queries automatically use whichever indexes are most appropriate. You do not need to change your queries to take advantage of a new index. Query optimizers are complicated beasts that took many years of research and development, but you only need to build one once, and every application using the database benefits. That is the key insight of the relational model, and it is why it won.

Document databases reverted back to the hierarchical model in one aspect: storing nested records (one-to-many relationships) within their parent record rather than in a separate table. However, when it comes to representing many-to-one and many-to-many relationships, relational and document databases are not fundamentally different: in both cases the related item is referenced by a unique identifier, called a foreign key in the relational model and a document reference in the document model. The identifier is resolved at read time by a join or follow-up queries. Document databases have so far not followed the path of CODASYL.

Relational versus document databases today

The main arguments for the document model are schema flexibility, better performance due to locality, and that for some applications it is closer to the data structures used by the application. The relational model counters with better support for joins and for many-to-one and many-to-many relationships.

Which leads to simpler code? If the data in your application has a document-like structure (a tree of one-to-many relationships, where typically the entire tree is loaded at once), use a document model. The relational technique of shredding (splitting a document-like structure into multiple tables) can lead to cumbersome schemas and unnecessarily complicated code. The document model has limitations too: you cannot refer directly to a nested item within a document, you have to say something like "the second item in the list of positions for user 251", much like an access path in the hierarchical model. As long as documents are not too deeply nested, that is not a problem.

The poor support for joins in document databases may or may not matter depending on the application. For an analytics application that records which events occurred at which time, many-to-many relationships may never be needed. But if your application does use many-to-many relationships, the document model becomes less appealing: you can reduce the need for joins by denormalizing, but then the application has to do extra work to keep the denormalized copies consistent. Joins can be emulated in application code with multiple requests, but that moves complexity into the application and is usually slower than a join done by specialized code inside the database. For highly interconnected data the document model is awkward, the relational model is acceptable, and graph models are the most natural.

Schema flexibility in the document model

Most document databases, and the JSON support in relational databases, do not enforce any schema on the data in documents. XML support in relational databases usually comes with optional schema validation. No schema means arbitrary keys and values can be added to a document, and when reading, clients have no guarantee what fields the documents may contain.

Document databases are sometimes called schemaless, but that is misleading: the code that reads the data usually assumes some kind of structure, so there is an implicit schema that is not enforced by the database. A more accurate term is schema-on-read: the structure of the data is implicit and only interpreted when the data is read. This is in contrast to schema-on-write, the traditional approach of relational databases, where the schema is explicit and the database ensures all written data conforms to it. Schema-on-read is similar to dynamic (runtime) type checking in programming languages, whereas schema-on-write is similar to static (compile-time) type checking. Just as the advocates of static and dynamic typing have big debates about their relative merits, enforcement of schemas in a database is a contentious topic with no right or wrong answer.

The difference is most noticeable when an application wants to change the format of its data. Suppose you currently store each user's full name in one field and want to store first and last names separately. In a document database you just start writing new documents with the new fields and have code in the application that handles the case when old documents are read:

if (user && user.name && !user.first_name) {
  // Documents written before Dec 8, 2013 don't have first_name
  user.first_name = user.name.split(" ")[0];
}

In a schema-on-write database you perform a migration:

ALTER TABLE users ADD COLUMN first_name text;
UPDATE users SET first_name = split_part(name, ' ', 1);   -- PostgreSQL

Schema changes have a bad reputation for being slow and requiring downtime. That reputation is not entirely deserved: most relational database systems execute ALTER TABLE in a few milliseconds. MySQL is a notable exception, since it historically copied the entire table on ALTER TABLE, which can mean minutes or hours of downtime on a large table, though tools such as pt-online-schema-change and gh-ost, and MySQL's own online DDL, work around this. Running the UPDATE on a large table is likely to be slow on any database because every row must be rewritten; if that is unacceptable, leave first_name defaulting to NULL and fill it in at read time, as you would with a document database.

Schema-on-read is advantageous when the items in the collection do not all have the same structure, for example because there are many different types of objects and it is not practical to put each type in its own table, or because the structure of the data is determined by external systems over which you have no control and which may change at any time. When all records are expected to have the same structure, schemas are a useful mechanism for documenting and enforcing that structure. Chapter 4 discusses schema evolution in detail.

Data locality for queries

A document is usually stored as a single continuous string, encoded as JSON, XML or a binary variant such as MongoDB's BSON. If your application often needs to access the entire document (to render it on a web page, say), there is a performance advantage to this storage locality. If data is split across multiple tables, multiple index lookups are required to retrieve it all, which may require more disk seeks and take more time.

The locality advantage only applies if you need large parts of the document at the same time. The database typically needs to load the entire document even if you access only a small portion of it, which is wasteful on large documents. On updates, the entire document usually needs to be rewritten; only modifications that do not change the encoded size can easily be performed in place. For these reasons it is generally recommended to keep documents fairly small and to avoid writes that increase their size.

Locality is not exclusive to the document model. Google's Spanner offers the same locality property in a relational model by allowing a table's rows to be interleaved (nested) within a parent table. Oracle's multi-table index cluster tables do something similar. The column-family concept in the Bigtable data model (used in Cassandra and HBase) has a similar purpose of managing locality.

Convergence of document and relational databases

Most relational systems other than MySQL have supported XML since the mid-2000s, including functions to make local modifications to XML documents and to index and query inside them, which lets applications use data models very similar to a document database. PostgreSQL since version 9.3, MySQL since 5.7 and IBM DB2 since 10.5 have a similar level of support for JSON documents.

On the document side, RethinkDB supports relational-like joins in its query language, and some MongoDB drivers automatically resolve document references, effectively performing a client-side join, though this is likely to be slower than a join in the database since it requires additional network round-trips and is less optimized. MongoDB has since added the $lookup aggregation stage for server-side left outer joins. The models are complementing each other; a hybrid of the two is a good route for databases to take in future.

Query languages for data

Declarative versus imperative

When the relational model was introduced, it included a new way of querying data: SQL is a declarative query language, whereas IMS and CODASYL queried the database with imperative code. Many commonly used programming languages are imperative. The book illustrates with a list of animals; in imperative JavaScript you write a loop:

function getSharks() {
  var sharks = [];
  for (var i = 0; i < animals.length; i++) {
    if (animals[i].family === "Sharks") {
      sharks.push(animals[i]);
    }
  }
  return sharks;
}

In relational algebra you write sharks = σ(family = "Sharks")(animals), and in SQL:

SELECT * FROM animals WHERE family = 'Sharks';

An imperative language tells the computer to perform certain operations in a certain order: step through the list, check each element, add matches to the output. A declarative language specifies the pattern of the data you want (what conditions the results must meet, how to transform the data by sorting, grouping or aggregating) but not how to achieve that goal. It is up to the database's query optimizer to decide which indexes and join methods to use, and in which order to execute the various parts of the query.

This has two advantages. A declarative query is typically more concise and easier to work with, and it hides implementation details of the database engine, so the database can introduce performance improvements without any changes to queries. For example, in the imperative code above, the list of animals appears in a particular order; if the database wants to reclaim unused disk space behind the scenes, it may need to move records around, changing the order. Can the database do that safely without breaking queries? With SQL, yes, because the query does not guarantee any particular ordering (it never asked for one). Declarative languages also lend themselves to parallel execution across multiple cores and machines, because they specify only the pattern of the results, not the algorithm used to determine them. Imperative code is hard to parallelize because it specifies instructions that must be performed in a particular order.

Declarative queries on the web

The same contrast appears outside databases. To highlight the currently selected navigation item on a web page, in CSS you write a declarative selector:

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

In imperative JavaScript with the core DOM API, you iterate over all <li> elements, check their class, find their child <p> elements and set the style manually. That code is longer, harder to understand, and brittle: if the browser adds a new, faster method for finding elements by class, the imperative code must be rewritten to benefit, whereas the CSS declaration works with any browser that supports CSS. The point is that declarative languages are not an exotic database idea; they are how most of the web is styled.

MapReduce querying

MapReduce is a programming model for processing large amounts of data in bulk across many machines, popularized by Google. A limited form of it is supported by some NoSQL datastores, including MongoDB and CouchDB, as a mechanism for performing read-only queries across many documents. It is neither declarative nor fully imperative but somewhere in between: the logic of the query is expressed with snippets of code that are called repeatedly by the processing framework. It is based on the map (also known as collect) and reduce (also known as fold or inject) functions that exist in many functional programming languages.

The book's example: counting shark sightings per month. In PostgreSQL:

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

The same query in MongoDB's map-reduce feature supplies a filter declaratively (query: { family: "Sharks" }), a map function that emits a key (year-month) and value (number of animals) for every matching document, and a reduce function that sums the values for each key. The map and reduce functions must be pure: they only use the data passed to them as input, cannot perform additional database queries, and must not have side effects. That restriction allows the database to run them anywhere, in any order, and rerun them on failure. But they can still parse strings, call library functions, perform calculations and so on.

The usability problem is that you have to write two carefully coordinated JavaScript functions, which is often harder than writing a single query. And a declarative query language offers more opportunities for a query optimizer to improve performance. For this reason MongoDB 2.2 added the aggregation pipeline, a declarative query language:

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

That is similar in expressiveness to a subset of SQL, dressed up in JSON-based syntax rather than English-sentence style. The moral of the story: a NoSQL system found itself accidentally reinventing SQL, albeit in disguise.

Graph-like data models

When graphs fit

Many-to-many relationships are the main distinguishing feature between the data models. If your application has mostly one-to-many relationships (tree-structured data) or no relationships between records, the document model is appropriate. If many-to-many relationships are common but simple, the relational model handles them. But as the connections within your data become more complex, it becomes more natural to model the data as a graph.

A graph consists of vertices (also called nodes or entities) and edges (also called relationships or arcs). Typical examples: social graphs (people are vertices, "knows" edges), the web graph (pages and links; PageRank is a graph algorithm), road or rail networks (junctions and segments; shortest-path algorithms). Graphs are not limited to homogeneous data: Facebook maintains a single graph with many types of vertices (people, locations, events, check-ins, comments) and edges (friendship, check-in location, who commented on which post, who attended which event).

The book uses a running example: two people, Lucy from Idaho and Alain from Beaune, France, who married and live in London. The data includes countries, states, cities, and the facts of birth and residence.

Notice that the structure is irregular: the US has states, France has regions and departments, the UK has countries and counties. A graph does not force all of these into the same shape.

Property graphs

In the property graph model (Neo4j, Titan and its successor JanusGraph, InfiniteGraph), each vertex has a unique identifier, a set of outgoing edges, a set of incoming edges, and a collection of properties (key-value pairs). Each edge has a unique identifier, a tail vertex (where it starts), a head vertex (where it ends), a label describing the relationship, and a collection of properties.

You can think of a graph store as two relational tables:

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);

Three aspects of the model matter. Any vertex can have an edge connecting it with any other vertex; there is no schema restricting which kinds of things can be associated. Given any vertex, you can efficiently find both its incoming and outgoing edges and thus traverse the graph, following a path forward or backward (that is what the two indexes are for). By using different labels for different kinds of relationships, you can store several kinds of information in a single graph while maintaining a clean data model.

This gives graphs a great deal of flexibility. You can express regional structures in different countries without forcing them into one schema, add facts such as food allergies as vertices with edges to allergens, and extend the graph as the application grows without redesigning the schema.

The Cypher query language

Cypher is a declarative query language for property graphs, created for Neo4j (named after a character in The Matrix). To insert the Lucy data:

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)

The arrow notation (Idaho) -[:WITHIN]-> (USA) creates an edge labeled WITHIN with tail Idaho and head USA. The book's query asks for the names of everyone who emigrated from the United States to Europe:

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

Read it as: find any vertex person that has an outgoing BORN_IN edge to some vertex, from which you can follow a chain of zero or more WITHIN edges until you reach a vertex of type Location whose name is "United States", and similarly for LIVES_IN and "Europe". The *0.. is a variable-length path, and the query optimizer decides how to execute it: it might scan all people and check their birthplaces, or start from the two location vertices and work backwards. You do not have to specify the execution strategy.

Graph queries in SQL

Since the graph can be stored as two tables, you can query it in SQL. The hard part is that in a relational query you usually know in advance which joins you need, whereas in a graph query the number of joins is not fixed: the WITHIN*0.. chain may be one hop (Idaho is directly in the United States) or several (Beaune, Burgundy, France, Europe). Since SQL:1999 this is expressible with recursive common table expressions (WITH RECURSIVE), but the book shows the equivalent query takes about 29 lines compared with 4 in Cypher, and is considerably harder to read. Different data models are designed to satisfy different use cases, and the right one makes the query obvious.

Triple stores and SPARQL

The triple-store model is mostly equivalent to the property graph model, using different words. All information is stored as three-part statements: (subject, predicate, object), such as (Jim, likes, bananas). The subject is equivalent to a vertex. The object is one of two things: a value in a primitive datatype, in which case the predicate and object are equivalent to a key and value of a property on the subject vertex (as in (Lucy, age, 33)); or another vertex, in which case the predicate is an edge, the subject the tail vertex, and the object the head vertex (as in (Lucy, marriedTo, Alain)).

The book writes the Lucy example in Turtle, a subset of Notation3, with syntactic shortcuts such as _:lucy a :Person; :name "Lucy"; :bornIn _:idaho..

Triple stores are associated with the semantic web, an early-2000s vision that websites would publish machine-readable data in RDF (Resource Description Framework) so that the web became a database of everything. The semantic web largely failed to arrive, and the association has put some people off triple stores, but the model itself is useful for applications regardless. RDF's quirks, such as every subject, predicate and object being a URI such as <http://my-company.com/namespace#lives_in>, exist so that data from different sources can be combined without name clashes; the URIs do not need to resolve to anything.

SPARQL is the query language for triple stores using the RDF data model (pronounced "sparkle"), and Cypher's pattern matching is borrowed from it, so they look similar:

PREFIX : <urn:example:>

SELECT ?personName WHERE {
  ?person :name ?personName.
  ?person :bornIn  / :within* / :name "United States".
  ?person :livesIn / :within* / :name "Europe".
}

The / :within* is the variable-length path. Because RDF does not distinguish properties from edges (both are predicates), the same syntax matches both.

Graph databases versus the network model

Is the graph model just CODASYL in disguise? No, and the differences are instructive:

• CODASYL had a schema that specified which record type could be nested within which other record type. A graph database has no such restriction: any vertex can have an edge to any other vertex, giving applications much more flexibility to adapt to changing requirements.
• In CODASYL the only way to reach a record was to traverse one of the access paths to it. In a graph database you can refer directly to any vertex by its unique ID, or use an index to find vertices with a particular value.
• In CODASYL the children of a record were an ordered set, so the database had to maintain that ordering (which affected storage layout) and applications inserting records had to worry about position. In a graph database vertices and edges are unordered; you can only sort results when making a query.
• CODASYL queries were imperative, difficult to write and easily broken by changes in the schema. Graph databases support high-level declarative languages such as Cypher or SPARQL, as well as imperative code if you want it.

The foundation: Datalog

Datalog is much older than Cypher or SPARQL, having been studied extensively by academics in the 1980s, and it provides the foundation that later query languages build on. It is used in a few systems: Datomic uses it as its query language, and Cascalog is a Datalog implementation for querying large datasets in Hadoop.

Datalog's data model is similar to the triple-store model, generalized a bit. Instead of (subject, predicate, object) you write predicate(subject, object): name(idaho, 'Idaho'), within(idaho, usa), born_in(lucy, idaho). Queries are built from rules that define new predicates in terms of existing ones. The emigration query becomes:

within_recursive(Location, Name) :- name(Location, Name).

within_recursive(Location, Name) :- within(Location, Via),
                                    within_recursive(Via, Name).

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

?- migrated(Who, 'United States', 'Europe').

Words starting with an uppercase letter are variables; predicates are matched like in Cypher and SPARQL. A rule applies if the system can find a match for all predicates on the right-hand side of :-, in which case it is as though the left-hand side was added to the database. Rules can refer to other rules and to themselves, so the recursive within_recursive builds up the chain of containment one step at a time. Rules can also be combined and reused in different queries. The Datalog approach is less convenient for simple one-off queries, but it copes better with complex data because small pieces of logic compose.

Choosing a data model

	Relational	Document	Graph
Natural shape of data	Tables of regular rows, many-to-one and many-to-many via joins	Self-contained trees (one-to-many)	Highly interconnected many-to-many, variable-depth paths
Schema	Schema-on-write, enforced	Schema-on-read, implicit	Flexible; any vertex connects to any vertex
Joins	Strong, optimized by the engine	Weak or absent; emulated in application	Traversal is the core operation
Locality	Row-level; related data spread across tables	Whole document stored together	Vertex and adjacent edges
Query language	SQL (declarative)	Query APIs, aggregation pipelines, map-reduce	Cypher, SPARQL, Datalog (declarative)
Weak spot	Impedance mismatch; shredding trees into tables	Many-to-many; large or growing documents; no direct reference into nested items	Simple tabular or aggregate-heavy workloads
Typical systems	PostgreSQL, MySQL, Oracle, SQL Server, Spanner	MongoDB, CouchDB, RethinkDB, Espresso, DynamoDB (document mode)	Neo4j, JanusGraph, Amazon Neptune, Datomic

Decision heuristics the chapter supports:

• Count the relationship types. Mostly one-to-many trees loaded whole: document. Regular many-to-many with fixed-depth joins: relational. Variable-depth traversals, heterogeneous entities, growing connectivity: graph.
• Ask who controls the structure. If an external system dictates the record format and may change it, schema-on-read saves you from constant migrations. If you control it and all records look alike, schema-on-write documents and enforces it for free.
• Check document size and growth. Documents that are read whole and stay small benefit from locality; documents that grow (appending events forever) get rewritten on every update.
• Remember convergence. PostgreSQL's jsonb with GIN indexes gives you document locality inside a relational schema; a relational store with recursive CTEs can run graph queries at small scale. A second database is a cost, not a default.

Interview angle

• SQL or NoSQL for a new product? Reframe: what are the relationships and access patterns? If the data is tree-shaped and read whole, a document store or a JSON column fits. If there are many-to-many relationships and ad hoc queries, relational. If connections dominate and traversals have variable depth, a graph database. Also weigh operational maturity: a relational database with JSON columns covers most startups without a second system.
• Explain the object-relational impedance mismatch and how ORMs help. Application objects are nested and pointer-linked; relations are flat sets of rows. Translating between them is boilerplate and a source of bugs (N+1 queries, lazy-loading surprises). ORMs generate the boilerplate but cannot change the fact that a tree becomes several tables and a join, so you still design the schema and understand the SQL it emits.
• Why store region_id instead of the region name? Normalization. A human-meaningful string may change, has spelling and ambiguity problems, cannot be localized, and when duplicated must be updated everywhere. An ID is stable and meaningless to humans, so one table holds the name and everything else references it. The cost is a many-to-one relationship that requires a join at read time.
• Compare schema-on-read with schema-on-write. Schema-on-write enforces structure at insert time, like static typing; migrations are explicit and the data is guaranteed uniform. Schema-on-read interprets structure when reading, like dynamic typing; new fields appear without migration, but every reader must handle every historical shape. Prefer schema-on-read for heterogeneous records or externally dictated formats; otherwise the schema is documentation and a safety net.
• What goes wrong when a document grows without bound? Locality turns into a liability: every read loads the whole document even when you need one field, and every update rewrites it, since in-place modification is only possible when the encoded size does not change. Keep documents small, and split append-heavy data (events, comments) into separate records referenced by ID.
• Why did the relational model beat the CODASYL network model, and what is the lesson for document databases? CODASYL made the application follow hand-chosen access paths, so every new query pattern meant rewriting code. The relational model exposed all data as plain relations and let a query optimizer choose access paths, so adding an index sped up existing queries without code changes. Document databases borrow the hierarchical model's nesting but, crucially, still reference other records by ID and expose declarative query APIs, so they have avoided CODASYL's trap so far.
• Why did MongoDB add the aggregation pipeline when it already had map-reduce? Map-reduce requires two coordinated pure JavaScript functions, which is harder to write than a single query and gives the engine little room to optimize. A declarative pipeline is shorter, easier to read, and lets the database choose execution order, use indexes and parallelize. It is essentially SQL's WHERE and GROUP BY in JSON syntax.
• How would you model and query "friends of friends who live in the same city"? This is a variable-depth many-to-many traversal, ideal for a property graph: (me)-[:FRIEND*2]->(fof)-[:LIVES_IN]->(city)<-[:LIVES_IN]-(me) in Cypher. In SQL it is two self-joins on a friendship table plus a join on residence; fine at fixed depth, but "friends of friends of friends" and beyond needs a recursive CTE and gets slow and verbose.
• Property graph or triple store? They are nearly equivalent models. Property graphs (Neo4j, JanusGraph) treat vertices and edges as first-class objects with properties, and use Cypher or Gremlin. Triple stores treat everything as (subject, predicate, object) statements, use RDF for interoperability across datasets, and are queried with SPARQL. Pick based on ecosystem and whether you need to merge data from many independent sources (RDF's URIs help there).

Pitfalls and misconceptions

• "Document databases are schemaless." There is always a schema; it just lives in the reading code instead of in the database. Schema-on-read means every reader handles every historical shape of the data, forever, unless you migrate.
• Treating locality as free. Whole-document storage is fast when you read the whole document. If you read one field of a 2 MB document, or append to a document on every event, you pay for the whole thing each time.
• Emulating joins in application code without noticing. Multiple round-trips to resolve references are a join, performed by less optimized code with more network latency. If you find yourself doing this a lot, your data has many-to-many relationships and the model is wrong.
• Denormalizing to avoid joins and forgetting the write side. Every duplicated copy must be updated on change, usually without the database's help. Denormalization trades read cost for write complexity and consistency risk; it is not a pure win.
• Assuming ALTER TABLE always means downtime. On PostgreSQL and most engines, adding a nullable column is a metadata change taking milliseconds. The expensive part is backfilling data, which you can defer to read time exactly as a document database would.
• Using human-readable strings as keys. Names, emails and titles change, collide and need localization. Use surrogate IDs and store the string once.
• Reaching for a graph database because the data "has relationships". All data has relationships. Graph databases earn their keep when traversals have variable or unbounded depth and entities are heterogeneous; a social-graph lookup at fixed depth is a self-join in SQL.
• Believing NoSQL means no query language. The trend is the opposite: MongoDB's aggregation pipeline, Cypher, SPARQL and Datalog are all declarative. Imperative map-reduce was a step backward that the ecosystem retreated from.

Key terms

Term	Meaning
Relational model	Data as relations (tables) of tuples (rows); storage layout hidden behind a declarative query language
Document model	Self-contained, nested records (JSON, XML, BSON) stored as a unit
Graph model	Vertices and edges, both carrying properties; relationships are first-class
Impedance mismatch	The translation gap between application objects and relational rows
ORM	Object-relational mapping library that generates the translation layer (Hibernate, ActiveRecord)
Normalization	Removing duplication by storing each fact once and referencing it by ID
Denormalization	Duplicating data to avoid joins, at the cost of update complexity
One-to-many / many-to-one / many-to-many	Relationship cardinalities; trees are one-to-many, references are many-to-one, networks are many-to-many
Foreign key / document reference	An ID pointing at another row or document, resolved at read time
Schema-on-write	Schema enforced when data is written (relational databases)
Schema-on-read	Structure interpreted when data is read; the schema lives in the application code
Locality	Storing data that is read together physically together
Hierarchical model	1960s–70s tree-of-records model (IBM IMS); one parent per record
Network model (CODASYL)	Records with multiple parents linked by pointer-like access paths that applications traverse manually
Access path	The route through linked records an application had to follow to reach data in the network model
Query optimizer	The database component that chooses indexes, join order and algorithms for a declarative query
Declarative query	Specifies the shape of the result, not the steps to compute it (SQL, Cypher, SPARQL, Datalog, CSS)
MapReduce	A programming model using pure map and reduce functions for bulk processing; used as a query mechanism by MongoDB and CouchDB
Property graph	Graph model where vertices and edges have IDs, labels and key-value properties (Neo4j, JanusGraph)
Triple store / RDF	Data as (subject, predicate, object) statements; RDF is the web-oriented standard with URIs as identifiers
Cypher / SPARQL / Datalog	Declarative graph query languages for property graphs, RDF triple stores and rule-based deductive databases respectively
Polyglot persistence	Using several datastores with different models within one application

Further reading

• DDIA, Chapter 2 (reference list at https://github.com/ept/ddia-references).
• Edgar F. Codd, "A Relational Model of Data for Large Shared Data Banks", Communications of the ACM, 1970. The paper that introduced relations, tuples and data independence.
• Michael Stonebraker and Joseph M. Hellerstein, "What Goes Around Comes Around", in Readings in Database Systems, 4th edition, 2005. A history of data models (hierarchical, network, relational, object, XML) arguing that each new model repeats the old debates; the source of the CODASYL argument in this chapter.
• Charles W. Bachman, "The Programmer as Navigator", Communications of the ACM, 1973 (Turing Award lecture). The network-model view from its inventor; read it to understand what the relational model was reacting against.
• Martin Fowler, "Schemaless Data Structures", martinfowler.com, 2013. A short essay on why "schemaless" really means an implicit schema.
• PostgreSQL documentation, "JSON Types" (https://www.postgresql.org/docs/current/datatype-json.html) and "WITH Queries (Common Table Expressions)" for WITH RECURSIVE.
• Neo4j, The Cypher Manual (https://neo4j.com/docs/cypher-manual/current/).
• W3C, "SPARQL 1.1 Query Language" (https://www.w3.org/TR/sparql11-query/) and "RDF 1.1 Turtle".
• Sandeep Parikh and Kelly Stirman, "Schema Design for Time Series Data in MongoDB" (MongoDB blog, 2013). A practical account of the document-growth and locality trade-offs.