除運算

除運算

除運算是一種非傳統的集合運算,是廣義笛卡兒積的逆運算。設有兩個關係R和關係S,其元數分別為n和m(n>m>0),則R和S進行除法的結果記為P=R÷S,其中P是一個元組數最大為n-m(有重複需去掉重複項)的關係且滿足以下性質:P中的每個元組u與R中每個元組v所組成的元組(v,u)不在關係S中。

由於除法定義採用的是逆運算定義,通常逆運算的進行需要有相關條件保證運算的可施行性和非平凡性。實際上,關係R能被關係S除的充分必要條件是:

R中應有應有某些屬性不出現在S中。

基本信息

定義

除運算 除運算

給定關係R(X,Y)和S(Y,Z),其中X、Y、Z是屬性組,做除運算的前提是兩個關係具有相同的屬性或屬性組。可 以看出關係R和關係S的相同屬性組是Y。R中的Y與S中的可以有不同的屬性名,但必須出自相同的域集(相同的數據類型)。

以下根據像集來定義:關係R除以關係S是一個新關係P(X),P是R中滿足下列條件的元組:在X上分量值x的像集Yx包含S在Y上投影的集合。其中Yx為值x在R中的像集,有x=tr[x]。

R與S的除運算為:R÷S={t[X]|t∈RΛΠ(S)⊆Y}

運算的結果是為了找出來t[x],t∈表示t的條件是它本身屬於R,π(S)表示而且tr屬於S關係對於Y屬性組的投影,⊆Y表示還要包含於分量值x的像集Yx。x=t[x]表示運算後發現要找出來的關係組就是在X上的分量值x。

除操作是同時從行和列角度進行運算。 在進行除運算時,將被除關係R的屬性分成兩部分:與除關係相同的部分Y和不同的部分X。在被除關係中按X分組,即相同的X值的元組分為一組。出發的運算是求包括除關係中全部Y值的組,這些族中的X將做為除結果的元組。

像集

當t[X]=x時,x在R中的象集(Images Set)為:

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

它表示R中屬性組為X上值為x的諸元組在Z上分量的集合,實際上就是所有值等於x的元組(或記錄),然後在Z上的投影。

計算步驟

計算關係R除以關係S的步驟

將被除關係R的屬性分像集屬性和結果屬性兩部分:與除關係S相同的屬性屬於像集屬性,不相同的屬性屬於結果屬性。

求出被除關係R中X的各個分量的象集Y(將被除關係分組,結果屬性值X一樣的元組分為一組。);

在除關係S中,求出與被除關係相同的屬性(像集屬性)Y的投影,得到除目標數據集合Π(S);

逐一考察每個組,比較像集Y和除目標數據集合Π(S),選取滿足Π(S)⊇Y像集屬性值包括除目標屬性集合,則對應的結果屬性值應該屬於該除法運算結果集。

1.

將被除關係R的屬性分像集屬性和結果屬性兩部分:與除關係S相同的屬性屬於像集屬性,不相同的屬性屬於結果屬性。

2.

求出被除關係R中X的各個分量的象集Y(將被除關係分組,結果屬性值X一樣的元組分為一組。);

3.

在除關係S中,求出與被除關係相同的屬性(像集屬性)Y的投影,得到除目標數據集合Π(S);

4.

逐一考察每個組,比較像集Y和除目標數據集合Π(S),選取滿足Π(S)⊇Y像集屬性值包括除目標屬性集合,則對應的結果屬性值應該屬於該除法運算結果集。

性質

兩個關係的除法運算可表示為:

R÷S=Π(R)-Π((Π(R)×S)-R)

示例

設關係R、S分別如下表所示。

關係R
ABC
a1b1c2
a2b3c7
a3b4c6
a1b2c3
a4b6c6
a2b2c3
a1b2c1

a在R中的象集為{(b1,c2),(b2,c3),(b2,c1)}

a在R中的象集為{(b3,c7), (b2,c3)}

a在R中的象集為{(b4,c6)}

a在R中的象集為{(b6,c6}

關係S
BCD
b1c2d1
b2c1d1
b2c3 d2

S在(B,C)上的投影為{(b,c),(b,c),(b,c)},所以只有a的像集(B,C)a包含S在(B,C)屬性組上的投影,即:R÷S={a}

A
a1

套用

SC關係表
學號Sno課程號Cno成績Grade
201215121192
201215121285
201215121388
201215122290
201215122380

查詢至少選修1號課程和3號課程的學生號碼。

首先建立一個臨時關係K,然後求Π(SC)÷K。這裡先求投影是為了簡便運算書寫,直接相除仍然包含K,有一樣的結果。

關係K
課程號Cno
1
3

求解過程與示例類似,先對SC關係在(Sno,Cno)屬性上投影,然後逐一求出每一學生(Sno)的像集,一次檢查這些像集是否包含K。

結果為{201215121}

相關詞條

熱門詞條

聯絡我們