了得網計算機/網絡_數據庫管理繫統概論

編輯推薦

數據庫管理繫統已經成為繼操作繫統之後*復雜的繫統軟件。本書詳盡介紹了數據庫管理繫統的體繫結構、各大基本功能以及實現技術。本書可以做為院校師生的輔助教材，做為數據庫基礎原理的後繼學習資料，加深對握數據庫管理繫統原理的理解；也可供數據庫管理員和數據庫繫統開發人員參考，使他們從宏觀、總體的角度掌握數據庫管理繫統的基本概念和基本原理，了解數據庫管理繫統與操作繫統之間的運作原理，以更好的使用和維護數據庫管理繫統。

內容簡介

本書繫統闡述數據庫技術的核心軟件——數據庫管理繫統，詳細講解其基本功能、工作模式、繫統結構和實現技術，並對新型數據庫管理繫統予以介紹和展望，為有興趣的讀者指明研讀方向。全書共分為11章：第1章緒論；第2章數據庫管理繫統的數據組織與存儲；第3章DBMS數據定義、操縱與完整性約束；第4章查詢處理；第5章查詢優化；第6章事務；第7章並發控制；第8章數據庫安全；第9章數據庫恢復；第10章數據庫管理繫統性能配置；第11章新型數據庫管理繫統。
本書可以作為高等學校計算機類專業、信息管理與信息繫統等相關專業本科生和研究生“數據庫”及相關課程的教材或教學參考書，也可供從事數據庫管理繫統研究、開發和應用的人員參考。

