分布式數(shù)據(jù)庫(kù)第四章

1、分布式數(shù)據(jù)庫(kù)中的查詢(xún)處理和優(yōu)化 -分布式數(shù)據(jù)庫(kù)的查詢(xún)處理和優(yōu)化 4.1 分布式查詢(xún)優(yōu)化概述 4.2 分布式查詢(xún)優(yōu)化的準(zhǔn)則和代價(jià)估算 4.3 分布式查詢(xún)策略的比較分析1. 分布式查詢(xún)優(yōu)化概述 1.1 分布式查詢(xún)優(yōu)化目標(biāo) 遇到的查詢(xún)處理問(wèn)題： 將查詢(xún)轉(zhuǎn)換為代數(shù)表達(dá)式 集中式 在所有等價(jià)表達(dá)式中選擇最優(yōu)表達(dá)式 集中式中所遇到的問(wèn)題 分布式 站點(diǎn)之間交換數(shù)據(jù)的操作 選擇最優(yōu)的執(zhí)行站點(diǎn) 數(shù)據(jù)被傳送的方式1. 分布式查詢(xún)優(yōu)化概述 1.1 分布式查詢(xún)優(yōu)化目標(biāo) 集中式數(shù)據(jù)庫(kù)的查詢(xún)優(yōu)化：查詢(xún)優(yōu)化按照優(yōu)化的層次分類(lèi) ： 代數(shù)優(yōu)化代數(shù)優(yōu)化：指關(guān)系代數(shù)表達(dá)式的優(yōu)化，即按照一定的規(guī)則，改變代數(shù)表達(dá)式中操作的次序和組合，

2、使查詢(xún)執(zhí)行更高效； 物理優(yōu)化物理優(yōu)化：指存取路徑和底層操作算法的選擇。1. 分布式查詢(xún)優(yōu)化概述 1.1 分布式查詢(xún)優(yōu)化的目標(biāo)1. 分布式查詢(xún)優(yōu)化概述1.2 分布式查詢(xún)優(yōu)化的準(zhǔn)則和代價(jià)估算查詢(xún)優(yōu)化準(zhǔn)則：使得通訊費(fèi)用最低和響應(yīng)時(shí)間最短，即以最小的總代價(jià)，在最短的響應(yīng)時(shí)間內(nèi)獲得需要的數(shù)據(jù)。 1. 通訊費(fèi)用與所傳輸?shù)臄?shù)據(jù)量和通信次數(shù)有關(guān)，與分布式數(shù)據(jù)庫(kù)系統(tǒng)基于的通信網(wǎng)絡(luò)類(lèi)型有關(guān) 2. 響應(yīng)時(shí)間是從提交查詢(xún)到完成查詢(xún)所需時(shí)間，其和通信時(shí)間有關(guān)，也與局部處理時(shí)間有關(guān)查詢(xún)代價(jià)分析：1.遠(yuǎn)程通訊網(wǎng)絡(luò) 局部處理時(shí)間可以忽略不計(jì)，減少通訊代價(jià)是主要目標(biāo)2.高速局域網(wǎng) 傳輸時(shí)間比局部處理時(shí)間要短很多，以響應(yīng)時(shí)間作為

3、優(yōu)化目標(biāo)，局部處理時(shí)間是關(guān)鍵1. 分布式查詢(xún)優(yōu)化概述1.2 分布式查詢(xún)優(yōu)化的準(zhǔn)則和代價(jià)估算查詢(xún)代價(jià)的估算方法- 設(shè)一個(gè)查詢(xún)執(zhí)行的預(yù)期代價(jià)為QC, 則 在集中式數(shù)據(jù)庫(kù)中：QC=I/O代價(jià)+CPU代價(jià) 在分布式數(shù)據(jù)庫(kù)中：QC=I/O代價(jià)+CPU代價(jià)+通信代價(jià)通信代價(jià)可用如下公式作粗略估算： TC(X) = C0 + C1 * X 其中， X：為傳輸數(shù)據(jù)量，通常以bit為單位計(jì)算； C0：為兩站點(diǎn)通信初始化一次所花費(fèi)的時(shí)間，它由通信系統(tǒng)確定，近似一個(gè)常數(shù) C1：為傳輸率 (傳輸速度的倒數(shù))，即單位數(shù)據(jù)傳輸?shù)臅r(shí)間，單位是 s/b。 1. 分布式查詢(xún)優(yōu)化概述1.3 分布式查詢(xún)策略的比較分析 在分布式數(shù)據(jù)

