第3章: リレーショナル代数 — SQLを支える数学的骨格

なぜ代数なのか — SQLが「書き換え可能」な理由

第1章で「SQLは宣言的言語で、HOWはオプティマイザが決める」と述べました。 しかしこれは何でも自由に書き換えていいという意味ではありません。 同じ結果を保証する書き換え則が数学的に証明されているからこそ、オプティマイザは安心して実行計画を選べます。 その数学的基盤がリレーショナル代数（Relational Algebra）です。

Coddが1970年論文で提示した関係代数は8つの演算子からなる代数系で、 すべての演算子が「関係を入力として受け取り、関係を返す」という共通シグネチャを持ちます。 この性質こそが、SQLの柔軟さ・合成可能性・最適化可能性を同時に実現する鍵です。

8つの演算子 — 基本5 + 派生3

リレーショナル代数の演算子は歴史的に基本演算子5つと派生演算子3つに分けられます。 基本演算子だけで表現力は十分（チューリング完全ではないが関係完備）ですが、派生演算子は実用上よく使う組み合わせの糖衣構文です。

σと π — WHERE と SELECT の本質

最も基本的な2つの演算子、選択（σ）と射影（π）から始めましょう。

σ条件(関係)  — 選択: 条件を満たす「行」を抜き出す
π属性リスト(関係)  — 射影: 指定した「列」だけ残す

例: 従業員テーブル employees(id, name, age, dept) に対して

σage >= 30(employees)
  → ageが30以上の従業員の「すべての列」

πname, dept(employees)
  → すべての従業員の「nameとdeptだけ」

πname, dept(σage >= 30(employees))
  → 30歳以上の従業員の「nameとdeptだけ」

これをSQLに翻訳すると、美しい対応関係が見えてきます。

-- π name, dept (σ age >= 30 (employees))
SELECT name, dept          -- ← π (射影)
FROM employees             -- ← 入力関係
WHERE age >= 30;           -- ← σ (選択)

-- 論理実行順序では WHERE → SELECT の順に評価される
-- つまり SQL は関数合成 π(σ(R)) の「外側から書く」記法

SQLが「SELECT 〜 FROM 〜 WHERE 〜」の順に書くのは一見不思議ですが、 関係代数で内側から外側に向かって演算が適用されるのに対し、 人間が「何を取りたいか」を先に表明する英語的な語順に合わせた設計です。 論理実行順序は第4章で詳しく扱います。

⋈ — 結合は σ と × の合成

結合（Join）は派生演算子で、定義は以下の通りです。

R ⋈θ S ≡ σθ(R × S)

意味: 「R と S のデカルト積を作ってから、条件θで選択する」

具体例:
employees(id, name, dept_id) × departments(id, dept_name)
 → 全組み合わせ(m×n行)
 ↓ σ employees.dept_id = departments.id
 → dept_id = id の組だけ残る(= INNER JOIN)

∪ / ∩ / − — 集合演算子

和・積・差は2つの関係の属性構造(スキーマ)が一致しているときのみ適用できます。 この制約は「型(スキーマ)の互換性」と呼ばれ、コンパイル時チェックの基礎になります。

-- ∪ (UNION): 2024年と2025年の顧客を一覧化
SELECT id, name FROM customers_2024
UNION
SELECT id, name FROM customers_2025;

-- ∩ (INTERSECT): 2年連続で利用した顧客
SELECT id, name FROM customers_2024
INTERSECT
SELECT id, name FROM customers_2025;

-- − (EXCEPT / MINUS): 2024年のみ利用した顧客(=離脱)
SELECT id, name FROM customers_2024
EXCEPT
SELECT id, name FROM customers_2025;
-- Oracle/DB2 は MINUS、PostgreSQL/SQL Server/MySQL 8+ は EXCEPT

これらの演算子はデフォルトで重複を除去します（集合なので）。 重複を保持したい場合はUNION ALLを使いますが、これは厳密にはマルチセット（bag）の演算で、 純粋な関係代数にはありません。実用上の効率のためにSQLが拡張している部分です。

÷ — 「すべての〜」を表す商演算

除算（Division）は8演算子の中で最も理解が難しいですが、 「すべての〜を満たす」というタイプのクエリに対応します。

例: enrollments(student_id, course_id) と required(course_id) に対し

enrollments ÷ required
 → 「required に含まれるすべてのコースを履修している学生」

SQLでは÷を直接表現する構文がないため、NOT EXISTSの二重否定で書きます。

-- 「必修科目をすべて履修している学生」
SELECT DISTINCT e.student_id
FROM enrollments e
WHERE NOT EXISTS (
  SELECT 1 FROM required r
  WHERE NOT EXISTS (
    SELECT 1 FROM enrollments e2
    WHERE e2.student_id = e.student_id
      AND e2.course_id = r.course_id
  )
);
-- 読み方: 「必修のうち、この学生が履修していないものが無い」 = 全部履修

閉包性と合成可能性 — SQLが柔軟な本当の理由

関係代数の最大の特徴は閉包性（Closure Property）です。 すべての演算子が「関係を入力し、関係を返す」ため、演算結果をそのまま次の演算の入力にできます。

flowchart LR
    A[関係 R] --> S[σ選択]
    S --> P[π射影]
    P --> J[⋈結合]
    J --> U[∪和]
    U --> OUT[関係 R']
    style OUT fill:#3b82f6,color:#fff
    style A fill:#3b82f6,color:#fff

この性質がSQLにもたらした実用的な帰結が「FROM句の中にSELECTを書ける」ことです。

-- FROM句にサブクエリ = 関係を返す式ならどこでも置ける
SELECT dept, AVG(salary) AS avg_salary
FROM (
  SELECT dept, salary
  FROM employees
  WHERE hire_date >= '2020-01-01'
) AS recent_employees
GROUP BY dept;

-- これが閉包性の直接的な恩恵。
-- サブクエリも「関係」なので、FROM句(関係を期待する位置)に置ける。

等価変換則 — オプティマイザの書き換えの根拠

関係代数には書き換えても結果が同じと数学的に証明された等価変換則があります。 これがオプティマイザの論理的書き換え(rewrite rules)の根拠です。

第3章のまとめ

• リレーショナル代数はσ/π/×/∪/−の基本5演算子と⋈/∩/÷の派生3演算子からなる代数系である
• すべての演算子が「関係→関係」を返す閉包性を持ち、これがSQLの合成可能性（サブクエリをどこにでも書ける）の源泉
• SQLの各構文は関係代数に対応する: WHERE=σ、SELECT列リスト=π、INNER JOIN=⋈、UNION=∪、EXCEPT=−
• 等価変換則（選択の可換性・押し下げ、結合の可換性・結合法則など）が数学的に保証されているからこそ、オプティマイザは論理的書き換え(rewrite)で最適な実行計画を選べる
• SQLは関係代数と等価な関係完備だが、再帰CTE・集約関数・ウィンドウ関数は関係代数を超えた拡張である

次章では、関係代数の抽象を現実のSQL構文に落とし込み、 FROM→WHERE→GROUP BY→HAVING→SELECT→ORDER BYの論理実行順序、JOINの6種類、 NULLの3値論理という「初学者が詰まるトップポイント」を徹底的に整理します。