目錄
第1章緒論1
1.1數據庫管理繫統1
1.1.1數據庫管理繫統概述1
1.1.2數據庫管理繫統工作模式2
1.2數據庫管理繫統結構3
1.2.1應用層4
1.2.2語言處理層4
1.2.3存儲管理層4
1.3語言處理層5
1.4存儲管理層7
1.4.1數據存取7
1.4.2緩衝區管理7
1.4.3數據存儲的物理組織8目錄
第1章緒論1
1.1數據庫管理繫統1
1.1.1數據庫管理繫統概述1
1.1.2數據庫管理繫統工作模式2
1.2數據庫管理繫統結構3
1.2.1應用層4
1.2.2語言處理層4
1.2.3存儲管理層4
1.3語言處理層5
1.4存儲管理層7
1.4.1數據存取7
1.4.2緩衝區管理7
1.4.3數據存儲的物理組織8
1.5數據庫管理繫統基本功能10
1.6小結11
思考題11
第2章數據庫管理繫統的數據組織與存儲13
2.1數據庫繫統存儲結構13
2.1.1數據庫磁盤存儲器中的數據結構13
2.1.2數據庫繫統存儲介質16
2.1.3存儲介質層次結構18
2.2數據文件的記錄格式19
2.2.1定長記錄格式19
2.2.2變長記錄格式22數據庫管理繫統概論目錄2.3數據文件格式23
2.3.1文件格式23
2.3.2順序文件24
2.3.3聚集文件25
2.4索引技術26
2.4.1索引基本概念26
2.4.2順序索引27
2.4.3輔助索引30
2.4.4索引的更新31
2.4.5索引的自動生成32
2.5B 樹索引文件32
2.5.1B 樹結構33
2.5.2B 樹的查詢34
2.5.3B 樹的更新35
2.5.4B 樹文件組織36
2.5.5B樹索引文件37
2.6散列索引文件38
2.6.1散列技術38
2.6.2靜態散列索引40
2.6.3可擴充散列結構42
2.7小結45
思考題46
第3章DBMS數據定義、操縱與完整性約束47
3.1SQL概述47
3.1.1數據定義語言48
3.1.2數據操縱語言48
3.1.3數據完整性控制48
3.1.4數據控制語言48
3.1.5事務管理48
3.1.6嵌入式SQL和動態SQL48
3.2項目工程公司數據庫49
3.3DBMS數據定義52
3.3.1模式的定義與刪除53
3.3.2基本表的定義、修改與刪除54
3.3.3視圖建立與刪除簡介57
3.3.4索引的建立、修改與刪除57
3.4DBMS數據操縱58
3.4.1數據查詢58
3.4.2數據更新67
3.4.3視圖69
3.5DBMS完整性約束74
3.5.1完整性概述74
3.5.2實體完整性75
3.5.3參照完整性77
3.5.4非空約束79
3.5.5約束79
3.5.6CHECK約束80
3.5.7完整性約束命名80
3.5.8觸發器81
3.6小結84
思考題84
第4章查詢處理87
4.1概述87
4.2查詢的選擇運算實現89
4.2.1使用單文件掃描和索引的選擇89
4.2.2涉及比較的選擇91
4.2.3復合條件選擇92
4.3查詢的排序處理93
4.3.1外部歸並排序算法93
4.3.2外部歸並排序的代價分析94
4.4查詢的連接處理95
4.4.1嵌套循環算法95
4.4.2索引嵌套循環連接96
4.4.3歸並連接算法96
4.4.4散列連接算法98
4.5表達式計算101
4.5.1物化101
4.5.2流水線101
4.6小結102
思考題103
第5章查詢優化105
5.1概述105
5.2代數優化106
5.2.1關繫代數表達式等價變換規則106
5.2.2基於啟發式規則的代數優化108
5.2.3代數優化實例109
5.3物理優化112
5.3.1基於啟發式規則的物理優化112
5.3.2基於代價估算的物理優化113
5.4基於語義的查詢優化113
5.5小結114
思考題114
第6章事務115
6.1事務的概念115
6.2事務的ACID性質116
6.3一個簡單的事務實例116
6.4事務抽像模型與狀態變遷118
6.5SQL中事務的存取模式和隔離級別120
6.6小結121
思考題121
第7章並發控制123
7.1事務的並發執行123
7.1.1事務並發執行的必要性123
7.1.2事務並發執行趨勢124
7.1.3並發操作帶來的問題124
7.1.4並發事務調度可串行化與可恢復性126
7.1.5並發控制技術133
7.2封鎖技術134
7.2.1封鎖類型134
7.2.2封鎖協議135
7.2.3兩段鎖協議138
7.2.4封鎖的實現141
7.3封鎖帶來的問題142
7.3.1活鎖142
7.3.2死鎖142
7.4多粒度封鎖145
7.4.1多粒度樹145
7.4.2意向鎖146
7.4.3多粒度封鎖協議148
7.5時間戳技術148
7.5.1時間戳148
7.5.2時間戳排序協議149
7.5.3改進的時間戳協議——Thomas寫規則150
7.6多版本機制與快照隔離151
7.6.1多版本並發控制151
7.6.2多版本兩段鎖協議152
7.6.3快照隔離153
7.7幻行現像155
7.8小結157
思考題158
第8章數據庫安全159
8.1數據庫安全概述159
8.1.1威脅數據庫的安全因素159
8.1.2數據庫安全標準簡介160
8.2數據庫繫統安全控制163
8.2.1數據庫繫統安全模型163
8.2.2數據庫管理繫統安全性控制模型163
8.2.3用戶身份標識與鋻別164
8.3存取控制概述165
8.3.1自主存取控制166
8.3.2強制存取控制172
8.4審計173
8.4.1審計事件173
8.4.2審計的作用174
8.4.3AUDIT語句和NOAUDIT語句174
8.4.4ORACLE的審計技術174
8.5數據加密175
8.5.1加密技術175
8.5.2數據庫中的加密支持176
8.6更高安全性保護177
8.6.1推理控制177
8.6.2隱蔽信道178
8.6.3數據隱私179
8.7小結179
思考題180
第9章數據庫恢復181
9.1故障類型181
9.1.1事務故障181
9.1.2繫統故障182
9.1.3介質故障182
9.2恢復機制下的存儲器與數據訪問182
9.2.1存儲器種類182
9.2.2穩定存儲器的實現183
9.2.3事務數據訪問機制183
9.3恢復的基本原理與實現方法184
9.3.1恢復與事務原子性184
9.3.2日志恢復的基本原則與實現方法185
9.3.3影子復制恢復的基本原理185
9.4日志恢復技術186
9.4.1數據轉儲186
9.4.2日志文件格式187
9.4.3日志登記原則188
9.4.4使用日志重做和撤銷事務189
9.4.5檢查點191
9.5緩衝區管理192
9.5.1日志記錄緩衝192
9.5.2數據庫緩衝193
9.5.3模糊檢查點194
9.6恢復算法194
9.6.1事務故障恢復——事務回滾195
9.6.2繫統故障恢復195
9.6.3介質故障後的恢復197
9.7ARIES恢復技術197
9.7.1ARIES特點198
9.7.2ARIES數據結構198
9.7.3ARIES恢復算法200
9.7.4ARIES恢復算法特征202
9.8容災備份繫統203
9.9小結205
思考題206
第10章數據庫管理繫統性能配置207
10.1性能配置207
10.1.1瓶頸位置208
10.1.2硬件調整208
10.1.3數據庫繫統參數調整210
10.1.4模式與事務調整210
10.2性能基準程序211
10.2.1任務集211
10.2.2數據庫應用類型212
10.2.3TPC基準測試213
10.3數據庫標準217
10.3.1SQL標準217
10.3.2數據庫連接標準218
10.3.3對像數據庫標準218
10.3.4XML標準218
10.4小結219
思考題219
第11章新型數據庫管理繫統221
11.1數據庫管理繫統發展的三個階段222
11.1.1代數據庫管理繫統——基於格式化模型DBMS222
11.1.2第二代數據庫管理繫統——關繫DBMS222
11.1.3第三代數據庫管理繫統——新一代DBMS222
11.2基於新型數據模型的數據庫管理繫統223
11.2.1面向對像數據庫管理繫統223
11.2.2關繫對像數據庫管理繫統224
11.2.3XML數據庫管理繫統224
11.3大數據管理繫統225
11.3.1大數據225
11.3.2大數據建模——基於分析的用戶建模227
11.3.3大數據管理繫統228
11.4小結230
思考題231
參考文獻232

前言

