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

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

*2.3

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

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

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

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

DOWN出生年份*2.3.1

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

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

DOWN出生年份*2.3.1

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

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

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

1、響應(yīng)用戶查詢的一般過程

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

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

E1×E2≡E2×E1

E1E2≡E2E1

E1E2≡E2E1FF2）連接、笛卡爾積結(jié)合律

(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、關(guān)系代數(shù)表達式的優(yōu)化算法輸入：一個關(guān)系表達式的語法樹輸出：計算該表達式的程序方法：1)把σF1∧F2∧...∧Fn(E)變換為

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

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

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

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

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

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

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

5、適當(dāng)?shù)貙﹃P(guān)系文件做預(yù)處理2.4.2

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

π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ù)庫原理的學(xué)生姓名和成績

π姓名,成績（σ課程名=‘?dāng)?shù)據(jù)庫原理’∧學(xué)生.學(xué)號=學(xué)習(xí).學(xué)號∧學(xué)習(xí).課程號=課程.課程號（學(xué)生×

學(xué)習(xí)×

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