關(guān)系數(shù)據(jù)庫的查詢優(yōu)化

1、武漢大學(xué)數(shù)據(jù)庫原理課題組6.1 DBMS 簡介簡介6.3 關(guān)系數(shù)據(jù)庫的查詢優(yōu)化關(guān)系數(shù)據(jù)庫的查詢優(yōu)化第六章第六章 數(shù)據(jù)庫管理系統(tǒng)數(shù)據(jù)庫管理系統(tǒng)6.4 關(guān)系關(guān)系DBMS產(chǎn)品及其選擇產(chǎn)品及其選擇本章本章小結(jié)小結(jié)6.2 關(guān)系關(guān)系DBMS武漢大學(xué)數(shù)據(jù)庫原理課題組6.1 DBMS 簡介簡介DBMS是一種負責數(shù)據(jù)庫的定義、建立、操作、管理和維護的軟件系統(tǒng)，其職能是有效地實現(xiàn)數(shù)據(jù)庫三級模式之間的轉(zhuǎn)換。DBMS是數(shù)據(jù)庫系統(tǒng)的核心，是介于用戶和OS之間的系統(tǒng)軟件，它實現(xiàn)對共享數(shù)據(jù)的有效組織、管理和各種操作。DBMS建立在OS之上，需要OS的支持。DBMS是用戶操縱、管理DB的工具。用戶應(yīng)用程序DBMSOSDB武漢

2、大學(xué)數(shù)據(jù)庫原理課題組6.1 DBMS 簡介簡介1.DBMS1.DBMS的特點與功能的特點與功能DBMSDBMS具備如下特點具備如下特點( (目標目標) )：(1)完備高效DBMS應(yīng)提供完備的數(shù)據(jù)庫管理功能，具有高的系統(tǒng)效率和高的用戶生產(chǎn)率。應(yīng)提供支持高效存取的數(shù)據(jù)結(jié)構(gòu)，以實現(xiàn)對于大量數(shù)據(jù)的持久存儲，具有較高的數(shù)據(jù)獨立性。(2)界面友好DBMS的用戶接口應(yīng)面向應(yīng)用、面向用戶。需提供方便的編程接口，以建立應(yīng)用程序訪問數(shù)據(jù)庫的通道；使用戶可通過多種方式、易用的語言對數(shù)據(jù)庫進行復(fù)雜操作。武漢大學(xué)數(shù)據(jù)庫原理課題組6.1 DBMS 簡介簡介(3)事務(wù)管理DBMS支持多個用戶進程同時對數(shù)據(jù)進行存取操作，引入

3、了“事務(wù)”的概念來實現(xiàn)對多個用戶數(shù)據(jù)庫訪問的管理。事務(wù)是數(shù)據(jù)庫恢復(fù)及并發(fā)控制的基本單位，通過事務(wù)管理可有效地支持多用戶操作，支持數(shù)據(jù)庫的安全性和完整性。事務(wù)管理是DBMS的基本功能之一。(4)結(jié)構(gòu)清晰DBMS是一個復(fù)雜的軟件系統(tǒng)，向上與應(yīng)用程序通信，向下與操作系統(tǒng)及其他軟、硬件資源交互。因此，結(jié)構(gòu)清晰、層次分明的DBMS有利于支持外層開發(fā)環(huán)境的構(gòu)造，也便于自身的設(shè)計、開發(fā)和維護，同時有利于數(shù)據(jù)庫系統(tǒng)的擴展。武漢大學(xué)數(shù)據(jù)庫原理課題組6.1 DBMS 簡介簡介(5)規(guī)范開放開放的DBMS首先應(yīng)符合標準和規(guī)范；其次，具備可伸縮性以及互操作性。DBMS不僅為建立以其為核心的軟件開發(fā)環(huán)境或應(yīng)用系統(tǒng)提供支

4、持，也為DBMS自身的再開發(fā)創(chuàng)造條件。DBMS的功能：(1)數(shù)據(jù)定義數(shù)據(jù)定義包括定義構(gòu)成數(shù)據(jù)庫結(jié)構(gòu)的外模式、模式和內(nèi)模式，定義各個外模式與模式之間的映射，定義模式與內(nèi)模式之間的映射，定義有關(guān)的約束條件。(2)數(shù)據(jù)操縱數(shù)據(jù)操縱包括對數(shù)據(jù)庫數(shù)據(jù)的查詢、插入、修改和刪除等基本操作。 (3)數(shù)據(jù)組織、存儲和管理確定以何種文件結(jié)構(gòu)和存取方式物理地組織這些數(shù)據(jù)，如何實現(xiàn)數(shù)據(jù)之間的聯(lián)系，以便提高存儲空間利用率以及提高隨機查找、順序查找、增刪改等操作的時間效率。武漢大學(xué)數(shù)據(jù)庫原理課題組6.1 DBMS 簡介簡介(4)數(shù)據(jù)庫運行管理對數(shù)據(jù)庫的運行進行管理是DBMS運行時的核心工作，包括對數(shù)據(jù)庫進行并發(fā)控制、安全

