《《數(shù)據(jù)庫管理系統(tǒng)》PPT課件.ppt》由會員分享，可在線閱讀，更多相關(guān)《《數(shù)據(jù)庫管理系統(tǒng)》PPT課件.ppt（30頁珍藏版）》請在裝配圖網(wǎng)上搜索。

1、6.2 關(guān)系DBS的查詢優(yōu)化,第六章 數(shù)據(jù)庫管理系統(tǒng),6.1 DBMS簡介,6.3 關(guān)系DBMS的發(fā)展,6.1 DBMS簡介,1. DBMS位置 DBMS是DBS的核心軟件，介于用戶和OS之間的系統(tǒng)軟件，它實(shí)現(xiàn)對共享數(shù)據(jù)的有效組織、管理和各種操作。,DBMS建立在OS之上， 需要OS的支持。 DBMS是用戶操縱、管理 DB的工具。 說明:獨(dú)立DBMS、OS擴(kuò)充,6.1 DBMS簡介,DBMS的特點(diǎn) 1. 完備高效 2. 界面友好 3. 事務(wù)處理 4. 結(jié)構(gòu)清晰 5. 規(guī)范開放,DBMS的功能 (1) 數(shù)據(jù)定義 (用DDL) (2) 數(shù)據(jù)操縱 (用DML) (3) 數(shù)據(jù)組織、存儲和管理 (4)

2、數(shù)據(jù)庫運(yùn)行管理 (5) 數(shù)據(jù)庫的建立和維護(hù) (6) 數(shù)據(jù)通信接口,6.1 DBMS簡介,2.DBMS的組成 (1) 數(shù)據(jù)定義語言及其翻譯處理程序 (2) 數(shù)據(jù)操縱語言及其編譯（或解釋）程序 (3) 數(shù)據(jù)庫運(yùn)行控制程序 (4) 實(shí)用程序 3.DBMS運(yùn)行環(huán)境 (1)分布: 數(shù)據(jù)分布、功能分布、處理分布。 (2)開放：開放的硬件平臺、支撐軟件、網(wǎng)絡(luò)支持、 異質(zhì)數(shù)據(jù)庫互連、用戶界面。,,,,,,,,,,,,,,,,,,,,,,日志,,,,應(yīng)用程序A,狀態(tài),工作區(qū),,,,,6.1 DBMS簡介,4.用戶訪問數(shù)據(jù)庫的工作過程 應(yīng)用程序A向DBMS發(fā)出讀一個記錄的命令。程序給出記錄類型名及

3、欲讀記錄的碼值。 DBMS分析命令，并調(diào)用A對應(yīng)的子模式，檢查A的存取權(quán)限，決定是否執(zhí)行A的命令。 決定執(zhí)行A的命令后，DBMS調(diào)用模式，根據(jù)子模式與模式變換的定義，確定所涉及的模式記錄類型；通過模式與內(nèi)模式的變換找到這些記錄類型的內(nèi)模式名。 DBMS調(diào)用內(nèi)模式，確定所讀入的物理記錄。 DBMS向OS發(fā)讀該物理記錄的命令,6.1 DBMS簡介, OS執(zhí)行讀命令并把數(shù)據(jù)從外存讀到內(nèi)存的系統(tǒng)緩沖區(qū)。 DBMS按模式、子模式定義，導(dǎo)出用戶程序需要的記錄形式，并送到應(yīng)用程序A的工作區(qū)。 DBMS向應(yīng)用程序A送命令執(zhí)行情況的狀態(tài)信息。 記載日志 DBMS把對數(shù)據(jù)庫更新操作的全部情況都記載下來，以便數(shù)據(jù)庫

4、的恢復(fù)。 應(yīng)用程序檢查狀態(tài)信息，若成功，對工作區(qū)中的數(shù)據(jù)正常處理；若失敗，決定下一步如何執(zhí)行。,6.1 DBMS簡介,6.2 關(guān)系DBS的查詢優(yōu)化,數(shù)據(jù)查詢是DBS中最基本、最常用和最復(fù)雜的數(shù)據(jù)操作，查詢優(yōu)化是影響關(guān)系DBMS性能的關(guān)鍵因素。 關(guān)系數(shù)據(jù)理論基于關(guān)系代數(shù)，同一個查詢要求可以對應(yīng)多個不同形式卻相互等價的表達(dá)式。 關(guān)系數(shù)據(jù)查詢語言是非過程化的，由DBMS自動生成若干候選的查詢計劃并擇優(yōu)使用。,,,,,查詢語句,,查詢輸出,,關(guān)系代數(shù)表達(dá)式,,執(zhí)行計劃,語法分析與翻譯,執(zhí)行引擎,優(yōu)化器,,,,數(shù)據(jù),有關(guān)數(shù)據(jù)的統(tǒng)計信息,1.查詢處理的過程,6.2 關(guān)系DBS的查詢優(yōu)化,6.2 關(guān)系DBS

