Database Design: Reading the Relational Model, SQL and Normalization as the Placement of Facts

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 (Proposition 5.2): 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^{+}$ (Lemma 4.3).
• 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 (Theorem 6.3).
• 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.

Example 1.1（How a single table falls apart）

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

Definition 2.1（Relation schemas and relations）

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.

Definition 2.2（Superkeys, candidate keys, primary keys and foreign keys）

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.

Note

For a primary key one may use a natural key, a value with business meaning (a customer code), or a surrogate key, a serial number or UUID. Natural keys can change value when business rules change (codes reassigned after a merger, say), forcing a mass rewrite on the referencing side. In systems meant to last, I think it is safer to make a surrogate key the primary key and put a separate uniqueness constraint on the natural key.

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 Example 1.1 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).

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 Definition 2.2. 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.

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$).

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.

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 Example 1.1. 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$.

Example 3.1（Joining four tables and carrying the aggregation through to the end）

We compute the total amount of each order.

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 Example 1.1 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.

Remark 3.2

The aggregation of Example 3.1 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.

Tip

JOIN is an inner join: rows with no partner on either side disappear. If you want a listing that also includes customers who have never placed an order, use LEFT JOIN and flatten the NULLs in the aggregation with something like COALESCE(SUM(...), 0). Rows quietly vanishing from an aggregate that was written as though it were an inner join is one of the most common mistakes in SQL.

---

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”.

Definition 4.1（Functional dependency）

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 Definition 2.2, 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.

Definition 4.2（Attribute closure）

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.

Lemma 4.3（Attribute closure theorem）

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.

Proof（Lemma 4.3）

($\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 Definition 4.2 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$.

∎

Corollary 4.4（Test for superkeys）

$K \subseteq R$ is a superkey if and only if $K^{+} = R$.

Proof（Corollary 4.4）

That $K$ is a superkey means that $K \to R$ holds in every $F$-legal relation, that is, $F \models K \to R$. By Lemma 4.3 this is equivalent to $R \subseteq K^{+}$, and since $K^{+} \subseteq R$ always holds, it is equivalent to $K^{+} = R$.

∎

Example 4.5（Finding the candidate keys of the order schema）

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 Corollary 4.4. 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

Definition 5.1（First, second and third 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.

Proposition 5.2（A determinant that is not a key necessarily creates redundancy）

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.

Proof（Proposition 5.2）

Since $X$ is not a superkey, Corollary 4.4 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 Lemma 4.3: $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 Lemma 4.3 give $B \in X^{+}$, so $t_1[B] = t_2[B] = 0$. All three conditions are met.

∎

Proposition 5.2 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 Example 1.1 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 Theorem 6.4).

flowchart TB
A["Unnormalized<br/>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)"]

The three stages of normalization and the dependencies removed at each stage

Example 5.3（Decomposing the order schema from 1NF to 3NF）

We start from $R = \{O, D, C, N, S, P, M, U, Q\}$ of Example 1.1 with $F = \{O \to DC,\ C \to NS,\ P \to MU,\ OP \to Q\}$. As computed in Example 4.5, 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 Example 1.1 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.

erDiagram
CUSTOMERS ||--o{ ORDERS : "places"
ORDERS ||--|{ ORDER_ITEMS : "contains"
PRODUCTS ||--o{ ORDER_ITEMS : "is specified in"
CUSTOMERS {
  char customer_id PK
  varchar name
  varchar address
}
ORDERS {
  int order_id PK
  date order_date
  char customer_id FK
}
PRODUCTS {
  char product_id PK
  varchar name
  int unit_price
}
ORDER_ITEMS {
  int order_id PK_FK
  char product_id PK_FK
  int quantity
}

The schema after 3NF decomposition (lines are foreign key references)

Remark 5.4

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 Proposition 5.2 shows, manual synchronization eventually breaks.

---

6. Correctness of a decomposition: lossless joins

In Example 5.3 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.

Definition 6.1（Lossless-join decomposition）

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$.

Example 6.2（A decomposition that loses information）

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”.

Theorem 6.3（Heath's theorem）

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.

Proof（Theorem 6.3）

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 Example 6.2 failed is precisely that neither $B \to A$ nor $B \to C$ held. Every step of the decomposition in Example 5.3 has the shape of Theorem 6.3. 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.

Theorem 6.4（3NF synthesis theorem）

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.

Remark 6.5

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 (Example 3.1). The document model does the opposite: following the principle write together what you read together, it stores the data pre-assembled.

Example 7.1（The same order in a document model）

Order 1001, which Example 5.3 split across four tables, becomes a single document in a document model.

{
  "_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 Proposition 5.2. 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 Remark 3.2), or in which name changes effectively never happen.

Note also that items being an array violates the 1NF of Definition 5.1. 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 (decomposition of end-to-end delay（Proposition 2.2）［ネットワーク（TCP/IP）］). 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 Corollary 5.3［クラウドコンピューティング］). 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 (Definition 6.1［クラウドコンピューティング］) 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.

Caution

Comparisons like “NoSQL is fast” and “relational databases are slow” do not hold up. Running the same access pattern on a single node, a properly indexed relational database is rarely the loser. Differences appear only at a scale that does not fit on a single node, or for access patterns that the relational model expresses awkwardly.

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 (service models（Definition 2.2）［クラウドコンピューティング］) discussed in Cloud Computing. How much availability improves when a standby is provisioned can be estimated in the form of Proposition 6.2［クラウドコンピューティング］. The standard practice is to manage the schema definition itself in files, like code, and keep the history of migrations (commit graph（Definition 4.1）［Git］) in a version control system (Git). To understand the behaviour of distributed databases one needs to know the reality of network latency and partitions, so Networking (TCP/IP) is a useful companion.

---

8. Exercises

Exercise 8.1Standard

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.

Solution

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 Definition 5.1 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 Corollary 4.4. BCNF admits only condition 1 (the determinant is a superkey), so this is a violation. As stated in Remark 6.5, the difference lies in the compromise “whether redundancy on prime attributes is tolerated”.

Exercise 8.2Standard

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.

Solution

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 Theorem 6.3. 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.

Exercise 8.3Easy

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$.

Solution

Since customers who have bought nothing must also be included, we need an outer join anchored on customers.

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$.

Exercise 8.4Hard

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.

Solution

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 Theorem 6.3 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
• 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/.
• 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

---

Appendix: Outline of the 3NF synthesis algorithm

We describe the procedure that produces the decomposition of Theorem 6.4. The details of the proof are in the references listed in Remark 6.5.

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 Lemma 4.3; 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 Example 5.3, 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.