5、性檢查、完整性約束條件的檢查和執(zhí)行、數(shù)據(jù)庫的內(nèi)部維護等。所有訪問數(shù)據(jù)庫的操作都要在這些控制程序的統(tǒng)一管理下進行，以保證數(shù)據(jù)的安全性、完整性、一致性以及多用戶對數(shù)據(jù)庫的并發(fā)使用。(5)數(shù)據(jù)庫的建立與維護建立數(shù)據(jù)庫包括數(shù)據(jù)庫初始數(shù)據(jù)的輸入與數(shù)據(jù)轉(zhuǎn)換等。維護數(shù)據(jù)庫包括數(shù)據(jù)庫的轉(zhuǎn)儲與恢復(fù)、數(shù)據(jù)庫的重組織與重構(gòu)造、性能的監(jiān)視與分析等。 (6)數(shù)據(jù)通信接口DBMS需要提供與其他軟件系統(tǒng)進行通信的功能。武漢大學(xué)數(shù)據(jù)庫原理課題組6.1 DBMS 簡介簡介2.DBMS2.DBMS的組成的組成為提供上述6個方面的功能，DBMS的核心通常由以下4部分組成：(1) 數(shù)據(jù)定義語言及其翻譯處理程序DBMS一般都提供數(shù)據(jù)定

6、義語言DDL供用戶定義數(shù)據(jù)庫的外模式、模式、內(nèi)模式、各級模式之間的映射、有關(guān)的約束條件等。(2) 數(shù)據(jù)操縱語言及其編譯（或解釋）程序DBMS提供了數(shù)據(jù)操縱語言DML實現(xiàn)對數(shù)據(jù)庫的查詢檢索、插入、修改、刪除等基本操作。DML分為宿主型和主動型兩種。宿主型不能獨立使用，必須嵌入到主語言中。自主型是交互式命令語言，語法簡單，可以獨立使用。 (3) 數(shù)據(jù)庫運行控制程序 (4) 實用程序 武漢大學(xué)數(shù)據(jù)庫原理課題組6.1 DBMS 簡介簡介(3) 數(shù)據(jù)庫運行控制程序 DBMS提供了一些負責數(shù)據(jù)庫運行過程中的控制與管理的系統(tǒng)運行控制程序，包括系統(tǒng)初啟程序、文件讀寫與維護等。它們在數(shù)據(jù)庫運行過程中監(jiān)視對數(shù)據(jù)庫

7、的所有操作，控制管理數(shù)據(jù)庫資源，處理多用戶的并發(fā)操作等。(4) 實用程序 DBMS通常還提供一些服務(wù)性程序，包括數(shù)據(jù)初始裝入程序、數(shù)據(jù)轉(zhuǎn)儲程序、數(shù)據(jù)庫恢復(fù)程序、性能檢測程序、數(shù)據(jù)庫再組織程序、數(shù)據(jù)轉(zhuǎn)換程序、通信程序等。數(shù)據(jù)庫用戶可利用這些實用程序完成數(shù)據(jù)庫的建立與維護，以及數(shù)據(jù)通信與格式的轉(zhuǎn)換。武漢大學(xué)數(shù)據(jù)庫原理課題組6.1 DBMS 簡介簡介3.DBMS3.DBMS運行環(huán)境運行環(huán)境 隨著網(wǎng)絡(luò)技術(shù)逐漸成熟和實用化，DBMS的運行環(huán)境也由單機到網(wǎng)絡(luò)，集中到分布，封閉到開放。(1)分布n數(shù)據(jù)分布：數(shù)據(jù)物理地分布在網(wǎng)絡(luò)的不同節(jié)點上，各節(jié)點的數(shù)據(jù)是一個統(tǒng)一的整體，由系統(tǒng)的用戶共享。n功能分布：在網(wǎng)絡(luò)環(huán)

8、境下，數(shù)據(jù)管理功能分散在客戶端和服務(wù)器端完成。n處理分布：由多臺計算機合成、協(xié)調(diào)地完成某一任務(wù)。武漢大學(xué)數(shù)據(jù)庫原理課題組6.1 DBMS 簡介簡介(2)開放n開放的硬件平臺：能在各種硬件平臺上運行。n開放的支撐軟件：可在多種操作系統(tǒng)環(huán)境下運行。n開放的網(wǎng)絡(luò)支持：支持各種重要的網(wǎng)絡(luò)協(xié)議。n異質(zhì)數(shù)據(jù)庫的互連、互操作：解決異質(zhì)數(shù)據(jù)庫的通信和存取。n開放的用戶界面：即提供給用戶統(tǒng)一的語言界面和可移植的應(yīng)用開發(fā)工具。武漢大學(xué)數(shù)據(jù)庫原理課題組6.1 DBMS 簡介簡介4. 用戶訪問數(shù)據(jù)庫的工作過程整個數(shù)據(jù)庫系統(tǒng)的工作過程大致歸納為以下三個階段：(1)數(shù)據(jù)庫管理員建立并維護數(shù)據(jù)庫。DBA利用模式、內(nèi)模式DD

9、L等語言，描述數(shù)據(jù)庫的總體邏輯結(jié)構(gòu)，安置數(shù)據(jù)在庫中的存放方式和位置，并通過各種維護管理程序去建立、更新或刪除有關(guān)數(shù)據(jù)，維護管理和控制系統(tǒng)運行及日常工作。(2)用戶編寫應(yīng)用程序。用戶利用外模式DDL語言定義自己的外模式，用DML語言編寫所需操作命令，并將其嵌入到主語言的程序中。(3)應(yīng)用程序在DBMS支持下運行。當模式、內(nèi)模式、外模式和用戶源程序翻譯為目標代碼后，即可啟動目標程序執(zhí)行，完成數(shù)據(jù)庫操作。武漢大學(xué)數(shù)據(jù)庫原理課題組6.1 DBMS 簡介簡介 系統(tǒng)緩沖區(qū)概念模式內(nèi)模式DBMS OS 外部記錄存儲記錄數(shù)據(jù)庫 應(yīng)用程序A 外模式日志應(yīng)用程序A狀態(tài)工作區(qū) 武漢大學(xué)數(shù)據(jù)庫原理課題組 應(yīng)用程序A向

