⟖

: _這裡的關係代數不同於奧古斯都・德・摩根在 1860 年為代數邏輯提供的關係代數_

**關係代數**是一階邏輯的分支，是閉合於運算下的關係的集合。運算作用於一個或多個關係上來生成一個關係。關係代數是計算機科學的一部分。

在純數學中的關係代數是有關於數理邏輯和集合論的代數結構。

## 介紹

關係代數在 1970 年 E.F. Codd 發表數據的關係模型之前很少受到注意。Codd 曾是皮爾士選集編輯者 Arthur W. Burks 的博士研究生。Codd 提議這樣一種代數作為資料庫查詢語言的基礎。第一個基於 Codd 的代數的查詢語言是 ISBL，許多作者都認同這個先驅的工作展示了一個使 Codd 的想法成為有用語言的方式。商務系統 12 是追隨 ISBL 先例的短命工業級實力的關係 DBMS。在 1998 年 Chris Date 和 Hugh Darwen 提議了一種叫 **Tutorial D** 的語言，意圖用於教學關係資料庫理論，它的查詢語言也吸取了 ISBL 的想法。Rel 是 **Tutorial D** 的一個實現。即使 SQL 的查詢語言也鬆散的基於了關係代數，儘管 SQL 中的操作數（表）不完全是關係，很多有用的關於關係代數的理論在 SQL 對應者中不成立。

因為關係被解釋為某個謂詞的外延，關係代數的每個運算在謂詞演算中都有對應者。例如，自然連接是邏輯 AND（ $\land $ ）的對應者。如果關係 _R_ 和 _S_ 分別表示謂詞 _p1_ 和 _p2_ 的外延，則 _R_ 和 _S_ 的自然連接（_R_ $\bowtie $ _S_）是表示謂詞 _p1_ $\land $ _p2_ 的外延的關係。

認識到 Codd 的代數事實上關於一階邏輯不完備是很重要的。實現它會引起不可逾越的特定計算困難。為了克服這些困難，他限制操作數為有限關係，並提議了對否定（NOT）和析取（OR）的有限支持。類似的限制在很多其他基於邏輯的計算機語言中也能見到。Codd 定義術語**關係完備性**來稱呼一個語言除了他提議的限制之外關於一階邏輯是完備的。在實踐中這些限制對他的關係代數用於資料庫用途的適用性沒有不利作用。

## 原始運算

如同任何代數，一些運算是原始的，而可以通過原始運算來定義的另一些運算是導出的。儘管邏輯中的 AND, OR 和 NOT 的選取，某種程度上是任意性的是眾所周知的，Codd 對他的代數作了類似的任意選取。

Codd 的代數的六個原始運算是「選擇」、「投影」、笛卡爾積（也叫做「叉積」或「交叉連接」）、併集、差集和「重命名」。（實際上，Codd 忽略了重命名，而 ISBL 的發明者顯式地包括了它）。這六個運算在省略其中任何一個都要損失表達能力的意義上是基本的。已經依據這六個原始運算定義了很多其他運算。其中最重要的是交集、除法和自然連接。事實上 ISBL 顯著的用自然連接替代了笛卡爾積，它是笛卡爾積的退化情況。

總之，關係代數的運算有與域關係演算或元組關係演算同樣的表達能力。但是出於前面介紹中給出的原因，關係代數有嚴格弱於沒有函數符號的一階謂詞演算的表達能力。關係代數實際上對應於一階邏輯的子集，即沒有遞歸和否定的 Horn 子句。

### 集合運算

儘管六個基本運算中有三個取自集合論，在它們的關係代數對應者中存在額外的約束：對於併集和差集，涉及到的兩個關係必須是「併集相容」的 — 就是說，兩個關係必須有同樣的屬性集合。因為交集可以用差集來定義，交集所涉及的兩個關係也必須是併集相容的。

笛卡爾積定義得與集合論有所不同，這裡的元組是平坦的、無子元組的。就是說，不同於集合論，那裡的 _n_ 元組和 _m_ 元組的笛卡爾積是 2 元組，而關係代數中它們的笛卡爾積把這個 2 元組展平為 _n_+_m_ 元組。更形式的說，_R_ × _S_ 被定義為：

　
: _R_ $\times $ _S_ = {_r_ $\cup $ _s_| _r_ $\in $ _R_, _s_ $\in $ _S_}

