Data models and query languages

1. Layers of data models

A data model affects two things: how you write the software, and how you think about the problem. This is why it is perhaps the most important part of software design.

Most applications have many layers of data models. Each layer answers one question: how do I represent this thing with the tools of the layer below? Each layer hides the complexity of the layer below it. People in different teams can then work together.

Every data model carries assumptions about how you will use it. Some uses are easy. Some are not possible. Some operations are fast. Some are slow. It takes a lot of effort to learn even one model well. So choose a model that fits your application.

In this chapter you will compare three models: relational, document, and graph. You will also look at the query languages of each model.

2. Relational model and document model

The best-known data model is SQL. It is based on the relational model that Edgar Codd proposed in 1970. Data is in relations (tables in SQL). A relation is an unordered set of tuples (rows in SQL).

In 1970 many people doubted that this could be fast enough. But by the middle of the 1980s, relational databases and SQL were the first choice for data with a regular structure. That is about 25 to 30 years of leadership, which is very long in computing.

The first use cases were business data processing on mainframes:

• Transaction processing: sales, bank transfers, airline reservations, warehouse stock.
• Batch processing: invoices, payroll, reports.

The goal of the relational model was to hide the internal storage details behind a clean interface. Other models from that time (hierarchical, network) forced developers to think about the internal form of the data. Later, object databases (late 1980s) and XML databases (early 2000s) also tried to replace it. They stayed in small niches. The relational model also grew far beyond business data. Much of the web still uses it: publishing, social networks, shops, games, and SaaS tools.

The birth of NoSQL

In the 2010s, NoSQL was the newest attempt to replace the relational model. The name is not a technology. It started in 2009 as a hashtag for a meetup about open-source, distributed, non-relational databases. People later said it means "Not Only SQL".

These forces pushed people toward NoSQL:

• The need for more scalability: very large data sets or very high write rates.
• A preference for free and open-source software.
• Special queries that the relational model does not support well.
• Frustration with the strict relational schema. People wanted a more flexible model.

Different applications have different needs. So the best tool for one job may be wrong for another job. It is likely that relational databases and other stores will be used together. People call this polyglot persistence.

The object-relational mismatch

Most application code uses object-oriented languages. If the data lives in tables, you need an awkward translation layer between objects and rows. This gap is called impedance mismatch. The word comes from electronics, where a bad match between two circuits causes signal loss.

ORM tools (for example ActiveRecord and Hibernate) reduce the boilerplate code. But they cannot hide the difference completely.

Example: a résumé

Think about a profile page like a LinkedIn profile. First name and last name appear once per user, so they fit as columns in a users table. But a person has many jobs, many schools, and many contact items. That is a one-to-many relationship. There are three common ways to store it:

1. Separate tables with a foreign key to users (the classic, normalized way).
2. Structured data types in one row, for example JSON or XML columns. Many SQL databases support this now.
3. One text column with JSON that only the application understands. The database cannot search inside it.

CREATE TABLE users (
  user_id     integer PRIMARY KEY,
  first_name  text,
  last_name   text,
  summary     text,
  region_id   text,
  industry_id integer
);
CREATE TABLE positions (
  position_id integer PRIMARY KEY,
  user_id     integer REFERENCES users (user_id),
  job_title   text,
  organization text
);
CREATE TABLE education (
  education_id integer PRIMARY KEY,
  user_id      integer REFERENCES users (user_id),
  school_name  text,
  start_year   integer,
  end_year     integer
);
CREATE TABLE contact_info (
  contact_id integer PRIMARY KEY,
  user_id    integer REFERENCES users (user_id),
  kind       text,   -- 'blog', 'twitter', ...
  url        text
);

