Data Models and Query Languages

Designing Data-Intensive Applications · Chapter 2 · Recall lab

Chapter 1 gave you three words to argue with. Chapter 2 gives you one question that decides almost everything downstream: what kinds of relationships does your data actually have? Answer “trees” and the document model fits. Answer “everything relates to everything” and you want a graph. Answer “some of both” and you get the relational model, which is why it has survived thirty years of challengers. Every widget below is the same résumé, seen through a different lens.

The relational model came from Edgar Codd in 1970: data organised into relations (SQL tables), each an unordered collection of tuples (rows). It was a theoretical proposal that many doubted could be implemented efficiently, and by the mid-1980s it had won. Its roots are 1960s–70s mainframe business data processing, transaction processing and batch processing, and the goal that distinguished it from its contemporaries was to hide the internal representation of the data behind a cleaner interface. Competitors came and went: network and hierarchical models in the 70s, object databases around 1990, XML databases in the early 2000s. Each generated hype; none lasted.

The impedance mismatch

Most application code is written in object-oriented languages, so storing data in relational tables requires an awkward translation layer between application objects and tables, rows and columns. The disconnect is called an impedance mismatch, a term borrowed from electronics, where power transfer across a connection is maximized when the output and input impedances match, and a mismatch causes signal reflections and other trouble. ORMs like ActiveRecord and Hibernate cut the boilerplate, but they can’t erase the difference between the models.

The signature exhibit, one résumé, three models

A LinkedIn profile: first_name and last_name appear exactly once per user, so they’re columns. But most people have had several positions, varying amounts of education, and any number of pieces of contact_info. Those are one-to-many relationships, which is to say, the data is a tree. Watch what each model does with that tree.

{
  "user_id":     251,
  "first_name":  "Bill",
  "last_name":   "Gates",
  "summary":     "Co-chair of the Bill & Melinda Gates... Active blogger.",
  "region_id":   "us:91",
  "industry_id": 131,
  "photo_url":   "/p/7/000/253/05b/308dd6e.jpg",
  "positions": [
    {"job_title": "Co-chair", "organization": "Bill & Melinda Gates Foundation"},
    {"job_title": "Co-founder, Chairman", "organization": "Microsoft"}
  ],
  "education": [
    {"school_name": "Harvard University",       "start": 1973, "end": 1975},
    {"school_name": "Lakeside School, Seattle", "start": null, "end": null}
  ],
  "contact_info": {
    "blog":    "http://thegatesnotes.com",
    "twitter": "http://twitter.com/BillGates"
  }
}

-- vertices
(251:Person   {first_name:"Bill", last_name:"Gates"})
(gf:Org       {name:"Bill & Melinda Gates Foundation"})
(ms:Org       {name:"Microsoft"})
(hv:School    {name:"Harvard University"})
(sea:Location {name:"Greater Seattle Area"})

-- edges carry properties too
(251) -[:WORKED_AT {job_title:"Co-chair"}]-> (gf)
(251) -[:WORKED_AT {job_title:"Co-founder, Chairman"}]-> (ms)
(251) -[:STUDIED_AT {start:1973, end:1975}]-> (hv)
(251) -[:LIVES_IN]-> (sea)

And here is the catch that drives the rest of the chapter: normalizing requires many-to-one relationships, many people live in one region, many work in one industry, and many-to-one doesn’t fit the document model nicely. In relational databases, referring to rows in other tables by ID is normal because joins are easy. In document databases, joins aren’t needed for one-to-many trees, and support for joins is often weak. If the database can’t join, you emulate it in application code with multiple queries, moving work out of the database and into your app.

The escalator, data gets more interconnected as you add features

Even if version one fits a join-free document model, features accumulate. Add each one and watch the relationship types change.

IMS worked well for one-to-many relationships, made many-to-many difficult, and didn’t support joins. Developers had to choose between duplicating data or manually resolving references from one record to another. Those 1960s and ’70s problems are very much the problems developers hit with document databases today. Two solutions were proposed, and the “great debate” between them ran through much of the 1970s.

