SQLと関係代数基本演算編

佐久間正樹

リレーショナルデータベースの根本理論には、関係代数（relational algebra）があり、SQLもその上に構築されています。とはいえ、SQLではINNER JOINやOUTER JOINのような複雑な演算が一発で書けてしまい、サブクエリやWindow関数などのような一見数学から縁遠いように見える便利な機能もあるため、その数学的な意味や構成を意識することは多くありません。本稿では、SQL文の背後にある関係代数的な操作を明らかにし、複雑な結合が基本演算で構成可能であることを、数式とSQL文を対比させながら検証していきます。

紛らわしいですが、「関係代数」と呼ばれる数学的な体系は、二項関係の合成と逆を抽象化した剰余付きブール代数であるrelation algebraと、表（テーブル、リレーション、関係）の演算を扱うrelational algebraの2つがあり、両者は異なります。本稿で扱うのは「relational algebra」の方です。

1 関係代数の基本演算

関係代数ではテーブルをタプル（行）の集合と捉えて、テーブル同士の演算を考えます。ここで言う「集合」は数学的な意味での集合です。従って、行の順番などのより詳細な構造は無視されます。「関係」とはテーブルのことです。

関係代数は以下の基本演算により構成されます。

選択（selection）または制限（restriction）：\(\sigma_{\theta}(R)\)

関係\(R\)のうち、条件\(\theta\)を満たす行のみを抽出します。
射影（projection）：\(\pi_{A_1,\ldots,A_k}(R)\)

関係\(R\)のうち、属性\(A_1,\ldots,A_k\)のみを抽出します。
直積（Cartesian product）：\(R \times S\)

関係\(R\)と\(S\)の行の全ての組み合わせからなる関係を作ります。SQLではCROSS JOINに相当しますが、実用上は明示的に使われる機会は少ないと思います。しかし、関係代数では非常に重要な二項演算です。
和（union）：\(R \cup S\)

行に関して和集合をとります。
差（difference）：\(R – S\)

行に関して差集合をとります。通常の数学では分野にもよりますが、\(R\setminus S\)という表記の方が一般的かもしれません。
再命名（renaming）：\(\rho_{S(B_1, \dots, B_n)}(R)\)

属性名を変更する演算です。一見すると演算として扱うのは不自然に思えるかもしれませんが、エドガー・F・コッドによる初期の関係代数の体系には含まれていました。

これらの基本演算だけで様々な関係演算が構築できることが関係代数の強力な性質の一つです。例えば、\(R,S\)が型適合である、すなわち属性が共通であるという前提の下で、共通部分（交わり）をとる操作は、ドモルガンの法則から確認できるように \[R\cap S=R-(R-S)\] と「差」だけで表現できます。

2 INNER JOINの関係代数的表現

SQLでは欠かせないINNER JOIN（内部結合）は一見数学らしくない演算ですが、関係代数の基本演算のみで表現できます。例えば、次のようなSQL文を考えます：

SELECT *
FROM Employee e
JOIN Department d ON e.dept_id = d.dept_id;

これは関係代数で次のように表されます：

\[\begin{equation}
\pi_{*}\left( \sigma_{e.\text{dept\_id} = d.\text{dept\_id}}(E\times D) \right)
\end{equation}\]

つまり、次のような操作を順番に繰り返した結果です。

直積：\(E \times D\)
選択：\(e.\text{dept\_id} = d.\text{dept\_id}\)
射影：必要な属性（列）のみ抽出

また、自然結合も内部結合の一種と見做せ、2つのリレーションスキーマ \[R(A_1,\ldots,A_n,C_1,\ldots, C_k),S(B_1,\ldots,B_m,C_1,\ldots, C_k)\] の自然結合は \[R \bowtie S=\pi_{A_1,\ldots,A_n,B_1,\ldots,B_m,C_1,\ldots,C_k}(\sigma_{(R.C_1=S.C_1,\ldots,R.C_k=S.C_k)}(R\times S))\] となります。ここで、\(R\), \(S\)に共通する属性を\(C_1,\ldots,C_k\)とおきました。異なるリレーションスキーマにおける属性の同一性は、名前と型が同じなどの基準により事前に了解されているものとします。さらに、自然結合を\(R\)の属性全体\(\Omega_R\)に射影したもの \[R\ltimes S=\pi_{\Omega_R}(R \bowtie S)\] を半結合（準結合、semijoin）と言います。\(R\ltimes S\)は、\(R,S\)に共通する全ての属性の値が等しいという意味で対応する\(S\)の行が存在するような\(R\)の行全体からなる集合で、\(\Omega_R\cap\Omega_S=\emptyset\)のときは\(R\bowtie S=R\times S\), \(R\ltimes S=R\)になります。

