第4章 關系運算

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

s[i]θu[j]：元組s的第i個分量和元組u的第j個分量滿足θ關系。

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

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