數(shù)據(jù)庫原理與應用 課件 第2章 2.3-2.4查詢優(yōu)化

1與關系代數(shù)不同，關系演算是非過程化語言，它只描述所需要的信息，而不給出獲得該信息的具體過程。按照謂詞變元的不同，關系演算分為元組關系演算和域關系演算兩種。

*2.3

關系演算元組關系是以元組變量作為謂詞變元的基本對象元組關系演算語言ALPHA

共有GET、PUT、HOLD、UPDATE、DELETE、DROP6條語句操作語句工作空間名（表達式）：操作條件*2.3.1

元組關系演算查詢所有學生的數(shù)據(jù)GETW(學生)查詢學生表中有哪些院系GETW(學生.學院)查詢所有1980年以后出生的學生學號和籍貫GET

W(學生.學號,學生.籍貫):學生.出生年份>1980查詢所有學生的數(shù)據(jù)，結果按出生年份降序排序GETW(學生)

DOWN出生年份*2.3.1

元組關系演算查詢所有學生的數(shù)據(jù)GETW(學生)查詢學生表中有哪些院系GETW(學生.學院)查詢所有1980年以后出生的學生學號和籍貫GET

W(學生.學號,學生.籍貫):學生.出生年份>1980查詢所有學生的數(shù)據(jù)，結果按出生年份降序排序GETW(學生)

DOWN出生年份*2.3.1

元組關系演算5域關系演算表達式的定義用域變量代替元組變量的每一個分量，域變量的變化范圍是某個值域而不是一個關系域關系演算的查詢表達式為：{t1,t2,…,tk|P(t1,t2,…,tk)}

其中t1,t2,…,tk代表域變量，P是域演算公式。*2.3.1

域關系演算6用戶輸入查詢查詢的內部表示執(zhí)行查詢步驟向用戶報告查詢結果查詢語句的句法分析查詢優(yōu)化處理查詢

1、響應用戶查詢的一般過程

2.4查詢優(yōu)化7例：查詢學號為091502的學生選修的課程名稱。E1=π課程名(σ課程.學號=學習.學號∧學習.學號=‘091502’(課程×學習))E2=π課程名(σ課程.學號=學習.學號(課程×σ學號=‘091502’(學習)))E3=π課程名(課程∞σ學號=‘091502’(學習))查詢效率：E3>E2>E12.4.1

查詢優(yōu)化的必要性8關系代數(shù)表達式的等價變換規(guī)則1）連接、笛卡爾積交換律

E1×E2≡E2×E1

E1E2≡E2E1

E1E2≡E2E1FF2）連接、笛卡爾積結合律

(E1×E2)×E3≡E1×(E2×E3)

(E1E2)E3≡E1(E2E3)

(E1E2)E3≡E1(E2E3)F1F2F1F22.4.1

查詢優(yōu)化的必要性93、投影的串接定律(注意條件)πA1,A2,…,An(πB1,B2,…,Bm(E))≡πA1,A2,…,An(E)4、選擇的串接定律σF1(σF2(E))≡σF1∧F2(E)5、選擇與投影的交換律（注意條件）σF(πA1,A2,…,An(E))≡πA1,A2,…,An(σF(E))（F只涉及A1,A2,…,An）πA1,A2,…,An(σF(E))≡πA1,A2,…,AnσF(πA1,…,An,B1,…,Bm(E)))6、選擇與笛卡爾積的交換律σF(E1×E2)≡σF(E1)

×E2σF(E1×E2)≡σF1(E1)

×σF2(E2)σF(E1×E2)≡σF2(σF1(E1)

×E2)107、選擇與并的交換σF(E1∪E2)≡σF(E1)

∪σF(E2)8、選擇與差的交換σF(E1-E2)≡σF(E1)

-σF(E2)9、投影與笛卡爾積的交換律πA1,A2,…,An,B1,B2,…,Bm(E1×E2)≡πA1,A2,…,An(E1)×πB1,B2,…,Bm(

E2)10、投影與并的交換πA1,A2,…,An(E1∪E2)≡πA1,A2,…,An(E1)∪πA1,A2,…,An(E2)2.4.1

