関係代数 (関係モデル)のソースを表示

'''関係代数'''（かんけいだいすう、リレーショナル代数、[[英語|英]]: relational algebra）は、[[関係データベース]]の[[関係モデル]] （リレーショナルモデル）において、[[集合論]]と[[一階述語論理]]に基づいて、[[関係 (データベース)|関係]] （リレーション、[[表 (データベース)|表]]、テーブル）として表現されたデータを扱う、[[コンピュータ科学]]における[[代数学|代数]]的な演算の体系である。

関係として表現されたデータに対して行う演算体系としては、[[関係論理]]（関係計算）とこの項目で説明する関係代数の2種類が知られている。
関係代数と関係論理は、主に[[エドガー・F・コッド]]によって考案され、その後コッドを含めた関係データベース（関係モデル）の研究者たちが発展させてきた。

現在では、関係代数の[[演算 (数学)|演算子]]としては、[[#和|和]]、[[#差|差]]、[[#交わり|交わり]] (交差) 、[[#直積|直積]]、[[#制限|制限]] (選択) 、[[#射影|射影]]、[[#結合|結合]]、[[#商|商]]の8種類が言及されることが多い。
ただし[[#属性名変更|属性名変更]]や[[#拡張|拡張]]、[[#要約|要約]]などこの他の演算子も考案されている。

関係代数を[[実装]]した[[データベース言語]]（[[問い合わせ言語]]）としては、[[SQL]] や [[Tutorial D]] などが挙げられる。
ただし SQL については、関係代数を完全な形で実装していないとして批判する意見がある。

数学的に純粋な関係代数は、[[数理論理学]]や[[集合論]]と比較して、[[代数的構造]]をなしている。

== 概要 ==
関係代数の基本的な考え方は、[[集合論]]と[[一階述語論理]]の流れをくんでいる。

関係代数の演算子は、閉包性（closure）をもつ。[[関係 (データベース)|関係]]において閉包である。
つまり次のことがいえる。
* 関係代数は、1つもしくは複数の関係を基にして演算を行う。
* 関係代数で演算を行って返される結果は、必ず関係である。
* 関係代数演算の結果として返された関係を基にして、さらに関係代数で演算することができる。入れ子になった関係代数演算を行うことができる。

現在、言及されることが多い関係代数の[[演算 (数学)|演算子]]としては、[[#和|和]]、[[#差|差]]、[[#交わり|交わり]] (交差) 、[[#直積|直積]]、[[#制限|制限]] (選択) 、[[#射影|射影]]、[[#結合|結合]]、[[#商|商]]の8種類がある（この8種類の演算子については後の[[#基本的な演算子]]の節で説明する）。
ただし[[#属性名変更|属性名変更]]や[[#拡張|拡張]]、[[#要約|要約]]などこの他の演算子も考案されている（後の[[#応用的な演算子]]の節で説明する）。

関係代数は、[[関係データベース管理システム]]（RDBMS、[[関係データベース]]）の[[データベース言語]]（[[問い合わせ言語]]）の基礎となっている。

関係代数と[[関係論理]]（関係計算）は互いに等価である。
関係代数で表現された式は、等価な関係論理の式で表現することができる。
また関係論理で表現された式は、等価な関係代数の式で表現することができる。

関係代数を実装したデータベース言語としては、[[SQL]] や [[Tutorial D]] などが挙げられる。
SQLは、関係代数と関係論理を実装しているとされる。
ただし一部の研究者などの人々（[[クリス・デイト]]や[[ヒュー・ダーウェン]]など）は、SQLに対して、[[関係モデル]]を考案した[[エドガー・F・コッド]]の関係代数を完全な形で実装していないなどとして、批判的な立場をとっている。
デイトとダーウェンは完全な実装として [[D (データベース言語仕様)|D]]（[[Tutorial D]]）を考案し提唱している。

関係は何らかの[[述語]]の[[外延]]と解釈することができるので、関係代数の各々の[[演算 (数学)|演算子]]は述語計算に相当するものと解釈できる。
例えば、自然結合は論理積 AND（<math>\land</math>）に相当する。
関係 ''R'' と関係 ''S'' があり、それぞれ述語 ''p1'' と述語 ''p2'' の外延を表現したものとすると、''R'' と ''S'' の自然結合（''R'' <math>\bowtie</math> ''S''）は、述語 ''p1'' <math>\land</math> ''p2'' の外延を表現する。

関係代数の演算子の正確な集合は、関係代数の定義により異なり得る。
また関係代数の演算子の正確な集合は、名前付けを行わない関係モデル（数学的な関係を採用している）を使うか、それとも名前付けを行う[[関係モデル]]（数学的な関係の名前付けによる一般化を採用している）を使うか、ということにも依存している。
この項目の説明では、名前付けを行う関係モデルを使うことにする。
名前付けを行う関係モデルは、コッドが提唱したものであり、一定の人々によりコッドの最も重要な革新的業績と考えられている。
こうした人々による肯定的な評価は、コッドが自分の関係モデルから関係の[[属性 (データベース)|属性]]の順序という概念を除外したことが大きな理由である。
このモデルでは[[組 (データベース)|組]]（タプル）は、属性名の集合から属性値の集合を導出する部分関数である。
この項目の説明では、組 ''t'' の属性 ''a'' を ''t(a)'' と記述する。

コッドの関係代数が[[一階述語論理]]に関しては実際には完全ではないと留意しておくことは、重要である。
仮に一階述語論理に関して完全であったならば、関係モデルをどのように実装するにせよ、コンピュータ上の克服できない困難に突き当たってしまうであろう。
こうした困難を克服するためにコッドは、関係代数の演算対象を有限の関係のみに限定し、また[[否定]]（NOT）と[[選言]] （OR）を限定的にサポートすることを提唱した。
コッドの関係代数は、実際には[[ホーン節]]で再帰と否定の無い一階述語論理のサブセットである。
こうした限定に類することは、他の多くの論理に基づくコンピュータ言語においてもみられることである。

コッドは、関係データベース言語の表現能力について'''関係完備'''という用語を定義した。
関係完備とは、コッドが提唱した限定のもとで、一階述語論理に関して完全な言語であることを意味する。
実際にコッドが提唱した限定は、コッドの関係代数をデータベースのさまざまな目的に適用することにおいて、不都合は無かった。
関係代数は関係完備である。
関係代数と同等もしくは同等以上の表現能力を持つ関係データベース言語は関係完備であるといえる。
[[関係論理]]（関係計算）は、関係代数と同等の表現能力を持つため、関係完備である。
なお関係論理には定義域関係論理と組関係論理がある。

どのような代数であれ、一定の数の[[演算 (数学)|演算子]]は基本的 (プリミティブ) であり、それ以外の演算子は、基本的な演算子のみをもって定義できるため、基本的ではない。
関係代数における基本的な演算子の選択が、論理学における基本的な演算子の選択と似ているならば、利便である。
AND、OR および NOT の論理における基本的な演算子の選択は恣意的であることはよく知られているが、コッドは自分の関係代数において恣意的な選択をした。
コッドは関係代数において次の6つの基本的な演算子を定めた。
* [[#制限|制限]]（選択）
* [[#射影|射影]]
* [[#直積|直積]]（[[直積集合]]）
* [[#和|和]]（[[合併 (集合論)|和集合]]）
* [[#差|差]]（[[差集合]]）
* [[#属性名変更|属性名変更]]
（実際にはコッドは属性名変更を基本的な演算子群から除去した。しかし属性名変更を含めた例として後の[[#歴史]]の節で述べる ISBL が存在する）
この6つの演算子は、表現能力を損なうこと無くこの6つのいずれをも除くことはできないという意味で、関係代数の基盤をなす。
他の多くの演算子がこの6つの演算子を基にして定義されてきた。
この6つの演算子を基にして定義された演算子のうち非常に重要なものは、[[#交わり|交わり]]（交差、[[共通部分]]）、[[#商|商]]、[[#自然結合|自然結合]]である。
実際に ISBL は直積を自然結合で置き換えるという重要な事例を残した。
直積は自然結合から退化した演算である。

== 関係論理との対比 ==
例えば関係代数では、書籍データベースから次の手順で、特定の書名の書籍を在庫としてもつ書店の店名と電話番号を問い合わせるであろう。
# 書籍関係と書名関係を書店IDで[[#自然結合|結合]]する。
# 結合して生成された関係を指定された書名で[[#制限|制限]]する。
# 制限して生成された関係を店名と電話番号で[[#射影|射影]]する。

この例の問い合わせは[[関係論理]]（関係計算）では次のような宣言的に定式化できる。
{{Indent|書籍データベースにおいて、書籍関係と書名関係のそれぞれの書店IDが同一であるものとし、指定された書名をもつ店名と電話番号を取得する。}}

== 歴史 ==
関係代数は、[[エドガー・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 では活用できない（そのため[[#問い合わせ最適化|関係代数式の最適化]]、[[クエリ最適化|オプティマイザ]]およびデータベース利用者に大きな損失を与えている）。

== 関係モデル ==

[[ファイル:Relational model concepts_Version_Japanese.png|thumbnail|right|360px|[[関係モデル]]の概念]]

{{main|関係モデル}}

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

== 関係の型適合 ==
[[集合論]]に基づく関係[[演算 (数学)|演算子]]（[[#直積|直積]]を除く、[[#和|和]]、[[#差|差]]、[[#交わり|交わり]]）では、2つの型適合（type-compatibility）する[[関係 (データベース)|関係]]を対象として演算を行う。
この種の関係演算では、型適合しない2つ関係を対象として演算を行うことはできない。
型適合は、和両立（union-compatibility）ともいう。

関係の型適合とは、言い換えれば2つの関係がうまく組み合わせることができるということである。
具体的には、関係 R と関係 S について、次の条件が満たされる場合、R と S は型適合である。
* R と S が同じ数の[[属性 (データベース)|属性]]をもっていること。
* R と S がもつ属性の名前が同じであること。
* R と S がもつ同じ名前の属性の[[定義域 (データベース)|定義域]]が同じであること。

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

=== 和 ===
和（union）演算 R ∪ S は、R と S を、R の全ての組（タプル、行）と S の全ての組で構成される一つの[[関係 (データベース)|関係]]を返す。
この演算では、R と S が型適合であることが前提となる。
重複する組は除去される。

参考: [[合併 (集合論)|和集合]]

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

==== 例 ====
{| cellpadding="8"
 |- style="vertical-align: top;"
 |
  {| class="wikitable"
   |+ R:
   ! A || B || C
   |-
   | 1 || 2 || 3
   |-
   | 4 || 5 || 6
   |}
 ||
  {| class="wikitable"
   |+ S:
   ! A || B || C
   |-
   | 7 || 8 || 9
   |-
   | 4 || 5 || 6
   |}
 ||
{| class="wikitable"
 |+ ! style="margin-left: auto; margin-right: auto;" | R ∪ S:
 ! A || B || C
 |-
 | 7 || 8 || 9
 |-
 | 4 || 5 || 6
 |-
 | 1 || 2 || 3
 |}
|}

==== 定義 ====
{|
 |<math>R \cup S := \{ t | t \in R \lor t \in S \}</math>
 |}

==== SQL ====
R UNION S

==== Tutorial D ====
R UNION S

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

参考: [[差集合]]

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

==== 例 ====
{| cellpadding="8"
 |- style="vertical-align: top;"
 |
  {| class="wikitable"
   |+ R:
   ! A || B || C
   |-
   | 1 || 2 || 3
   |-
   | 4 || 5 || 6
   |}
 ||
  {| class="wikitable"
   |+ S:
   ! A || B || C
   |-
   | 7 || 8 || 9
   |-
   | 4 || 5 || 6
   |}
 ||
{| class="wikitable"
 |+ ! style="margin-left: auto; margin-right: auto;" | R − S:
 ! A || B || C
 |-
 | 1 || 2 || 3
 |}
|}

==== 定義 ====
{|
 |<math>R - S := \{ t | t \in R \land t \notin S \}</math>
 |}

==== SQL ====
R EXCEPT S

==== Tutorial D ====
R MINUS S

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

参考: [[共通部分]]

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

==== 例 ====
{| cellpadding="8"
 |- style="vertical-align: top;"
 |
  {| class="wikitable"
   |+ R:
   ! A || B || C
   |-
   | 1 || 2 || 3
   |-
   | 4 || 5 || 6
   |}
 ||
  {| class="wikitable"
   |+ S:
   ! A || B || C
   |-
   | 7 || 8 || 9
   |-
   | 4 || 5 || 6
   |}
 ||
{| class="wikitable"
 |+ ! style="margin-left: auto; margin-right: auto;" | R ∩ S:
 ! A || B || C
 |-
 | 4 || 5 || 6
 |}
|}

==== 定義 ====
{|
 |<math>R \cap S := \{ t | t \in R \land t \in S \}</math>
 |}

==== 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 の属性の数を、足し算した数になる。

参考: [[直積集合]]

==== 前提 ====
関係 R と S に共通の属性名が無いこと。

==== 例 ====
{| cellpadding="8"
 |- style="vertical-align: top;"
 |
  {| class="wikitable"
   |+ R:
   ! A || B || C || D
   |-
   | 1 || 2 || 3 || 4
   |-
   | 4 || 5 || 6 || 7
   |-
   | 7 || 8 || 9 || 0
   |}
 ||
  {| class="wikitable"
   |+ S:
   ! E || F || G
   |-
   | 1 || 2 || 3
   |-
   | 7 || 8 || 9
   |}
 ||
  {| class="wikitable"
   |+ ! style="margin-left: auto; margin-right: auto;" | R x S:
   ! A || B || C || D || E || F || G
   |-
   | 1 || 2 || 3 || 4 || 1 || 2 || 3
   |-
   | 4 || 5 || 6 || 7 || 1 || 2 || 3
   |-
   | 7 || 8 || 9 || 0 || 1 || 2 || 3
   |-
   | 1 || 2 || 3 || 4 || 7 || 8 || 9
   |-
   | 4 || 5 || 6 || 7 || 7 || 8 || 9
   |-
   | 7 || 8 || 9 || 0 || 7 || 8 || 9
   |}
 |}

==== 定義 ====
任意の2つの関係 <math>R={(a_1,a_2,...,a_n)}</math> と <math>S={(b_1,b_2,...,b_m)}</math> について、直積は次のように定義される。

{|
 |<math>R\times S:=\{(a_1,a_2,...,a_n,b_1,b_2,...,b_m)|(a_1,a_2,...,a_n)\in R\wedge (b_1,b_2,...,b_m)\in S\}</math> 
 |}

==== SQL ====
SELECT * FROM R, S

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


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

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

==== 例 ====
{| cellpadding="8"
 |- style="vertical-align: top;"
 |
  {| class="wikitable"
   |+  R:
   ! A || B || C
   |-
   | 1 || 2 || 4
   |-
   | 4 || 6 || 7
   |-
   | 1 || 6 || 7
   |-
   | 8 || 6 || 1
   |}
 ||
  {| class="wikitable"
   |+ R[A=1]:
   ! A || B || C
   |-
   | 1 || 2 || 4
   |-
   | 1 || 6 || 7
   |}
 ||
  {| class="wikitable"
   |+ R[C>6]:
   ! A || B || C
   |-
   | 4 || 6 || 7
   |-
   | 1 || 6 || 7
   |}
 |}

==== 定義 ====
Rを関係とすると、制限は次のように定義される。

{|
 |<math>\sigma_\varphi(R) := \{ \ t : t \in R, \ \varphi(t) \ \}</math>
 |}

<math>\varphi</math> は次のような条件式である。
なお、θは一般的な比較演算子 (&lt;、≤、=、&gt;、≥、&lt;&gt;) である。
* 属性と定数の比較の条件式: 属性 θ 定数
* 属性同士の比較条件式: 属性 θ 属性
* 比較条件式に論理演算記号 (∧、∨、¬) を適用したもの

==== SQL ====
SELECT * FROM R WHERE A = 1

==== Tutorial D ====
R WHERE A = 1

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

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

==== 例 ====
{| cellpadding="8"
 |- style="vertical-align: top;"
 |
  {| class="wikitable"
   |+  R:
   ! A || B || C
   |-
   | 1 || 2 || 3
   |-
   | 4 || 5 || 6
   |}
 ||
  {| class="wikitable"
   |+ R[A,B]:
   ! A || B
   |-
   | 1 || 2
   |-
   | 4 || 5
   |}
 ||
  {| class="wikitable"
   |+ R[A]:
   ! A
   |-
   | 1
   |-
   | 4
   |}
 |}

==== 定義 ====
Rを関係とし、Rは {A<sub>1</sub>, …, A<sub>k</sub>} として属性をもつとする。
また、β ⊆ {A<sub>1</sub>, …, A<sub>k</sub>} とする (βはRの全属性の部分集合である属性の集合) 。

{|
 |<math>\pi_{\beta}(R):=\{t_{\beta}|t \in R\}</math>
 |}

t<sub>β</sub> := (β) は、βを構成する属性集合だけからなる組を意味する。

==== SQL ====
SELECT A, B FROM R 

==== Tutorial D ====
R { A, B }

=== 結合 ===

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

==== 前提 ====
関係 R と S に共通の属性名が無いこと。

==== 例 ====
{| cellpadding="8"
 |- style="vertical-align: top;"
 |
  {| class="wikitable"
   |+ R:
   ! A || B || C || D
   |-
   | 1 || 2 || 3 || 4
   |-
   | 4 || 5 || 6 || 7
   |-
   | 7 || 8 || 9 || 0
   |}
 ||
  {| class="wikitable"
   |+ S:
   ! E || F || G
   |-
   | 1 || 2 || 3
   |-
   | 7 || 8 || 9
   |}
 ||
  {| class="wikitable"
   |+ R x S:
   ! A || B || C || D || E || F || G
   |-
   | '''1''' || 2 || 3 || 4 || '''1''' || 2 || 3
   |-
   | 4 || 5 || 6 || 7 || 1 || 2 || 3
   |-
   | 7 || 8 || 9 || 0 || 1 || 2 || 3
   |-
   | 1 || 2 || 3 || 4 || 7 || 8 || 9
   |-
   | 4 || 5 || 6 || 7 || 7 || 8 || 9
   |-
   | '''7''' || 8 || 9 || 0 || '''7''' || 8 || 9
   |}
||
  {| class="wikitable"
   |+ JOIN(R, R.A <> S.E, S):
   ! A || B || C || D || E || F || G
   |-
   | 4 || 5 || 6 || 7 || 1 || 2 || 3
   |-
   | 7 || 8 || 9 || 0 || 1 || 2 || 3
   |-
   | 1 || 2 || 3 || 4 || 7 || 8 || 9
   |-
   | 4 || 5 || 6 || 7 || 7 || 8 || 9
   |}
 |}

==== 定義 ====
関係<math>R(A_1, ..., A_n, B_1, ..., B_n)</math> と関係<math>S(B_1, ..., B_n, C_1, ..., C_n)</math> のθ結合は、次のように定義される。
なお、θ比較式を expression とする。

{|
 |<math>R \triangleright\!\!\triangleleft\,_{\mathrm{expression}} S:= \{ r \cup s | r \in R \land s \in S \land \mathrm{expression} \}</math>
 |}

この定義を演繹すると次のように表現できる。

{|
 |<math>R \triangleright\!\!\triangleleft\,_{\mathrm{expression}} S:= \sigma_{\mathrm{expression}}(R \times S)</math>
 |}

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

===== 例 =====
{| cellpadding="8"
 |- style="vertical-align: top;"
 |
  {| class="wikitable"
   |+ R:
   ! A || B || C || D
   |-
   | 1 || 2 || 3 || 4
   |-
   | 4 || 5 || 6 || 7
   |-
   | 7 || 8 || 9 || 0
   |}
 ||
  {| class="wikitable"
   |+ S:
   ! E || F || G
   |-
   | 1 || 2 || 3
   |-
   | 7 || 8 || 9
   |}
 ||
  {| class="wikitable"
   |+ R x S:
   ! A || B || C || D || E || F || G
   |-
   | '''1''' || 2 || 3 || 4 || '''1''' || 2 || 3
   |-
   | 4 || 5 || 6 || 7 || 1 || 2 || 3
   |-
   | 7 || 8 || 9 || 0 || 1 || 2 || 3
   |-
   | 1 || 2 || 3 || 4 || 7 || 8 || 9
   |-
   | 4 || 5 || 6 || 7 || 7 || 8 || 9
   |-
   | '''7''' || 8 || 9 || 0 || '''7''' || 8 || 9
   |}
||
  {| class="wikitable"
   |+ JOIN(R, R.A = S.E, S):
   ! A || B || C || D || E || F || G
   |-
   | '''1''' || 2 || 3 || 4 || '''1''' || 2 || 3
   |-
   | '''7''' || 8 || 9 || 0 || '''7''' || 8 || 9
   |}
 |}

===== 定義 =====
関係Rと関係Sがあり、これらの関係内の属性集合A、Bについて A&nbsp;∈&nbsp;R、B&nbsp;∈&nbsp;S とすると、等結合は次のように定義される。

{|
 |<math>R \triangleright\!\!\triangleleft\,_{A=B} S:= \{ r \cup s | r \in R \land s \in S \land r_{[A]}=s_{[B]} \}</math>
 |}

==== 自然結合 ====
自然結合（natural join）は⋈と書かれる二項演算で、2つの関係に共通の属性の値が等しいすべての組み合わせからなる関係を返す。
2つの関係に共通の属性がない場合、これは直積に等しくなる。
自然結合では交換法則と結合法則が成り立つ。
すなわち、<math> R \triangleright\!\!\triangleleft\, S = S \triangleright\!\!\triangleleft\, R</math> であり、<math> (R \triangleright\!\!\triangleleft\, S ) \triangleright\!\!\triangleleft\, T = R \triangleright\!\!\triangleleft\, ( S \triangleright\!\!\triangleleft\, T)</math> である。
関係代数演算において、この交換法則と結合法則は[[クエリ最適化]]のために活用することができる。

==== 前提 ====
なし。

===== 例 =====
{| cellpadding="8"
 |- style="vertical-align: top;"
 |
  {| class="wikitable"
   |+ 従業員:
   ! 名前 || 従業員ID || 部署名
   |-
   | ハリー || 3415 || ファイナンス
   |-
   | サリー || 2241 || 販売
   |-
   | ジョージ || 3401 || ファイナンス
   |-
   | ハリエット || 2202 || 販売
   |-
   | メアリー || 1257 || 人事
   |}
 ||
  {| class="wikitable"
   |+ 部署:
   ! 部署名 || マネージャー
   |-
   | ファイナンス || ジョージ
   |-
   | 販売 || ハリエット
   |-
   | 生産 || チャールズ
   |}
||
  {| class="wikitable"
   |+ 従業員⋈部署:
   !名前 || 従業員ID || 部署名 || マネージャー
   |-
   | ハリー || 3415 || ファイナンス || ジョージ
   |-
   | サリー || 2241 || 販売 || ハリエット
   |-
   | ジョージ || 3401 || ファイナンス || ジョージ
   |-
   | ハリエット || 2202 || 販売 || ハリエット
   |}
 |}
従業員と部署の共通の属性は部署名であり、従業員⋈部署には部署名が同じになる組み合わせが含まれている。
従業員の(メアリー,1257,人事)と部署の(生産,チャールズ)は部署名が同じになる組み合わせがないため従業員⋈部署には含まれず、部署の(ファイナンス,ジョージ)と(販売,ハリエット)は部署名が同じになる組み合わせが複数あるため従業員⋈部署に複数回登場する。

===== 定義 =====
関係<math>R(A_1, ..., A_n, B_1, ..., B_n)</math> と関係<math>S(B_1, ..., B_n, C_1, ..., C_n)</math> の自然結合は次のように定義される。

{|
 |<math>R \triangleright\!\!\triangleleft\, S:= \{ r \cup s_{[C_1, ..., C_n]} | r \in R \land s \in S \land r_{[B_1, ..., B_n]} =s_{[B_1, ..., B_n]} \}</math>
 |}

===== SQL =====
R NATURAL JOIN S

===== Tutorial D =====
R JOIN S


==== 準結合 ====
準結合（半結合、semijoin）は、自然結合に似た二項演算R⋉Sで、自然結合R⋈Sの属性をRに含まれているもののみに射影した関係を返す。

===== 例 =====
{| cellpadding="8"
 |- style="vertical-align: top;"
 |
  {| class="wikitable"
   |+ 従業員:
   ! 名前 || 従業員ID || 部署名
   |-
   | ハリー || 3415 || ファイナンス
   |-
   | サリー || 2241 || 販売
   |-
   | ジョージ || 3401 || ファイナンス
   |-
   | ハリエット || 2202 || 生産
   |}
 ||
  {| class="wikitable"
   |+ 部署:
   ! 部署名 || マネージャー
   |-
   | 販売 || サリー
   |-
   | 生産 || ハリエット
   |}
 ||
  {| class="wikitable"
   |+ 従業員⋉部署:
   !名前 || 従業員ID || 部署名
   |-
   | サリー || 2241 || 販売
   |-
   | ハリエット || 2202 || 生産
   |}
 |}

===== 定義 =====
関係<math>R(A_1, ..., A_n, B_1, ..., B_n)</math> と関係<math>S(B_1, ..., B_n, C_1, ..., C_n)</math> の準結合は、次のように定義される。

{|
 |<math>R \ \triangleright\!\!\!< S:= \{ r | r \in R \land s \in S \land r_{[B_1, ..., B_n]} =s_{[B_1, ..., B_n]} \}</math>
 |}

=== 商 ===
商（division）演算 R ÷ S は、 R に固有の属性名に対する R のタプルの制限、つまりRの属性ではあるがSの属性ではなく、 Sのタプルとのすべての組み合わせがRに存在するという制限で構成されている。
商は直積演算とは対称となる逆の演算と考えることができる。
関係Rと関係Sがあり、<math>\beta</math> を R の属性集合、<math>\gamma</math> を S の属性集合とする。
<math>\beta \cap \gamma = \varnothing</math> が成立する場合、次のようになる。

<math>T = R \times S</math><br/>
<math>T \div S = R</math>

==== 例 ====
関係Rがあり、R の属性として father、mother、child、age があるとする。
さらに関係Sがあり、S の属性として child、age があるとする。
S には Maria（4歳）と Sabine（2歳）のデータが存在する。
R を S で商を求めると、一つの関係が結果として返される。
この結果として返された関係は、Maria（4歳）と Sabine（2歳）を娘としてもつ夫婦のみで構成される関係である。
{| cellpadding="8"
 |- style="vertical-align: top;"
 |
  {| class="wikitable"
   |+ R:
   ! father || mother || child || age
   |-
   | Hans || Helga || Harald || 5
   |-
   | Hans || Helga || Maria || 4
   |-
   | Hans || Ursula || Sabine || 2
   |-
   | Martin || Melanie || Gertrud || 7
   |-
   | Martin || Melanie || Maria || 4
   |-
   | Martin || Melanie || Sabine || 2
   |-
   | Peter || Christina || Robert || 9
   |}
 ||
  {| class="wikitable"
   |+ S:
   ! child || age
   |-
   | Maria || 4
   |-
   | Sabine || 2
   |}
 ||
  {| class="wikitable"
   |+ R÷S:
   ! father || mother
   |-
   | Martin || Melanie
   |}
 |}

==== 定義 ====
商は、演繹して導き出される演算子であるため、関係代数の他の演算子を使って定義される。
関係 R と S があり、<math>\beta</math> を R の属性集合、<math>\gamma</math> を S の属性集合とし、<math>R'</math> を次のとおりとする。<math>R' := \beta \setminus \gamma</math>

このとき、商は次のとおり定義される。

<math>R \div S := \pi_{R'}(R) - \pi_{R'}((\pi_{R'}(R) \times S) - R)</math>

==== SQL ====
SQLでは、直接、商を求める機能は、提供されていない<ref>山平耕作、小寺孝、土田正士 (2004) p.109</ref>。
商演算を行うには複雑な問い合わせを記述する必要がある。

==== Tutorial D ====
R DIVIDEBY S

== 応用的な演算子 ==

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

=== 属性名変更 ===
属性名変更（rename）は、[[関係 (データベース)|関係]]の[[属性 (データベース)|属性]]の名前を変更する演算である。
この演算子は次に述べるとおり重要である。
* さまざまな関係の結合演算を可能とする。
* 同じ属性名を持つ2つの関係を元にする直積演算を可能とする。とりわけ同じ関係同士でも直積演算を可能とする。
* さまざまな属性を持つ2つの関係を元にして多くの関係代数演算を可能とする。

属性名変更は次のように記述する。

<math>\beta_{[\mathrm{new}\leftarrow\mathrm{old}]} (R)</math> もしくは R[old→new]

==== 例 ====
{| cellpadding="8"
 |- style="vertical-align: top;"
 |
  {| class="wikitable"
   |+ R:
   ! A || B || C
   |-
   | 1 || 2 || 3
   |-
   | 4 || 5 || 6
   |}
 ||
  {| class="wikitable"
   |+ R[B→X]:
   ! A || X || C
   |-
   | 1 || 2 || 3
   |-
   | 4 || 5 || 6
   |}
 |}

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

<math>\beta_{[\mathrm{new}\leftarrow\mathrm{old}]}(R):= \{t'|t'(R-\mathrm{new})=t(R-\mathrm{old}) \land t'(\mathrm{new})=t(\mathrm{old})\}</math>

==== SQL ====
SELECT A, B AS X, C FROM R

==== Tutorial D ====
R RENAME ( B AS X )

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

==== 例 ====
関係Rについて、Rの属性Bが[[インチ]]単位で示されているとして、[[センチメートル]]単位の値を求める場合。
{| cellpadding="8"
 |- style="vertical-align: top;"
 |
  {| class="wikitable"
   |+ R:
   ! A || B
   |-
   | 1 || 2
   |-
   | 3 || 4
   |-
   | 5 || 6
   |}
 ||
  {| class="wikitable"
   |+ EXPAND R ADD (B * 2.54 AS X):
   ! A || B || X
   |-
   | 1 || 2 || 5.08
   |-
   | 3 || 4 || 10.16
   |-
   | 5 || 6 || 15.24
   |}
 |}

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

==== Tutorial D ====
EXPAND R ADD (B * 2.54 AS X) 

=== 要約 ===
多くの[[関係データベース管理システム]]（RDBMS、[[関係データベース]]）では次の5つの要約（summarize）の機能を使うことができる。
* sum（合計値）
* count（演算対象となる関係の組の数）
* average（平均値）
* maximum（最大値）
* minimum（最小値）
<!--
関係代数においては、一般に次のように記述する。
{{Indent|<sub>Exp1, Exp2, Exp3...</sub>G<sub>func1, func2, func3...</sub>(関係)}}
-->

==== 例 ====
関係Rについて、Rの属性AとAにおけるBの最大値を求める。
{| cellpadding="8"
 |- style="vertical-align: top;"
 |
  {| class="wikitable"
   |+ R:
   ! A || B
   |-
   | 1 || 1
   |-
   | 1 || 2
   |-
   | 1 || 4
   |-
   | 2 || 2
   |-
   | 2 || 3
   |-
   | 3 || 1
   |-
   | 3 || 5
   |}
 ||
  {| class="wikitable"
   |+ SUMMARISE R PER ( R{A} ) ADD ( MAX(B) AS X ):
   ! A || X
   |-
   | 1 || 4
   |-
   | 2 || 3
   |-
   | 3 || 5
   |}
 |}

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

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

=== <span id="外部結合"></span>外結合 ===
先述した通常の結合（内結合）が結合対象となる2つの関係の組を対応づけて関係を返すのに対し、外結合（外部結合、outer join）は、内結合により返される組に加え、外結合の対象となる関係の組で内結合により対応づけられる組が存在しない組についても、存在しない部分を [[null]] という値ないし印で満たして、外結合の結果として返される関係に追加する。

3種類の外結合が定義されている。
すなわち[[#左外結合|左外結合]]、[[#右外結合|右外結合]]、[[#完全外結合|完全外結合]]の3種類がある（「外」の字は省略される場合がある）。

外結合については、[[関係モデル]]における null を否定する立場などから、導入すべきでないとの意見があり、議論の対象となっている。
Tutorial D では外結合に相当する機能は無い。

null についてはここでは説明せず、外結合で満たされるべき場所に割り当てる概念である、と述べるにとどめる。
ここで述べる null は、データベース言語 [[SQL]] における NULL であるとの前提をしない。
また null は値ではなく印であるとの前提や、賛否両論のある三値論理を導入するとの前提もしない。

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

===== 例 =====
この例で R と S で共通の名前を持つ属性に関して S に共通する組が無い R の組については、左外結合で返される関係においては null の値が設定される。
R で属性 A の値が 4 である組については、対応する S の組が無いため、左外結合で返される関係で、null が出現している。
{| cellpadding="8"
 |- style="vertical-align: top;"
 |
  {| class="wikitable"
   |+ R:
   ! A || B || C || D
   |-
   | 1 || 2 || 3 || 4
   |-
   | 4 || 5 || 6 || 7
   |-
   | 7 || 8 || 9 || 0
   |}
 ||
  {| class="wikitable"
   |+ S:
   ! A || F || G
   |-
   | 1 || 2 || 3
   |-
   | 7 || 8 || 9
   |}
||
  {| class="wikitable"
   |+ LEFT OUTER JOIN (R, S):
   !A || B || C || D || F || G
   |-
   | '''1''' || 2 || 3 || 4 || 2 || 3
   |-
   | '''4''' || 5 || 6 || 7 || (null) || (null)
   |-
   | '''7''' || 8 || 9 || 0 || 8 || 9
   |}
 |}

数学的には、左外結合は自然結合と集合和とで模擬実行できる。
{{Indent|''R'' <nowiki>=</nowiki>X ''S''  <nowiki>=</nowiki>  ''R'' ∪ (''R''<math>\bowtie</math>''S'')}}

===== SQL =====
R LEFT OUTER JOIN S

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

===== 例 =====
この例で R と S で共通の名前を持つ属性に関して R に共通する組が無い S の組については、右外結合で返される関係においては null の値が設定される。
S で属性 A の値が 10 である組については、対応する R の組が無いため、完全外結合で返される関係で、null が出現している。
{| cellpadding="8"
 |- style="vertical-align: top;"
 |
  {| class="wikitable"
   |+ R:
   ! A || B || C || D
   |-
   | 1 || 2 || 3 || 4
   |-
   | 4 || 5 || 6 || 7
   |-
   | 7 || 8 || 9 || 0
   |}
 ||
  {| class="wikitable"
   |+ S:
   ! A || F || G
   |-
   | 1 || 2 || 3
   |-
   | 7 || 8 || 9
   |-
   | 10 || 11 || 12
   |}
||
  {| class="wikitable"
   |+ RIGHT OUTER JOIN (R, S):
   !A || B || C || D || F || G
   |-
   | '''1''' || 2 || 3 || 4 || 2 || 3
   |-
   | '''7''' || 8 || 9 || 0 || 8 || 9
   |-
   | '''10''' || (null) || (null) || (null) || 11 || 12
   |}
 |}

数学的には、右外結合は自然結合と集合和とで模擬実行できる。
{{Indent|''R'' X<nowiki>=</nowiki> ''S''  <nowiki>=</nowiki>  ''S'' ∪ (''R''<math>\bowtie</math>''S'')}}

===== SQL =====
R RIGHT OUTER JOIN S

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

===== 例 =====
この例で R と S で共通の名前を持つ属性に関して、S に共通する組が無い R の組、および R に共通する組が無い S の組については、完全外結合で返される関係においては null の値が設定される。
R で属性 A の値が 4 である組については、対応する S の組が無いため、完全外結合で返される関係で、null が出現している。
また S で属性 A の値が 10 である組については、対応する R の組が無いため、完全外結合で返される関係で、null が出現している。
{| cellpadding="8"
 |- style="vertical-align: top;"
 |
  {| class="wikitable"
   |+ R:
   ! A || B || C || D
   |-
   | 1 || 2 || 3 || 4
   |-
   | 4 || 5 || 6 || 7
   |-
   | 7 || 8 || 9 || 0
   |}
 ||
  {| class="wikitable"
   |+ S:
   ! A || F || G
   |-
   | 1 || 2 || 3
   |-
   | 7 || 8 || 9
   |-
   | 10 || 11 || 12
   |}
||
  {| class="wikitable"
   |+ FULL OUTER JOIN (R, S):
   !A || B || C || D || F || G
   |-
   | '''1''' || 2 || 3 || 4 || 2 || 3
   |-
   | '''4''' || 5 || 6 || 7 || (null) || (null)
   |-
   | '''7''' || 8 || 9 || 0 || 8 || 9
   |-
   | '''10''' || (null) || (null) || (null) || 11 || 12
   |}
 |}

数学的には、完全外結合は左外結合と右外結合 (したがって自然結合と集合和) とで模擬実行できる。
{{Indent|''R''<nowiki>=X=</nowiki>''S'' <nowiki>=</nowiki> (''R''<nowiki>=</nowiki>X''S'') ∪ (''R''X<nowiki>=</nowiki>''S'') or ''R''<nowiki>=X=</nowiki>''S'' <nowiki>=</nowiki> ''R'' ∪ ''S'' ∪ (''R'' ⋈ ''S'')}}

===== SQL =====
R FULL OUTER JOIN S

== 問い合わせ最適化 ==
関係代数と[[関係 (データベース)|関係]]群に対する問い合わせの最適化について説明する。

関係群に対する問い合わせは[[木構造 (データ構造)|木構造]]として表現される。
その木構造において、
* 節は関係代数演算子である。
* 葉は関係である。
* 部分木は部分関係代数式である。

最適化の第一の目標は、関係代数式を、木構造内の部分木により与えられる部分関係代数式が生成する関係の平均的な大きさを、最適化前の関係代数式が生成する関係の平均的な大きさより小さくする、同等な関係代数式に変換することである。
第二の目標は、一つの問い合わせ内において複数回出現する共通の部分関係代数式を同定することであり、また同時に複数の問い合わせが評価される際、それら全ての問い合わせにおいて複数回出現する共通の部分関係代数式を同定することである。
第二の目標で複数回出現する共通の部分関係代数式を同定することにより、一度その部分関係代数式を計算すれば、その計算結果を同じ部分関係代数式が出現し評価する際に再利用すれば良く、問い合わせにおいて再度同じ部分関係代数式を計算する必要は無くなる。

次に木構造のこうした変換における法則群を説明する。

参考: [[クエリ最適化]]

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

==== 制限演算の基本的な法則 ====
#<math>\sigma_{A}(R)=\sigma_{A}\sigma_{A}(R)</math>
#<math>\sigma_{A}\sigma_{B}(R)=\sigma_{B}\sigma_{A}(R)</math>

==== 複合した制限演算の分解 ====
先述の2つの法則を、制限演算の連なりを分割/結合するために使うことができる。
いくつかの情況においては、制限演算を結合することは有効である。
なぜなら制限演算子を2回使うのではなく1回で済むからである。
別の情況においては、複合した制限演算を分割することが有効である。
このときは、複合した制限演算を木構造内で移動できない場合に、個々の制限演算に分割することで、移動できるようになる。

#<math>\sigma_{A \land B}(R)=\sigma_{A}(\sigma_{B}(R))=\sigma_{B}(\sigma_{A}(R))</math>
#<math>\sigma_{A \lor B}(R)=\sigma_{A}(R)\cup\sigma_{B}(R)</math>

==== 制限と直積 ====
直積は評価に最もコストを要する演算である。
入力の関係の濃度 (組の数) が <math>N</math> と <math>M</math> であった場合、直積演算の結果として返される関係の濃度は <math>NM</math> となる。
そのため直積演算を行う前に、演算対象の2つの関係の濃度をできるだけ小さくするよう、最善を尽くすことが重要である。

直積演算の後に制限演算を行う場合、例えば σ<sub><math>A</math></sub>(<math>R</math> × <math>P</math>) を評価する場合、この最適化は効果的に行うことができる。
結合の定義を考えると、最適化をとりわけ効果的に行うことができる。
もし制限演算の後に直積演算が続くのであれば、他の制限の法則を使うことで、制限演算を問い合わせの木構造の高い位置から葉の方向へ押し下げるよう試みることができる。

この場合制限条件式 <math>A</math> を、複合した制限演算を分割する法則群を使うことで、制限条件式 <math>B</math>、<math>C</math>、<math>D</math> へと分解する。
すなわち <math>A</math> = <math>B</math> ∧ <math>C</math> ∧ <math>D</math> となる。
そして <math>B</math> は関係 <math>R</math> の属性のみから構成され、<math>C</math> は関係 <math>P</math> の属性のみから構成され、<math>D</math> は <!--<math>A</math> の一部として--> <math>R</math> と <math>P</math> の両方の属性から構成されるようにする。
<math>B</math>、<math>C</math>、<math>D</math> のいずれかが欠如している場合もある。
以上の変換は次のように示される。
*σ<sub><math>A</math></sub>(<math>R</math> × <math>P</math>) = σ<sub><math>B</math> ∧ <math>C</math> ∧ <math>D</math></sub>(<math>R</math> × <math>P</math>) = σ<sub><math>D</math></sub>(σ<sub><math>B</math></sub>(<math>R</math>) × σ<sub><math>C</math></sub>(<math>P</math>))

==== 制限と集合演算 ====
次の3つの法則は、問い合わせの木構造において制限演算を集合演算 (差・和・交わり) よりも葉に近い方向に押し下げる。

注意: 差演算もしくは交わり演算の場合は、木構造を変換することで、制限演算を演算対象の関係群のうちただ一つの関係に対して適用することが可能である。
この適用による最適化が有効なのは、演算対象の関係群のうち一つが小さく、小さな関係を演算対象として使うことによる利益に対して、制限演算を行うことに伴うオーバーヘッドが大きい場合である。

#<math>\sigma_{A}(R\setminus P)=\sigma_{A}(R)\setminus \sigma_{A}(P) =\sigma_{A}(R)\setminus P</math>
#<math>\sigma_{A}(R\cup P)=\sigma_{A}(R)\cup\sigma_{A}(P)</math>
#<math>\sigma_{A}(R\cap P)=\sigma_{A}(R)\cap\sigma_{A}(P)=\sigma_{A}(R)\cap P=R\cap \sigma_{A}(P)</math>
<!--
==== 制限と射影 ====
{{節スタブ}}
-->
== 関連項目 ==
* [[関係モデル]]
** [[関係 (データベース)]]
** [[関係論理]] (関係計算)
* [[関係データベース]]
* [[関係データベース管理システム]] (RDBMS)
* [[データベース言語]] / [[問い合わせ言語]]
** [[SQL]]
** [[D (データベース言語仕様)]]
*** [[Tutorial D]]
* [[クエリ最適化]]
* [[エドガー・F・コッド]]

== 参考文献 ==
* [[エドガー・F・コッド|Edgar F. Codd]]、''[http://www.acm.org/classics/nov95/ A Relational Model of Data for Large Shared Data Banks]'', ''Communications of the ACM.'' 6/13/1970, S. 377–387. - エドガー・F・コッドの[[関係モデル]]の論文 (1970年)
* [[クリス・デイト|C.J.Date]]、株式会社クイープ (訳)、『データベース実践講義&mdash;エンジニアのためのリレーショナル理論』、[[オーム社]]、2006年、ISBN 4-87311-275-3
* C.J.Date、[[ヒュー・ダーウェン|Hugh Darwen]]、QUIP LLC (訳)、『標準SQLガイド 改訂第4版』、[[アスキー (企業)|アスキー]]、1999年、ISBN 4-7561-2047-4
* 山平耕作、小寺孝、土田正士、『SQLスーパーテキスト』、[[技術評論社]]、2004年、ISBN 4-7741-1974-1

== 脚注 ==
{{Reflist}}

== 外部リンク ==
* [http://leap.sourceforge.net LEAP] - 学習目的の[[関係データベース管理システム]] (RDBMS) であり、関係代数を実装している。
* [http://www-db.stanford.edu/~widom/cs346/ioannidis.pdf Query Optimization] - この論文は、[[クエリ最適化]]における関係代数の使用に関する上質の入門であり、より深い研究内容を記した多くの引用文献を含んでいる。

{{Database}}

{{DEFAULTSORT:かんけいたいすう}}
[[Category:データベース]]
[[Category:問い合わせ言語]]
[[Category:データモデリング]]
[[Category:関係モデル]]