3.1 關系代數及其運算

關系代數是一種抽象的查詢語言，是關系數據操作語言的一種傳統表達方式，它是用關系的運算來表達查詢的。

關系數據庫的數據操作分為查詢和更新兩類。查詢用于各種檢索操作，更新用于插入、刪除和修改等操作。關系操作的特點是集合操作方式，即操作的對象和結構都是集合。關系模型中常用的關系操作包括選擇（SELECT）、投影（PROJECT）、連接（JOIN）、除（DIVIDE）、并（UNION）、交（INTERSECTION）、差（DIFFERENCE）等。

早期的關系操作能力通常用代數方式或邏輯方式來表示，關系查詢語言根據其理論基礎的不同分成兩大類。

1）關系代數語言：用關系的運算來表達查詢要求的方式，查詢操作是以集合操作為基礎運算的DML語言。

2）關系演算語言：用謂詞來表達查詢要求的方式，查詢操作是以謂詞演算為基礎運算的DML語言。關系演算又可按謂詞變元的基本對象是元組變量還是域變量分為元組關系演算和域關系演算。

關系代數、元組關系演算和域關系演算三種語言在表達能力方面是完全等價的。

由于關系代數是建立在集合代數的基礎上，下面先定義幾個關系術語中的數學定義。

3.1.1 關系的數學定義

1．域（Domain）

域是一組具有相同數據類型值的集合。在關系模型中，使用域來表示實體屬性的取值范圍，通常用D_i表示某個域。

例如，自然數、整數、實數、一個字符串、{男，女}，大于10小于等于90的正整數等都可以是域。

2．笛卡兒積（Cartesian Product）

給定一組域D_l，D₂，…，D_n，這些域中可以有相同的，則D_l，D₂，…，D_n的笛卡兒積為：

D_l×D₂×…×D_n={（d₁，d₂，…，d_n）|d_i∈D_j，j=1，2，…，n}

其中每一個元素（d₁，d₂，…，d_n）叫作一個n元組或簡稱元組，元素中的每一個值d_i叫作一個分量。若D_i（i=1，2，…，n）為有限集，其基數（基數是指一個域中可以取值的個數。）為m_i（i=1，2，…，n），則D_l×D₂×…×D_n的基數為：

笛卡兒積可以表示成一個二維表，表中的每行對應一個元組，表中的每列對應一個域。例如，給出3個域：

姓名集合：D₁={史丹妮，周冬元，李曉輝}

性別集合：D₂={男，女}

專業集合：D₃={會計，商務}

D₁×D₂×D₃={（史丹妮，男，會計），（史丹妮，男，商務），（史丹妮，女，會計），（史丹妮，女，商務），（周冬元，男，會計），（周冬元，男，商務），（周冬元，女，會計），（周冬元，女，商務），（李曉輝，男，會計），（李曉輝，男，商務），（李曉輝，女，會計），（李曉輝，女，商務）}，這12個元組可列成一張二維表，如表3-1所示。

3．關系（Relation）

D_l×D₂×…×D_n的子集叫作在域D_l，D₂，…，D_n上的關系，表示為R（D_l，D₂，…，D_n）。

這里R表示關系的名字，n是關系屬性的個數，稱為目數或度數（Degree）；

當n=1時，稱該關系為單目關系（Unary relation）；

當n=2時，稱該關系為二目關系（Binary relation）。

關系是笛卡兒積的有限子集，所以關系也是一個二維表。

例如，可以在表3-1的笛卡兒積中取出一個子集來構造一個學生關系。由于一個學生只有一個專業和性別，所以笛卡兒積中的許多元組在實際中是無意義的，僅僅挑出有實際意義的元組構建一個關系，該關系名為Student，字段名取域名：姓名、性別和專業，如表3-2所示。

3.1.2 關系代數概述

關系代數是一種抽象的查詢語言，是關系數據操縱語言的一種傳統表達方式，它是用對關系的運算來表達查詢的。任何一種運算都是將一定的運算符作用于一定的運算對象上，得到預期的運算結果，所以運算對象、運算符、運算結果是運算的三大要素。

關系代數的運算對象是關系，運算結果亦為關系。

關系代數中使用的運算符包括4類：集合運算符、專門的關系運算符、比較運算符和邏輯運算符，如表3-3所示。

