1、本章內(nèi)容提要 支持關(guān)系模型的數(shù)據(jù)庫(kù)系統(tǒng)是關(guān)系系統(tǒng)。 由于支持關(guān)系模型的程度不同，實(shí)際的數(shù)據(jù)庫(kù)系統(tǒng)可以分為表式系統(tǒng)、（最?。╆P(guān)系系統(tǒng)、關(guān)系完備的和全關(guān)系的四類系統(tǒng)。 查詢處理是數(shù)據(jù)庫(kù)管理系統(tǒng)的核心，而查詢優(yōu)化技術(shù)又是查詢處理的關(guān)鍵技術(shù)。查詢優(yōu)化一般可分為代數(shù)優(yōu)化和物理優(yōu)化。代數(shù)優(yōu)化是指關(guān)系代數(shù)表達(dá)式的優(yōu)化，物理優(yōu)化則是指存取路樣和低層操作算法指示變量的選擇。,第四章 關(guān)系系統(tǒng)及其查詢優(yōu)化,本章重點(diǎn)： 關(guān)系系統(tǒng)中查詢優(yōu)化的概念、基本原理和技術(shù)； 查詢優(yōu)化的一般準(zhǔn)則； 查詢優(yōu)化的一般步驟。 本章難點(diǎn)： 查詢優(yōu)化的一般準(zhǔn)則； 查詢優(yōu)化的一般步驟。,第四章 關(guān)系系統(tǒng)及其查詢優(yōu)化,關(guān)系模型的三要素：關(guān)系數(shù)

2、據(jù)結(jié)構(gòu) 關(guān)系操作 關(guān)系的完整性 關(guān)系系統(tǒng)和關(guān)系模型是兩個(gè)密切相關(guān)而又不同的概念。支持關(guān)系模型的數(shù)據(jù)庫(kù)管理系統(tǒng)稱為關(guān)系系統(tǒng)。但是關(guān)系模型中并非每一部分都是同等重要的，所以我們不苛求完全支持關(guān)系模型的系統(tǒng)才能稱為關(guān)系系統(tǒng)。因此，我們給出一個(gè)關(guān)系系統(tǒng)的最小要求以及分類的定義。,第四章 關(guān)系系統(tǒng)及其查詢優(yōu)化 4.1 關(guān)系系統(tǒng),4.1.1 關(guān)系系統(tǒng)的定義 一個(gè)系統(tǒng)可定義為關(guān)系系統(tǒng)，當(dāng)且僅當(dāng)它： 1.支持關(guān)系關(guān)系數(shù)據(jù)庫(kù)（關(guān)系數(shù)據(jù)結(jié)構(gòu)）； 2.支持選擇、投影和（自然）連接運(yùn)算，對(duì)這些運(yùn)算不必要求定義任何物理存取路徑。 系統(tǒng)要進(jìn)行查詢優(yōu)化，以獲得較好的性能。這正是關(guān)系系統(tǒng)實(shí)施的關(guān)鍵技術(shù)。,第四章 關(guān)系系統(tǒng)及其

