第4章 關(guān)系運(yùn)算

第4章關(guān)系運(yùn)算學(xué)習(xí)目的和要求總體要求：深刻理解關(guān)系模型的運(yùn)算理論，了解查詢優(yōu)化的意義和啟發(fā)式優(yōu)化算法。熟練掌握：關(guān)系代數(shù)的基本理論和應(yīng)用；掌握：關(guān)系演算的定義及簡(jiǎn)單應(yīng)用；理解：關(guān)系代數(shù)表達(dá)式的優(yōu)化學(xué)習(xí)重點(diǎn)：關(guān)系代數(shù)運(yùn)算；學(xué)習(xí)難點(diǎn)：關(guān)系演算；第4章關(guān)系運(yùn)算關(guān)系模型的三個(gè)重要組成部分：數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)操縱數(shù)據(jù)完整性規(guī)則DML可分為：數(shù)據(jù)查詢語(yǔ)句、數(shù)據(jù)更新語(yǔ)句；關(guān)系運(yùn)算理論是數(shù)據(jù)查詢的理論基礎(chǔ)；關(guān)系代數(shù)：以集合操作為基礎(chǔ)的查詢；關(guān)系演算：以謂詞演算為基礎(chǔ)的查詢；4.1.1關(guān)系代數(shù)的5個(gè)基本操作傳統(tǒng)的集合操作：并、差、交、笛卡兒積、笛卡兒積的逆運(yùn)算；擴(kuò)充的關(guān)系操作：投影、選擇；關(guān)系代數(shù)的基本操作：并、差、笛卡兒積、投影、選擇；4.1.1關(guān)系代數(shù)的5個(gè)基本操作1．并(Union)設(shè)R和S具有相同的關(guān)系模式，R和S的并是由屬于R或?qū)儆赟的元組構(gòu)成的集合。2．差（Difference）設(shè)R和S具有相同的關(guān)系模式，R和S的差是由屬于R但不屬于S的元組構(gòu)成的集合。4.1.1關(guān)系代數(shù)的5個(gè)基本操作3．笛卡兒積(CartesianProduct)設(shè)R和S的元數(shù)（屬性個(gè)數(shù)）分別是r和s，R和S的笛卡兒積是一個(gè)(r+s)元的元組集合，每個(gè)元組的前r個(gè)分量（屬性值）來(lái)自R的一個(gè)元組，后s個(gè)分量來(lái)自s的一個(gè)元組。若R有個(gè)元組，S有n元組，則R×S有m*n個(gè)元組。4.1.1關(guān)系代數(shù)的5個(gè)基本操作4．投影(Projection)設(shè)R為k元關(guān)系，R在其分量Ai1,…,Aim（m≦k,i1,…,im為1到k的整數(shù)）上的投影用∏i1,…,im(R)表示，它是一個(gè)m元的組合：該操作實(shí)現(xiàn)對(duì)關(guān)系的垂直分割，消去某些列，并重新安排列的順序。121110987654321DCBA∏3,1(R)或∏C,A(R)9115713AC4.1.1關(guān)系代數(shù)的5個(gè)基本操作5．選擇(Selection)選擇是根據(jù)條件對(duì)關(guān)系作水平分割，即選擇符合條件的元組。條件用命題公式F表示，F(xiàn)有２種成分：運(yùn)算對(duì)象：常數(shù)、元組分量（屬性）運(yùn)算符：比較運(yùn)算符、邏輯運(yùn)算符例4.1（P97）4.1.2關(guān)系代數(shù)的4個(gè)組合操作1．交(Intersection)R和S的交是由屬于R又屬于S的元組構(gòu)成的集合。由于R∩S=R-R(R-S)或R∩S=S-(S-R)，故交不是獨(dú)立操作。4.1.2關(guān)系代數(shù)的4個(gè)組合操作2．連接(Join)連接是從R和S的笛卡兒積中選取屬性滿足某一比較運(yùn)算操作的元組。由于故連接是由笛卡兒積和選擇操作組合而成。例：4.2(P98)4.1.2關(guān)系代數(shù)的4個(gè)組合操作3．自然連接(NaturalJoin)先計(jì)算R×S；設(shè)R和S的公共屬性為A1,…,Ak,挑選R×S中滿足R.A1=S.A1,…,R.Ak=S.Ak的元組；去掉S.A1,…,S.Ak這些列，即得到自然連接。其中i1,…,im為Ｒ和S的全部屬性。自然連接是去掉重復(fù)屬性的等值連接。沒(méi)有公共屬性的自然連接轉(zhuǎn)化為笛卡兒積。例4.3(P98)4.1.2關(guān)系代數(shù)的4個(gè)組合操作4．除法(Division)設(shè)R和S的元數(shù)分別為r和s(r>s>0)，R÷S是一個(gè)r-s元的元組的集合，它滿足下列條件的最大關(guān)系：該集合中每個(gè)元組t與S中每個(gè)元組u組成的新元組<t,u>必然在關(guān)系R中。例4.4(P99)4.1.3關(guān)系代數(shù)運(yùn)算的應(yīng)用實(shí)例在關(guān)系代數(shù)運(yùn)算中，把由5個(gè)操作經(jīng)過(guò)有限次復(fù)合的式子稱為關(guān)系代數(shù)表達(dá)。關(guān)系代數(shù)表達(dá)式的結(jié)果仍為關(guān)系。例：設(shè)有如下關(guān)系：教師T(T#,Tname,Title)課程C(C#,Cname,T#)學(xué)生S(S#,Sname,Age,sex)選課SC(S#,C#,Score)請(qǐng)用關(guān)系代數(shù)表達(dá)式實(shí)現(xiàn)P100的查詢。4.1.4關(guān)系代數(shù)的兩個(gè)擴(kuò)充操作外連接(OuterJoin)若R和S做自然連接時(shí)，把原該丟棄的元組也保留在新關(guān)系中，同時(shí)在這些元組新增加的屬性上填空值(Null)，這種操作稱“外連接”。只保留R中的元組的操作稱“左連接”只保留S中的元組的操作稱“右連接”外部并(OuterUnion)對(duì)關(guān)系模式不同的R和S，外部并所構(gòu)成的新關(guān)系的屬性由R和S的所有屬性（公共屬性只取一次）組成。例：P1024.2關(guān)系演算關(guān)系演算：元組演算：以元組為變量域演算：以域?yàn)樽兞?.2.1元組關(guān)系演算元且表達(dá)式的一般形式：{t|P(t)}.t是元組變量，表示一個(gè)元數(shù)固定的元組，P是公式，也稱謂詞，即計(jì)算機(jī)語(yǔ)言中的條件表達(dá)式。表示滿足公式P的所有元組t的集合。4.2.1元組關(guān)系演算1、原子公式和公式的意義在元組表達(dá)式，公式由原子公式構(gòu)成定義：原子公式有下列3種形式：R(s)：s是R的一個(gè)元組。

s[i]θu[j]：元組s的第i個(gè)分量和元組u的第j個(gè)分量滿足θ關(guān)系。

s[i]θa或aθs[j]：元組s的第i個(gè)分量與常數(shù)a之間滿足θ關(guān)系。元組變量未用存在量詞或全稱量詞定義的變量稱自由變量，否則稱約束變量。4.2.1元組關(guān)系演算公式的遞歸定義：每個(gè)原子是一個(gè)公式，其元組變量是自由變量。如果P1和P2是公式，那么┑P1、P1∧P２、P1∨P2和P1=>P2也都是公式。如果P1是公式，那么：公式只能由上述4種形式構(gòu)成。4.2.1元組關(guān)系演算例：P103-104321987654CBA321965643CBARS4.2.1元組關(guān)系演算等價(jià)轉(zhuǎn)換規(guī)則4.2.1元組關(guān)系演算2、關(guān)系代數(shù)表達(dá)式到元組表達(dá)式的轉(zhuǎn)換設(shè)R和S為3元關(guān)系，則：例4.10(P105)4.2.1元組關(guān)系演算例4.11：(P105、P100)有如下關(guān)系：教師T(T#,Tname,Title)、課程C(C#,Cname,T#)、學(xué)生S(S#,Sname,Age,sex)、選課SC(S#,C#,Score)4.2.2域關(guān)系演算域關(guān)系演算類似于元組關(guān)系演算，用域變量代替元組變量的第一個(gè)分量，其變化范圍是某個(gè)值域。原子公式：R(x,…,xk)，R為k元關(guān)系，xi為常量或域變量；Xθj，x,y至少有一個(gè)是域變量；也可用邏輯與、或、非，存在量詞和全稱量詞等形成新公式，但此時(shí)x是域變量；域演算表達(dá)式的一般形式為：

{t1…tk|P(t1,…,tk)}例：P1064.2.2域關(guān)系演算元組表達(dá)式到域表達(dá)式的轉(zhuǎn)換總體思想：用域變量代替相應(yīng)元組變量或其分量。詳細(xì)方法見(jiàn)(P106-107)例4.13例4.144.2.3關(guān)系運(yùn)算的安全約束和等價(jià)性關(guān)系運(yùn)算的安全性在關(guān)系代數(shù)中沒(méi)有集合的“補(bǔ)”操作，因而關(guān)系運(yùn)算總是安全的。關(guān)系演算可能出現(xiàn)無(wú)限關(guān)系和無(wú)窮驗(yàn)證問(wèn)題而不安全；定義：在數(shù)據(jù)庫(kù)技術(shù)中，不產(chǎn)生無(wú)限關(guān)系和無(wú)窮驗(yàn)證的運(yùn)算稱為安全運(yùn)算，相應(yīng)的表達(dá)式稱為安全表達(dá)式，所采取的措施稱為安全約束。4.2.3關(guān)系運(yùn)算的安全約束和等價(jià)性關(guān)系運(yùn)算的等價(jià)性已經(jīng)證明，基于系代數(shù)運(yùn)算的最小完備集的關(guān)系代數(shù)、安全的的元組關(guān)系演算、安全的域關(guān)系演算在關(guān)系的表達(dá)和操作能力上完全等價(jià)的。基于關(guān)系運(yùn)算的關(guān)系查詢語(yǔ)言已研制成功并廣泛使用：ISBL(InformationSystemBaseLanguage)QUEL(QueryLanguage)QBE(QuerybyExample)SQL(StructuredQueryLanguage)4.3關(guān)系代數(shù)表達(dá)式的優(yōu)化查詢處理的代價(jià)通常取決于磁盤(pán)訪問(wèn)；同一查詢有多個(gè)等價(jià)的關(guān)系代數(shù)表達(dá)式，而不同的查詢策略所需的磁盤(pán)訪問(wèn)次數(shù)差別可能很大；關(guān)系代數(shù)表達(dá)式中需要指出若干關(guān)系的操作步驟；查詢優(yōu)化主要解決如何設(shè)計(jì)查詢策略以實(shí)現(xiàn)查詢代價(jià)的最小化（省時(shí)、省空間、高效）4.3.1關(guān)系代數(shù)表達(dá)式的優(yōu)化問(wèn)題笛卡兒積和連接運(yùn)算最費(fèi)時(shí)間；例4.15：有關(guān)笛卡兒積的優(yōu)化問(wèn)題(P109-110)4.3.2啟發(fā)式優(yōu)化算法啟發(fā)式優(yōu)化(HeuristicOptimization)主要通過(guò)合理操作順序以查詢對(duì)系統(tǒng)時(shí)間和空間的需求，與關(guān)系的存儲(chǔ)技術(shù)無(wú)關(guān)，是目前最常用的查詢優(yōu)化技術(shù)；啟發(fā)式規(guī)則（3條）盡可能早執(zhí)行選擇操作；盡可能早執(zhí)行投影操作；避免直接做笛卡兒積，把笛卡兒積操作之前和之后的一連串選擇和投影合并操作；關(guān)系代數(shù)表達(dá)式的啟發(fā)式優(yōu)化由DML編譯器完成；4.3.2啟發(fā)式優(yōu)化算法啟發(fā)式優(yōu)化算法對(duì)一個(gè)關(guān)系代數(shù)表達(dá)式進(jìn)行語(yǔ)法分析可得到語(yǔ)法樹(shù)，樹(shù)中葉子是關(guān)系，非葉結(jié)點(diǎn)是關(guān)系操作。輸入：關(guān)系表達(dá)式的語(yǔ)法樹(shù)輸出：表達(dá)式的優(yōu)化序列4.3.2啟發(fā)式優(yōu)化算法步驟把每個(gè)形為δF1∧…∧Fn(E)的子表達(dá)式轉(zhuǎn)換成選擇級(jí)聯(lián)形式：δF1(…(δFn(E))…)盡可能將選擇操作下推到最早可能執(zhí)行的