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

1、關(guān)系系統(tǒng)及查詢(xún)優(yōu)化 關(guān)系系統(tǒng)的定義、分類(lèi) 全關(guān)系系統(tǒng)的十二條基本準(zhǔn)則 查詢(xún)優(yōu)化的目標(biāo)、步驟 查詢(xún)優(yōu)化的實(shí)例 查詢(xún)優(yōu)化的一般準(zhǔn)則 關(guān)系代數(shù)表達(dá)式的優(yōu)化算法一、關(guān)系系統(tǒng)定義 關(guān)系系統(tǒng)：支持關(guān)系模型的數(shù)據(jù)庫(kù)管理系統(tǒng)稱(chēng)為關(guān)系關(guān)系系統(tǒng)：支持關(guān)系模型的數(shù)據(jù)庫(kù)管理系統(tǒng)稱(chēng)為關(guān)系系統(tǒng)。系統(tǒng)。（籠統(tǒng)） 關(guān)系模型中并非每一部分都同等重要，并不苛求一個(gè)實(shí)際的關(guān)系數(shù)據(jù)庫(kù) 管理系統(tǒng)必須完全支持關(guān)系模型，也不苛求完全支持關(guān)系模型的系統(tǒng)才能稱(chēng)為關(guān)系系統(tǒng)。 一個(gè)系統(tǒng)可定義為關(guān)系系統(tǒng)，當(dāng)且僅當(dāng)它一個(gè)系統(tǒng)可定義為關(guān)系系統(tǒng)，當(dāng)且僅當(dāng)它至少至少： 1、支持關(guān)系數(shù)據(jù)結(jié)構(gòu)（表） 2、支持選擇、投影和（自然）連接運(yùn)算，對(duì)這些運(yùn)算 不要求用戶(hù)

2、定義任何物理存取路徑。 對(duì)關(guān)系系統(tǒng)的最低要求關(guān)系系統(tǒng)的定義（續(xù)） 不支持關(guān)系數(shù)據(jù)結(jié)構(gòu)的系統(tǒng)顯然不能稱(chēng)為關(guān)系系統(tǒng) 僅支持關(guān)系數(shù)據(jù)結(jié)構(gòu)，但沒(méi)有選擇、投影和連接運(yùn)算功能的系統(tǒng)仍不能算作關(guān)系系統(tǒng)。 原因：不能提高用戶(hù)的生產(chǎn)率 支持選擇、投影和連接運(yùn)算，但要求定義物理存取路徑，這種系統(tǒng)也不能算作真正的關(guān)系系統(tǒng) 原因：就降低或喪失了數(shù)據(jù)的物理獨(dú)立性 選擇、投影、連接運(yùn)算是最有用的運(yùn)算二、關(guān)系系統(tǒng)的分類(lèi)前面定義的關(guān)系系統(tǒng)是關(guān)系系統(tǒng)的最小要求。按照E.F.Codd的思想，可以把關(guān)系系統(tǒng)分類(lèi)：1、表式系統(tǒng) 僅支持表數(shù)據(jù)結(jié)構(gòu)，不支持集合級(jí)的操作，不能算關(guān)系系統(tǒng)。2、最小關(guān)系系統(tǒng)支持關(guān)系數(shù)據(jù)結(jié)構(gòu)和三種關(guān)系操作。（F

3、oxBase, FoxPro等）3、關(guān)系完備的系統(tǒng)支持關(guān)系數(shù)據(jù)結(jié)構(gòu)和所有的關(guān)系代數(shù)操作（功能上等價(jià)）。4、全關(guān)系系統(tǒng)支持關(guān)系模型的所有特征。即不僅是關(guān)系上完備的，而且支持?jǐn)?shù)據(jù)結(jié)構(gòu)中域的概念，支持實(shí)體完整性和參照完整性。（目前大多數(shù)關(guān)系系統(tǒng)已接近或達(dá)到了這個(gè)目標(biāo)）關(guān)系系統(tǒng)的分類(lèi) （續(xù)） 數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)操作數(shù)據(jù)操作完整性完整性表式系統(tǒng)表式系統(tǒng)表表 (最小最小)關(guān)系系統(tǒng)關(guān)系系統(tǒng)表表選擇、投影、選擇、投影、連接連接 關(guān)系完備的系統(tǒng)關(guān)系完備的系統(tǒng)表表 全關(guān)系系統(tǒng)全關(guān)系系統(tǒng) 全關(guān)系系統(tǒng)的十二條基本準(zhǔn)則 這是關(guān)系模型的奠基人E.F.Codd從理論和實(shí)際緊密結(jié)合的高度，對(duì)關(guān)系型DBMS的評(píng)述。從實(shí)際意義

