データベース設計の基礎：関係モデル・SQL・正規化を「事実の置き場所」から考える

情報科学ソフトウェア開発第3章学部無料公開約 42 分2026-08-23

前提:Docker と Kubernetes：コンテナはなぜ軽く、クラスタはなぜ自己修復するのか

生 Markdown

0. この記事の要点

リレーショナルデータベースは「表」の集まりではなく、**関係（有限集合としてのタプルの集まり）**の集まりです。この見方に立つと、SQL の各命令が集合演算として理解できます。
主キーは行を一意に決める最小の属性集合、外部キーは別の表の主キーへの参照です。この 2 つだけで、表と表のつながりのほとんどが表現できます。
正規化は美観の問題ではありません。同じ事実が 2 か所に書かれている状態は、必ず更新異常を引き起こすという定理（命題 5.2）が根拠です。
第 1〜第 3 正規形は、関数従属 $X \to Y$ の $X$ が「キーの一部か」「キーでないか」で段階的に条件を強めたものです。判定は属性閉包 $X^{+}$ の計算に帰着します（補題 4.3）。
表を分割するときは、分割してから結合し直しても元に戻ること（無損失結合分解）が必要です。関数従属があれば自動的に保証されます（定理 6.3）。
NoSQL は「正規化しないデータベース」ではなく、結合を実行時から設計時へ前倒しする代わりに水平分割しやすくした設計です。どちらを選ぶかはアクセスパターンで決まります。

1. 動機：なぜ表計算ソフトのシートでは足りないのか

受注管理をやろうとしたとき、多くの人がまず作るのは 1 枚の大きな表です。1 行に「いつ・誰が・何を・いくつ買ったか」を全部書く。これで一応動きます。動くのですが、しばらく使うと必ず次のことが起きます。

例 1.1（1 枚の表が壊れていく過程）

次のような表を作ったとします（受注 1001 で 2 種類の商品を買ったので 2 行になっています）。

受注番号	受注日	顧客ID	顧客名	顧客住所	商品ID	商品名	単価	数量
1001	2026-04-01	C01	田中商事	東京都千代田区	P01	ボルト	120	10
1001	2026-04-01	C01	田中商事	東京都千代田区	P02	ナット	80	25
1002	2026-04-03	C02	佐藤工業	大阪市北区	P01	ボルト	120	4

ここで 3 つの事故が起きます。

更新異常。 田中商事が引っ越しました。住所を書き換えるべき行は 2 行あります。1 行だけ直すと、同じ顧客の住所が 2 通り存在する状態になります。行数は受注件数に比例して増えるので、この危険は時間とともに大きくなります。

挿入異常。 新商品 P03 を登録したいのですが、まだ 1 件も売れていません。この表は「受注の行」しか持てないので、商品だけを登録する場所がありません。受注番号を空欄にした幽霊行を入れるほかなくなります。

削除異常。 受注 1002 をキャンセルして行を消すと、顧客 C02（佐藤工業）の名前と住所もこの世から消えます。消したかったのは受注であって顧客ではありません。

3 つの事故はどれも同じ原因から来ています。性質の違う事実を 1 つの行に同居させたことです。「顧客 C01 の住所は東京都千代田区である」という事実と、「受注 1001 で商品 P01 を 10 個買った」という事実は、独立に生まれ、独立に変化し、独立に消えます。それを 1 行に束ねてしまうと、片方を触るたびにもう片方が巻き添えになります。

E. F. Codd が 1970 年の論文で関係モデルを提案したとき、動機はまさにここにありました。当時の階層型・ネットワーク型データベースでは、データの物理的な並び方（どのレコードがどのポインタでつながっているか）をアプリケーションが知っている必要があり、格納方法を変えるとプログラムが壊れました。Codd は、データを**数学的な関係（relation）**として記述し、問い合わせを関係代数という宣言的な言語で書けば、物理的な格納方法から独立できると主張しました。そして同じ論文の後半で、「どういう関係の形なら異常が起きないか」という基準、すなわち正規形を導入しています。関係モデルと正規化は最初から一組だったのです。

この記事では、関係モデルの語彙を定義し（§2）、SQL の基本操作を実データで確かめ（§3）、関数従属を導入して（§4）第 1〜第 3 正規形の必要性を証明します（§5）。さらに分割の正しさを保証する定理（§6）と、NoSQL との使い分け（§7）を扱います。

2. 関係モデルの準備

定義 2.1（関係スキーマと関係）

属性（attribute）の有限集合 $R = \{A_1, \ldots, A_n\}$ を関係スキーマと呼びます。各属性 $A_i$ には値の集合（定義域） $\mathrm{dom}(A_i)$ が定まっているとします。

写像 $t$ であって、各 $A_i$ に $t[A_i] \in \mathrm{dom}(A_i)$ を対応させるものを $R$ 上のタプル（行）と呼びます。 $R$ 上のタプル全体の集合を $\mathrm{Tup}(R)$ と書くとき、その有限部分集合 $r \subseteq \mathrm{Tup}(R)$ を $R$ 上の関係（テーブルの中身、インスタンス）と呼びます。

部分集合 $X \subseteq R$ に対し、 $t[X]$ は $t$ を $X$ に制限したタプルを表します。

定義のうえで大事な点が 2 つあります。第一に、関係は集合なので同じタプルが 2 つ入ることはありません。第二に、集合には順序がないので、行の並び順も列の並び順も意味を持ちません。実際の SQL 製品は重複行を許し（SELECT の結果は多重集合になります）、列に順序を与えますが、設計を考えるときは集合として考えるほうが混乱しません。

定義 2.2（スーパーキー・候補キー・主キー・外部キー）

関係スキーマ $R$ と、 $R$ 上で許される関係の集まり（制約を満たすインスタンス全体）が与えられているとします。 $K \subseteq R$ がスーパーキーであるとは、許されるどのインスタンス $r$ についても

\forall t_1, t_2 \in r,\quad t_1[K] = t_2[K] \implies t_1 = t_2

が成り立つことをいいます。スーパーキーであって、そのどの真部分集合もスーパーキーでないものを候補キーと呼びます。候補キーが複数あるとき、設計者が 1 つを選んで主キー（primary key）と宣言します。候補キーに属する属性を主属性、そうでない属性を非主属性と呼びます。

関係スキーマ $S$ の属性集合 $X \subseteq S$ が、関係スキーマ $R$ の主キー $K$ への外部キーであるとは、 $S$ のどのインスタンス $s$ と対応する $R$ のインスタンス $r$ についても

\forall t \in s,\ \exists u \in r,\quad t[X] = u[K]

