関係代数 (関係モデル)

関係代数（かんけいだいすう、リレーショナル代数、英: relational algebra）は、関係データベースの関係モデル （リレーショナルモデル）において、集合論と一階述語論理に基づいて、関係 （リレーション、表、テーブル）として表現されたデータを扱う、コンピュータ科学における代数的な演算の体系である。
関係として表現されたデータに対して行う演算体系としては、関係論理（関係計算）とこの項目で説明する関係代数の2種類が知られている。
関係代数と関係論理は、主にエドガー・F・コッドによって考案され、その後コッドを含めた関係データベース（関係モデル）の研究者たちが発展させてきた。
現在では、関係代数の演算子としては、和、差、交わり (交差) 、直積、制限 (選択) 、射影、結合、商の8種類が言及されることが多い。
ただし属性名変更や拡張、要約などこの他の演算子も考案されている。
関係代数を実装したデータベース言語（問い合わせ言語）としては、SQL や Tutorial D などが挙げられる。
ただし SQL については、関係代数を完全な形で実装していないとして批判する意見がある。
数学的に純粋な関係代数は、数理論理学や集合論と比較して、代数的構造をなしている。

歴史

関係代数は、エドガー・F・コッドが1969年に関係モデルを考案するまで、世間ではほとんど興味を持たれなかった。
コッドは関係代数をデータベース言語（問い合わせ言語）の基礎として提唱した。
コッドの関係代数に基づいて実装された最初のデータベース言語は、IBMの ISBL（Information Systems Base Language）であった。
ISBL は PRTV（Peterlee Relational Test Vehicle）という関係データベース管理システム（RDBMS、関係データベース）のデータベース言語である。
ISBL の開拓的な作業はデータベース分野の権威たちの多くにより、コッドの構想を使い勝手の良い言語に実装する道筋をつけたとして、称賛されている。
その後、ISBL という実装を引き継いだ IBM Business System 12 という RDBMS は業界で短期間の影響力をもった。
1998年にクリス・デイトとヒュー・ダーウェンは Tutorial D というデータベース言語を提唱した。
Tutorial D は、関係データベース理論を学習するために使われることを想定していた。
また Tutorial D は ISBL の基本的な考え方を利用している。
Rel という RDBMS は Tutorial D を実装している。
データベース言語 SQL は、関係代数に不完全ながらある程度基づいている。
SQL の演算対象となる表（テーブル）は厳密に関係と呼べるものではなく、また関係代数におけるいくつかの便利な法則も SQL では活用できない（そのため関係代数式の最適化、オプティマイザおよびデータベース利用者に大きな損失を与えている）。

関係モデル

関係代数は関係モデルに基づく関係データベースのデータベース言語 (問い合わせ言語) であるため、最初に関係モデルを簡単に定義する。
関係モデルにおける基本的な構成要素は定義域すなわちデータ型である。
組は順序づけられていない属性の集合である。
属性は定義域と値のペアである。
関係変数は、特定の関係型の名前つきの変数であり、順序づけられていない属性名と属性の定義域のペアの集合である。
関係変数は関係の見出しを提供する。
関係は見出しと組の集合から構成される。
こうした関係モデルの概念は数学的に定義されるが、既存のデータベースの実装はこうした定義に厳密に準拠しているわけではない。
表 (テーブル) は、関係の視覚的表現として受け容れられている。
組は行の概念に似ている。

基本的な演算子

基本的な関係代数の演算子は大きく2つに分類することができる。
集合論に基づく演算子と関係代数に特有な演算子である。
まず集合論に基づく演算子（和、差、交わり (交差) 、直積）を説明し、続けて関係代数特有の演算子（制限 (選択) 、射影、結合、商）を説明する。
また各演算子について、データベース言語（問い合わせ言語）SQL と Tutorial D による関係代数式の表現例を示す。

和

和（union）演算 R ∪ S は、R と S を、R の全ての組（タプル、行）と S の全ての組で構成される一つの関係を返す。
この演算では、R と S が型適合であることが前提となる。
重複する組は除去される。
参考: 和集合