4、庫(kù)系統(tǒng)中，查詢(xún)優(yōu)化包括兩個(gè)內(nèi)容：查詢(xún)策略?xún)?yōu)化和局部處理優(yōu)化，而查詢(xún)策略?xún)?yōu)化尤為重要。例4.1 在教學(xué)數(shù)據(jù)庫(kù)中，有 S( s#, sname, age, sex) 104 元組 存放在Site A C( c#, cname, teacher) 105 元組 存放在Site B SC( s#, c#, grade) 106 元組 存放在Site A假定：若每個(gè)元組長(zhǎng)度100Bit, 通訊傳輸速度 104 bit/s, 通訊延遲時(shí)間為 1s。問(wèn)題：要求查出所有選修MATHS課的男學(xué)生的學(xué)號(hào)和姓名1. 分布式查詢(xún)優(yōu)化概述1.3 分布式查詢(xún)策略的比較分析解：在分片透明性的DDBMS支持下，SQL查詢(xún)語(yǔ)句

5、如下 SELECT s#, sname FROM S, C, SC WHERE S.s#=SC.s# AND C.c#=SC.c# AND sex=男 AND cname=maths;S, SCCSite ASite B1. 分布式查詢(xún)優(yōu)化概述1.3 分布式查詢(xún)策略的比較分析代價(jià)公式 QC = I/O 代價(jià) + CPU 代價(jià) + 通訊代價(jià) 通訊代價(jià) TC = 傳輸延遲時(shí)間C0+ (傳輸數(shù)據(jù)量X * 數(shù)據(jù)傳輸速率C1)1. 分布式查詢(xún)優(yōu)化概述1.3 分布式查詢(xún)策略的比較分析策略1: A 傳C B 把關(guān)系 C 傳輸?shù)?A 地,在 A 地處理查詢(xún) T1 = 1 + (105 * 100 / 104)

6、 S,SC 通信1次 C 103 秒 16.7 分鐘 A 傳S,SC B 把關(guān)系 S 和SC 傳輸?shù)?B 地 , 在 B 地處理查詢(xún) T2 = 2+(104+106) * 100 / 104 S,SC 通信2次 C 10100 秒 28小時(shí) A 問(wèn)105 B 先在A地求出男學(xué)生的成績(jī)?cè)M有105 再根據(jù)C#的值詢(xún)問(wèn)B地 ,核實(shí)是否C=MATHS S,SC 答105 C T3 (2 * 105 *1)=2*105 秒 2.3 天策略2:策略3:S, SCCSite ASite B1. 分布式查詢(xún)優(yōu)化概述1.3 分布式查詢(xún)策略的比較分析S, SCCSite ASite B A 問(wèn)10 B 先在B地

7、求出MATHS的元組,有10個(gè) 再根據(jù)C#的值詢(xún)問(wèn) A 地的S， SC的連接， S ,SC 答10 C 核實(shí)是否為選修MATHS的男生 T4 (2 * 10 * 1) = 20 秒 A 傳輸105 B 先在A地求出男生選課元組，有105個(gè) 再把結(jié)果傳輸?shù)?B 地, 在 B 地執(zhí)行查詢(xún)， S,SC 通信1次 C T5 = 1 + (105 * 100) / 104 1000 秒 16.7 分 A 傳輸10 B 先在B地求出為 MATHS 的元組，有10個(gè) 再把結(jié)果傳輸?shù)?A 地 , 在 A 地執(zhí)行查詢(xún)， S,SC 通信 1次 C T6 = 1 + (10 * 100) / 104 1 秒策略 4

