NoSQL Databases

Learning Objectives

By the end of this page, you should be able to:

• Explain why relational databases hit scaling limits and how NoSQL systems address them.
• State the CAP theorem and reason about the Consistency/Availability/Partition-tolerance trade-off for a given system.
• Identify the four major NoSQL categories, name a real system for each, and sketch their data model.
• Contrast BASE properties with ACID and explain what "eventual consistency" actually means.
• Describe how sharding achieves horizontal scalability.
• Decide, for a given scenario, whether a relational or NoSQL database is the better fit, and justify the choice.

Quick Answer

NoSQL ("Not Only SQL") databases are non-relational data stores built to handle scale, flexible/changing data shapes, and distributed deployment better than traditional relational databases — often by relaxing strict consistency guarantees. They emerged because relational databases scale vertically (bigger machine) and struggle to scale horizontally (more machines) while keeping ACID guarantees across a distributed cluster. The CAP theorem explains why: a distributed system can't have perfect Consistency, Availability, and Partition tolerance simultaneously, so NoSQL systems typically favor availability and partition tolerance, accepting eventual rather than immediate consistency (BASE instead of ACID). There are four major families — key-value (Redis, DynamoDB), document (MongoDB), column-family (Cassandra, HBase), and graph (Neo4j) — each optimized for a different access pattern. Choose NoSQL when you need massive horizontal scale, flexible/evolving schemas, or a data shape (documents, graphs) that maps awkwardly onto tables; choose relational when you need strong consistency and complex multi-table transactions, like banking.

Why NoSQL Emerged: The Scaling Problem

Relational databases were designed in an era of single, powerful machines. When traffic grows, the traditional answer is vertical scaling — buy a bigger server with more CPU, RAM, and disk. That works until it doesn't: there's a hard ceiling on how big one machine can get, and the biggest machines are disproportionately expensive.

The alternative is horizontal scaling — add more (cheaper, commodity) machines and spread the data and load across them. Relational databases resist this because their core value proposition is strong consistency enforced by joins, foreign keys, and multi-row transactions — all of which become expensive or fragile once your rows live on different machines that must coordinate over a network. A JOIN across a table sharded over ten servers means shuffling data across the network for every query; a transaction touching rows on three different nodes means those nodes must agree before committing, which slows everything down and creates failure modes a single-machine database never has to think about.

Web-scale companies (Google, Amazon, Facebook) hit this wall in the early-to-mid 2000s: millions of users, globally distributed, needing to stay up even when individual servers or entire data centers failed. Their answer was to build data stores that gave up some relational guarantees — rigid schemas, multi-row transactions, immediate consistency — in exchange for the ability to scale horizontally across thousands of cheap machines and stay available during failures. That trade-off is NoSQL.

The CAP Theorem

The CAP theorem (Eric Brewer) formalizes the trade-off any distributed data store must make. It says a distributed system can provide at most two of these three guarantees at the same time:

• Consistency (C): every read receives the most recent write, or an error. All nodes see the same data at the same time.
• Availability (A): every request receives a (non-error) response, even if it isn't the most recent write.
• Partition tolerance (P): the system keeps working even when network failures split it into groups of nodes that can't talk to each other.

Here's the concrete reasoning: network partitions will happen in any real distributed system — a switch fails, a data center loses connectivity, a cable gets cut. Once partitioned, each side of the split has to decide: do I keep answering requests (favoring Availability) even though I might be out of sync with the other side, or do I refuse to answer until I can confirm I'm consistent with the other side (favoring Consistency)? You cannot have both during the partition. So in practice, the real design choice for any distributed database is CP vs. AP — partition tolerance is non-negotiable for a distributed system, so you're really choosing what happens when the network fails.

• A CP system (e.g., MongoDB in its default configuration, HBase) will refuse to serve a read/write on a partitioned node rather than risk returning stale or conflicting data — it sacrifices availability for correctness.
• An AP system (e.g., Cassandra, DynamoDB) will keep serving reads and writes on both sides of a partition, and reconcile the conflicting data later — it sacrifices immediate consistency for uptime.

A concrete example: imagine a shopping cart service split across two data centers, and the link between them goes down. An AP design (like DynamoDB, which Amazon originally built for exactly this) lets both data centers keep accepting "add to cart" requests independently, then merges the two carts once the network heals — a customer might briefly see a slightly stale cart, but checkout never goes down. A CP design would instead block writes on one side until the partition resolves, guaranteeing correctness but disappointing users who can't add items during an outage.

