CAP, BASE and the NoSQL landscape

Three guarantees and a cut cable

The exam guideline lists "The CAP theorem" and "ACID vs. BASE" among the theory topics of NoSQL and data models, and this part of the deck is where both live. Page 195, "CAP Theorem (Brewer's Theorem)", states it: "It is impossible for a distributed computer system to simultaneously provide all three of the following guarantees":

Read them on the hook (Fig. 1). A partition is the cut cable: the network splits the nodes into groups that cannot exchange messages. Consistency would mean Dublin answering "0 left", the same data Milan has. Availability means Dublin gives a real answer, a number of tickets, and not an error. Partition tolerance means the system keeps operating although every message across the cut is lost.

Dublin's copy says 1, and nothing has reached it since the cut. The slides state the theorem without proof; the classic argument — Seth Gilbert and Nancy Lynch proved Brewer's conjecture in 2002 — fits on the same two copies (background, not slide text).

1. Take the smallest distributed system: two copies, Milan and Dublin, both holding \(v_0\), "1 ticket left". With more nodes the argument is the same: split them into two groups that cannot talk to each other.

2. Cut the cable: every message between the two is now lost — the "arbitrary partitioning due to network failures (e.g., message loss)" of the definition. Partition tolerance asks the system to keep operating anyway.

3. A client asks Milan to write \(v_1\), "0 left". Refusing with an error would already give up availability, so Milan accepts — and the write exists in Milan only: no message can carry it to Dublin.

4. A client then asks Dublin for the value. To stay available, Dublin must answer, without asking Milan.

5. Dublin has heard nothing since the cut, so it can only return \(v_0\), while consistency demanded \(v_1\). While a partition lasts, C or A must give way; choosing which is the only freedom left.

So the answer out of Dublin's reach is "0 left": it is the truth, but no message can bring it there. What remains is a choice between the other two — and that is where the last line of p. 195 goes too far.

Consistency or availability, decided per operation

Page 196, "So, what can be done?", corrects the slide before it. A distributed system needs a network, and "Failures can, and will, occur to a networked system", so partition tolerance must be accommodated. Then "the only option left is choosing between Consistency and Availability": "CA doesn't make any sense", except for a database on a single site — one machine has no cable to cut. (The slide adds 2-phase commit and cache validation protocols: they keep copies in step only while every node can be reached.) The choice is "Not necessarily in a mutually exclusive manner, but possibly by partial accommodation of both → trade-off analysis important". Then the two lines to learn word for word:

CP keeps the data right and gives up the answer; AP keeps answering and gives up being sure. Neither produces the current value on the far side of the cut. Try both in the widget — and the mixed setting the next slides recommend.

Two seesaws (pp. 197–198, Fig. 2) say what the widget showed. The first balances consistency against availability: the choice during a partition. The second swaps availability for performance. Read it as the trade-off of an ordinary day, with no partition at all: to answer consistently a replica must first hear from the others — the round trip of task 4 — so consistency is paid in waiting time. Beside it the slide writes three sentences to know by heart: "It's a trade-off!", "It's a continuous space!", "It's not at DBMS level, It's at operation level!".

"Continuous": between "wait for every copy" and "answer from the nearest one" lie settings such as "wait for two copies out of three", which lesson 22 meets as Cassandra's consistency levels. "Operation level" is task 3: one database serves the sale CP and the page AP. (Background: in 2012 Daniel Abadi gave this pair of trade-offs a name, PACELC — if Partition, then Availability or Consistency; Else, Latency or Consistency.)

Page 199 is the picture everybody remembers, the "Visual Guide to CAP Theorem" (Fig. 3): a triangle with "Pick Two" in the middle and databases lined up along its sides.

Read it as a map from 2010 (it comes from a blog post by Nathan Hurst — background), with two caveats the course itself supplies. It classifies whole products, while p. 198 has just said the choice is made per operation: MongoDB and Cassandra let each request say how many copies must agree (lessons 16 and 22). And its CA side is no third option for a distributed system: p. 196 grants CA only to a single site, where there is nothing to partition. Yet that side also lists Aster Data, Greenplum and Vertica, databases that run on clusters — when their network splits, they too must give up C or A.

