基本介紹
- 中文名：關係代數
- 外文名：relation algebra
關係代數分類,傳統的集合運算,專門的關係運算,
關係代數分類
傳統的集合運算
傳統的集合運算是二目運算，包括並、交、差、廣義笛卡爾積四種運算。
⒈ 並（Union）
設關係R和關係S具有相同的目n（即兩個關係都有n個屬性），且相應的屬性取自同一個域，則關係R與關係S的並由屬於R且屬於S的元組組成。其結果關係仍為n目關係。記作：
R∪S={t|t∈R∨t∈S}
⒉ 差（Difference）
設關係R和關係S具有相同的目n，且相應的屬性取自同一個域，則關係R與關係S的差由屬於R而不屬於S的所有元組組成。其結果關係仍為n目關係。記作：
R－S={t|t∈R∧t∉S}
⒊ 交（Intersection Referential integrity）
設關係R和關係S具有相同的目n，且相應的屬性取自同一個域，則關係R與關係S的交由既屬於R又屬於S的元組組成。其結果關係仍為n目關係。記作：
R∩S={t|t∈R∧t∈S}
⒋ 廣義笛卡爾積（Extended cartesian product）
這裡的笛卡爾積嚴格地講是廣義笛卡爾積(Extended Cartesian Product)。在不會出現混淆的情況下廣義笛卡爾積也稱為笛卡爾積。
兩個分別為n目和m目的關係R和S的廣義笛卡爾積是一個(n+m)列的元組的集合。元組的前n列是關係R的一個元組，後m列是關係S的一個元組。若R有k1個元組，S有k2個元組，則關係R和關係S的廣義笛卡爾積有k1×k2個元組。
記作：
R×S={(t_r t_s ) ?|t_r∈R?t_s∈S}
專門的關係運算
專門的關係運算(Specific relation operations)包括選擇、投影、連線、除等。
為了敘述上的方便，我們先引入幾個記號。
1. 設關係模式為R(A1, A2, …, An)。它的一個關係設為R。t∈R表示t是R的一個元組。t[Ai]則表示元組t中相應於屬性Ai的一個分量 。
2. 若A={Ai1, Ai2, …, Aik}，其中Ai1, Ai2, …, Aik是A1, A2, …, An中的一部分，則A稱為屬性列或域列。フA則表示{A1, A2, …, An}中去掉{Ai1, Ai2, …, Aik}後剩餘的屬性組。t[A]=(t[Ai1], t[Ai2], …, t[Aik])表示元組t在屬性列A上諸分量的集合。
3. R為n目關係，S為m目關係。設tr∈R(r為下標)，ts∈S(s為下標)，則trts(整個式子上方加一個半弧，r和s為下標) 稱為元組的連線（Concatenation）。它是一個(n+m)列的元組，前n個分量為R中的一個n元組，後m個分量為S中的一個m元組。
4. 給定一個關係R(X,Z)，X和Z為屬性組。我們定義，當t[X]=x時，x在R中的象集（Images Set）為：
Zx={t[Z]|t∈R, t[X]=x}
x在R中的像集為R中Z屬性對應分量的集合，而這些分量所對應的元組中的屬性組X上的值為x。
例如，圖中，x_1在R中的像集Z_(x_1 )={Z_1，Z_2，Z_3，Z_4}， x_2在R中的像集Z_(x_2 )={Z_2，Z_3}，x_3在R中的像集Z_(x_3 )={Z_1，Z_3}。
X1 | Z1 |
X1 | Z2 |
X1 | Z3 |
X1 | Z4 |
X2 | Z2 |
X2 | Z3 |
X3 | Z1 |
X3 | Z3 |
1. 選擇（Selection）
選擇又稱為限制（Restriction）。它是在關係R中選擇滿足給定條件的諸元組，記作：
σF(R) = {t|t∈R ∧ F(t)='真'}
其中F表示選擇條件，它是一個邏輯表達式，取邏輯值‘真’或‘假’。
邏輯表達式F的基本形式為：
X1 θ Y1 [ φ X2 θ Y2 ]
θ表示比較運算符，它可以是>、≥、<、≤、=或≠。X1、Y1等是屬性名或常量或簡單函式。屬性名也可以用它的序號來代替。φ表示邏輯運算符，它可以是フ、∧或∨。[ ]表示任選項，即[ ]中的部分可以要也可以不要，...表示上述格式可以重複下去。
2. 投影（Projection）
關係R上的投影是從R中選擇出若干屬性列組成新的關係。記作：
ΠA(R) = { t[A] | t∈R }
其中A為R中的屬性列。
3. 連線（Join）
連線運算從R和S的笛卡爾積R×S中選取（R關係）在A屬性組上的值與（S關係）在B屬性組上值滿足比較關係θ的元組。
連線運算中有兩種最為重要也最為常用的連線，一種是等值連線（equi-join），另一種是自然連線（Natural join）。
θ為“=”的連線運算稱為等值連線。它是從關係R與S的笛卡爾積中選取A、B屬性值相等的那些元組。
自然連線（Natural join）是一種特殊的等值連線，它要求兩個關係中進行比較的分量必須是相同的屬性組，並且要在結果中把重複的屬性去掉。
一般的連線操作是從行的角度進行運算。但自然連線還需要取消了重複列，所以是同時從行和列的角度進行運算。
4. 除（Division）
除法運算是一個複合的二目運算。如果把笛卡爾積看作“乘法”運算，則除法運算可以看作這個“乘法”的逆運算。
給定關係R(X，Y)和S(Y，Z)，其中X、Y、Z為屬性組。R中的Y與S中的Y可以有不同的屬性名，但必須出自相同的域集。R與S的除運算得到一個新的關係P(X)，P是R中滿足下列條件的元組在X屬性列上的投影：元組在X上的分量值x的像集YX包含S在Y上投影的集合。記作：
R÷S={t_r [X]|t_r∈R?π_r （S）?Y_x}
其中，Y_x為x在R中的像集，x=t_r [X]。顯然，除操作是同時從行和列的角度進行運算。
根據關係運算的除法定義，可以得出它的運算步驟。
(1) 將被除關係的屬性分為像集屬性和結果屬性兩部分；與除關係相同的屬性屬於像集屬性；不相同的屬性屬於結果屬性。
(2) 在除關係中，對像集屬性投影，得到除目標數據集。
(3) 將被除關係分組。分組原則是：結果屬性值一樣的元組分為一組。
(4) 逐一考察每個組，如果它的像集屬性值中包括目標數據集，則對應的結果屬性應屬於該除法運算結果集。