BASE vs. ACID

Where relational databases promise ACID (Atomicity, Consistency, Isolation, Durability), most NoSQL systems instead promise BASE:

• Basically Available: the system guarantees availability, in the CAP sense — it will respond, even under failure.
• Soft state: the state of the system may change over time, even without new input, as replicas converge toward the same value.
• Eventual consistency: if no new updates are made, all replicas will eventually return the same (correct) value — but not necessarily right now.

The mental model: ACID databases treat every read as "give me the truth, right now, guaranteed" — worth the coordination cost for money transfers. BASE databases treat every read as "give me a reasonably recent answer, fast, and don't go down" — the right trade for a social media like-count or a product view counter, where a one-second-stale number costs nothing but downtime costs real money.

The Four Major NoSQL Categories

1. Key-Value Stores

The simplest possible model: every item is a unique key mapped to an opaque value (a string, blob, or serialized object). The database doesn't inspect or query inside the value — it just stores and retrieves by key, which is why lookups are extremely fast.

Redis example — storing and reading a user session:

SET session:8291 '{"user_id": 42, "cart_items": 3}'
EXPIRE session:8291 3600
GET session:8291

DynamoDB example — a key-value item with a partition key:

PutItem(table="Sessions", key={"session_id": "8291"}, value={...})
GetItem(table="Sessions", key={"session_id": "8291"})

Advantages: sub-millisecond reads/writes, trivial horizontal scaling (the key determines which shard owns it), simple mental model. Limitation: you generally can't query by anything other than the key — no "find all sessions with cart_items > 2" without scanning everything. Best fit: caching, session storage, shopping carts, real-time leaderboards.

2. Document Stores

Data is stored as self-contained documents (usually JSON/BSON), each of which can have a different shape from the next. Related data is often embedded inside a document instead of being split across tables and joined.

MongoDB example document for a blog post:

{
  "_id": "post_501",
  "title": "Understanding CAP Theorem",
  "author": { "name": "Priya Menon", "email": "priya@example.com" },
  "tags": ["databases", "distributed-systems"],
  "comments": [
    { "user": "raj99", "text": "Great explanation!", "likes": 4 },
    { "user": "dev_anu", "text": "Clarified CP vs AP for me.", "likes": 2 }
  ],
  "published": true
}

Querying it:

db.posts.find({ tags: "distributed-systems", published: true })
db.posts.insertOne({ title: "New Post", author: {...}, tags: [] })
db.posts.updateOne({ _id: "post_501" }, { $push: { comments: { user: "x", text: "Nice!" } } })

Notice the author and comments are embedded rather than living in separate authors and comments tables joined by foreign keys — one query retrieves the whole post with everything needed to render it. Advantages: flexible schema (documents in the same collection can differ), natural mapping to how applications already think in objects, no join overhead for embedded data. Limitation: relationships across documents (e.g., "all posts by this author" when authors are a separate collection) still require something join-like, which document databases handle less gracefully than relational ones. Best fit: content management, catalogs, user profiles — anything with nested, variably-shaped records.

3. Column-Family Stores

Data is organized by column families rather than rows, and optimized for very high write throughput across huge, sparse datasets spread over many machines. Conceptually, think of each row as having a row key, and then a flexible set of columns — different rows can have entirely different columns, unlike a fixed-width relational table.

Cassandra-style wide-column example, storing sensor readings keyed by sensor ID and timestamp:

Row key: sensor_42
  timestamp:2026-07-01T10:00 -> {temp: 21.4, humidity: 55}
  timestamp:2026-07-01T10:05 -> {temp: 21.6}
  timestamp:2026-07-01T10:10 -> {temp: 21.5, humidity: 54, battery: 87}

-- Cassandra Query Language (CQL) -- looks like SQL but the underlying model is column-family
SELECT * FROM sensor_readings WHERE sensor_id = 'sensor_42' AND reading_time > '2026-07-01T10:00';

Notice the second row simply omits humidity, and the third adds a battery column no earlier row had — that sparseness is normal and cheap. Advantages: extremely high write throughput, linear horizontal scalability (rows are distributed by row key across a ring of nodes), good compression of sparse data. Limitation: query flexibility is limited — you generally design the table around the queries you'll run (query-first modeling), and ad hoc analytical queries across the whole dataset are painful. Best fit: time-series data (IoT sensor streams), write-heavy logging, and systems needing to ingest huge volumes of data continuously, like Facebook's Cassandra-backed inbox search, historically.

4. Graph Databases