{
  "user_id": 251,
  "first_name": "Asha",
  "last_name": "Rao",
  "summary": "Engineer who writes about open source.",
  "region_id": "in:KA",
  "industry_id": 131,
  "positions": [
    { "job_title": "Staff engineer", "organization": "Northwind" },
    { "job_title": "Engineer",       "organization": "Acme Labs" }
  ],
  "education": [
    { "school_name": "State University", "start": 2012, "end": 2016 }
  ],
  "contact_info": { "blog": "https://example.com/asha" }
}

A résumé is mostly a self-contained document. So JSON fits well. Document databases such as MongoDB, RethinkDB, and CouchDB use this model. JSON is also simpler than XML.

The JSON version has better locality: all the data is in one place, so one query is enough. The relational version needs several queries or a join of many tables.

// Document database: one read.
const profile = await profiles.findOne({ user_id: 251 });

// Relational database: four reads (or one large join).
const user      = await db.one( "SELECT * FROM users        WHERE user_id = $1", [251]);
const positions = await db.many("SELECT * FROM positions    WHERE user_id = $1", [251]);
const education = await db.many("SELECT * FROM education    WHERE user_id = $1", [251]);
const contact   = await db.many("SELECT * FROM contact_info WHERE user_id = $1", [251]);

The one-to-many links (profile to jobs, schools, contacts) form a tree. The JSON format shows this tree clearly.

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

Look at the JSON again. It stores region_id and industry_id as IDs, not as text like "Greater Seattle Area". Why?

When people choose from a standard list (a drop-down), you get these benefits:

• The same style and spelling in all profiles.
• No confusion between cities with the same name.
• Easy update: the name is in one place only.
• Translation: the list can be translated for each language.
• Better search: the list knows that Seattle is in Washington state. A search for "Washington" can find the profile.

The question is about duplication. An ID has no meaning for humans. So it never needs to change, even when the name changes. A text value has meaning for humans. So it may need to change, and every copy must change with it. That costs writes and risks inconsistency, where some copies change and some do not. Removing this duplication is the key idea of normalization.

But normalized data needs many-to-one relationships: many people live in one region, and many people work in one industry. These do not fit well in the document model. In a relational database, you refer to rows in other tables by ID, and joins are easy. In a document database, joins for tree structures are not needed, and join support is often weak. If the database has no join, the application must do the join with several queries. This moves work from the database to your code.

Data becomes more connected over time

A first version may fit a document model without joins. But when you add features, the data gets more links. Think about two changes to the résumé:

• Organizations and schools become entities. Each one gets its own page with a logo and news. A résumé then links to them.
• Recommendations. One user writes a recommendation for another. If the writer changes their photo, the photo must change in every recommendation. So the recommendation must refer to the writer's profile.

The data inside each profile can stay in one document. But the references to organizations, schools, and other users need joins when you read them. Many people link to one organization, and one person links to many organizations. That is many-to-many.

Are document databases repeating history?

The argument about many-to-many links is older than NoSQL. It started in the first database systems.

In the 1970s, the most popular business database was IBM's IMS. It was built for stock control in the Apollo space program and first sold in 1968. It is still in use. IMS used the hierarchical model: all data is a tree of records inside records. This is very close to JSON. It worked well for one-to-many links. It was hard for many-to-many links, and it had no joins. Developers had to choose: copy the data (denormalize), or follow references by hand. Document database users have the same problem today.

Two solutions competed in the 1970s: the network model and the relational model.

The network model (CODASYL)

The network model was a standard from a committee named CODASYL. It allowed a record to have many parents. For example, one "Greater Seattle Area" record could link to all the users who live there. This allowed many-to-one and many-to-many links.

But the links were like pointers in a programming language. The only way to reach a record was to follow a path of links from a root record. This is an access path. A query moved a cursor along these paths. With many parents, several paths could lead to the same record, and the programmer had to remember all of them. Even the committee members said it was like moving in an n-dimensional space.

The result: code was complex and fragile. If you had no path to the data you wanted, you were in trouble. If you changed the paths, you had to rewrite a lot of query code.

The relational model