Access paths, and the one insight that decided it

In CODASYL the links between records weren’t foreign keys but something closer to pointers, stored on disk, but pointer-like. The only way to reach a record was to follow a path from a root record along those chains of links: an access path. Simple cases were like walking a linked list. But with many-to-many relationships, several different paths lead to the same record, and the programmer had to hold all of them in their head. Queries were performed by moving a cursor through the database, iterating over record lists and following access paths; even committee members admitted this was like navigating an n-dimensional data space.

Manual access-path selection made the best use of extremely limited 1970s hardware, tape drives, whose seeks are brutally slow. The cost was code that was complicated and inflexible: if you didn’t have a path to the data you wanted, you were stuck. You could add one, but then you had to rewrite a lot of handwritten query code to use it. Changing an application’s data model was hard.

What the relational model did instead was lay all the data in the open: a relation is a collection of tuples, and that’s it. No labyrinthine nesting, no access paths. Read any or all rows matching an arbitrary condition; read a row by designating some columns as a key; insert into any table without worrying about foreign keys. The query optimizer decides which parts of the query run in which order and which indexes to use, those choices are the access path, but they’re made automatically, so you rarely think about them. Want to query in a new way? Declare a new index; existing queries start using it without being rewritten.

So, are document databases repeating history?

Schema flexibility, the word “schemaless” is wrong

Most document databases don’t enforce any schema, so arbitrary keys and values can be added and readers get no guarantees about which fields exist. But the code that reads the data almost always assumes some structure, there is an implicit schema that the database simply doesn’t enforce. The accurate terms are schema-on-read (structure implicit, interpreted when data is read) versus schema-on-write (schema explicit, database ensures conformance on write). The analogy is dynamic runtime type checking versus static compile-time type checking, and, like that debate, there’s no general right answer.

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

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

Data locality, a real advantage with real limits

A document is normally stored as a single continuous string, JSON, XML, or a binary variant like MongoDB’s BSON. If you often need the whole document (to render a page, say), that storage locality is a genuine performance win: the shredded relational version needs multiple index lookups, more disk seeks, more time.

Convergence

The models complement each other, and a hybrid looks like a good route for databases to take. Worth knowing: Codd’s original 1970 description allowed something quite like JSON documents inside a relational schema. He called them nonsimple domains, a value in a row needn’t be a primitive, it could be a nested relation, giving arbitrarily nested trees as values. SQL added roughly that, thirty years later.

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

sharks = σfamily = "Sharks"(animals)

-- σ is the selection
-- operator: keep only
-- tuples matching the
-- condition.

SELECT * FROM animals
WHERE family = 'Sharks';

-- SQL followed the
-- structure of the
-- relational algebra
-- fairly closely.

Imperative code tells the computer to perform certain operations in a certain order. A declarative language specifies only the pattern of the data you want, what conditions results must meet, how they should be transformed, and leaves the how to the optimizer.

The browser proof, CSS versus DOM manipulation

A site about ocean animals. The user is on the sharks page, so that nav item carries class="selected", and you want the title of the selected page to have a blue background. Declaratively that’s li.selected > p { background-color: blue }, all <p> elements whose direct parent is an <li> with class selected. Imperatively, in the core DOM API, it’s a nested loop. Both boxes below start correct. Then move the selection.

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

<!-- XSL: the XPath li[@class='selected']/p is equivalent
     to the CSS selector li.selected > p -->
<xsl:template match="li[@class='selected']/p">
  <fo:block background-color="blue">
    <xsl:apply-templates/>
  </fo:block>
</xsl:template>

MapReduce, neither one thing nor the other

You’re a marine biologist logging an observation record every time you see animals. You want sharks sighted per month. MapReduce is neither declarative nor fully imperative but in between: query logic expressed as snippets of code that the framework calls repeatedly, built on map (collect) and reduce (fold, inject) from functional programming. A limited form is supported by MongoDB and CouchDB for read-only queries across many documents.

