リレーショナル代数とSQLの宣言的意味論

SQL の意味はどこで定義されるのか

SELECT name FROM users WHERE age > 30 と書くだけで、結合の順序やループの回し方を一切指定しなくても正しい結果が返ります。この「何が欲しいか（what）だけを書けば、どう取るか（how）は処理系が決める」という性質を宣言的（declarative）と呼びます。ではこの宣言的な文の意味は、どこで厳密に定義されているのでしょうか。答えはリレーショナル代数です。SQL の各構文は、最終的に代数の演算子の組み合わせへ翻訳され、その代数式の値が「クエリの結果」の定義になります。本稿では代数の演算を正確に押さえ、SQL がどう翻訳され、なぜ宣言的でいられるのかを理論から追います。

リレーショナル代数の基本演算

リレーショナル代数は、関係（リレーション、すなわちタプルの集合）を入力に取り、関係を出力する演算子の体系です。出力もまた関係なので、演算子を入れ子にして式を組み立てられる（閉包性）のが要点です。基本となるのは次の演算です。

選択 σ は行を絞り、射影 π は列を絞ります。直積 × は2つの関係の全ペアを作る演算で、結合 ⋈ は「直積してから選択する」ことの略記です。つまり R ⋈[条件] S は σ[条件](R × S) と等価で、これが内部結合の数学的な定義です。和・差・直積は集合論由来の演算で、和と差は両関係が同じ属性構成（union compatible）でなければ適用できません。

SELECT-FROM-WHERE はこう翻訳される

SQL の最も基本的な問い合わせブロックは、リレーショナル代数の3演算の合成へ機械的に翻訳できます。次の対応が翻訳の核です。

SELECT  列リスト     →  π（射影）
FROM    表のリスト   →  × / ⋈（直積・結合）
WHERE   条件        →  σ（選択）

例えば次の SQL を考えます。

SELECT u.name, o.amount
FROM users u, orders o
WHERE u.id = o.user_id
  AND o.amount > 1000;

この文の意味は、代数では次の1本の式として定義されます（属性名は簡略表記）。

π[name, amount] ( σ[u.id = o.user_id AND o.amount > 1000] ( users × orders ) )

つまり「users と orders の直積を作り、結合条件と絞り込み条件で選択し、必要な2列に射影する」という手続きが、この SQL の厳密な意味です。GROUP BY は集約演算子 γ（ガンマ）へ、HAVING は集約後の選択 σ へ、ORDER BY はソート演算子 τ へ翻訳されます。SQL の各句が代数の演算子に1対1で近く対応している点が、翻訳を機械化できる理由です。SQL の基礎構文との対応は SQL の基本 も参照してください。

等価変換：宣言的でいられる理由

ここで決定的に重要なのは、上の代数式が意味の定義であって、実行手順そのものではないことです。users × orders を素朴に作れば全組み合わせという巨大な中間結果が生まれますが、誰もそんな実行はしません。リレーショナル代数には**等価規則（代数法則）**があり、結果を変えずに式を別の形へ書き換えられます。

処理系はこれらの規則で式を変形し、論理的に等価な無数の式の中から実行コストが最小のものを選びます。σ を結合より下へ押し下げる述語プッシュダウンや、結合順序の組み替えはその代表です。ユーザーが書いた WHERE の順序や FROM の並びに縛られず、最適な形へ作り替えられる——これこそが SQL が宣言的でいられる仕組みです。どの等価形が最小コストかを統計から選ぶ過程は クエリオプティマイザの内部 で詳述しています。

除算：「すべてに対応する」を表す演算

基本演算ほど目立ちませんが、実務で問われやすいのが**除算（÷）です。除算は「Y のすべての値に対応する X」を求める演算で、「全教科を履修した学生」「すべての必須部品を在庫する倉庫」のような全称（すべての〜）**を表現します。

関係 R(X, Y) を関係 S(Y) で割った R ÷ S は、「S に含まれるすべての Y 値と組になって R に現れる X 値」の集合です。定義上は次のように差で表せます。

R ÷ S = π[X](R) − π[X]( ( π[X](R) × S ) − R )

直感的には「X の候補すべてに S の全 Y を掛けた理想形 π[X](R) × S から、実際に R にある組を引くと『欠けている組』が残る。欠けが1つでもある X を全体から除けば、すべてを満たす X だけが残る」という構成です。SQL に除算の専用構文はないため、二重の NOT EXISTS（「S の中に、R に存在しない組がない X」）で書くのが定石です。

-- すべての必須スキル(required_skills)を持つ社員を求める（除算）
SELECT e.id
FROM employees e
WHERE NOT EXISTS (                       -- 欠けているスキルが
  SELECT 1 FROM required_skills rs
  WHERE NOT EXISTS (                     -- その社員に存在しない、という
    SELECT 1 FROM emp_skills es
    WHERE es.emp_id = e.id
      AND es.skill_id = rs.skill_id
  )                                      -- 組み合わせが
);                                       -- 1つも無い社員

代数と計算：コッドの定理

リレーショナル代数は演算子を順に適用する手続き的な言語です。これと対をなすのが関係計算（relational calculus）で、こちらは「結果が満たすべき条件」を論理式で書く宣言的な言語です。関係計算には変数がタプル全体を走るタプル関係計算と、属性値を走るドメイン関係計算があります。

# タプル関係計算での例（「年齢が30超のユーザー名」）
{ t.name | t ∈ users ∧ t.age > 30 }

この記法は「どの行を、どの順で読むか」を一切含まず、結果集合の性質だけを述べています。SQL の SELECT ... WHERE ... は、見た目はこの関係計算の論理式に近い宣言的な書き方です。

ここで理論上の要となるのがコッドの定理（Codd's theorem）です。リレーショナル代数と（安全な）関係計算は表現力が等価であり、一方で書ける問い合わせは必ず他方でも書ける、という定理です。

コッドの定理は実装にとって本質的です。利用者は関係計算に近い宣言的な SQL を書き、処理系はそれを等価な代数式へ翻訳し、等価変換で最適化してから実行できる。宣言的に書けること（計算側）と、手続き的に最適化・実行できること（代数側）が、表現力を一切損なわずに両立する——この等価性こそが、リレーショナルモデルの理論的な土台です。

まとめ

• リレーショナル代数は選択σ・射影π・結合⋈・和∪・差−・除算÷などの演算子で関係から関係を作る手続き的言語で、SQL の意味はこの代数式への翻訳として定義される。
• SELECT→π、FROM→×/⋈、WHERE→σ と機械的に翻訳でき、処理系は等価規則（プッシュダウン・交換律・結合律）で式を変形して最小コストの実行形を選ぶ。これが SQL の宣言性の正体。
• 除算は「すべてに対応する」全称を表す演算で、SQL では二重の NOT EXISTS で書く。
• リレーショナル代数（手続き的）と関係計算（宣言的）は表現力が等価であり（コッドの定理）、この等価性が、宣言的に書けることと手続き的に最適化できることを両立させている。