リレーショナルデータベース入門/リレーショナル代数

初めに

この記事は「リレーショナルデータベース入門 第３版」の第２章の一部をまとめたものです。
リレーションの例などは徹底攻略 データベーススペシャリスト教科書 令和4年度で用いられている具体例を参考にしています。

リレーションやドメインなどといった言葉の定義は別で書いた記事を参照ください。

リレーショナル代数とは

リレーショナル代数というリレーショナル操作言語はコッドにより、リレーショナルデータモデルの提案時にデータ操作言語の一つとして提案され、合計８つの演算が導入された。
・４つの集合演算（和、差、共通、直積）
・４つのリレーショナル台数に特有の演算（射影、選択、結合、商）
集合演算を含むのは、リレーションがそもそもドメインの直積の部分「集合」として定義したためである。

４つの集合演算（和、差、共通、直積）

和集合、差集合、共通集合の操作を行うためには次の和両立という条件を満たす必要がある

定義（和両立）

リレーションR(A_{1}...A_{n})とS(B_{1}...B_{m})が和両立であるとは次を満たすこと\\
1. \quad n=m\\
2.\forall i\in \{1...n\}\quad dom(A_{i})=dom({B_{i}})

2.の意味は、属性名は違えどリレーションを構成するドメインが同じであるということである。大雑把に言えば、同じ類のカラム、カラム数を持っているリレーション同士であることが条件ということである。

４つの集合演算（和、差、共通、直積）の定義をする。
これらは通常の集合論における演算と同一のため、詳細は割愛する。

定義（和集合）

RとSを和両立なリレーションとする。\\このときRとSの和は次のように定義されるリレーションである\\
R\cup S　＝\{t|t\in R \lor　t\in S\}

定義（差集合）

RとSを和両立なリレーションとする。\\このときRとSの差は次のように定義されるリレーションである\\
Rー S　＝\{t|t\in R \land　t\notin S\}

定義（共通集合）

RとSを和両立なリレーションとする。\\このときRとSの共通は次のように定義されるリレーションである\\
R\cap　S　＝\{t|t\in R \land　t\in S\}

定義（直積集合）

RとSをn項、m項リレーションとする。\\このときRとSの直積は次のように定義されるn+m項リレーションである\\
R×S　＝\{(r,s)|r\in R \land　s\in S\}

４つのリレーショナル台数に特有の演算（射影、選択、結合、商）

次に４つのリレーショナル台数に特有の演算（射影、選択、結合、商）の定義をする

射影演算

射影とは端的に言うと、リレーションの各行から指定したカラムだけを取り出す操作である(SQLで言うと指定したカラムをselectする感じ)

定義（射影）

R(A_{1},...,A_{n})をリレーションとする。\\
Rの全属性集合の部分集合をX=\{A_{i_{1}},...,A_{i_{k}}\}とする。(１\leqq　i_{1}<・・・<i_{k}\leqq　n)
\\このときRのX上の射影R[X]は次のように定義されるリレーションである\\
R[X]=\{u|u\in dom(A_{i_{1}})×・・・×dom(A_{i_{k}})　\land　\\
\exists t\in R\quad s.t\quad (t[A_{i_{1}}]=u[A_{i_{1}}]\land　・・・\land　t[A_{i_{k}}]=u[A_{i_{k}}])\quad\}

具体例として以下のidと名前と年齢の属性を持つ名簿リレーションR(A1,A2,A3)を使う
つまりR={(1,Aさん,30),(2,Bさん,50),(3,Cさん,70)}、A1 = id,A2=名前,A3=年齢とする

リレーションR(A1,A2,A3)

id	名前	年齢
1	Aさん	30
2	Bさん	50
3	Cさん	70

全属性集合{id,名前,年齢}の部分集合X＝{id,名前}とする。

先に結論を簡単にいうと、射影操作はこのXの属性のカラムだけ取り出したタプルの集合となる。
つまりR[X]={(1,Aさん),(2,Bさん),(3,Cさん)}となる。

射影リレーションR(X)

id	名前
1	Aさん
2	Bさん
3	Cさん

実際、射影R[X]の定義を満たしているか確認する。
R[X]の元 u=(1,Aさん)を取ると、これはdom(A1)×dom(A2)の元である。
また、u[A1]=t[A1]（=1）, u[A2]=t[A2]（=Aさん)を満たすような、Rのタプル t=(1,Aさん,30)を取ることができる。他のR[X]の元を取っても同様である。

選択演算

選択演算は直感的に言うと、リレーションRから指定した条件を満たすタプルだけを取り出す操作のことである(sqlで言うところのwhere句)
まず２つの属性がθ-比較可能と言う概念を述べる。ここでθは２項の述語（戻り値が真理値である２変数の命題関数、例えばx>yは２項の述語でありx=5,y=2を入れれば true を返す）を表す。

定義（θ-比較可能）

R(A_{1},...,A_{n})をリレーションとする。\\
このとき属性A_{i}とA_{j}がθ-比較可能とは次の条件を満たしていることである\\
1.\quad dom(A_{i})=dom(A_{j})\\
2.\quad Rの任意のタプルtに対して、t[A_{i}]θt[A_{j}]の真偽が常に定まる\\

ここで、t[Ai]θt[Aj]とはtのAiの値とtのAjの値をθの述語に代入した結果である
この定義はつまり、「比較対象の属性のドメインが同じ類であること(例えば、数字なら数字同士でしか比較できない)とそれらの比較結果が必ず真偽で決まること（unknownとかはダメ。unknownへの拡張は後に議論する）をθ-比較可能という」ようなことを言っている。
これを用いてθ-比較演算の定義をする。

定義（θ-比較演算）