が成り立つことを要求する制約をいいます（ $t[X]$ が NULL の場合を除きます）。この制約を参照整合性と呼びます。

主キーは「行を指し示す住所」、外部キーは「その住所への参照」です。プログラミング言語でいえば主キーがオブジェクトの同一性、外部キーがポインタに当たり、参照整合性は「ぶら下がりポインタを作らせない」という約束に当たります。

以降、この記事を通じて次の受注データベースを例に使います。属性を 1 文字で表します。

記号	$O$	$D$	$C$	$N$	$S$	$P$	$M$	$U$	$Q$
意味	受注番号	受注日	顧客ID	顧客名	顧客住所	商品ID	商品名	単価	数量

例 1.1 の 1 枚の表は $R = \{O, D, C, N, S, P, M, U, Q\}$ 上の関係です。

3. SQL の基本操作

SQL は関係モデルに対する事実上の標準言語です。ここでは、後の議論で使う 5 つの操作を、正規化済みの 4 つのテーブルの上で確認します。テーブルは次のとおりです（作り方は §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 が外部キー宣言で、定義 2.2 の参照整合性を DBMS に強制させる指定です。存在しない customer_id を持つ受注を挿入しようとすると、DBMS がその INSERT を拒否します。整合性をアプリケーション側の if 文で守ろうとすると、経路が増えるたびに漏れが生じます。DBMS に宣言しておけば、どの経路から来ても守られます。

INSERT は関係にタプルを追加します。

INSERT INTO customers (customer_id, name, address) VALUES
  ('C01', '田中商事', '東京都千代田区'),
  ('C02', '佐藤工業', '大阪市北区');

