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

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

9.1關(guān)系系統(tǒng)

9.2關(guān)系數(shù)據(jù)庫系統(tǒng)的查詢優(yōu)化

1

:第九章關(guān)系系統(tǒng)及其查詢優(yōu)化

,'------------------------------------------------------------

，9.1關(guān)系系統(tǒng)

:9.2關(guān)系數(shù)據(jù)庫系統(tǒng)的查詢優(yōu)化

2

：：9.1關(guān)系系統(tǒng)

9?關(guān)系模型的三個基本要素

-關(guān)系數(shù)據(jù)結(jié)構(gòu)；關(guān)系的完整性；關(guān)系操作

:?支持關(guān)系模型的數(shù)據(jù)庫系統(tǒng)稱為關(guān)系系統(tǒng)。但

?關(guān)系模型中并非每一部分都是同等重要的，所

?以并不苛求一個實際的關(guān)系數(shù)據(jù)庫系統(tǒng)必須完

?全支持關(guān)系模型，也不苛求完全支持關(guān)系模型

?的系統(tǒng)才能稱為關(guān)系系統(tǒng)。因此，可以給出一

?個關(guān)系系統(tǒng)的最小要求以及分類的定義。

3

：9.1關(guān)系系統(tǒng)

??9.1.1關(guān)系系統(tǒng)的定義

.

??9.L2關(guān)系系統(tǒng)的分類

：9.1關(guān)系系統(tǒng)

:?9.1.1關(guān)系系統(tǒng)的定義

??9.L2關(guān)系系統(tǒng)的分類

5

：911關(guān)系系統(tǒng)的定義

,?一個系統(tǒng)可定義為關(guān)系系統(tǒng)，當且僅當

:它：

?-支持關(guān)系數(shù)據(jù)庫（關(guān)系數(shù)據(jù)庫結(jié)構(gòu)）

?-支持選擇、投影和（自然）連接運算，對這

?些運算不必要求定義任何物理存取路徑。

6

：911關(guān)系系統(tǒng)的定義

，?說明

-除了要支持關(guān)系數(shù)據(jù)結(jié)構(gòu)外，還必須支持選擇、投

?影、連接運算，用戶使用才方便，才能提高用戶的

?生產(chǎn)率。提高用戶生產(chǎn)率正是關(guān)系系統(tǒng)的主要目標

,之一。

.?-依賴物理存取路徑來實現(xiàn)關(guān)系運算就降低或喪失了

e數(shù)據(jù)的物理獨立性。不依賴物理存取路徑來實現(xiàn)關(guān)

?系運算就要求關(guān)系系統(tǒng)自動地選擇路徑。為此系統(tǒng)

,要進行查詢優(yōu)化，以獲得較好的性能。這正是關(guān)系

?系統(tǒng)實施的關(guān)鍵技術(shù)。

7

：911關(guān)系系統(tǒng)的定義

?-要求關(guān)系系統(tǒng)支持三種最主要的運算而不是

?關(guān)系代數(shù)的全部運算功能，是因為它們是最

*有用的運算功能，能解決絕大部分的的實際

?問題。

8

：9.1關(guān)系系統(tǒng)

:?9.1.1關(guān)系系統(tǒng)的定義

??9.L2關(guān)系系統(tǒng)的分類

9

：9.1.2關(guān)系系統(tǒng)的分類

?---------------------------------------

??上節(jié)定義的關(guān)系系統(tǒng)是關(guān)系系統(tǒng)的最小

:要求，許多實際系統(tǒng)，都不同程度地超

?過了這些要求

??可以把關(guān)系系統(tǒng)分類：

:-表式系統(tǒng)

,僅支持關(guān)系（即表）數(shù)據(jù)結(jié)構(gòu)，不支持集合

?級的操作。表式系統(tǒng)不是關(guān)系系統(tǒng)

10

-（最?。╆P(guān)系系統(tǒng)

上節(jié)定義的關(guān)系系統(tǒng)，它們僅支持關(guān)系數(shù)據(jù)

結(jié)構(gòu)和三種關(guān)系操作。許多微機關(guān)系數(shù)據(jù)庫

系統(tǒng)如FoxBase,FoxPro等就屬于這一類。

-關(guān)系完備的系統(tǒng)

支持關(guān)系數(shù)據(jù)結(jié)構(gòu)前所有的關(guān)系代數(shù)操作

（功能上與關(guān)系代數(shù)等價）。

-全關(guān)系系統(tǒng)

支持關(guān)系模型的所有特征。

11

:第九章關(guān)系系統(tǒng)及其查詢優(yōu)化

,'----------------------------------------------------------------

?9.1關(guān)系系統(tǒng)

:9.2關(guān)系數(shù)據(jù)庫系統(tǒng)的查詢優(yōu)化

12

：9.2關(guān)系數(shù)據(jù)庫系統(tǒng)的查詢優(yōu)化