8、： 策略 5： 策略 6：1. 分布式查詢(xún)優(yōu)化概述1.3 分布式查詢(xún)策略的比較分析 假設(shè)，每個(gè)站點(diǎn)執(zhí)行的CPU和I/O效率相同，并未考慮并行。 不同查詢(xún)策略結(jié)果的比較 處理策略處理策略方法時(shí)間1把C送到A地，在A地處理查詢(xún)16.7分2把S，SC送到B地，在B地處理查詢(xún)28小時(shí)3對(duì)每個(gè)男生的成績(jī)核查相應(yīng)的課程名2.3天4取課程名MATHS的課程號(hào)，核查為男生的記錄20秒5把男生記錄送到B地，在B地處理查詢(xún)16.7分6把把MATHS的記錄送到的記錄送到A地，在地，在A地處理地處理查詢(xún)查詢(xún)1秒秒一個(gè)好的查詢(xún)處理應(yīng)該使數(shù)據(jù)的傳輸量和通信次數(shù)最少，這樣才能使查詢(xún)所花費(fèi)的數(shù)據(jù)傳輸和通信時(shí)間減少，從而減少查

9、詢(xún)的總代價(jià)。由此可見(jiàn)：2. 分布式查詢(xún)優(yōu)化的知識(shí)回顧1. 集合運(yùn)算：并、差、交、笛卡爾、選擇、投影、連接、除等2. 關(guān)系表達(dá)式： 2. 分布式查詢(xún)優(yōu)化的知識(shí)回顧3.查詢(xún)樹(shù) -對(duì)一個(gè)關(guān)系代數(shù)表達(dá)式表示的查詢(xún)，進(jìn)行語(yǔ)法分析，可以 得到一棵語(yǔ)法樹(shù)。 -樹(shù)的葉子是已知的關(guān)系，樹(shù)的各個(gè)節(jié)點(diǎn)是關(guān)系代數(shù)操作符，樹(shù)的根是查詢(xún)結(jié)果，所以也稱(chēng)操作符樹(shù)。 -用語(yǔ)法樹(shù)來(lái)描述一個(gè)查詢(xún)要求，更加清晰、更加直觀，且 易于分析和調(diào)整查詢(xún)問(wèn)題的具體操作次序。因此，語(yǔ)法樹(shù)又稱(chēng)查詢(xún)樹(shù)。4.關(guān)系代數(shù)表達(dá)式的等價(jià)變換 所謂兩個(gè)關(guān)系代數(shù)表達(dá)式E1和E2等價(jià)是指：用相同的關(guān)系代替兩個(gè)表達(dá)式中相應(yīng)的關(guān)系時(shí)，所得到的結(jié)果是一樣的。稱(chēng)此兩個(gè)關(guān)系

10、代數(shù)表達(dá)式E1和E2等價(jià)，記作E1E2. 2. 分布式查詢(xún)優(yōu)化的知識(shí)回顧5.等價(jià)變換規(guī)則： * 有關(guān)空值的等價(jià)變換規(guī)則 R = R R = R = R = - R = R - = R R = R = * 交換律* 二元操作交換律* 二元操作分配律* 等等 3. 分布式查詢(xún)的分類(lèi)與層次結(jié)構(gòu)2.1 分布式查詢(xún)的分類(lèi)局部查詢(xún)：指在本站點(diǎn)上執(zhí)行查詢(xún)，即查詢(xún)本站點(diǎn)存放的數(shù)據(jù)?？梢允褂眉惺讲樵?xún)處理的技術(shù)。遠(yuǎn)程查詢(xún)：指在某個(gè)站點(diǎn)上執(zhí)行查詢(xún)，即查詢(xún)?cè)诰W(wǎng)絡(luò)上的另一個(gè)站點(diǎn)上存放的數(shù)據(jù)。全局查詢(xún)：涉及多個(gè)站點(diǎn)查詢(xún)數(shù)據(jù), 匯總后傳回發(fā)出查詢(xún)請(qǐng)求的站點(diǎn)。 在分布式環(huán)境下，查詢(xún)可分為三種類(lèi)型：局部查詢(xún)、遠(yuǎn)程查詢(xún)和在分布

