數(shù)據(jù)庫課本第四章關(guān)系系統(tǒng)及其查詢優(yōu)化

課本第四章

關(guān)系系統(tǒng)及其

查詢優(yōu)化本章要點(diǎn)本章主要介紹以下幾個(gè)問題：1.關(guān)系系統(tǒng)。2.什么是查詢優(yōu)化？3.查詢優(yōu)化的策略。4.查詢優(yōu)化的步驟。教學(xué)要求

1．了解數(shù)據(jù)庫系統(tǒng)是如何對查詢進(jìn)行優(yōu)化的。 2．深入理解查詢優(yōu)化策略；掌握用關(guān)系代數(shù)等價(jià)變換規(guī)則對關(guān)系代數(shù)查詢表達(dá)式進(jìn)行優(yōu)化的方法；學(xué)會(huì)按查詢優(yōu)化的步驟對查詢進(jìn)行優(yōu)化。4.1關(guān)系系統(tǒng)一個(gè)系統(tǒng)可定義為關(guān)系系統(tǒng)，當(dāng)且僅當(dāng)它：（1）支持關(guān)系數(shù)據(jù)結(jié)構(gòu)（二維表）。（2）支持選擇、投影和連接運(yùn)算，對這些運(yùn)算不必要求定義任何物理存取路徑。關(guān)系系統(tǒng)的分類：表式系統(tǒng)：僅支持關(guān)系數(shù)據(jù)結(jié)構(gòu)，不支持集合級操作。不算關(guān)系系統(tǒng)。（最?。╆P(guān)系系統(tǒng)：支持關(guān)系數(shù)據(jù)結(jié)構(gòu)和三種關(guān)系運(yùn)算。（Foxbase,Foxpro）關(guān)系完備的系統(tǒng)：支持關(guān)系數(shù)據(jù)結(jié)構(gòu)和所有的關(guān)系代數(shù)操作。全關(guān)系系統(tǒng)：支持關(guān)系模型的所有特征。不僅支持關(guān)系數(shù)據(jù)結(jié)構(gòu)和所有的關(guān)系代數(shù)操作，而且支持?jǐn)?shù)據(jù)結(jié)構(gòu)中域的概念，支持實(shí)體完整性和參照完整性。4.2查詢優(yōu)化在關(guān)系數(shù)據(jù)庫中，用戶只是通過命令通知計(jì)算機(jī)要做什么，而沒有明確應(yīng)該如何具體操作。因此系統(tǒng)有足夠的靈活性作出存取路徑等與查詢效率有關(guān)的選擇，即使查詢過程既省時(shí)間，又省空間，具有較高的效率。這就是查詢優(yōu)化。用戶提出要求后，系統(tǒng)會(huì)自動(dòng)根據(jù)普遍的、行之有效的優(yōu)化策略按照關(guān)系代數(shù)等價(jià)變換規(guī)則對查詢表達(dá)式進(jìn)行變換，最后得到優(yōu)化合理、效率較高的查詢方案。一、什么是查詢優(yōu)化？二、查詢優(yōu)化的一般策略例如：查詢李明選修的所有課程?？梢杂藐P(guān)系代數(shù)來表達(dá)多種不同的查詢方法。S1=πcno（σS.sno=SC.sno

∧S.sname=“李明”(S×SC))S2=πcno（σS.sname=“李明”

(SSC))S3=πcno（σS.sname=“李明”

(S）SC)三種查詢的結(jié)果是完全相同的，但三種查詢的具體操作、所占用的內(nèi)存、所消耗的時(shí)間是不相同的。顯然：

S3優(yōu)于S2優(yōu)于S1查詢優(yōu)化對減少系統(tǒng)開銷、提高運(yùn)行速度是很重要的。

我們希望在系統(tǒng)開銷盡量小的情況下對查詢進(jìn)行盡可能的優(yōu)化。一般采用以下策略： 1．選擇運(yùn)算盡早進(jìn)行。 2．投影運(yùn)算與選擇運(yùn)算同時(shí)進(jìn)行。 3．將笛卡爾積與隨后的選擇運(yùn)算合并為連接運(yùn)算。 4．投影運(yùn)算與其他運(yùn)算同時(shí)進(jìn)行。 5．尋找公共子表達(dá)式并將結(jié)果存儲(chǔ)。 6．對文件進(jìn)行預(yù)處理。(在連接的屬性上建立索引和對關(guān)系排序，然后執(zhí)行連接)三、關(guān)系代數(shù)的等價(jià)變換