10、DBMS發(fā)出讀一個記錄的命令。程序給出記錄類型名及欲讀記錄的碼值。 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ā)讀該物理記錄的命令。武漢大學(xué)數(shù)據(jù)庫原理課題組 OS執(zhí)行讀命令并把數(shù)據(jù)從外存讀到內(nèi)存的系統(tǒng)緩沖區(qū)。 DBMS按模式、子模式定義，導(dǎo)出用戶程序需要的記錄形式，并送到應(yīng)用程序A的工作區(qū)。 DBMS向應(yīng)用程序A送命令執(zhí)行情況的狀態(tài)信息。 記載日志 DBM

11、S把對數(shù)據(jù)庫更新操作的全部情況都記載下來，以便數(shù)據(jù)庫的恢復(fù)。 應(yīng)用程序檢查狀態(tài)信息，若成功，對工作區(qū)中的數(shù)據(jù)正常處理；若失敗，決定下一步如何執(zhí)行。武漢大學(xué)數(shù)據(jù)庫原理課題組6.2 關(guān)系關(guān)系DBMS1.關(guān)系DBMS的發(fā)展階段1970年IBM的Codd的論文大型共享數(shù)據(jù)庫數(shù)據(jù)的關(guān)系模型奠定了關(guān)系數(shù)據(jù)庫技術(shù)的理論基礎(chǔ)。n第一階段：關(guān)系數(shù)據(jù)庫理論研究和原型開發(fā)的時代。20世紀70年代以來，經(jīng)過大量高層次的研究和開發(fā)取得了一系列重要成果。奠定了關(guān)系模型的理論基礎(chǔ)，給出了大家一致接受的關(guān)系模型的規(guī)范說明。研究了關(guān)系數(shù)據(jù)語言。研制了大量的關(guān)系DBMS的原型。武漢大學(xué)數(shù)據(jù)庫原理課題組6.2 關(guān)系關(guān)系DBMSn第

12、二階段：關(guān)系DBMS的實用階段。從20世紀70年代后期開始，從理論上攻克了諸如查詢優(yōu)化、并發(fā)控制、完整性機制和故障恢復(fù)等一系列重大技術(shù)問題，從而使數(shù)據(jù)庫走向?qū)嵱没?、商業(yè)化。n第三階段：關(guān)系DBMS的成熟與發(fā)展階段。從20世紀80年代以來，微機在性價比上的提高，使計算機進入各個領(lǐng)域。大量的信息系統(tǒng)的建立，要求計算機應(yīng)用領(lǐng)域從集中到分布，由單機到網(wǎng)絡(luò)，由信息管理、輔助決策到企業(yè)級的聯(lián)機事務(wù)處理。這一時期以客戶/服務(wù)器的體系結(jié)構(gòu)出現(xiàn)為標志。武漢大學(xué)數(shù)據(jù)庫原理課題組6.2 關(guān)系關(guān)系DBMS 關(guān)系DBMS經(jīng)歷了30多年的發(fā)展和演變，已經(jīng)取得了輝煌的成就，發(fā)展成了一門內(nèi)容豐富的學(xué)科，形成了總量達數(shù)百億美元

13、的一個軟件產(chǎn)業(yè)。關(guān)系數(shù)據(jù)庫已經(jīng)發(fā)展成為軟件產(chǎn)業(yè)中一個規(guī)模巨大、增長迅速的市場。 目前，市場上具有代表性的關(guān)系DBMS產(chǎn)品包括Oracle、DB2、SQL Server等。盡管由于互聯(lián)網(wǎng)應(yīng)用的興起，可擴展的標記語言（XML）格式的數(shù)據(jù)大量出現(xiàn)，需要新的數(shù)據(jù)模型與新技術(shù)支持，但關(guān)系技術(shù)仍然是主流，關(guān)系DBMS仍是當今最流行的數(shù)據(jù)庫軟件。無論是多媒體的內(nèi)容管理、XML數(shù)據(jù)支持，還是復(fù)雜對象支持等大多都是在關(guān)系系統(tǒng)內(nèi)核技術(shù)基礎(chǔ)上進行的擴展。武漢大學(xué)數(shù)據(jù)庫原理課題組6.2 關(guān)系關(guān)系DBMS2.應(yīng)用對關(guān)系DBMS的要求 數(shù)據(jù)的擴展、計算機硬件平臺的升級和數(shù)據(jù)庫應(yīng)用的延伸，推動著數(shù)據(jù)庫技術(shù)與系統(tǒng)的發(fā)展，數(shù)據(jù)

14、庫要管理的數(shù)據(jù)的復(fù)雜度和數(shù)據(jù)量都在迅速增長，計算機硬件平臺的發(fā)展仍然遵守著摩爾定律，數(shù)據(jù)庫應(yīng)用迅速向速度、廣度擴展。尤其是互聯(lián)網(wǎng)的出現(xiàn)，極大地改變了數(shù)據(jù)庫的應(yīng)用環(huán)境，向數(shù)據(jù)庫領(lǐng)域提出了前所未有的技術(shù)挑戰(zhàn)。應(yīng)用對關(guān)系DBMS的要求有：(1)具有高可靠性、高性能 數(shù)據(jù)庫是企業(yè)信息系統(tǒng)的核心和基礎(chǔ)，其可靠性和性能是企業(yè)領(lǐng)導(dǎo)人非常關(guān)心的問題。一旦宕機會給企業(yè)造成巨大的經(jīng)濟損失，甚至?xí)鸱杉m紛。(2)高可伸縮性和高安全性 從企業(yè)信息系統(tǒng)發(fā)展的角度看，一個系統(tǒng)的可擴展能力是非常重要的。數(shù)據(jù)的安全性是另一個重要的課題。武漢大學(xué)數(shù)據(jù)庫原理課題組6.2 關(guān)系關(guān)系DBMS(3)互聯(lián)訪問 互聯(lián)訪問是指數(shù)據(jù)庫系統(tǒng)