The relational model put all data in the open. A table is a set of rows. That is all. You can read any rows that match any condition. You can look up a row by key. You can insert a row without thinking about links to other tables.

In a relational database the query optimizer chooses the access path automatically. You do not need to think about it. If you want a new type of query, you add an index. The queries do not change. The optimizer is difficult to build, but you build it once, and then all applications benefit.

Comparison with document databases

Document databases went back to the hierarchical model in one point: they store nested records (one-to-many) inside the parent record. For many-to-one and many-to-many, relational and document databases are not very different. In both, the related item is referenced by a unique ID. It is a foreign key in the relational model and a document reference in the document model. The ID is resolved at read time with a join or a follow-up query. Document databases did not copy CODASYL.

Relational and document databases today

The book compares only the data models here. (Fault tolerance and concurrency come in later chapters.)

Which model gives simpler code?

If your data looks like a document (a tree of one-to-many links that you usually load all at once), a document model is probably a good idea. The relational technique of shredding (splitting a document into many tables) can make the schema and the code more complex than needed.

The document model has limits. You cannot point directly at an item inside a document. You must say "the second item in the positions list of user 251". This is like an access path. It is fine if documents are not deeply nested.

Weak join support may or may not be a problem. An analytics app that records events with timestamps may never need many-to-many links. But if your data has many-to-many links, the document model is less attractive:

• You can reduce joins by denormalizing. Then your code must keep the copies consistent.
• You can do joins in your code with many requests. This is more complex and usually slower than a join inside the database.

The book's rule: for highly connected 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 do not enforce a schema on the documents. You can add any key. When you read, you have no guarantee about the fields.

People say "schemaless", but this is misleading. The code that reads the data assumes a structure. So there is an implicit schema, which the database does not enforce. A better term is schema-on-read: the structure is interpreted when you read. The opposite is schema-on-write: the database checks every write against an explicit schema (the relational way).

The difference is clear when the data format must change. Example: you store the full name in one field, and now you want a first name and a last name.

// New documents have "first_name". Old documents only have "name".
function readUser(doc: any) {
  if (doc.name && !doc.first_name) {
    doc.first_name = doc.name.split(" ")[0];   // handle the old shape on read
  }
  return doc;
}

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

Schema changes have a bad name: slow, with downtime. The book says this is not fully fair. Most relational databases run ALTER TABLE in milliseconds. MySQL was an exception at that time, because it copied the whole table. (Newer MySQL versions improved this. Check the documentation for your version.) The UPDATE on a large table is slow in every database, because every row is rewritten. If this is not acceptable, leave first_name as NULL and fill it in at read time, as with a document database.

When is schema-on-read better? When the items do not all have the same structure:

• There are many types of objects, and one table per type is not practical.
• An outside system decides the structure, and it can change at any time.

When all records have the same structure, a schema is useful. It documents and enforces the structure.

Data locality for queries