Data is modeled explicitly as nodes (entities) and relationships (edges), often with properties on both. This is the natural fit when the relationships themselves — not just the entities — are what you need to query efficiently.

Neo4j example: a small social graph.

(Alice:Person)-[:FRIENDS_WITH]->(Bob:Person)
(Bob:Person)-[:FRIENDS_WITH]->(Chen:Person)
(Alice:Person)-[:LIKES]->(Post:Content {title: "CAP Theorem Explained"})

Querying with Cypher — "find friends-of-friends of Alice who aren't already her friend":

MATCH (alice:Person {name: "Alice"})-[:FRIENDS_WITH]->(:Person)-[:FRIENDS_WITH]->(fof:Person)
WHERE NOT (alice)-[:FRIENDS_WITH]->(fof) AND alice <> fof
RETURN DISTINCT fof.name

In a relational database, this same query requires a multi-way self-join on a friendships table, which gets slower as the graph gets deeper (friends-of-friends-of-friends...). A graph database stores relationships as first-class pointers, so traversing them is a fast, local operation regardless of how large the overall dataset is. Advantages: natural fit for highly interconnected data, fast multi-hop traversal, intuitive query language for relationship-heavy questions. Limitation: less efficient for simple, non-relational bulk operations (e.g., "sum a column across a million rows") than a column-family or relational store. Best fit: social networks, recommendation engines, fraud detection (tracing suspicious chains of transactions), knowledge graphs.

Sharding and Horizontal Scaling

Sharding is how NoSQL systems achieve horizontal scale: the dataset is split into partitions ("shards"), and each shard is stored on a different machine. A shard key (or partition key) determines which shard a given piece of data lives on — for example, user_id % number_of_shards, or a hash of the document's _id.

Each shard handles only its slice of the data and traffic, so adding more shards (more machines) increases total capacity roughly linearly — unlike vertical scaling, which hits a ceiling on a single machine. The trade-off: queries that need data from multiple shards (e.g., "find the top 10 users globally by score") are more expensive, since the coordinator has to fan the query out to every shard and merge results. This is exactly why NoSQL schema design is often "query-first" — you choose your shard key based on how you'll actually query the data, not based on normalized theoretical structure.

Choosing NoSQL vs. Relational: Concrete Scenarios

• Banking ledger: relational. You need multi-row ACID transactions (debit one account, credit another, atomically) and strict consistency — a stale balance is unacceptable.
• Product catalog for an e-commerce site with wildly different attributes per category (a shirt has size/color, a laptop has RAM/CPU): document store. Forcing every product into one fixed table means either dozens of nullable columns or a fragile EAV (entity-attribute-value) pattern; a document naturally holds "whatever attributes this product has."
• IoT platform ingesting millions of sensor readings per second: column-family store. Extremely high write throughput and time-ordered access patterns are exactly what Cassandra/HBase are built for.
• Social network friend/follow graph and "people you may know" recommendations: graph database. Multi-hop relationship queries are what graph databases are optimized for; the same query on a relational self-join table degrades badly as hops increase.
• Session cache in front of a web application: key-value store. You just need fast lookup-by-key with automatic expiry; no query complexity is needed.
• Regulatory/compliance reporting requiring complex multi-table joins and audit trails: relational. Ad hoc analytical SQL across normalized tables is still what relational databases do best.

Key Terms

Term	Definition
NoSQL	A broad category of non-relational databases designed for horizontal scale, flexible schemas, or specialized data shapes (key-value, document, column-family, graph).
CAP Theorem	The principle that a distributed data store can guarantee at most two of Consistency, Availability, and Partition tolerance at once.
BASE	Basically Available, Soft state, Eventual consistency — the consistency model most NoSQL systems favor over strict ACID.
Eventual Consistency	A guarantee that, absent new writes, all replicas of a piece of data will converge to the same value over time.
Sharding	Splitting a dataset into partitions ("shards") distributed across multiple machines to scale horizontally.
Shard Key	The field (or hash of it) used to decide which shard a given record belongs to.
Key-Value Store	A NoSQL model that maps unique keys directly to opaque values, optimized for fast lookups (e.g., Redis, DynamoDB).
Document Store	A NoSQL model that stores flexible, often nested JSON-like documents, allowing different shapes per record (e.g., MongoDB).
Column-Family Store	A NoSQL model that organizes sparse data by row key and flexible column groups, optimized for massive write throughput (e.g., Cassandra, HBase).
Graph Database	A NoSQL model that stores entities as nodes and relationships as first-class edges, optimized for traversal queries (e.g., Neo4j).
Horizontal Scaling	Increasing capacity by adding more machines, as opposed to vertical scaling (a bigger single machine).