前提

関係 R と S が型適合であること。

SQL

R UNION S

Tutorial D

R UNION S

差

差（difference）演算 R − S は、R から、S に属する組を取り除いた関係を返す。
この演算では、R と S が型適合であることが前提となる。
参考: 差集合

前提

関係 R と S が型適合であること。

SQL

R EXCEPT S

Tutorial D

R MINUS S

交わり

交わり（交差、共通、積、intersection）演算 R ∩ S は、R と S の両方に属する組から関係を返す。
この演算では、R と S が型適合であることが前提となる。
交わり演算と等価な演算を、差演算を使って表現することができる。
R ∩ S = R − (R − S)
参考: 共通部分

前提

関係 R と S が型適合であること。

SQL

R INTERSECT S

Tutorial D

R INTERSECT S

直積

直積（積、デカルト積、cartesian product）演算 R × S は、R と S の組の全ての組み合わせの関係（デカルト積）を返す。
言い換えると、R がもつ全ての組が、S のもつ全ての組と、組み合わせられる。
直積演算では、R と S が型適合である必要は無い。
直積演算 R × S の組の数は、R の組の数と S の組の数を、掛け算した数になる。
直積演算 R × S の属性の数は、R の属性の数と S の属性の数を、足し算した数になる。
参考: 直積集合

SQL

SELECT * FROM R, S

Tutorial D

直接にはサポートされない。

制限

制限（restriction）は、選択（selection）ともいい、ある関係から、指定した条件に合う組の集合を関係として返す。

前提

どの条件式の要素も比較可能であり、比較演算子θを使って条件式が記述されていること。

SQL

SELECT * FROM R WHERE A = 1

Tutorial D

R WHERE A = 1

射影

射影（projection）演算は、ある関係から属性を限定した関係を返す。
射影演算は、Rを構成する属性集合から、いくつかの属性を抽出する。
βを抽出する属性の集合とすると、射影は、πβ(R) もしくは R[β] と記述することができる。

前提

射影演算で指定された属性が、対象となる関係に含まれていること。

SQL

SELECT A, B FROM R

Tutorial D

R { A, B }

結合

結合 (join) は、2つの関係から1つの関係を返す演算であり、直積演算と制限演算を組み合わせた演算に相当する。
一般に、結合を直積演算と制限演算の組み合わせと考えると、この制限演算の制限条件は、A θ B の普通の属性比較が真となるという条件である（θは行おうとする結合演算に応じた比較演算子）。
θ比較の比較演算子は、<、≤、=、>、≥、<> である。
この一般化された結合演算の概念は、θ結合（シータ結合）とも呼ばれる。
一般化された結合演算であるθ結合を具象化した演算として、この節で述べる等結合、自然結合、準結合（半結合）などがある。
この他に外結合（外部結合）も考案されているが、外結合の妥当性については議論の対象となっており、後の節で説明する。

等結合

等結合（equijoin）は、θ結合においてθ比較の比較演算子が「 = 」である結合演算である。

自然結合

自然結合（natural join）の結果として返される関係は、2つの関係に等結合を適用して返された関係から、内容の重複する余分な属性を射影により取り除いた関係である。
自然結合では交換法則と結合法則が成り立つ。
すなわち、 であり、 である。
関係代数演算において、この交換法則と結合法則はクエリ最適化のために活用することができる。

SQL

R NATURAL JOIN S

Tutorial D

R JOIN S

準結合

準結合（半結合、semijoin）は、2つの関係を元にして自然結合を行って返された関係から、結合の元になった一方の関係にのみ存在する属性を射影で除去する演算である。

商

商（division）演算 R ÷ S は、直積演算とは対称となる逆の演算と考えることができる。
関係Rと関係Sがあり、 を R の属性集合、 を S の属性集合とする。
 が成立する場合、次のようになる。

定義

商は、演繹して導き出される演算子であるため、関係代数の他の演算子を使って定義される。
関係 R と S があり、 を R の属性集合、 を S の属性集合とし、 を次のとおりとする。
このとき、商は次のとおり定義される。