關(guān)系代數(shù)表達(dá)式的優(yōu)化是查詢優(yōu)化的重要基礎(chǔ)。 所謂關(guān)系代數(shù)表達(dá)式的優(yōu)化，就是要按照一定的等價(jià)變換規(guī)則將其轉(zhuǎn)換為查詢效率更高的表達(dá)式。

1.等價(jià)如果兩個(gè)關(guān)系代數(shù)表達(dá)式的運(yùn)算結(jié)果關(guān)系完全一樣，則稱兩個(gè)關(guān)系代數(shù)表達(dá)式E1和E2等價(jià)，記作：

E1≡E2。2.變換規(guī)則

常用的關(guān)系代數(shù)等價(jià)變換規(guī)則如下：

規(guī)則1．連接或笛卡爾積的交換律設(shè)E1和E2是關(guān)系代數(shù)表達(dá)式，F(xiàn)是連接的條件，則有： E1╳E2≡E2╳E1 E1E2≡E2E1 E1FE2≡E2FE1規(guī)則2．連接或笛卡爾積的結(jié)合律 設(shè)E1、E2和E3是關(guān)系代數(shù)表達(dá)式，F(xiàn)1和F2是連接的條件，其中F1只涉及到E1和E2的屬性，F(xiàn)2只涉及到E2和E3的屬性，則有：(E1╳E2)╳E3≡E1╳(E2╳E3)(E1E2)E3≡E1(E2E3)(E1F1E2)F2E3≡E1F1(E2F2E3)規(guī)則3．投影的串接律 設(shè)E為關(guān)系代數(shù)表達(dá)式，A、B為屬性集，且A是B的子集，則有：

πA(πB(E))≡πA(E)

規(guī)則4．選擇的交換/串接律

F1和F2為選擇條件，則有： ①.選擇的交換律