出版說明在我國高等教育逐步實現大眾化後，越來越多的高等學校將會面向國民經濟發展的線，為行業、企業培養各級各類高級應用型專門人纔。為此，*已經啟動了“高等學校教學質量和教學改革工程”，強調要以信息技術為手段，深化教學改革和人纔培養模式改革。如何根據社會的實際需要，根據各行各業的具體人纔需求，培養具有特色顯著的人纔，是我們共同面臨的重大問題。具體地，培養具有一定專業特色的和特定能力強的計算機專業應用型人纔則是計算機教育要解決的問題。
為了適應21世紀人纔培養的需要，培養具有特色的計算機人纔，急需一批適合各種人纔培養特點的計算機專業教材。目前，一些高校在計算機專業教學和教材改革方面已經做了大量工作，許多教師在計算機專業教學和科研方面已經積累了許多寶貴經驗。將他們的教研成果轉化為教材的形式，向全國其他學校推廣，對於深化我國高等學校的教學改革是一件十分有意義的事。
清華大學出版社在經過大量調查研究的基礎上，決定編寫出版一套“普通高校本科計算機專業特色教材精選”。本套教材是針對當前高等教育改革的新形勢，以社會對人纔的需求為導向，主要以培養應用型計算機人纔為目標，立足課程改革和教材創新，廣泛吸納全國各地的高等院校計算機優秀教師參與編寫，從中精選出版確實反映計算機專業教學方向的特色教材，供普通高等院校計算機專業學生使用。出版說明在我國高等教育逐步實現大眾化後，越來越多的高等學校將會面向國民經濟發展的線，為行業、企業培養各級各類高級應用型專門人纔。為此，*已經啟動了“高等學校教學質量和教學改革工程”，強調要以信息技術為手段，深化教學改革和人纔培養模式改革。如何根據社會的實際需要，根據各行各業的具體人纔需求，培養具有特色顯著的人纔，是我們共同面臨的重大問題。具體地，培養具有一定專業特色的和特定能力強的計算機專業應用型人纔則是計算機教育要解決的問題。
為了適應21世紀人纔培養的需要，培養具有特色的計算機人纔，急需一批適合各種人纔培養特點的計算機專業教材。目前，一些高校在計算機專業教學和教材改革方面已經做了大量工作，許多教師在計算機專業教學和科研方面已經積累了許多寶貴經驗。將他們的教研成果轉化為教材的形式，向全國其他學校推廣，對於深化我國高等學校的教學改革是一件十分有意義的事。
清華大學出版社在經過大量調查研究的基礎上，決定編寫出版一套“普通高校本科計算機專業特色教材精選”。本套教材是針對當前高等教育改革的新形勢，以社會對人纔的需求為導向，主要以培養應用型計算機人纔為目標，立足課程改革和教材創新，廣泛吸納全國各地的高等院校計算機優秀教師參與編寫，從中精選出版確實反映計算機專業教學方向的特色教材，供普通高等院校計算機專業學生使用。
本套教材具有以下特點：
1. 編寫目的明確
本套教材是深入研究各地各學校辦學特色的基礎上，面向普通高校的計算機專業學生編寫的。學生通過本套教材，主要學習計算機科學與技術專業的基本理論和基本知識，接受利用計算機解決實際問題的基本訓練，培養研究和開發計算機繫統，特別是應用繫統的基本能力。2. 理論知識與實踐訓練相結合
根據計算學科的三個學科形態及其關繫，本套教材力求突出學科理論與實踐緊密結合的特征，結合實例講解理論，使理論來源於實踐，又進一步指導實踐得到自然的體現，使學生通過實踐深化對理論的理解，更重要的是使學生學會理論方法的實際運用。
3. 注意培養學生的動手能力
數據庫管理繫統概論出版說明每種教材都增加了能力訓練部分的內容，學生通過學習和練習，能比較熟練地應用計算機知識解決實際問題。既注意培養學生分析問題的能力，也注重培養學生解決問題的能力，以適應新經濟時代對人纔的需要，滿足就業要求。
4. 注重教材的立體化配套
大多數教材都將陸續配套教師用課件、習題及其解答提示，學生上機實驗指導等輔助教學資源，有些教材還提供能用於網上下載的文件，以方便教學。
由於各地區各學校的培養目標、教學要求和辦學特色均有所不同，所以對特色教學的理解也不盡一致，我們懇切希望大家在使用教材的過程中，及時地給我們提出批評和改進意見，以便我們做好教材的修訂改版工作，使其日趨完善。
我們相信經過大家的共同努力，這套教材一定能成為特色鮮明、質量上乘的優秀教材，同時，我們也希望通過本套教材的編寫出版，為“高等學校教學質量和教學改革工程”作出貢獻。