5、的查詢優(yōu)化,查詢處理包括三個基本步驟： 解析和翻譯 優(yōu)化 實(shí)現(xiàn)（求值）,解析和翻譯 解析：檢查語法、驗證關(guān)系 翻譯：將查詢轉(zhuǎn)化為內(nèi)部形式，并進(jìn)一步翻譯為關(guān)系代數(shù). 實(shí)現(xiàn) 執(zhí)行引擎選取一個查詢計劃并執(zhí)行，而后將結(jié)果返回給查詢.,6.3 關(guān)系DBS的查詢處理,查詢優(yōu)化: 在所有等價的執(zhí)行計劃中選取代價最低的那個。 代價是利用從系統(tǒng)目錄中獲取的統(tǒng)計信息估算得到的。 e.g. 關(guān)系中的元組數(shù)目, 元組的大小等. 需要研究： 如何估量查詢的代價 實(shí)現(xiàn)關(guān)系代數(shù)操作的算法 將單個操作算法結(jié)合起來形成一個對表達(dá)式的完整求值 如何實(shí)現(xiàn)查詢優(yōu)化，即如何尋求一個具有最低代價的執(zhí)行計劃。,6.3 關(guān)系DBS的查詢處理

6、代價度量,代價通常是利用回答查詢所需的時間來度量的。 很多因素會影響查詢時間：磁盤存取, CPU, 網(wǎng)絡(luò)連接等 通常磁盤存取是最耗時的部分, 并且容易估算, 主要考慮. Number of seeks * average-seek-cost Number of blocks read * average-block-read-cost Number of blocks written * average-block-write-cost 寫的代價大于讀的代價：寫以后需要回讀以確保正確的寫,6.3 關(guān)系DBS的查詢處理代價度量,簡化起見，僅使用 number of block 從磁盤傳送

7、塊的數(shù)目作為代價的度量。 代價依賴于內(nèi)存緩沖區(qū)的大小 更多內(nèi)存降低磁盤存取次數(shù) 可用內(nèi)存數(shù)與 OS 其它進(jìn)程相關(guān), 難以事先確定 一般使用最壞估計, 假設(shè)可用內(nèi)存最小時的情況。 是實(shí)際模型的簡化 忽略了順序和隨機(jī)讀寫的區(qū)別 忽略了CPU的代價 忽略了寫到磁盤的代價。,,為什么要查詢優(yōu)化？ 例: Student表有l(wèi)000個學(xué)生記錄，每人平均選10門課程， SC表共有1000*10=l0000個選課記錄。（統(tǒng)計信息）。要求: 查學(xué)生“王林”所選課程的成績在85分以上的課程號。 SELECT Cno FROM S，SC WHERE S.Sno=SC.Sno AND Sname=王林 A

8、ND Grade 85 ；,等價的關(guān)系代數(shù)表示： Cno( F1 F2 F3 ( SSC ) ) Cno( F2 F3 ( S SC ) ) Cno( F2 (S) F3 (SC) ),分析： 哪種效率高？,6.2 關(guān)系DBS的查詢優(yōu)化,6.2 關(guān)系DBS的查詢優(yōu)化, Cno( F1 F2 F3 ( SSC ) ) Cno( F2 F3 ( S SC ) ) Cno( F2 (S) F3 (SC) ) 先在兩表上做 ，產(chǎn)生1000*10000=107個連接記錄，再在其上進(jìn)行先后操作。其基本運(yùn)算的次數(shù)為：3*107。 先在兩個表上做 ，產(chǎn)生1000*10=104個連接記錄，再在其上進(jìn)行