INSERT INTO products (product_id, name, unit_price) VALUES
  ('P01', 'ボルト', 120),
  ('P02', 'ナット',  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 は選択（条件を満たす行の抽出、関係代数の $\sigma$ ）と射影（列の抽出、 $\pi$ ）を合わせたものです。

SELECT product_id, quantity
FROM   order_items
WHERE  order_id = 1001;

結果は $\pi_{P, Q}(\sigma_{O = 1001}(\mathrm{order\_items}))$ 、すなわち 2 行 ('P01', 10), ('P02', 25) です。

UPDATE と DELETE は既存の行の書き換えと削除です。

UPDATE customers SET address = '横浜市西区' WHERE customer_id = 'C01';
DELETE FROM order_items WHERE order_id = 1002 AND product_id = 'P01';

例 1.1 と比べてください。住所の更新は customers の 1 行だけを触ります。受注を消しても顧客は消えません。正規化の効果はこの 2 行に凝縮されています。

JOIN は複数の関係を条件で結び付ける操作です。内部結合 $r \bowtie_{\theta} s$ は $r \times s$ のうち条件 $\theta$ を満たすタプルの集合と定義されます。

例 3.1（4 テーブルの結合と集計を最後まで計算する）

受注ごとの合計金額を出します。

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;

計算を追います。まず orders と order_items の結合で 3 行できます（受注 1001 が 2 行、1002 が 1 行）。それぞれに customers と products を結合すると、次の中間結果になります。

order_id	customer	product_id	quantity	unit_price	小計
1001	田中商事	P01	10	120	1200
1001	田中商事	P02	25	80	2000
1002	佐藤工業	P01	4	120	480

GROUP BY o.order_id, c.name で受注番号ごとにまとめ、SUM を取ります。

order_id	customer	total
1001	田中商事	3200
1002	佐藤工業	480

$1200 + 2000 = 3200$ 、 $480$ です。例 1.1 の 1 枚表なら結合は不要でしたが、その代わりに更新異常を抱えていました。正規化は、更新時の安全を、参照時の結合コストで買う取引です。

注意 3.2

例 3.1 の集計には、実務では見過ごせない欠陥があります。単価を products から引いているため、商品の値上げをすると過去の受注の合計金額まで変わってしまうのです。「商品 P01 の現在の単価は 120 円である」と「受注 1001 の時点での P01 の単価は 120 円だった」は別の事実です。後者が必要なら、order_items に unit_price_at_order を持たせます。これは重複に見えますが、関数従属 $P \to U$ が成り立つのは「現在」についてだけで、受注時点の単価は $P$ から決まらないため、正規化違反ではありません。正規形の判定は、属性の見た目ではなく、成り立っている関数従属で決まります。

4. 関数従属と属性閉包

正規化の議論をするには、「この列の値が決まれば、あの列の値も決まる」という関係を形式化する必要があります。

定義 4.1（関数従属）

関係スキーマ $R$ と $X, Y \subseteq R$ に対し、 $R$ 上の関係 $r$ が関数従属 $X \to Y$ を満たすとは

\forall t_1, t_2 \in r,\quad t_1[X] = t_2[X] \implies t_1[Y] = t_2[Y]

が成り立つことをいいます。 $Y \subseteq X$ のとき $X \to Y$ は任意の $r$ で成り立つので、これを自明な関数従属と呼びます。

関数従属の集合 $F$ が与えられたとき、 $F$ のすべてを満たす関係を** $F$ -正当と呼びます。 $F$ -正当なすべての関係が $X \to Y$ を満たすとき、 $X \to Y$ は $F$ から論理的に導かれる**といい、 $F \models X \to Y$ と書きます。 $F \models X \to Y$ なる $X \to Y$ 全体を $F^{+}$ と書きます。

定義 2.2 と見比べると、 $K$ がスーパーキーであることは $K \to R$ が成り立つことに他なりません。つまりキーは関数従属の特別な場合です。

受注の例では、成り立つ関数従属の基底として次を取ります。

F = \{\ O \to DC,\quad C \to NS,\quad P \to MU,\quad OP \to Q\ \}

読み下すと、「受注番号が決まれば受注日と顧客が決まる」「顧客 ID が決まれば顧客名と住所が決まる」「商品 ID が決まれば商品名と単価が決まる」「受注番号と商品 ID が決まれば数量が決まる」です。どれも業務上の事実であり、データを見て推測するものではありません。関数従属は業務の仕様であって、たまたま今のデータが満たしている性質ではないという点は強調しておきます。

$F^{+}$ は一般に巨大ですが、実際に必要なのは「特定の $X$ から何が決まるか」だけです。それを与えるのが属性閉包です。

定義 4.2（属性閉包）

$X \subseteq R$ に対し、 $X$ の属性閉包 $X^{+}$ を次の手続きの結果と定めます。

$X^{+} := X$ とする。
$F$ の中に $V \to W$ であって $V \subseteq X^{+}$ かつ $W \not\subseteq X^{+}$ なるものがある限り、 $X^{+} := X^{+} \cup W$ とする。
そのようなものが無くなったら終了。

$R$ は有限で $X^{+}$ は各ステップで真に増えるので、この手続きは高々 $|R|$ 回の追加で停止します。

補題 4.3（属性閉包定理）

関係スキーマ $R$ 、関数従属集合 $F$ 、 $X, Y \subseteq R$ に対し、

F \models X \to Y \iff Y \subseteq X^{+}

が成り立ちます。

証明（補題 4.3）

（ $\Leftarrow$ ）健全性。 $X^{+}$ の構成における追加の回数についての帰納法で、「 $F$ -正当な任意の関係 $r$ は $X \to X^{+}$ を満たす」ことを示します。

初期状態では $X^{+} = X$ であり、 $X \to X$ は自明な関数従属なのでどんな $r$ でも成り立ちます。

帰納段階。現時点の値を $Z$ と書き、 $r$ が $X \to Z$ を満たしていると仮定します。手続きが $V \to W \in F$ （ $V \subseteq Z$ ）を使って $Z' = Z \cup W$ に更新したとします。 $t_1, t_2 \in r$ が $t_1[X] = t_2[X]$ を満たすとすると、帰納法の仮定より $t_1[Z] = t_2[Z]$ です。 $V \subseteq Z$ なので $t_1[V] = t_2[V]$ が従い、 $r$ は $F$ -正当だから $V \to W$ を満たし、よって $t_1[W] = t_2[W]$ です。したがって $t_1[Z \cup W] = t_2[Z \cup W]$ 、すなわち $r$ は $X \to Z'$ を満たします。

停止時の $Z$ が $X^{+}$ なので、 $F \models X \to X^{+}$ が示せました。 $Y \subseteq X^{+}$ なら $t_1[X^{+}] = t_2[X^{+}]$ から $t_1[Y] = t_2[Y]$ が出るので $F \models X \to Y$ です。

（ $\Rightarrow$ ）完全性。 対偶を示します。 $Y \not\subseteq X^{+}$ と仮定し、 $F$ -正当でありながら $X \to Y$ を満たさない関係を 1 つ作ります。

$E \in Y \setminus X^{+}$ を取ります。定義域はすべて $\{0, 1\}$ を含むとしてよい（含まなければ 2 元を選び直せばよい）ので、次の 2 つのタプルからなる関係 $r = \{t_1, t_2\}$ を考えます。

t_1[A] = 0 \ \ (\forall A \in R), \qquad t_2[A] = \begin{cases} 0 & (A \in X^{+}) \\ 1 & (A \notin X^{+}) \end{cases}

$E \notin X^{+}$ より $t_1[E] = 0 \ne 1 = t_2[E]$ なので $t_1 \ne t_2$ であり、 $r$ はちょうど 2 タプルからなります。

$r$ が $F$ -正当であることを示します。 $V \to W \in F$ を任意に取り、2 つの場合に分けます。

$V \subseteq X^{+}$ の場合。定義 4.2 の手続きは停止しているので $W \subseteq X^{+}$ です（さもなければ $V \to W$ でさらに追加できてしまい、停止していません）。よって $V, W$ ともに $X^{+}$ に含まれ、その上では $t_1$ と $t_2$ はどちらも $0$ を取って一致します。ゆえに $V \to W$ は満たされます。
$V \not\subseteq X^{+}$ の場合。 $B \in V \setminus X^{+}$ を取ると $t_1[B] = 0 \ne 1 = t_2[B]$ なので $t_1[V] \ne t_2[V]$ です。 $r$ には $t_1, t_2$ しかないため、 $V$ 上で一致する相異なるタプルの組は存在せず、 $V \to W$ は空虚に満たされます。

一方、 $X \subseteq X^{+}$ より $t_1[X] = t_2[X] = 0$ ですが、 $E \in Y$ で $t_1[E] \ne t_2[E]$ なので $t_1[Y] \ne t_2[Y]$ です。よって $r$ は $X \to Y$ を満たしません。 $F$ -正当な反例が構成できたので $F \not\models X \to Y$ です。

系 4.4（スーパーキーの判定）

$K \subseteq R$ がスーパーキーであることと $K^{+} = R$ であることは同値です。

証明（系 4.4）

$K$ がスーパーキーであるとは、 $F$ -正当なすべての関係で $K \to R$ が成り立つこと、すなわち $F \models K \to R$ です。補題 4.3 よりこれは $R \subseteq K^{+}$ と同値で、常に $K^{+} \subseteq R$ なので $K^{+} = R$ と同値です。

例 4.5（受注スキーマの候補キーを求める）

$R = \{O, D, C, N, S, P, M, U, Q\}$ 、 $F = \{O \to DC,\ C \to NS,\ P \to MU,\ OP \to Q\}$ とします。

$\{O, P\}^{+}$ を計算します。

$X^{+} = \{O, P\}$ 。
$O \to DC$ が使える（ $O \in X^{+}$ ）ので $X^{+} = \{O, P, D, C\}$ 。
$P \to MU$ が使えるので $X^{+} = \{O, P, D, C, M, U\}$ 。
$C \to NS$ が使えるので $X^{+} = \{O, P, D, C, M, U, N, S\}$ 。
$OP \to Q$ が使えるので $X^{+} = \{O, P, D, C, M, U, N, S, Q\} = R$ 。

よって系 4.4 より $\{O, P\}$ はスーパーキーです。極小性を確かめます。 $\{O\}^{+} = \{O, D, C, N, S\} \ne R$ （ $P, M, U, Q$ が入りません）、 $\{P\}^{+} = \{P, M, U\} \ne R$ です。どちらも $R$ に届かないので、 $\{O, P\}$ は候補キーです。

さらに、 $Q$ を含む関数従属は $OP \to Q$ しかなく、右辺にしか現れない属性 $Q$ はどの候補キーにも属せません。また $O$ と $P$ はどの関数従属の右辺にも現れないので、どのスーパーキーにも必ず含まれます。したがって候補キーは $\{O, P\}$ ただ 1 つです。主属性は $O, P$ の 2 つ、残る $D, C, N, S, M, U, Q$ は非主属性です。

5. 正規化：第 1〜第 3 正規形

定義 5.1（第 1・第 2・第 3 正規形）

関係スキーマ $R$ と関数従属集合 $F$ が与えられているとします。

第 1 正規形（1NF）：すべての属性の定義域が原子的な値からなること。すなわち、1 つのセルに複数の値のリストや入れ子の表を入れないこと。

第 2 正規形（2NF）：1NF であり、かつ、どの候補キー $K$ 、どの非主属性 $A$ 、どの真部分集合 $X \subsetneq K$ についても $F \not\models X \to A$ であること。言い換えると、非主属性が候補キーの一部だけに従属することがないこと（部分関数従属がないこと）。

第 3 正規形（3NF）：1NF であり、かつ $F^{+}$ に属する任意の非自明な関数従属 $X \to A$ （ $A \in R \setminus X$ は単一属性としてよい）について、次のいずれかが成り立つこと。

$X$ が $R$ のスーパーキーである、または
$A$ が主属性である。

3NF の条件 1 を満たす関数従属だけを許す（条件 2 を認めない）と、**ボイス・コッド正規形（BCNF）**になります。これらの包含関係は BCNF $\subsetneq$ 3NF $\subsetneq$ 2NF $\subsetneq$ 1NF です。

なぜこの階段を上るのか。理由は次の命題に尽きます。

命題 5.2（キーでない決定項は必ず冗長を生む）

関係スキーマ $R$ と関数従属集合 $F$ を考えます。 $X \subseteq R$ と $B \in R \setminus X$ が

$F \models X \to B$ （ $X$ は $B$ を決める）、かつ
$X$ は $R$ のスーパーキーでない

を満たすとします。このとき、 $F$ -正当であって、しかも

t_1 \ne t_2,\qquad t_1[X] = t_2[X],\qquad t_1[B] = t_2[B]

を満たす 2 つのタプル $t_1, t_2$ を含む関係 $r$ が存在します。すなわち「 $X$ の値が $x$ のとき $B$ の値は $b$ である」という 1 つの事実が、2 行に重複して格納されうる状態になります。

証明（命題 5.2）

$X$ がスーパーキーでないので、系 4.4 より $X^{+} \ne R$ です。よって $E \in R \setminus X^{+}$ が取れます。

補題 4.3 の完全性の証明で構成したのと同じ 2 タプル関係 $r = \{t_1, t_2\}$ を取ります。すなわち $t_1$ は全属性で $0$ 、 $t_2$ は $X^{+}$ 上で $0$ 、 $R \setminus X^{+}$ 上で $1$ とします。同じ場合分けにより $r$ は $F$ -正当です。

$t_1[E] = 0 \ne 1 = t_2[E]$ なので $t_1 \ne t_2$ です。 $X \subseteq X^{+}$ なので $t_1[X] = t_2[X]$ です。さらに $F \models X \to B$ と補題 4.3 より $B \in X^{+}$ なので $t_1[B] = t_2[B] = 0$ です。これで 3 条件がすべて満たされました。

命題 5.2 は「冗長が起きることがある」ではなく「冗長を含むインスタンスが業務ルール上まったく正当である」と言っています。正当である以上、いつかは現れます。そして冗長があれば、片方だけを書き換える更新異常が起こりえます。例 1.1 の住所の重複は、 $C \to S$ において $C$ が $R$ のスーパーキーでない（候補キーは $\{O, P\}$ だけでした）ことの帰結だったわけです。

逆に、3NF の条件 1 を満たしていれば $X$ がスーパーキーなので、 $t_1[X] = t_2[X]$ から $t_1 = t_2$ が出て重複行は存在せず、この形の冗長は起きません。3NF が条件 2（ $A$ が主属性）を例外として認めているのは妥協で、その分の冗長は残ります。BCNF はこの妥協を許しませんが、代わりに関数従属を保存できない分解しか作れない場合があります（定理 6.4 の後の注意を参照）。

flowchart TB
A["非正規形<br/>セルに複数値・繰り返し列"] -->|"値を原子化し、繰り返しを行に展開"| B["第1正規形 (1NF)"]
B -->|"候補キーの一部への従属を別表に分離"| C["第2正規形 (2NF)"]
C -->|"非主属性を経由する推移的従属を別表に分離"| D["第3正規形 (3NF)"]
D -->|"主属性への従属も許さない"| E["ボイス・コッド正規形 (BCNF)"]

正規化の 3 段階と、各段階で取り除かれる従属

例 5.3（受注スキーマを 1NF から 3NF まで分解する）

出発点は例 1.1 の $R = \{O, D, C, N, S, P, M, U, Q\}$ 、 $F = \{O \to DC,\ C \to NS,\ P \to MU,\ OP \to Q\}$ です。候補キーは例 4.5 で求めたとおり $\{O, P\}$ の 1 つだけです。

1NF の確認。 もし元データが「商品欄に P01:10, P02:25 と 2 件書く」形式だったなら 1NF 違反です。この場合、1 受注 1 商品を 1 行に展開すれば 1NF になります。例 1.1 の表はすでにこの形なので 1NF です。

2NF への分解。 非主属性 $D, C, N, S, M, U$ について、候補キー $\{O, P\}$ の真部分集合からの従属を探します。

$O \to D$ 、 $O \to C$ が成り立ち、 $\{O\} \subsetneq \{O, P\}$ です。さらに $O \to C \to NS$ より $O \to N$ 、 $O \to S$ も成り立ちます。部分関数従属です。
$P \to M$ 、 $P \to U$ が成り立ち、 $\{P\} \subsetneq \{O, P\}$ です。部分関数従属です。

そこで $O$ が決める属性の組と $P$ が決める属性の組を切り出します。

R_1 = \{O, D, C, N, S\},\quad R_2 = \{P, M, U\},\quad R_3 = \{O, P, Q\}

$R_3$ の候補キーは $\{O, P\}$ 、非主属性は $Q$ だけで、 $O \to Q$ も $P \to Q$ も成り立たない（ $\{O\}^{+}$ にも $\{P\}^{+}$ にも $Q$ は入りません）ので $R_3$ は 2NF です。 $R_2$ の候補キーは $\{P\}$ で、真部分集合は空集合のみ、 $\varnothing \to M$ は成り立たないので 2NF です。 $R_1$ の候補キーは $\{O\}$ で、同様に 2NF です。

3NF への分解。 $R_1$ を調べます。候補キーは $\{O\}$ で、非自明な従属 $C \to N$ が $F^{+}$ にあります。 $\{C\}^{+} = \{C, N, S\} \ne R_1$ なので $C$ は $R_1$ のスーパーキーではなく、 $N$ は $R_1$ の主属性でもありません（ $R_1$ の候補キーは $\{O\}$ だけ）。よって 3NF 違反です。これは $O \to C \to NS$ という推移的従属が原因です。 $C$ が決める部分を切り出します。

R_{1a} = \{O, D, C\},\qquad R_{1b} = \{C, N, S\}

最終的な分解は

\{O, D, C\},\quad \{C, N, S\},\quad \{P, M, U\},\quad \{O, P, Q\}

の 4 つで、これが §3 の orders、customers、products、order_items に対応します。それぞれで 3NF 条件を確認します。 $\{O, D, C\}$ では非自明な従属は $O \to DC$ のみで $O$ が候補キー、 $\{C, N, S\}$ では $C \to NS$ のみで $C$ が候補キー、 $\{P, M, U\}$ では $P \to MU$ のみで $P$ が候補キー、 $\{O, P, Q\}$ では $OP \to Q$ のみで $\{O, P\}$ が候補キーです。すべて 3NF の条件 1 を満たすので、実は BCNF でもあります。

erDiagram
CUSTOMERS ||--o{ ORDERS : "発注する"
ORDERS ||--|{ ORDER_ITEMS : "含む"
PRODUCTS ||--o{ ORDER_ITEMS : "指定される"
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
}

3NF 分解後のスキーマ（線は外部キー参照）

注意 5.4

正規化は目的ではなく手段です。3NF まで分解したうえで、参照が極端に多く更新がほとんど起きない箇所（集計済みの月次売上など）を、あえて重複させて別テーブルに持つことがあります。これを非正規化と呼びます。非正規化を行うときの条件は 1 つで、冗長を同期させる責任を誰が持つかを明示することです。トリガ、マテリアライズドビュー、バッチ再計算のいずれかで機械的に同期させ、アプリケーションの書き込み処理に「2 か所を更新する」義務を負わせないでください。命題 5.2 が示すとおり、人手の同期はいずれ破れます。

6. 分解の正しさ：無損失結合

例 5.3 では表を分けました。しかし、分け方によっては元の情報が失われることがあります。この危険を排除する条件を述べます。

定義 6.1（無損失結合分解）

関係スキーマ $R$ とその部分集合 $R_1, R_2$ が $R_1 \cup R_2 = R$ を満たすとします。関数従属集合 $F$ に対し、この分解が無損失結合分解であるとは、 $F$ -正当な任意の関係 $r$ について

r = \pi_{R_1}(r) \bowtie \pi_{R_2}(r)

が成り立つことをいいます。ここで $\bowtie$ は共通属性 $R_1 \cap R_2$ の値が等しいタプルどうしを結合する自然結合です。

例 6.2（情報が失われる分解）

$R = \{A, B, C\}$ で関数従属が何もない（ $F = \varnothing$ ）とし、 $r = \{(1,1,1),\ (2,1,2)\}$ を取ります。 $R_1 = \{A, B\}$ 、 $R_2 = \{B, C\}$ に分解すると

\pi_{R_1}(r) = \{(1,1), (2,1)\},\qquad \pi_{R_2}(r) = \{(1,1), (1,2)\}

です。 $B$ の値はどちらも $1$ しかないので、自然結合は $2 \times 2 = 4$ 個のタプルを作ります。

\pi_{R_1}(r) \bowtie \pi_{R_2}(r) = \{(1,1,1),\ (1,1,2),\ (2,1,1),\ (2,1,2)\}

元の $r$ に無かった $(1,1,2)$ と $(2,1,1)$ が生まれました。分解して結合し直したら嘘のデータが増えたわけです。どんな分解でも常に $r \subseteq \pi_{R_1}(r) \bowtie \pi_{R_2}(r)$ ですから、失われるのは行ではなく「どの値とどの値が同じ行にあったか」という結び付きの情報です。

定理 6.3（ヒースの定理）

関係スキーマ $R$ を互いに素な 3 つの部分集合 $X, Y, Z$ に分割し（ $R = X \cup Y \cup Z$ 、 $X \cap Y = Y \cap Z = Z \cap X = \varnothing$ ）、関数従属集合 $F$ が $F \models X \to Y$ を満たすとします。このとき $R_1 = X \cup Y$ 、 $R_2 = X \cup Z$ への分解は無損失結合分解です。すなわち $F$ -正当な任意の関係 $r$ について

r = \pi_{X \cup Y}(r) \bowtie \pi_{X \cup Z}(r)

が成り立ちます。

証明（定理 6.3）

$R_1 \cap R_2 = X$ であることに注意します（ $Y \cap Z = \varnothing$ なので共通部分は $X$ ちょうどです）。

（ $\subseteq$ ） $t \in r$ とします。 $t_1 = t[X \cup Y] \in \pi_{X \cup Y}(r)$ 、 $t_2 = t[X \cup Z] \in \pi_{X \cup Z}(r)$ であり、両者は $X$ 上で $t[X]$ に一致します。よって自然結合の定義からこの 2 つは結合され、その結果は $X$ 上で $t[X]$ 、 $Y$ 上で $t[Y]$ 、 $Z$ 上で $t[Z]$ を取るタプル、すなわち $t$ 自身です。ゆえに $t \in \pi_{X \cup Y}(r) \bowtie \pi_{X \cup Z}(r)$ です。この向きは関数従属を使いません。

（ $\supseteq$ ） $u$ を右辺のタプルとします。自然結合の定義より、ある $t_1, t_2 \in r$ が存在して

u[X \cup Y] = t_1[X \cup Y],\qquad u[X \cup Z] = t_2[X \cup Z]

となります。特に $t_1[X] = u[X] = t_2[X]$ です。ここで仮定 $F \models X \to Y$ と $r$ が $F$ -正当であることから、 $r$ は $X \to Y$ を満たします。 $t_1[X] = t_2[X]$ なので $t_1[Y] = t_2[Y]$ が従います。

すると $t_2$ は、 $X$ 上で $u[X]$ 、 $Z$ 上で $u[Z]$ 、そして $Y$ 上で $t_2[Y] = t_1[Y] = u[Y]$ を取ります。 $R = X \cup Y \cup Z$ なので $t_2$ は全属性で $u$ と一致し、 $u = t_2 \in r$ です。

例 6.2 が失敗したのは、まさに $B \to A$ も $B \to C$ も成り立たなかったからです。例 5.3 の分解はすべて定理 6.3 の形になっています。例えば $R_1 = \{O, D, C, N, S\}$ を $\{O, D, C\}$ と $\{C, N, S\}$ に分けたとき、 $X = \{C\}$ 、 $Y = \{N, S\}$ 、 $Z = \{O, D\}$ と取れば $C \to NS$ が成り立つので無損失です。「切り出す側の共通列が、切り出される側の決定項になっている」ように分割すれば、情報は失われません。これが「 $C$ が決める属性をまとめて別表にする」という手順の正当化です。

分解にはもう 1 つ望ましい性質があります。従属性保存、すなわち元の $F$ の制約が分解後の各表への制約だけでチェックできることです。これが崩れると、各表を単独で見れば正しいのに全体としては業務ルールに違反する状態を許してしまい、検査のために結合が必要になります。

定理 6.4（3NF 合成定理）

任意の関係スキーマ $R$ と任意の関数従属集合 $F$ に対し、 $R$ の分解 $R_1, \ldots, R_k$ であって次の 3 条件をすべて満たすものが存在し、 $F$ の大きさの多項式時間で構成できます。

各 $R_i$ は（ $F$ を $R_i$ に射影した従属集合に関して）3NF である。
分解は無損失結合分解である。
分解は従属性保存である。

注意 6.5

証明は Appendix に構成法（3NF 合成アルゴリズム）の概要を示します。完全な証明は Abiteboul–Hull–Vianu『Foundations of Databases』第 11 章、または Ullman『Principles of Database and Knowledge-Base Systems, Volume I』第 7 章にあります。

BCNF については事情が異なります。無損失分解は常に得られますが、従属性保存は一般には達成できません。標準的な反例は $R = \{A, B, C\}$ 、 $F = \{AB \to C,\ C \to B\}$ です。候補キーは $\{A, B\}$ と $\{A, C\}$ で、 $C \to B$ の $C$ はスーパーキーでないため BCNF 違反ですが、 $B$ は主属性なので 3NF は満たしています。この $R$ を BCNF に分解すると、どう分けても $AB \to C$ が 1 つの表の中に収まらず、保存できません。3NF が実務の標準とされているのは、この「3 条件を同時に満たせる最強の正規形」という位置付けによります。

7. NoSQL との違いと使い分け

2000 年代後半、Web サービスの規模が単一サーバの限界を超えたことをきっかけに、関係モデル以外のデータモデルが広く使われるようになりました。総称して NoSQL と呼ばれます。代表的な 4 系統を挙げます。

系統	データモデル	代表例	得意なこと
キー・バリュー（KVS）	キーから不透明な値への写像	Redis, Amazon DynamoDB	キー指定の超高速な読み書き、セッション・キャッシュ
ドキュメント型	キーから JSON 様の入れ子文書へ	MongoDB, Couchbase	集約単位でまとめて読み書きする、スキーマが揺れるデータ
ワイドカラム型	行キー + 列族	Apache Cassandra, HBase	書き込み量が極端に多い時系列・ログ
グラフ型	頂点と辺	Neo4j	多段のたどり（友人の友人、経路探索）

関係データベースとの本質的な違いは 3 点に整理できます。

第一に、結合の実行時期です。 関係モデルは事実を最小単位に分けて保存し、必要になった時点で JOIN で組み立てます（例 3.1）。ドキュメント型は逆に、一緒に読むものを一緒に書くという方針で、あらかじめ組み立てた形で保存します。

例 7.1（同じ受注をドキュメント型で表す）

例 5.3 の 4 テーブルに分けた受注 1001 を、ドキュメント型では 1 つの文書にします。

{
  "_id": 1001,
  "order_date": "2026-04-01",
  "customer": { "id": "C01", "name": "田中商事", "address": "東京都千代田区" },
  "items": [
    { "product_id": "P01", "name": "ボルト", "unit_price": 120, "quantity": 10 },
    { "product_id": "P02", "name": "ナット", "unit_price":  80, "quantity": 25 }
  ]
}

利点は明確です。「受注 1001 の内容を表示する」という操作が、キー 1001 による 1 回の読み取りで済みます。結合は不要で、データが複数サーバに分散していてもこの文書は必ず 1 台に載っています。

代償も明確です。顧客名が受注ごとに複製されており、これは命題 5.2 が指摘したとおりの冗長です。田中商事の社名が変わったら、その顧客の全受注文書を書き換えなければなりません。ドキュメント型はこの代償を承知のうえで受け入れる設計です。受け入れられるのは、受注時点の顧客名を保存したい業務（注意 3.2 と同じ理屈）や、社名変更が事実上起きない業務に限られます。

なお、items が配列になっている点は定義 5.1 の 1NF に違反しています。ドキュメント型は 1NF を意図的に捨てたモデルだと言えます。

第二に、水平分割（シャーディング）のしやすさです。 結合の相手が別のサーバにいると、ネットワーク越しにデータを寄せ集める必要が生じ、そのたびに往復の遅延が乗ります（端点間遅延の分解（命題 2.2）［ネットワーク（TCP/IP）］）。ドキュメント型や KVS はキーのハッシュで機械的に分割でき、1 回の操作が必ず 1 台で完結するので、台数を増やせば性能がほぼ線形に伸びます（負荷を $n$ 台に均等分散したときの応答時間については系 5.3［クラウドコンピューティング］を参照）。関係データベースでも分割はできますが、分割をまたぐ結合とトランザクションが壁になります。

第三に、一貫性の保証です。 関係データベースは ACID（原子性・一貫性・独立性・永続性）を満たすトランザクションを提供し、「口座 A から引いて口座 B に足す」を不可分に実行できます。分散システムでは、E. Brewer の CAP 定理として知られる制約があり、ネットワーク分断が起きている間は、強い一貫性と可用性の両方を同時に満たすことができません。多くの NoSQL はこの局面で可用性（定義 6.1［クラウドコンピューティング］）を選び、結果整合性（分断が解消すれば時間とともに値が揃う）を提供します。書き込みが返ってきた直後に別のノードを読むと古い値が見えることがある、という前提でアプリケーションを書く必要があります。

判断の目安をまとめます。

状況	推奨
複数の実体をまたぐ整合性（在庫と受注、口座間振替）が必要	関係データベース
問い合わせの形が事前に決まらない（分析、管理画面の絞り込み）	関係データベース
常に単一のキーで読み書きし、遅延に厳しい（セッション、カート）	KVS
集約単位が明確で、その単位でまるごと読み書きする	ドキュメント型
書き込み量が読み取りを大きく上回り、時系列で追記される	ワイドカラム型
多段の関係をたどる（推薦、経路、権限の継承）	グラフ型

現在は境界が曖昧になっています。PostgreSQL の JSONB 型は文書を列に格納して索引を張れますし、多くの NoSQL がトランザクションを部分的に導入しています。まず正規化された関係モデルで設計し、実測で問題が出た箇所だけを別の道具に置き換える、という順序が安全だと思います。データベースの選定は、運用（バックアップ、監視、フェイルオーバー）まで含めた判断になるため、クラウドコンピューティングのマネージドサービス（サービスモデル（定義 2.2）［クラウドコンピューティング］）の選択肢と合わせて検討してください。待機系を用意したときに可用性がどれだけ上がるかは命題 6.2［クラウドコンピューティング］の形で見積もれます。スキーマ定義そのものはコードと同じくファイルで管理し、バージョン管理システム（Git）でマイグレーションの履歴（コミットグラフ（定義 4.1）［バージョン管理システム Git］）を残すのが標準的なやり方です。分散データベースの挙動を理解するには、ネットワークの遅延と分断の実態を知る必要があるので、ネットワーク（TCP/IP）も参考になります。

8. 演習

演習 8.1標準

$R = \{A, B, C, D, E\}$ 、 $F = \{A \to BC,\ CD \to E,\ B \to D,\ E \to A\}$ とします。

$R$ の候補キーをすべて求めてください。
$R$ は 3NF ですか。BCNF ですか。理由を述べてください。

解答

1. 属性閉包を計算します。

$\{A\}^{+}$ ： $A \to BC$ より $\{A,B,C\}$ 、 $B \to D$ より $\{A,B,C,D\}$ 、 $CD \to E$ より $\{A,B,C,D,E\} = R$ 。よって $\{A\}$ はスーパーキーで、真部分集合は空集合のみ（ $\varnothing^{+} = \varnothing \ne R$ ）なので候補キーです。

$\{E\}^{+}$ ： $E \to A$ より $\{E,A\}$ 、以下 $A$ の場合と同じく $R$ に到達します。よって $\{E\}$ も候補キーです。

$\{B\}^{+} = \{B, D\}$ 、 $\{C\}^{+} = \{C\}$ 、 $\{D\}^{+} = \{D\}$ で、いずれも $R$ に届きません。

$\{B, C\}^{+}$ ： $B \to D$ より $\{B,C,D\}$ 、 $CD \to E$ より $\{B,C,D,E\}$ 、 $E \to A$ より $R$ 。 $\{B\}$ も $\{C\}$ もスーパーキーでないので $\{B,C\}$ は候補キーです。

$\{C, D\}^{+}$ ： $CD \to E$ より $\{C,D,E\}$ 、 $E \to A$ より $\{C,D,E,A\}$ 、 $A \to BC$ より $R$ 。 $\{C\}, \{D\}$ はスーパーキーでないので $\{C,D\}$ も候補キーです。

$\{B, D\}^{+} = \{B, D\}$ なのでこれは候補キーではありません。以上より候補キーは $\{A\}$ 、 $\{E\}$ 、 $\{B,C\}$ 、 $\{C,D\}$ の 4 つです。

2. 主属性を数えます。 $A, E, B, C, D$ はいずれかの候補キーに現れるので、すべての属性が主属性です。したがって定義 5.1 の 3NF 条件の 2 番目が常に成り立ち、 $R$ は 3NF です。

BCNF ではありません。 $B \to D$ は非自明で、 $\{B\}^{+} = \{B, D\} \ne R$ なので系 4.4 より $B$ はスーパーキーではありません。BCNF は条件 1（決定項がスーパーキー）しか認めないので違反です。注意 6.5 のとおり、この差は「主属性の冗長を許すかどうか」の妥協点の違いです。

演習 8.2標準

大学の履修管理として $R = \{\mathit{StudentID},\ \mathit{StudentName},\ \mathit{CourseID},\ \mathit{CourseName},\ \mathit{TeacherID},\ \mathit{TeacherName},\ \mathit{Grade}\}$ を考え、関数従属を

\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}

とします（1 科目の担当教員は 1 人、1 人の教員は複数科目を持ちうる）。候補キーを求め、2NF 違反と 3NF 違反をそれぞれ指摘し、3NF まで分解してください。各分解が無損失であることも述べてください。

解答

記号を $S, SN, C, CN, T, TN, G$ と略します。 $F = \{S \to SN,\ C \to CN\,T,\ T \to TN,\ SC \to G\}$ です。

候補キー。 $\{S, C\}^{+}$ ： $S \to SN$ で $SN$ 、 $C \to CN\,T$ で $CN, T$ 、 $T \to TN$ で $TN$ 、 $SC \to G$ で $G$ が入り $R$ 全体になります。 $\{S\}^{+} = \{S, SN\}$ 、 $\{C\}^{+} = \{C, CN, T, TN\}$ でどちらも $R$ に届きません。また $S$ と $C$ はどの従属の右辺にも現れないので、すべてのスーパーキーに含まれます。よって候補キーは $\{S, C\}$ のみ、主属性は $S, C$ です。

2NF 違反。 非主属性 $SN$ が候補キーの真部分集合 $\{S\}$ に従属します（ $S \to SN$ ）。同様に $CN, T, TN$ が $\{C\}$ に従属します（ $C \to CN$ 、 $C \to T$ 、 $C \to T \to TN$ ）。いずれも部分関数従属です。

3NF 違反。 2NF 違反を解消して $\{C, CN, T, TN\}$ を作ったとしても、候補キーは $\{C\}$ で、 $T \to TN$ において $\{T\}^{+} = \{T, TN\}$ はこの表の全属性ではなく $T$ はスーパーキーでありません。 $TN$ も主属性ではないので 3NF 違反（推移的従属 $C \to T \to TN$ ）です。

分解。

\{S, SN\},\quad \{C, CN, T\},\quad \{T, TN\},\quad \{S, C, G\}

各表の非自明な従属はそれぞれ $S \to SN$ 、 $C \to CN\,T$ 、 $T \to TN$ 、 $SC \to G$ のみで、左辺がその表の候補キーになっているので 3NF（かつ BCNF）です。

無損失性。 すべての分割が定理 6.3 の形です。例えば $R$ から $\{S, SN\}$ を切り出す段階では $X = \{S\}$ 、 $Y = \{SN\}$ 、 $Z = R \setminus \{S, SN\}$ と取ると $S \to SN$ が成り立つので無損失です。 $\{C, CN, T, TN\}$ から $\{T, TN\}$ を切り出す段階では $X = \{T\}$ 、 $Y = \{TN\}$ 、 $Z = \{C, CN\}$ と取ると $T \to TN$ が成り立つので無損失です。無損失分解を繰り返した結果は無損失なので、全体も無損失です。

演習 8.3易

§3 のスキーマに対し、「顧客ごとの累計購入金額を、金額の大きい順に並べて出す。ただし 1 円も買っていない顧客も $0$ 円として含める」という SQL を書いてください。

解答

「買っていない顧客も含める」ので、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;

内側を JOIN（内部結合）にすると、受注のない顧客の行が消えてしまい要件を満たしません。また、受注が 1 件も無い顧客では SUM の対象が全部 NULL になり SUM は NULL を返すので、COALESCE で $0$ に置き換えます。§3 のデータでは C01 が $3200$ 、C02 が $480$ になります。

演習 8.4難

$R = \{A, B, C\}$ 、 $F = \{A \to B\}$ とします。分解 $R_1 = \{A, B\}$ 、 $R_2 = \{B, C\}$ が無損失結合分解でないことを、反例となる $F$ -正当な関係を具体的に構成して示してください。また、無損失になる別の分解を 1 つ挙げ、根拠を述べてください。

解答

反例。 $r = \{(1, 0, 1),\ (2, 0, 2)\}$ を取ります（ $(A, B, C)$ の順）。 $A$ の値 $1, 2$ は相異なるので、 $A \to B$ を満たすべき組は存在せず、 $r$ は $F$ -正当です。

$\pi_{AB}(r) = \{(1,0), (2,0)\}$ 、 $\pi_{BC}(r) = \{(0,1), (0,2)\}$ です。 $B$ の値はどちらも $0$ だけなので、自然結合は $4$ タプル

\{(1,0,1),\ (1,0,2),\ (2,0,1),\ (2,0,2)\}

を返し、元の $r$ に無い $(1,0,2)$ と $(2,0,1)$ を含みます。よって無損失ではありません。原因は共通属性 $B$ が $A$ も $C$ も決めないことで、 $B \to A$ も $B \to C$ も $F$ から導かれません（ $\{B\}^{+} = \{B\}$ ）。

無損失な分解。 $R_1' = \{A, B\}$ 、 $R_2' = \{A, C\}$ とします。 $X = \{A\}$ 、 $Y = \{B\}$ 、 $Z = \{C\}$ と置くと、 $X, Y, Z$ は互いに素で和が $R$ 、かつ $F \models A \to B$ です。定理 6.3 の仮定がすべて満たされるので、この分解は無損失結合分解です。

念のため上の $r$ で確認します。 $\pi_{AB}(r) = \{(1,0), (2,0)\}$ 、 $\pi_{AC}(r) = \{(1,1), (2,2)\}$ で、 $A$ で結合すると $(1,0,1)$ と $(2,0,2)$ の 2 タプルだけが得られ、 $r$ に一致します。

参考文献

E. F. Codd, “A Relational Model of Data for Large Shared Data Banks”, Communications of the ACM 13 (1970), 377–387. 関係モデルと正規化を提案した原論文です。doi:10.1145/362384.362685
S. Abiteboul, R. Hull, V. Vianu, Foundations of Databases, Addison-Wesley, 1995 — 第 8 章（関数従属）と第 11 章（正規形と分解）。関数従属の推論と正規形の理論を厳密に扱っています。著者による全文が webdam.inria.fr/Alice/ で公開されています。
A. Silberschatz, H. F. Korth, S. Sudarshan, Database System Concepts, 7th ed., McGraw-Hill, 2019 — 第 7 章（正規化）と第 3〜4 章（SQL）。学部の標準的な教科書です。
J. D. Ullman, Principles of Database and Knowledge-Base Systems, Volume I, Computer Science Press, 1988 — 第 7 章。3NF 合成アルゴリズムの構成と正当性の証明があります。
M. Kleppmann, Designing Data-Intensive Applications, O’Reilly, 2017 — 第 2 章（データモデルと問い合わせ言語）、第 5〜9 章（複製・分割・トランザクション・一貫性）。関係モデルと NoSQL の比較、および分散環境での一貫性を扱っています。
S. Gilbert, N. Lynch, “Brewer’s Conjecture and the Feasibility of Consistent, Available, Partition-Tolerant Web Services”, ACM SIGACT News 33 (2002), 51–59. CAP 定理の形式的な証明です。doi:10.1145/564585.564601

Appendix: 3NF 合成アルゴリズムの概要

定理 6.4 の分解を作る手順を述べます。証明の細部は注意 6.5 に挙げた文献にあります。

第 1 段階：極小被覆を作る。 関数従属集合 $F$ から、次の 3 条件を満たす $F_c$ （ $F_c^{+} = F^{+}$ を保ちます）を作ります。(a) すべての従属の右辺が単一属性である。(b) どの従属 $X \to A$ についても、 $X$ からどの属性を除いても $F_c$ と同値でなくなる（左辺が極小）。(c) どの従属を除いても $F_c$ と同値でなくなる（従属の個数が極小）。手順は、まず右辺を分解して単一属性にし、次に各従属の左辺の属性を 1 つずつ試しに除いて補題 4.3 で導出可能性を判定し、最後に各従属を 1 つずつ試しに除いて同じ判定を行う、というものです。判定はすべて属性閉包の計算で済むので多項式時間です。

第 2 段階：左辺ごとに表を作る。 $F_c$ の従属を左辺が同じものどうしにまとめ、左辺 $X$ と、その左辺を持つ従属の右辺全体 $A_1, \ldots, A_m$ を合わせた $X \cup \{A_1, \ldots, A_m\}$ を 1 つの関係スキーマとします。この段階で、 $F_c$ のすべての従属がいずれかの表の中に収まるので従属性保存が保証されます。

第 3 段階：候補キーを 1 つ加える。 第 2 段階で作った表のどれも $R$ の候補キーを含んでいない場合、候補キー $K$ を 1 つ選び、 $K$ そのものを属性集合とする表を追加します。これにより無損失結合が保証されます（結合の順序を候補キーから辿れるようになるためです）。

第 4 段階：包含される表を除く。 ある表の属性集合が別の表の属性集合に含まれているとき、小さいほうを捨てます。

例 5.3 の受注スキーマにこの手順を適用すると、 $F$ はすでに極小被覆に近く、左辺ごとにまとめると $\{O, D, C\}$ 、 $\{C, N, S\}$ 、 $\{P, M, U\}$ 、 $\{O, P, Q\}$ の 4 つが得られます。最後の表が候補キー $\{O, P\}$ を含んでいるので第 3 段階の追加は不要です。手作業で分解した結果と一致しました。

この手順の限界。 合成アルゴリズムは 3NF までしか保証しません。各表がさらに BCNF かは個別に確認が必要で、BCNF でない場合に無理に分解すると従属性保存が失われることがあります。実務では 3NF まで分解し、残った例外（主属性への従属）が実際に問題を起こすかを業務の側から判断するのが現実的だと思います。

この記事の誤りを報告する・運営: 夢現技研合同会社・料金プラン・利用条件・特定商取引法に基づく表記