3 \(\theta\)結合の関係代数的表現

\(\theta\)結合とは、2つのリレーションに対して任意の述語\(\theta\)を用いて行を結合する操作です。「＝」以外にも指定できるのでINNER JOINの一般化に当たります。

関係代数において、\(\theta\)結合\(R \bowtie_{\theta} S\)は以下のように基本演算により表現できます： \[R \bowtie_{\theta} S = \sigma_{\theta}(R \times S)\]

例えば、

SELECT * FROM Employee e, Department d
WHERE e.dept_id = d.id AND d.location = 'Tokyo';

は関係代数では以下に対応します： \[\sigma_{(E.\text{dept\_id} = D.\text{id}) \land (D.\text{location} = \text{'Tokyo'})}(E \times D)\] これは\(\theta\)結合の典型的な形であり、直積と選択によって表現可能であることが分かります。

4 LEFT OUTER JOINの関係代数的構成

次のSQL文を考えます：

SELECT *
FROM Employee e
LEFT JOIN Department d ON e.dept_id = d.dept_id;

LEFT OUTER JOINはINNER JOINに相当する行に加えて、左表に存在するが右表にはマッチしない行も保持します。この関係代数での構成表現は次のようになります：

\[\begin{equation}
(E \Join_\theta D) \cup
\left\{\left( E – \pi_E(E \Join_\theta D) \right) \times \text{Nullify}(D)\right\}
\end{equation}\]

ここで、それぞれの操作を分解すると以下のようになります。

\(E \Join_\theta D\) はINNER JOIN
\(\pi_E(E \Join_\theta D)\) はJOINにマッチした左表の行
\(E – \pi_E(E \Join_\theta D)\) はマッチしなかった行
\(\text{Nullify}(D)\) は\(D\)のスキーマ構造（属性の名前や順序）を持ちつつ\(D\)の属性を全てNULLで埋めて得られる関係

他にも完全外部結合なども含め、様々な種類の結合が \[\text{直積} + \text{選択} + \text{射影} + \text{NULL補完}\] で構成できるという理解は、SQLと数学の橋渡しになります。ただし、\(\text{Nullify}(\cdot)\)はコッドによる狭義の関係代数における単項演算としては定義されておらず、認めない拡張関係代数の流派もあります。NULLの数学的な扱いは難しいですが、ドメイン（属性の値となり得るものの集合）の要素とは区別された単なる記号として扱われます。

5 多段JOINの例と変形

以下のSQLを関係代数で表現します：

SELECT *
FROM A
JOIN B ON A.id = B.a_id
JOIN C ON B.id = C.b_id;

これは前述の基本演算を用いて次のように表されます：

\[\begin{equation}
\pi_{*}\left( \sigma_{(A.id = B.a\_id) \land (B.id = C.b\_id)} \left( (A \times B) \times C \right) \right)
\end{equation}\]

しかし、これを愚直に実行すると、行数\(|A|\times |B|\times |C|\)のテーブルを作ってから選択・射影するという方法になるため、\(A,B,C\)が巨大なテーブルの場合はパフォーマンスが悪いことが見て取れます。実行計画としては、 \[(A \Join_{\theta_1} B) \Join_{\theta_2} C\] のように段階的にJOINを評価する形で実行する方が遥かに効率的で、標準的なRDBMSではこちらが実行されます。\(\sigma\)の直積\(\times\)に関する条件付き分配法則を用いると上記の基本演算による表現と一致することが確認できます。効率化するための演算法則についてはクエリ最適化の節で具体的に見ます。

6 商の関係代数的表現

関係代数における商（division）演算は、直積、差集合、射影といった基本演算を組み合わせることで表現できます。商演算は、ある関係において「全ての条件を満たすもの」を求める際に用いられます。

例えば、\(R(A, B)\)と\(S(B)\)が与えられたとき、\(R \div S\)は、\(S\)に含まれる全ての属性値\(b\)に対して\((a, b) \in R\)となる\(a\)の集合を求めます。

Definition 1. \[R \div S = \{ a \in \pi_A(R) \mid \forall b \in S,\ (a, b) \in R \}\]

この演算は、関係代数の基本演算を使って以下のように構成的に表すことができます：