SQL

SQLでは、直接、商を求める機能は、提供されていない。
商演算を行うには複雑な問い合わせを記述する必要がある。

Tutorial D

R DIVIDEBY S

応用的な演算子

先述の8つの関係代数演算子よりも後の時期に考案された演算子を説明する。
先の節と同様に各演算子について、データベース言語 (問い合わせ言語) SQL と Tutorial D による関係代数式の表現例を示す。

定義

属性名変更により返される組の集合を  t'  とすると、属性名変更は次のように定義される。

SQL

SELECT A, B AS X, C FROM R

Tutorial D

R RENAME ( B AS X )

拡張

拡張（extend）は、ある関係に何らかの式に基づいて算出される新たな属性が、追加された関係を返す演算である。

SQL

SELECT A, B, (B * 2.54) AS X FROM R

Tutorial D

EXPAND R ADD (B * 2.54 AS X)

SQL

SELECT A, MAX(B) AS X FROM R GROUP BY A

Tutorial D

SUMMARISE R PER ( R{A} ) ADD ( MAX(B) AS X )

外結合

先述した通常の結合（内結合）が結合対象となる2つの関係の組を対応づけて関係を返すのに対し、外結合（外部結合、outer join）は、内結合により返される組に加え、外結合の対象となる関係の組で内結合により対応づけられる組が存在しない組についても、存在しない部分を null という値ないし印で満たして、外結合の結果として返される関係に追加する。
3種類の外結合が定義されている。
すなわち左外結合、右外結合、完全外結合の3種類がある（「外」の字は省略される場合がある）。
外結合については、関係モデルにおける null を否定する立場などから、導入すべきでないとの意見があり、議論の対象となっている。
Tutorial D では外結合に相当する機能は無い。
null についてはここでは説明せず、外結合で満たされるべき場所に割り当てる概念である、と述べるにとどめる。
ここで述べる null は、データベース言語 SQL における NULL であるとの前提をしない。
また null は値ではなく印であるとの前提や、賛否両論のある三値論理を導入するとの前提もしない。

左外結合

関係Rと関係Sがある場合の左外結合（左外部結合、左結合、left outer join） R =X S を考える。
左外結合の結果として返される関係は、 R と S においてこの2つの関係に共通する名前の属性の属性値が全て互いに等しい組の集合に加え（大雑把な表現だが）、Rの組でSに対応づけられない組の集合から、構成される関係である。

SQL

R LEFT OUTER JOIN S

右外結合

右外結合（右外部結合、右結合、right outer join）は左外結合とほとんど同じ振る舞いをするが、左外結合の場合とは逆に、右外結合の対象となる2つの関係のうち2番目の関係に現れる組に相当する組が、右外結合の結果として返される関係に全て現れるという点で異なっている。
関係Rと関係Sがある場合の右外結合 R X= S を考える。
右外結合の結果として返される関係は、 R と S においてこの2つの関係に共通する名前の属性の属性値が全て互いに等しい組の集合に加え、Sの組でRに対応づけられない組の集合から、構成される関係である。

SQL

R RIGHT OUTER JOIN S

完全外結合

完全外結合（完全外部結合、完全結合、単に外結合ともいう、full outer join）の結果として返される関係は、実際には左外結合と右外結合の結果を組み合わせた関係である。
関係Rと関係Sがある場合の完全外結合 R =X= S を考える。
完全外結合の結果として返される関係は、 R と S においてこの2つの関係に共通する名前の属性の属性値が全て互いに等しい組の集合に加え、Rの組でSに対応づけられない組の集合と、Sの組でRに対応づけられない組の集合から、構成される関係である。

SQL

R FULL OUTER JOIN S

最適化における制限演算

制限演算に関する法則は、問い合わせ最適化において大きな役割を果たす。
制限演算は、演算対象の関係の組の数を大幅に減らす。
そのため最適化においては、制限演算を問い合わせ木構造の葉の方向へ移動することで、部分関係代数式により生成される関係群の大きさを小さくすることができるであろう。