BASE: stale is fine, if you say when

Look again at the AP answer of the widget: "1 left, 4,999 going, as of 21:00". It is out of date, and it is not a lie. Page 202, "ACID vs. BASE", makes this a design principle: "It's ok to use stale data (Accounting systems do this all the time. It's called "closing out the books.") ; it's ok to give approximate answers". The condition: "Use resource versioning -> say what the data really is about – no more, no less." Not "x is 5", but "The value of x is 5, at time T and date D". A balance sheet closed on 31 December is still true in March — about 31 December.

The name is a chemistry pun: p. 200 shows three beakers, acid, base and salt, under "Recall the CAP theorem!", and p. 202 shifts "the PH from 0-6 (acidic) to 8-14 (basic)". Page 201 answers the obvious fear, "ACID properties may not hold -> no properties at all then???": these systems focus on "availability of data even in the presence of multiple failures" and "spread data across many storage systems with a high degree of replication" — the many copies that make immediate consistency expensive. Hence the question of p. 202, "Can some compromise be made between C and A?", instead of giving up either one completely.

The last letter carries the deepest remark of the section. Eventual consistency is "purely a liveness guarantee (reads eventually return the requested value); but does not make safety guarantees, i.e., an eventually consistent system can return any value before it converges". A liveness property promises that something good eventually happens; a safety property, that nothing bad ever happens. Fig. 4 shows the difference on three replicas.

Eventual consistency promises convergence, not correctness on the way: if the writes stop, every copy ends up equal; before that, any value may come back.

Page 204 sends the bill. There is "No general answer to whether your application needs an ACID versus BASE consistency model", but "Given BASE's loose consistency, developers need to be more knowledgeable and rigorous about consistent data if they choose a BASE store", and "Planning around BASE limitations can sometimes be a major disadvantage when compared to the simplicity of ACID transactions." In an ACID database the DBMS keeps the data correct (lesson 3); in a BASE store the application must — the oversold ticket becomes your code's problem. Hence: "A fully ACID database is the perfect fit for use cases where data reliability and consistency are essential."

Which is why relational did not give way. Page 205, "Why didn't we change Relational?", answers "Consolidated", "Integration platform", "Granting ACID properties!" (lesson 3); the second item returns in section 5.

NoSQL: a name older than the movement

Page 207 compresses the argument so far into one "Good Quote!", signed Cedric Beust: "Google, Amazon, Facebook, and DARPA all recognized that when you scale systems large enough, you can never put enough iron in one place to get the job done (and you wouldn't want to, to prevent a single point of failure). Once you accept that you have a distributed system, you need to give up consistency or availability, which the fundamental transactionality of traditional RDBMSs cannot abide." Scale forces distribution (lesson 3), distribution forces the CAP choice, and the choice calls for new databases.

They are older than their name (Fig. 5). Pages 208–209 run from "MultiValue databases at TRW in 1965" to "The term NoSQL was reintroduced in early 2009"; p. 210, "The #NOSQL story", adds "A meetup — Johan Oskarsson in SF, CA, June 2009" and "A hashtag: #nosql". The slide prints in bold the date that surprises: "Carlo Strozzi used the term NoSQL in 1998 to name his lightweight, open-source relational database that did not expose the standard SQL interface."

Who built them? Page 214, "NoSQL originators": Google (BigTable, LevelDB), LinkedIn (Voldemort), Facebook (Cassandra), Twitter (Hadoop/Hbase, FlockDB, Cassandra), Netflix (SimpleDB, Hadoop/HBase, Cassandra), CERN (CouchDB). Not database vendors: web companies and a laboratory whose own data outgrew "iron in one place". Some built the stores (BigTable, Cassandra, Voldemort, FlockDB); others were their early, visible users. Page 215, "Transactional properties?!", draws the line between the two worlds:

Not only SQL is the reading to keep: SQL stays where its guarantees are needed, and the new stores are added beside it.

Four families, one line each

