SQL vs NoSQL: Differences, CAP Theorem and When to Use

For decades "database" meant a relational database queried with SQL. In the 2000s, web companies needed to store more data, across more machines, with less rigid structure than one relational server handled comfortably, and a family of non-relational systems grew up under the name NoSQL (now read as "not only SQL"). Interviewers ask about the trade-offs: when a document or key-value store beats a table, what ACID and BASE mean, and what the CAP theorem really says. This note answers those, and covers replication and sharding, the two techniques behind every distributed database.

The relational model

A relational database stores data in tables with a schema declared in advance (schema-on-write). Tables are linked by keys, queries combine them with joins, constraints keep the data valid, and transactions are ACID across any number of rows and tables. MySQL, PostgreSQL, Oracle Database and SQL Server are the common ones. Its strengths are exact, flexible querying (any question the data can answer, written in SQL) and integrity. Its traditional weakness is scaling writes beyond one machine, which is possible but not built in.

The previous notes describe this model: keys, normalization, joins and transactions.

The NoSQL families

Here is the same idea, a customer and her orders, in each model:

1. Relational: the customer, her 2 orders and their 3 items go into three tables linked by keys, each fact stored once. Showing her profile with orders takes two joins.
2. Document: the orders and their items are embedded inside the customer, so one read of 162 bytes returns everything the profile page needs. Data another document also needs would have to be copied into it.
3. Key-value: the store knows only keys and the bytes stored under them. GET customer:101 is one very fast lookup, but "orders above ₹1,000" cannot be asked: the store cannot look inside a value.
4. Wide-column: customer_id is the partition key, so all of Asha's orders live together on the same nodes, sorted by the clustering columns, newest first. Reading her latest orders is one sequential read; the table exists for that one query.
5. Graph: Asha, her orders and the products are nodes, and each relationship is a stored edge. A question that follows relationships, such as which products she bought, walks edges from her node instead of joining tables.

Document (MongoDB), as stored:

{
  "_id": 101,
  "name": "Asha",
  "city": "Pune",
  "orders": [
    { "order_id": 9001, "total": 1499, "items": ["keyboard"] },
    { "order_id": 9002, "total": 299, "items": ["mouse pad", "cable"] }
  ]
}

Embedding is fast to read but duplicates data that other documents also need, which is denormalization with the usual update anomalies.

Key-value (Redis): the database knows only keys. Values can be strings, or in Redis's case lists, hashes and sorted sets, and keys can expire.

SET cart:101 "{\"items\": 3, \"total\": 1798}" EX 3600
GET cart:101

Wide-column (Cassandra): you design one table per query. Here the partition key customer_id decides which nodes store the rows, and the clustering columns keep each customer's orders sorted newest first inside the partition.

CREATE TABLE orders_by_customer (
  customer_id int,
  order_date  date,
  order_id    int,
  total       int,
  PRIMARY KEY ((customer_id), order_date, order_id)
) WITH CLUSTERING ORDER BY (order_date DESC, order_id DESC);

Graph (Neo4j, Cypher query language): relationships are stored as edges, so "what did Asha's friends buy?" is a traversal, not a chain of joins.

MATCH (a:Customer {name: 'Asha'})-[:FRIEND]->(f)-[:BOUGHT]->(p:Product)
RETURN DISTINCT p.name

SQL vs NoSQL

The line has blurred. PostgreSQL and MySQL store and index JSON; MongoDB has multi-document transactions; Cassandra speaks the SQL-like CQL; and distributed SQL databases such as Google Spanner, CockroachDB and TiDB scale horizontally with ACID transactions. Choose by the workload, not the label.

ACID vs BASE

ACID puts correctness first. BASE describes many distributed NoSQL stores:

• Basically available: the system answers every request, even during failures, possibly with stale data.
• Soft state: the state can change without new input, as replicas exchange updates.
• Eventually consistent: if updates stop, all replicas converge to the same value.

The CAP theorem

Eric Brewer conjectured it in 2000, and Seth Gilbert and Nancy Lynch proved it in 2002. Its three properties have precise meanings:

• Consistency (C): every read returns the most recent write or an error, as if there were one copy of the data (linearizability).
• Availability (A): every request received by a non-failing node gets a non-error response.
• Partition tolerance (P): the system keeps operating when the network drops messages between nodes.

The theorem: if a network partition occurs, a distributed system must choose between consistency and availability. It cannot guarantee both while nodes cannot talk to each other.

1. Two replicas of the same data, in Mumbai and Singapore. While the link works, a write to Mumbai (likes = 42) is copied to Singapore, and both answer alike.
2. The link fails: a partition. A new write reaches Mumbai, which now holds 43, but cannot be copied, so Singapore still holds 42. Now a read arrives in Singapore.
3. A CP choice keeps consistency: Singapore cannot confirm it has the latest value, so it refuses the read with an error until the link is back. Everyone who gets an answer gets the latest one.
4. An AP choice keeps availability: Singapore answers with what it has, 42, which is stale. Every request gets an answer, and some answers are out of date.
5. When the link returns, the AP replicas exchange updates and converge on 43: eventual consistency. CAP's choice only bites during a partition; with the link up, a system can be both consistent and available.

The popular "pick any two of three" is misleading. Partitions are not optional in a distributed system, so you cannot "choose CA" by giving up P; a CA system is simply one that is not distributed, such as a single database server. When there is no partition, a system can be both consistent and available. The PACELC refinement (Daniel Abadi, 2012) adds the everyday trade-off: if there is a Partition, choose A or C; Else, choose lower Latency or Consistency.

