NoSQL: Document, Key-Value, Graph

One shop, four filing systems 🗂️

An online shop keeps its orders in a relational database, and that works well. Then three new problems arrive. The product catalogue needs different fields for every kind of product: a T-shirt has sizes and a colour, a laptop has memory and cores. Login sessions and shopping carts are read thousands of times per second, always by their id and nothing else. And the "people you may know" feature has to walk friendships two or three hops deep.

Each problem fits a different kind of store. NoSQL ("not only SQL") is the umbrella name for databases that do not use the relational table model. Many of them have a query language too, but they organise data around a different idea.

What you'll learn

• The four main families: key-value, document, wide-column and graph stores, and what each is good at
• How a document database is queried (nested fields, arrays, operators)
• Embedding versus referencing, and why access patterns drive NoSQL schema design
• The trade-offs against SQL: consistency, transactions, joins and schema

The labs are in Python: you write a MongoDB-style query matcher, shape relational rows into an order document, and run a friends-of-friends graph query.

The four families

• Key-value stores are a giant dictionary: a key points to a value the database does not look inside. You GET, SET and DELETE by key, often with an expiry time (TTL). Examples: Redis, Memcached, Amazon DynamoDB. Good for sessions, carts, caches, counters and feature flags. Weak at any question other than "give me the value for this key".
• Document stores keep self-contained documents (JSON-like; MongoDB stores a binary form called BSON) with nested objects and arrays. Documents in one collection need not share the same fields. You can query and index any field. Examples: MongoDB, Couchbase, Firestore. Good for aggregates that are read and written together, such as an order with its lines.
• Wide-column stores group rows into partitions by a partition key and keep the rows of a partition sorted, spreading partitions across many machines. Examples: Apache Cassandra, ScyllaDB, Apache HBase, Google Bigtable. Good for huge write volumes: event logs, sensor readings, chat messages.
• Graph databases store nodes and relationships (edges), both with properties, and queries walk the relationships. Examples: Neo4j (query language Cypher) and Amazon Neptune; ISO standardised a graph query language, GQL, as ISO/IEC 39075:2024. Good for social networks, recommendations, fraud rings and dependency graphs.

The same fact, "Amal ordered two notebooks", in each shape:

key-value    "cart:amal"  ->  "notebook x2"                  (an opaque value)
document     { _id: "amal", name: "Amal", orders: [ { item: "notebook", qty: 2 } ] }
wide-column  partition "amal" | 2025-03-02 -> notebook x2 | 2025-03-09 -> pen x5
graph        (Amal:Person) -[:ORDERED {qty: 2}]-> (Notebook:Product)

Querying a document store

In MongoDB you query a collection with a query document: you describe the documents you want, field by field.

db.products.find({ category: "laptop", price: { $lt: 2000 } })  // every field must match (AND)
db.products.find({ "specs.ram_gb": 32 })      // dot notation reaches into embedded documents
db.products.find({ tags: "work" })            // matches when the tags array CONTAINS "work"
db.products.find({ category: { $in: ["home", "clothing"] } })
db.products.createIndex({ category: 1, price: 1 })   // secondary indexes, as in SQL

Three rules make this work:

• A query document is an implicit AND: a document matches only if every listed field matches.
• A dotted path such as "specs.ram_gb" follows embedded objects. A document without that path does not match a value or a comparison (one exception: { field: null } also matches documents that lack the field).
• A plain value matches an array field when any element equals it. Operators such as $gt, $gte, $lt, $lte and $in take an object instead of a value.

"Schemaless" really means schema-on-read. The database will accept a product with prise instead of price, but your code will not find it. The structure still exists, it just lives in your application, so serious projects add validation (MongoDB supports $jsonSchema validators) and handle documents written in older shapes.

Embed or reference?

The biggest design decision in a document database is whether related data lives inside a document (embedding) or in another document that you point to by id (referencing).

Embedded: one read shows the page            Referenced: one read per document
orders: {                                     orders:    { _id: 1001, customer_id: 7, line_ids: [...] }
  _id: 1001,                                  customers: { _id: 7, name: "Amal", email: ... }
  customer: { id: 7, name: "Amal" },          lines:     { _id: 31, order_id: 1001, product: ... }
  lines: [ { product: "Notebook", qty: 2 },
           { product: "Pen", qty: 5 } ]
}

Embed when the data is read together, the relationship is one-to-few, the child has no life of its own (an order line without its order), and its size stays bounded.

