関係代数（かんけいだいすう、リレーショナル代数、英: relational algebra）は、関係データベースの関係モデル （リレーショナルモデル）において、集合論と一階述語論理に基づいて、関係 （リレーション、表、テーブル）として表現されたデータを扱う、コンピュータ科学における代数的な演算の体系である。関係として表現されたデータに対して行う演算体系としては、関係論理（関係計算）とこの項目で説明する関係代数の2種類が知られている。関係代数と関係論理は、主にエドガー・F・コッドによって考案され、その後コッドを含めた関係データベース（関係モデル）の研究者たちが発展させてきた。現在では、関係代数の演算子としては、和、差、交わり (交差) 、直積、制限 (選択) 、射影、結合、商の8種類が言及されることが多い。ただし属性名変更や拡張、要約などこの他の演算子も考案されている。関係代数を実装したデータベース言語（問い合わせ言語）としては、SQL や Tutorial D などが挙げられる。ただし SQL については、関係代数を完全な形で実装していないとして批判する意見がある。数学的に純粋な関係代数は、数理論理学や集合論と比較して、代数的構造をなしている。関係代数の基本的な考え方は、集合論と一階述語論理の流れをくんでいる。関係代数の演算子は、閉包性（closure）をもつ。関係において閉包である。つまり次のことがいえる。現在、言及されることが多い関係代数の演算子としては、和、差、交わり (交差) 、直積、制限 (選択) 、射影、結合、商の8種類がある（この8種類の演算子については後の#基本的な演算子の節で説明する）。ただし属性名変更や拡張、要約などこの他の演算子も考案されている（後の#応用的な演算子の節で説明する）。関係代数は、関係データベース管理システム（RDBMS、関係データベース）のデータベース言語（問い合わせ言語）の基礎となっている。関係代数と関係論理（関係計算）は互いに等価である。関係代数で表現された式は、等価な関係論理の式で表現することができる。また関係論理で表現された式は、等価な関係代数の式で表現することができる。関係代数を実装したデータベース言語としては、SQL や Tutorial D などが挙げられる。SQLは、関係代数と関係論理を実装しているとされる。ただし一部の研究者などの人々（クリス・デイトやヒュー・ダーウェンなど）は、SQLに対して、関係モデルを考案したエドガー・F・コッドの関係代数を完全な形で実装していないなどとして、批判的な立場をとっている。デイトとダーウェンは完全な実装として D（Tutorial D）を考案し提唱している。関係は何らかの述語の外延と解釈することができるので、関係代数の各々の演算子は述語計算に相当するものと解釈できる。例えば、自然結合は論理積 AND（formula_1）に相当する。関係 "R" と関係 "S" があり、それぞれ述語 "p1" と述語 "p2" の外延を表現したものとすると、"R" と "S" の自然結合（"R" formula_2 "S"）は、述語 "p1" formula_1 "p2" の外延を表現する。関係代数の演算子の正確な集合は、関係代数の定義により異なり得る。また関係代数の演算子の正確な集合は、名前付けを行わない関係モデル（数学的な関係を採用している）を使うか、それとも名前付けを行う関係モデル（数学的な関係の名前付けによる一般化を採用している）を使うか、ということにも依存している。この項目の説明では、名前付けを行う関係モデルを使うことにする。名前付けを行う関係モデルは、コッドが提唱したものであり、一定の人々によりコッドの最も重要な革新的業績と考えられている。こうした人々による肯定的な評価は、コッドが自分の関係モデルから関係の属性の順序という概念を除外したことが大きな理由である。このモデルでは組（タプル）は、属性名の集合から属性値の集合を導出する部分関数である。この項目の説明では、組 "t" の属性 "a" を "t(a)" と記述する。コッドの関係代数が一階述語論理に関しては実際には完全ではないと留意しておくことは、重要である。仮に一階述語論理に関して完全であったならば、関係モデルをどのように実装するにせよ、コンピュータ上の克服できない困難に突き当たってしまうであろう。こうした困難を克服するためにコッドは、関係代数の演算対象を有限の関係のみに限定し、また否定（NOT）と選言 （OR）を限定的にサポートすることを提唱した。コッドの関係代数は、実際にはホーン節で再帰と否定の無い一階述語論理のサブセットである。こうした限定に類することは、他の多くの論理に基づくコンピュータ言語においてもみられることである。コッドは、関係データベース言語の表現能力について関係完備という用語を定義した。関係完備とは、コッドが提唱した限定のもとで、一階述語論理に関して完全な言語であることを意味する。実際にコッドが提唱した限定は、コッドの関係代数をデータベースのさまざまな目的に適用することにおいて、不都合は無かった。関係代数は関係完備である。関係代数と同等もしくは同等以上の表現能力を持つ関係データベース言語は関係完備であるといえる。関係論理（関係計算）は、関係代数と同等の表現能力を持つため、関係完備である。なお関係論理には定義域関係論理と組関係論理がある。どのような代数であれ、一定の数の演算子は基本的 (プリミティブ) であり、それ以外の演算子は、基本的な演算子のみをもって定義できるため、基本的ではない。関係代数における基本的な演算子の選択が、論理学における基本的な演算子の選択と似ているならば、利便である。AND、OR および NOT の論理における基本的な演算子の選択は恣意的であることはよく知られているが、コッドは自分の関係代数において恣意的な選択をした。コッドは関係代数において次の6つの基本的な演算子を定めた。（実際にはコッドは属性名変更を基本的な演算子群から除去した。しかし属性名変更を含めた例として後の#歴史の節で述べる ISBL が存在する）この6つの演算子は、表現能力を損なうこと無くこの6つのいずれをも除くことはできないという意味で、関係代数の基盤をなす。他の多くの演算子がこの6つの演算子を基にして定義されてきた。この6つの演算子を基にして定義された演算子のうち非常に重要なものは、交わり（交差、共通部分）、商、自然結合である。実際に ISBL は直積を自然結合で置き換えるという重要な事例を残した。直積は自然結合から退化した演算である。例えば関係代数では、書籍データベースから次の手順で、特定の書名の書籍を在庫としてもつ書店の店名と電話番号を問い合わせるであろう。この例の問い合わせは関係論理（関係計算）では次のような宣言的に定式化できる。関係代数は、エドガー・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つの型適合（type-compatibility）する関係を対象として演算を行う。この種の関係演算では、型適合しない2つ関係を対象として演算を行うことはできない。型適合は、和両立（union-compatibility）ともいう。関係の型適合とは、言い換えれば2つの関係がうまく組み合わせることができるということである。具体的には、関係 R と関係 S について、次の条件が満たされる場合、R と S は型適合である。基本的な関係代数の演算子は大きく2つに分類することができる。集合論に基づく演算子と関係代数に特有な演算子である。まず集合論に基づく演算子（和、差、交わり (交差) 、直積）を説明し、続けて関係代数特有の演算子（制限 (選択) 、射影、結合、商）を説明する。また各演算子について、データベース言語（問い合わせ言語）SQL と Tutorial D による関係代数式の表現例を示す。和（union）演算 R ∪ S は、R と S を、R の全ての組（タプル、行）と S の全ての組で構成される一つの関係を返す。この演算では、R と S が型適合であることが前提となる。重複する組は除去される。参考: 和集合関係 R と S が型適合であること。R UNION SR UNION S差（difference）演算 R − S は、R から、S に属する組を取り除いた関係を返す。この演算では、R と S が型適合であることが前提となる。参考: 差集合関係 R と S が型適合であること。R EXCEPT SR MINUS S交わり（交差、共通、積、intersection）演算 R ∩ S は、R と S の両方に属する組から関係を返す。この演算では、R と S が型適合であることが前提となる。交わり演算と等価な演算を、差演算を使って表現することができる。参考: 共通部分関係 R と S が型適合であること。R INTERSECT SR INTERSECT S直積（積、デカルト積、cartesian product）演算 R × S は、R と S の組の全ての組み合わせの関係（デカルト積）を返す。言い換えると、R がもつ全ての組が、S のもつ全ての組と、組み合わせられる。直積演算では、R と S が型適合である必要は無い。直積演算 R × S の組の数は、R の組の数と S の組の数を、掛け算した数になる。直積演算 R × S の属性の数は、R の属性の数と S の属性の数を、足し算した数になる。参考: 直積集合任意の2つの関係 formula_4 と formula_5 について、直積は次のように定義される。SELECT * FROM R, S直接にはサポートされない。制限（restriction）は、選択（selection）ともいい、ある関係から、指定した条件に合う組の集合を関係として返す。どの条件式の要素も比較可能であり、比較演算子θを使って条件式が記述されていること。Rを関係とすると、制限は次のように定義される。formula_6 は次のような条件式である。なお、θは一般的な比較演算子 (<、≤、=、>、≥、<>) である。SELECT * FROM R WHERE A = 1R WHERE A = 1射影（projection）演算は、ある関係から属性を限定した関係を返す。射影演算は、Rを構成する属性集合から、いくつかの属性を抽出する。βを抽出する属性の集合とすると、射影は、π"(R)" もしくは R[β] と記述することができる。射影演算で指定された属性が、対象となる関係に含まれていること。Rを関係とし、Rは {A, …, A} として属性をもつとする。また、β ⊆ {A, …, A} とする (βはRの全属性の部分集合である属性の集合) 。t := (β) は、βを構成する属性集合だけからなる組を意味する。SELECT A, B FROM R 結合 (join) は、2つの関係から1つの関係を返す演算であり、直積演算と制限演算を組み合わせた演算に相当する。一般に、結合を直積演算と制限演算の組み合わせと考えると、この制限演算の制限条件は、A θ B の普通の属性比較が真となるという条件である（θは行おうとする結合演算に応じた比較演算子）。θ比較の比較演算子は、<、≤、=、>、≥、<> である。この一般化された結合演算の概念は、θ結合（シータ結合）とも呼ばれる。一般化された結合演算であるθ結合を具象化した演算として、この節で述べる等結合、自然結合、準結合（半結合）などがある。この他に外結合（外部結合）も考案されているが、外結合の妥当性については議論の対象となっており、後の節で説明する。関係formula_7 と関係formula_8 のθ結合は、次のように定義される。なお、θ比較式を expression とする。この定義を演繹すると次のように表現できる。等結合（equijoin）は、θ結合においてθ比較の比較演算子が「 = 」である結合演算である。関係Rと関係Sがあり、これらの関係内の属性集合A、Bについて A ∈ R、B ∈ S とすると、等結合は次のように定義される。自然結合（natural join）の結果として返される関係は、2つの関係に等結合を適用して返された関係から、内容の重複する余分な属性を射影により取り除いた関係である。自然結合では交換法則と結合法則が成り立つ。すなわち、formula_9 であり、formula_10 である。関係代数演算において、この交換法則と結合法則はクエリ最適化のために活用することができる。関係formula_7 と関係formula_8 の自然結合は次のように定義される。R NATURAL JOIN SR JOIN S準結合（半結合、semijoin）は、2つの関係を元にして自然結合を行って返された関係から、結合の元になった一方の関係にのみ存在する属性を射影で除去する演算である。関係formula_7 と関係formula_8 の準結合は、次のように定義される。商（division）演算 R ÷ S は、直積演算とは対称となる逆の演算と考えることができる。関係Rと関係Sがあり、formula_15 を R の属性集合、formula_16 を S の属性集合とする。formula_17 が成立する場合、次のようになる。formula_18formula_19関係Rがあり、R の属性として father、mother、child、age があるとする。さらに関係Sがあり、S の属性として child、age があるとする。S には Maria（4歳）と Sabine（2歳）のデータが存在する。R を S で商を求めると、一つの関係が結果として返される。この結果として返された関係は、Maria（4歳）と Sabine（2歳）を娘としてもつ夫婦のみで構成される関係である。商は、演繹して導き出される演算子であるため、関係代数の他の演算子を使って定義される。関係 R と S があり、formula_15 を R の属性集合、formula_16 を S の属性集合とし、formula_22 を次のとおりとする。formula_23このとき、商は次のとおり定義される。formula_24SQLでは、直接、商を求める機能は、提供されていない。商演算を行うには複雑な問い合わせを記述する必要がある。R DIVIDEBY S先述の8つの関係代数演算子よりも後の時期に考案された演算子を説明する。先の節と同様に各演算子について、データベース言語 (問い合わせ言語) SQL と Tutorial D による関係代数式の表現例を示す。属性名変更（rename）は、関係の属性の名前を変更する演算である。この演算子は次に述べるとおり重要である。属性名変更は次のように記述する。formula_25 もしくは R[old→new]属性名変更により返される組の集合を " t' " とすると、属性名変更は次のように定義される。formula_26SELECT A, B AS X, C FROM RR RENAME ( B AS X )拡張（extend）は、ある関係に何らかの式に基づいて算出される新たな属性が、追加された関係を返す演算である。関係Rについて、Rの属性Bがインチ単位で示されているとして、センチメートル単位の値を求める場合。SELECT A, B, (B * 2.54) AS X FROM REXPAND R ADD (B * 2.54 AS X) 多くの関係データベース管理システム（RDBMS、関係データベース）では次の5つの要約（summarize）の機能を使うことができる。関係Rについて、Rの属性AとAにおけるBの最大値を求める。SELECT A, MAX(B) AS X FROM R GROUP BY ASUMMARISE 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に対応づけられない組の集合から、構成される関係である。この例で R と S で共通の名前を持つ属性に関して S に共通する組が無い R の組については、左外結合で返される関係においては null の値が設定される。R で属性 A の値が 4 である組については、対応する S の組が無いため、左外結合で返される関係で、null が出現している。数学的には、左外結合は自然結合と集合和とで模擬実行できる。R LEFT OUTER JOIN S右外結合（右外部結合、右結合、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 が出現している。数学的には、右外結合は自然結合と集合和とで模擬実行できる。R RIGHT OUTER JOIN S完全外結合（完全外部結合、完全結合、単に外結合ともいう、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 が出現している。数学的には、完全外結合は左外結合と右外結合 (したがって自然結合と集合和) とで模擬実行できる。R FULL OUTER JOIN S関係代数と関係群に対する問い合わせの最適化について説明する。関係群に対する問い合わせは木構造として表現される。その木構造において、最適化の第一の目標は、関係代数式を、木構造内の部分木により与えられる部分関係代数式が生成する関係の平均的な大きさを、最適化前の関係代数式が生成する関係の平均的な大きさより小さくする、同等な関係代数式に変換することである。第二の目標は、一つの問い合わせ内において複数回出現する共通の部分関係代数式を同定することであり、また同時に複数の問い合わせが評価される際、それら全ての問い合わせにおいて複数回出現する共通の部分関係代数式を同定することである。第二の目標で複数回出現する共通の部分関係代数式を同定することにより、一度その部分関係代数式を計算すれば、その計算結果を同じ部分関係代数式が出現し評価する際に再利用すれば良く、問い合わせにおいて再度同じ部分関係代数式を計算する必要は無くなる。次に木構造のこうした変換における法則群を説明する。参考: クエリ最適化制限演算に関する法則は、問い合わせ最適化において大きな役割を果たす。制限演算は、演算対象の関係の組の数を大幅に減らす。そのため最適化においては、制限演算を問い合わせ木構造の葉の方向へ移動することで、部分関係代数式により生成される関係群の大きさを小さくすることができるであろう。先述の2つの法則を、制限演算の連なりを分割/結合するために使うことができる。いくつかの情況においては、制限演算を結合することは有効である。なぜなら制限演算子を2回使うのではなく1回で済むからである。別の情況においては、複合した制限演算を分割することが有効である。このときは、複合した制限演算を木構造内で移動できない場合に、個々の制限演算に分割することで、移動できるようになる。直積は評価に最もコストを要する演算である。入力の関係の濃度 (組の数) が formula_31 と formula_32 であった場合、直積演算の結果として返される関係の濃度は formula_33 となる。そのため直積演算を行う前に、演算対象の2つの関係の濃度をできるだけ小さくするよう、最善を尽くすことが重要である。直積演算の後に制限演算を行う場合、例えば σ(formula_34 × formula_35) を評価する場合、この最適化は効果的に行うことができる。結合の定義を考えると、最適化をとりわけ効果的に行うことができる。もし制限演算の後に直積演算が続くのであれば、他の制限の法則を使うことで、制限演算を問い合わせの木構造の高い位置から葉の方向へ押し下げるよう試みることができる。この場合制限条件式 formula_36 を、複合した制限演算を分割する法則群を使うことで、制限条件式 formula_37、formula_38、formula_39 へと分解する。すなわち formula_36 = formula_37 ∧ formula_38 ∧ formula_39 となる。そして formula_37 は関係 formula_34 の属性のみから構成され、formula_38 は関係 formula_35 の属性のみから構成され、formula_39 は formula_34 と formula_35 の両方の属性から構成されるようにする。formula_37、formula_38、formula_39 のいずれかが欠如している場合もある。以上の変換は次のように示される。次の3つの法則は、問い合わせの木構造において制限演算を集合演算 (差・和・交わり) よりも葉に近い方向に押し下げる。注意: 差演算もしくは交わり演算の場合は、木構造を変換することで、制限演算を演算対象の関係群のうちただ一つの関係に対して適用することが可能である。この適用による最適化が有効なのは、演算対象の関係群のうち一つが小さく、小さな関係を演算対象として使うことによる利益に対して、制限演算を行うことに伴うオーバーヘッドが大きい場合である。

出典:wikipedia