清華大學出版社前言數據庫管理繫統是對數據進行存儲、管理、處理與維護的繫統軟件，是數據庫技術的核心部分。隨著計算機硬件、軟件技術的迅速發展，數據庫技術在各行各業的廣泛應用以及大數據時代的到來，數據庫管理繫統的理論與技術及其發展越來越成為計算機科學與技術教育中必不可少的部分。
本書詳細講述數據庫管理繫統的基本概念、工作模式、體繫結構、功能模塊組成以及主流實現技術；並介紹大數據時代下，數據庫管理繫統發展的新興成果與方向。
全書分為11章，第1章對數據庫管理繫統及其工作模式、繫統結構與主要功能進行綜述；第2章講述數據庫管理繫統的數據組織與存儲，包括記錄格式、文件格式、索引結構與實現技術；第3章講述數據庫管理繫統的數據操縱與數據完整性約束；第4章講述查詢處理，包括查詢處理的一般步驟、選擇運算實現、排序與連接處理、表達式計算；第5章講述查詢優化，包括代數優化與物理優化；第6章講述數據庫管理繫統運行與管理的基本單位——事務；第7章講述並發控制，包括並發操作問題、並發事務調度的可串行化與可恢復性、並發控制主流技術，重點討論封鎖技術；第8章講述數據庫安全性控制，基於數據庫繫統安全模型與數據庫管理繫統安全控制模型討論自主存取控制、審計、強制存取控制、數據加密等DBMS安全性措施；第9章講述數據庫恢復，包括故障類型、恢復原理、恢復算法、恢復算法ARIES以及容災備份機制等；第10章講述數據庫管理繫統性能配置；第11章介紹新型數據庫管理繫統，包括面向對像數據庫管理繫統、對像關繫數據庫管理繫統、XML數據庫管理繫統、大數據管理繫統。
本書針對數據庫管理繫統的內容詳細豐富，彌補了數據庫教學中對DBMS原理、實現技術與算法涉及不深的不足。讀者可以根據需要閱讀或者學習書中部分章節。數據庫管理繫統概論全書由徐述組織與執筆。湖南城市學院習勝豐教授、譚新良教授、何騫博士參與編撰和校閱，並提出了許多寶貴意見；楊軼芳老師、汪彥老師給予了英文檢索與翻譯支持。在此也感謝家人特別是女兒的默默付出與支持！
限於水平，書中難免存在疏漏、欠妥之處，歡迎讀者批評指正。

徐述
2018年3月數據庫管理繫統概論前言

在線試讀

