Database Fundamentals

Relational and Non-Relational Databases

Relational, document, key-value, column-family, graph. The families differ less in what they store than in which guarantees they keep. This lesson compares them on the guarantees, not on the marketing.

Beginner

Learning objectives

  • State the defining properties of the relational model and the guarantees that follow
  • Describe the four main non-relational families and what each optimises
  • Explain the CAP theorem's actual claim and its common misreading
  • Explain eventual consistency and BASE without slogans
  • Choose a database family using explicit, stated criteria

Prerequisites

  • Introduction to Databases
  • Database Management Systems: Definition and Functions
  • The ANSI/SPARC Three-Level Architecture

Introduction

"Relational or NoSQL?" is usually asked as a question about technology, and usually answered with a slogan. It is really a question about which guarantees you are willing to give up, and it cannot be answered without naming them.

This lesson has one purpose: make the comparison decidable. It does not argue that one family is better. It states what each family guarantees, what it costs, and what evidence would justify the choice.

What the relational model actually guarantees

The relational model was proposed by E. F. Codd in 1970 and rests on a small number of ideas:

  1. All data are represented as relations (tables): sets of tuples (rows) over a fixed set of named attributes (columns).
  2. Each attribute has a domain: a set of allowed values, with a type.
  3. There is no ordering of rows, and no ordering of columns beyond their names.
  4. Data are accessed by value, not by position or pointer.
  5. A declarative query language (SQL) expresses what to retrieve.

From these ideas follow the guarantees that make the model durable:

Guarantee What it means Enabled by
Physical data independence Storage can change freely Access by value, not by pointer
Set semantics No duplicate rows; results are sets, not sequences Relations are sets
Declarative optimisation The engine chooses the plan Query language states what, not how
Composable queries A query's result is itself a relation Closure of the relational algebra
Constraints as first-class objects Keys, foreign keys, checks, domains A formal schema with a type system
Mature transaction support ACID with configurable isolation Decades of engine engineering

The last one is worth stating precisely, because it is often misunderstood: ACID is not inherent in the relational model. It is a property of the DBMS implementation. Early relational systems had weak transaction support. What is true is that the relational model, with its formal schema and value-based access, makes it tractable to implement ACID — and the relational vendors have had fifty years to do it.

The four non-relational families

Each family optimises something the relational model does not optimise well, and pays for it in guarantees.

1. Document stores

Examples: MongoDB, CouchDB, Firestore.

Unit of storage: a document — usually JSON — containing nested structures and arrays.

What it optimises: reading a complete aggregate in one operation, and evolving the schema without migrations.

{
  "_id": "prestito-8821",
  "socio": { "codice": "1042", "cognome": "Rossi", "nome": "Anna" },
  "copia": { "inventario": "INV-7731", "titolo": "Il nome della rosa" },
  "dataInizio": "2025-03-01",
  "dataScadenza": "2025-03-31"
}

What it gains: one read returns the whole loan with everything a screen needs. No joins. The application's object model maps directly.

What it costs:

  • The same fact is stored many times. The member's name is in every loan document. Change the name and you must update every document — which is exactly the redundancy of Lesson 3, reintroduced deliberately.
  • No cross-document constraints. "A loan must refer to an existing member" is not enforceable by the database. It becomes an application responsibility.
  • Cross-aggregate queries are weak. "Total loans per department" requires either a scan of everything or a separately maintained aggregate.