9、先后操作。其基本運(yùn)算的次數(shù)為：107+2*104。 先分別在兩個表上做,再做 ，產(chǎn)生1*10=10個連接記錄，再在其上進(jìn)行 。其基本運(yùn)算的次數(shù)為：104+103+*101。,連接時間復(fù)雜度為： O(107) O(104) O(101),,2.查詢優(yōu)化的一般策略,6.2 關(guān)系DBS的查詢優(yōu)化,啟發(fā)式優(yōu)化利用一套規(guī)則來轉(zhuǎn)換查詢樹, 這些規(guī)則通常(但不是所有情況)都能改善執(zhí)行性能: 盡早執(zhí)行選擇 (減少元組數(shù)目) 盡早執(zhí)行投影 (減少屬性數(shù)目) 在其他類似操作之前執(zhí)行最具限制性的選擇和連接操作. 某些系統(tǒng)只使用啟發(fā)式, 其他的結(jié)合了啟發(fā)式與部分基于代價的優(yōu)化.,6.2 關(guān)系DBS的查詢優(yōu)化,3. 關(guān)

10、系代數(shù)表達(dá)式的轉(zhuǎn)換 如果在每個合法的數(shù)據(jù)庫實(shí)例上, 兩個關(guān)系代數(shù)表達(dá)式都生成同樣的元組集合, 則這兩個關(guān)系代數(shù)表達(dá)式稱為等價的 注意: 元組次序是無關(guān)的 在SQL中, 輸入和輸出都是元組的多重集合 如果在每個合法的數(shù)據(jù)庫實(shí)例上, 兩個關(guān)系代數(shù)表達(dá)式都生成同樣的元組多重集合, 則這兩個表達(dá)式在關(guān)系代數(shù)的多重集合版本下稱為等價的 等價規(guī)則說明了兩種形式的表達(dá)式是等價的 可以用一個表達(dá)式替換另一個 12條等價規(guī)則,,6.2 關(guān)系DBS的查詢優(yōu)化,合取選擇操作可以分解成個體選擇的序列. 選擇操作是可交換的. 一個投影操作序列中只有最后一個是必要的, 其余皆可省略. 選擇可與笛卡兒積及 連接結(jié)合. (E

11、1 X E2) = E1 E2 1(E1 2 E2) = E1 1 2 E2,,,,6.2 關(guān)系DBS的查詢優(yōu)化,5. 連接操作 (及自然連接) 可交換.E1 E2 = E2 E1 6.(a) 自然連接操作是可結(jié)合的: (E1 E2) E3 = E1 (E2 E3)(b) 連接按如下方式是可結(jié)合的: (E1 1 E2) 2 3 E3 = E1 2 3 (E2 2 E3) 其中2 僅涉及來自E2 和E3的屬性.,,,,,,,,,,,6.2 關(guān)系DBS的查詢優(yōu)化,7.在下面兩個條件下, 選擇操作對 連接操作有分配律:(a) 當(dāng)0中的所有屬性僅涉及被連接表達(dá)式之一(E1)

12、的屬性時. 0E1 E2) = (0(E1)) E2 (b) 當(dāng)1 僅涉及E1的屬性且2僅涉及E2的屬性時. 1 E1 E2) = (1(E1)) ( (E2)),,,,,6.2 關(guān)系DBS的查詢優(yōu)化,8.投影操作對 連接操作的分配律如下: (a) 若 僅涉及來自L1 L2的屬性: (b) 考慮連接 E1 E2. 若 L1 和 L2 分別是來自E1和E2的屬性集合. 令 L3 是連接條件中涉及的E1的屬性, 但不在L1 L2中, 并且 令 L4是連接條件中涉及的E2的屬性,但不在L1 L2中.,,6.2 關(guān)系DBS的查詢優(yōu)化,集合運(yùn)算并和交都是可交換的 E1 E2 =

13、E2 E1 E1 E2 = E2 E1 (集合差不是可交換的). 集合并和交都是可結(jié)合的. (E1 E2) E3 = E1 (E2 E3) (E1 E2) E3 = E1 (E2 E3) 選擇操作對, 和可分配. (E1 E2) = (E1) (E2) 類似地可用和 替換同樣: (E1 E2) = (E1) E2 類似地可用 替換 , 但不能用 12. 投影操作對并可分配 L(E1 E2) = (L(E1)) (L(E2)),連接次序例 對所有關(guān)系 r1, r2, 及r3, (r1 r2) r3 = r1 (r2 r3 ) 若r2