??查詢優(yōu)化在關(guān)系數(shù)據(jù)庫系統(tǒng)中有著非常重要的

?地位。關(guān)系數(shù)據(jù)庫系統(tǒng)和非結(jié)構(gòu)化的SQL語言

?能夠取得巨大的成功，關(guān)鍵是得益于查詢優(yōu)化

.技術(shù)的發(fā)展。關(guān)系查詢優(yōu)化是影響RDBMS性

：能的關(guān)鍵因素。

??關(guān)系系統(tǒng)為了達到用戶可接受的性能必須進行

?查詢優(yōu)化。關(guān)系表達式的語義級別很高，使關(guān)

?系系統(tǒng)可以從關(guān)系表達式中分析查詢語義，提

?供了執(zhí)行查詢優(yōu)化的可能性。

13

：9.2關(guān)系數(shù)據(jù)庫系統(tǒng)的查詢優(yōu)化

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

:?9.2.2一個實例

:?9.2.3查詢優(yōu)化的一般準則

:?9.2.4關(guān)系代數(shù)等價變換規(guī)則

，?9.2.5關(guān)系代數(shù)表達式的優(yōu)化算法

Z?9.2.6優(yōu)化的一般步驟

14

：9.2關(guān)系數(shù)據(jù)庫系統(tǒng)的查詢優(yōu)化

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

:?9.2.2一個實例

:?9.2.3查詢優(yōu)化的一般準則

:?9.2.4關(guān)系代數(shù)等價變換規(guī)則

，?9.2.5關(guān)系代數(shù)表達式的優(yōu)化算法

Z?9.2.6優(yōu)化的一般步驟

15

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

??關(guān)系系統(tǒng)的查詢優(yōu)化既是RDBMS實現(xiàn)的

,關(guān)鍵技術(shù)又是關(guān)系系統(tǒng)的優(yōu)點所在。

:?查詢優(yōu)化的優(yōu)點在于用戶不必考慮如何

a最好地表達查詢以獲得較好的效率，而

；?且在于系統(tǒng)可以比用戶程序的“優(yōu)化”

?做得更好。這是因為：

?-優(yōu)化器可以從數(shù)據(jù)字典中獲得許多用戶程序

,難以獲得的統(tǒng)計信息，并根據(jù)這些信息選擇

?有效的執(zhí)行計劃。

16

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

?-如果數(shù)據(jù)庫的物理統(tǒng)計信息改變了，系統(tǒng)可

?以自動對查詢進行重新優(yōu)化以選擇相適應(yīng)的

?執(zhí)行計劃。不必重寫程序。

:-優(yōu)化器可以考慮數(shù)百種不同的執(zhí)行計劃，是

?程序員無法做到的。

?-優(yōu)化器中包括了許多復(fù)雜的優(yōu)化技術(shù)，系統(tǒng)

?的自動優(yōu)化相當于使得所有人都擁有這些優(yōu)

?化技術(shù)。

■17

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

??關(guān)系數(shù)據(jù)庫查詢優(yōu)化的總目標是：

:選擇有效的策略，求得給定關(guān)系表達式的值。

??實際系統(tǒng)對查詢優(yōu)化的具體實現(xiàn)步驟：

:-將查詢轉(zhuǎn)換成某種內(nèi)部表示，語法樹。

:-根據(jù)一定的等價變換規(guī)則把語法樹轉(zhuǎn)換成標

?準（優(yōu)化）形式。

-選擇低層的操作算法。對于語法樹中的每一

個操作選擇具體的執(zhí)行算法。

18

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

?-生成查詢計劃（查詢執(zhí)行方案）。通常執(zhí)行

?方案有多個，需要對每個執(zhí)行計劃計算代價,

:從中選擇代價最小的一個。

:?目前的商品化RDBMS大都采用基于代價

一的優(yōu)化算法

?總代價=1/0代價+CPU代價+內(nèi)存代價

19

：9.2關(guān)系數(shù)據(jù)庫系統(tǒng)的查詢優(yōu)化

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

:?9.2.2一個實例

:?9.2.3查詢優(yōu)化的一般準則

:?9.2.4關(guān)系代數(shù)等價變換規(guī)則

，?9.2.5關(guān)系代數(shù)表達式的優(yōu)化算法

Z?9.2.6優(yōu)化的一般步驟

20

:9.2.2一個實例

??例求選修了2號課程的學(xué)生姓名。

:用SQL語言表達：

?SELECTStudent.Sname

?FROMStudent,SC

:WHEREStudent.Sno=SC.SnoANDSC.Cno=625

?假設(shè)有1000個學(xué)生記錄，10000個選課記

?錄，50個人選修了2號課程

?9.2.2一個實例

系統(tǒng)可以用多種等價的關(guān)系表達式來完成這一

查詢：

兀SnameStudent.Sno=SC.Sno/\SC.Cno=，2(StudentXSC))