{
  observationTimestamp: Date.parse(
    "Mon, 25 Dec 1995 12:34:56 GMT"),
  family:     "Sharks",
  species:    "Carcharodon carcharias",
  numAnimals: 3
}
{
  observationTimestamp: Date.parse(
    "Tue, 12 Dec 1995 16:17:18 GMT"),
  family:     "Sharks",
  species:    "Carcharias taurus",
  numAnimals: 4
}

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" }
  } }
]);

In those three, every vertex is the same kind of thing. But an equally powerful use of graphs is storing completely different types of object in one datastore. Facebook keeps a single graph whose vertices are people, locations, events, checkins and comments, and whose edges say who is friends with whom, which checkin happened where, who commented on which post, who attended which event.

The working example, Lucy and Alain

Two people: Lucy from Idaho, Alain from Beaune, France. Married, living in London. Click any vertex to see how the property graph model stores it.

You can think of a graph store as two relational tables, one for vertices, one for edges:

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);   -- both directions matter

The same question, four query languages

Find the names of all the people who emigrated from the United States to Europe. Precisely: every vertex with a BORN_IN edge to a location within the US and a LIVES_IN edge to a location within Europe, returning each one’s name.

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

PREFIX : <urn:example:>

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

WITH RECURSIVE

  -- in_usa is the set of vertex IDs of all locations within the United States
  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 is the set of vertex IDs of all locations within Europe
  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 is the set of vertex IDs of all people born in the US
  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 is the set of vertex IDs of all people living in Europe
  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 to find those people who were both born in the US *and* live in Europe
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;

/* facts */
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).

Are graph databases CODASYL again?

At first glance the network model looks a lot like the graph model. The answer is no, in four specific ways.

Triple-stores, RDF, and the semantic web

The triple-store model is mostly equivalent to the property graph model with different words. All information is stored as three-part statements: (subject, predicate, object). In (Jim, likes, bananas), Jim is the subject, likes the predicate, bananas the object. The subject is a vertex. The object is one of two things:

@prefix : <urn:example:>.
_:lucy     a       :Person.
_:lucy     :name   "Lucy".
_:lucy     :bornIn _:idaho.
_:idaho    a       :Location.
_:idaho    :name   "Idaho".
_:idaho    :type   "state".
_:idaho    :within _:usa.

@prefix : <urn:example:>.
_: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.

The foundation, Datalog

Much older than SPARQL or Cypher, studied extensively by academics in the 1980s, and less known among engineers, but it matters because it’s the foundation the later languages build on. In practice it’s the query language of Datomic, and Cascalog is a Datalog implementation for querying large datasets in Hadoop. Its data model generalizes the triple store slightly: instead of (subject, predicate, object) you write predicate(subject, object).

Where Cypher and SPARQL jump straight in with SELECT, Datalog takes a small step at a time: you define rules that teach the database new predicates, derived from data or from other rules. Rules can call other rules and recurse, so complex queries are built a piece at a time. Words starting with an uppercase letter are variables. A rule applies when the system finds a match for every predicate on the right-hand side of :-; when it applies, it’s as though the left-hand side were added to the database.

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

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

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

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

Chapter 2 in one breath. Data began as one big tree, the hierarchical model, which couldn’t represent many-to-many relationships, so the relational model was invented to fix that. More recently some applications didn’t fit relations either, and NoSQL diverged in two directions: document databases for self-contained documents with rare relationships between them, and graph databases for the opposite case where anything is potentially related to everything. All three are widely used and each is good in its domain; one model can be emulated in another, but the result is usually awkward, which is why there’s no one-size-fits-all system. Document and graph databases typically don’t enforce a schema, but your application still assumes a structure, so the real question is only whether the schema is explicit on write or implicit on read. Each model brings its own language: SQL, MapReduce, the aggregation pipeline, Cypher, SPARQL, Datalog, plus CSS and XPath as instructive non-database parallels.