關係代數 (資料庫)

這裡的關係代數不同於奧古斯都·德·摩根在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中的在它們的公共屬性名字上相等的所有元組的組合。例如下面是表格「雇員」和「部門」和它們的自然連接：

雇員 Name EmpId DeptName Harry 3415 財務 Sally 2241 銷售 George 3401 財務 Harriet 2202 銷售

部門 DeptName Manager 財務 George 銷售 Harriet 生產 Charles

雇員⋈部門 Name EmpId DeptName Manager Harry 3415 財務 George Sally 2241 銷售 Harriet George 3401 財務 George Harriet 2202 銷售 Harriet

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

自然連接被確證為最重要的算法之一，因為它是邏輯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的原始運算模擬如下。假定b₁,...,b_m是公共於R和S的公共屬性名字，a₁,...,a_n是唯一於R的屬性名字而c₁,...,c_k是唯一於S的屬性名字。進一步假定屬性名字 d₁,...,d_m不在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生成所有可能選項的一個表。

車 CarModel CarPrice CarA 20'000 CarB 30'000 CarC 50'000

船 BoatModel BoatPrice Boat1 10'000 Boat2 40'000 Boat3 60'000

車$\bowtie$船$\scriptstyle CarPrice\geq BoatPrice$ CarModel CarPrice BoatModel BoatPrice CarA 20'000 Boat1 10'000 CarB 30'000 Boat1 10'000 CarC 50'000 Boat1 10'000 CarC 50'000 Boat2 40'000

如果我們要組合來自兩個關係的元組，而組合條件不是簡單的共享屬性上的相等，則有一種更一般形式的連接算子才方便，這就是θ-連接（或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中的元組。例如下面的例子是「雇員」和「部門」和它們的半連接的表：

雇員 Name EmpId DeptName Harry 3415 財務 Sally 2241 銷售 George 3401 財務 Harriet 2202 生產

部門 DeptName Manager 銷售 Harriet 生產 Charles

雇員⋉部門 Name EmpId DeptName Sally 2241 銷售 Harriet 2202 生產

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

R $\ltimes$ S = { t : t $\in$ R, s $\in$ S, fun (t $\cup$ s) }

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

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

R $\ltimes$ S = $\Pi$_a1,..,an（R$\bowtie$S）

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

反連接 (▷)

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

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

雇員 Name EmpId DeptName Harry 3415 財務 Sally 2241 銷售 George 3401 財務 Harriet 2202 生產

部門 DeptName Manager 銷售 Harriet 生產 Charles

雇員▷部門 Name EmpId DeptName Harry 3415 財務 George 3401 財務

反連接形式定義為：

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項目」和它們的除法：

完成 Student Task Fred Database1 Fred Database2 Fred Compiler1 Eugene Database1 Eugene Compiler1 Sara Database1 Sara Database2

DB項目 Task Database1 Database2

完成÷ DB項目 Student Fred Sara

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

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

R ÷ S = { t[a₁,...,a_n] : t $\in$ R $\wedge$ $\forall$s $\in$ S ( (t[a₁,...,a_n] $\cup$ s) $\in$ R) }

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

除法可以用基本運算模擬如下。我們假定a₁,...,a_n是唯一於R的屬性名字而 b₁,...,b_m是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...}G_{func1,func2,func3...}（關係）。必須指定要用的函數，而表達式是可選的。假定有一個叫Account的表有兩列，分別是Branch_Name和Balance，並希望找到有最高結餘的分部的名字，我們可以寫_{Branch_Name}G_Max(Balance)（Account）。要找到最高餘額我們可以簡單的寫G_Max(Balance)（Account）。

關係代數的限制

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

$\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.

參見

• 資料庫
• 關係模型