3、查詢優(yōu)化 4.1 關(guān)系系統(tǒng),4.1.2 關(guān)系系統(tǒng)的分類 4.1.1定義的關(guān)系系統(tǒng)是關(guān)系系統(tǒng)的最小要求，許多實(shí)際系統(tǒng)都不同程度地超過(guò)了這些要求。 按照E.F.Codd的思想，可以把關(guān)系系統(tǒng)分類分為四類： 1. 表式系統(tǒng) 2. (最小）關(guān)系系統(tǒng) 3. 關(guān)系完備的系統(tǒng) 4. 全關(guān)系系統(tǒng),第四章 關(guān)系系統(tǒng)及其查詢優(yōu)化4.1 關(guān)系系統(tǒng),4.1.3 全關(guān)系系統(tǒng)的十二條基本準(zhǔn)則 準(zhǔn)則0 一個(gè)關(guān)系型的DBMS必須能完全通過(guò)它的關(guān)系能力來(lái)管理數(shù)據(jù)庫(kù)。準(zhǔn)則0是下面十二條準(zhǔn)則的基礎(chǔ)。 準(zhǔn)則1 信息準(zhǔn)則。 準(zhǔn)則2 保證訪問(wèn)準(zhǔn)則。依靠表名、主碼和列名的組合，保證能以邏輯方式訪問(wèn)關(guān)系數(shù)據(jù)庫(kù)中的每個(gè)數(shù)據(jù)項(xiàng)(分量值)。 準(zhǔn)則

4、3 空值的系統(tǒng)化處理。 準(zhǔn)則4 基于關(guān)系模型的動(dòng)態(tài)的聯(lián)機(jī)數(shù)據(jù)字典。 準(zhǔn)則5 統(tǒng)一的數(shù)據(jù)子語(yǔ)言準(zhǔn)則。,第四章 關(guān)系系統(tǒng)及其查詢優(yōu)化4.1 關(guān)系系統(tǒng),第四章 關(guān)系系統(tǒng)及其查詢優(yōu)化 4.1 關(guān)系系統(tǒng),4.1.3 全關(guān)系系統(tǒng)的十二條基本準(zhǔn)則 準(zhǔn)則6 視圖更新準(zhǔn)則。 準(zhǔn)則7 高級(jí)的插入、修改和刪除操作。 準(zhǔn)則8 數(shù)據(jù)物理獨(dú)立性。 準(zhǔn)則9 數(shù)據(jù)邏輯獨(dú)立性。 準(zhǔn)則l0 數(shù)據(jù)完整性的獨(dú)立性。 準(zhǔn)則11 分布獨(dú)立性。 準(zhǔn)則12 無(wú)破壞準(zhǔn)則,4.2.1 關(guān)系系統(tǒng)及其查詢優(yōu)化 查詢優(yōu)化在關(guān)系數(shù)據(jù)庫(kù)中有非常重要的地位。 關(guān)系數(shù)據(jù)庫(kù)系統(tǒng)和非過(guò)程化的SQL語(yǔ)言能夠成功，關(guān)鍵是得益于查詢優(yōu)化的發(fā)展。 關(guān)系系統(tǒng)的查詢優(yōu)化既是

5、RDBMS實(shí)現(xiàn)的關(guān)鍵技術(shù)又是關(guān)系系統(tǒng)的優(yōu)點(diǎn)所在。它減輕了用戶選擇存取路徑的負(fù)擔(dān)。用戶只要提出干什么，不必指出怎么干。 查詢優(yōu)化的優(yōu)點(diǎn)不僅在于用戶不必考慮如何最好地表達(dá)查詢以獲得較好的效率，而且在于系統(tǒng)可以比用戶程序的“優(yōu)化”做得更好。,第四章 關(guān)系系統(tǒng)及其查詢優(yōu)化 4.2 關(guān)系數(shù)據(jù)庫(kù)系統(tǒng)的查詢優(yōu)化,關(guān)系數(shù)據(jù)庫(kù)查詢優(yōu)化的總目標(biāo)是：選擇有效的策略，求得給定關(guān)系表達(dá)式的值。 實(shí)際系統(tǒng)對(duì)查詢優(yōu)化的具體實(shí)現(xiàn)一般可以歸納為四個(gè)步驟： 1、將查詢轉(zhuǎn)換成某種內(nèi)部表示，通常是語(yǔ)法樹。 2、根據(jù)一定的等價(jià)變換規(guī)則把語(yǔ)法樹轉(zhuǎn)換成標(biāo)準(zhǔn)（優(yōu)化）形式。 3、選擇低層的操作算法。 4、生成查詢計(jì)劃（查詢執(zhí)行方案 ）。,第四

6、章 關(guān)系系統(tǒng)及其查詢優(yōu)化 4.2 關(guān)系數(shù)據(jù)庫(kù)系統(tǒng)的查詢優(yōu)化,查詢優(yōu)化有兩種基本策略：基于語(yǔ)法的查詢優(yōu)化（結(jié)構(gòu)優(yōu)化） 基于代價(jià)的查詢優(yōu)化。 基于代價(jià)的優(yōu)化算法： 在集中式數(shù)據(jù)庫(kù)中，查詢的執(zhí)行開銷主要包括： 總代價(jià) = I/O代價(jià) + CPU代價(jià) 在多用戶環(huán)境下： 總代價(jià) = I/O代價(jià) + CPU代價(jià) + 內(nèi)存代價(jià) 4.2.2 一個(gè)實(shí)例 （P159-161） 一個(gè)簡(jiǎn)單的例子，說(shuō)明為什么要進(jìn)行查詢優(yōu)化。 例 求選修了2號(hào)課程的學(xué)生姓名。用SQL語(yǔ)言表達(dá)： SELECT Student.Sname FROM Student，SC WHERE Student.Sno = SC.Sno AND SC.C

7、no = 2；,第四章 關(guān)系系統(tǒng)及其查詢優(yōu)化 4.2 關(guān)系數(shù)據(jù)庫(kù)系統(tǒng)的查詢優(yōu)化,4.2.3 查詢優(yōu)化的一般準(zhǔn)則 下面的優(yōu)化策略一般能提高查詢效率,但不一定是所有策略中最優(yōu)的。其實(shí)優(yōu)化一詞并不確切，也許改進(jìn)或改善更恰當(dāng)些。 l. 選擇運(yùn)算應(yīng)盡可能先做。 2.在執(zhí)行連接前對(duì)關(guān)系適當(dāng)?shù)仡A(yù)處理。 3.把投影運(yùn)算和選擇運(yùn)算同時(shí)進(jìn)行。 4.把投影同其前或其后的雙目運(yùn)算結(jié)合起來(lái)，沒(méi)有必要為了去掉某些字段而掃描一遍關(guān)系。 5.杷某些選擇同在它前面要執(zhí)行的笛卡爾積結(jié)合起來(lái)成為一個(gè)連接運(yùn)算。 6.找出公共子表達(dá)式。,第四章 關(guān)系系統(tǒng)及其查詢優(yōu)化 4.2 關(guān)系數(shù)據(jù)庫(kù)系統(tǒng)的查詢優(yōu)化,第四章 關(guān)系系統(tǒng)及其查詢優(yōu)化4.2