A document store is a good fit when the aggregate is genuinely the unit of work and the duplicated fields are genuinely immutable (a product's name in a historical invoice, for example, should be frozen).

2. Key-value stores

Examples: Redis, DynamoDB, Riak, Memcached.

Unit of storage: a value of opaque type, addressed by a key.

What it optimises: extremely fast single-key access at very large scale, and horizontal distribution.

What it costs: no query language beyond key access (in the pure form), no constraints, no relationships. Every access pattern must be designed in advance, because the key design is the query design.

When it is right: caching, session state, counters, rate limiting, feature flags — things that are accessed by a known key and have no relationships.

3. Column-family stores

Examples: Cassandra, HBase, ScyllaDB.

Unit of storage: rows identified by a partition key, with columns grouped into families; each row may have different columns.

What it optimises: very high write throughput and linear horizontal scalability across many nodes, with data distributed by partition key.

What it costs: the data model is designed from the queries backwards — you decide the partition key and the sort order based on the reads you need. Adding an unanticipated query often means a new table duplicating the data. Transactions are limited or absent.

When it is right: time-series and event data, telemetry, very high-volume writes where the access patterns are known and stable.

4. Graph databases

Examples: Neo4j, Amazon Neptune, ArangoDB.

Unit of storage: nodes and edges, both with properties.

What it optimises: traversals — "friends of friends", "shortest path", "all parts that depend on this part", "which courses must be passed before this one".

What it costs: weaker support for large-scale aggregation over all data, and a query language (Cypher, Gremlin, SPARQL) that has to be learned.

When it is right: the domain's central question is a traversal of variable depth. Note that a relational database can store a graph perfectly well; what it cannot do efficiently is traverse it to arbitrary depth, because each hop is a join.

Summary of the families

Family Optimises Gives up Typical use
Relational Correctness, ad-hoc querying, integrity Easy horizontal scaling; rigid schema Transactional systems, anything with money
Document Aggregate reads, schema evolution Cross-aggregate integrity, single source of truth Content, catalogues, application state
Key-value Latency at scale Everything except key access Cache, sessions, counters
Column-family Write throughput, distribution Ad-hoc queries, transactions Telemetry, events, logs
Graph Deep traversals Bulk aggregation Social, recommendations, dependencies

The CAP theorem, correctly stated

Almost every discussion of this topic invokes CAP, and almost every invocation is wrong. The theorem (Brewer, 2000; Gilbert and Lynch, 2002) says:

CAP

In the presence of a network partition (P) — some nodes cannot communicate with others — a distributed system must choose between consistency (C, every read sees the latest write) and availability (A, every request receives a non-error response). It cannot have both.

What it does not say:

  • It does not say "pick two of three". P is not optional: partitions happen in any real network. The real choice is C or A when a partition occurs.
  • It does not apply to a single-node system, which has no partitions to be in.
  • "Consistency" in CAP is linearizability, a much stronger property than ACID's C. Most systems people call "CP" are not linearizable in the CAP sense.
  • It says nothing about latency. The practical, everyday trade in distributed systems is between consistency and latency, not availability — this is the substance of PACELC (Abadi, 2012): if there is a Partition, choose A or C; Else, choose Latency or Consistency.

Eventual consistency and BASE

Eventual consistency

A system is eventually consistent if, given no new writes, all replicas will eventually converge to the same value. It says nothing about when, and nothing about what a read returns in the meantime.

BASE — Basically Available, Soft state, Eventual consistency — was proposed as the opposite of ACID. Read it carefully:

  • Basically available: the system responds, possibly with stale or partial data.
  • Soft state: state may change without new input, because replicas are converging.
  • Eventual consistency: as defined above.

The word "eventually" carries all the risk. Consider a library where a member's suspension is written to one replica and read from another:

Time Replica A Replica B Consequence
t₀ member suspended member active A loan is granted that should have been refused
t₀ + 200 ms member suspended member suspended Converged — the wrong loan already exists

The system is correct by its own definition. The business is not. Eventual consistency is a choice about which errors you accept, and the choice must be made by the people who own the consequences — not by the team that prefers one library.

Choosing: explicit criteria

A defensible choice names its criteria before comparing products.

Question If yes → If no →
Is correctness of money, inventory or safety critical? Relational, with transactions Any family may be viable
Do you need ad-hoc queries you cannot predict? Relational A specialised family
Is the access pattern known, stable and key-based? Key-value or column-family Relational
Is the natural unit of read a whole aggregate? Document Relational
Is the central question a variable-depth traversal? Graph Relational
Do you need to scale writes beyond one machine on day one? Column-family / sharded relational Relational
Is the team able to operate a distributed system? Distributed Relational (a single well-run node beats a badly-run cluster)
Do you have a legal retention/erasure requirement per record? Relational, or a store with documented semantics Any

Two criteria deserve emphasis because they are usually omitted:

Operational competence. A distributed database with five nodes and eventual consistency requires monitoring, conflict handling and runbooks. A single relational instance with a backup and an index is a solved problem. Choosing the harder system without the competence to run it is a far more common cause of outages than choosing the "wrong" data model.

Total cost of ownership over ten years. The relational ecosystem's advantage is not raw speed; it is the accumulated tooling: migrations, backup, replication, monitoring, ORMs, reporting, SQL skills, and the fact that a new hire already knows it.

Advanced

Choose, and defend the choice

For each scenario, choose a database family, state the two criteria that drive the choice, and name one thing you are giving up.

  1. A library's loan and reservation system: 40 desks, 5 000 loans a day, a fine must never be lost.
  2. A session store for a web application: 200 000 active sessions, 5-minute expiry.
  3. A product catalogue for an online shop: 300 000 products with varying attributes per category, read far more than written.
  4. A telemetry pipeline: 80 000 sensor readings per second, queried by device and time range.
  5. A "who knows whom" feature in a professional network, with queries like "colleagues of colleagues who work in this industry".
  6. A course prerequisite system for a university: "which courses are reachable from this one, and in what order".
  7. An audit log for a bank: append-only, must never be altered, must be queryable by regulator request.
  8. A real-time leaderboard for a game: 2 million players, updated constantly, top 100 displayed.
Show the commented solution

1. Relational. Criteria: money-critical correctness (a fine must never be lost → ACID durability and atomicity) and unpredictable ad-hoc queries (the library will ask new questions every year). Giving up: easy horizontal scaling, which is irrelevant at 5 000 loans a day. A single well-run instance with a proper backup and binary log handles this for a decade.

2. Key-value. Criteria: access strictly by known key and latency at scale with cheap expiry. Giving up: queryability — "how many sessions are active?" may be impossible or expensive. Note that session data is disposable by design, which is exactly what makes the loss of guarantees acceptable here.

3. Document — with a caveat. Criteria: the read unit is a whole product and attributes vary by category (a schema that would need either many nullable columns or an EAV table in SQL). Giving up: cross-product integrity and easy reporting ("all products with attribute X") unless the document store's indexes are designed for it. The caveat: prices and stock must stay in the transactional system, because they are money-critical; the catalogue document is a derived read model.

4. Column-family. Criteria: write throughput beyond a single node and access pattern known and stable (by device, by time range). Giving up: ad-hoc queries and multi-row transactions. Note that the partition key choice — device, or time bucket, or a combination — determines everything and cannot easily be changed later.

5. Graph. Criterion: the central question is a variable-depth traversal ("colleagues of colleagues"). Giving up: efficient bulk aggregation over all members. A relational database could store the same edges; what it cannot do cheaply is traverse to unbounded depth, because each hop is a join.

6. Graph, or relational with a recursive query. The honest answer is that both work: SQL has recursive common table expressions (WITH RECURSIVE), which handle prerequisite chains well when the depth is moderate and the graph is small. Choose the graph database only if traversals dominate the workload and the graph is large. Giving up with the graph: a second technology and a second query language for a small dataset. This scenario is a good reminder that "graph-shaped" does not automatically mean "needs a graph database".

7. Relational, with an append-only design. Criteria: regulatory correctness and queryability and immutability. Giving up: nothing important. The right design is a table with no UPDATE/DELETE grants for the application user, an INSERT-only policy, and possibly a hash chain or write-once storage underneath. Note that "append-only" is a design decision, not a product category — a relational database does it perfectly well.

8. Key-value or a specialised in-memory store. Criteria: access by known key with a sorted top-N query and very high write rate. Giving up: durability guarantees, usually (many leaderboards are acceptable to lose on restart). If losing the leaderboard is acceptable, Redis-style is ideal; if not, a relational table with an index on the score is simpler and safe.

What this exercise teaches. In eight scenarios the relational model is a defensible answer in five, and the "modern" choice in three — and in each of those three the deciding factor was a specific access pattern or a specific scale, not a preference. The scenarios where people choose wrongly are almost always 6 (graph-shaped but small) and 8 (write-heavy but tiny). Scale and shape decide; fashion does not.

Common mistakes

  • "NoSQL is faster." A key-value store answers a key lookup faster than a relational engine, and cannot answer a join at all. "Faster" without a workload is meaningless.
  • "Relational databases do not scale." They scale vertically very far and horizontally with read replicas and sharding. Every large bank and airline runs relational. What they do not do easily is write sharding across hundreds of nodes.
  • "Schemaless means no schema." A document store has a schema: it lives in the application code and in the shape of existing documents. The difference is that it is not enforced, so it drifts.
  • "CAP says pick two of three." P is not optional. The choice is C or A during a partition.
  • "Eventual consistency is fine, we'll handle conflicts later." Conflicts are business decisions. "Later" means "in production, with real money".
  • "We need a graph database because our data are a graph." Almost all data are a graph. The question is whether traversal is the dominant operation.

Summary

  • The relational model represents all data as relations over typed domains, accessed by value, queried declaratively. From this follow physical independence, set semantics, composable queries, first-class constraints and tractable ACID.
  • Document, key-value, column-family and graph stores each optimise one thing — aggregate reads, key latency, write throughput, traversals — and give up cross-aggregate integrity, ad-hoc querying or transactions.
  • CAP is about consistency versus availability during a network partition. It is not "pick two of three", and it says nothing about latency.
  • Eventual consistency promises convergence, not a bound. Choosing it is choosing which errors the business accepts.
  • A defensible choice names its criteria: correctness criticality, query predictability, access pattern stability, traversal depth, scale, and above all operational competence.
  • Polyglot persistence is normal; the discipline that keeps it safe is naming one system of record per fact and treating every other copy as derived.

Verification questions

  1. Why does "relational" not mean "has relationships", and what does it mean?
  2. Which guarantee of the relational model makes physical data independence possible, and why?
  3. State the CAP theorem precisely, then explain what the popular "pick two of three" version gets wrong.
  4. A document store keeps the member's name inside every loan document. Which problem from Lesson 3 does this reintroduce, and when is it acceptable?
  5. Give a scenario that is graph-shaped and for which a relational database is still the better choice, and say why.
Show the answers
  1. It refers to relations in the mathematical sense: sets of tuples over named attributes. Every database family stores relationships between things; only the relational one is named after relations. "Relational = has foreign keys" makes the term meaningless.

  2. Access by value, not by position or pointer. Because a query names columns and conditions rather than file offsets, the storage layout can change without affecting the query — the logical/physical mapping absorbs the change.

  3. Precisely: in the presence of a network partition, a distributed system must sacrifice either linearizability or availability for the affected data. The popular version is wrong because P is not a choice — partitions occur in any network — so the real choice is C or A when a partition happens. It also says nothing about latency, which is the trade systems make every day (PACELC).

  4. It reintroduces uncontrolled redundancy, and therefore the possibility of inconsistency: the name can differ between documents and the master record. It is acceptable when the duplicated value is genuinely immutable in that context — the member's name as it was on the loan date is a historical fact that should not change, and then the document is not a copy of the current name but a record of a past one. The distinction between "copy" and "historical fact" is the whole decision.

  5. A university's prerequisite graph with 3 000 courses. It is graph-shaped, and yet a relational database with a prerequisito(corso, corsoRichiesto) table and a recursive CTE answers "which courses are reachable" correctly and efficiently, while keeping the same transactions, constraints and backup procedures as the rest of the university system. A separate graph database would add a technology, a query language and a synchronisation problem for a dataset that fits in memory. Traversal depth and volume, not shape, are what justify the graph family.

Where to go next

Related lessons