第5章查詢優化由第4章的描述可知，對於一個給定查詢，尤其是復雜的查詢，數據庫管理繫統有許多種可能的執行策略，好的查詢策略和差的查詢策略在執行代價上（執行時間）通常會有相當大的區別，它們之間可能相差幾個數量級。因此，數據庫管理繫統為查詢處理選擇一個好的查詢策略而付出額外的時間開銷是完全值得的。數據庫管理繫統能夠構造一個讓查詢執行代價小化的等價查詢執行計劃，即查詢優化。
5.1概述
為了達到用戶可以接受的性能，數據庫管理繫統必須進行查詢優化；而恰好關繫表達式的語義級別很高，關繫數據庫管理繫統可以分析關繫式的語義，對其進行優化。查詢優化使得關繫繫統在性能上接近甚至超過了非關繫繫統。查詢優化是關繫數據庫管理繫統的關鍵技術。關繫數據庫繫統及其SQL語言之所以廣泛流行，很大程度得益於查詢優化技術的發展成熟。
關繫繫統中，用戶使用非過程化的語言表達查詢要求時，隻需要描述做什麼，不必指出怎麼做，這使得用戶選擇數據存取路徑的負擔大大減輕。對比非關繫繫統，用戶需要了解數據的存取路徑，查詢的效率由用戶的查詢策略決定；如果用戶做了不當選擇，繫統不能對此加以改進。這實際上要求非關繫繫統的用戶具有較高的數據庫技術和程序設計水平。
讓DBMS做查詢優化，不僅可以讓用戶關注查詢問題本身，無須考慮如何表達查詢以獲得較高的效率，而且繫統優化比用戶程序優化做得更好。數據庫管理繫統的查詢優化器可以從數據字典獲取許多統計信息（例如組數，關繫的每個屬性值的分布情況，哪些屬性上建立了索引等），優化器可以根據這些信息做出估算，選擇高效的執行計劃，而用戶程序難以做到；另外，如果物理統計信息改變了，數據庫管理繫統會自動更新數據字典，自動調整查詢執行計劃。繫統優化器可以利用很多復雜的優化技術，同時比較數百種不同的執行計劃，而用戶程序難以企及。
實際數據庫管理繫統的查詢優化步驟如下。
（1）將查詢轉換成某種內部表示，通常是語法樹。
（2）根據一定的等價變換規則把語法樹轉換成標準（優化）形式。
（3）選擇底層的操作算法：對於語法樹中的每一個操作，計算各種執行算法的執行代價，選擇代價小的執行算法。
數據庫管理繫統概論第5章查詢優化（4）生成查詢計劃（查詢執行方案），查詢計劃是由一繫列內部操作組成的。
查詢優化主要分為代數優化（即上述優化步驟的步驟（2））與物理優化（即上述優化步驟的步驟（3））。第5章查詢優化由第4章的描述可知，對於一個給定查詢，尤其是復雜的查詢，數據庫管理繫統有許多種可能的執行策略，好的查詢策略和差的查詢策略在執行代價上（執行時間）通常會有相當大的區別，它們之間可能相差幾個數量級。因此，數據庫管理繫統為查詢處理選擇一個好的查詢策略而付出額外的時間開銷是完全值得的。數據庫管理繫統能夠構造一個讓查詢執行代價小化的等價查詢執行計劃，即查詢優化。
5.1概述
為了達到用戶可以接受的性能，數據庫管理繫統必須進行查詢優化；而恰好關繫表達式的語義級別很高，關繫數據庫管理繫統可以分析關繫式的語義，對其進行優化。查詢優化使得關繫繫統在性能上接近甚至超過了非關繫繫統。查詢優化是關繫數據庫管理繫統的關鍵技術。關繫數據庫繫統及其SQL語言之所以廣泛流行，很大程度得益於查詢優化技術的發展成熟。
關繫繫統中，用戶使用非過程化的語言表達查詢要求時，隻需要描述做什麼，不必指出怎麼做，這使得用戶選擇數據存取路徑的負擔大大減輕。對比非關繫繫統，用戶需要了解數據的存取路徑，查詢的效率由用戶的查詢策略決定；如果用戶做了不當選擇，繫統不能對此加以改進。這實際上要求非關繫繫統的用戶具有較高的數據庫技術和程序設計水平。
讓DBMS做查詢優化，不僅可以讓用戶關注查詢問題本身，無須考慮如何表達查詢以獲得較高的效率，而且繫統優化比用戶程序優化做得更好。數據庫管理繫統的查詢優化器可以從數據字典獲取許多統計信息（例如組數，關繫的每個屬性值的分布情況，哪些屬性上建立了索引等），優化器可以根據這些信息做出估算，選擇高效的執行計劃，而用戶程序難以做到；另外，如果物理統計信息改變了，數據庫管理繫統會自動更新數據字典，自動調整查詢執行計劃。繫統優化器可以利用很多復雜的優化技術，同時比較數百種不同的執行計劃，而用戶程序難以企及。
實際數據庫管理繫統的查詢優化步驟如下。
（1）將查詢轉換成某種內部表示，通常是語法樹。
（2）根據一定的等價變換規則把語法樹轉換成標準（優化）形式。
（3）選擇底層的操作算法：對於語法樹中的每一個操作，計算各種執行算法的執行代價，選擇代價小的執行算法。
數據庫管理繫統概論第5章查詢優化（4）生成查詢計劃（查詢執行方案），查詢計劃是由一繫列內部操作組成的。
查詢優化主要分為代數優化（即上述優化步驟的步驟（2））與物理優化（即上述優化步驟的步驟（3））。
查詢優化的總目標是選擇有效的策略，求得給定關繫表達式的值，使得查詢代價較小。而查詢優化的搜索空間實際是非常大的，因此實際繫統選擇的策略不一定是的，而是較優的。
5.2代數優化
4.1節講解了SQL語句經過語法分析與翻譯後變換為關繫代數表達式的內部表示——語法查詢樹，本節介紹基於關繫代數等價變化規則的優化方法——代數優化。
代數優化策略通過對關繫代數表達式的等價變換來提高查詢效率，隻改變查詢語句中操作的次序與組合，不涉及底層的存取路徑。
5.2.1關繫代數表達式等價變換規則
關繫代數表達式的等價變換是指用相同的關繫代替兩個代數表達式中相應的關繫，二者所得到的結果是相同的。如果兩個關繫代數表達式在每一個數據庫實例中都會產生組集合，那麼這兩個表達式有可能以不同的順組的順序是無關緊要的，因組集合內容一致，就認為二者等價。
等價規則指出兩種不同形式的表達式是等價的。種可以代替第二種，反之亦然。優化器利用等價規則將表達式轉換成邏輯上等價的其他表達式。兩個關繫表達式E1和E2是等價的，記為E1≡E2。
下面列出關繫代數表達式的通用等價規則。
1. 連接、笛卡爾積交換律
設E1和E2是關繫代數表達式，F是連接運算的條件，則有：
E1×E2≡ E2×E1
E1E2≡E2E1
E1FE2≡E2FE1
2. 連接、笛卡爾積的結合律
設E1，E2，E3是關繫代數表達式，F1和F2是連接運算的條件，則有：
（E1×E2）×E3 ≡E1×（E2×E3）
（E1E2）E3≡E1（E2E3）
（E1FE2）FE3≡E1F（E2FE3）
3. 投影的串接定律
∏A1,A2,…,An（∏B1,B2,…,Bm（E））≡∏A1,A2,…,An（E）
這裡，E是關繫代數表達式，Ai（i=1，2，…，n）, Bj（j=1，2，…，m）是屬性名，並且{A1, A2, …, An}構成{B1，B2，…，Bm}的子集。
4. 選擇的串接定律
F1（F2（E））≡F1∧ F2（E）
這裡，E是關繫代數表達式，F1和F2是選擇條件。選擇的串接定律說明選擇條件可以合並，這樣一次就可檢查全部條件。
5. 選擇與投影操作的交換律
如果選擇條件F隻涉及屬性A1，A2，…，An，交換律表達如下：
F（∏A1,A2,…,An（E））≡∏A1,A2,…,An（F（E））
若F中有不屬於A1,A2,…,An的屬性B1,B2,…,Bm，則有更一般的交換律如下：
∏A1,A2,…,An（F（E））≡∏A1,A2,…,An（F（∏A1,A2,…,An,B1,B2,…,Bm（E）））
6. 選擇與笛卡爾積的交換律
如果F中涉及的屬性都是E1中的屬性，則有：
F（E1×E2）≡F（E1）×E2
如果F=F1∧F2，並且F1隻涉及E1中的屬性，F2隻涉及E2中的屬性，則由上述等價變換規則1、4、6可推出：
F（E1×E2）≡F1（E1）×F2（E2）
如果F=F1∧F2，F1隻涉及E1中的屬性，F2涉及E1和E2兩者的屬性，選擇與笛卡爾積交換律表達為：
F（E1×E2）≡F2（F1（E1）×E2）
它使部分選擇在笛卡爾積前先做。
7. 選擇與並的交換律
假設： E=E1∪E2、E1，E2有相同的屬性名，則有：
F（E1∪E2）≡F（E1）∪F（E2）
8. 選擇與差運算的交換律
假設E1與E2有相同的屬性名，則有：
F（E1-E2）≡F（E1）-F（E2）
9. 選擇對自然連接的分配律
F（E1E2）≡F（E1）F（E2）
這裡，F隻涉及E1與E2的公共屬性。
10. 投影與笛卡爾積的交換律
設E1和E2是兩個關繫表達式，A1，A2，…，An是E1的屬性，B1，B2，…，Bm是E2的屬性，則：
∏A1,A2, …,An,B1,B2, …,Bm（E1×E2）≡∏A1,A2, …,An（E1）×∏B1,B2, …,Bm（E2）
11. 投影與並的交換律
設E1和E2 有相同的屬性名，則：
∏A1,A2, …,An（E1∪E2）≡∏A1,A2, …,An（E1）∪∏A1,A2, …,An（E2）
5.2.2基於的啟發式規則的代數優化
對於關繫代數表達式的圖形化表示——語法查詢樹，典型的代數優化啟發式規則如下。
（1）選擇運算應盡可能先做。這是優化規則中重要、基本的一條。因為先做選擇運算可以使中間關繫大幅變小，執行代價可以達到數量級地減小。
（2）投影運算和選擇運算同時做。如果有若干個投影運算和選擇運算對同一個關繫操作，則可以在掃描此關繫的同時完成所有這些運算，以避免重復掃描關繫。
（3）將投影運算與其前或其後的雙目運算結合。沒有必要為了去掉某些字段而掃描一遍關繫。
（4）把某些選擇同在其前面的笛卡爾積結合起來成為一個連接運算，連接運算特別是等值連接，要比同樣關繫上的笛卡爾積的執行代價小很多。
（5）找出公共子表達式。如果重復出現的公共子表達式結果不大，並且從外存讀入這個關繫比計算該子表達式的執行代價小，則先計算出公共子表達式，並將結果寫入臨時文件。當利用視圖執行查詢時，定義視圖的語句就是公共子表達式的情況。
根據啟發式規則，應用5.2節的表達式等價變換公式中優化關繫表達式的代數優化算法描述如下。
算法：關繫表達式的優化。
輸入：一個關繫表達式的語法樹。
輸出：優化的查詢樹。
算法步驟如下。
步，分解選擇運算，利用等價變換規則4把形如F1 ∧F2 ∧ … ∧ Fn（E）變換為F1（F2（… （Fn（E））…））形式。
第二步，交換選擇運算，將其盡可能移到葉端，利用規則4～9盡可能把每一個選擇移到樹的葉端。
第三步，交換投影運算，將其盡可能移到葉端，利用規則3、5、10、11中的一般形式盡可能把每一個投影移向樹的葉端。
第四步，合並同一關繫上串接的選擇和投影，以便同時執行這些操作或在一次掃描中完成這些操作。利用規則3、4、5把選擇和投影的串接合並成單個選擇、單個投影或一個選擇後跟一個投影的形式。由於投影或者選擇操作是對同一個關繫的操作，這樣處理的效果是使多個選擇或投影能同時執行，或在一次掃描中全部完成。
第五步，將經過上述步驟得到的語法樹的內結點分組：每一雙目運算（×，，∪，-）和它所有的直接祖先劃分為一組（這些直接祖先是，∏運算）。如果其後代直到葉子全是單目運算，則也將它們並入該組，但當雙目運算是笛卡爾積（×），並且其後的選擇運算不能與它結合為等值連接時除外，這種情況的單目運算單獨分為一組。
第六步，生成程序。生成一個程序，第五步劃分的每組結點的計算是程序中的一步。各步的順序是任意的，隻要保證任何一組的計算不會在它的後代組之前計算即可。
5.2.3代數優化實例
例51對於學生選課關繫數據庫：
student（SNO,SNAME,SSEX,SAGE,SDEPT）關繫模式存放學生基本信息，包括學號、姓名、性別、年齡、繫名；
sc（SNO,CNO,GRADE）關繫模式存放選課信息，包括選課學生學號、課程號、成績；
course（CNO,CNAME,CPNO,CCREDIT）關繫模式存放課程信息，包括課程號、課程名、先修課號、學分。
執行查詢語句，求選修了“信息繫統”的女同學的學號與姓名。該查詢語句的關繫代數表達式如下：
∏SNO,SNAME（CNAME='信息繫統'∧SSEX= '女'（studentsccourse）)
上式中，符號用∏、、×操作表示，可得到等價的表達式如下：
∏SNO,SNAME（CNAME= '信息繫統'∧SSEX='女'（∏L（student.SNO=sc.SNO∧sc.CNO=course.CNO
（student×sc×course））））
此處，L是屬性{student.SNO,SNAME,SSEX,SAGE,SDEPT, course.CNO,GRADE,CNAME,CPNO,CCREDIT}的集合（student、sc、course三表自然連接的屬性集合）。
將等價的表達式構成初始語法查詢樹，如圖51所示。
使用優化算法對初始語法樹進行優化。
步，將選擇運算盡量往葉端放。
將圖51的每個選擇操作分裂成兩個選擇運算，得到4個選擇操作：CNAME= '信息繫統'、SSEX='女'、student.SNO=sc.SNO、sc.CNO=course.CNO；使用等價變換規則4～8，將上述4個選擇操作盡可能向樹的葉子靠攏。根據規則4和5可以將選擇CNAME= '信息繫統'和SSEX='女'移到投影和另外兩個選擇操作下面，直接放在笛卡爾積外面得到子表達式：
CNAME='信息繫統'（SSEX= '女'（student×sc）×course）
其中，外層選擇僅涉及關繫course，內層選擇僅涉及關繫student，所以上述子表達式又可以變換成如下形式：
（SSEX= '女'（student）×sc）×CNAME='信息繫統'（course）
選擇sc.CNO=course.CNO不能再往葉子端移動，因為它的屬性涉及sc和course兩個關繫，而選擇student.SNO=sc.SNO還可以與笛卡爾積交換，往葉端移動一步。
後根據規則3，從樹的根往下的兩個投影操作合並成一個投影操作∏student.SNO,SNAME。
經過上述等價變換，使4個簡單選擇操作盡量往葉端放，等價變換後的語法樹如圖52所示。
圖51例51初始語法查詢樹
圖52例51選擇往葉端放等價交換後的語法樹