σF1（σF2（E））≡σF2(σF1(

E））

②.選擇的串接律

σF1（σF2（E））≡σF1∧F2（E）規(guī)則5．選擇與投影的交換/串接律①.選擇與投影的交換律 設(shè)選擇條件F只涉及屬性A1,A2,…,An，則有：πA1,A2,…,An（σF（E））≡σF（πA1,A2,…,An（E））②選擇與投影的串接律 設(shè)選擇條件F中有不屬于A1,…,An的屬性B1,…,Bm，則有：

πA1,…,An（σF（E））≡πA1,…,An（σF （πA1,…,An,B1,…,Bm（E）））

規(guī)則6選擇對笛卡爾積的分配律 如果選擇條件F只涉及E1中的屬性：σF(E1╳E2）≡σF(E1）╳E2

如果選擇條件F=F1∧F2，且F1只涉及E1的屬性，F(xiàn)2只涉及E2的屬性：

σF（E1╳E2）≡σF1（E1）╳σF2（E2）規(guī)則7．投影對笛卡爾積的分配律 設(shè)E1和E2是關(guān)系代數(shù)表達(dá)式，Ai（i=1,2,…,n）是E1的屬性，Bj（j=1,2,…,m）是E2的屬性，則有：

πA1,…,An,B1,…,Bm(E1╳E2)≡

πA1,…,An(E1)╳πB1,…,Bm(E2)

規(guī)則8．選擇對并的分配律

設(shè)E1和E2具有相同的屬性集，則有：

σF（E1∪E2）≡σF（E1）∪σF（E2）規(guī)則9.投影對并的分配律 設(shè)E1和E2有相同的屬性集，則有：

πA1,…,An(E1∪E2)≡π

A1,…,An(E1)∪π

A1,…,An(E2)規(guī)則10.選擇對差的分配律 設(shè)E1和E2有相同的屬性集，則有：σF(E1﹣E2）≡σF（E1）-σF（E2）3.應(yīng)用舉例設(shè)圖書管理數(shù)據(jù)庫關(guān)系模式如下：Book（Title,Author,Publisher,BN）；

圖書（書名，作者，出版社，書號(hào)）Student（Name,Class,LN）；

學(xué)生（姓名，班級，借書證號(hào)）Loan（LN,BN,Date）；

借書（借書證號(hào)，書號(hào)，借書日期）三個(gè)關(guān)系的鍵碼分別是：書號(hào)BN，借書證號(hào)LN及書號(hào)和借書證號(hào)。查詢要求是：2001年元旦前借出的圖書的書名及借書學(xué)生的姓名。查詢的最基本（笨）的方法是：令：X=πR（σF（B╳S╳L））其中F代表：S.LN=L.LNANDB.BN=L.BN，形式上為選擇條件，實(shí)際上是等值連接條件；R代表T、A、P、BN、N、C、LN和D，即三個(gè)關(guān)系的屬性集。于是，查詢要求可用如下表達(dá)式來描述：πT,N（σD<20010101（X））這一原始表達(dá)式可畫成原始語法樹，如下所示.

π

T,N

σD<20010101

π

T,A,P,BN,N,C,LN,D

σB.BN=L.BNANDS.LN=L.LN

╳

╳

LS

B

⑴.按照規(guī)則——選擇的串接律，把相與的兩個(gè)選擇條件分解為兩個(gè)獨(dú)立的選擇條件。σS.LN=L.LNANDB.BN=L.BN→a)σS.LN=L.LNb)σB.BN=L.BN

⑵.利用規(guī)則——選擇與投影的交換律，把σD<20010101與πR交換。

再利用規(guī)則——選擇的交換律，把選擇σD<20010101與上一步分解的兩個(gè)選擇（實(shí)質(zhì)上是連接），按先選擇后連接的原則加以交換，σD<20010101（B╳S╳L）

由于選擇僅涉及關(guān)系L，則按照規(guī)則——選擇對笛卡爾積的分配律：B╳S╳（σD<20010101（L））⑶.由于選擇條件a)σS.LN=L.LN與關(guān)系B無關(guān)，同樣按照選擇對笛卡爾積的分配律，得：B╳（σS.LN=L.LN（S╳（σD<20010101（L））））⑷.利用規(guī)則——投影串接律，得：

πT,N（πR（…））→πT,N（…）

這時(shí)的表達(dá)式可畫成中間語法樹。

π

T,N

σB.BN=L.BN

σS.LN=L.LN

╳

╳

LS

B

σD<20010101

⑸．利用選擇與投影的串接律，對如下表達(dá)式進(jìn)行變換：πT,N（σB.BN=L.BN（…））→

π

T,N（σB.BN=L.BN（π

T,N,B.BN,L.BN（…）））

⑹．把投影πT,N,B.BN,L.BN分解為πT,B.BN和πN,L.BN，然后利用——投影對笛卡爾積的分配律，分別對相關(guān)的部分作投影：πT,N（σB.BN=L.BN（πT,B.BN（B）╳πN,L.BN（σS.LN=L.LN（S╳σD<20010101（L）））））⑺.再利用選擇與投影串接律，把投影與選擇串接，πN,L.BN（σS.LN=L.LN（S╳σD<20010101（L）））→πN,L.BN（σS.LN=L.LN（πN,L.BN,S.LN,L.LN（S╳σD<20010101（L））））把新的投影分解成πN,S.LN和π

L.BN,L.LN，然后再次利用規(guī)則7投影對笛卡爾積的分配律，把投影移入笛卡爾積：πN,S.BN（S）╳（π

L.BN,L.LN（σD<20010101（L）））優(yōu)化的查詢表達(dá)式如下：πT,N（σB.BN=L.BN（πT,B.BN（B）╳πN,L.BN（σS.LN=L.LN（πN,S.LN(S）╳（π

L.BN,L.LN（σD<20010101（L）））））））

按照習(xí)慣，把優(yōu)化的查詢表達(dá)式寫成自然連接表達(dá)式可為：πT,N（πT,B.BN（B）πN,L.BN（（πN,S.LN（S）(πL.BN,L.LN（σD<20010101（L））））））查詢優(yōu)化的一般步驟：1.把查詢轉(zhuǎn)換成一種內(nèi)部表示

通常采取的內(nèi)部表示是表達(dá)樹。例如： E1=πcno(σS.SNo=SC.SNo

ANDS.SName=’李明’（S╳SC）)

可用如下表達(dá)樹（又稱語法樹）來表示：四、查詢優(yōu)化步驟

π

cno

σS.SNo=SC.SnoANDS.SName=’李明’╳

SCS

2．利用關(guān)系代數(shù)等價(jià)變換規(guī)則以及查詢優(yōu)化的一般策略，將語法樹進(jìn)行優(yōu)化,應(yīng)該盡量先做選擇運(yùn)算。根據(jù)等價(jià)變換規(guī)則第6條，E1的關(guān)系代數(shù)語法樹可以優(yōu)化成如下的形式

π

cno

σS.SNo=SC.SNo

SC

σS.SName=’李明‘

S╳

3．選擇適當(dāng)?shù)牡蛯哟嫒÷窂? 所謂選擇低層存取路徑，指的就是要充分利用數(shù)據(jù)庫中已有的索引等信息。假如選擇條件或連接條件所涉及