11、式環(huán)境下，查詢(xún)可分為三種類(lèi)型：局部查詢(xún)、遠(yuǎn)程查詢(xún)和全局查詢(xún)。局部查詢(xún)只在本站點(diǎn)上執(zhí)行查詢(xún)。遠(yuǎn)程查詢(xún)和全局查詢(xún)?nèi)植樵?xún)。局部查詢(xún)只在本站點(diǎn)上執(zhí)行查詢(xún)。遠(yuǎn)程查詢(xún)和全局查詢(xún)由于涉及遠(yuǎn)程站點(diǎn)或多個(gè)站點(diǎn)上的數(shù)據(jù)，必須進(jìn)行站點(diǎn)間數(shù)據(jù)和信由于涉及遠(yuǎn)程站點(diǎn)或多個(gè)站點(diǎn)上的數(shù)據(jù)，必須進(jìn)行站點(diǎn)間數(shù)據(jù)和信息的傳遞，需要一定的通信費(fèi)用。息的傳遞，需要一定的通信費(fèi)用。3. 分布式查詢(xún)的分類(lèi)與層次結(jié)構(gòu)2.1 分布式查詢(xún)的分類(lèi)n局部查詢(xún) * 局部查詢(xún)只涉及本地，單個(gè)站點(diǎn)的數(shù)據(jù), 所以查詢(xún)優(yōu)化技術(shù)與集中式數(shù)據(jù)庫(kù)查 詢(xún)所采取的優(yōu)化技術(shù)相同，如查詢(xún)分解、關(guān)系代數(shù)表達(dá)式的等價(jià)變換、基于代價(jià)的估算等。 * 局部查詢(xún)一般策略有： - 選

12、擇和投影運(yùn)算應(yīng)盡可能先做，可以使中間結(jié)果數(shù)據(jù)大大減少。 - 在執(zhí)行連接前對(duì)數(shù)據(jù)庫(kù)數(shù)據(jù)進(jìn)行適當(dāng)?shù)念A(yù)處理，如對(duì)數(shù)據(jù)按連接屬性排序和在連接屬性上建立索引，以減少掃描次數(shù)，提高連接速度。 - 同時(shí)執(zhí)行一串投影和選擇操作，且盡可能把它們與其前后的二元操作結(jié)合起來(lái)，以避免重復(fù)掃描關(guān)系和減少中間數(shù)據(jù)。 - 找出公共子表達(dá)式等。3. 分布式查詢(xún)的分類(lèi)與層次結(jié)構(gòu)2.1 分布式查詢(xún)的分類(lèi)n遠(yuǎn)程查詢(xún) * 遠(yuǎn)程查詢(xún)只涉及單個(gè)站點(diǎn)的數(shù)據(jù), 所以它的局部處理的優(yōu)化策略與本地查詢(xún)所采取的優(yōu)化策略相同。 * 遠(yuǎn)程查詢(xún)還涉及遠(yuǎn)程站點(diǎn)的選擇，即選擇哪個(gè)遠(yuǎn)程站點(diǎn)上的數(shù)據(jù)或數(shù)據(jù)片段作為查詢(xún)的對(duì)象。 * 為了減少遠(yuǎn)程查詢(xún)的通信代價(jià)，如

13、果數(shù)據(jù)是冗余分配，應(yīng)盡可能選擇距發(fā)出查詢(xún)應(yīng)用的站點(diǎn)最近的站點(diǎn)上的數(shù)據(jù)或數(shù)據(jù)片段作為查詢(xún)的對(duì)象。3. 分布式查詢(xún)的分類(lèi)與層次結(jié)構(gòu)2.1 分布式查詢(xún)的分類(lèi)n全局查詢(xún) 全局查詢(xún)涉及多個(gè)站點(diǎn)上的數(shù)據(jù)，因此查詢(xún)處理和優(yōu)化技術(shù)要復(fù)雜得多。為執(zhí)行全局查詢(xún)并確定一個(gè)好的查詢(xún)策略，需要做許多判斷和計(jì)算工作。這些工作大致可歸為如下四類(lèi)： (1) 具體化 -查詢(xún)所要訪問(wèn)的每一個(gè)數(shù)據(jù)或數(shù)據(jù)片段，認(rèn)定其一個(gè)或多個(gè)副本。 -如果一個(gè)查詢(xún)所要訪問(wèn)的每一個(gè)數(shù)據(jù)或數(shù)據(jù)片段，都只有一個(gè)副本，則稱(chēng)為非冗余具體化，否則稱(chēng)為冗余具體化。 -對(duì)冗余具體化就要研究如何為每一個(gè)數(shù)據(jù)或數(shù)據(jù)片段選擇它的哪個(gè) 副本，才能使通信代價(jià)最小，從而使查詢(xún)

