關(guān)系系統(tǒng)及其查詢(xún)優(yōu)化

1、第四章 關(guān)系系統(tǒng)及其查詢(xún)優(yōu)化4.1 關(guān)系系統(tǒng)n關(guān)系系統(tǒng)與關(guān)系模型的關(guān)系？n支持關(guān)系模型的數(shù)據(jù)庫(kù)管理系統(tǒng)是關(guān)系系統(tǒng)？n一個(gè)實(shí)際的關(guān)系系統(tǒng)必須完全支持關(guān)系模型？n只有完全支持關(guān)系模型的系統(tǒng)才能稱(chēng)為關(guān)系系統(tǒng)？n什么樣的系統(tǒng)可以定義為關(guān)系系統(tǒng)？4.1.1 關(guān)系系統(tǒng)的定義n一個(gè)系統(tǒng)可以定義為關(guān)系系統(tǒng)，當(dāng)且僅當(dāng)它： (1) 支持關(guān)系數(shù)據(jù)庫(kù)(關(guān)系數(shù)據(jù)結(jié)構(gòu))：表 (2) 支持選擇、投影和(自然)連接運(yùn)算，且對(duì)這些運(yùn)算不必要求任何物理存儲(chǔ)路徑方便用戶(hù)使用的重要運(yùn)算而由關(guān)系系統(tǒng)自動(dòng)選擇進(jìn)一步理解：方便用戶(hù)，提高性能，物理獨(dú)立性，最有用進(jìn)一步理解：方便用戶(hù)，提高性能，物理獨(dú)立性，最有用4.1.2 關(guān)系系統(tǒng)的分類(lèi)n關(guān)

2、系模型的組成部分n數(shù)據(jù)結(jié)構(gòu)(關(guān)系)S，完整性約束I，數(shù)據(jù)操縱M用陰影表示支持程度4.1.2 關(guān)系系統(tǒng)的分類(lèi)n表式關(guān)系：n僅支持關(guān)系數(shù)據(jù)結(jié)構(gòu)，如倒排表列n最小關(guān)系系統(tǒng)：n僅支持關(guān)系數(shù)據(jù)結(jié)構(gòu)和三種關(guān)系操作，如FoxBASE, FoxPron關(guān)系完備的系統(tǒng)n支持關(guān)系數(shù)據(jù)結(jié)構(gòu)和所有的關(guān)系代數(shù)操作，如Oracle, Sybasen全關(guān)系系統(tǒng)：n完全地支持關(guān)系模型的所有特征n是一個(gè)目標(biāo)，有一套參考準(zhǔn)則(12條) 自學(xué)全關(guān)系系統(tǒng)的12條基本準(zhǔn)則4.2 關(guān)系系統(tǒng)的查詢(xún)優(yōu)化4.2.1關(guān)系系統(tǒng)及其查詢(xún)優(yōu)化n說(shuō)明n查詢(xún)處理是RDBMS的核心，而查詢(xún)優(yōu)化技術(shù)是查詢(xún)處理的關(guān)鍵技術(shù)n查詢(xún)優(yōu)化的目標(biāo)n選擇有效的策略，求得給

3、定表達(dá)式的值n查詢(xún)優(yōu)化的優(yōu)點(diǎn)n使得用戶(hù)在表達(dá)查詢(xún)時(shí)不必考慮查詢(xún)效率問(wèn)題nRDBMS將通過(guò)優(yōu)化器(Optimizer)自動(dòng)進(jìn)行查詢(xún)優(yōu)化SQL、關(guān)系代數(shù)等表達(dá)式優(yōu)化器可以做什么？查詢(xún)優(yōu)化的一般步驟n將查詢(xún)轉(zhuǎn)換成某種內(nèi)部表示，如語(yǔ)法樹(shù)n語(yǔ)法樹(shù)有多種形式，如關(guān)系代數(shù)語(yǔ)法樹(shù)。n將語(yǔ)法樹(shù)轉(zhuǎn)換成標(biāo)準(zhǔn)(優(yōu)化)形式：n優(yōu)化器將應(yīng)用等價(jià)轉(zhuǎn)換規(guī)則反復(fù)地(通過(guò)內(nèi)部的循環(huán)算法)對(duì)查詢(xún)表達(dá)式進(jìn)行嘗試性轉(zhuǎn)換，將原始的語(yǔ)法樹(shù)轉(zhuǎn)換成“優(yōu)化”的形式。n選擇低層的存取路徑：n根據(jù)數(shù)據(jù)字典中的存取路徑、數(shù)據(jù)的存儲(chǔ)分布以及聚簇情況等信息來(lái)選擇具體的執(zhí)行算法，進(jìn)一步改善查詢(xún)效率。n生成由一系列內(nèi)部操作組成的查詢(xún)執(zhí)行方案，選擇代價(jià)最小的。