15、要支持互聯(lián)網(wǎng)環(huán)境下的應(yīng)用，支持信息系統(tǒng)之間的互操作，實現(xiàn)異構(gòu)數(shù)據(jù)庫間的數(shù)據(jù)交換和共享，要處理以XML類型的數(shù)據(jù)為代表的網(wǎng)上數(shù)據(jù)，甚至要考慮無線通信發(fā)展帶來的革命性變化。(4)協(xié)同服務(wù) 面向行業(yè)應(yīng)用領(lǐng)域要求，在DBMS核心基礎(chǔ)上，開發(fā)豐富的數(shù)據(jù)庫套件及應(yīng)用構(gòu)件，通過制造業(yè)信息化、電子政務(wù)等領(lǐng)域應(yīng)用套件捆綁，形成以DBMS為核心的面向行業(yè)的應(yīng)用軟件產(chǎn)品家族。滿足應(yīng)用需求、協(xié)同發(fā)展數(shù)據(jù)庫套件與應(yīng)用構(gòu)件，已成為當今數(shù)據(jù)庫技術(shù)與產(chǎn)品發(fā)展的新趨勢。規(guī)劃中的Oracle11i的主要擴展方面據(jù)稱主要也是各種面向應(yīng)用套件的支持。(5)開放平臺 許多國建愈來愈重視免費的開放源碼的Linux操作系統(tǒng)，因此能夠運行在

16、Linux上的數(shù)據(jù)庫管理系統(tǒng)已成為關(guān)系DBMS的方向之一。IBM和Oracle的關(guān)系DBMS都可以在Linux上運行。武漢大學(xué)數(shù)據(jù)庫原理課題組6.2 關(guān)系關(guān)系DBMS3. 關(guān)系DBMS的發(fā)展趨勢(1)產(chǎn)品系列化 一方面，Web和數(shù)據(jù)倉庫等應(yīng)用的興起，數(shù)據(jù)的絕對量在以驚人的速度迅速膨脹；另一方面，移動服務(wù)和嵌入式應(yīng)用快速增長。針對市場的不同需求，數(shù)據(jù)庫正在朝系列化方向發(fā)展。例如SQL Server：企業(yè)版、標準版、開發(fā)版、個人版。(2)支持互聯(lián)網(wǎng)應(yīng)用 數(shù)據(jù)庫系統(tǒng)是網(wǎng)絡(luò)時代的重要基礎(chǔ)設(shè)施之一。支持Internet應(yīng)用已經(jīng)成為數(shù)據(jù)庫系統(tǒng)的重要方面。此外，互聯(lián)網(wǎng)提供大量以XML數(shù)據(jù)為特征的半結(jié)構(gòu)化數(shù)據(jù)

17、，支持這種類型數(shù)據(jù)的存儲、共享、管理、檢索也是各數(shù)據(jù)庫廠商的發(fā)展方向。(3)智能化、集成化 數(shù)據(jù)豐富知識缺乏的現(xiàn)實直接導(dǎo)致了數(shù)據(jù)挖掘等技術(shù)的出現(xiàn)，促使數(shù)據(jù)庫向智能化方向發(fā)展。武漢大學(xué)數(shù)據(jù)庫原理課題組關(guān)系關(guān)系DBMSDBMS的發(fā)展階段及相關(guān)技術(shù)支持的發(fā)展階段及相關(guān)技術(shù)支持 第一階段第一階段第二階段第二階段第三階段第三階段對關(guān)系模型的支持表結(jié)構(gòu)支持支持支持關(guān)系操作不完善支持支持完整性無不完善支持運行環(huán)境單機單用戶有 有 有多用戶無有有網(wǎng)絡(luò)單機聯(lián)網(wǎng)無有有分布DB無有有C/S 環(huán)境無無有開放網(wǎng)絡(luò)異質(zhì)DB無無有 系統(tǒng)構(gòu)成RDBMS核心有有有擴充部分OS功能 無 無有集成、擴充工具無有有對應(yīng)用的支持信息管

18、理與決策不完善支持支持聯(lián)機事務(wù)處理(OLTP)無支持支持聯(lián)機分析處理(OLAP) 無無支持武漢大學(xué)數(shù)據(jù)庫原理課題組6.3 關(guān)系關(guān)系DBS的查詢優(yōu)化的查詢優(yōu)化1.查詢處理與查詢優(yōu)化查詢處理與查詢優(yōu)化(1)查詢處理中的優(yōu)化問題數(shù)據(jù)查詢是數(shù)據(jù)庫系統(tǒng)中最基本、最常用和最復(fù)雜的操作。對于同一個查詢要求，通?？梢詫?yīng)多個不同形式但相互等價的關(guān)系代數(shù)表達式。相同的查詢要求和結(jié)果存在著不同的執(zhí)行策略，不同的策略會導(dǎo)致不同的系統(tǒng)開銷。從查詢的多個執(zhí)行策略中進行合理選擇的過程就是“查詢處理過程中的優(yōu)化”，簡稱為查詢優(yōu)化。武漢大學(xué)數(shù)據(jù)庫原理課題組6.3 關(guān)系關(guān)系DBS的查詢優(yōu)化的查詢優(yōu)化(2)查詢優(yōu)化的基本途徑查詢