The deck sorts the newcomers twice. Page 211, "Kinds of NoSQL", first makes a two-way cut: "Key/Value or 'the big hash table' (remember caching?)" — Amazon S3 (Dynamo), Voldemort, Scalaris, MemcacheDB, Azure Table Storage, Redis, Riak — against "Schema-less": "Cassandra (column-based)", "CouchDB (document-based)", "Neo4J (graph-based)", "HBase (column-based)" — an odd cut, since key-value stores are schema-less too. Pages 212–213, "Different Types of NoSQL", then give the four families the exam works with, each with the line that tells it apart. Learn the lines: they are the motivations of the one-point table.

The four lines differ in what the database can see (Fig. 6). A key-value store sees keys only: the payload is opaque, so the one question it answers fast is "what is under this key?" — which is why p. 211 says "remember caching?". A document store sees inside the payload: it can index and filter on fields, it "can operate against values in document". A graph store sees the relationships themselves, stored next to the nodes, so a query walks from node to node instead of joining tables. And the column store keeps rows found by a key, each row with its own set of columns — which is not quite what p. 212 says.

The exam adds a fifth family that these slides do not list. The guideline deck names, among the features to know, "Search-based (ElasticSearch)", and the 2026/27 rules list Elasticsearch among the practical topics. Its line: an inverted index from words to documents, with relevance scoring — find by words and rank the hits (lessons 24–26).

One more slide explains how a company ends up using several families at once. Page 216, "Integration: from data to services" (Fig. 7), shows two applications, Billing and Inventory. In the "SQL world" they meet in one Integration Database — p. 205's "Integration platform" — so its schema is a contract nobody may break, and one model must serve them all. In the "NO-SQL world" each owns an Application Database and they talk through a web service: each database now belongs to one application and can be schema-less, a graph or a key-value store, whichever fits that application's data.

The one-point table: which database for which part

Five of the nine past papers open with the same exercise: "Exercise 1 - Unstructured data models (1 PT)", "Which DB technology would be the best to store the entities/rel. of the ER diagram? [you may not need all the rows of the table]", with a three-column table, ENTITIES / REL. | DB TYPE | MOTIVATION, and three empty rows. The exam guideline describes the skill in its own words: "which data model families should be used for each part of the data". The family lines of section 5 are the toolkit; here is a recipe:

1. Read the shape of the data. A web of many-to-many relationships points to a graph. An entity read together with its 1:N children, or an ISA whose children carry different attributes, points to a document. Free text searched by words points to a search engine. A value reached only through its key — a cache, a set, a counter with a TTL — points to key-value. A large, continuously growing volume of records, written fast and read by key, points to a column store.
2. Read the shape of the questions: counting along paths, filtering inside an aggregate, ranking by words, fetching by key.
3. Group the entities and relationships into two or three parts, one family each.
4. Motivate each row with data shape, question shape and the family's line from pp. 212–213.

The column store fills no row of the solved table below, but two 2025 papers say when the examiners reach for one: "Suppose you expect to record large-scale, continuously increasing number of sales of products in the market, and therefore you decide to store it in a columnar database" (exam of 12 Sept 2025, exercise 1; the exam of 30 May 2025 says the same of "a large number of purchases of puzzles"). A volume that keeps growing, read by key: that is the column store's motivation.

Now rehearse on a real paper: the exam of 13 June 2025, "tracking concert attendances and performances", exercise 1. Its ER diagram has Person, with the total and exclusive sub-entities Audience, Artistic Director, Maestro and Musician, and Concert, Location, Track, Orchestra and Instrument, joined by Attend, Organize, Located, At, Perform, Direct, Compose and Play. The widget takes it one fragment at a time, drawn in the paper's notation.

Back to the concert hall of the hook. "0 tickets left" was out of Dublin's reach: the truth was on the other side of the cut. The other two answers are the two corners: "1 left, as of 21:00" is AP, "try again later" is CP. For Buy you want CP — an error is better than a seat sold twice, as the widget's oversold counter showed. For the count of fans going, AP is fine, and honest when it carries its time. One system, two choices, made per operation: "It's not at DBMS level, It's at operation level!". And "pick two of three" was never the menu — the cut cable had already chosen P.