4、目前商品化RDBMS大都采用基于代價(jià)的優(yōu)化算法多用戶(hù)環(huán)境下總代價(jià)多用戶(hù)環(huán)境下總代價(jià)I/O代價(jià)代價(jià)CPU代價(jià)內(nèi)存代價(jià)代價(jià)內(nèi)存代價(jià)4.2.2 一個(gè)實(shí)例)(3)(2)(1 2 . 2 . 2 .SCStudentQSCStudentQSCStudentQCnoSCSnameCnoSCSnameCnoSCSnoSCSnoStudentSname或或例子：求選修了2號(hào)課程的學(xué)生姓名假設(shè)：學(xué)生-課程數(shù)據(jù)庫(kù)中有1000個(gè)學(xué)生記錄，10000個(gè)選課記錄，其中選修2號(hào)課程的選課記錄為50個(gè)SELECT Student.SnameFROM Student, SCWHERE Student.Sno = SC.Sno

5、 AND SC.Cno = 2;SQL：關(guān)系代數(shù)：對(duì)于Q1，假設(shè)讀取表的策略為：一個(gè)塊能裝10個(gè)Student元組或100個(gè)SC元組，在內(nèi)存中存放5塊Student元組和1塊SC元組，每秒讀寫(xiě)20塊。代價(jià)分析1：Q11、計(jì)算笛卡爾積：n讀取所有數(shù)據(jù)庫(kù)記錄到內(nèi)存所需時(shí)間：n需讀取總塊數(shù)為1000/10 + 1000/(10*5) * 10000/100 = 100 + 20*100 = 2100塊，總計(jì)花費(fèi)2100/20=105秒n從內(nèi)存寫(xiě)到中間文件讀取笛卡兒積所需時(shí)間：n計(jì)算笛卡爾積后生成元組數(shù)為103*104=107個(gè)。設(shè)每塊能裝10個(gè)元組，則將積結(jié)果塊從內(nèi)存寫(xiě)到中間文件為107/10/20

6、=5*104秒2、選擇操作n需要將笛卡爾積結(jié)果塊從中間文件讀入內(nèi)存，需要的時(shí)間同樣為107/10/20=5*104秒。3、投影：假設(shè)選擇操作后得到的結(jié)果僅50個(gè)元組，最后在此基礎(chǔ)上作投影操作，時(shí)間可以忽略。因此，忽略?xún)?nèi)存代價(jià)，執(zhí)行Q1的總時(shí)間約為105+2*5*104秒讀Student表100塊讀SC表20遍，每遍100塊代價(jià)分析2：Q21、計(jì)算自然連接n需要讀取的總塊數(shù)和花費(fèi)的時(shí)間為仍為 2100塊和105秒n自然連接后生成的元組數(shù)為104個(gè)，設(shè)每塊能裝10個(gè)元組，則計(jì)算完自然連接后將這些塊從內(nèi)存寫(xiě)到中間文件時(shí)間均為104/10/20=50秒。2、選擇操作n需要將連接后的結(jié)果從中間文件讀入內(nèi)

7、存，需要的時(shí)間同樣為50秒。3、投影操作：時(shí)間可以忽略因此，忽略?xún)?nèi)存代價(jià)，執(zhí)行Q1的總時(shí)間約為105+2*50 = 205秒代價(jià)分析3：Q31、選擇運(yùn)算n先對(duì)SC表作選擇運(yùn)算，只需讀一遍SC表，存取100塊花費(fèi)時(shí)間為100/205秒。因?yàn)闈M(mǎn)足條件的元祖僅50個(gè)，不必使用中間文件。2、自然連接n讀取Student表，把讀入的Student元組和內(nèi)存中的SC元組作連接。也只需讀一遍Student表共100塊花費(fèi)時(shí)間為5秒3、投影運(yùn)算：時(shí)間可以忽略因此，忽略?xún)?nèi)存代價(jià)，執(zhí)行Q1的總時(shí)間約為5+5 = 10秒可見(jiàn)，同樣的查詢(xún)通過(guò)不同的執(zhí)行過(guò)程，其效率相差很大，因此有必要進(jìn)行查詢(xún)優(yōu)化。4.2.3 查詢(xún)優(yōu)化