Many databases are tunable, so classify a configuration rather than a product. Cassandra with consistency level ONE behaves as AP; with QUORUM reads and writes it leans towards consistency. MongoDB with majority read and write concerns behaves as CP. Also note that CAP's C is not ACID's C: ACID's consistency means constraints hold, while CAP's means replicas agree.

Replication

Replication keeps copies of the same data on several nodes, for fault tolerance and to spread reads.

• Leader-follower (primary-replica): all writes go to the leader, which streams changes to followers; reads may go to any. MySQL replication, PostgreSQL streaming replication and MongoDB replica sets work this way.
• Synchronous or asynchronous: a synchronous leader waits for a follower to confirm each write, so failover loses nothing but writes are slower; an asynchronous one does not wait, so followers lag and a failover can lose the latest writes.
• Replication lag can break read-your-writes: a user's next read, served by a follower that is behind, may not show her own change.
• Multi-leader accepts writes in several places (for example one leader per data centre) and must resolve conflicting writes.
• Leaderless (Dynamo-style, as in Cassandra): a client writes to W of the N replicas and reads from R of them. If R + W > N, every read set overlaps every write set.

1. The user renames her profile to "Asha Patel". The write goes to the leader, which acknowledges it and streams it to the followers without waiting: follower 1 has applied it, follower 2 has not yet.
2. The next page load is a read, sent to follower 2, which still shows "Asha". The user's own change seems to have vanished, though it is safe on the leader.
3. A common fix: for a short while after a user writes, read that user's own data from the leader. Everyone else's reads can still go to any follower.

The quorum rule of leaderless stores, checked over every possible read:

1. A write of v2 waits for W = 2 of the 3 replicas. With R = 2, all 3 possible read sets share at least one replica with the write set, because 2 + 2 > 3: every read sees v2 and keeps the newest version.
2. With R = 1, R + W = 3 is not greater than 3: a read that happens to ask only replica 3 gets the old v1. The overlap rule, not the number of copies, is what makes reads current.

Sharding

Sharding (horizontal partitioning) splits the rows of one data set across nodes by a shard key, so each node stores and serves only its part. It spreads data volume and write load, which replication alone cannot.

1. By range, each shard holds a contiguous run of ids. A range query for 1005–1008 (blue) stays on one shard, but every new order, 1010, 1011, 1012 (solid), lands on the last shard: a hot spot.
2. By hash, each id goes to shard (FNV-1a hash of the id) mod 3. The new orders spread over 3 shards, but neighbouring ids are scattered, so the same range query must ask every shard.

A good shard key has many distinct values, spreads reads and writes evenly, and keeps data that is queried together on one shard. The costs are real: joins and transactions across shards are slow or unsupported, and rebalancing moves data while the system runs. Relational databases can be sharded too, with tools such as Vitess for MySQL and Citus for PostgreSQL. Vertical scaling (a bigger machine) is simpler and should usually come first; horizontal scaling (more machines) is what sharding enables.

When to choose which

Many systems use several stores at once (polyglot persistence): a relational database as the source of truth for accounts and orders, Redis in front of it as a cache, perhaps a search engine beside it. The practical default is a relational database until a measured need points elsewhere.

Common mistakes

• Reading CAP as "pick two of three": partitions are unavoidable, so the choice is C or A during a partition.
• Equating CAP's consistency with ACID's consistency.
• Saying NoSQL databases have no transactions: many offer single-record atomicity, and some offer multi-record ACID transactions.
• Saying SQL databases cannot scale horizontally: replicas, sharding tools and distributed SQL all exist.
• Confusing replication with sharding: copies of the same data versus different parts of the data.
• Choosing NoSQL for "flexible schema" and then needing joins and integrity everywhere.

Interview questions

What does NoSQL stand for, and what are its main types? It is now read as "not only SQL", a name for non-relational databases. The main types are document, key-value, wide-column and graph stores.

State the CAP theorem correctly. In the presence of a network partition, a distributed system cannot be both consistent (linearizable) and available. It must refuse some requests to stay consistent, or answer them with possibly stale data to stay available.

Is Cassandra CP or AP? It is usually described as AP, because it keeps accepting reads and writes during partitions and converges later. But consistency is tunable per query, and QUORUM reads with QUORUM writes give much stronger guarantees, so it depends on configuration.

What is the difference between vertical and horizontal scaling? Vertical scaling adds CPU, memory or disk to one machine; it is simple but bounded and keeps one point of failure. Horizontal scaling adds machines and spreads data and load across them through replication and sharding.

How do you choose a shard key? Pick a column with many distinct values and even access, used by most queries to find data, so that each query hits one shard and no shard runs hot. User id is a common choice; a timestamp alone is a classic hot-spot mistake.

What is R + W > N in leaderless replication? With N replicas, a write waits for W acknowledgements and a read queries R replicas. If R + W > N the two sets must share at least one replica, so a read sees the latest acknowledged write.

Would you store a bank's transactions in MongoDB or MySQL? In a relational database such as MySQL or PostgreSQL by default, because transfers need multi-row ACID transactions, constraints and strong consistency. A document store could work with multi-document transactions, but it gives up the strengths it is chosen for.

Why might a social network use a graph database? Queries such as friends of friends or people you may know follow edges several hops deep. A graph database stores the edges directly, so each hop is a pointer lookup, whereas a relational database needs one self-join per hop.

You have reached the end of the DBMS notes. Go back to the start with Introduction to DBMS, browse the DBMS notes, or test yourself with the SQL (Basic) and SQL (Intermediate) skill tests.