14、代價(jià)最小且結(jié)果正確。 -冗余具體化的目標(biāo)：通過(guò)冗余數(shù)據(jù)提高處理并行性和減少通信費(fèi)用。不僅需要考慮副本選擇問(wèn)題，還需研究在冗余具體化情況下，如何 提高處理的并行性等優(yōu)化查詢(xún)策略。3. 分布式查詢(xún)的分類(lèi)與層次結(jié)構(gòu)2.1 分布式查詢(xún)的分類(lèi) (2) 確定操作執(zhí)行次序 -在分布式數(shù)據(jù)庫(kù)系統(tǒng)中確定二元操作連接操作和并操作的次序。其它操作次序，選擇和投影盡可能早執(zhí)行。 -可供選擇的策略通常有兩種： 一種是先執(zhí)行所有連接操作，再執(zhí)行并操作 另一種是先執(zhí)行部分并操作，再執(zhí)行連接操作。 -選擇哪種策略與其代價(jià)有關(guān)，先估算各種策略代價(jià)，從中選出代價(jià)最小的形成執(zhí)行方案。 (3) 確定操作執(zhí)行方法 -把若干個(gè)操作連接起

15、來(lái)在一次數(shù)據(jù)庫(kù)訪問(wèn)中，確定可用的訪問(wèn)路徑(如選擇索引)，以及確定某種計(jì)算方法等。 -連接方法在查詢(xún)優(yōu)化中起著重要作用，是查詢(xún)中最費(fèi)時(shí)的操作。因此連接的執(zhí)行方法是研究查詢(xún)優(yōu)化中操作執(zhí)行方法的重點(diǎn)。3. 分布式查詢(xún)的分類(lèi)與層次結(jié)構(gòu)2.1 分布式查詢(xún)的分類(lèi) (4) 確定執(zhí)行站點(diǎn) -全局查詢(xún)執(zhí)行站點(diǎn)不一定是發(fā)出查詢(xún)的站點(diǎn)，全局查詢(xún) 原則上可以在網(wǎng)絡(luò)上的任意站點(diǎn)上執(zhí)行，然后將結(jié)果傳 送到發(fā)出查詢(xún)的站點(diǎn)。 -確定執(zhí)行站點(diǎn)主要考慮通信代價(jià)和執(zhí)行效率，一般選擇 離提供數(shù)據(jù)的站點(diǎn)較近的站點(diǎn)。也應(yīng)考慮查詢(xún)速度，盡 量選擇較空閑的站點(diǎn)執(zhí)行查詢(xún)操作。 * 為了找到一個(gè)查詢(xún)的最優(yōu)策略，就要確定執(zhí)行查詢(xún)的物理 片段，也必

16、須確 定查詢(xún)中各操作執(zhí)行的次序和執(zhí)行站點(diǎn)， 而這又依賴(lài)于每個(gè)操作的執(zhí)行方法。這四個(gè)問(wèn)題聯(lián)系不是 單向的或線性的，而是相互制約的。要根據(jù)應(yīng)用統(tǒng)籌考慮。但無(wú)論如何，連接和合并操作是引起遠(yuǎn)程通信的主要原因，連接操作還是最費(fèi)時(shí)間、空間的操作。 * 因此連接操作的優(yōu)化成為分布式查詢(xún)優(yōu)化的首要任務(wù)。3. 分布式查詢(xún)的分類(lèi)與層次結(jié)構(gòu)2.2 分布式查詢(xún)的層次結(jié)構(gòu)3. 分布式查詢(xún)的分類(lèi)與層次結(jié)構(gòu)2.2 分布式查詢(xún)的層次結(jié)構(gòu)查詢(xún)分解 -將查詢(xún)問(wèn)題（SQL）轉(zhuǎn)換成一個(gè)定義在全局關(guān)系上的關(guān)系代數(shù)表達(dá)式 -需要從全局概念模式中獲得轉(zhuǎn)換所需要的信息數(shù)據(jù)本地化 -把一個(gè)在全局關(guān)系上的查詢(xún)具體化，落實(shí)到合適的(使盡可能做到本

17、地化或近地化)片段上的查詢(xún)。即將全局關(guān)系的關(guān)系代數(shù)表達(dá)式變換為相應(yīng)片段上的關(guān)系代數(shù)表達(dá)式。 -這一變換所需要的信息在分片模式和片段的分配模式中獲得3. 分布式查詢(xún)的分類(lèi)與層次結(jié)構(gòu)2.2 分布式查詢(xún)的層次結(jié)構(gòu)全局優(yōu)化 -輸入的是分片查詢(xún)，查詢(xún)優(yōu)化目標(biāo)是尋找一個(gè)近于最優(yōu) 的執(zhí)行策略。 -全局優(yōu)化即是找出分片查詢(xún)的最佳操作次序，使得代價(jià)函數(shù)最小。代價(jià)函數(shù)一般是I/O、CPU和通信代價(jià)之和。 -全局優(yōu)化的一個(gè)重要方面是關(guān)于連接操作的優(yōu)化。全局 優(yōu)化處理層輸出是一個(gè)優(yōu)化的、片段上的關(guān)系代數(shù)查詢(xún)。局部?jī)?yōu)化 -局部查詢(xún)優(yōu)化由擁有與查詢(xún)有關(guān)的片段的各個(gè)站點(diǎn)執(zhí)行。在每個(gè)站點(diǎn)上執(zhí)行的子查詢(xún)被稱(chēng)為局部查詢(xún)。它由該站