8、 關(guān)系數(shù)據(jù)庫(kù)系統(tǒng)的查詢優(yōu)化,關(guān)系代數(shù)表達(dá)式的優(yōu)化是查詢優(yōu)化的基本課題。 兩個(gè)關(guān)系表達(dá)式的等價(jià) 常用的等價(jià)變換規(guī)則有： l. 連接、笛卡爾積交換律 2.連接、笛卡爾積的結(jié)合律 3.投影的串接定律 4.選擇的串接定律 5.選擇與投影的交換律 6.選擇與笛卡爾積的交換律 7.選擇與并的交換 8.選擇與差運(yùn)算的交換 9.投影與笛卡爾積的交換 l0.投影與并的交換,第四章 關(guān)系系統(tǒng)及其查詢優(yōu)化 4.2 關(guān)系數(shù)據(jù)庫(kù)系統(tǒng)的查詢優(yōu)化,4.2.5 關(guān)系代數(shù)表達(dá)式的優(yōu)化算法 可以應(yīng)用上面的變換法則來(lái)優(yōu)化關(guān)系表達(dá)式，使優(yōu)化后的表達(dá)式能遵循4.2.3中的一般原則。 關(guān)系表達(dá)式的優(yōu)化算法：關(guān)系表達(dá)式的優(yōu)化。 輸入：一個(gè)

9、關(guān)系表達(dá)式的語(yǔ)法樹。 輸出：計(jì)算該表達(dá)式的程序。 方法： 利用規(guī)則(4)把形如 F1F2.Fn(E)變換為 F1( F2(.( Fn(E).) 對(duì)每一個(gè)選擇，利用規(guī)則(4)（8）盡可能把它移到樹的葉端。 對(duì)每一個(gè)投影利用規(guī)則(3)，(9)，(l0)，(5)中的一般形式盡可能把它移向樹的葉端。 利用規(guī)則(3)(5)把選擇和投影的串接合并成單個(gè)選擇、單個(gè)投影或一個(gè)選擇后跟一個(gè)投影。 把上述得到的語(yǔ)法樹的內(nèi)節(jié)點(diǎn)分組。 生成一個(gè)程序，每組結(jié)點(diǎn)的計(jì)算是程序中的一步。,第四章 關(guān)系系統(tǒng)及其查詢優(yōu)化 4.2 關(guān)系數(shù)據(jù)庫(kù)系統(tǒng)的查詢優(yōu)化,4.2.6 優(yōu)化的一般步驟 各個(gè)關(guān)系系統(tǒng)的優(yōu)化方法不盡相同,大致的步驟可以歸納如下: l. 把查詢轉(zhuǎn)換成某種內(nèi)部表示 2. 把語(yǔ)法樹轉(zhuǎn)換成標(biāo)淮(優(yōu)化)形式 3. 選擇低層的存取路徑 4. 生成查詢計(jì)劃，選擇代價(jià)最小的,第四章 關(guān)系系統(tǒng)及其查詢優(yōu)化 4.2 關(guān)系數(shù)據(jù)庫(kù)系統(tǒng)的查詢優(yōu)化,例：查詢優(yōu)化語(yǔ)法樹：Select sname from student,sc where student.sno =s.sno and c