4、上看，這十二條準(zhǔn)則可以作為評(píng)價(jià)或購(gòu)買(mǎi)關(guān)系型產(chǎn)品的標(biāo)準(zhǔn)。 詳細(xì)見(jiàn)書(shū)。三、關(guān)系系統(tǒng)的查詢(xún)優(yōu)化非關(guān)系系統(tǒng)中，用戶(hù)使用過(guò)程化的語(yǔ)言表達(dá)查詢(xún)要求、執(zhí)行的操作以及操作序列，用戶(hù)必須了解存取路徑，查詢(xún)效率由用戶(hù)的存取策略決定，需要用戶(hù)對(duì) 查詢(xún)程序進(jìn)行“優(yōu)化”。而在關(guān)系系統(tǒng)中，用戶(hù)只需提出“干什么”，而不必指出“怎么干”，由系統(tǒng)來(lái)確定存取策略，提高查詢(xún)效率，即完成查詢(xún)優(yōu)化的工作。查詢(xún)優(yōu)化在關(guān)系數(shù)據(jù)庫(kù)系統(tǒng)中有著非常重要的地位，是影響RDBMS性能的關(guān)鍵因素。系統(tǒng)的“優(yōu)化器”功能與用戶(hù)“優(yōu)化工作”對(duì)比：1）可以從數(shù)據(jù)字典中獲取許多統(tǒng)計(jì)信息2）如果物理統(tǒng)計(jì)信息改變了，前者可重新優(yōu)化選擇相適應(yīng)的執(zhí)行計(jì)劃，而后者必須重

5、新寫(xiě)程序，而實(shí)際應(yīng)用中往往不太可能。3）前者可考慮數(shù)百種不同的執(zhí)行計(jì)劃，而程序員一般只能考慮有限的幾種可能性。4）前者包括了很多復(fù)雜的優(yōu)化技術(shù)，往往只有最好的程序員才能掌握。系統(tǒng)的自動(dòng)優(yōu)化使得所有人都擁有這些優(yōu)化技術(shù)。查詢(xún)優(yōu)化的一般步驟1）將查詢(xún)轉(zhuǎn)換成某種內(nèi)部表示，通常是語(yǔ)法樹(shù)（關(guān)系代數(shù)語(yǔ)法樹(shù)）。2）根據(jù)一定的等價(jià)變換規(guī)則把語(yǔ)法樹(shù)轉(zhuǎn)換成標(biāo)準(zhǔn)形式（優(yōu)化形式）。可采用關(guān)系代數(shù)表達(dá)式的優(yōu)化算法自動(dòng)進(jìn)行優(yōu)化。3）選擇低層的操作算法，即確定存取路徑。對(duì)于語(yǔ)法樹(shù)中的每一個(gè)操作需要根據(jù)存取路徑（有無(wú)索引）、數(shù)據(jù)的存儲(chǔ)分布、存儲(chǔ)數(shù)據(jù)的聚簇等信息來(lái)選擇具體的執(zhí)行算法。4）生成查詢(xún)計(jì)劃（執(zhí)行方案），選擇代價(jià)最小的

6、。對(duì)每個(gè)執(zhí)行計(jì)劃計(jì)算代價(jià)，從中選擇代價(jià)最小的一個(gè)。在集中式關(guān)系數(shù)據(jù)庫(kù)中，計(jì)算代價(jià)時(shí)主要考慮磁盤(pán)讀寫(xiě)的I/O次數(shù)，也有一些系統(tǒng)換考慮了CPU的處理時(shí)間。目前的商品化RDBMS答對(duì)采用基于代價(jià)的優(yōu)化算法： 這種方法要求優(yōu)化器充分考慮系統(tǒng)中的各種參數(shù)（如緩沖區(qū)大小、表的大小、數(shù)據(jù)的分布、存取路徑等）。集中式數(shù)據(jù)庫(kù)：總代價(jià)=I/O代價(jià)+CPU代價(jià) （時(shí)間）多用戶(hù)數(shù)據(jù)庫(kù)：總代價(jià)=I/O代價(jià)+CPU代價(jià) +內(nèi)存代價(jià) （時(shí)間）查詢(xún)優(yōu)化的一般準(zhǔn)則1）選擇運(yùn)算應(yīng)盡可能先做。因?yàn)樗墒褂?jì)算的中間結(jié)果大大變小。2）在執(zhí)行連接（自然連接）前對(duì)關(guān)系適當(dāng)?shù)仡A(yù)處理。主要有兩種方法，在連接屬性上建立索引和對(duì)關(guān)系排序，然后執(zhí)行