19、優(yōu)化的基本途徑可以分為用戶手動處理和機器自動處理兩種。對于非關(guān)系數(shù)據(jù)庫系統(tǒng)，由于用戶通常使用低層次的語義表達查詢要求，任何的查詢策略的選取只能由用戶自己去完成。關(guān)系數(shù)據(jù)庫查詢優(yōu)化是由機器自動處理。以關(guān)系數(shù)據(jù)理論為基礎(chǔ)，建立起由系統(tǒng)通過機器自動完成查詢優(yōu)化的有效機制。關(guān)系數(shù)據(jù)庫查詢語言可以設(shè)計成非過程化的，即用戶只需要表述做什么，而不需要關(guān)心如何做，查詢處理和查詢優(yōu)化的過程由系統(tǒng)自動完成。武漢大學(xué)數(shù)據(jù)庫原理課題組6.3 關(guān)系關(guān)系DBS的查詢優(yōu)化的查詢優(yōu)化(3)查詢優(yōu)化器查詢優(yōu)化的總目標是選擇有效的策略，求得給定關(guān)系表達式的值。由關(guān)系數(shù)據(jù)庫管理系統(tǒng)自動生成若干候選查詢計劃并從中選取較優(yōu)的查詢計劃的

20、程序成為查詢優(yōu)化器。由系統(tǒng)自動優(yōu)化的主要原因： 優(yōu)化器可以從數(shù)據(jù)字典中獲取許多統(tǒng)計信息，并根據(jù)這些信息選擇有效地執(zhí)行計劃，而用戶程序則難以獲得這些信息。 如果數(shù)據(jù)庫的物理統(tǒng)計信息改變了，那么系統(tǒng)可以自動對查詢進行重新優(yōu)化以選擇相適應(yīng)的執(zhí)行計劃，而在非關(guān)系系統(tǒng)中必須重寫程序。武漢大學(xué)數(shù)據(jù)庫原理課題組6.3 關(guān)系關(guān)系DBS的查詢優(yōu)化的查詢優(yōu)化 優(yōu)化器可以考慮數(shù)百種不同的執(zhí)行計劃，而程序員一般只能考慮有限的幾種可能性。 優(yōu)化器中包括了很多復(fù)雜的優(yōu)化技術(shù)，這些優(yōu)化技術(shù)往往只有最好的程序員才能掌握。系統(tǒng)的自動優(yōu)化相當于使所有人都擁有這些優(yōu)化技術(shù)。(4)查詢優(yōu)化技術(shù)的分類 規(guī)則優(yōu)化查詢僅僅涉及查詢語句本身

21、，根據(jù)某些啟發(fā)式規(guī)則如“先選擇、投影，后連接”等就可以完成優(yōu)化，稱之為規(guī)則優(yōu)化。這類優(yōu)化的特點是對查詢的關(guān)系代數(shù)表達式進行等價變化，以減少執(zhí)行開銷，所以也稱為代數(shù)優(yōu)化。武漢大學(xué)數(shù)據(jù)庫原理課題組6.3 關(guān)系關(guān)系DBS的查詢優(yōu)化的查詢優(yōu)化 物理優(yōu)化優(yōu)化與數(shù)據(jù)的物理組織和訪問路徑有關(guān)，例如已經(jīng)組織了基于查詢的專門索引或者排序文件的情況下，就需要對如何選擇實現(xiàn)策略進行必要的考慮，諸如此類的問題就是物理優(yōu)化。n 代價估算優(yōu)化對于多個候選策略逐個進行執(zhí)行代價估算，從中選擇代價最小的作為執(zhí)行策略，就稱為代價估算優(yōu)化。規(guī)則優(yōu)化要對查詢的關(guān)系代數(shù)表達式進行等價變換，物理優(yōu)化涉及數(shù)據(jù)文件的組織方式，代價估算優(yōu)化開

22、銷較大，它們都適合于一定的場合。實際中的查詢優(yōu)化通常是將幾種技術(shù)結(jié)合使用。武漢大學(xué)數(shù)據(jù)庫原理課題組6.3 關(guān)系關(guān)系DBS的查詢優(yōu)化的查詢優(yōu)化(5)關(guān)系查詢處理過程 在層次數(shù)據(jù)庫和網(wǎng)狀數(shù)據(jù)庫中，采用的是導(dǎo)航式操作，即查詢語句既要包含查詢的條件與結(jié)果，還要描述實現(xiàn)此查詢的過程。在關(guān)系數(shù)據(jù)庫當中，由于關(guān)系表達式具有高度的語義層次，故使相應(yīng)的查詢語句重在表達查詢條件和查詢結(jié)果，而將查詢的具體實施過程及查詢策略選擇交給DBMS承擔。對用戶而言，關(guān)系數(shù)據(jù)查詢具有非過程性的顯著特征。武漢大學(xué)數(shù)據(jù)庫原理課題組6.3 關(guān)系關(guān)系DBS的查詢優(yōu)化的查詢優(yōu)化(6)查詢優(yōu)化的必要性在單機數(shù)據(jù)庫中：總代價 = I/O代價

