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

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

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

3、R)=?也就是說，R對稱當且僅當s(R)=R定理 2.5：設R是A上的二元關系, 則(1)R是自反的當且僅當r(R)=R；(2)R是對稱的當且僅當s(R)=R；(3)R是傳遞的當且僅當t(R)=R。自反的(對稱的, 傳遞的)； RR；對任一自反(對稱, 傳遞)關系R,若RR,則RR。7定理 2.5：設R是A上的二元關系, 則(1)R是自反的當且僅當r(R)=R；(2)R是對稱的當且僅當s(R)=R；(3)R是傳遞的當且僅當t(R)=R。定理 2.6：設R1和R2是A上的二元關系,R1R2則(1)r(R1)r(R2)；(2)s(R1)s(R2)；(3)t(R1)t(R2)。8設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：設R是集合A上的二元關系,IA是集合A上的恒等關系,則r(R)=RIA。(IA=(a,a)|aA)證明：令R=RIA。驗證R滿足閉包的三個條件9(1) 自反(2) RR，(3)假設有A上的二元關系R，R自反且RR，(目標是RR)定理 2.8：設R是集合A上的二元關系, 則s(R)=RR-1。證明：令R=RR-1。驗證R滿足閉包的三個條件(1) R=RR-1對稱(R是對稱的當且僅當R

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

6、(R)14四、閉包的性質定理 2.11：設R是A上的二元關系。(1)若R是自反的,則s(R)和t(R)都是自反的 (2)若R是對稱的,則r(R)和t(R)都是對稱的 (3)若R是傳遞的,則r(R)是傳遞的。證明(1)(3)證明:(1)對任意的aA,目標是(a,a)s(R), (a,a)t(R)(3)對任意(a,b),(b,c)r(R)=RIA,目標是(a,c)RIA15R是傳遞的,s(R)是否傳遞？不一定定理 2.12：設R是A上的二元關系, 則(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是對稱的當且僅當s(R)=Rts(R)是否與st(R)相等?162.6 等價關系與劃分一、等價關系定義 2.13：設R是集合A上的二元關系,若R是自反的、對稱的和傳遞的,則稱R是A上的等價關系。若aRb,則稱a與b等價。17例：設整數(shù)集I上的模m同余關系R是I上的等價關系。證明:(1)自反(目標是證明對任意aI，有aRa)(2)對稱(目標是證明若有aRb，則必有bRa)(3)傳遞(目標是證明若有aRb，bRc，則必有aRc)因此整數(shù)集I上的模m同余關系R是I上的等價關系18例:設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的劃分。注