A document is usually stored as one continuous string (JSON, XML, or a binary form such as MongoDB's BSON). If you often need the whole document, for example to show it on a web page, this locality is faster than many index lookups and disk seeks.

But there are limits:

• The advantage exists only if you need large parts of the document at the same time.
• The database usually loads the whole document, even if you need a small part.
• When you update, the whole document is usually rewritten. Only changes that keep the same size are easy to do in place.

So keep documents small and avoid writes that make them bigger. This limits the use cases for document databases. Locality is also not only for documents. Google Spanner lets a relational schema declare that child rows are stored inside the parent table. Oracle has multi-table index cluster tables. The column-family idea in Bigtable (used in Cassandra and HBase) has the same aim.

Convergence of the two models

Most relational databases support XML (since the mid-2000s) and JSON (PostgreSQL 9.3, MySQL 5.7, IBM DB2 10.5, as the book lists). Some document databases added joins. So the two types become more similar. This is good, because the models complement each other. A database that handles documents and relational queries lets you choose the best mix.

3. Query languages for data

Declarative and imperative queries

When the relational model came, it also brought a new way to query: SQL is a declarative language. IMS and CODASYL used imperative code.

• Imperative: you tell the computer how, step by step, in a fixed order.
• Declarative: you tell the computer what pattern of data you want: the conditions, and how to sort, group, or total it. You do not say how to get it. The query optimizer decides.

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

SELECT * FROM animals WHERE family = 'Sharks';

The SQL query follows the relational algebra closely. In relational algebra, "select the sharks" is written with the symbol σ (sigma).

Why is the declarative way better?

1. It is shorter and easier to use.
2. It hides the engine. The database can get faster without changes to your queries. Example: the database wants to reclaim free disk space, so it moves records. The order of the animals changes. SQL gives no guarantee about the order, so nothing breaks. In imperative code, the database cannot know if your code depends on the order.
3. It is easier to run in parallel. CPUs now get faster by adding cores, not by higher clock speed. Imperative code with a fixed order is hard to split across cores and machines. A declarative query only describes the result, so the database can choose a parallel plan.

Declarative queries also work in the browser

The same idea helps outside databases. Take a navigation menu. The selected item has the CSS class selected. You want a blue background for the title of the selected page.

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

const items = document.getElementsByTagName("li");
for (let i = 0; i < items.length; i++) {
  if (items[i].className === "selected") {
    for (const child of items[i].childNodes) {
      if (child.nodeType === Node.ELEMENT_NODE && child.tagName === "P") {
        child.setAttribute("style", "background-color: blue");
      }
    }
  }
}

The CSS rule is a pattern. The imperative code has two problems:

• If the user clicks another page and the class is removed, the blue color stays. With CSS, the browser sees that the rule no longer applies and removes the color by itself.
• If a faster API appears, you must rewrite the code. Browser makers can make CSS faster with no change to your code.

MapReduce querying

MapReduce is a model for processing a lot of data on many machines. Google made it popular. Some NoSQL stores (MongoDB, CouchDB) support a limited form of it for read-only queries over many documents. Chapter 10 of the book covers it in detail.

It is between declarative and imperative. You write two small pieces of code, and the framework calls them again and again:

• map is called once for each matching document. It emits key-value pairs.
• The framework groups the pairs by key.
• reduce is called once for each key, with all the values of that key.

Both functions must be pure functions: they use only their input, they do not run other database queries, and they have no side effects. Then the database can run them anywhere, in any order, and run them again after a failure.

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

db.observations.mapReduce(
  function map() {
    const y = this.observedAt.getFullYear();
    const m = this.observedAt.getMonth() + 1;
    emit(y + "-" + m, this.numAnimals);     // key = "2024-11"
  },
  function reduce(key, values) {
    return Array.sum(values);               // add up one month
  },
  { query: { family: "Sharks" }, out: "monthlySharkReport" }
);

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

MapReduce is low level. Two coordinated functions are harder to write than one query, and a declarative language gives the optimizer more room. So MongoDB 2.2 added the declarative aggregation pipeline. It has about the same power as a part of SQL, with a JSON syntax. The lesson: a NoSQL system can end up inventing SQL again, in disguise. Also, SQL does not need one machine: many systems run SQL on a cluster, with or without MapReduce.

4. Graph-like data models

The document model fits trees and records with few links. The relational model handles simple many-to-many links. But when the links are very common and complex, a graph is more natural.

A graph has two kinds of objects: vertices (also called nodes or entities) and edges (also called relationships or arcs).

Known algorithms work on graphs. A car navigation system finds the shortest path in the road graph. PageRank uses the web graph to rank pages for search.

The vertices do not need to be the same type. Facebook keeps one graph with people, places, events, check-ins, and comments as vertices, and with edges such as "is friends with", "happened at", and "commented on".

Property graphs

In the property graph model (used by Neo4j and others), each vertex has:

• a unique ID
• a set of outgoing edges
• a set of incoming edges
• properties (key-value pairs)

Each edge has:

• a unique ID
• a tail vertex (where it starts) and a head vertex (where it ends)
• a label that names the kind of relationship
• properties (key-value pairs)

You can store a property graph in two relational tables:

CREATE TABLE vertices (
  vertex_id  integer PRIMARY KEY,
  properties jsonb
);
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  jsonb
);
CREATE INDEX edges_tails ON edges (tail_vertex);   -- outgoing edges of a vertex
CREATE INDEX edges_heads ON edges (head_vertex);   -- incoming edges of a vertex