R(A_{1},...,A_{n})をリレーションとする。\\
属性A_{i}とA_{j}がθ-比較可能とする\\
このとき、Rの属性A_{i}とA_{j}上のθ-比較R[A_{i}θA_{j}]は次で定義されるリレーションである\\
R[A_{i}θA_{j}] = \{t|t\in R\land　（t[A_{i}]θt[A_{j}]=真)\}

この定義はつまり、「θ-比較可能とは属性同士の比較がtrueになる結果を表示する演算である」と言うこと。
なお、この定義においては二つの属性に対しての比較であり、定値との比較演算は含まれていない（商品価格が1000以上みたいな比較はこの定義に基づいて表現できない）。
しかし定値リレーションと言うリレーションを用意し、射影演算・直積演算・θ-比較演算を組み合わせれば、定値の場合の比較演算定義も可能である(今は可能と言うことにとどめる)

結合演算

結合演算とは２つのリレーションに対し、指定した属性を指定した条件で比較し、それがtrueになったタプル同士を組み合わせ(結合)した結果を返す操作である。（SQLで言うところのjoinである）

定義（θ-結合演算）

R(A_{1},...,A_{n}),S(B_{1},...,B_{m})をリレーションとする。\\
属性A_{i}とB_{j}がθ-比較可能とする\\
このとき、RとSのA_{i},B_{j}のθ-結合R[A_{i}θB_{j}]Sは次で定義されるリレーションである\\
R[A_{i}θB_{j}]S = \{(t,u)|t\in R\land　u\in S\land （t[A_{i}]θu[B_{j}]=真)\}

この定義を以下の具体例を用いてみていく。

具体例：リレーションR「社員」

A1,A2,A3,A4はそれぞれ社員番号、社員名、 給与 、所属とする

社員番号	社員名	給与	所属
1	A	20	K11
2	B	30	E22
3	C	40	E22
4	D	50	K11

具体例：リレーションS「部門」

B1,B2,B3をそれぞれ部門番号、部門名 、部門長とする

部門番号	部門名	部門長
K11	開発部	1
E22	営業部	4

θを「x=y」といった＝での比較述語とする。
この時A4とB1がθ-比較可能であり、θ結合の結果は以下になる。

具体例：リレーションR[A4θB1]S「部門」

社員.社員番号	社員.社員名	社員.給与	社員.所属	部門.部門番号	部門.部門名	部門.部門長
1	A	20	K11	K11	開発部	1
2	B	30	E22	E22	営業部	4
3	C	40	E22	E22	営業部	4
4	D	50	K11	K11	開発部	1

実際、θ-結合の定義を満たしている。なぜなら、このリレーションの左４列のカラムに関してはRのタプルであり、かつ右４列はSのタプルであるので、このリレーションの要素はRとSのタプルの組み合わせになっている。また、A4とB1がθ-比較演算結果がtrueのもののみ表している。（この具体例はsqlで言うところのinner joinのようなものである）

さて、これを用いて、自然結合演算を導入する。

定義（自然結合演算）

R(A_{1},...,A_{n}),S(B_{1},...,B_{m})をリレーションとする.\\
これらの結合属性（属性の共通部分）を{C_{1},...,C_{k}}とする.\\
また,各C_{i}についてRとSでそのドメインが等しいとする.\\
この時,RとSの自然結合R*Sは次で定義されるリレーションである.\\
R*S = \{(t,u)|t\in R\land　u\in dom(D_{1})×・・・×dom(D_{m-k})\land\exists u\in S\quad\\
 s.t\quad(t[C_{i}]=u[C_{i}](i=1,..,k))\land(v[D_{j}]=u[D_{j}](j=1,..,m-k))\}\\
 ここで\{D_{1},...,D_{m-k}\}=\{B_{1},...,B_{m}\}-\{C_{1},...,.C_{k}\}とする.

この定義を以下の具体例を用いてみていく。

具体例：リレーションR「社員」

A1,A2,A3,A4はそれぞれ社員番号、社員名、 給与 、所属とする

社員番号	社員名	給与	部門番号
1	A	20	K11
2	B	30	E22
3	C	40	E22
4	D	50	K11

具体例：リレーションS「部門」

B1,B2,B3をそれぞれ部門番号、部門名 、部門長とする

部門番号	部門名	部門長
K11	開発部	1
E22	営業部	4

これらの共通属性はC1=部門番号である。
またSと共通属性の差集合はD1=部門名,D2=部門長である。
これらの自然結合の結果は 以下のようになる（これは先ほどのθを「x=y」といった＝での比較述語とした時のθ結合の具体例とほぼ同じ結果である。）

具体例：リレーションR*S

社員番号	社員名	給与	部門番号	部門名	部門長
1	A	20	K11	開発部	1
2	B	30	E22	営業部	4
3	C	40	E22	営業部	4
4	D	50	K11	開発部	1

これは確かに自然結合の定義を満たしている。
例えばリレーションR*Sの一番上のタプルをとり、t=(1,A,20,K11),v=(開発部,1)とすれば,
tはRのタプルであり,vはD1とD2のドメインの元である。
また、Sのタプルとしてu=(K11,開発部,1)を取れば、uのC1値とtのC1値は一致するし、uのD1値とD2値はそれぞれvのD1値とD2値と一致する。

大雑把にいえば、 Rのタプルに対して,共通属性の値（例でいうと部門番号）が同じであるようなSのタプルとの組み合わせ（から共通部分の重複を除いたもの）が自然結合のタプルとなる。

これらを用いて正規化の概念を別記事で述べていく。

参考

・リレーショナルデータベース入門 第３版
・徹底攻略 データベーススペシャリスト教科書 令和4年度