7、連接。（詳細(xì)見(jiàn)書(shū) P.161）3）把投影運(yùn)算和選擇運(yùn)算同時(shí)進(jìn)行。當(dāng)他們對(duì)同一個(gè)關(guān)系操作，則可以在掃描關(guān)系的同時(shí)完成所有的這些運(yùn)算來(lái)避免重復(fù)掃描關(guān)系。4）把投影和其前或其后的雙目運(yùn)算結(jié)合起來(lái)，沒(méi)有必要為了去掉某些字段而掃描一遍關(guān)系。5）把某些選擇同在它前面要執(zhí)行的笛卡兒積結(jié)合起來(lái)成為一個(gè)連接運(yùn)算，連接特別是等值連接運(yùn)算要比同樣關(guān)系上的笛卡兒積省很多時(shí)間。6）找出公共子表達(dá)式，如果這種重復(fù)出現(xiàn)的子表達(dá)式結(jié)果不是很大，從外存讀入結(jié)果比計(jì)算該子表達(dá)式的時(shí)間少得多，可先計(jì)算一次該子表達(dá)式并把結(jié)果寫(xiě)入中間文件是合算的。如查詢(xún)的是視圖，定義視圖的表達(dá)式就是公共子表達(dá)式的情況。關(guān)系代數(shù)等價(jià)變換規(guī)則 各種查詢(xún)語(yǔ)

8、言都可以轉(zhuǎn)換成關(guān)系代數(shù)表達(dá)式，因此查詢(xún)優(yōu)化可以轉(zhuǎn)換為對(duì)關(guān)系代數(shù)表達(dá)式的優(yōu)化。而其優(yōu)化的基礎(chǔ)是關(guān)系代數(shù)表達(dá)式的等價(jià)變換規(guī)則。 等價(jià)：等價(jià)：如果用相同的關(guān)系來(lái)代替兩個(gè)表達(dá)式中相應(yīng)的關(guān)系所得到的結(jié)果是相同的，則說(shuō)這兩個(gè)關(guān)系代數(shù)表達(dá)式E1、E2是等價(jià)的，記為E1E2。 常用的等價(jià)變換規(guī)則：常用的等價(jià)變換規(guī)則：10條（見(jiàn)書(shū)P.162-164）。 關(guān)系代數(shù)表達(dá)式的優(yōu)化原則：關(guān)系代數(shù)表達(dá)式的優(yōu)化原則：應(yīng)用等價(jià)變換規(guī)則來(lái)優(yōu)化關(guān)系表達(dá)式，使得優(yōu)化后的表達(dá)式能遵循查詢(xún)優(yōu)化的一般準(zhǔn)則，如把選擇和投影盡可能地早做（即把它們移到表達(dá)式語(yǔ)法樹(shù)的下部，葉端）。關(guān)系代數(shù)表達(dá)式的優(yōu)化算法算法：關(guān)系表達(dá)式的優(yōu)化。輸入：一個(gè)關(guān)系表