Common Mistakes

Misconception 1: "NoSQL means 'no schema at all.'" Why it's wrong: Document and column-family stores don't enforce a rigid schema up front, but the data still has structure — application code still expects certain fields to exist, and inconsistent documents cause bugs just as surely as a broken relational schema would. Correct understanding: NoSQL databases have a flexible or schema-on-read structure rather than no structure — the schema still exists conceptually, it's just enforced by convention and application logic instead of the database engine.

Misconception 2: "NoSQL databases are always faster than relational databases." Why it's wrong: Speed depends entirely on the access pattern. A well-indexed relational query on structured data can easily outperform a poorly-modeled NoSQL query that has to scan across shards. NoSQL's speed advantage comes from horizontal scalability and avoiding cross-machine joins for specific access patterns, not from some inherent property of being "not SQL." Correct understanding: NoSQL systems are optimized for particular access patterns (key lookup, document retrieval, graph traversal, high-throughput writes) — they aren't universally faster, they're differently optimized.

Misconception 3: "Eventual consistency means the data is often wrong." Why it's wrong: Eventual consistency doesn't mean data is incorrect — it means that immediately after a write, different replicas might briefly return different (but each individually valid, previously-written) values, until replication catches up, usually within milliseconds to seconds. Correct understanding: Eventual consistency is a deliberate, bounded trade-off for availability and partition tolerance — it's a guarantee about when all replicas converge, not a statement that the database is unreliable.

Comparison and Connections

The Four NoSQL Categories

Category	Data Model	Real Systems	Query Style	Best Suited For
Key-Value	Key → opaque value	Redis, DynamoDB, Memcached	GET key, SET key value	Caching, sessions, leaderboards
Document	Nested JSON/BSON documents	MongoDB, CouchDB	find(), filter on nested fields	Catalogs, CMS, user profiles
Column-Family	Row key + flexible column groups	Cassandra, HBase	CQL, query-first table design	Time-series, high-volume writes
Graph	Nodes + relationship edges	Neo4j, Amazon Neptune	Cypher / Gremlin traversal	Social graphs, recommendations, fraud detection

ACID vs. BASE

Aspect	ACID (Relational)	BASE (Most NoSQL)
Consistency	Strong — every read sees the latest committed write	Eventual — replicas converge over time
Availability under partition	May be sacrificed to preserve consistency	Usually prioritized
Transaction scope	Multi-row, multi-table transactions supported	Often limited to single-document/single-row atomicity
Typical use case	Banking, inventory counts, anything needing exact correctness	Social feeds, caches, high-scale write-heavy systems

SQL vs. NoSQL

Feature	Relational (SQL)	NoSQL
Schema	Fixed, enforced at write time	Flexible, often enforced by application
Scaling	Primarily vertical	Primarily horizontal (sharding)
Consistency	Strong (ACID) by default	Eventual (BASE) by default, tunable in some systems
Relationships	Foreign keys and joins	Embedding (document), edges (graph), or denormalization
Best fit	Complex transactions, structured reporting	Massive scale, flexible/evolving data, specialized access patterns

Practice Questions

Recall

1. What do the letters in BASE stand for? Answer guidance: Basically Available, Soft state, Eventual consistency.
2. Name the four major categories of NoSQL databases and one real system for each. Answer guidance: Key-value (Redis/DynamoDB), Document (MongoDB), Column-family (Cassandra/HBase), Graph (Neo4j).

Understanding

3. Explain why a distributed database cannot guarantee Consistency, Availability, and Partition tolerance all at once. Answer guidance: When a network partition occurs, each isolated side must choose between refusing to respond (preserving consistency) or responding anyway with potentially stale data (preserving availability) — since partitions are unavoidable in real distributed systems, the real choice is CP vs. AP.
4. Why do document databases embed related data instead of using foreign keys and joins the way relational databases do? Answer guidance: Embedding lets one query retrieve everything needed to render a record (e.g., a post with its comments) without cross-machine joins, which are expensive in a horizontally sharded system; the trade-off is data duplication and more complex updates if the embedded data changes independently.

Application

