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

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

*2.3

關(guān)系演算元組關(guān)系是以元組變量作為謂詞變?cè)幕緦?duì)象元組關(guān)系演算語(yǔ)言ALPHA

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

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

W(學(xué)生.學(xué)號(hào),學(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é)號(hào)和籍貫GET

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

DOWN出生年份*2.3.1

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

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

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

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

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

查詢優(yōu)化的必要性8關(guān)系代數(shù)表達(dá)式的等價(jià)變換規(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ù)表達(dá)式的優(yōu)化算法輸入：一個(gè)關(guān)系表達(dá)式的語(yǔ)法樹(shù)輸出：計(jì)算該表達(dá)式的程序方法：1)把σF1∧F2∧...∧Fn(E)變換為

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

2)對(duì)每一個(gè)選擇盡可能把它移到樹(shù)的葉端。

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

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

2、合并笛卡爾積和其后的選擇操作，使之稱為一個(gè)連接運(yùn)算

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

4、找出表達(dá)式里的公共子表達(dá)式。

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

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

π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)化后的表達(dá)式18例：查詢選修了數(shù)據(jù)庫(kù)原理的學(xué)生姓名和成績(jī)

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

學(xué)習(xí)×

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