\[R \div S = \pi_A(R) – \pi_A \left( (\pi_A(R) \times S) – R \right)\]

\(\pi_A(R)\)は\(R\)に含まれる全ての\(a\)値の集合を意味します。
\(\pi_A(R) \times S\)は、その各\(a\)に対して\(S\)の全ての\(b\)を組み合わせた直積です（全ての\((a, b)\)の可能なペア）。
そこから\(R\)を引くことで、「\(R\)に存在しない\((a, b)\)」を抽出します。
この結果に\(\pi_A\)を適用すると、「条件を満たさない\(a\)」が抽出されます。
最後に\(\pi_A(R)\)からこれらを引くことで、条件を全て満たす\(a\)のみが残ります。

これが何故「商」と言われているかと言うと、属性集合\(\Omega_Q\)をもつ関係\(Q\)と属性集合\(\Omega_S\)をもつ関係\(S\)が\(\Omega_Q\cap \Omega_S=\emptyset\)を満たすとき、 \[T=Q\times S\Longrightarrow T\div S=Q\] が成り立つ、すなわち、\((\div S):T\mapsto T\div S\)が直積演算\((\times S):Q\mapsto Q\times S\)の条件付きの左逆写像になっているからです。

現状、標準的なRDBMS（MySQL, PostgreSQLなど）においては商を直接表現する構文は存在しませんが、ネストされたサブクエリを用いて等価な処理が可能です。

-- スキーマ
R(a, b)
S(b)

-- クエリ
SELECT DISTINCT R1.a
FROM R R1
WHERE NOT EXISTS (
  SELECT *
  FROM S S1
  WHERE NOT EXISTS (
    SELECT *
    FROM R R2
    WHERE R2.a = R1.a AND R2.b = S1.b
  )
)

このクエリは、「\((a, b)\)が\(R\)に存在しないような\(b\in S\)が存在しない」すなわち「\(S\)の全ての\(b\)に対して、\((a, b)\)が\(R\)に存在する」ような\(R\)の\(a\)を全て取得することを意味します。これは集合論的に以下が成立することから従います。 \[\begin{eqnarray*}
R \div S &= \{ a \in \pi_A(R) \mid \forall b \in S,\ (a, b) \in R \} \\
&= \{ a \in \pi_A(R) \mid \neg(\exists b \in S,\ (a, b) \not\in R)\}.
\end{eqnarray*}\] 更に変形していくと基本演算による構成的表示が得られます。 \[\begin{eqnarray*}
R \div S &= \{ a \in \pi_A(R) \mid \neg(\exists b \in S,\ (a, b) \not\in R)\}\\
&= \pi_A(R)-\{ a \in \pi_A(R) \mid \exists b \in S,\ (a, b) \not\in R\}\\
&= \pi_A(R)-\{ a \in \pi_A(R) \mid \exists b \in S,\ (a, b) \in (\pi_A(R)\times S) – R\}\\
&= \pi_A(R)-\pi_{A}(\{ (a,b) \in \pi_A(R)\times S \mid (a, b) \in (\pi_A(R)\times S)- R\})\\
&= \pi_A(R)-\pi_{A}((\pi_A(R)\times S)- R).
\end{eqnarray*}\]

応用として、商演算は「すべての資格を持つ従業員」や「すべての製品を扱う業者」など、全称的な包含条件を満たす対象の列挙に利用できます。

7 サブクエリ・集計関数・Window関数の関係代数的解釈

SQLにおける更に高階的なクエリ（サブクエリ、集計関数、Window関数、WITH RECURSIVE句など）も、関係代数で解釈できます。

7.1 サブクエリ

内部に別のSELECT文を含むSELECT文は、関係代数においては入れ子になった選択（制限）・射影・集合演算に対応します。サブクエリは、テーブルを葉、関係代数の演算子をノードとしてクエリを木構造（構文木）で表現した際に、特定の部分木に対応します。

SELECT name FROM Employee
WHERE dept_id IN (
    SELECT dept_id FROM Department
    WHERE location = 'Tokyo'
);

これは関係代数では以下のように書けます：

\[\pi_{\text{name}} \left( \sigma_{\text{dept\_id} \in \pi_{\text{dept\_id}}(\sigma_{\text{location = 'Tokyo'}}(\text{D}))}(\text{E}) \right)\]