兀sname(OSC.Cno=，2'(StudentxSC))

兀Sname(StudentoSC.Cno=，2(sc))

22

:9.2.2一個實例

??在進行連接運算時，要在內(nèi)存中讀入若

:干塊的Student元組和SC元組，然后進行

?連接。設(shè)一個塊能裝入10個Student元組

,或100個SC元組，在內(nèi)存中存放5塊

?Student元組和1塊SC元組，同時假設(shè)塊

:的讀寫速度為每秒20塊。以此計算在上

?面的3種情況中，完成查詢所需要的時間

?為：

23

:9.2.2一個實例

■?第一種情況：約105s

?-廣義笛卡爾積：105+5X104s

?-作選擇操作：5X104s

?-作投影：

??第二種情況：約205s

:?第三種情況：約10s

.-如果Student表在Sno上有索引，SC表在Cno上有索

*弓I,用時會減少到幾秒。

:?由此可見查詢優(yōu)化是非常必要的。

24

：9.2關(guān)系數(shù)據(jù)庫系統(tǒng)的查詢優(yōu)化

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

:?9.2.2一個實例

:?9.2.3查詢優(yōu)化的一般準則

:?9.2.4關(guān)系代數(shù)等價變換規(guī)則

，?9.2.5關(guān)系代數(shù)表達式的優(yōu)化算法

Z?9.2.6優(yōu)化的一般步驟

25

：923查詢優(yōu)化的一般準則

?1、選擇運算應(yīng)盡可能先做。在優(yōu)化策略中這是

?最重要、最基本的一條。

:2、在執(zhí)行連接前對關(guān)系適當?shù)念A(yù)處理

U-在連接屬性上建立索引（索引連接方法）

、-對關(guān)系排序（排序合并連接方法）

3、把投影運算和選擇運算同時進行。在對同一

?個關(guān)系進行若干投影和選擇運算時，則可以

?在掃描此關(guān)系時同時完成所有的這些運算。

■

26

：923查詢優(yōu)化的一般準則

?4、把投影同其前或其后的雙目運算結(jié)合起來。

:5、把某些選擇同它前面要執(zhí)行的笛卡爾積結(jié)合

:起來成為一個連接運算。

?6、找出公共子表達式。如果這種重復(fù)出現(xiàn)的子

一表達式的結(jié)果不是很大的關(guān)系，而且從外存中

?讀入這個關(guān)系比計算子表達式的時間少得多，

?則先計算一次公共子表達式并把結(jié)果寫入中間

?文件是核算的。例如視圖就是公共子表達式。

27

：9.2關(guān)系數(shù)據(jù)庫系統(tǒng)的查詢優(yōu)化

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

:?9.2.2一個實例

:?9.2.3查詢優(yōu)化的一般準則

:?9.2.4關(guān)系代數(shù)等價變換規(guī)則

，?9.2.5關(guān)系代數(shù)表達式的優(yōu)化算法

Z?9.2.6優(yōu)化的一般步驟

28

：924關(guān)系代數(shù)等價變換規(guī)則

??查詢語言都可以轉(zhuǎn)換成關(guān)系代數(shù)表達式，關(guān)系

?代數(shù)表達式的優(yōu)化是查詢優(yōu)化的基本課題。研

?究關(guān)系代數(shù)表達式的優(yōu)化最好從研究關(guān)系代數(shù)

:表達式的等價變換規(guī)則開始。

：?所謂關(guān)系代數(shù)表達式的等價是指用相同的關(guān)系

?代替兩個表達式中相應(yīng)的關(guān)系所得到的結(jié)果是

?相同的。

,?兩個關(guān)系表達式Ei和E2等價，記為EI=E2。

29

：9.2.4關(guān)系代數(shù)等價變換規(guī)則

??常用的等價變換規(guī)則有：

:1.連接、笛卡爾積交換律

?2.連接、笛卡爾積的結(jié)合律

:3.投影的串接定律

?4.選擇的串接定律

:5.選擇與投影的交換律

30

：9.2.4關(guān)系代數(shù)等價變換規(guī)則

?6.選擇與笛卡爾積的交換律

:7.選擇與并的交換

8.選擇與差的交換

:9.投影與笛卡爾積的交換

，10.投影與并的交換

31

：9.2關(guān)系數(shù)據(jù)庫系統(tǒng)的查詢優(yōu)化

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

:?9.2.2一個實例

:?9.2.3查詢優(yōu)化的一般準則

:?9.2.4關(guān)系代數(shù)等價變換規(guī)則

，?9.2.5關(guān)系代數(shù)表達式的優(yōu)化算法

Z?9.2.6優(yōu)化的一般步驟

32

：9.2.5關(guān)系代數(shù)表達式的優(yōu)化算法

??算法：關(guān)系表達式的優(yōu)化

:?輸入：一個關(guān)系表達式的語法樹

,?輸出：計算該表達式的程序

:?方法：

l.—變換OF1AF2A...AFn(￡)為OF19F2(…9Fn(石)).??))

?-對每一個選擇，盡可能把它移到