Data models and query languages
Relational: one table per kind of thing, joined by user_id
| user_id | first_name | last_name | region_id | industry_id |
|---|---|---|---|---|
| 251 | Bill | Gates | us:91 | 131 |
| id | user_id | job_title | organization |
|---|---|---|---|
| 458 | 251 | Co-chair | Bill & Melinda Gates Foundation |
| 457 | 251 | Co-founder, Chairman | Microsoft |
| id | user_id | school_name | start | end |
|---|---|---|---|---|
| 807 | 251 | Harvard University | 1973 | 1975 |
| 806 | 251 | Lakeside School, Seattle | NULL | NULL |
| id | user_id | type | url |
|---|---|---|---|
| 155 | 251 | blog | http://thegatesnotes.com |
| 156 | 251 | http://twitter.com/BillGates |
Document: the whole profile is one self-contained JSON value
{
"user_id": 251,
"first_name": "Bill", "last_name": "Gates",
"region_id": "us:91", "industry_id": 131,
"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"
}
}A profile is a tree of one-to-many relationships, and JSON writes the tree down directly. Relational tables need a separate table per branch plus joins (or several queries) to put it back together, which is the "impedance mismatch" with application objects.
Blocks on disk touched by this operation
Storing the profile as one value means a single read loads everything, while the relational layout needs an index lookup per table. Locality only helps when you need most of the document: reading one field still loads the whole thing, and an update typically rewrites all of it (red). Try: 40 positions, then "update photo_id".
each profile document carries its own copy of the text
With IDs the human-readable name is stored once, so a rename is one write and nothing can disagree. The cost is a join (or an extra lookup in application code) on every read. Try: denormalized + crash after 2 writes, then rename.
Change: split name into first_name + last_name
ALTER TABLE users ADD COLUMN first_name text; ALTER TABLE users ADD COLUMN last_name text; UPDATE users SET first_name = split_part(name, ' ', 1), last_name = substr(name, strpos(name, ' ') + 1);
users table
Amber = old format, green = new. Try: schema-on-read, deploy, write a user, then untick "handles old documents". In schema-on-write mode, write a user during the migration.
Imperative: you say how
function getSharks() {var sharks = [];for (var i = 0; i < animals.length; i++) {if (animals[i].family === "Sharks") {sharks.push(animals[i]);}}return sharks;}
The SQL text never changes; only the plan does. The loop can't be parallelized or use an index without rewriting it. Try: run each strategy and compare "rows examined" and the order of results.
animals
styles.css
li.selected > p {
background-color: blue;
}Click a heading to move class="selected"
- Sharksclass="selected"
Great white, Mako
- Whales
Humpback, Blue
- Dolphins
Orca, Spinner
- Rays
Manta, Stingray
Try: in script mode, run the script, then select another item. The old blue background stays, because the script ran once and knows nothing about later changes. CSS keeps re-applying the rule, and the browser is free to make that fast.
MapReduce querying
mapreduce-querying1 · input documents (filtered, then mapped)
2 · emitted (key, value) pairs
3 · reduced output
the query
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"
}
);map and reduce must be pure functions: no side effects, no extra queries. That lets the database run them anywhere, in any order, and rerun them after a failure. Try: step through the job, then switch to SQL or the aggregation pipeline, which state the same thing declaratively.
Property graph: vertices and labelled edges, each with properties
The location hierarchy has different depths: London is in England in the UK, Beaune is in Bourgogne in France. The variable-length pattern WITHIN*0.. handles that, which is awkward with SQL joins. Try: step through Lucy, then change "lives in" to North America and see Ken match instead.
Cypher
MATCH
(person) -[:BORN_IN]-> () -[:WITHIN*0..]-> (:Location {name:'United States'}),
(person) -[:LIVES_IN]-> () -[:WITHIN*0..]-> (:Location {name:'Europe'})
RETURN person.nameDeclarative: the database may just as well start from the two location vertices and walk WITHIN edges backwards. The query says what, not how.
Datalog: build the answer from rules
within_recursive(Location, Name) :- name(Location, Name). /* rule 1 */
within_recursive(Location, Name) :- within(Location, Via), /* rule 2 */
within_recursive(Via, Name).
migrated(Name, BornIn, LivingIn) :- name(Person, Name), /* rule 3 */
born_in(Person, BornLoc),
within_recursive(BornLoc, BornIn),
lives_in(Person, LivingLoc),
within_recursive(LivingLoc, LivingIn).
?- migrated(Who, 'United States', 'Europe').Facts are predicate(subject, object). Rules derive new facts from existing ones, and rules can refer to themselves, so you can build complex queries a piece at a time.
Derived facts: within_recursive(Location, Name)
0 factsEach round applies rule 2 to the facts derived so far (new ones are highlighted), one more WITHIN hop each time, until nothing new appears. Try: step round by round and watch "Europe" travel down from countries to cities.
- takeawayDocuments fit trees of one-to-many data that you load all at once, and they give you locality and schema flexibility. They struggle once many-to-one and many-to-many links appear, because then you need joins.
- takeawayNormalize with IDs when facts are shared: one write per change, no drift, at the cost of joins. Schema-on-read doesn't remove the schema, it moves it into application code.
- takeawayDeclarative languages (SQL, CSS, Cypher, SPARQL, Datalog) say what you want and leave how to the engine. That is what lets databases add indexes, parallelism and recursion without your queries changing.
Key concepts · 18
book chapter 2- Relational model
Data organized as relations (tables) of unordered tuples (rows), queried with SQL.
It hides how the data is stored behind a clean interface. The query optimizer, not the developer, decides the access path, so new queries don't need new code paths.
PostgreSQLMySQLSQLite↑ see it in the visualization - Document model
Self-contained documents (usually JSON) that nest their one-to-many children inside.
A good fit when data is a tree that gets loaded all at once, such as a résumé. Weak support for joins makes highly interconnected data awkward.
MongoDBCouchDBRethinkDBEspresso↑ see it in the visualization - Object-relational impedance mismatch
The awkward translation layer between objects in application code and tables of rows.
ORMs reduce the boilerplate but don't hide the difference completely. A JSON document is closer to the objects many applications use.
ActiveRecordHibernate↑ see it in the visualization - One-to-many relationships
One record owning many children, like a user's positions, schools and contact links.
These form a tree. Documents store the tree directly; relational schemas spread it over several tables joined by a foreign key.
↑ see it in the visualization - Storage locality
A document is stored as one contiguous value, so loading the whole thing is a single read.
It only pays off when you need most of the document. Reading one field still loads all of it, and updates usually rewrite all of it, so keep documents small.
Spanner interleaved tablesBigtable column families↑ see it in the visualization - Normalization
Storing each human-meaningful fact once and referring to it by ID everywhere else.
Avoids duplicated text that can drift out of sync and makes renames a single write. The price is a join (or an extra lookup) when reading.
↑ see it in the visualization - Many-to-one relationships
Many records pointing at one shared entity, such as many people living in one region.
They need joins. Relational databases do joins well; with documents the application often has to emulate them with extra queries.
↑ see it in the visualization - Many-to-many relationships
Links in both directions, such as people and the organizations they worked for.
As applications grow, data tends to become more interconnected. That pushes document models toward references and joins, or toward graphs.
↑ see it in the visualization - Schema-on-read vs schema-on-write
Schema-on-read: the structure is implicit and interpreted when data is read. Schema-on-write: the database enforces an explicit schema.
It's like dynamic vs static typing. Schema-on-read lets old and new formats coexist and handles heterogeneous data; schema-on-write needs migrations but guarantees the shape.
↑ see it in the visualization - Schema migration
Changing a schema, e.g. ALTER TABLE followed by an UPDATE that rewrites existing rows.
Adding a column is usually fast, but rewriting every row of a large table can take a long time and, in some databases, locks the table.
MySQL ALTER TABLE copies the table↑ see it in the visualization - Declarative query languages
You state the pattern of data you want; the database decides how to find it (SQL, CSS, Cypher, SPARQL).
Hides implementation details, so the database can add indexes, reorder work or run in parallel without your query changing.
↑ see it in the visualization - Imperative querying
Code that spells out every step and its order, such as a loop over records.
Hard to parallelize and hard for the system to optimize, because the code fixes the algorithm.
↑ see it in the visualization - MapReduce querying
A query written as a pure map function that emits key/value pairs and a reduce function that combines the values for each key.
Somewhere between declarative and imperative. Pure functions can run anywhere in any order, but writing two coordinated functions is harder than one query, which is why MongoDB added the declarative aggregation pipeline.
MongoDBCouchDBHadoop↑ see it in the visualization - Property graphs
Vertices and edges, each with a label and key-value properties; any vertex can connect to any other.
Very flexible for highly connected, evolving data. New kinds of vertices and edges need no schema change, and traversals follow edges in either direction.
Neo4jTitanInfiniteGraph↑ see it in the visualization - Cypher
Neo4j's declarative graph query language, built around arrow patterns like (a)-[:WITHIN*0..]->(b).
Variable-length paths make walking a hierarchy of unknown depth a single line. The SQL equivalent needs a recursive common table expression.
Neo4j↑ see it in the visualization - Triple-stores
Everything stored as (subject, predicate, object) statements, where the object is either a value or another vertex.
The same graph idea in a uniform format that merges easily. It's the basis of RDF and the semantic web.
DatomicAllegroGraphRDF / Turtle↑ see it in the visualization - SPARQL
The query language for RDF triple-stores, with property paths like :within*.
Even shorter than Cypher for the same query. Cypher's pattern syntax borrows from it.
↑ see it in the visualization - Datalog
A logic language of facts and rules; rules derive new facts and can be recursive.
Older than SQL and the foundation of later graph query languages. Rules compose like functions, so you build up complex queries a piece at a time.
DatomicCascalog↑ see it in the visualization