5. A ride-sharing app needs to track live driver locations for millions of drivers with extremely fast reads and writes, and doesn't need complex queries across the data. Which NoSQL category fits best, and why? Answer guidance: Key-value store (e.g., Redis) — the access pattern is a simple, fast lookup/update by driver ID, exactly what key-value stores are optimized for.
6. A team is choosing a database for tracking financial transactions across multiple linked accounts, where a transfer must debit one account and credit another atomically. Which model should they choose, and why? Answer guidance: A relational database with ACID guarantees — the operation is a multi-row transaction requiring atomicity and strong consistency, which is exactly what BASE-oriented NoSQL systems trade away for scalability.

Analysis

7. Compare how a column-family store and a graph database would each handle the query "find all users connected to User X within two hops," and explain which is better suited and why. Answer guidance: A graph database handles this natively and efficiently via relationship traversal (Cypher pattern match); a column-family store would require designing a specific denormalized table for this exact query pattern in advance, and ad hoc multi-hop traversal is not something it's built for.
8. A startup initially chooses Cassandra for its user database to "future-proof for scale," but later struggles because it needs frequent ad hoc analytical queries across arbitrary fields. What went wrong in the decision process, and what should they have weighed? Answer guidance: Cassandra requires query-first schema design optimized around known access patterns; choosing it before query patterns were well understood, and without weighing the need for flexible ad hoc querying, led to a mismatch — a document store or relational database with proper indexing might have served better if query flexibility was a priority over raw write throughput.

FAQ

Q: Does using a NoSQL database mean giving up transactions entirely? A: No. Most document stores (like MongoDB) support atomic transactions within a single document, and increasingly support multi-document transactions too — though usually with more overhead and narrower scope than a relational database's multi-table ACID transactions.

Q: Is MongoDB CP or AP under the CAP theorem? A: By default, MongoDB is generally categorized as CP — it prioritizes consistency, and a partitioned replica set will elect a single primary and refuse writes on nodes that can't reach a majority, rather than risk inconsistent data.

Q: Can a single application use both a relational database and a NoSQL database? A: Yes, and this is common — it's called polyglot persistence. For example, an e-commerce app might use PostgreSQL for orders and payments (needs strong consistency) and MongoDB for product catalog data (needs flexible, evolving schema).

Q: Why do NoSQL databases scale horizontally more easily than relational ones? A: Because they're designed to avoid the operations that get expensive across machines — multi-table joins and multi-row transactions — often by denormalizing data (embedding, wide columns) or accepting eventual consistency, so each shard can largely operate independently.

Q: If eventual consistency is a compromise, why do so many companies accept it? A: Because for a huge share of real-world data — social media likes, product view counts, session data, activity feeds — a few hundred milliseconds of staleness is completely invisible to users, while even a few seconds of downtime is not. The trade strongly favors availability in those cases.

Q: How is a graph database different from just storing relationships in a relational join table? A: In a relational database, a multi-hop query becomes a chain of joins that gets more expensive with each additional hop. In a graph database, relationships are stored as direct pointers between nodes, so traversing them is a fast, localized operation regardless of how deep the graph goes.

Quick Revision

• NoSQL emerged because relational databases scale vertically well but resist horizontal scaling due to joins and multi-row transactions.
• CAP theorem: a distributed system gets at most 2 of Consistency, Availability, Partition tolerance; in practice the real choice is CP vs. AP.
• BASE (Basically Available, Soft state, Eventual consistency) is the NoSQL alternative to ACID.
• Key-value stores (Redis, DynamoDB): fastest, simplest, lookup by key only — great for caching/sessions.
• Document stores (MongoDB): flexible JSON-like documents, often embed related data instead of joining.
• Column-family stores (Cassandra, HBase): row key + flexible sparse columns, built for massive write throughput and query-first design.
• Graph databases (Neo4j): nodes + relationships as first-class citizens, ideal for multi-hop traversal queries.
• Sharding splits data across machines by a shard key, enabling near-linear horizontal scaling but making cross-shard queries costlier.
• Choose relational for strong consistency and complex multi-row transactions (banking); choose NoSQL for scale, flexible schemas, or specialized access patterns (catalogs, sensor data, social graphs).
• NoSQL is not "schema-less," just "schema-flexible" — structure still exists, enforced by the application instead of the database engine.
• Eventual consistency is a deliberate, bounded trade-off, not a synonym for "unreliable data."

Related Topics

Prerequisites

• Introduction to DBMS and the relational model
• Basic understanding of ACID transactions

Related Topics

• Relational Database Model
• Distributed Systems concepts (replication, partitioning)
• Database Design Considerations for scalability

Next Topics

• Data Warehousing and Big Data
• Distributed Transactions and Consensus Protocols
• Database Sharding and Replication Strategies