14、r3 很大且r1 r2 較小, 我們選擇 (r1 r2) r3 從而我們計算并存儲一個較小的臨時關(guān)系.,,,,,,,,,6.2 關(guān)系DBS的查詢優(yōu)化,4. 關(guān)系代數(shù)表達(dá)式的優(yōu)化算法,算法：關(guān)系表達(dá)式的優(yōu)化。 輸入：一個關(guān)系表達(dá)式的語法樹。 輸出：計算該表達(dá)式的程序。,（1）用規(guī)則4把形如: F1F2... (E) 變?yōu)? F1(F2...(E)) 再利用規(guī)則58 把每一個選擇運(yùn)算盡可能移到樹的葉端。 （2）對每一個投影利用規(guī)則3、5、9、l0，盡可能把它移向樹的葉端。 （3）利用規(guī)則35把選擇和投影的串接合并成單個選擇、單個投影或一個選擇后跟一個投影。使多個選擇或投影能同時執(zhí)行，或在一次掃描中

15、全部完成， （4）使用規(guī)則12 使選擇運(yùn)算與笛卡爾積結(jié)合成連接運(yùn)算。 （5）對語法樹中的內(nèi)節(jié)點(diǎn)進(jìn)行分組。 （6）找出查詢樹中的公共子樹。 （7）輸出由分組結(jié)果得到的優(yōu)化語法樹。,例P278,五種基本運(yùn)算表示,6.4 關(guān)系DBS的查詢優(yōu)化,生成、選擇查詢計劃。,用到查詢優(yōu)化的一般策略,5.查詢優(yōu)化的一般步驟： 將查詢表示成關(guān)系代數(shù)語法樹。 根據(jù)變換規(guī)則將其轉(zhuǎn)換成標(biāo)準(zhǔn)優(yōu)化形式。 選擇低層的操作算法。 對語法樹中的每一操作需要根據(jù)存取路徑、數(shù)據(jù)的分布、聚簇等信息來選擇具體的執(zhí)行算法。,6.3 關(guān)系DBMS的發(fā)展,一、關(guān)系DBMS的發(fā)展階段 第一階段是關(guān)系數(shù)據(jù)庫理論研究和原型開發(fā)的時代: 奠定了關(guān)系

16、模型的理論基礎(chǔ)。 研究了關(guān)系數(shù)據(jù)語言。 研制了大量關(guān)系DBMS的原型。 第二階段是關(guān)系DBMS的實(shí)用階段: 攻克了查詢優(yōu)化，并發(fā)控制，完整性機(jī)制等一系列重大技術(shù)問題。從而使得數(shù)據(jù)庫走向商業(yè)化。 第三階段是關(guān)系DBMS的成熟與發(fā)展階段: 應(yīng)用領(lǐng)域由集中到分布，由單機(jī)到網(wǎng)絡(luò)，由信息管理，輔助決策到企業(yè)級的聯(lián)機(jī)事務(wù)處理。,表6.1 關(guān)系DBMS的發(fā)展階段及相關(guān)技術(shù)支持,6.3 關(guān)系DBMS的發(fā)展,二、關(guān)系DBMS的發(fā)展趨勢 產(chǎn)品系列化 支持高速互聯(lián)網(wǎng)應(yīng)用 智能化集成化 三、關(guān)系DBMS產(chǎn)品的選擇 應(yīng)用對關(guān)系DBMS的要求 具有高可伸縮性及高可用性 高可靠性和高安全性 高速互聯(lián)互訪 高效協(xié)同服務(wù) 高度平臺開放,6.3 關(guān)系DBMS的發(fā)展,關(guān)系DBMS產(chǎn)品選擇的因素 數(shù)據(jù)庫應(yīng)用的規(guī)模、類型和用戶的數(shù)量 速度指標(biāo) 軟件、硬件平臺性能與價格比 開發(fā)者的經(jīng)驗和習(xí)慣 安全性,第六章 數(shù)據(jù)庫管理系統(tǒng),小結(jié)： 1. DBMS的定義、特點(diǎn)及功能 2. 關(guān)系DBS的查詢優(yōu)化 目標(biāo)、一般策略 關(guān)系代數(shù)等價變換規(guī)則及優(yōu)化算法 優(yōu)化的步驟,練習(xí)： P290 第4、6題,