18、 點(diǎn)上的DBMS進(jìn)行優(yōu)化，采用集中式數(shù)據(jù)庫(kù)系統(tǒng)中查詢(xún) 優(yōu)化的算法。所需信息取自局部模式。4. 基于關(guān)系代數(shù)等價(jià)變換的查詢(xún)優(yōu)化3.1 基于關(guān)系代數(shù)等價(jià)變換的查詢(xún)優(yōu)化的基本代理 基本原理：1.把查詢(xún)問(wèn)題轉(zhuǎn)化為關(guān)系代數(shù)表達(dá)式；2.分析得到查詢(xún)樹(shù)；3.進(jìn)行全局到片段的變換得到基于片段的查詢(xún)樹(shù)；4.利用關(guān)系代數(shù)等價(jià)變換規(guī)則的優(yōu)化算法，盡可能先執(zhí)行 選擇和投影操作，后執(zhí)行連接和合并操作；5.對(duì)該查詢(xún)樹(shù)進(jìn)行優(yōu)化，從而達(dá)到查詢(xún)優(yōu)化的目的。 水平分片：把分片的分片條件與選擇條件進(jìn)行比較，判別它們之間是否 存在矛盾，去掉存在矛盾的片段。如果只剩下一個(gè)水平分片的 片段，就可以去掉一個(gè)“并”操作。 垂直分片：把片段中

19、的屬性集與投影操作涉及的屬性集進(jìn)行比較，去掉 無(wú)關(guān)的所有片段。如果只剩下一個(gè)垂直分片的片段，就可以去 掉一個(gè)“連接”操作。 4. 基于關(guān)系代數(shù)等價(jià)變換的查詢(xún)優(yōu)化3.2 基于關(guān)系代數(shù)等價(jià)變換的查詢(xún)優(yōu)化的實(shí)現(xiàn)步驟實(shí)現(xiàn)步驟： -將一個(gè)查詢(xún)問(wèn)題轉(zhuǎn)換成關(guān)系代數(shù)表達(dá)式。 -從關(guān)系代數(shù)表達(dá)式到查詢(xún)樹(shù)的變換：對(duì)一個(gè)關(guān)系代數(shù)表達(dá)式進(jìn)行語(yǔ)法分析，可以得到一棵語(yǔ)法樹(shù)(或查詢(xún)樹(shù))，即查詢(xún)樹(shù)根節(jié)點(diǎn)是最終的查詢(xún)結(jié)果，葉子節(jié)點(diǎn)是查詢(xún)涉及的所有關(guān)系或片段，中間節(jié)點(diǎn)是按關(guān)系代數(shù)表達(dá)式中的操作順序組成的一組關(guān)系操作符。 -從全局查詢(xún)到片段查詢(xún)的變換：把基于全局關(guān)系的查詢(xún)樹(shù)中的全局關(guān)系名，用其重構(gòu)該全局關(guān)系的各個(gè)片段名替換，變換成

