【正文】 別為：R(t)、 S (t)， 則 （ 1） R∪ S 可等價(jià)地表示為 {t｜ R(t)∨ S (t)} （ 2） R － S 等價(jià)于 { t ｜ R(t)∧ ?S (t)} （ 3） R S等價(jià)于 {t ｜ (?u)(? v)( R (u )∧ S (v)∧ t[1]=u [1] ∧ … ∧ t [k1]= u [k1 ] ∧ t [k1+1]= v [1]∧ … ∧ t [k1+ k2]= v [k2])} 式中 ， R 、 S依次為 k k2元關(guān)系 ， u 、 v 表示 R 、S 的元組變量 。 （ 4） πi1,i2,… , in (R )等價(jià)于 {t ｜ (? u )( R (u )∧ t [1]=u [i1]∧ ... ∧ t [n]= u [in]} （ 5） σF (R )等價(jià)于 { t ｜ R (t)∧ F 39。} 其中 F 39。為 F在謂詞演算中的表示形式 ， 即用t [i]代替 F中 t 的第 i個(gè)分量即為 F 39。 .1 元組關(guān)系演算 []設(shè)關(guān)系 R和 S都是二元關(guān)系 ， 把關(guān)系代數(shù)表達(dá)式 π1， 4 ( σ2=3(R S))轉(zhuǎn)換成元組演算表達(dá)式的過程如下： R S可用 {t｜ (?u)(?v)( R (u )∧ S (v)∧ t [1]= u [1]∧ t [2]= u [2]∧ t [3]= v [1]∧ t [4]= v [2])}表示； 對于 σ2=3(R S)只需在公式中加入 “ ∧ t [2]= t [3]”即可； 對于 π1， 4 ( σ2=3(R S))可得到如下元組表達(dá)式： {t｜ (?w)(?u)(?v)( R (u )∧ S (v)∧ w[1]= u [1]∧ w [2]= u[2]∧ w [3]= v [1]∧ w [4]= v [2]) ∧ w [2]= w [3]∧ t [1]= w [1]∧ t [2]= w [4]} 在對上式化簡 ， 去掉元組變量 w可得： {t｜ (?u)(?v)( R (u )∧ S (v)∧ u[2]= v[1] ∧ t [1]= u [1]∧ t [2]= v [2]} Example [] 對于例 1檢索學(xué)習(xí)課程號為 C3的學(xué)生學(xué)號與成績 2檢索選修課程名為 Maths的學(xué)生學(xué)號與姓名 3檢索選修課程號為 C1或 C4的學(xué)生學(xué)號 4檢索至少選修課程號為 C2和 C4的學(xué)生學(xué)號 {t｜ (?u)( SC(u ) ∧ u[2]=?C3? ∧ t [1]= u [1]∧ t [2]= u [3]) } {t｜ (?u)(?v)(?w)(S(u)∧ SC(v)∧ C(w) ∧ u [1]= v [1]∧ v [2]=w [1]∧ w [2]=?Maths? ∧ t [1]=u[1]∧ t [2]= u [2])} {t｜ (?u)( SC(u ) ∧ (u[2]=?C1? ∨ u[2]=?C4?)∧ t [1]= u [1] ) } {t|(?u)(?v)(SC(u)∧ SC(v)∧ u[2]=?C2?∧ v[2]=?C4?∧ u[1]=v[1]∧ t [1]=u[1])} 5檢索沒有學(xué) C2課程的學(xué)生姓名與年齡 6檢索學(xué)習(xí)全部課程的學(xué)生姓名 7檢索所學(xué)課程包含學(xué)生 S3所學(xué)課程的學(xué)生學(xué)號 {t|(?u)(?v)(?w)(S(u)∧ C(v)∧ SC(w)∧ u[1]=w[1] ∧ w[2]=v[1]∧ t [1]=u[2])} {t｜ (?u) (SC(u)∧ (?v) (SC(v)∧ (v[1]=?S3? ? (?w)(SC(w) ∧ w[1]=u[1]∧ w [2]= v [2]))) ∧ t [1]= u [1])} { t｜ (?u)( ? v)(S(u)∧ SC(v)∧ (u[1]=v[1] ? v[2]≠‘ C2’)∧ t [1]=u[2]∧ t [2]= u [3])} 域關(guān)系演算 域關(guān)系演算類似于元組演算 ， 所不同的是公式中的變量不是元組變量 ， 而是表示元組變量各個(gè)分量的域變量 。 域演算表達(dá)式的一般形式為： {t1 t2… tk｜ φ(t1, t2, …, tk)} 其中 t1， t2， … tk為元組變量 t的各個(gè)分量 ， 統(tǒng)稱為域變量 ， φ是一個(gè)公式 ， 類似于元組演算公式 。 域關(guān)系演算 遞歸地定義域演算公式如下 : （ 1） 原子命題函數(shù)是公式 ， 域演算也有如下 3種形式的原子命題函數(shù)或原子公式 。 ① R(t1 t2… tk )。 R是 k元關(guān)系 ， ti是域變量或常量 。R(t1 t2… tk ) 表示命題函數(shù)： “ 以 t1， t2， … ， tk為分量的元組在關(guān)系 R中 ” 。 ② ti θ c或 c θ ti。 ti為元組變量 ｔ 的第 i個(gè)分量 ， c為常量 ， θ為算術(shù)比較運(yùn)算符 。 ③ ti θ uj。 ti為元組 t的第 i個(gè)分量 ， uj為元組 u的第 j個(gè)分量 ， θ同上 。 域關(guān)系演算 （ 2 ） 設(shè) φ φ2 是公式 ， 則 ? φ φ1∧ φφ1∨ φ φ1 ? φ2也都是公式 。 （ 3） 設(shè) φ(t1, t2, … , tk)是公式 ， 則 (?ti)(φ)、(?ti)(φ)且 i=（ 1,2,… , k） 都是公式 。 （ 4） 域演算公式中運(yùn)算符的優(yōu)先級類同元組演算規(guī)定 。 （ 5） 域演算的全部公式均按 （ 1） 、 （ 2） 、 （ 3） 、（ 4） 求得 ， 別無其他形式 。 類似元組演算 ， 域演算公式也都是它的原子公式經(jīng)過有限次的邏輯運(yùn)算?、 ∨ 、 ∧ 、 ?和量詞運(yùn)算而形成的復(fù)合公式 。 域關(guān)系演算 將元組表達(dá)式轉(zhuǎn)化成域表達(dá)式： ① 設(shè)元組表達(dá)式為 { t | P( t )}， t是 k元的元組變量 ，那么引進(jìn) k個(gè)域變量 t1， t2， … ， tk， 用來替換元組變量t, t[i]用 ti 替換； ② 同樣對每個(gè)量詞 (?u) (?u),若 u是 m元的元組變量 ，那么引入 m個(gè)新的域變量 u1， u2， … ， um用來替換 u, u[i]用 ui替換； (?u)用 (? u1) (? u2) … (? um) 或簡寫為 （ ? u1， u2， … ， um） 來替換 。 例如將例 ： 化簡得： {w1w2| (? u1u2)(? v1v2) (R(u1u2) ∧ S(v1v2 ) ∧ u2 = v1 ∧ w1 =u1 ∧ w2=v2 } {w1w2| (? u2) (R(w1u2) ∧ S(u2 w2 ))} Example 如下圖所示為為三個(gè)關(guān)系 R,S,W,分別寫出下面三個(gè)域表達(dá)式的值： ① R1={XYZ｜ R(XYZ)∧ Y 3∧ X 5} ② R2={(XYZ｜ (R(XYZ)∨ (S(XYZ)∧ Y=4))} ③ R3={XYZ｜ (?uv)(R(ZXu)∧ W(Yv)∧ u v} A B C A B C 1 2 3 1 2 3 4 5 6 3 4 6 7 8 9 5 6 9 D E 7 5 4 8 R S W Example R3 B D A 5 7 4 8 7 7 8 4 7 A B C 1 2 3 4 5 6 7 8 9 3 4 6 B C 5 6 4 A R2 R1 Example {ab| R(ab) ∧ R(ba)} 轉(zhuǎn)換成等價(jià)的關(guān)系代數(shù)表達(dá)式和元組表達(dá)式。 R與 S都是二元關(guān)系，試把元組表達(dá)式 {t| R(t) ∧ (?u)(S(u) ∧ u[1]t[2])}轉(zhuǎn)化成等價(jià)的域表達(dá)式和關(guān)系代數(shù)表達(dá)式。 π 1， 2 ( σ1=4 ∧ 2=3 (R R) 或 R ∩ π2 ,1 (R) {t|(?u)(?v)(R(u)∧ R(v)∧ u[1]=v[2]∧ u[2]=v[1]∧ t[1]=u[1]∧ t [2]=u[2])} 或 {t|(?v)(R(t)∧ R(v)∧ t[1]=v[2]∧ t [1]=v[1])} {t1t2 | (R(t1t2)∧ (?u1u2)S(u1u2)∧ u1t2} π1， 2 ( σ23(R S)) 或 π 1,2 (R S) 21 Example R(A,B)和 S(A,C)， 試把下列域表達(dá)式轉(zhuǎn)換成等價(jià)的關(guān)系表達(dá)式 。 （ 1） { a| (?b)( R(ab) ∧ b=17)} （ 2） { abc | (R(ab) ∧ S(ac))} （ 3{ a|(?b)(R(ab)∨ (?c)((?d)(S(dc)) ? S(ac))} （ 4） { a|(?c)( S(ac) ∧ (? b1b2 )(R(ab1)∧ R(cb2 ) ∧ b1 b2 ))} π1( σ2=?17?(R)) R S π1 (R ∪ (S 247。 π2 (S) ) π1 ( σ1=3 ∧ 2=5 ∧ 46(S R R) 習(xí) 題 3 在學(xué)生選課關(guān)系模式中，試用關(guān)系表達(dá)式表示下列查詢語句；并將其轉(zhuǎn)換成等價(jià)的元組表達(dá)式 1〉檢索學(xué)號為 S3的學(xué)生所學(xué)課程的課程名與任課教師名； 2〉檢索至少選修 hua老師所授課程中一門課的女生姓名； 3〉檢索 WANG同學(xué)不學(xué)的課程的課程號； 4〉檢索至少選修兩門課的學(xué)生學(xué)號； 5〉檢索全部學(xué)生都選修的課程的課程號與課程名； 6〉檢索選修課程包含 MIAO老師所授全部課程的學(xué)生學(xué)號； 參 考 解 答 (1) π CNAME,TEACHER (σS=?S3? (SC C) ) (2)πSNAME (σSEX=?F? ∧ TEACHER=?hua? (S SC C) (3)π C (C) π C (σSNAME=?WANG? (S SC) ) (4) π1 ( σ1=4 ∧ 2 ≠5 (SC SC) (5)π C ,SNAME ( C （ π S,C (SC) 247。 π S (S) ) ) (6) π S,C (SC) 247。 π C (σTEACHER = ?MIAO? (C) ) 參 考 解 答 (1) {t｜ (?u) (?v)( SC(u ) ∧ C(v) ∧ u[1]=?S3? ∧ u[2]=v[1] ∧ t [1]= v [2]∧ t [2]= u [2])} (2) {t｜ (?u)(?v)(?w)(S(u)∧ SC(v)∧ C(w) ∧ w [3]=?hua? ∧ u [4]=?F? ∧ u [1]= v [1]∧ v [2]=w [1] ∧ t [1]=u[2])} (3) {t｜ (?u) (?v)(?w)(C(u)∧ S (v) ∧ SC(w) ∧ v [2]=‘WANG’∧ (w[1]=v[1] ? w[2]≠u[1])∧ t [1]=u[1])} 參 考 解 答 (4){t|(?u)(?v)(SC(u)∧ SC(v)∧ u[1]=v[1]∧ u[2] ≠v[2]∧ t [1]=u[1])} (5){t|(?u)(?v)(?w)(S(v)∧ C(u)∧ SC(w)∧ w[2]=u[1] ∧ w[1]=v[1]∧ t [1]=u[1] ∧ t [2]=u[2])} (6) {t｜ (?u) (SC(u)∧ (?v) (C(v)∧ (v[3]=?MIAO? ? (?w)(SC(w) ∧ w[1]=u[1]∧ w [2]= v [1]))) ∧ t [1]= u [1])}