Three important points:

1. Any vertex can connect to any other vertex. No schema limits the links.
2. From any vertex you can find both incoming and outgoing edges. So you can walk the graph forward and backward. This is why there are two indexes.
3. Different labels let you store different kinds of facts in one graph, with a clean model.

This gives great flexibility. Figure 5 shows things that are hard in a classic relational schema: different region structures in different countries, a country inside another structure, and different levels of detail. You can extend the graph with more facts. For example, add a vertex for each food allergen, link people to the allergens, and link allergens to foods. Then you can query what is safe for each person to eat. Graphs are good for evolvability.

Cypher and SQL: the same query

Cypher is a declarative query language for property graphs. It was made for the Neo4j database. The name comes from a character in the movie The Matrix. It has nothing to do with cryptography.

CREATE
  (Asia:Location   {name: 'Asia',   type: 'continent'}),
  (India:Location  {name: 'India',  type: 'country'}),
  (Kerala:Location {name: 'Kerala', type: 'state'}),
  (Maya:Person     {name: 'Maya'}),
  (Kerala) -[:WITHIN]-> (India) -[:WITHIN]-> (Asia),
  (Maya)   -[:BORN_IN]-> (Kerala)

The arrow (Kerala) -[:WITHIN]-> (India) creates an edge with the label WITHIN.

Now a question: who was born in India and lives in Europe? This needs a path of variable length. A person may be born in a city, and the city is within a state, which is within a country. How many steps? You do not know in advance. In Cypher, :WITHIN*0.. means "follow a WITHIN edge zero or more times". It is like * in a regular expression.

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

WITH RECURSIVE
  in_india(vertex_id) AS (
    SELECT vertex_id FROM vertices WHERE properties->>'name' = 'India'
    UNION
    SELECT e.tail_vertex FROM edges e
      JOIN in_india i ON e.head_vertex = i.vertex_id
     WHERE e.label = 'within'
  ),
  in_europe(vertex_id) AS (
    SELECT vertex_id FROM vertices WHERE properties->>'name' = 'Europe'
    UNION
    SELECT e.tail_vertex FROM edges e
      JOIN in_europe i ON e.head_vertex = i.vertex_id
     WHERE e.label = 'within'
  )
SELECT p.properties->>'name'
FROM vertices p
JOIN edges b ON b.tail_vertex = p.vertex_id AND b.label = 'born_in'
JOIN in_india  ON b.head_vertex = in_india.vertex_id
JOIN edges l ON l.tail_vertex = p.vertex_id AND l.label = 'lives_in'
JOIN in_europe ON l.head_vertex = in_europe.vertex_id;

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

within_recursive(Loc, Name) :- name(Loc, Name).
within_recursive(Loc, Name) :- within(Loc, Via),
                               within_recursive(Via, Name).

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

?- migrated(Who, 'India', 'Europe').    % Who = 'Maya'.

Compare the lengths. Cypher and SPARQL need about 3 to 5 lines. SQL needs about 20 lines. The book's version of this comparison is 4 lines against 29 lines. SQL can do it, but with difficulty. Since SQL:1999, a recursive common table expression (WITH RECURSIVE) can do variable-length paths. The book says: different data models serve different use cases, so choose the model that fits your application.