Reference when the relationship is many-to-many, the list can grow without limit (the comments of a viral post: MongoDB caps a document at 16 MiB), or the data is shared and updated on its own (a customer's email).

A useful middle way is the extended reference: store the id plus the few fields the page shows, such as { id: 7, name: "Amal" }. Every copy is redundancy, though, and the update anomaly from the normalization lesson comes back: if Amal changes her name, every copy must be found and fixed. Copy only what rarely changes, or what should be frozen, like the price an order was paid at.

Access patterns come first

In a relational database you normalize first and can then ask almost any question with joins. In most NoSQL stores, joins are limited or missing, so you work the other way round:

1. List the queries the application runs most: "show an order page", "list a customer's last 10 orders".
2. Shape the data so each frequent query reads one document or one partition.
3. Accept duplication where it buys those fast reads, and keep it in sync on purpose.

That is why a Cassandra design often has one table per query. DynamoDB reaches the same goal another way: AWS recommends as few tables as possible, in most cases a single table whose keys are designed so that each access pattern reads one partition. Either way, a design that is perfect for one access pattern can be painful for a question nobody planned.

Key-value, wide-column and graph in practice

Key-value (Redis): the key design is the schema. Names like session:<id> and rate:<user> make it obvious what lives where.

SET session:9f2c '{"user":"amal"}' EX 1800   # value with a 30-minute expiry
GET session:9f2c
INCR rate:amal                                # atomic counter, no read-modify-write race
EXPIRE rate:amal 60

Wide-column (Cassandra, CQL): the partition key decides which machines store a row, and the clustering column sorts rows inside the partition. Queries are expected to name the partition key; anything else means scanning the cluster.

CREATE TABLE messages_by_room (
    room_id     text,
    message_id  timeuuid,          -- time-based id: sorts by time and never collides
    author      text,
    body        text,
    PRIMARY KEY ((room_id), message_id)
) WITH CLUSTERING ORDER BY (message_id DESC);

SELECT author, body FROM messages_by_room WHERE room_id = 'general' LIMIT 50;

Graph (Neo4j, Cypher): relationships are stored as first-class data, so a query that hops through friends of friends follows them directly instead of joining a big table to itself again and again.

MATCH (me:Person {name: "Amal"})-[:FRIEND]-(f:Person)-[:FRIEND]-(fof:Person)
WHERE fof <> me AND NOT (me)-[:FRIEND]-(fof)
RETURN fof.name AS suggestion, count(f) AS mutual
ORDER BY mutual DESC, suggestion

The trade-offs against SQL

• Scaling out. Many NoSQL systems were built to spread data over many machines (sharding) from day one. Relational databases scale up well and can be sharded too, with more effort.
• Consistency. Distributed stores often copy data asynchronously, so a read may briefly return old data (eventual consistency); Cassandra lets each query choose a consistency level such as ONE, QUORUM or ALL. The CAP theorem (Brewer's conjecture, proved by Gilbert and Lynch in 2002) says that during a network partition a distributed store must choose between staying consistent and staying available.
• Transactions. Support varies: MongoDB has multi-document ACID transactions (since 4.0 for replica sets, 4.2 for sharded clusters), Redis has MULTI/EXEC, and Cassandra's lightweight transactions are compare-and-set on one partition. Ask exactly which ACID guarantees you get.
• Joins and new questions. Limited or costly; a question nobody planned may need a new document shape or table.
• Schema. Flexible to write, but the schema moves into your code, and documents in old shapes stay until you migrate them.

The line is blurry: PostgreSQL's jsonb type (with GIN indexes) and SQLite's JSON functions give relational databases document features. A sensible default is a relational database, adding a specialised store when a concrete access pattern needs it. Using several stores side by side is called polyglot persistence, and its price is running and securing several systems.

Recap and what to practice next

• Key-value stores answer "the value for this key" very fast, with TTLs and atomic counters. Document stores keep nested, flexible documents you can query and index by any field. Wide-column stores partition rows across machines for huge write volumes. Graph databases follow relationships directly.
• Document queries are an implicit AND; dotted paths reach into embedded documents, and a plain value matches an array when any element matches.
• Embed data that is read together, one-to-few and bounded; reference data that is shared, many-to-many or unbounded; the extended reference copies only what the page shows.
• NoSQL design starts from access patterns: shape the data so each frequent query reads one document or one partition, and own the duplication you create.
• Compared with SQL you often gain scale-out and flexibility, and pay with weaker or narrower transactions, limited joins and a schema that lives in your code.

Practice next: extend the query lab with $ne and $exists. In the order lab, add a second access pattern, "a customer's orders", and decide whether it needs its own document shape. Then turn to protecting data: whatever the model, the next lessons cover keeping it safe from attackers and from accidents.