8、的一般準(zhǔn)則n選擇運(yùn)算應(yīng)盡可能先做n在執(zhí)行連接前對(duì)關(guān)系適當(dāng)?shù)仡A(yù)處理（建立索引，排序）n將投影運(yùn)算和選擇運(yùn)算同時(shí)進(jìn)行n將投影同其前或其后的雙目運(yùn)算結(jié)合起來(lái)，減少掃描關(guān)系的次數(shù)n將某些選擇同在它前面要執(zhí)行的笛卡爾積結(jié)合起來(lái)成為一個(gè)連接運(yùn)算，連接運(yùn)算比笛卡爾積省很多時(shí)間n找出公共子表達(dá)式4.2.4 關(guān)系代數(shù)等價(jià)變換規(guī)則n各種關(guān)系查詢(xún)語(yǔ)言都可以等價(jià)地轉(zhuǎn)換為關(guān)系代數(shù)表達(dá)式，因此關(guān)系代數(shù)表達(dá)式的優(yōu)化是查詢(xún)優(yōu)化的基本課題n研究關(guān)系代數(shù)表達(dá)式的優(yōu)化最后從其等價(jià)變換規(guī)則開(kāi)始常用的關(guān)系代數(shù)等價(jià)變換規(guī)則n1）連接、笛卡爾積的交換n2）連接、笛卡爾積的結(jié)合n3）投影的串接n4）選擇的串接122112211221EEEE

9、EEEEEEEEFF)()()()()()(3221132211321321321321EEEEEEEEEEEEEEEEEEFFFF的子集是其中BmBAnAEEAnAABmBBAnAA,.,1,.,1),()(,.,2, 1,.,2, 1,.,2, 1)()(2121EEFFFFn5）選擇與投影的交換n6）選擇與笛卡爾積的交換n7）選擇與并的交換n8）選擇與差的交換)()(,.,2, 1,.,2, 1EEFAnAAAnAAF)()()(212121EEEEEEFFF有相同的屬性名，則和設(shè))()()(,21212121EEEEEEEEEFFF則有相同的屬性名，設(shè))2)()(212,11)2()(

10、)(2211, 212)()(11122121121121EEEEEEFEFEEEEEFEFFFFEEEEEFFFFFFFFF則兩者的屬性，和涉及中的屬性只涉及如果則中的屬性，只涉及中的屬性，只涉及且如果則中的屬性，中涉及的屬性都是如果常用的關(guān)系代數(shù)等價(jià)變換規(guī)則(續(xù))n9）投影與笛卡爾積的交換n10）投影與并的交換)()()(2,.,2, 11,.,2, 121,.,2, 121EEEEEEAnAAAnAAAnAA有相同的屬性名，則和設(shè))()()(,.,1,.,1, 212,.,2, 11,.,2, 121,.,2, 1,.,2, 121EEEEEBmBEAnAEEBmBBAnAABmBBAn

11、AA則的屬性，是的屬性，是且和設(shè)兩個(gè)關(guān)系常用的關(guān)系代數(shù)等價(jià)變換規(guī)則(續(xù))4.2.5 關(guān)系代數(shù)表達(dá)式的優(yōu)化算法關(guān)系代數(shù)語(yǔ)法樹(shù)(Q1的語(yǔ)法樹(shù))SELECT Student.SnameFROM Student, SCWHERE Student.Sno = SC.Sno AND SC.Cno = 2;Student SCproject(Sname)select(SC.Cno= 2)join(Student.Sno =SC.Sno) Sname Student.Sno =SC.Sno Student SC.Cno= 2SCStudent SCSname SC.Cno= 2 Student.Sno =SC

12、.Sno 原始語(yǔ)法樹(shù)優(yōu)化后的語(yǔ)法樹(shù)(Q3的語(yǔ)法樹(shù))關(guān)系表達(dá)式的優(yōu)化算法n輸入：語(yǔ)法樹(shù)n輸出：計(jì)算程序n方法：n利用規(guī)則4變換n對(duì)每個(gè)選擇處理，利用規(guī)則4-8盡可能將其移到樹(shù)的葉端n對(duì)每個(gè)投影處理，利用規(guī)則0盡可能將其移到樹(shù)的葉端n利用規(guī)則3-5將選擇和投影的串接合并成單個(gè)選擇，單個(gè)投影或一個(gè)選擇后跟一個(gè)投影，使多個(gè)選擇或投影能并行n將以上得到的語(yǔ)法樹(shù)的內(nèi)節(jié)點(diǎn)分組n生成一個(gè)程序，每一節(jié)點(diǎn)為一步語(yǔ)法樹(shù)及其優(yōu)化實(shí)例MovieStarStarsInstarnamename)(,birthdateMAXyear關(guān)系代數(shù)語(yǔ)法樹(shù)一SELECT year,MAX(birthdate)FROM MovieStar, StarsInWHERE name = starnameGROUP BY year;StarsIn(title, year, starname)MovieStar(name, address, gender, birth