關係代數

關係代數

關係代數是一種抽象的查詢語言,用對關係的運算來表達查詢,作為研究關係數據語言的數學工具。關係代數的運算對象是關係,運算結果亦為關係。關係代數用到的運算符包括四類:集合運算符、專門的關係運算符、算術比較符和邏輯運算符比較運算符和邏輯運算符是用來輔助專門的關係運算符進行操作的,所以按照運算符的不同,主要將關係代數分為傳統的集合運算和專門的關係運算兩類。

關係代數分類

傳統的集合運算

傳統的集合運算是二目運算,包括並、交、差、廣義笛卡爾積四種運算。

⒈ 並(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}。

X Z
X Z
X Z
X Z
X Z
X Z
X Z
X Z

1. 選擇(Selection)

選擇又稱為限制(Restriction)。它是在關係R中選擇滿足給定條件的諸元組,記作:

σF(R) = {t|t∈R ∧ F(t)="真"}

其中F表示選擇條件,它是一個邏輯表達式,取邏輯值‘真’或‘假’。

邏輯表達式F的基本形式為:

X1 θ Y1 [ φ X2 θ Y2 ]

θ表示比較運算符,它可以是>、≥、<、≤、=或≠。X1、Y1等是屬性名或常量或簡單函式。屬性名也可以用它的序號來代替。φ表示邏輯運算符,它可以是フ、∧或∨。[ ]表示任選項,即[ ]中的部分可以要也可以不要,...表示上述格式可以重複下去。

因此選擇運算實際上是從關係R中選取使邏輯表達式F為真的元組。這是從行的角度進行的運算。

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) 逐一考察每個組,如果它的像集屬性值中包括目標數據集,則對應的結果屬性應屬於該除法運算結果集。

相關詞條

相關搜尋

熱門詞條

聯絡我們