23、 + CPU代價 在多用戶環(huán)境下：總代價 = I/O代價 + CPU代價 + 內(nèi)存代價在網(wǎng)絡(luò)環(huán)境下： 總代價 = I/O代價 + CPU代價 + 內(nèi)存代價+ 網(wǎng)絡(luò)代價 查詢的執(zhí)行開銷與多個因素有關(guān)：軟件環(huán)境、硬件環(huán)境、數(shù)據(jù)量、方法。難以精確分析，故僅進行定性說明。武漢大學(xué)數(shù)據(jù)庫原理課題組例:Student表有l(wèi)000個學(xué)生記錄，每人平均選10門課程， SC表共有1000*10=l0000個選課記錄。要求: 查學(xué)生“王林”所選課程的成績在85分以上的課程號。SELECT CnoFROM S，SCWHERE S.Sno=SC.Sno AND Sname=王林 AND Grade 85 ；等價的關(guān)系

24、代數(shù)表示：等價的關(guān)系代數(shù)表示： Cno( F1 F2 F3 ( SSC ) ) Cno( F2 F3 ( S SC ) ) Cno( F2 (S) F3 (SC) ) 條件 F1 條件 F2 條件 F3分析：哪種效率高？武漢大學(xué)數(shù)據(jù)庫原理課題組 Cno(F1F2F3(SSC) Cno(F2F3(SSC) Cno(F2(S) F3(SC) v 先在兩表上做 ，產(chǎn)生1000*10000=107個連接記錄，再在其上進行先后操作。其基本運算的次數(shù)為：3*107。v 先在兩個表上做 ，產(chǎn)生1000*10=104個連接記錄，再在其上進行先后操作。其基本運算的次數(shù)為：107+2*104。v 先分別在兩個表上

25、做,再做 ，產(chǎn)生1*10=10個連接記錄，再在其上進行 。其基本運算的次數(shù)為：104+103+2*101。n連接時間復(fù)雜度為： O(107) O(104) O(101)武漢大學(xué)數(shù)據(jù)庫原理課題組 2. 查詢優(yōu)化的一般策略查詢優(yōu)化的一般策略n1) 選擇運算應(yīng)盡可能先做。n2) 在執(zhí)行連接前對關(guān)系適當?shù)仡A(yù)處理。 其方法有：索引連接方法、排序合并連接方法。snocnograde200101001902001010028720010100372210101001852101010026222010100470snosname200101王蕭虎200102李云鋼210101郭敏星210102高 靈2201

26、01王 睿排序合并法：O(n+m)武漢大學(xué)數(shù)據(jù)庫原理課題組 2. 查詢優(yōu)化的一般策略查詢優(yōu)化的一般策略3) 把投影運算和選擇運算同時進行。 例： Sno( Grade90(SC)4) 把投影同其前或其后的雙目運算結(jié)合起來。 例： Sno(S1-S2) 、 S1 Sno (S2)5) 把某些選擇同在它前面要執(zhí)行的笛卡爾積結(jié)合起來成為一個連接運算。 例： R. A S. C(RS)= R S AC 6) 找出公共子表達式。武漢大學(xué)數(shù)據(jù)庫原理課題組6.3 關(guān)系關(guān)系DBS的查詢優(yōu)化的查詢優(yōu)化3. 3. 關(guān)系代數(shù)表達式的等價規(guī)則關(guān)系代數(shù)表達式的等價規(guī)則關(guān)系代數(shù)表達式的等價:兩個關(guān)系表達式El和E2是等價

