【正文】 選擇操作的實現(xiàn)（續(xù)）v［ 例 1C4］ 以 C4為例， Sdept＝ ‘CS’ AND Sage20，如果 Sdept和 Sage上都有索引：167。求這 2組指針的交集216。得到計算機系年齡大于 20的學生167。通過這些元組指針到 student表中檢索216。把滿足條件的元組作為結(jié)果輸出。 對外層循環(huán) (Student)的每一個元組 (s)，檢索內(nèi)層循環(huán)(SC)中的每一個元組 (sc)167。 如果滿足連接條件，則串接后作為結(jié)果輸出，直到外層循環(huán)表中的元組處理完為止 An Introduction to Database System連接操作的實現(xiàn)（續(xù)）2. 排序 合并方法 (sortmerge join 或 merge join) 167。 排序－合并連接方法的步驟：216。取 Student表中第一個 Sno，依次掃描 SC表中具有相同Sno的元組 An Introduction to Database System連接操作的實現(xiàn)（續(xù)）202215121202215122202215123202215124...202215121 1 92202215121 2 85202215121 3 88202215122 2 90202215122 3 80...排序 合并連接方法示意圖An Introduction to Database System連接操作的實現(xiàn)（續(xù)）167。當掃描到 Sno不相同的第一個 SC元組時，返回 Student表掃描它的下一個元組，再掃描 SC表中具有相同 Sno的元組，把它們連接起來 216。 把連接屬性作為 hash碼，用同一個 hash函數(shù)把 R和S中的元組散列到同一個 hash文件中167。 (1) 優(yōu)化器可以從數(shù)據(jù)字典中獲取許多統(tǒng)計信息，而用戶程序則難以獲得這些信息167。在非關系系統(tǒng)中必須重寫程序，而重寫程序在實際應用中往往是不太可能的。 (3)優(yōu)化器可以考慮數(shù)百種不同的執(zhí)行計劃，程序員一般只能考慮有限的幾種可能性。 (4)優(yōu)化器中包括了很多復雜的優(yōu)化技術(shù)，這些優(yōu)化技術(shù)往往只有最好的程序員才能掌握。 集中式數(shù)據(jù)庫216。I/O代價是最主要的 167。總代價 =I/O代價 +CPU代價 +內(nèi)存代價＋通信代價 An Introduction to Database System查詢優(yōu)化概述（續(xù)）v查詢優(yōu)化的總目標：167。 求得給定關系表達式的值167。用 SQL表達： SELECT FROM Student， SC WHERE = AND =‘2’； n 假定學生 課程數(shù)據(jù)庫中有 1000個學生記錄， 10000個選課記錄n 其中選修 2號課程的選課記錄為 50個 An Introduction to Database System一個實例（續(xù)）v系統(tǒng)可以用多種等價的關系代數(shù)表達式來完成這一查詢Q1=πSname(=∧ =39。 (StudentSC))Q2=πSname(=39。 (Student SC))Q3=πSname(Student =39。(SC)) An Introduction to Database System一個實例（續(xù)）v 一、第一種情況 Q1=πSname(=∧ =39。 StudentSC))1. 計算廣義笛卡爾積 v 把 Student和 SC的每個元組連接起來的做法：167。167。 從 SC中讀入一塊和內(nèi)存中的 Student元組連接，直到 SC表處理完。 再讀入若干塊 Student元組，讀入一塊 SC元組167。讀 SC表 20遍，每遍 100塊。設每塊能裝 10個元組，則寫出這些塊要用 106/20=5104s An Introduction to Database System一個實例（續(xù)）2. 作選擇操作 167。 假定內(nèi)存處理時間忽略。 滿足條件的元組假設僅 50個，均可放在內(nèi)存 An Introduction to Database System一個實例（續(xù)）3. 作投影操作 167。 第一種情況下執(zhí)行查詢的總時間 ≈105+25104≈105s167。239。執(zhí)行自然連接，讀取 Student和 SC表的策略不變，總的讀取塊數(shù)仍為 2100塊花費 105 s 216。寫出這些元組時間為 104/10/20=50s，為第一種情況的千分之一 2. 讀取中間文件塊，執(zhí)行選擇運算，花費時間也為 50s。 第二種情況總的執(zhí)行時間 ≈105+50+50≈205s An Introduction to Database System一個實例（續(xù)）v三、 第三種情況 Q3=πSname(Student =39。(SC))1. 先對 SC表作選擇運算，只需讀一遍 SC表，存取 100塊花費時間為 5s，因為滿足條件的元組僅 50個，不必使用中間文件。也只需讀一遍 Student表共 100塊，花費時間為 5s。 第一步就不必讀取所有的 SC元組而只需讀取 Cno=‘2’的那些元組 (50個 )167。 第二步也不必讀取所有的 Student元組167。 讀取 Student表的塊數(shù)也可大大減少 v 總的存取時間將進一步減少到數(shù)秒 An Introduction to Database System一個實例（續(xù)）v把代數(shù)表達式 Q1變換為 Q Q3，167。 SC表的選擇操作算法有全表掃描和索引掃描 2種方法，經(jīng)過初步估算，索引掃描方法較優(yōu) 167。4. 選擇的串接定律 ( (E))≡ (E)這里， E是關系代數(shù)表達式， F F2是選擇條件。這樣一次就可檢查全部條件。若 F中有不屬于 A1， … ， An的屬性 B1， … ， Bm則有更一般的規(guī)則： (σF(E))≡ (σF( (E)))An Introduction to Database System關系代數(shù)表達式等價變換規(guī)則（續(xù)）6. 選擇與笛卡爾積的交換律如果 F中涉及的屬性都是 E1中的屬性，則 (E1E2)≡ (E1)E2如果 F=F1∧ F2，并且 F1只涉及 E1中的屬性， F2只涉及 E2中的屬性，則由上面的等價變換規(guī)則 1， 4， 6可推出： (E1E2)≡ (E1) (E2)若 F1只涉及 E1中的屬性， F2涉及 E1和 E2兩者的屬性，則仍有 (E1E2)≡ ( (E1)E2)它使部分選擇在笛卡爾積前先做。在優(yōu)化策略中這是最重要、最基本的一條2. 把投影運算和選擇運算同時進行216。如果這種重復出現(xiàn)的子表達式的結(jié)果不是很大的關系并且從外存中讀入這個關系比計算該子表達式的時間少得多，則先計算一次公共子表達式并把結(jié)果寫入中間文件是合算的216。算法：關系表達式的優(yōu)化輸入：一個關系表達式的查詢樹輸出：優(yōu)化的查詢樹方法：(1) 利用等價變換規(guī)則 4把形如 σF1∧ F2∧ … ∧ Fn(E)變換為σF1(σF2(…( σFn(E))…)) 。An Introduction to Da