復(fù)旦大學(xué) 計算機院 趙一鳴 離散數(shù)學(xué)(中文課件) 3

1、四、投影運算在數(shù)據(jù)庫中, 用關(guān)系來描述數(shù)據(jù)時常用投影運算進行數(shù)據(jù)操作。定義 2.10：設(shè)R是A1,A2,An的n元關(guān)系,定義R在Ai1,Ai2,Aim上的投影是一個m元關(guān)系,它是通過選取R中的每個有序ni1,第i2,第im個分量組成有序mm元關(guān)系中的元素,這個投影記為Ai1,Ai2,Aim(R)。1例：四元關(guān)系R和三元關(guān)系S定義如下:2關(guān)系R的投影的元素個數(shù)R的元素個數(shù)。3討論了關(guān)系的性質(zhì):自反,反自反,對稱,反對稱,傳遞通常一些關(guān)系不一定具有這些性質(zhì),但若在此關(guān)系基礎(chǔ)之上適當(dāng)增加一些元素,就可以使之具有所要的性質(zhì)了。例：R=(a,b),(b,a),(a,c),不對稱。若增加元素(c,a),得

2、R=(a,b),(b,a),(a,c), (c,a)，而且R是一個包含R的不可減少任何元素的對稱關(guān)系閉包42.5 關(guān)系的閉包一、閉包的定義從給定關(guān)系R出發(fā)構(gòu)造一個新關(guān)系R,使得R包含R,并且R是具有某種性質(zhì)的關(guān)系,同時R又是包含R的最小關(guān)系。從關(guān)系R得到新關(guān)系R的運算通稱為閉包運算。5定義 2.11：設(shè)R是A上的二元關(guān)系,定義R的自反(對稱,傳遞)閉包記為R,滿足下列三個條件：(1)R是自反的(對稱的, 傳遞的)；(2) RR；(3)對任一自反(對稱, 傳遞)關(guān)系R,若RR,則RR。R的自反閉包,對稱閉包和傳遞閉包分別記為r(R),s(R)和t(R)(t(R)又記為R+)。6例：若R對稱，s(

3、R)=?也就是說，R對稱當(dāng)且僅當(dāng)s(R)=R定理 2.5：設(shè)R是A上的二元關(guān)系, 則(1)R是自反的當(dāng)且僅當(dāng)r(R)=R；(2)R是對稱的當(dāng)且僅當(dāng)s(R)=R；(3)R是傳遞的當(dāng)且僅當(dāng)t(R)=R。自反的(對稱的, 傳遞的)； RR；對任一自反(對稱, 傳遞)關(guān)系R,若RR,則RR。7定理 2.5：設(shè)R是A上的二元關(guān)系, 則(1)R是自反的當(dāng)且僅當(dāng)r(R)=R；(2)R是對稱的當(dāng)且僅當(dāng)s(R)=R；(3)R是傳遞的當(dāng)且僅當(dāng)t(R)=R。定理 2.6：設(shè)R1和R2是A上的二元關(guān)系,R1R2則(1)r(R1)r(R2)；(2)s(R1)s(R2)；(3)t(R1)t(R2)。8設(shè)A=1,2,3,R

4、=(1,2),(1,3),則r(R)=(1,1),(2,2),(3,3),(1,2),(1,3)s(R)=(1,2),(1,3),(2,1),(3,1)t(R)=(1,2),(1,3)二、確定閉包的方法定理 2.7：設(shè)R是集合A上的二元關(guān)系,IA是集合A上的恒等關(guān)系,則r(R)=RIA。(IA=(a,a)|aA)證明：令R=RIA。驗證R滿足閉包的三個條件9(1) 自反(2) RR，(3)假設(shè)有A上的二元關(guān)系R，R自反且RR，(目標(biāo)是RR)定理 2.8：設(shè)R是集合A上的二元關(guān)系, 則s(R)=RR-1。證明：令R=RR-1。驗證R滿足閉包的三個條件(1) R=RR-1對稱(R是對稱的當(dāng)且僅當(dāng)R

5、=R-1)(2)RRR-1=R，(3)假設(shè)有A上二元關(guān)系R，R對稱且RR，(目標(biāo)RR)10例：整數(shù)集上的“”的對稱閉包是“”，少了=任一非空集A，其上的恒等關(guān)系的自反(對稱)閉包就是恒等關(guān)系其上的空關(guān)系的自反閉包是恒等關(guān)系其上的空關(guān)系的對稱閉包是空關(guān)系定理 2.9：設(shè)R是集合A上的二元關(guān)系, 則11(1)傳遞：對任意(a,b),(b,c)R=RR2R3(a,c)R,(2)RRR2R3=R，(3)假設(shè)有A上的二元關(guān)系R，R傳遞且RR，(目標(biāo)是RR)12定理 2.10：設(shè)R是有限集A上的二元關(guān)系, 且|A|=n,則13例：A=a,b,c,d,R=(a,b),(b,a),(b,c),(c,d),求t

6、(R)14四、閉包的性質(zhì)定理 2.11：設(shè)R是A上的二元關(guān)系。(1)若R是自反的,則s(R)和t(R)都是自反的 (2)若R是對稱的,則r(R)和t(R)都是對稱的 (3)若R是傳遞的,則r(R)是傳遞的。證明(1)(3)證明:(1)對任意的aA,目標(biāo)是(a,a)s(R), (a,a)t(R)(3)對任意(a,b),(b,c)r(R)=RIA,目標(biāo)是(a,c)RIA15R是傳遞的,s(R)是否傳遞？不一定定理 2.12：設(shè)R是A上的二元關(guān)系, 則(1)rs(R)=sr(R)(這里rs(R)讀作R的對稱自反閉包); (2)rt(R)=tr(R); (3)st(R)ts(R)。定理 2.6:R1R

7、2則t(R1)t(R2), s(R1)s(R2)定理2.11(2)(若R是對稱的,則r(R)和t(R)都是對稱的定理 2.5(2)R是對稱的當(dāng)且僅當(dāng)s(R)=Rts(R)是否與st(R)相等?162.6 等價關(guān)系與劃分一、等價關(guān)系定義 2.13：設(shè)R是集合A上的二元關(guān)系,若R是自反的、對稱的和傳遞的,則稱R是A上的等價關(guān)系。若aRb,則稱a與b等價。17例：設(shè)整數(shù)集I上的模m同余關(guān)系R是I上的等價關(guān)系。證明:(1)自反(目標(biāo)是證明對任意aI，有aRa)(2)對稱(目標(biāo)是證明若有aRb，則必有bRa)(3)傳遞(目標(biāo)是證明若有aRb，bRc，則必有aRc)因此整數(shù)集I上的模m同余關(guān)系R是I上的等價關(guān)系18例:設(shè)A=a,b,c,考察下列幾個由A的子集所組成的集合：P=a,b,c,S=a,b,c,T=a,b,c,U=a,c,V=a,b,b,c,W=a,b,a,c,c,對于P,由于a,bc=a,b,c，a,bc=，P是A的劃分。對于S,由于abc=a,b,c，ab=ac=bc=，S是A的劃分。對于T,顯然是A的劃分。對于U, 由于aca,b,c，所以不是A的劃分對于V, 盡管a,bb,c=a,b,c，但a,bb,c=b,所以不是A的劃分。類似可知W也不是A的劃分。注