A declarative language lets the database choose how to run the query. In the emigrant query, one plan scans all people and checks the birthplace and the home of each. Another plan starts at the two location vertices ("India" and "Europe"), walks backward over incoming WITHIN edges to find all places inside them, and then finds the people. You do not choose. The optimizer does.

Triple-stores and SPARQL

The triple-store model is mostly the same as the property graph model, with different words. It stores all data as three-part statements: (subject, predicate, object). Example: (Maya, likes, mangoes).

The subject is like a vertex. The object is one of two things:

1. A simple value (a string or a number). Then the predicate and object are like a property key and value. Example: (maya, age, 33) is a vertex maya with the property age: 33.
2. Another vertex. Then the predicate is an edge. Example: (maya, marriedTo, louis).

@prefix : <urn:example:> .
_:maya   a :Person;   :name "Maya";   :bornIn _:kerala .
_:kerala a :Location; :name "Kerala"; :type "state";     :within _:india .
_:india  a :Location; :name "India";  :type "country";   :within _:asia .
_:asia   a :Location; :name "Asia";   :type "continent" .

The semicolon lets you say many things about the same subject. The names like _:maya only help to show which triples talk about the same vertex.

The semantic web

If you read about triple-stores, you will find many articles about the semantic web. The triple model does not depend on it. The idea is simple: websites already publish text and pictures for humans, so they could also publish machine-readable data in one common format (RDF). Then computers could join the data from many sites into a "database of everything". This was overhyped in the early 2000s, and it did not happen in practice. But there is good work from this project. Triples can be a good internal data model for an application, even if you never publish RDF.

RDF has a quirk: subjects, predicates, and objects are often URIs, such as http://my-company.com/ns#within. The reason is that you can combine your data with data from others. If they give a different meaning to "within", the names do not clash, because their URI is different.

SPARQL (pronounced "sparkle") is the query language for RDF triple-stores. It is older than Cypher, and Cypher borrowed its pattern matching from SPARQL. In SPARQL, variables start with a question mark. See the SPARQL tab above.

The foundation: Datalog

Datalog is much older (academic work in the 1980s). It is less known, but it is the foundation for later languages. Datomic uses it. Cascalog uses it for large data sets in Hadoop. It is a subset of Prolog.

Datalog writes a triple as predicate(subject, object).

name(asia, 'Asia').       type(asia, continent).
name(india, 'India').     type(india, country).    within(india, asia).
name(kerala, 'Kerala').   type(kerala, state).     within(kerala, india).
name(maya, 'Maya').       born_in(maya, kerala).

Datalog goes in small steps. You define rules that create new predicates from data or from other rules. Rules can use other rules, like functions that call functions. Variables start with an uppercase letter. A rule applies when the system can match all the parts on the right of :-. Then it is as if the left side were added to the database.

Datalog is less convenient for a quick one-off query. But rules can be combined and reused, so it copes better when the data is complex.

5. Summary and glossary

History: data started as one big tree (hierarchical model). It was bad for many-to-many links, so the relational model came. Later, some applications did not fit the relational model, and NoSQL stores went in two directions:

1. Document databases for self-contained documents, with rare links between documents.
2. Graph databases for the opposite case: anything can relate to anything.

All three models are in wide use today. One model can imitate another (a graph in a relational database), but the result is often awkward. That is why we have different systems for different jobs.

Document and graph databases usually do not enforce a schema. But your code still assumes a structure. The only question is: is the schema explicit (checked on write) or implicit (handled on read)?

Compare the three models

The chapter also names models that it does not cover. Genome research needs sequence-similarity search, which none of these databases do. The Large Hadron Collider handles hundreds of petabytes and needs custom solutions. Full-text search is a data model that people often use next to a database. The next chapter explains how databases store and find data.

Glossary

6. Check yourself

Next in the book: Chapter 3, Storage and Retrieval. It explains how databases store data on disk and find it again: log-structured storage, B-trees, and the difference between transaction processing and analytics.