9、達(dá)式的語(yǔ)法樹(shù)。輸出：計(jì)算該表達(dá)式的程序。1）利用規(guī)則4把形如F1F2 Fn(E)變換為 F1( F2( Fn(E)。2）對(duì)每個(gè)選擇，利用規(guī)則4-8盡可能把它移到樹(shù)的葉端。3）對(duì)每個(gè)投影，利用規(guī)則3，9，10，5中的一般形式盡可能把它移向樹(shù)的葉端。4）利用規(guī)則3-5把選擇和投影的串接合并成單個(gè)選擇、單個(gè)投影或一個(gè)選擇后跟一個(gè)投影。使得多個(gè)選擇或投影能同時(shí)執(zhí)行，或在一次掃描中全部完成。5）將得到的語(yǔ)法樹(shù)的內(nèi)結(jié)點(diǎn)進(jìn)行分組。每一雙目運(yùn)算和它所有的直接祖先（ ， ）為一組；如果其后代直到葉子全是單目運(yùn)算，則也將它們并入該組；但當(dāng)雙目運(yùn)算是笛卡兒積，而且其后的選擇不能與它結(jié)合為等值連接時(shí),則一直到葉子的一

10、目運(yùn)算結(jié)點(diǎn)須單獨(dú)立一組。6）自動(dòng)生成一個(gè)程序。每組結(jié)點(diǎn)的計(jì)算是程序中的一步。各步的順序是任意的，只要保證任何一組的計(jì)算不會(huì)在它的后代組之前計(jì)算。7）執(zhí)行時(shí)從葉端依次向上進(jìn)行，每組運(yùn)算只對(duì)關(guān)系進(jìn)行一次掃描。優(yōu)化的一般步驟（1）把查詢(xún)轉(zhuǎn)換成某種內(nèi)部表示 通常是（關(guān)系代數(shù)）語(yǔ)法樹(shù)，以4.2.2節(jié)中的實(shí)例為例。（2）把語(yǔ)法樹(shù)轉(zhuǎn)換成標(biāo)準(zhǔn)（優(yōu)化）形式。 語(yǔ)法樹(shù)最終的優(yōu)化形式語(yǔ)法樹(shù)最終的優(yōu)化形式（運(yùn)用了哪些變換規(guī)則？） Sname Student.Sno=SC.Sno Sname,Sno Sno Student Cno=2 SC StudentCno=2SCSnameStudent.Sno=SC.SnoSn

11、ame, Student.Sno, SC.Sno（3）選擇低層的存取路徑 根據(jù)第（2）步得到的優(yōu)化了的語(yǔ)法樹(shù)計(jì)算關(guān)系表達(dá)式值的時(shí)候要充分考慮索引、數(shù)據(jù)的存儲(chǔ)分布等存取路徑，利用它們進(jìn)一步改善查詢(xún)效率。 優(yōu)化器查找數(shù)據(jù)字典獲得當(dāng)前數(shù)據(jù)庫(kù)狀態(tài)信息選擇字段上是否有索引連接的兩個(gè)表是否有序連接字段上是否有索引 然后根據(jù)一定的優(yōu)化規(guī)則選擇存取路徑（4）生成查詢(xún)計(jì)劃，選擇代價(jià)最小的）生成查詢(xún)計(jì)劃，選擇代價(jià)最小的 查詢(xún)計(jì)劃是由一組內(nèi)部過(guò)程組成的，這組內(nèi)部過(guò)程實(shí)現(xiàn)按某條存取路徑計(jì)算關(guān)系表達(dá)式的值。 在作連接運(yùn)算時(shí)，若兩個(gè)表(設(shè)為R1，R2)均無(wú)序，連接屬性上也沒(méi)有索引，則可以有下面幾種查詢(xún)計(jì)劃： 對(duì)兩個(gè)表作排

12、序預(yù)處理 對(duì)R1在連接屬性上建索引 對(duì)R2在連接屬性上建索引 在R1，R2的連接屬性上均建索引 對(duì)不同的查詢(xún)計(jì)劃計(jì)算代價(jià)，選擇代價(jià)最小的一個(gè)。 在計(jì)算代價(jià)時(shí)主要考慮磁盤(pán)讀寫(xiě)的I/O數(shù)，內(nèi)存CPU處理時(shí)間在粗略計(jì)算時(shí)可不考慮。實(shí)例_查詢(xún)優(yōu)化的實(shí)例 SELECT Student.Sname FROM Student,SC WHER Student.Sno=SC.Sno AND SC.Cno=2;系統(tǒng)可以用多種等價(jià)的關(guān)系代數(shù)表達(dá)式來(lái)完成這一查詢(xún)： 如 q1= sname( student.sno=o=2(studentsc) q2= sname( o=2(student sc) q3= sname(

13、student o=2(sc)這三種不同的查詢(xún)執(zhí)行策略，其查詢(xún)時(shí)間相差很大?？赏ㄟ^(guò)某種代價(jià)模型(如只計(jì)算I/O時(shí)間代價(jià))，粗略計(jì)算出各種查詢(xún)執(zhí)行方案的代價(jià)，選擇代價(jià)最小的來(lái)實(shí)現(xiàn)查詢(xún)。實(shí)例_查詢(xún)優(yōu)化的實(shí)例 讀取Student和SC表的策略Student表SC表100個(gè)SC元組內(nèi)存緩沖區(qū)中間文件10個(gè)Student元組10個(gè)連接后的元組第一個(gè)五塊第二個(gè)五塊 共一千個(gè)學(xué)生記錄 共一萬(wàn)個(gè)選課記錄 第1100個(gè)元組第101200個(gè)元組 第110個(gè)元組第1120個(gè)元組第一塊第二塊第 n 塊 Student表第1個(gè)五塊的元組 SC表第1塊的元組 SC表第2塊的元組 SC表第n塊的元組 Student表第2個(gè)五塊的元組 SC表第1塊的元組 SC表第2塊的元組 SC表第n塊的元組 Student表最后五塊的元組 SC表第1塊的元組 SC表第2塊的元組 SC表第n塊的元組 假設(shè)1：1000個(gè)學(xué)生記錄，10000個(gè)選課記錄，在內(nèi)存中存放5塊Student元組和一塊SC元組，一塊能裝10個(gè)學(xué)生記錄或100個(gè)選課記錄。 則讀取總塊數(shù)為： 1000 1000 10000 10 105 10