はじめに
最近「達人に学ぶ SQL 徹底指南書 第 2 版」を読みました。
この本では、関係データベースや SQL の背景にある集合論や群論などにも触れられています。
学生時代に学んだ数学が関係データベースの基礎になっていることを知り爽快でした。
関係データベースについて数学的な切り口でまとめてみます ✍
1. 関係とは集合である
関係の定義は、次の式によって与えられます。
関係: $R$ , 属性（列）: $A_i$ , その定義域: $D_i$
$$R \subseteq D_1 \times D_2 \times D_3 \times \cdots \times D_n$$
つまり、関係は、列の定義域の直積の部分集合です。
ex.
属性 $a_1$, $a_2$, $a_3$ がそれぞれ次の定義域を取る場合を考えます。
$$
d_1 = \{1\}, d_2 = \{'\mathrm{m}', '\mathrm{f}'\}, d_3 = \{'\mathrm{r}', '\mathrm{g}', '\mathrm{b}'\}
$$
このとき、直積は次の通り。
| $a_1$ | $a_2$ | $a_3$ |
|---|---|---|
| 1 | m | r |
| 1 | m | g |
| 1 | m | b |
| 1 | f | r |
| 1 | f | g |
| 1 | f | b |
関係（テーブル）は、この部分集合となります。
2. 関係と代数構造
代数構造のうち、次の 3 つについて考えます。
- 群: 加法・減法について閉じている
- 環: 加法・減法・乗法について閉じている
- 体: 加法・減法・乗法・除法について閉じている
関係（テーブル）は、群であり、環であり、体であると言えます。
つまり、テーブル同士を足し算、引き算、掛け算、割り算しても、その結果はテーブルになります。
ex.
加法、減法、乗法について、次のテーブルに対するクエリを例示します。
A
| id | name |
|---|---|
| 1 | 太郎 |
| 2 | 花子 |
| 3 | 次郎 |
B
| id | name |
|---|---|
| 1 | 太郎 |
| 2 | 花子 |
| 4 | 三郎 |
2.1 加法（UNION）
SELECT name FROM A
UNION
SELECT name FROM B;
結果
| name |
|---|
| 太郎 |
| 花子 |
| 次郎 |
| 三郎 |
重複を許す場合は UNION ALL を使います。
ALL オプションを付けると、重複削除のための暗黙のソートが行われないため、パフォーマンスが良いです。
2.2 減法（EXCEPT）
SELECT name FROM A
EXCEPT
SELECT name FROM B;
結果
| name |
|---|
| 次郎 |
2.3 乗法（CROSS JOIN）
SELECT
A.name AS a_name,
B.name AS b_name
FROM
A CROSS JOIN B;
結果
| a_name | b_name |
|---|---|
| 太郎 | 太郎 |
| 太郎 | 花子 |
| 太郎 | 三郎 |
| 花子 | 太郎 |
| 花子 | 花子 |
| 花子 | 三郎 |
| 次郎 | 太郎 |
| 次郎 | 花子 |
| 次郎 | 三郎 |
2.4 除法
演算子は定義されていないが、次の 3 通りで表現できます。
- NOT EXISTS を入れ子にする
- HAVING 句を使う
- 減法で表現する
ex.
EmployeeSkill テーブルから、RequiredSkill テーブルの技術すべてに精通した社員を選択することを考えます。
RequiredSkill
| skill |
|---|
| Oracle |
| UNIX |
| Java |
EmployeeSkill
| emp_id | skill |
|---|---|
| 1 | Oracle |
| 1 | UNIX |
| 1 | Java |
| 1 | C# |
| 2 | Oracle |
| 2 | UNIX |
| 2 | Java |
| 3 | UNIX |
| 3 | Oracle |
| 3 | PHP |
| 3 | Perl |
| 3 | C++ |
| 4 | Perl |
| 5 | Oracle |
結果
| emp_id |
|---|
| 1 |
| 2 |
2.4.1 NOT EXISTS を入れ子にする
SELECT emp_id
FROM EmployeeSkill ES1
WHERE NOT EXISTS (
SELECT skill
FROM RequiredSkill RS
WHERE NOT EXISTS (
SELECT 1
FROM EmployeeSkill ES2
WHERE ES2.emp_id = ES1.emp_id
AND ES2.skill = RS.skill
)
);
2.4.2 HAVING 句を使う
SELECT emp_id
FROM EmployeeSkill
WHERE skill IN (SELECT skill FROM RequiredSkill)
GROUP BY emp_id
HAVING
COUNT(DISTINCT skill) = (
SELECT COUNT(*) FROM RequiredSkill
);
ちなみに、パフォーマンスを考慮するのであれば、IN を EXISTS や INNER JOIN に置き換えるとよいです。
IN を EXISTS で置き換える
SELECT emp_id
FROM EmployeeSkill ES
WHERE EXISTS (
SELECT 1
FROM RequiredSkill RS
WHERE RS.skill = ES.skill
)
GROUP BY emp_id
HAVING
COUNT(DISTINCT ES.skill) = (
SELECT COUNT(*) FROM RequiredSkill
);
メリット
- 結合キーでインデックスを使える可能性がある
- 全表検索の必要がない（1 行でも条件を満たす行が存在したらそこで検索を打ち切るため）
IN を INNER JOIN で置き換える
SELECT ES.emp_id
FROM
EmployeeSkill ES
INNER JOIN RequiredSkill RS
ON ES.skill = RS.skill
GROUP BY ES.emp_id
HAVING
COUNT(DISTINCT ES.skill) = (
SELECT COUNT(*) FROM RequiredSkill
);
メリット
- 結合キーでインデックスを使える可能性がある
- 中間ビューが作られない（サブクエリがなくなるため）
2.4.3 減法で表現する
SELECT DISTINCT emp_id
FROM EmployeeSkill ES
WHERE NOT EXISTS (
SELECT skill
FROM RequiredSkill
EXCEPT
SELECT skill
FROM EmployeeSkill ES2
WHERE ES2.emp_id = ES.emp_id
);
3. 結合と集合演算
ex.
各結合について、次のテーブル（再掲）に対するクエリを例示します。
A
| id | name |
|---|---|
| 1 | 太郎 |
| 2 | 花子 |
| 3 | 次郎 |
B
| id | name |
|---|---|
| 1 | 太郎 |
| 2 | 花子 |
| 4 | 三郎 |
3.1 交差結合（CROSS JOIN）
直積（再掲）
SELECT
A.name AS a_name,
B.name AS b_name
FROM
A CROSS JOIN B;
結果
| a_name | b_name |
|---|---|
| 太郎 | 太郎 |
| 太郎 | 花子 |
| 太郎 | 三郎 |
| 花子 | 太郎 |
| 花子 | 花子 |
| 花子 | 三郎 |
| 次郎 | 太郎 |
| 次郎 | 花子 |
| 次郎 | 三郎 |
3.2 内部結合（INNER JOIN）
論理積（INTERSECT）
SELECT
A.name AS a_name,
B.name AS b_name
FROM
A INNER JOIN B
ON A.id = B.id;
結果
| a_name | b_name |
|---|---|
| 太郎 | 太郎 |
| 花子 | 花子 |
3.3.1 完全外部結合（FULL OUTER JOIN）
論理和（UNION）
SELECT
A.name AS a_name,
B.name AS b_name
FROM
A FULL OUTER JOIN B
ON A.id = B.id;
結果
| a_name | b_name |
|---|---|
| 太郎 | 太郎 |
| 花子 | 花子 |
| 次郎 | |
| 三郎 |
排他的論理和
SELECT
COALESCE(A.name, B.name) AS name
FROM
A FULL OUTER JOIN B
ON A.id = B.id
WHERE
A.name IS NULL
OR B.name IS NULL;
結果
| name |
|---|
| 次郎 |
| 三郎 |
3.3.2 左外部結合（LEFT OUTER JOIN）
A - B
SELECT
A.name AS a_name
FROM
A LEFT OUTER JOIN B
ON A.id = B.id
WHERE
B.name IS NULL;
結果
| a_name |
|---|
| 次郎 |
3.3.3 右外部結合（RIGHT OUTER JOIN）
B - A
SELECT
B.name AS B_name
FROM
A RIGHT OUTER JOIN B
ON A.id = B.id
WHERE
A.name IS NULL;
結果
| b_name |
|---|
| 三郎 |
おわりに
「達人に学ぶ SQL 徹底指南書 第 2 版」で、著者は次のように述べています。
Theory is Practical.
関係データベースが数学的な理論に厳密であるがゆえに実用的なのはとても美しいと感じました。（読書感想文）
余談
添付したベン図は matplotlib-venn を使って描きました 🎨