27、的，可記為E1E2。常用的等價變換規(guī)則:（連接、笛卡爾積的結(jié)合、交換律）3）投影的串接定律 A1,A2An (B1,B2.Bn (E) A1,A2An (E)4）選擇的串接定律 F1( F2 (E) F1 F2 (E) 5）選擇與投影的交換律(兩種形式） （1）若F只涉及A1,A2An 屬性： A1，A2An ( F (E) F ( A1,A2An (E)子集子集武漢大學(xué)數(shù)據(jù)庫原理課題組3. 關(guān)系代數(shù)關(guān)系代數(shù)等價規(guī)則等價規(guī)則 (2)若F中還涉及 其他屬性B1，. Bn： A1,A2An ( F (E) A1，A2An ( F (A1，A2 An，B1 ， Bn(E) 6)選擇與笛卡兒積的交換律

28、 F (E1XE2) F1 ( E1) X F2 ( E2)F1只涉及E1中屬性 F中涉及的其他屬性武漢大學(xué)數(shù)據(jù)庫原理課題組3. 關(guān)系代數(shù)關(guān)系代數(shù)等價規(guī)則等價規(guī)則 7)選擇與并的交換設(shè)E=E1E2，E1,E2有相同的屬性名，則 F (E1 E2) F ( E1) F ( E2)8)選擇與差運算的交換設(shè)E1,E2有相同的屬性名，則 F (E1-E2) F ( E1) - F ( E2)武漢大學(xué)數(shù)據(jù)庫原理課題組3. 關(guān)系代數(shù)關(guān)系代數(shù)等價規(guī)則等價規(guī)則 是E1中屬性9)投影與笛卡兒積的交換律 A1,A2An，B1,Bn (E1XE2) A1,A2An (E1) X B1,B2 Bn(E2)該式使得投影

29、在笛卡爾積之前先做，以減少連接數(shù)量。10)投影與并的交換設(shè)E1和E2有相同的屬性名，則A1,A2,An(E1E2) A1,A2,An(E1)A1,A2,An(E2) 武漢大學(xué)數(shù)據(jù)庫原理課題組3. 關(guān)系代數(shù)關(guān)系代數(shù)等價規(guī)則等價規(guī)則11.選擇對自然連接的分配律:若F中涉及屬性都是El中屬性,則： (1) F(El E2) F(El) E2 若F=F1F2,并且F1只涉及E1中、F2只涉及E2中的屬性,則： (2) F(E1 E2) F1(El) F2(E2)12. 選擇與連接操作的結(jié)合：設(shè)A1,An是E1的屬性,B1,Bm 是E2的屬性，F(xiàn)為形如：E1.AiE2.Bj所組成的合取式則： F(ElE

30、2) El E2 F例:cno( F1F2 F3(StudentSC) /式 = cno( F2F3( F1(StudentSC) /用規(guī)則4得到 = cno( F2F3(Student SC) /用規(guī)則12得式 = cno( F2(Student) F3(SC) /再用規(guī)則11得式武漢大學(xué)數(shù)據(jù)庫原理課題組4. 關(guān)系代數(shù)表達式的優(yōu)化算法關(guān)系代數(shù)表達式的優(yōu)化算法n算法：關(guān)系表達式的優(yōu)化。算法：關(guān)系表達式的優(yōu)化。 輸入：一個關(guān)系表達式的語法樹。 輸出：計算該表達式的程序。 （1）用規(guī)則4把形如: F1F2. (E) 變?yōu)? F1(F2.(E) 再利用規(guī)則58 把每一個選擇運算盡可能移到樹的葉端。

31、（2）對每個投影用規(guī)則3、5、9、l0，盡量把它移向樹的葉端 （3）利用規(guī)則35把選擇和投影的串接合并成單個選擇、單個投影或一個選擇后跟一個投影。使多個選擇或投影能同時執(zhí)行，或在一次掃描中全部完成， （4）使用規(guī)則12 使選擇運算與笛卡爾積結(jié)合成連接運算。 （5）對語法樹中的內(nèi)節(jié)點進行分組。 （6）找出查詢樹中的公共子樹。 （7）輸出由分組結(jié)果得到的優(yōu)化語法樹。 例例SRA F五種基本五種基本運算表示運算表示武漢大學(xué)數(shù)據(jù)庫原理課題組6.3 關(guān)系關(guān)系DBS的查詢優(yōu)化的查詢優(yōu)化n生成、選擇查詢計劃。用到查詢優(yōu)化的一般策略n5.查詢優(yōu)化的一般步驟：查詢優(yōu)化的一般步驟：n將查詢表示成關(guān)系代數(shù)語法樹。n

32、根據(jù)變換規(guī)則將其轉(zhuǎn)換成標準優(yōu)化形式。n選擇低層的操作算法。 對語法樹中的每一操作需要根據(jù)存取路徑、數(shù)據(jù)的分布、聚簇等信息來選擇具體的執(zhí)行算法。武漢大學(xué)數(shù)據(jù)庫原理課題組6.4 關(guān)系關(guān)系DBMSDBMS產(chǎn)品及其選擇產(chǎn)品及其選擇產(chǎn)品名稱產(chǎn)品名稱開發(fā)公司開發(fā)公司簡介簡介MS-SQL ServerMicrosoft是Windows平臺上最為流行的中型關(guān)系型數(shù)據(jù)庫管理系統(tǒng)，采用客戶/服務(wù)器體系結(jié)構(gòu)，圖形化用戶界面，支持Web技術(shù)，支持多種數(shù)據(jù)庫文件的導(dǎo)入。是一個可擴展的、高性能的數(shù)據(jù)庫管理系統(tǒng)。以其內(nèi)置的數(shù)據(jù)復(fù)制功能、強大的管理工具、與Internet的緊密集成和開放的系統(tǒng)結(jié)構(gòu)，提供了一個出眾的數(shù)據(jù)庫平臺

33、。即將推出版本 SQL Server 2008。AccessMicrosoft基于Windows平臺的桌面式的小型關(guān)系型數(shù)據(jù)庫管理系統(tǒng)，單文件型數(shù)據(jù)庫，是Office軟件包的一個組成部分，有可視化開發(fā)環(huán)境。目前比較流行的開發(fā)工具都支持Access數(shù)據(jù)庫。最新版本2003。Visual FoxproMicrosoft基于Windows平臺的兼?zhèn)鋺?yīng)用程序開發(fā)和數(shù)據(jù)庫管理功能的小型關(guān)系型數(shù)據(jù)庫管理系統(tǒng)，其數(shù)據(jù)庫可以升遷為Oracle和MS-SQL Server，可以開發(fā)桌面、客戶/服務(wù)器體系結(jié)構(gòu)和Web的數(shù)據(jù)庫應(yīng)用程序，新版支持.NET框架。最新版本VFP 8.0。OracleOracle在數(shù)據(jù)庫領(lǐng)

34、域一直處于領(lǐng)先地位，是世界上使用最廣泛的大型關(guān)系型數(shù)據(jù)庫管理系統(tǒng)，其1999年推出的Oracle8i是世界上第一個互聯(lián)網(wǎng)數(shù)據(jù)庫產(chǎn)品，最新產(chǎn)品Oracle 11G。DB2IBMDB2 UDB（通用數(shù)據(jù)庫）是為UNIX、OS/2、Windows NT提供的關(guān)系型數(shù)據(jù)庫解決方案，能夠在各種系統(tǒng)中運用，最新版本 DB2 9.0。SybaseSybase是一個以“客戶/服務(wù)器數(shù)據(jù)庫體系結(jié)構(gòu)”為開發(fā)目標的面向聯(lián)機事務(wù)處理的大型關(guān)系型數(shù)據(jù)庫管理系統(tǒng)。最新版本 Sybase 12。武漢大學(xué)數(shù)據(jù)庫原理課題組6.4 關(guān)系關(guān)系DBMSDBMS產(chǎn)品及其選擇產(chǎn)品及其選擇1.SQL Server SQL Server是微

35、軟推出的適用于大型網(wǎng)絡(luò)環(huán)境的數(shù)據(jù)產(chǎn)品，一經(jīng)推出就得到了廣大用戶的積極響應(yīng)并迅速占領(lǐng)了NT環(huán)境下的數(shù)據(jù)庫領(lǐng)域，成為數(shù)據(jù)庫市場上的一個重要產(chǎn)品。 SQL Server 2000是一種典型的具有客戶/服務(wù)器體系架構(gòu)的關(guān)系數(shù)據(jù)庫管理系統(tǒng)，它使用Transact-SQL語句在服務(wù)器和客戶機之間傳送請求和回應(yīng)，具有可靠性、可伸縮性、可管理性、可用性等特點。它支持大規(guī)模聯(lián)機事務(wù)處理（OLTP）、數(shù)據(jù)倉庫、數(shù)據(jù)挖掘和電子商務(wù)等應(yīng)用。它的出現(xiàn)極大地推動了數(shù)據(jù)庫的應(yīng)用和普及，無論是在功能上，還是在安全性、可維護性和易操作性上都較以前版本有了很大提高。武漢大學(xué)數(shù)據(jù)庫原理課題組6.4 關(guān)系關(guān)系DBMSDBMS產(chǎn)品及其

36、選擇產(chǎn)品及其選擇A.SQL Server 20000的功能特點的功能特點(1)網(wǎng)絡(luò)性能好SQL Server 2000與其他產(chǎn)品共同提供了可靠安全的Internet和Intranet系統(tǒng)的數(shù)據(jù)存儲功能，其數(shù)據(jù)庫引擎提供完整的可擴展標記語言(XML)支持。此外，提供了English Query和Microsoft檢索服務(wù)等功能，在Web應(yīng)用程序中實現(xiàn)了友好的用戶查詢功能和強大的數(shù)據(jù)檢索功能。(2)可伸縮性和可用性SQL Server 2000數(shù)據(jù)庫引擎可以在Windows 2000的各個版本等操作系統(tǒng)上運行。同時當以默認設(shè)置運行時，SQL Server 2000還具有動態(tài)自調(diào)整功能，可以有效地運

37、行在便攜式電腦和臺式機中，用戶無須承擔管理任務(wù)。其企業(yè)版支持聯(lián)合服務(wù)器、索引視圖和大型內(nèi)存支持等功能，使其可以升級到Web站點所需的最高性能級別。武漢大學(xué)數(shù)據(jù)庫原理課題組6.4 關(guān)系關(guān)系DBMSDBMS產(chǎn)品及其選擇產(chǎn)品及其選擇(3)提供較完善的數(shù)據(jù)庫功能SQL Server 2000關(guān)系數(shù)據(jù)庫引擎支持當今苛刻的數(shù)據(jù)處理環(huán)境所需的功能，如分布式查詢、動態(tài)行級鎖定、充分的完整性保護、分布式事務(wù)、復(fù)制等功能，為用戶提供安全的企業(yè)級數(shù)據(jù)庫功能。(4)支持數(shù)據(jù)倉庫SQL Server 2000包含多個可用于生成有效地支持決策、支持處理需求的數(shù)據(jù)倉庫的組件。這些組件包括：數(shù)據(jù)倉庫框架，數(shù)據(jù)轉(zhuǎn)換服務(wù)，聯(lián)機分

38、析處理支持，數(shù)據(jù)挖掘支持，English Query，Meta Data Services。(5)易于安裝和使用SQL Server 2000中包含了一系列管理和開發(fā)工具，這些工具可以在多個站點上安裝、部署、管理和使用SQL Server 數(shù)據(jù)庫。武漢大學(xué)數(shù)據(jù)庫原理課題組6.4 關(guān)系關(guān)系DBMSDBMS產(chǎn)品及其選擇產(chǎn)品及其選擇B.SQL Server 的基本服務(wù)的基本服務(wù)SQL Server 2000提供了四種基本的服務(wù)類型，即SQL Server 服務(wù)、代理服務(wù)（SQL Server Agent）、分布式事務(wù)處理協(xié)調(diào)器（Distributed Transaction Coordinator，

39、DTC）以及全文檢索服務(wù)（Microsoft Search）。(1) SQL Server 服務(wù)SQL Server 服務(wù)是SQL Server 2000的核心服務(wù)。它直接管理和維護數(shù)據(jù)庫，負責處理所有來自客戶端的Transact-SQL語句并管理服務(wù)器上構(gòu)成數(shù)據(jù)庫的所有文件，同時還負責處理存儲過程，并將執(zhí)行結(jié)果返回給客戶端。其他服務(wù)都依賴于此服務(wù)。武漢大學(xué)數(shù)據(jù)庫原理課題組6.4 關(guān)系關(guān)系DBMSDBMS產(chǎn)品及其選擇產(chǎn)品及其選擇(2) 代理服務(wù)對那些需要定期進行的管理工作，SQL Server 2000提供了一種稱為代理的功能。這個代理能夠根據(jù)系統(tǒng)管理員預(yù)先設(shè)定好的計劃自動執(zhí)行相應(yīng)的功能，同時它還能對系統(tǒng)管理員設(shè)定好的錯誤等特定事件自動報警，而且代理服務(wù)還能通過電子郵件等方式把系統(tǒng)存在的各種問題發(fā)送給指定的用戶。這種服務(wù)能很好