20、相應(yīng)片段上的查詢(xún)樹(shù)。 -利用關(guān)系代數(shù)等價(jià)變換規(guī)則優(yōu)化算法，對(duì)片段的查詢(xún)樹(shù)進(jìn)行優(yōu)化處理，最后達(dá)到優(yōu)化查詢(xún)目的。 4. 基于關(guān)系代數(shù)等價(jià)變換的查詢(xún)優(yōu)化3.2 基于關(guān)系代數(shù)等價(jià)變換的查詢(xún)優(yōu)化的實(shí)現(xiàn)步驟優(yōu)化算法：1.連接操作和合并操作盡可能上提（樹(shù)根方向）；2.選擇操作和投影操作盡可能下移（葉子方向）；3.盡可能先執(zhí)行選擇和投影操作，后執(zhí)行連接和合并操作。4.經(jīng)過(guò)選擇和投影操作不但可以減少其后操作量，還可以 減少操作次數(shù)。實(shí)現(xiàn)步驟和方法： 轉(zhuǎn)換一：查詢(xún)問(wèn)題關(guān)系代數(shù)表達(dá)式 轉(zhuǎn)換二：關(guān)系代數(shù)表達(dá)式查詢(xún)樹(shù) 轉(zhuǎn)換三：全局查詢(xún)樹(shù)分拆成片段查詢(xún)樹(shù) 優(yōu)化：利用關(guān)系代數(shù)等價(jià)變換規(guī)則的優(yōu)化算法，優(yōu)化查詢(xún)樹(shù)，進(jìn)而優(yōu)化查詢(xún)

21、4. 基于關(guān)系代數(shù)等價(jià)變換的查詢(xún)優(yōu)化3.3 基于關(guān)系代數(shù)等價(jià)變換的查詢(xún)優(yōu)化舉例例4.2 對(duì)于教學(xué)數(shù)據(jù)庫(kù)全局關(guān)系S(S#, SNAME, AGE, SEX)和和SC(S#, C#, GRADE)被水平分片。hh S SCS1: SEX=M男學(xué)生全體男學(xué)生全體S2: SEX=F女學(xué)生全體女學(xué)生全體SC1：C#=20課程號(hào)課程號(hào)20課程號(hào)課程號(hào)20查詢(xún)問(wèn)題：查找至少有一門(mén)功課成績(jī)?cè)诓樵?xún)問(wèn)題：查找至少有一門(mén)功課成績(jī)?cè)?0分以上的男生姓名。分以上的男生姓名。4. 基于關(guān)系代數(shù)等價(jià)變換的查詢(xún)優(yōu)化3.3 基于關(guān)系代數(shù)等價(jià)變換的查詢(xún)優(yōu)化舉例(1)這個(gè)查詢(xún)問(wèn)題的SQL語(yǔ)句是： Select Distinct s

22、name From S, SC Where S.s#=SC.s# AND sex=M AND grade90 (2)它的關(guān)系代數(shù)表達(dá)式是： SNAME( SEX=M and GRADE90( S.S #=SC.C# (SSC)(3)轉(zhuǎn)換為查詢(xún)樹(shù)，并且基于關(guān)系代數(shù)等價(jià)變換進(jìn)行優(yōu)化：4. 基于關(guān)系代數(shù)等價(jià)變換的查詢(xún)優(yōu)化3.3 基于關(guān)系代數(shù)等價(jià)變換的查詢(xún)優(yōu)化舉例4. 基于關(guān)系代數(shù)等價(jià)變換的查詢(xún)優(yōu)化3.3 基于關(guān)系代數(shù)等價(jià)變換的查詢(xún)優(yōu)化舉例4. 基于關(guān)系代數(shù)等價(jià)變換的查詢(xún)優(yōu)化3.3 基于關(guān)系代數(shù)等價(jià)變換的查詢(xún)優(yōu)化舉例4. 基于關(guān)系代數(shù)等價(jià)變換的查詢(xún)優(yōu)化3.3 基于關(guān)系代數(shù)等價(jià)變換的查詢(xún)優(yōu)化舉例水平分片關(guān)系查詢(xún)優(yōu)化的基本思想：水平分片關(guān)系查詢(xún)優(yōu)化的基本思想： 1. 盡量把選擇條件下移到分片的限定關(guān)系處；盡量把選擇條件下移到分片的限定關(guān)系處；