# Database Design: Reading the Relational Model, SQL and Normalization as the Placement of Facts
> Defines tables, keys and foreign keys, follows SQL on concrete data, and derives the first three normal forms with proofs from functional dependencies and attribute closure.
> https://rikai.mugen-giken.com/en/computer-science/software-engineering/database-design
## 0. Key points
- A relational database is not a collection of "tables" but a collection of **relations** (finite sets of tuples). From this point of view every SQL command becomes an operation on sets.
- A primary key is a minimal set of attributes that determines a row; a foreign key is a reference to the primary key of another table. These two notions alone express almost all of the connections between tables.
- Normalization is not a matter of taste. Its justification is a theorem (): **a state in which the same fact is written in two places necessarily invites update anomalies**.
- The first three normal forms strengthen one condition in stages, according to whether the left-hand side $X$ of a functional dependency $X \to Y$ is "part of a key" or "not a key at all". Deciding them reduces to computing the attribute closure $X^{+}$ ().
- When we split a table, we need to be able to split it and join it back without loss (a lossless-join decomposition). A functional dependency guarantees this automatically ().
- NoSQL is not "a database without normalization". It is a design that **moves the join from query time to design time** and in exchange makes horizontal partitioning easy. Which one to choose is decided by the access pattern.
---
## 1. Motivation: why a spreadsheet is not enough
When people set out to manage orders, the first thing most of them build is one big table. Each row records who bought what, how many, and when. This does work — for a while. After some use, however, the following always happens.
Suppose we build the following table (order 1001 contains two products, so it occupies two rows).
| Order no. | Order date | Customer ID | Customer name | Customer address | Product ID | Product name | Unit price | Quantity |
|---|---|---|---|---|---|---|---|---|
| 1001 | 2026-04-01 | C01 | Tanaka Trading | Chiyoda-ku, Tokyo | P01 | Bolt | 120 | 10 |
| 1001 | 2026-04-01 | C01 | Tanaka Trading | Chiyoda-ku, Tokyo | P02 | Nut | 80 | 25 |
| 1002 | 2026-04-03 | C02 | Sato Industries | Kita-ku, Osaka | P01 | Bolt | 120 | 4 |
Three accidents now occur.
**Update anomaly.** Tanaka Trading moves. There are two rows whose address must be rewritten. If only one of them is corrected, the same customer ends up with two different addresses. The number of rows grows with the number of orders, so this danger grows with time.
**Insertion anomaly.** We want to register a new product P03, but nothing has been sold yet. This table can hold only "order rows", so there is nowhere to record a product on its own. The only option is a ghost row with an empty order number.
**Deletion anomaly.** If order 1002 is cancelled and its row deleted, the name and address of customer C02 (Sato Industries) vanish from the world as well. What we wanted to delete was an order, not a customer.
All three accidents have the same cause: **facts of different natures were made to share one row**. The fact "the address of customer C01 is Chiyoda-ku, Tokyo" and the fact "10 units of product P01 were bought in order 1001" arise independently, change independently, and disappear independently. Bundle them into one row and every time we touch one of them the other is caught in the crossfire.
When E. F. Codd proposed the relational model in his 1970 paper, this was exactly his motivation. In the hierarchical and network databases of the time, applications had to know how the data was physically arranged (which record was linked to which pointer), and changing the storage layout broke the programs. Codd argued that if data is described as a mathematical **relation** and queries are written in a declarative language — relational algebra — then one becomes independent of the physical storage. In the second half of the same paper he introduced a criterion for "which shapes of relation are free of anomalies", namely the normal forms. The relational model and normalization were a single package from the very beginning.
In this article we define the vocabulary of the relational model (§2), check the basic SQL operations against real data (§3), introduce functional dependencies (§4), and prove why the first three normal forms are needed (§5). We then treat the theorem that guarantees the correctness of a decomposition (§6) and the trade-off with NoSQL (§7).
---
## 2. Preliminaries on the relational model
A finite set $R = \{A_1, \ldots, A_n\}$ of **attributes** is called a **relation schema**. Each attribute $A_i$ is assumed to come with a set of values, its **domain** $\mathrm{dom}(A_i)$.
A map $t$ assigning to each $A_i$ a value $t[A_i] \in \mathrm{dom}(A_i)$ is called a **tuple** (a row) over $R$. Writing $\mathrm{Tup}(R)$ for the set of all tuples over $R$, a finite subset $r \subseteq \mathrm{Tup}(R)$ is called a **relation** over $R$ (the contents of a table, an instance).
For a subset $X \subseteq R$, we write $t[X]$ for the restriction of $t$ to $X$.
Two points in this definition matter. First, a relation is a **set**, so the same tuple cannot occur twice. Second, sets have no order, so neither the order of the rows nor the order of the columns carries meaning. Actual SQL products do allow duplicate rows (the result of a `SELECT` is a multiset) and do impose an order on columns, but when thinking about design it is less confusing to think in terms of sets.
Let a relation schema $R$ be given, together with the family of relations permitted over $R$ (all instances satisfying the constraints). We say that $K \subseteq R$ is a **superkey** if, for every permitted instance $r$,
$$
\forall t_1, t_2 \in r,\quad t_1[K] = t_2[K] \implies t_1 = t_2
$$
holds. A superkey none of whose proper subsets is a superkey is called a **candidate key**. When there are several candidate keys, the designer picks one and declares it the **primary key**. An attribute belonging to some candidate key is called a **prime attribute**; otherwise it is **non-prime**.
A set of attributes $X \subseteq S$ of a relation schema $S$ is a **foreign key** referencing the primary key $K$ of a relation schema $R$ if we impose the constraint that, for every instance $s$ of $S$ and the corresponding instance $r$ of $R$,
$$
\forall t \in s,\ \exists u \in r,\quad t[X] = u[K]
$$
holds (excluding the case where $t[X]$ is NULL). This constraint is called **referential integrity**.
A primary key is "the address that points at a row"; a foreign key is "a reference to that address". In the vocabulary of programming languages, the primary key corresponds to object identity, the foreign key to a pointer, and referential integrity to the promise that no dangling pointer is ever created.
Throughout this article we use the following order database as our example, denoting each attribute by a single letter.
| Symbol | $O$ | $D$ | $C$ | $N$ | $S$ | $P$ | $M$ | $U$ | $Q$ |
|---|---|---|---|---|---|---|---|---|---|
| Meaning | order no. | order date | customer ID | customer name | customer address | product ID | product name | unit price | quantity |
The single table of is a relation over $R = \{O, D, C, N, S, P, M, U, Q\}$.
---
## 3. Basic SQL operations
SQL is the de facto standard language for the relational model. Here we check five operations that we will need later, working on the four normalized tables below (we derive them in §5).
```sql
CREATE TABLE customers (
customer_id CHAR(3) PRIMARY KEY,
name VARCHAR(100) NOT NULL,
address VARCHAR(200) NOT NULL
);
CREATE TABLE products (
product_id CHAR(3) PRIMARY KEY,
name VARCHAR(100) NOT NULL,
unit_price INTEGER NOT NULL CHECK (unit_price >= 0)
);
CREATE TABLE orders (
order_id INTEGER PRIMARY KEY,
order_date DATE NOT NULL,
customer_id CHAR(3) NOT NULL REFERENCES customers(customer_id)
);
CREATE TABLE order_items (
order_id INTEGER NOT NULL REFERENCES orders(order_id),
product_id CHAR(3) NOT NULL REFERENCES products(product_id),
quantity INTEGER NOT NULL CHECK (quantity > 0),
PRIMARY KEY (order_id, product_id)
);
```
`REFERENCES` is the foreign key declaration: it tells the DBMS to enforce the referential integrity of . An attempt to insert an order with a nonexistent `customer_id` is rejected by the DBMS. If instead we try to protect integrity with `if` statements in the application, gaps appear as soon as new code paths are added. Declared in the DBMS, the constraint holds no matter which path the data arrives by.
**INSERT** adds tuples to a relation.
```sql
INSERT INTO customers (customer_id, name, address) VALUES
('C01', 'Tanaka Trading', 'Chiyoda-ku, Tokyo'),
('C02', 'Sato Industries', 'Kita-ku, Osaka');
INSERT INTO products (product_id, name, unit_price) VALUES
('P01', 'Bolt', 120),
('P02', 'Nut', 80);
INSERT INTO orders (order_id, order_date, customer_id) VALUES
(1001, '2026-04-01', 'C01'),
(1002, '2026-04-03', 'C02');
INSERT INTO order_items (order_id, product_id, quantity) VALUES
(1001, 'P01', 10),
(1001, 'P02', 25),
(1002, 'P01', 4);
```
**SELECT** combines selection (extracting the rows satisfying a condition, the $\sigma$ of relational algebra) and projection (extracting columns, $\pi$).
```sql
SELECT product_id, quantity
FROM order_items
WHERE order_id = 1001;
```
The result is $\pi_{P, Q}(\sigma_{O = 1001}(\mathrm{order\_items}))$, that is, the two rows `('P01', 10), ('P02', 25)`.
**UPDATE** and **DELETE** rewrite and remove existing rows.
```sql
UPDATE customers SET address = 'Nishi-ku, Yokohama' WHERE customer_id = 'C01';
DELETE FROM order_items WHERE order_id = 1002 AND product_id = 'P01';
```
Compare this with . The address update touches exactly one row of `customers`. Deleting an order does not delete a customer. The whole effect of normalization is concentrated in these two lines.
**JOIN** combines several relations under a condition. The inner join $r \bowtie_{\theta} s$ is defined as the set of tuples of $r \times s$ satisfying the condition $\theta$.
We compute the total amount of each order.
```sql
SELECT o.order_id,
c.name AS customer,
SUM(oi.quantity * p.unit_price) AS total
FROM orders o
JOIN customers c ON c.customer_id = o.customer_id
JOIN order_items oi ON oi.order_id = o.order_id
JOIN products p ON p.product_id = oi.product_id
GROUP BY o.order_id, c.name
ORDER BY o.order_id;
```
Let us follow the computation. Joining `orders` with `order_items` produces three rows (two for order 1001, one for 1002). Joining each of them with `customers` and `products` gives the following intermediate result.
| order_id | customer | product_id | quantity | unit_price | subtotal |
|---|---|---|---|---|---|
| 1001 | Tanaka Trading | P01 | 10 | 120 | 1200 |
| 1001 | Tanaka Trading | P02 | 25 | 80 | 2000 |
| 1002 | Sato Industries | P01 | 4 | 120 | 480 |
`GROUP BY o.order_id, c.name` groups by order number and `SUM` adds the subtotals.
| order_id | customer | total |
|---|---|---|
| 1001 | Tanaka Trading | 3200 |
| 1002 | Sato Industries | 480 |
Indeed $1200 + 2000 = 3200$, and $480$. With the single table of no join would have been needed, but that table carried update anomalies instead. **Normalization is a trade in which safety at update time is bought with the cost of joins at query time.**
The aggregation of has a defect that cannot be ignored in practice. Because the unit price is taken from `products`, raising the price of a product **also changes the total of past orders**. "The current unit price of product P01 is 120" and "the unit price of P01 at the time of order 1001 was 120" are different facts. If the latter is needed, we give `order_items` a column `unit_price_at_order`. This looks like duplication, but the functional dependency $P \to U$ holds only for the *present*, and the unit price at the time of the order is not determined by $P$, so this is not a violation of any normal form. **Normal forms are decided by the functional dependencies that actually hold, not by how the attributes look.**
---
## 4. Functional dependencies and attribute closure
To discuss normalization we must formalize the relationship "once the value of this column is fixed, the value of that column is fixed too".
Let $R$ be a relation schema and $X, Y \subseteq R$. A relation $r$ over $R$ **satisfies** the **functional dependency** $X \to Y$ if
$$
\forall t_1, t_2 \in r,\quad t_1[X] = t_2[X] \implies t_1[Y] = t_2[Y]
$$
holds. When $Y \subseteq X$, the dependency $X \to Y$ holds for every $r$; such a dependency is called **trivial**.
Given a set $F$ of functional dependencies, a relation satisfying all of them is called **$F$-legal**. If every $F$-legal relation satisfies $X \to Y$, we say that $X \to Y$ is **logically implied** by $F$ and write $F \models X \to Y$. We write $F^{+}$ for the set of all $X \to Y$ with $F \models X \to Y$.
Comparing with , we see that $K$ being a superkey is nothing other than $K \to R$ holding. Keys are thus a special case of functional dependencies.
For the order example we take the following basis of dependencies that hold.
$$
F = \{\ O \to DC,\quad C \to NS,\quad P \to MU,\quad OP \to Q\ \}
$$
Read out loud: "the order number determines the order date and the customer", "the customer ID determines the customer's name and address", "the product ID determines the product name and unit price", "the order number together with the product ID determines the quantity". Each of these is a fact about the business, not something guessed by looking at the data. It is worth emphasizing that **functional dependencies are specifications of the business, not properties that the current data happens to satisfy**.
In general $F^{+}$ is enormous, but what we actually need is only "what is determined by a particular $X$". That is what the attribute closure gives us.
For $X \subseteq R$, define the **attribute closure** $X^{+}$ as the result of the following procedure.
1. Set $X^{+} := X$.
2. As long as $F$ contains some $V \to W$ with $V \subseteq X^{+}$ and $W \not\subseteq X^{+}$, set $X^{+} := X^{+} \cup W$.
3. Stop when no such dependency remains.
Since $R$ is finite and $X^{+}$ grows strictly at each step, the procedure halts after at most $|R|$ additions.
For a relation schema $R$, a set $F$ of functional dependencies, and $X, Y \subseteq R$,
$$
F \models X \to Y \iff Y \subseteq X^{+}
$$
holds.
**($\Leftarrow$) Soundness.** By induction on the number of additions in the construction of $X^{+}$, we show that every $F$-legal relation $r$ satisfies $X \to X^{+}$.
Initially $X^{+} = X$, and $X \to X$ is a trivial functional dependency, hence holds in every $r$.
Induction step. Write $Z$ for the current value and assume $r$ satisfies $X \to Z$. Suppose the procedure uses $V \to W \in F$ (with $V \subseteq Z$) to update to $Z' = Z \cup W$. Let $t_1, t_2 \in r$ satisfy $t_1[X] = t_2[X]$. By the induction hypothesis $t_1[Z] = t_2[Z]$. Since $V \subseteq Z$, it follows that $t_1[V] = t_2[V]$, and since $r$ is $F$-legal it satisfies $V \to W$, so $t_1[W] = t_2[W]$. Hence $t_1[Z \cup W] = t_2[Z \cup W]$, that is, $r$ satisfies $X \to Z'$.
The value of $Z$ at termination is $X^{+}$, so $F \models X \to X^{+}$. If $Y \subseteq X^{+}$, then $t_1[X^{+}] = t_2[X^{+}]$ gives $t_1[Y] = t_2[Y]$, so $F \models X \to Y$.
**($\Rightarrow$) Completeness.** We argue by contraposition. Assume $Y \not\subseteq X^{+}$ and construct a relation that is $F$-legal yet fails to satisfy $X \to Y$.
Pick $E \in Y \setminus X^{+}$. We may assume every domain contains $\{0, 1\}$ (if not, pick two of its elements instead), and consider the relation $r = \{t_1, t_2\}$ consisting of the following two tuples.
$$
t_1[A] = 0 \ \ (\forall A \in R), \qquad
t_2[A] = \begin{cases} 0 & (A \in X^{+}) \\ 1 & (A \notin X^{+}) \end{cases}
$$
Since $E \notin X^{+}$ we have $t_1[E] = 0 \ne 1 = t_2[E]$, so $t_1 \ne t_2$ and $r$ consists of exactly two tuples.
We show that $r$ is $F$-legal. Take any $V \to W \in F$ and distinguish two cases.
- Case $V \subseteq X^{+}$. The procedure of has halted, so $W \subseteq X^{+}$ (otherwise $V \to W$ could add something more and it would not have halted). Hence both $V$ and $W$ are contained in $X^{+}$, and there $t_1$ and $t_2$ both take the value $0$ and agree. Therefore $V \to W$ is satisfied.
- Case $V \not\subseteq X^{+}$. Take $B \in V \setminus X^{+}$; then $t_1[B] = 0 \ne 1 = t_2[B]$, so $t_1[V] \ne t_2[V]$. Since $r$ contains only $t_1$ and $t_2$, there is no pair of distinct tuples agreeing on $V$, and $V \to W$ is satisfied vacuously.
On the other hand $X \subseteq X^{+}$ gives $t_1[X] = t_2[X] = 0$, while $E \in Y$ and $t_1[E] \ne t_2[E]$ give $t_1[Y] \ne t_2[Y]$. So $r$ does not satisfy $X \to Y$. Having constructed an $F$-legal counterexample, we conclude $F \not\models X \to Y$.
$K \subseteq R$ is a superkey if and only if $K^{+} = R$.
That $K$ is a superkey means that $K \to R$ holds in every $F$-legal relation, that is, $F \models K \to R$. By this is equivalent to $R \subseteq K^{+}$, and since $K^{+} \subseteq R$ always holds, it is equivalent to $K^{+} = R$.
Let $R = \{O, D, C, N, S, P, M, U, Q\}$ and $F = \{O \to DC,\ C \to NS,\ P \to MU,\ OP \to Q\}$.
We compute $\{O, P\}^{+}$.
1. $X^{+} = \{O, P\}$.
2. $O \to DC$ applies (since $O \in X^{+}$), so $X^{+} = \{O, P, D, C\}$.
3. $P \to MU$ applies, so $X^{+} = \{O, P, D, C, M, U\}$.
4. $C \to NS$ applies, so $X^{+} = \{O, P, D, C, M, U, N, S\}$.
5. $OP \to Q$ applies, so $X^{+} = \{O, P, D, C, M, U, N, S, Q\} = R$.
Hence $\{O, P\}$ is a superkey by . We check minimality. We have $\{O\}^{+} = \{O, D, C, N, S\} \ne R$ (it does not contain $P, M, U, Q$) and $\{P\}^{+} = \{P, M, U\} \ne R$. Neither reaches $R$, so $\{O, P\}$ is a candidate key.
Moreover, the only dependency involving $Q$ is $OP \to Q$, and the attribute $Q$, which appears only on a right-hand side, cannot belong to any candidate key. Also $O$ and $P$ appear on the right-hand side of no dependency, so they must belong to every superkey. Therefore $\{O, P\}$ is the unique candidate key. The prime attributes are $O$ and $P$; the remaining $D, C, N, S, M, U, Q$ are non-prime.
---
## 5. Normalization: the first three normal forms
Let a relation schema $R$ and a set $F$ of functional dependencies be given.
**First normal form (1NF)**: the domain of every attribute consists of atomic values; that is, no cell contains a list of several values or a nested table.
**Second normal form (2NF)**: $R$ is in 1NF and, for every candidate key $K$, every non-prime attribute $A$ and every proper subset $X \subsetneq K$, we have $F \not\models X \to A$. In other words, no non-prime attribute depends on merely **part** of a candidate key (there is no partial functional dependency).
**Third normal form (3NF)**: $R$ is in 1NF and, for every nontrivial functional dependency $X \to A$ in $F^{+}$ (where $A \in R \setminus X$ may be taken to be a single attribute), at least one of the following holds.
1. $X$ is a superkey of $R$, or
2. $A$ is a prime attribute.
Allowing only dependencies satisfying condition 1 of 3NF (that is, refusing condition 2) gives **Boyce–Codd normal form (BCNF)**. The inclusions among these are BCNF $\subsetneq$ 3NF $\subsetneq$ 2NF $\subsetneq$ 1NF.
Why climb this staircase? The reason is entirely contained in the following proposition.
Consider a relation schema $R$ and a set $F$ of functional dependencies. Suppose $X \subseteq R$ and $B \in R \setminus X$ satisfy
- $F \models X \to B$ ($X$ determines $B$), and
- $X$ is not a superkey of $R$.
Then there exists an $F$-legal relation $r$ containing two tuples $t_1, t_2$ with
$$
t_1 \ne t_2,\qquad t_1[X] = t_2[X],\qquad t_1[B] = t_2[B].
$$
That is, the single fact "when the value of $X$ is $x$, the value of $B$ is $b$" can be stored redundantly in two rows.
Since $X$ is not a superkey, gives $X^{+} \ne R$, so we may pick $E \in R \setminus X^{+}$.
Take the same two-tuple relation $r = \{t_1, t_2\}$ constructed in the completeness half of the proof of : $t_1$ is $0$ on all attributes, and $t_2$ is $0$ on $X^{+}$ and $1$ on $R \setminus X^{+}$. By the same case distinction, $r$ is $F$-legal.
Since $t_1[E] = 0 \ne 1 = t_2[E]$, we have $t_1 \ne t_2$. Since $X \subseteq X^{+}$, we have $t_1[X] = t_2[X]$. Finally, $F \models X \to B$ and give $B \in X^{+}$, so $t_1[B] = t_2[B] = 0$. All three conditions are met.
does not say "redundancy may occur"; it says "**an instance containing the redundancy is perfectly legitimate under the business rules**". Being legitimate, it will appear sooner or later. And where there is redundancy, an update anomaly that rewrites only one of the copies becomes possible. The duplicated address in was thus a consequence of $C$ not being a superkey of $R$ in $C \to S$ (the only candidate key was $\{O, P\}$).
Conversely, if condition 1 of 3NF holds then $X$ is a superkey, so $t_1[X] = t_2[X]$ forces $t_1 = t_2$; there are no duplicate rows and this form of redundancy does not arise. That 3NF admits condition 2 ($A$ prime) as an exception is a compromise, and the corresponding redundancy remains. BCNF refuses this compromise, but in exchange there are cases in which only decompositions that fail to preserve dependencies exist (see the remark following ).
multi-valued cells, repeating columns"] -->|"atomize values, expand repetitions into rows"| B["First normal form (1NF)"]
B -->|"split off dependencies on part of a candidate key"| C["Second normal form (2NF)"]
C -->|"split off transitive dependencies through non-prime attributes"| D["Third normal form (3NF)"]
D -->|"forbid dependencies on prime attributes as well"| E["Boyce-Codd normal form (BCNF)"]`} />
We start from $R = \{O, D, C, N, S, P, M, U, Q\}$ of with $F = \{O \to DC,\ C \to NS,\ P \to MU,\ OP \to Q\}$. As computed in , the only candidate key is $\{O, P\}$.
**Checking 1NF.** If the original data had been in a format writing two entries as `P01:10, P02:25` in a product column, it would violate 1NF. In that case, expanding one order-and-product pair per row yields 1NF. The table of is already in this shape, so it is in 1NF.
**Decomposition to 2NF.** For the non-prime attributes $D, C, N, S, M, U$ we look for dependencies on proper subsets of the candidate key $\{O, P\}$.
- $O \to D$ and $O \to C$ hold, and $\{O\} \subsetneq \{O, P\}$. Moreover $O \to C \to NS$ gives $O \to N$ and $O \to S$ as well. These are partial functional dependencies.
- $P \to M$ and $P \to U$ hold, and $\{P\} \subsetneq \{O, P\}$. These too are partial functional dependencies.
So we carve out the group of attributes determined by $O$ and the group determined by $P$.
$$
R_1 = \{O, D, C, N, S\},\quad R_2 = \{P, M, U\},\quad R_3 = \{O, P, Q\}
$$
The candidate key of $R_3$ is $\{O, P\}$, its only non-prime attribute is $Q$, and neither $O \to Q$ nor $P \to Q$ holds ($Q$ belongs to neither $\{O\}^{+}$ nor $\{P\}^{+}$), so $R_3$ is in 2NF. The candidate key of $R_2$ is $\{P\}$, whose only proper subset is the empty set, and $\varnothing \to M$ does not hold, so $R_2$ is in 2NF. The candidate key of $R_1$ is $\{O\}$, and by the same argument $R_1$ is in 2NF.
**Decomposition to 3NF.** Examine $R_1$. Its candidate key is $\{O\}$, and the nontrivial dependency $C \to N$ lies in $F^{+}$. Since $\{C\}^{+} = \{C, N, S\} \ne R_1$, the set $C$ is not a superkey of $R_1$, and $N$ is not a prime attribute of $R_1$ either (the only candidate key of $R_1$ is $\{O\}$). Hence 3NF is violated. The cause is the **transitive dependency** $O \to C \to NS$. We carve out the part determined by $C$.
$$
R_{1a} = \{O, D, C\},\qquad R_{1b} = \{C, N, S\}
$$
The final decomposition consists of the four schemas
$$
\{O, D, C\},\quad \{C, N, S\},\quad \{P, M, U\},\quad \{O, P, Q\}
$$
which correspond to `orders`, `customers`, `products` and `order_items` of §3. Let us verify the 3NF condition in each. In $\{O, D, C\}$ the only nontrivial dependency is $O \to DC$ and $O$ is the candidate key; in $\{C, N, S\}$ it is $C \to NS$ with $C$ the candidate key; in $\{P, M, U\}$ it is $P \to MU$ with $P$ the candidate key; in $\{O, P, Q\}$ it is $OP \to Q$ with $\{O, P\}$ the candidate key. All satisfy condition 1 of 3NF, so in fact they are in BCNF as well.
Normalization is a means, not an end. After decomposing to 3NF, one sometimes deliberately duplicates data into a separate table for places that are read extremely often and almost never updated (precomputed monthly sales, say). This is called **denormalization**. There is exactly one condition for doing it: **make explicit who is responsible for keeping the redundant copies in sync**. Synchronize mechanically with a trigger, a materialized view or a batch recomputation, and do not saddle the application's write path with the obligation to "update two places". As shows, manual synchronization eventually breaks.
---
## 6. Correctness of a decomposition: lossless joins
In we split tables apart. But depending on how we split, **the original information can be lost**. We now state the condition that rules this danger out.
Let $R$ be a relation schema and $R_1, R_2$ subsets with $R_1 \cup R_2 = R$. Relative to a set $F$ of functional dependencies, this decomposition is a **lossless-join decomposition** if, for every $F$-legal relation $r$,
$$
r = \pi_{R_1}(r) \bowtie \pi_{R_2}(r)
$$
holds. Here $\bowtie$ is the natural join, which joins tuples agreeing on the common attributes $R_1 \cap R_2$.
Let $R = \{A, B, C\}$ with no functional dependencies at all ($F = \varnothing$), and take $r = \{(1,1,1),\ (2,1,2)\}$. Decomposing into $R_1 = \{A, B\}$ and $R_2 = \{B, C\}$ gives
$$
\pi_{R_1}(r) = \{(1,1), (2,1)\},\qquad \pi_{R_2}(r) = \{(1,1), (1,2)\}.
$$
Since the only value of $B$ on either side is $1$, the natural join produces $2 \times 2 = 4$ tuples.
$$
\pi_{R_1}(r) \bowtie \pi_{R_2}(r) = \{(1,1,1),\ (1,1,2),\ (2,1,1),\ (2,1,2)\}
$$
The tuples $(1,1,2)$ and $(2,1,1)$, absent from the original $r$, have been created. Decomposing and rejoining **manufactured false data**. Since $r \subseteq \pi_{R_1}(r) \bowtie \pi_{R_2}(r)$ always holds for any decomposition, what is lost is not rows but the linkage information "which value sat in the same row as which".
Partition a relation schema $R$ into three pairwise disjoint subsets $X, Y, Z$ (so $R = X \cup Y \cup Z$ and $X \cap Y = Y \cap Z = Z \cap X = \varnothing$), and suppose the set $F$ of functional dependencies satisfies $F \models X \to Y$. Then the decomposition into $R_1 = X \cup Y$ and $R_2 = X \cup Z$ is a lossless-join decomposition; that is, for every $F$-legal relation $r$,
$$
r = \pi_{X \cup Y}(r) \bowtie \pi_{X \cup Z}(r)
$$
holds.
Note that $R_1 \cap R_2 = X$ (since $Y \cap Z = \varnothing$, the intersection is exactly $X$).
**($\subseteq$)** Let $t \in r$. Then $t_1 = t[X \cup Y] \in \pi_{X \cup Y}(r)$ and $t_2 = t[X \cup Z] \in \pi_{X \cup Z}(r)$, and both agree on $X$ with the value $t[X]$. So by the definition of the natural join these two are joined, and the result is the tuple taking $t[X]$ on $X$, $t[Y]$ on $Y$ and $t[Z]$ on $Z$ — that is, $t$ itself. Hence $t \in \pi_{X \cup Y}(r) \bowtie \pi_{X \cup Z}(r)$. This direction does not use the functional dependency.
**($\supseteq$)** Let $u$ be a tuple of the right-hand side. By the definition of the natural join there exist $t_1, t_2 \in r$ with
$$
u[X \cup Y] = t_1[X \cup Y],\qquad u[X \cup Z] = t_2[X \cup Z].
$$
In particular $t_1[X] = u[X] = t_2[X]$. Now the hypothesis $F \models X \to Y$ together with the $F$-legality of $r$ implies that $r$ satisfies $X \to Y$. Since $t_1[X] = t_2[X]$, it follows that $t_1[Y] = t_2[Y]$.
Then $t_2$ takes $u[X]$ on $X$, $u[Z]$ on $Z$, and $t_2[Y] = t_1[Y] = u[Y]$ on $Y$. As $R = X \cup Y \cup Z$, the tuple $t_2$ agrees with $u$ on all attributes, so $u = t_2 \in r$.
The reason failed is precisely that neither $B \to A$ nor $B \to C$ held. Every step of the decomposition in has the shape of . For instance, when $R_1 = \{O, D, C, N, S\}$ was split into $\{O, D, C\}$ and $\{C, N, S\}$, taking $X = \{C\}$, $Y = \{N, S\}$, $Z = \{O, D\}$ makes $C \to NS$ hold, so the split is lossless. **If we split so that the shared column of the part carved out is a determinant of what is carved out, no information is lost.** This is the justification of the procedure "collect the attributes determined by $C$ into a separate table".
There is one more desirable property of a decomposition: **dependency preservation**, meaning that the constraints of the original $F$ can be checked using only the constraints on the individual tables of the decomposition. When this fails, a state may be allowed in which each table is correct on its own yet the whole violates the business rule, and checking the rule requires a join.
For every relation schema $R$ and every set $F$ of functional dependencies there exists a decomposition $R_1, \ldots, R_k$ of $R$ satisfying all three of the following conditions, and it can be constructed in time polynomial in the size of $F$.
1. Each $R_i$ is in 3NF (with respect to the projection of $F$ onto $R_i$).
2. The decomposition is a lossless-join decomposition.
3. The decomposition is dependency preserving.
The Appendix sketches the construction (the 3NF synthesis algorithm). A complete proof can be found in Chapter 11 of Abiteboul–Hull–Vianu, *Foundations of Databases*, or in Chapter 7 of Ullman, *Principles of Database and Knowledge-Base Systems, Volume I*.
For BCNF the situation is different. A lossless decomposition is always available, but **dependency preservation cannot be achieved in general**. The standard counterexample is $R = \{A, B, C\}$ with $F = \{AB \to C,\ C \to B\}$. The candidate keys are $\{A, B\}$ and $\{A, C\}$; since the $C$ of $C \to B$ is not a superkey, BCNF is violated, whereas $B$ is prime, so 3NF is satisfied. No matter how this $R$ is decomposed into BCNF, $AB \to C$ never fits inside a single table and cannot be preserved. That 3NF is the practical standard comes from exactly this position: it is the strongest normal form for which the three conditions can be met simultaneously.
---
## 7. Differences from NoSQL, and how to choose
In the late 2000s, as the scale of web services outgrew what a single server could handle, data models other than the relational one came into wide use. Collectively they are called NoSQL. Here are four representative families.
| Family | Data model | Representative systems | Strengths |
|---|---|---|---|
| Key-value (KVS) | map from keys to opaque values | Redis, Amazon DynamoDB | extremely fast reads and writes by key; sessions, caches |
| Document | map from keys to nested JSON-like documents | MongoDB, Couchbase | reading and writing a whole aggregate at once; data with a fluid schema |
| Wide column | row key + column families | Apache Cassandra, HBase | time series and logs with extremely high write volume |
| Graph | vertices and edges | Neo4j | multi-hop traversal (friends of friends, path finding) |
The essential differences from a relational database can be organized into three points.
**First, when the join happens.** The relational model stores facts split into their smallest units and assembles them with `JOIN` at the moment they are needed (). The document model does the opposite: following the principle **write together what you read together**, it stores the data pre-assembled.
Order 1001, which split across four tables, becomes a single document in a document model.
```json
{
"_id": 1001,
"order_date": "2026-04-01",
"customer": { "id": "C01", "name": "Tanaka Trading", "address": "Chiyoda-ku, Tokyo" },
"items": [
{ "product_id": "P01", "name": "Bolt", "unit_price": 120, "quantity": 10 },
{ "product_id": "P02", "name": "Nut", "unit_price": 80, "quantity": 25 }
]
}
```
The benefit is clear. The operation "display the contents of order 1001" is a single read by the key `1001`. No join is needed, and even if the data is spread over several servers this document is guaranteed to live on one of them.
The cost is equally clear. The customer name is replicated in every order, which is exactly the redundancy pointed out by . If Tanaka Trading changes its company name, every order document of that customer must be rewritten. The document model is a design that accepts this cost knowingly. It is acceptable only in businesses that want to preserve the customer name as of the time of the order (the same reasoning as in ), or in which name changes effectively never happen.
Note also that `items` being an array violates the 1NF of . One may say that the document model is a model that deliberately abandons 1NF.
**Second, the ease of horizontal partitioning (sharding).** If the counterpart of a join lives on another server, data must be gathered across the network, and each gathering adds a round-trip delay (). Document stores and key-value stores can be partitioned mechanically by hashing the key, and since every operation completes on a single machine, performance scales almost linearly with the number of machines (for the response time when load is spread evenly over $n$ machines, see ). Relational databases can be partitioned too, but joins and transactions crossing partitions form the barrier.
**Third, the consistency guarantee.** Relational databases provide transactions satisfying ACID (atomicity, consistency, isolation, durability), so that "debit account A and credit account B" can be executed indivisibly. In distributed systems there is a constraint known as E. Brewer's CAP theorem: while a network partition is in effect, strong consistency and availability cannot both be satisfied at once. Most NoSQL systems choose availability () in this situation and offer **eventual consistency** (once the partition heals, the values converge over time). Applications must be written on the assumption that reading a different node immediately after a write returns may show a stale value.
The following summarizes the rules of thumb.
| Situation | Recommendation |
|---|---|
| Consistency across several entities is required (stock and orders, transfers between accounts) | relational database |
| The shape of the queries is not fixed in advance (analytics, filtering in an admin console) | relational database |
| Always read and write by a single key, with tight latency requirements (sessions, carts) | KVS |
| The aggregate boundary is clear and the whole aggregate is read and written as a unit | document store |
| Write volume greatly exceeds read volume and data is appended in time order | wide column store |
| Multi-hop relationships are traversed (recommendation, routing, inheritance of permissions) | graph store |
Today the boundaries are blurring. PostgreSQL's `JSONB` type stores documents in a column and can index them, and many NoSQL systems have partially introduced transactions. I think the safe order is to **design first with a normalized relational model and replace with a different tool only the places where measurement shows a problem**. Choosing a database is a judgement that includes operations (backup, monitoring, failover), so consider it together with the managed-service options () discussed in [Cloud Computing](/computer-science/software-engineering/cloud-computing). How much availability improves when a standby is provisioned can be estimated in the form of . The standard practice is to manage the schema definition itself in files, like code, and keep the history of migrations () in a [version control system (Git)](/en/computer-science/software-engineering/version-control-git). To understand the behaviour of distributed databases one needs to know the reality of network latency and partitions, so [Networking (TCP/IP)](/computer-science/software-engineering/networking-tcp-ip) is a useful companion.
---
## 8. Exercises
Let $R = \{A, B, C, D, E\}$ and $F = \{A \to BC,\ CD \to E,\ B \to D,\ E \to A\}$.
1. Find all candidate keys of $R$.
2. Is $R$ in 3NF? In BCNF? Give reasons.
**1.** We compute attribute closures.
$\{A\}^{+}$: by $A \to BC$ we get $\{A,B,C\}$, by $B \to D$ we get $\{A,B,C,D\}$, by $CD \to E$ we get $\{A,B,C,D,E\} = R$. So $\{A\}$ is a superkey, and its only proper subset is the empty set ($\varnothing^{+} = \varnothing \ne R$), so it is a candidate key.
$\{E\}^{+}$: by $E \to A$ we get $\{E,A\}$, and from there we reach $R$ as in the case of $A$. So $\{E\}$ is a candidate key too.
$\{B\}^{+} = \{B, D\}$, $\{C\}^{+} = \{C\}$, $\{D\}^{+} = \{D\}$, none of which reaches $R$.
$\{B, C\}^{+}$: by $B \to D$ we get $\{B,C,D\}$, by $CD \to E$ we get $\{B,C,D,E\}$, by $E \to A$ we get $R$. Since neither $\{B\}$ nor $\{C\}$ is a superkey, $\{B,C\}$ is a candidate key.
$\{C, D\}^{+}$: by $CD \to E$ we get $\{C,D,E\}$, by $E \to A$ we get $\{C,D,E,A\}$, by $A \to BC$ we get $R$. Since neither $\{C\}$ nor $\{D\}$ is a superkey, $\{C,D\}$ is also a candidate key.
$\{B, D\}^{+} = \{B, D\}$, so this is not a candidate key. Altogether the candidate keys are the four sets $\{A\}$, $\{E\}$, $\{B,C\}$ and $\{C,D\}$.
**2.** Count the prime attributes. Each of $A, E, B, C, D$ occurs in some candidate key, so **every attribute is prime**. Therefore the second condition of 3NF in always holds, and $R$ is in 3NF.
It is not in BCNF. The dependency $B \to D$ is nontrivial, and $\{B\}^{+} = \{B, D\} \ne R$, so $B$ is not a superkey by . BCNF admits only condition 1 (the determinant is a superkey), so this is a violation. As stated in , the difference lies in the compromise "whether redundancy on prime attributes is tolerated".
As a university enrolment record, consider $R = \{\mathit{StudentID},\ \mathit{StudentName},\ \mathit{CourseID},\ \mathit{CourseName},\ \mathit{TeacherID},\ \mathit{TeacherName},\ \mathit{Grade}\}$ with functional dependencies
$$
\begin{aligned}
&\mathit{StudentID} \to \mathit{StudentName}, \qquad
\mathit{CourseID} \to \mathit{CourseName},\ \mathit{TeacherID},\\
&\mathit{TeacherID} \to \mathit{TeacherName}, \qquad
\mathit{StudentID},\mathit{CourseID} \to \mathit{Grade}
\end{aligned}
$$
(one course has exactly one teacher; one teacher may hold several courses). Find the candidate keys, point out a violation of 2NF and a violation of 3NF, and decompose down to 3NF. State also why each decomposition is lossless.
Abbreviate the symbols as $S, SN, C, CN, T, TN, G$. Then $F = \{S \to SN,\ C \to CN\,T,\ T \to TN,\ SC \to G\}$.
**Candidate keys.** $\{S, C\}^{+}$: $S \to SN$ adds $SN$, $C \to CN\,T$ adds $CN$ and $T$, $T \to TN$ adds $TN$, $SC \to G$ adds $G$, giving all of $R$. We have $\{S\}^{+} = \{S, SN\}$ and $\{C\}^{+} = \{C, CN, T, TN\}$, neither of which reaches $R$. Moreover $S$ and $C$ occur on the right-hand side of no dependency, so they belong to every superkey. Hence the only candidate key is $\{S, C\}$, and the prime attributes are $S$ and $C$.
**Violation of 2NF.** The non-prime attribute $SN$ depends on the proper subset $\{S\}$ of the candidate key ($S \to SN$). Likewise $CN, T, TN$ depend on $\{C\}$ ($C \to CN$, $C \to T$, and $C \to T \to TN$). All of these are partial functional dependencies.
**Violation of 3NF.** Even after resolving the 2NF violation to obtain $\{C, CN, T, TN\}$, the candidate key is $\{C\}$, and in $T \to TN$ we have $\{T\}^{+} = \{T, TN\}$, which is not the whole attribute set of this table, so $T$ is not a superkey. Since $TN$ is not prime either, 3NF is violated (the transitive dependency $C \to T \to TN$).
**Decomposition.**
$$
\{S, SN\},\quad \{C, CN, T\},\quad \{T, TN\},\quad \{S, C, G\}
$$
The only nontrivial dependency in each table is respectively $S \to SN$, $C \to CN\,T$, $T \to TN$, $SC \to G$, and in each the left-hand side is the candidate key of that table, so all are in 3NF (indeed in BCNF).
**Losslessness.** Every split has the shape of . For instance, at the stage where $\{S, SN\}$ is carved out of $R$, taking $X = \{S\}$, $Y = \{SN\}$, $Z = R \setminus \{S, SN\}$ makes $S \to SN$ hold, so the split is lossless. At the stage where $\{T, TN\}$ is carved out of $\{C, CN, T, TN\}$, taking $X = \{T\}$, $Y = \{TN\}$, $Z = \{C, CN\}$ makes $T \to TN$ hold, so that split is lossless as well. The result of repeating lossless decompositions is lossless, so the whole is lossless.
For the schema of §3, write SQL that lists the cumulative purchase amount per customer in decreasing order of amount, including customers who have bought nothing at all with an amount of $0$.
Since customers who have bought nothing must also be included, we need an outer join anchored on `customers`.
```sql
SELECT c.customer_id,
c.name,
COALESCE(SUM(oi.quantity * p.unit_price), 0) AS total
FROM customers c
LEFT JOIN orders o ON o.customer_id = c.customer_id
LEFT JOIN order_items oi ON oi.order_id = o.order_id
LEFT JOIN products p ON p.product_id = oi.product_id
GROUP BY c.customer_id, c.name
ORDER BY total DESC;
```
Making the inner joins plain `JOIN` (inner joins) would delete the rows of customers without orders and fail the requirement. Also, for a customer with no orders every argument of `SUM` is NULL and `SUM` returns NULL, so we replace it by $0$ with `COALESCE`. On the data of §3, C01 gives $3200$ and C02 gives $480$.
Let $R = \{A, B, C\}$ and $F = \{A \to B\}$. Show that the decomposition $R_1 = \{A, B\}$, $R_2 = \{B, C\}$ is not a lossless-join decomposition by explicitly constructing an $F$-legal relation as a counterexample. Then give one decomposition that is lossless, with a justification.
**Counterexample.** Take $r = \{(1, 0, 1),\ (2, 0, 2)\}$ (in the order $(A, B, C)$). The values $1, 2$ of $A$ are distinct, so there is no pair for which $A \to B$ imposes anything, and $r$ is $F$-legal.
We have $\pi_{AB}(r) = \{(1,0), (2,0)\}$ and $\pi_{BC}(r) = \{(0,1), (0,2)\}$. Since the only value of $B$ on either side is $0$, the natural join returns the $4$ tuples
$$
\{(1,0,1),\ (1,0,2),\ (2,0,1),\ (2,0,2)\}
$$
which include $(1,0,2)$ and $(2,0,1)$, absent from the original $r$. Hence the decomposition is not lossless. The cause is that the common attribute $B$ determines neither $A$ nor $C$: neither $B \to A$ nor $B \to C$ is implied by $F$ (indeed $\{B\}^{+} = \{B\}$).
**A lossless decomposition.** Take $R_1' = \{A, B\}$ and $R_2' = \{A, C\}$. Setting $X = \{A\}$, $Y = \{B\}$, $Z = \{C\}$, the sets $X, Y, Z$ are pairwise disjoint with union $R$, and $F \models A \to B$. All hypotheses of are met, so this decomposition is a lossless-join decomposition.
As a check, apply it to the $r$ above. We get $\pi_{AB}(r) = \{(1,0), (2,0)\}$ and $\pi_{AC}(r) = \{(1,1), (2,2)\}$, and joining on $A$ yields exactly the two tuples $(1,0,1)$ and $(2,0,2)$, which agree with $r$.
---
## References
- E. F. Codd, "A Relational Model of Data for Large Shared Data Banks", *Communications of the ACM* 13 (1970), 377–387. The original paper proposing the relational model and normalization. [doi:10.1145/362384.362685](https://doi.org/10.1145/362384.362685)
- S. Abiteboul, R. Hull, V. Vianu, *Foundations of Databases*, Addison-Wesley, 1995 — Chapter 8 (functional dependencies) and Chapter 11 (normal forms and decomposition). A rigorous treatment of reasoning about functional dependencies and of the theory of normal forms. The full text is made available by the authors at [webdam.inria.fr/Alice/](http://webdam.inria.fr/Alice/).
- A. Silberschatz, H. F. Korth, S. Sudarshan, *Database System Concepts*, 7th ed., McGraw-Hill, 2019 — Chapter 7 (normalization) and Chapters 3–4 (SQL). The standard undergraduate textbook.
- J. D. Ullman, *Principles of Database and Knowledge-Base Systems, Volume I*, Computer Science Press, 1988 — Chapter 7. Contains the construction of the 3NF synthesis algorithm and the proof of its correctness.
- M. Kleppmann, *Designing Data-Intensive Applications*, O'Reilly, 2017 — Chapter 2 (data models and query languages), Chapters 5–9 (replication, partitioning, transactions, consistency). Compares the relational model with NoSQL and treats consistency in distributed environments.
- S. Gilbert, N. Lynch, "Brewer's Conjecture and the Feasibility of Consistent, Available, Partition-Tolerant Web Services", *ACM SIGACT News* 33 (2002), 51–59. The formal proof of the CAP theorem. [doi:10.1145/564585.564601](https://doi.org/10.1145/564585.564601)
---
## Appendix: Outline of the 3NF synthesis algorithm
We describe the procedure that produces the decomposition of . The details of the proof are in the references listed in .
**Stage 1: build a minimal cover.** From the set $F$ of functional dependencies, build $F_c$ (preserving $F_c^{+} = F^{+}$) satisfying the following three conditions. (a) The right-hand side of every dependency is a single attribute. (b) For every dependency $X \to A$, removing any attribute from $X$ destroys equivalence with $F_c$ (the left-hand side is minimal). (c) Removing any dependency destroys equivalence with $F_c$ (the number of dependencies is minimal). The procedure is: first split the right-hand sides into single attributes; then, for each dependency, tentatively remove each attribute of the left-hand side and test derivability using ; finally, tentatively remove each dependency and run the same test. Every test is a computation of an attribute closure, so this runs in polynomial time.
**Stage 2: make one table per left-hand side.** Group the dependencies of $F_c$ by identical left-hand sides, and for a left-hand side $X$ with right-hand sides $A_1, \ldots, A_m$ take $X \cup \{A_1, \ldots, A_m\}$ as one relation schema. At this stage every dependency of $F_c$ fits inside some table, which guarantees **dependency preservation**.
**Stage 3: add one candidate key.** If none of the tables built in stage 2 contains a candidate key of $R$, choose a candidate key $K$ and add a table whose attribute set is $K$ itself. This guarantees the **lossless join** (it makes the order of joins traceable from the candidate key).
**Stage 4: remove contained tables.** When the attribute set of one table is contained in that of another, discard the smaller one.
Applying this procedure to the order schema of , the set $F$ is already close to a minimal cover, and grouping by left-hand side yields the four schemas $\{O, D, C\}$, $\{C, N, S\}$, $\{P, M, U\}$, $\{O, P, Q\}$. The last of these contains the candidate key $\{O, P\}$, so the addition of stage 3 is unnecessary. The result agrees with the decomposition we carried out by hand.
**Limits of this procedure.** The synthesis algorithm guarantees only 3NF. Whether each table is further in BCNF must be checked individually, and forcing a decomposition when it is not can destroy dependency preservation. In practice I think the realistic approach is to decompose to 3NF and then judge, from the business side, whether the remaining exceptions (dependencies on prime attributes) actually cause trouble.