一般に、共通の属性\(A\)をもつ関係\(R,S\)に対し、\(R\)の属性全体を\(\Omega_R\)とおいたときに \[\sigma_{A\in \pi_{A}(S)}(R)=\sigma_{\Omega_R}(R\Join_{R.A=S.A} S)\] が成り立つことと、\(\sigma\)と\(\Join\)の可換性から、この関係代数式は \[\begin{eqnarray*}
&&\pi_{\text{name}} \left( \sigma_{\text{dept\_id} \in \pi_{\text{dept\_id}}(\sigma_{\text{location = 'Tokyo'}}(\text{D}))}(\text{E}) \right)\\
&= \pi_{\text{name}} \left( \sigma_{\Omega_{\text{E}}}(\text{E}\Join_{\text{E}.\text{dept\_id}=\sigma_{\text{location = 'Tokyo'}}(\text{D}).\text{dept\_id}} \sigma_{\text{location = 'Tokyo'}}(\text{D})) \right)\\
&= \pi_{\text{name}} \left( \sigma_{\Omega_{\text{E}}}\circ\sigma_{\text{location = 'Tokyo'}}(\text{E}\Join_{\text{E}.\text{dept\_id}=\text{D}.\text{dept\_id}} \text{D}) \right)\\
&= \pi_{\text{name}} \left(\sigma_{\text{location = 'Tokyo'}}(\text{E}\Join_{\text{E}.\text{dept\_id}=\text{D}.\text{dept\_id}} \text{D}) \right)
\end{eqnarray*}\] のように変形できます。よって、上記のクエリは次のサブクエリを含まないクエリと等価です。

SELECT e.name
FROM Employee e
JOIN Department d ON e.dept_id = d.dept_id
WHERE d.location = 'Tokyo';

ちなみに、もし\(\Omega_R\cap \Omega_S=\{A\}\)であれば、\(\sigma_{A\in \pi_{A}(S)}(R)=R\ltimes S\)になります。\(R,S\)の共通の属性が\(A\)のみであることは\(\sigma_{A\in \pi_{A}(S)}(R)\)が半結合\(R\ltimes S\)に一致するための必要十分条件です。この変形公式はクエリ最適化にも有用です。

7.2 集計関数

コッドによる標準的な関係代数には集約演算子が含まれていませんが、後世に拡張された関係代数のいくつかの流派では「要約(summarize)」と呼ばれる演算（集計演算子\(\gamma\)）を導入しています。\(\gamma\)演算子を用いて集計関数やWindow関数を表現できます。

SELECT dept_id, COUNT(*) FROM Employee
GROUP BY dept_id;

\[\gamma_{\text{dept\_id},\ \text{count(*)}}(\text{Employee})\]

7.3 WITH RECURSIVE句

WITH RECURSIVE句の結果は関係代数と固定点演算子\(\mu\)を用いて表現できます。例えば、有向グラフの辺を辿ることで到達できるノード対を取得するクエリ

WITH RECURSIVE Reachable(x, y) AS (
  SELECT from_node, to_node
  FROM Edge
  UNION
  SELECT r.x, e.to_node
  FROM Reachable r
  JOIN Edge e ON r.y = e.from_node
)
SELECT * FROM Reachable;

を数学的に表現すると次のようになります。 \[\begin{equation*}
\text{Reachable} = \mu_R \left(\left(
\text{Edge} \cup
\pi_{x,\ e.\text{to\_node}} \left(
\rho_{x \leftarrow r.x,\ y \leftarrow r.y} (R \Join_{r.y = e.\text{from\_node}} \text{Edge})
\right)
\right)
\right).
\end{equation*}\] 以下、リネームは本質的ではないので省略します。この\(\mu\)はmodal \(\mu\)-calculusにおける最小不動点を得る演算子と本質的に同じものです。現実的には有限集合なのでこの場合の不動点の存在は自明ですが、これは属性from_nodeとto_nodeの共通のドメイン（グラフの頂点となり得るものの集合）\(V\)に対し、\(V\times V\)上の\(\subseteq\)-単調増加写像 \[R\mapsto F(R)\coloneqq \text{Edge} \cup
\pi_{x,\ e.\text{to\_node}} \left(
R\Join_{y = e.\text{from\_node}} \text{Edge}
\right)\] にKnaster–Tarskiの不動点定理またはKleeneの不動点定理を適用した結果になり、実際には有限回反復適用で停止して収束しますが、Knaster–Tarskiの不動点定理より \[\text{Reachable} = \lim_{n\to \infty}F^n (\emptyset)\] と表すことができます。

SQLと関係代数 基本演算編