關系代數的運算按運算符的不同可分為傳統的集合運算和專門的關系運算兩類。

傳統的集合運算將關系看成元組的集合，其運算是從關系的“水平”方向即行的角度進行的。

專門的關系運算不僅涉及行而且涉及列。比較運算符和邏輯運算符是用來輔助專門的關系運算進行操作的。

3.1.3 傳統的集合運算

傳統的集合運算是二目運算，包括并、交、差、廣義笛卡兒積4種運算。

設關系R和關系S具有相同的目n（即兩個關系都具有n個屬性），且相應的屬性取自同一個域，則可以定義并、差、交、廣義笛卡兒積運算如下。

1．并（Union）

關系R與關系S的并記作：

R∪S={t|t∈R∨t∈S}，t是元組變量

其結果關系仍為n目關系，由屬于R或屬于S的元組組成。

2．差（Difference）

關系R與關系S的差記作：

R-S={t|t∈R∧t ?S}，t是元組變量

其結果關系仍為n目關系，由屬于R而不屬于S的所有元組組成。

3．交（Intersection）

關系R與關系S的交記作：

R∩S={t|t∈R∧t∈S}，t是元組變量

其結果關系仍為n目關系，由既屬于R又屬于S的元組組成。關系的交可以用差來表示，即R∩S=R-（R-S）

4．廣義笛卡兒積（Extended Cartesian Product）

兩個分別為n目和m目的關系R和S的廣義笛卡兒積是一個（n+m）列的元組的集合。元組的前n列是關系R的一個元組，后m列是關系S的一個元組。若R有k₁個元組，S有k₂個元組，則關系R和關系S的廣義笛卡兒積有k_l×k₂個元組。記作：R×S={t_r⌒∩t_s|T_r∈R∧T_s∈S}

假定現在有兩個關系R與S是關系模式學生的實例，R和S如表3-4所示。

【例3-1】關系R∪S的結果如表3-5所示。

【例3-2】關系R-S的結果如表3-6所示。

【例3-3】關系R∩S的結果如表3-7所示。

【例3-4】關系R與關系S做廣義笛卡爾積的結果如表3-8所示。

3.1.4 專門的關系運算

專門的關系運算包括選擇、投影、連接、除等。為了敘述上的方便，先引入幾個符號。

1）設關系模式為R（A₁，A₂，…，A_n），它的一個關系設為R，t∈R表示t是R的一個元組，t[A_i]表示元組t中相應于屬性A_i上的一個分量。