查詢優(yōu)化的必要性115、關系代數(shù)表達式的優(yōu)化算法輸入：一個關系表達式的語法樹輸出：計算該表達式的程序方法：1)把σF1∧F2∧...∧Fn(E)變換為

σF1(σF2(…(σFn(E))…))

2)對每一個選擇盡可能把它移到樹的葉端。

3)對每一個投影盡可能把它移到樹的葉端。4)合并選擇和投影或一個選擇后跟一個投影。5)將得到的語法樹的內節(jié)點分組。(每一雙目運算和它所有的直接祖先為一組。6)生成一個程序，每組節(jié)點的計算是程序中的一步。求值順序為先子孫，后祖先。[規(guī)則4][規(guī)則3,5,9,10][規(guī)則4-8][規(guī)則3-5]12

1、盡可能早地執(zhí)行選擇操作（減少中間運算結果）

2、合并笛卡爾積和其后的選擇操作，使之稱為一個連接運算

3、合并連續(xù)的選擇和投影操作，以免分開運算造成多次掃描文件，從而節(jié)省了操作時間

4、找出表達式里的公共子表達式。

5、適當?shù)貙﹃P系文件做預處理2.4.2

查詢優(yōu)化的策略和算法13例：求001001號學生所選修的課程名及成績

πCN,G

（σSC.S#=‘001001’∧SC.C#=C.C#

（SC×C））πCN,GσSC.S#=‘001001’∧SC.C#=C.C#SCC×2.4.2

查詢優(yōu)化的策略和算法14πCN,GσSC.C#=C.C#SCC×σSC.S#=‘001001’πCN,GσSC.C#=C.C#SCC×σSC.S#=‘001001’選擇的串接定律選擇與笛卡爾積的交換15

πCN,GσSC.C#=C.C#SCC×σSC.S#=‘001001’πCN,G,SC.C#,C.C#5、選擇與投影的交換律σF(πA1,A2,…,An(E))≡πA1,A2,…,An(σF(E))（F只涉及A1,A2,…,An）πA1,A2,…,An(σF(E))≡πA1,A2,…,AnσF(πA1,…,An,B1,…,Bm(E)))16πCN,GσSC.C#=C.C#SCC×σSC.S#=‘001001’πC#,CNπG,C#

投影與笛卡爾積的交換律17∏CN,G（∏C#，G（σSC.S#=‘001001’（SC））∞∏CN，C#（C））優(yōu)化后的表達式18例：查詢選修了數(shù)據(jù)庫原理的學生姓名和成績

π姓名,成績（σ課程名=‘數(shù)據(jù)庫原理’∧學生.學號=學習.學號∧學習.課程號=課程.課程號（學生×

學習×

課程））π姓名,成績（σ課程名=‘數(shù)據(jù)庫原理’（學生學習課程））19Π姓名,成績σ課程名=‘數(shù)據(jù)庫原理’∧學生.學號=學習.學號∧學習.課程號=課程.課程號課程××學生學習20Π姓名,成績σ學習.課程號=課程.課程號課程××學生學習σ課程名=‘數(shù)據(jù)庫原理’σ學生.學號=學習.學號規(guī)則4、6選擇的串接選擇和笛卡爾積交換21Π姓名,成績σ學習.課程號=課程.課程號課程××學生學習σ課程名=‘數(shù)據(jù)庫原理’σ學生.學號=學習.學號Π姓名,成績,學習.課程號,課程.課程號規(guī)則5選擇和投影交換22Π姓名,成績σ學習.課程號=課程.課程號課程××學生學習σ課程名=‘數(shù)據(jù)庫原理’σ學生.學號=學習.學號Π姓名,課程號，成績Π課程號規(guī)則9投影和笛卡爾積交換23規(guī)則5選擇和投影交換Π姓名,成績σ學習.課程號=課程.課程號課程××學生學習σ課程名=‘數(shù)據(jù)庫原理’σ學生.學號=學習.學號Π課程號Π姓名,學生.學號,學習.學號,課程號，成績Π姓名,課程號，成績24規(guī)則9投影和笛卡爾積交換Π姓名,成績σ學習.課程號=課程.課程號課程××學生學習σ課程名=‘數(shù)據(jù)庫原理’σ學生.學號=學習.學號Π課程號Π姓名,學號Π課程號,學號,成績