關係代數 (資料庫)

這裡的關係代數不同於奧古斯都·德·摩根在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$ 是由正常選擇中所允許的原子和邏輯算子 $\and$ (與)、 $\or$ (或) 和 $\lnot$ (非)構成的命題公式。這種選擇選出 $R$ 中使 $\varphi$ 成立的所有元組。

重命名

主條目：重命名 (關係代數)

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

連接和類似連接的運算

自然連接

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

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

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

僱員 $\bowtie$ 部門
Name	EmpId	DeptName	Manager
Harry	3415	財務	George
Sally	2241	銷售	Harriet
George	3401	財務	George
Harriet	2202	銷售	Harriet

連接是關係複合的另一種術語；在範疇論中連接精確的是纖維積，在Unicode中，領結符號是 ⋈ (U+22C8)。

自然連接被確證為最重要的算子之一，因為它的邏輯 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' := ρ_d₁/b₁(...ρ_{d_m/b_m}( S)...)，接著我們採用笛卡爾積並選擇要連接的元組: : T := σ_b₁=d₁(...σ_{b_m=d_m}(R × S')...) ，最後我們採用一個投影來去掉重命名的屬性: : U := π_{a₁,...,a_n,b₁,...,b_m,c₁,...,c_k}(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 $\ltimes$ S 的連接，這裡的 R 和 S 是關係。半連接的結果只是在 S 中有在公共屬性名字上相等的元組所有的 R 中的元組。例如下面的例子是「僱員」和「部門」和它們的半連接的表:

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

部門
DeptName	Manager
銷售	Harriet
生產	Charles

僱員 $\ltimes$ 部門
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 =

Π

_{a₁,..,a_n}(R $\bowtie$ S)

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

反連接

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

例如「僱員」和「部門」和它們的反連接的表:

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

部門
DeptName	Manager
銷售	Harriet
生產	Charles

僱員 $\triangleright$ 部門
Name	EmpId	DeptName
Harry	3415	財務
George	3401	財務

反連接形式定義為:

R $\triangleright$ S = { t : t $\in$ R $\and$ $\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 := π_{a₁,...,a_n}(R) × S

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

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

U := T - R

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

V := π_{a₁,...,a_n}(U)

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

W := π_{a₁,...,a_n}(R) - V

外連接

主條目：外連接

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

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

定義三個外連接: 左外連接、右外連接和全外連接。(有時省略「外」字)

域計算的運算

聚集運算

多數資料庫包括五個聚集函數。這些運算是 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 $\exist$ 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)\,\!$
$\sigma_{A}\sigma_{B}(R)=\sigma_{B}\sigma_{A}(R)\,\!$

分解有複雜條件的選擇

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

$\sigma_{A \land B}(R)=\sigma_{A}(\sigma_{B}(R))=\sigma_{B}(\sigma_{A}(R))$
$\sigma_{A \lor B}(R)=\sigma_{A}(R)\cup\sigma_{B}(R)$

選擇和叉積

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

這可以有效的完成，如果叉積跟隨著選擇算子，比如 $σ 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))$

選擇和集合運算

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

$\sigma_{A}(R\setminus P)=\sigma_{A}(R)\setminus \sigma_{A}(P) =\sigma_{A}(R)\setminus P$
$\sigma_{A}(R\cup P)=\sigma_{A}(R)\cup\sigma_{A}(P)$
$\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\}$

投影和集合運算

投影在差集、並集和交集上是分配性的。

$\pi_{a_1, ..., a_n}(R \setminus P) = \pi_{a_1, ..., a_n}(R) \setminus \pi_{a_1, ..., a_n}(P)$
$\pi_{a_1, ..., a_n}(R \cup P) = \pi_{a_1, ..., a_n}(R) \cup \pi_{a_1, ..., a_n}(P)$
$\pi_{a_1, ..., a_n}(R \cap P) = \pi_{a_1, ..., a_n}(R) \cap \pi_{a_1, ..., a_n}(P)$

重命名

基本重命名性質

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

$\rho_{a / b}(\rho_{b / c}(R)) = \rho_{a / c}(R)\,\!$
$\rho_{a / b}(\rho_{c / d}(R)) = \rho_{c / d}(\rho_{a / b}(R))\,\!$

重命名和集合運算

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

$\rho_{a / b}(R \setminus P) = \rho_{a / b}(R) \setminus \rho_{a / b}(P)$
$\rho_{a / b}(R \cup P) = \rho_{a / b}(R) \cup \rho_{a / b}(P)$
$\rho_{a / b}(R \cap P) = \rho_{a / b}(R) \cap \rho_{a / b}(P)$

參見

資料庫管理系統（DBMS） ( 檢視 • 討論 • 編輯 • 歷史 )
概念資料庫 • 資料庫模型 • 資料庫儲存結構 • 關係模型 • 分散式資料庫 • ACID • NULL值關係資料庫 • 關係代數 • 關係演算 • 資料庫正規化 • 參照完整性 • 關係資料庫管理系統主鍵 • 外來鍵 • 代理主鍵 • 超鍵值 • 候選鍵
資料庫物件觸發程序 • 檢視表 • 資料表 • 指標 • 交易記錄檔 • 交易 • 資料庫索引預存程序 • 資料庫分割	SQL 分類：資料定義語言 • 資料操縱語言 • 資料控制語言指令：SELECT • INSERT • UPDATE • MERGE • DELETE • JOIN • UNION • CREATE • DROP • Begin work • COMMIT • ROLLBACK • TRUNCATE • ALTER 安全： SQL Injection • 參數化查詢
資料庫管理系統的實施
實施類型關聯式資料庫 • 檔案型資料庫 • Deductive • 維度化資料庫 • 階層式 • 對象資料庫 • 物件關聯式資料庫 • Temporal • XML資料庫
資料庫產品對象型 (對比) • 關係型 (對比)	資料庫成分查詢語言 • 查詢優化器 • 查詢計劃 • ODBC • JDBC • OLE DB

引用

^ Aho, Alfred V.; Jeffrey D. Ullman（1979）．“Universality of data retrieval languages”．Proceedings of the 6th ACM SIGACT-SIGPLAN symposium on Principles of programming languages：110-119．

外部連結

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.

Why are we here?
All text is available under the terms of the GNU Free Documentation License
This page is cache of Wikipedia. History