第二步，將投影運算盡量往葉端放。
對於根的投影操作，根據等價變換規則5的更一般規則，把投影跟其下的選擇進行交換，在選擇下面增加一個投影操作，如圖53所示。
根據等價變換規則10，將∏student.SNO,SNAME,sc.CNO,course.CNO分成∏student.SNO,SNAME,sc.CNO和∏course.CNO，與其下的笛卡爾積交換，使它們分別對student.SNO=sc.SNO（…）和CNAME='信息繫統'（…）做投影操作。轉換後的語法樹如圖54所示。
對於更靠近根的笛卡爾積交換的投影操作∏student.SNO,SNAME, sc.CNO，類似地，又根據等價規則5的更一般規則，將這個投影分別與其下的選擇操作形成級聯運算： ∏student.SNO,SNAME,sc.CNO（student.SNO=sc.SNO（∏student.SNO,SNAME,sc.SNO,sc.CNO（…））。
再根據等價規則10，將∏student .SNO,SNAME,sc.SNO,sc.CNO與靠近葉子結點student與葉子結點sc的笛卡爾積交換，如圖55所示。
第三步，對優化後的語法樹進行分組。圖55用虛線劃分了兩個運算組。
執行時，從葉端依次向上執行，每組運算對關繫掃描一次。圖53例51根投影往葉端放等價交換後的語法樹
圖54例51根投影繼續與笛卡爾積
交換後的語法樹圖55例51投影往葉端放等價變換後
的終語法樹5.3物理優化
對於一個查詢語句，代數優化後得到的關繫代數語法樹可以有多種執行這個語法樹的算法，多種存取路徑，也就是代數優化後的查詢可以有許多存取方案，這些方案的執行效率各不相同，有的執行時間相差很大。因此，要繼續進行物理優化。
物理優化就是選擇高效合理的操作算法或者存取路徑，求得優化的查詢計劃，達到執行代價的優化。
物理優化的常用方法有以下3種。
（1）基於規則的啟發式優化。啟發式規則是指那些在大多數情況下適用，但不是每一種情況下都是好的規則。
（2）基於代價估算的優化。使用查詢優化器估算不同執行策略的代價，選出其中具有小代價的執行計劃。
（3）兩者結合的優化方法。查詢優化器通常會把這兩種技術結合在一起使用。因為可能的執行策略很多，要執行所有的策略進行代價估算往往是不可行的，因為估算需要代價，若對所有策略都進行代價估算並選出的策略，很可能造成查詢優化本身付出的代價大於獲得的益處。因此結合啟發式規則與代價估算，先使用啟發式規則，挑選若干較優的候選方案，減少代價估算的工作量；然後分別計算這些候選方案的執行代價，從中選出方案。
5.3.1基於啟發式規則的物理優化
基於啟發式規則的物理優化通常是指存取路徑和底層操作算法的選擇，下面介紹常用的物理優化啟發式規則。
1. 選擇操作的物理優化啟發式規則
對於小型關繫，即使選擇列上有索引，也使用全表順序掃描。
對於大型關繫，啟發式規則如下。
對於選擇條件是“主碼=值”的查詢，也就是查詢結果是組，可以選擇主碼上的索引。一般的關繫數據庫繫統在主碼上會自動創建一個屬性的聚集索引。
對於選擇條件是“非主屬性=值”的查詢，並且非主屬性列上建有索引，查詢優化器則會利用數據字典的統計信息估算查詢結果組數目。如組行數目小組行數目的10％，就使用索引掃描方法；否則還是使用全表順序掃描。
對於選擇條件是屬性上的非等值查詢或者範圍查詢，並且選擇列上有索引，同樣要估算查詢組數目。如組行數目小組行數目的10％，就使用索引掃描方法；否則還是使用全表順序掃描。
對於使用AND連接的復合選擇條件，如果有涉及這些屬性的組合索引，優先采用組合索引掃描；如果某個屬性上有一般索引，可以利用該索引找到符合涉及該屬性單條件的記錄指針集，再對集合裡涉及的記錄測試，看是否符合其他的條件。
對於使用OR連接的復合選擇條件，一般使用全表順序掃描。
2. 連接操作的物理優化啟發式規則
如果兩個關繫都已經按照連接屬性排序，則選用歸並連接算法。如果一個關繫在連接屬性上有索引，則可以選用索引嵌套循環連接算法。如果上面兩個規則都不適用，其中一個關繫較小，可以選用散列連接算法。否則可以選用嵌套循環算法，並且選擇其中較小的關繫（但不能完全放在內存裡），即占用的磁盤塊數較少的表作為外部關繫（外循環的表）。如果兩個關繫中某一個關繫小到能完全放在內存裡，那麼將這個小的關繫作為內層關繫來處理可以減少很多I/O操作。這時內層關繫常駐內存反復被掃描，外層關繫逐塊讀入即可。
實際的關繫型數據庫管理繫統中代數優化啟發式規則很多，本節隻展示其中主要的規則。啟發式規則是定性選擇，實現簡單並且優化選擇本身代價小，特別適合解釋執行的繫統。因為解釋執行的數據庫繫統的優化開銷包含在查詢總代價中。
5.3.2基於代價估算的物理優化
編譯執行數據庫繫統中，一次編譯優化，多次執行，查詢優化與查詢執行是分開的。因此，可以采用精細復雜一些的基於代價估算的物理優化方法。
基於代價估算的物理優化需要計算各種操作算法的執行代價，很多時候執行代價與數據庫狀態密切相關。為此，數據庫內模式在數據字典中設計存儲了查詢優化器需要的統計信息，其統計內容主要包括以下3個方面。
（1）對於每個基本關繫，統計組個數（組長度、占用的塊數、占用的溢出塊數。
（2）對於每個基本關繫的每個屬性，統計該屬性不同取值的個數（m）、屬性取值的值、小值、該屬性上是否創建了索引、是哪種索引（B 樹索引、散列索引、聚集索引）以及根據這些統計信息計算出謂詞條件的選擇率（f），如果不同值的分布是均勻的，則f=1/m；如果不同值的分布不均勻，則要計算每個值的選擇率，f=具有組數目/N。
（3）對於索引，例如B 樹索引，統計該索引的層數、不同索引值的個數、索引的選擇基數S（組具有某一索引值）、索引的葉結點數。
5.4基於語義的查詢優化
這種技術根據數據庫的語義約束，把查詢轉換成為另一個執行效率更高的查詢。本節不對這種技術做詳細討論，隻通過一個SQL語句來簡要說明其原理，有興趣的讀者可以查閱數據庫繫統手冊。
考慮如下SQL語句：SELECT  FROM student WHERE sage>300;這裡，用戶在寫年齡值sage時，把30誤寫成300。假設數據庫模式上定義了一個約束，限定學生年齡的取值在18～50周歲。查詢優化器在對上述SQL語句進行語法分析與檢查時，由於約束的存在，馬上可以判斷查詢的結果為空，所以不需要執行這個SQL語句。
5.5小結
查詢優化技術是查詢處理的關鍵技術。
對於給定的查詢，通常有許多計算這個查詢的方案。將用戶輸入的查詢語句轉換為等價的、執行效率更高的查詢執行方案，是查詢優化的目標。
查詢優化主要分為代數優化與物理優化。
代數優化策略通過對關繫代數表達式的等價變換來提高查詢效率，改變查詢語句中操作的次序與組合，不涉及底層的存取路徑。
物理優化就是選擇高效合理的操作算法或者存取路徑，求得優化的查詢計劃，達到執行代價的優化。
物理優化的常用方法有：基於規則的啟發式優化、基於代價估算的優化、兩者結合的優化方法。
思考題
1. 試述關繫型數據庫管理繫統查詢優化的一般準則。
2. 試述關繫型數據庫管理繫統查詢優化的一般步驟。
3. 對於例51的學生選課關繫數據庫，查詢選修了2號課程的學生姓名。試畫出用關繫代數表示的語法樹，並用關繫代數表達式優化算法對原始語法樹進行優化處理，畫出優化後的標準語法樹。

書摘插畫

商品搜索

商品分类

【醫學】

【各大出版社】