此外，對於要定義的笛卡爾積，涉及的兩個關係必須有不相交表頭 — 就是說，它們一定不能有公共屬性名字。

### 投影 (π)

**投影**是寫為 $\pi _{a_{1},...,a_{n}}(R)$ 的一元運算，這裡的 $a_{1},...,a_{n}$ 是屬性名字的集合。這種投影的結果定義為當所有在 $R$ 中的元組被限制為集合 $\{a_{1},...,a_{n}\}$ 的時候所獲得的集合。

### 選擇 (σ)

**廣義選擇**是寫為 $\sigma _{\varphi }(R)$ 的一元運算，這裡的 $\varphi $ 是由正常選擇中所允許的原子和邏輯算子 $\land $ （與）、 $\lor $ (或) 和 $\lnot $ （非）構成的命題公式。這種選擇選出 $R$ 中使 $\varphi $ 成立的所有元組。

### 重命名 (ρ)

**重命名**是寫為 $\rho _{a/b}(R)$ 的一元運算，這裡的結果同一於 $R$ ，除了在所有元組中的 $b$ 欄位被重命名為 $a$ 欄位之外。它被簡單的用來重命名關係的屬性或關係自身。

## 連接和類似連接的運算

### 自然連接 (⋈)

自然連接是寫為 (_R_ ⋈ _S_) 的二元運算，這裡的 _R_ 和 _S_ 是關係。自然連接的結果是在 _R_ 和 _S_ 中的在它們的公共屬性名字上相等的所有元組的組合。例如下面是表格「雇員」和「部門」和它們的自然連接：

連接是關係複合的另一種術語；在範疇論中連接精確的是纖維積。

自然連接被確證為最重要的算法之一，因為它是邏輯 AND 的關係對應者。仔細注意如果同一個變量在用 AND 連結的兩個謂詞中出現，則這個變量表示相同的事物而兩個出現必須總是由同一個值來代換。特別是，自然連接允許組合有外鍵關聯的關係。例如，在上述例子中，外鍵成立於從_雇員_._DeptName_ 到_部門_._DeptName_，_雇員_和_部門_的自然連接組合了所有雇員和它們的部門。注意這能工作因為外鍵在相同名字的屬性之間保持。如果不是這樣，外鍵成立於從_部門_._manager_ 到 _Emp_._emp-number_，則我們必須在採用自然連接之前必須重命名這些列。這種自然連接有時叫做**相等連接**（參見 θ- 連接）。

更形式的說，自然連接的語義定義為：

　
: _R_ $\bowtie $ _S_ = { _t_ $\cup $ _s_ : _t_ $\in $ _R_, _s_ $\in $ _S_, fun (_t_ $\cup $ _s_) }

這裡的 fun (_r_) 是對於二元關係 _r_ 為真的謂詞，若且唯若 _r_ 是函數二元關係。通常要求 _R_ 和 _S_ 必須至少有一個公共屬性，但是如果省略了這個約束則在那種特殊情況下自然連接就完全變成上面定義的笛卡爾積。