2）若A={A_i1，A_i2，…，A_ik}，其中A_i1，A_i2，…，A_ik是A₁，A₂，…，A_n中的一部分，則A稱為字段名或域列。t[A]=（t[A_i1]，t[A_i2]，…，t[A_ik]）表示元組t在字段名A上諸分量的集合。A表示{A₁，A₂，…，An）中去掉{A_i1，A_i2，…，A_ik}后剩余的屬性組。

3）R為n目關系，S為m目關系。t_r∈R，t_s∈S，t_r⌒t_s稱為元組的連接，它是一個n+m列的元組，前n個分量為R中的一個n元組，后m個分量為S中的一個m元組。

4）給定一個關系R（X，Z），X和Z為屬性組。定義當t[X]=x時，x在R中的象集為：

Zx={t[Z]|t∈R，t[X]=x}

它表示R中屬性組X上值為x的諸元組在Z上分量的集合。

下面給出這些關系運算的定義。

1．選擇（Selection）

選擇又稱為限制（Restriction），它是在關系R中選擇滿足給定條件的諸元組，記作：σ_F（R）={t|t∈R∧F（t）=‘真’}

其中，F表示選擇條件，它是一個邏輯表達式，取邏輯值“真”或“假”。邏輯表達式F的基本形式為：

X₁θY₁[ΦX₂θY₂…]

其中，θ表示比較運算符，它可以是＞、≥、＜、≤、=或≠；X1，Y1是字段名、常量或簡單函數，字段名也可以用它的序號（如1，2，…）來代替；Φ表示邏輯運算符，它可以是?（非）、∧（與）或∨（或）；[ ]表示任選項，即[ ]中的部分可要可不要；…表示上述格式可以重復下去。選擇運算實際上是從關系R中選取使邏輯表達式F為真的元組，這是從行的角度進行的運算。

設有一個學生-課程數據庫如表3-9所示，它包括以下內容。

學生關系Student（說明：Sno表示學號，Sname表示姓名，Ssex表示性別，Sage表示年齡，Sdept表示所在系）

課程關系Course（說明：Cno表示課程號，Cname表示課程名）

選修關系Score（說明：Sno表示學號，Cno表示課程號，Degree表示成績）

其關系模式如下。

【例3-5】查詢數學系學生的信息。

σ_{Sdept=′數學系′}（Student）或σ_{5=′數學系′}（Student）

結果如表3-10所示。

【例3-6】查詢年齡小于20歲的學生的信息。

σ_Sage＜20（Student）或σ_4＜20（Student）

結果如表3-11所示。

2．投影（Projection）

關系R上的投影是從R中選擇出若干字段名組成新的關系。記作：

π_A（R）={t[A]|t∈R}

其中A為R中的字段名。

投影操作是從列的角度進行的運算。投影之后不僅取消了原關系中的某些列，而且還可能取消某些元組。因為取消了某些字段名后，就可能出現重復行，應取消這些完全相同的行。

【例3-7】查詢學生的學號和姓名。

π_Sno,Sname（Student）或π_1,2（Student）

結果如表3-12所示。

【例3-8】查詢學生關系Student中都有哪些系，即查詢學生關系Student在所在系屬性上的投影。

π_Sdept（Student）或π₅（Student）

結果如表3-13所示。

3．連接（Join）

連接也稱為θ連接，它是從兩個關系的笛卡爾積中選取屬性間滿足一定條件的元組。記作：

其中A和B分別為R和S上度數相等且可比的屬性組。θ是比較運算符。連接運算從R和S的笛卡爾積R×S中選取R關系在A屬性組上的值與S關系在B屬性組上值滿足比較關系的θ元組。

連接運算中有兩類最為重要，也是最為常用連接運算。一種是等值連接（Equijoin），另一種是自然連接。

θ為“=”的連接運算稱為等值連接。它是從關系R與S的廣義笛卡爾積中選取A、B屬性值相等的那些元組，即等值連接為：

自然連接（Natural join）是一種特殊的等值連接。它要求兩個關系中進行比較的分量必須是相同的屬性組，并且在結果中把重復的字段名去掉。若R和S具有相同的屬性組B，則自然連接可記作

R??S{t_r⌒t_s|t_r∈R∧t_s∈S∧t_r[A]θt_s[B]}

一般的連接操作是從行的角度進行運算。但是自然連接還需要取消重復列，所以是同時從行和列的角度進行運算。

如果把舍棄的元組也保存在結果關系中，而在其他屬性上填空值Null，那么這種連接就叫作外連接（Outer join）。如果只把左邊關系R中要舍棄的元組保留就叫作左外連接（Left outer join或Left join），如果只把右邊關系S中要舍棄的元組保留就叫作右外連接（Right outer join或Right join）。

【例3-9】設關系R、S分別為表3-14中的（a）和（b），一般連接C＞D的結果如表3-15（a）所示，等值連接R. B=S. B的結果如表3-15（b）所示，自然連接的結果如表3-15（c）所示。

4．除運算（Division）

給定關系R（X，Y）和S（Y，Z），其中X，Y，Z為屬性組。R中的Y與S中的Y可以有不同的字段名，但必須出自相同的域集。R與S的除運算得到一個新的關系P（X），P是R中滿足下列條件的元組在X字段名上的投影：元組在X上分量值x的象集Y_x包含S在Y上投影的集合。

R÷S={t_r[X]t_r∈R∧π_Y（S）?Y_X}

其中Y_x為x在R中的象集，x=t_r[X]。

除操作是同時從行和列角度進行運算的。

關系除法運算分下面4步進行。

1）將被除關系的屬性分為象集屬性和結果屬性：與除關系相同的屬性屬于象集屬性，不相同的屬性屬于結果屬性。

2）在除關系中，對與被除關系相同的屬性（象集屬性）進行投影，得到除目標數據集。

3）將被除關系分組，原則是，結果屬性值一樣的元組分為一組。

4）逐一考察每個組，如果它的象集屬性值中包括除目標數據集，則對應的結果屬性值應屬于該除法運算結果集。

說明：象集的本質是一次選擇運算和一次投影運算。

例如關系模式R（X，Y），X和Y表示互為補集的兩個屬性集，對于遵循模式R的某個關系A，當t[X]=x時，x在A中的象集（Images Set）為：

Zx={t[Z]|t∈ A，t[X]=x}

它表示：A中X分量等于x的元組集合在屬性集Z上的投影，如表3-16所示。

a1在A中的象集為{（b1，c2），（b2，c3），（b2，c1）}。

【例3-10】設關系R，S分別如表3-17（a）、（b）所示，求R÷S的結果。

關系除的運算過程如下。

1）找出關系R和關系S中的相同屬性，即B屬性和C屬性。在關系S中對B屬性和C屬性做投影，所得的結果為{（b1，c2），（b2，c3），（b2，c1）}。

2）被除關系R中與S中不相同的屬性列是A，在關系R在屬性A上做取消重復值的投影為{a1，a2，a3，a4}。

3）求關系R中A屬性對應的象集對應的象集B和C，根據關系R的數據，可以得到A屬性各分量值的象集。

其中：

a1的象集為{（b1，c2），（b2，c3），（b2，c1）}；

a2的象集為{（b3，c5），（b2，c3）}；

a3的象集為{（b4，c4）}；

a4的象集為{（b6，c4）}。

4）判斷包含關系，對比可以發現：a2、a3和a3的象集都不能包含關系S中的B屬性和C屬性的所有值，所以排除掉a2、a3和a3；而a1的象集包括了關系S中B屬性和C屬性的所有值，所以R÷S的最終結果就是{a1}。

在關系代數中，關系代數運算經過有限次復合后形成的式子稱為關系代數表達式。對關系數據庫中數據的查詢操作可以寫成一個關系代數表達式，或者說，寫成一個關系代數表達式就表示已經完成了查詢操作。

【例3-11】假設有兩個關系：學生學習成績與課程成績，如表3-18所示，則學生學習成績與課程成績除運算的結果是滿足一定課程成績條件的學生的表，結果如表3-19所示。

【例3-12】設學生-課程數據庫中有3個關系：S、C和SC，三個關系的關系實例分別如表3-20所示。利用關系代數進行查詢。

學生關系：S（sno，sname，ssex，sage，sdept）

課程關系：C（cno，cname，teacher）

選修關系：SC（sno，cno，degree）

屬性sno、sname、ssex、sage和sdept分別表示學號、姓名、性別、年齡和所在系，sno為主碼，屬性cno、cname、Teacher分別表示課程號、課程名、授課教師，cno為主碼，屬性sno、cno、degree分別表示學號、課程號和成績，（sno，cno）屬性組為主碼。

1）查詢選修課程號為C3號課程的學生學號和成績。

π_Sno,Degree（σ_Cno=′C3′（SC））

2）查詢學習課程號為C4課程的學生學號和姓名。

π_Sno,Sname（σ_Cno=′C4′（S∞SC））

3）查詢選修課程名為數據結構的學生學號和姓名。

π_sno,sname（σ_{cname=′數據結構′}（S??SC??C））

4）查詢選修課程號為C1或C3課程的學生學號。

π_Sno（σ_{Cno=′C1′∨Cno=′C3′}（SC））

5）查詢不選修課程號為C2的學生的姓名和年齡。

π_{Sname,Sage（S）}-π_Sname,Sage（σ_Cno=′C2′（S??SC））

6）查詢年齡在18～23歲之間的女生的學號、姓名和年齡。

π_{sno,sname,sage}（σ_{sage＞=18∧sage＜=23∧ssex=′女′}（S））

7）查詢至少選修課程號為C1與C5的學生的學號。

π_sno（σ_{1=4∧3=′C1′∧5=′C5′}（SC×SC））

8）查詢選修全部課程的學生的學號。

π_sno,cno（SC）÷π_cno（C）

9）查詢全部學生都選修的課程的課程號。

π_sno,cno（SC）÷π_sno（S）

10）查詢選修課程包含學生李飛所學課程的學生的姓名。

π_sname（S??（π_sno,cno（SC）÷π_cno（σ_{sname=′李飛′}（S）??SC）））

11）查詢選修了操作系統或軟件工程的學生學號和姓名。

π_sno,sname（σ_{cname=′操作系統′∨cname=′軟件工程′}（C??SC??S））