自然連接可以用 Codd 的原始運算模擬如下。假定 _b1,...,bm_ 是公共於 _R_ 和 _S_ 的公共屬性名字，_a1,...,an_ 是唯一於 _R_ 的屬性名字而 _c1,...,ck_ 是唯一於 _S_ 的屬性名字。進一步假定屬性名字 _d1,...,dm_ 不在 _R_ 和 _S_ 二者中。第一步我們可以重命名 _S_ 中的公共屬性名字：: _S'_ := ρd1/_b1_(...ρdm/_bm_(
_S_)...)，接著我們採用笛卡爾積並選擇要連接的元組：: _T_ := σb1=_d1_(...σbm=_dm_(_R_ × _S')...)_ ，最後我們採用一個投影來去掉重命名的屬性：: _U_ := πa1,...,an,b1,...,bm,c1,...,ck(_T_)
。

### θ- 連接和相等連接

考慮分別列出車模和船模的價格的表「車」和「船」。假設一個顧客要購買一個車模和一個船模，但不想為船花費比車更多的錢。在關係上的 θ- 連接 _CarPrice_ ≥ _BoatPrice_ 生成所有可能選項的一個表。

如果我們要組合來自兩個關係的元組，而組合條件不是簡單的共享屬性上的相等，則有一種更一般形式的連接算子才方便，這就是 θ- 連接（或 theta - 連接）。θ- 連接是寫為 ${\begin{matrix}R\ \bowtie \ S\\a\ \theta \ b\end{matrix}}$ 或 ${\begin{matrix}R\ \bowtie \ S\\a\ \theta \ v\end{matrix}}$ 的二元算子，這裡的 _a_ 和 _b_ 是屬性名字，θ 是在集合 {<, ≤, =,>, ≥} 中的二元關係，_v_ 是值常量，而 _R_ 和 _S_ 是關係。這個運算的結果由在 _R_ 和 _S_ 中滿足關係 θ 的元素的所有組合構成。只有 _S_ 和 _R_ 的表頭是不相交的，即不包含公共屬性的情況下，θ- 連接的結果才是有定義的。

這個運算可以用基本運算模擬如下：

　
: _R_ $\bowtie $ θ _S_ = σθ(_R_ × _S_)

在算子 θ 是等號算子 (=) 的時候這個連接也**相等連接**。

但是要注意，支持自然連接和重命名的計算機語言可以不需要 θ- 連接，因為它可以通過對自然連接（在沒有公共屬性的時候的它退化為笛卡爾積）的選擇來完成。

### 半連接 (⋉)(⋊)

半連接是類似於自然連接的寫為 _R_ ⋉ _S_ 的連接，這裡的 _R_ 和 _S_ 是關係。半連接的結果只是在 _S_ 中有在公共屬性名字上相等的元組所有的 _R_ 中的元組。例如下面的例子是「雇員」和「部門」和它們的半連接的表：

更形式的說半連接的語義定義如下：

　
: _R_ $\ltimes $ _S_ = { _t_ : _t_ $\in $ _R_, _s_ $\in $ _S_, fun (_t_ $\cup $ _s_) }

這裡的 fun (_r_) 定義同於自然連接。

半連接可以被使用自然連接模擬如下。假定 _a1,...,an_ 是 _R_ 的屬性名字，則：

　
: _R_ $\ltimes $ _S_ = $\Pi $ a1,..,_an_（_R_ $\bowtie $ _S_）

因為我們可以通過基本運算模擬自然連接因此也就可以模擬半連接。

### 反連接 (▷)

反連接是類似於自然連接的寫為 _R_ ▷ _S_ 的連接，這裡的 _R_ 和 _S_ 是關係。反連接的結果是在 _S_ 中沒有在公共屬性名字上相等的元組的 _R_ 中的那些元組。

例如「雇員」和「部門」和它們的反連接的表：

反連接形式定義為：

　
: _R_ $\triangleright $ _S_ = { _t_ : _t_ $\in $ _R_ $\land $ $\neg \exists $ _s_ $\in $ _S_ : fun (_t_ $\cup $ _s_) }

或

　
: _R_ $\triangleright $ _S_ = { _t_ : _t_ $\in $ _R_，_S_ 中沒有 _s_ 滿足 fun (_t_ $\cup $ _s_) }

這裡的 fun (_r_) 定義同於自然連接。

反連接還可以定義為半連接的補集：

　
: _R_ $\triangleright $ _S_ = _R_ - _R_ $\ltimes $ _S_

為此反連接有時叫做反半連接，反連接算子有時寫為其上有橫槓的半連接符號。

## 除法 (÷)

除法是寫為 _R_ ÷ _S_ 的二元關係。其結果由 _R_ 中元組到唯一於 _R_ 的屬性名字（就是說只在 _R_ 表頭中而不在 _S_ 表頭中的屬性）的限制構成，並且它們與 _S_ 中的元組的所有組合都存在於 _R_ 中。例如下面的「完成」和「DB 項目」和它們的除法：

如果「DB 項目」包含資料庫項目的所有任務，則這個除法的結果精確的包含已經完成了資料庫項目的所有學生。

更形式的說除法的語義定義如下：

　
: _R_ ÷ _S_ = { _t_[_a1,...,an_] : t $\in $ _R_ $\wedge $ $\forall $ _s_ $\in $ _S_ ( (_t_[_a1,...,an_] $\cup $ _s_) $\in $ _R_) }

這裡的 {_a1,...,an_} 是唯一於 _R_ 的屬性名字的集合而 _t_[_a1,...,an_] 是 _t_ 到這個集合的限制。通常要求在 _S_ 的表頭中的屬性名字是 _R_ 的表頭的屬性名字的子集，否則運算的結果永遠為空。

除法可以用基本運算模擬如下。我們假定 _a1,...,an_ 是唯一於 _R_ 的屬性名字而 _b1,...,bm_ 是 _S_ 的屬性名字。在第一步中我們投影 _R_ 於它的唯一屬性上，並接著構造它們與 _S_ 的元組的所有組合：

　
: _T_ := πa1,...,an(_R_) × _S_

在上面例子中，T 將是表示所有學生（因為 Student 是「完成」表的唯一鍵 / 屬性）與所有給定任務的組合的表。所以 Eugene 在 T 中將有兩行 Eugene -> Database1 和 Eugene -> Database2。

在下個步驟中，我們從這個關係中減去 _R_:

　
: _U_ := _T_ - _R_

注意在 _U_ 的都是 _R_ 中沒有出現的可能的組合。所以如果現在做到唯一於 _R_ 的屬性名字的投影，則我們有了 _R_ 中元組的限制，它們與 _S_ 的元組的所有組合都未出現在 _R_ 中：

　
: _V_ := πa1,...,an(_U_)

剩下的就是投影 _R_ 到唯一於它的屬性名字並減去 _V_:

　
: _W_ := πa1,...,an(_R_) - _V_

## 外連接

儘管連接（或內連接）的結果是由組合兩個操作數的匹配元組而形成的元組組成，外連接由這些元組加上通過向一個操作數的未匹配元組擴展上另一個操作數的每個屬性的「填充」值而形成的元組組成。

本節定義的運算假定「空」值 _ω_ 的存在性，我們不定義它並把它用做填充值。不應當假定它為資料庫語言 SQL 所定義的 NULL，也不應該假定 _ω_ 為一個標號而非一個值，也不應該假定它介入了有爭議的三值邏輯。

定義三個外連接：左外連接、右外連接和全外連接。（有時省略「外」字）

### 左外連接 (⟕)

左外連接寫成 _R_ ⟕ _S_，其中 _R_ 與 _S_ 為關係。左外連接的結果包含 _R_ 中所有元組，對每個元組，若在 _S_ 中有在公共屬性名字上相等的元組，則正常連接，若在 _S_ 中沒有在公共屬性名字上相等的元組，則依舊保留此元組，並將對應其他列設為 NULL。

　
: $(R\bowtie S)\cup ((R-\pi _{r_{1},r_{2},\dots ,r_{n}}(R\bowtie S))\times \{(\omega ,\dots \omega )\})$

### 右外連接 (⟖)

右外連接寫成 _R_ ⟖ _S_，其中 _R_ 與 _S_ 為關係。右外連接的結果包含 _S_ 中所有元組，對每個元組，若在 _R_ 中有在公共屬性名字上相等的元組，則正常連接，若在 _R_ 中沒有在公共屬性名字上相等的元組，則依舊保留此元組，並將對應其他列設為 NULL。

　
: $(R\bowtie S)\cup ((S-\pi _{s_{1},s_{2},\dots ,s_{n}}(R\bowtie S))\times \{(\omega ,\dots ,\omega )\})$

### 全外連接 (⟗)

全外連接寫成 _R_ ⟗ _S_，其中 _R_ 與 _S_ 為關係。全外連接的結果包含 _R_ 與 _S_ 中所有元組，對每個元組，若在另一關係上中有在公共屬性名字上相等的元組，則正常連接，若在另一關係上中沒有在公共屬性名字上相等的元組，則依舊保留此元組，並將對應其他列設為 NULL。

　
: _R_ ⟗ _S_ = (_R_ ⟕ _S_) ∪ (_R_ ⟖ _S_)

## 域計算的運算

### 聚集運算

多數資料庫包括五個聚集函數。這些運算是 Sum、Count、Average、Maximum 和 Minimum。在關係代數中被寫為 Exp1,Exp2,Exp3...Gfunc1,func2,func3...（關係）。必須指定要用的函數，而表達式是可選的。假定有一個叫 Account 的表有兩列，分別是 Branch\_Name 和 Balance，並希望找到有最高結餘的分部的名字，我們可以寫 Branch\_NameGMax(Balance)（Account）。要找到最高餘額我們可以簡單的寫 GMax(Balance)（Account）。

## 關係代數的限制

儘管關係代數對於大多數用途都足夠強大了，有一些在關係上的簡單而自然的運算不能用關係代數表達。二元關係的傳遞閉包就是其中之一。給定一個域 _D_，設二元關係 _R_ 是 _D_x_D_ 的子集。_R_ 的傳遞閉包 _R+_ 是包含 _R_ 的滿足如下條件的 _D_x_D_ 的子集：

　
: $\forall $ x $\forall $ y $\exists $ z((x,y) $\in $ R $\wedge $ (y,z) $\in $ R $\Rightarrow $ (x,z) $\in $ R)

可以證明沒有關係代數表達式 _E_(_R_) 接受 _R_ 作為變量參數而生成 _R_+。證明基於如下事實，給定一個關係表達式 _E_，對它聲稱 _E_(_R_) = _R_+，這裡的 _R_ 是變量，我們總是可以找到 _R_ 的一個實例_**r**_(和一個對應的域 **d**) 使得 _E_(_**r**_) ≠ _**r**_+。

## 有用於查詢優化的代數性質

查詢可以表示為一個樹，這裡的

* 內部節點是算子，
* 葉子是關係，
* 子樹是子表達式

主要目標是把表達式樹變換成等價的表達式樹，使得在樹中的子表達式生成的關係的平均大小比優化前更小。次要目標是在一個單一查詢中，或在要同時求值多於一個查詢的時候的所有這些查詢中，嘗試形成公共子表達式。在次要目標背後的原理是計算公共子表達式一次就夠了，其結果可以用於包含這個子表達式的所有查詢中。

我們提出可用於這種變換的一組規則。

### 選擇

關於選擇運算的規則在查詢優化中扮演了最重要的角色。選擇是可非常有效的減少在它的操作數中的行數的運算，所以如果我們設法把在表達式樹中選擇向著葉子方向移動，（子表達式產生的）內部關係的大小將被縮小。

#### 基本選擇性質

選擇是冪等性的（多次應用同一個選擇有同樣效果），和交換性的（應用選擇的次序在最終結果中沒有影響）。

 1. $\sigma _{A}(R)=\sigma _{A}\sigma _{A}(R)\,\!$
2. $\sigma _{A}\sigma _{B}(R)=\sigma _{B}\sigma _{A}(R)\,\!$

#### 分解有複雜條件的選擇

其條件是更簡單條件的合取的選擇等價於針對這些單獨條件的一序列選擇，而其條件是析取的選擇等價於選擇的併集。可以使用這些恆等式來合併多個選擇為更少的需要求值的選擇，或分解它們使得其成員選擇可以被移動或單獨優化。

 1. $\sigma _{A\land B}(R)=\sigma _{A}(\sigma _{B}(R))=\sigma _{B}(\sigma _{A}(R))$
2. $\sigma _{A\lor B}(R)=\sigma _{A}(R)\cup \sigma _{B}(R)$

#### 選擇和叉積

叉積對於計算是最耗費的算子。如果輸入關係有 $N$ 和 $M$ 行，結果將包含 $NM$ 行。所以在應用叉積算子之前盡最大可能減少兩個操作數的大小是非常重要的。

這可以有效的完成，如果叉積跟隨著選擇算子，比如 $\sigma _{A}$ ( $R$ × $P$ )。這是最合適考慮連接定義的情況。如果叉積不跟隨著選擇運算，我們可以嘗試使用其他規則從表達式樹更高層壓下一個選擇。

在上節情況下我們使用對複雜條件的分解規則把條件 $A$ 分解為條件 $B$ 、 $C$ 和 $D$ ，使得 $A$ = $B$ $\wedge $ $C$ $\wedge $ $D$ ，而 $B$ 只包含來自 $R$ 的屬性， $C$ 只包含來自 $P$ 的屬性， $D$ 包含 $A$ 的包含來自 $R$ 和 $P$ 二者的屬性的那些部分。注意 $B$ 、 $C$ 或 $D$ 可能為空，則下列規則成立：

　
: $\sigma _{A}(R\times P)=\sigma _{B\wedge C\wedge D}(R\times P)=\sigma _{D}(\sigma _{B}(R)\times \sigma _{C}(P))$

#### 選擇和集合運算

選擇在差集、交集和併集算子上是分配性的。使用下列三個規則在表達式樹中把壓入下面的集合運算中。注意，在差集和交集算子的情況下有可能在變換之後只把選擇算子應用於某一個操作數。在如下情況下這是有意義的，操作數之一很小，而計算選擇的花費超過了使用更小關係作為操作數的利益。

 1. $\sigma _{A}(R\setminus P)=\sigma _{A}(R)\setminus \sigma _{A}(P)=\sigma _{A}(R)\setminus P$
2. $\sigma _{A}(R\cup P)=\sigma _{A}(R)\cup \sigma _{A}(P)$
3. $\sigma _{A}(R\cap P)=\sigma _{A}(R)\cap \sigma _{A}(P)=\sigma _{A}(R)\cap P=R\cap \sigma _{A}(P)$

#### 選擇和投影

選擇與投影是交換性的，若且唯若在選擇條件中引用的欄位是在投影中的欄位的子集。在投影之前進行選擇可能有用，如果操作數是叉積或連接。在其他情況下，如果選擇條件計算相對破費，把選擇從投影中移動出來可能減少要測試的元組的數目（因為投影可能產生更少的元組，因為它清除由於取消欄位導致的重複元組）。

　
: $\pi _{a_{1},...,a_{n}}(\sigma _{A}(R))=\sigma _{A}(\pi _{a_{1},...,a_{n}}(R))$ 這裡的 $A\,$ 中的欄位 $\subseteq \{a_{1},...,a_{n}\}$

### 投影

#### 基本投影性質

投影是冪等性的，所以一系列（有效）投影等價於最外投影。

　
: $\pi _{a_{1},...,a_{n}}(\pi _{b_{1},...,b_{m}}(R))=\pi _{a_{1},...,a_{n}}(R)$ 這裡的 $\{a_{1},...,a_{n}\}\subseteq \{b_{1},...,b_{m}\}$

#### 投影和集合運算

投影在併集上是分配性的。

 1. $\pi _{a_{1},...,a_{n}}(R\cup P)=\pi _{a_{1},...,a_{n}}(R)\cup \pi _{a_{1},...,a_{n}}(P)$

### 重命名

#### 基本重命名性質

對一個變量的連續的重命名可以縮減為一個單一的重命名。沒有公共變量的重命名運算可以任意相互重新排序，這可以導致能縮減的重命名毗連起來。

 1. $\rho _{a/b}(\rho _{b/c}(R))=\rho _{a/c}(R)\,\!$
2. $\rho _{a/b}(\rho _{c/d}(R))=\rho _{c/d}(\rho _{a/b}(R))\,\!$

#### 重命名和集合運算

重命名關於差集、併集和交集是分配性的。

 1. $\rho _{a/b}(R\setminus P)=\rho _{a/b}(R)\setminus \rho _{a/b}(P)$
2. $\rho _{a/b}(R\cup P)=\rho _{a/b}(R)\cup \rho _{a/b}(P)$
3. $\rho _{a/b}(R\cap P)=\rho _{a/b}(R)\cap \rho _{a/b}(P)$

## 引用

## 外部連結

* LEAP - An implementation of the relational algebra （頁面存檔備份，存於網際網路檔案館）
* Query Optimization This paper is an excellent introduction into the use of the relational algebra in optimizing queries, and includes numerous citations for more in-depth study.

## 參見