第九章關系系統(tǒng)及其查詢優(yōu)化

第九章關系系統(tǒng)及其查詢優(yōu)化第1頁，課件共19頁，創(chuàng)作于2023年2月9.1關系系統(tǒng)關系系統(tǒng)定義支持關系模型的關系數(shù)據庫管理系統(tǒng)簡稱關系系統(tǒng)。1．下述關系的DBMS不能稱為關系系統(tǒng)1）不支持關系數(shù)據結構的系統(tǒng)2）支持關系數(shù)據結構，但無δ、π、運算功能的系統(tǒng)3）支持關系數(shù)據結構，有δ、π、運算，但要求定義物理存取路徑的系統(tǒng)可稱為關系系統(tǒng)的DBMS，當且僅當1）支持關系數(shù)據結構（關系數(shù)據庫）2）支持δ、π、運算，且不要求用戶定義任何物理存取路徑第2頁，課件共19頁，創(chuàng)作于2023年2月9.1關系系統(tǒng)關系系統(tǒng)分類4．全關系系統(tǒng)：支持關系模型的所有特征。在關系完備系統(tǒng)的基礎上，進一步支持實體完整性和參照完整性等。

DBⅡ,ORACLE,SYBASE,…已接近這個目標。目前尚無全關系系統(tǒng)。1．表式系統(tǒng)： 僅支持關系數(shù)據結構，不支持關系操作。2．（最?。╆P系系統(tǒng)： 支持關系數(shù)據結構，支持δ、π、∞運算，且不定義物理路徑。3．關系完備系統(tǒng)：支持關系數(shù)據結構和所有關系代數(shù)操作（或功能上與關系代數(shù)等價）。 DBⅡ,ORACLE,SYBASE,…屬于這一類第3頁，課件共19頁，創(chuàng)作于2023年2月9.1關系系統(tǒng)關系系統(tǒng)分類數(shù)據結構數(shù)據操作完整性約束表式系統(tǒng)表××(最小)關系系統(tǒng)表選擇、投影、連接×關系完備的系統(tǒng)表√×全關系系統(tǒng)√√√第4頁，課件共19頁，創(chuàng)作于2023年2月9.1關系系統(tǒng)全關系系統(tǒng)12條準則0.一個關系型的DBMS必須能完全通過它的關系能力來管理數(shù)據庫準則1：信息準則。關系型DBMS的所有信息都應在邏輯一級上用一種方法即表中的值顯式地表示準則2：保證訪問準則。依表名、主碼、列名的組合，保證能以邏輯方式訪問關系數(shù)據庫中的每個數(shù)據項。（獨立于物理結構）準則3：空值的系統(tǒng)化處理。支持NULL的概念準則4：基于關系模型的動態(tài)的聯(lián)機數(shù)據字典。（以關系的形式存儲元數(shù)據）準則5：統(tǒng)一的數(shù)據子語言準則。一體化的統(tǒng)一的數(shù)據子語言第5頁，課件共19頁，創(chuàng)作于2023年2月9.1關系系統(tǒng)全關系系統(tǒng)12條準則準則6：視圖準則。所有理論上可更新的視圖也應該允許由系統(tǒng)更新。準則7：高級的插入、修改、刪除操作。以關系為對象進行操作準則8：數(shù)據物理獨立性準則9：數(shù)據邏輯獨立性準則10：數(shù)據完整性的獨立性。用DDL定義并存儲在數(shù)據字典中，獨立于應用程序準則11：分布獨立性準則12：無破壞準則第6頁，課件共19頁，創(chuàng)作于2023年2月9.2關系系統(tǒng)的查詢優(yōu)化查詢優(yōu)化概述

●

查詢處理的過程查詢語句查詢輸出關系代數(shù)表達式執(zhí)行計劃語法分析與翻譯執(zhí)行引擎優(yōu)化器數(shù)據有關數(shù)據的統(tǒng)計信息第7頁，課件共19頁，創(chuàng)作于2023年2月9.2關系系統(tǒng)的查詢優(yōu)化查詢優(yōu)化概述

●

實際系統(tǒng)的查詢優(yōu)化步驟1.將查詢轉換成某種內部表示，通常是語法樹2.根據一定的等價變換規(guī)則把語法樹轉換成標準（優(yōu)化）形式3.選擇低層的操作算法對于語法樹中的每一個操作根據存取路徑、數(shù)據的尺寸、數(shù)據的存儲分布、存儲數(shù)據的聚簇等信息來計算各種執(zhí)行算法的執(zhí)行代價選擇代價小的執(zhí)行算法4.生成查詢計劃(查詢執(zhí)行方案)第8頁，課件共19頁，創(chuàng)作于2023年2月9.2關系系統(tǒng)的查詢優(yōu)化查詢優(yōu)化概述

●

常用查詢優(yōu)化技術用啟發(fā)式規(guī)則來縮減查詢計劃的搜索空間利用統(tǒng)計信息估算執(zhí)行代價基于代價

●代價模型集中式數(shù)據庫單用戶系統(tǒng)：總代價=I/O代價+CPU代價多用戶系統(tǒng)：總代價=I/O代價+CPU代價+內存代價分布式數(shù)據庫 總代價=I/O代價+CPU代價[+內存代價]+通信代價第9頁，課件共19頁，創(chuàng)作于2023年2月9.2關系系統(tǒng)的查詢優(yōu)化查詢優(yōu)化概述

●

一個實例:求選C2課程的學生名SELECTSNAMEFROM Student，SCWHEREStudent.Sno=SC.Sno

ANDCno=‘C2’；外存： Student:1000條,SC:10000條,選修2號課程:50條一個內存塊裝元組:10個Student,或100個SC,內存中一次可以存放:5塊Student元組,1塊SC元組和若干塊連接結果元組讀寫速度：20塊/秒連接方法：基于數(shù)據塊的嵌套循環(huán)法假設第10頁，課件共19頁，創(chuàng)作于2023年2月9.2關系系統(tǒng)的查詢優(yōu)化查詢優(yōu)化概述

●

一個實例1.Ｑ1＝ПSname(бStudent.Sno=SC.Sno∧SC.Cno=‘c2‘(Student×SC))

①Student×SC讀取總塊數(shù)=讀Student表塊數(shù)+讀SC表遍數(shù)*每遍塊數(shù) =1000/10+(1000/(10×5))×(10000/100)=2100讀數(shù)據時間=2100/20=105秒 中間結果大小=1000*10000=107(1千萬條元組)寫中間結果時間=10000000/10/20=50000秒

②б 讀數(shù)據時間=50000秒

③П總時間=105＋50000＋50000秒=100105秒=27.8小時第11頁，課件共19頁，創(chuàng)作于2023年2月9.2關系系統(tǒng)的查詢優(yōu)化查詢優(yōu)化概述2.Ｑ2＝ПＳname(бSC.Cno='2'(StudentSC))① 讀取總塊數(shù)=2100塊 讀數(shù)據時間=2100/20=105秒 中間結果大小=10000（減少1000倍） 寫中間結果時間=10000/10/20=50秒

②б

讀數(shù)據時間=50秒

③П

總時間＝105＋50＋50秒＝205秒=3.4分

●

一個實例第12頁，課件共19頁，創(chuàng)作于2023年2月9.2關系系統(tǒng)的查詢優(yōu)化查詢優(yōu)化概述3.Ｑ2＝ПSname(StudentбSC.Cno='2'(SC))

①б 讀SC表總塊數(shù)=10000/100=100塊 讀數(shù)據時間=100/20=5秒

中間結果大小=50條不必寫入外存

② 讀Student表總塊數(shù)=1000/10=100塊 讀數(shù)據時間=100/20=5秒

③П

總時間＝5＋5秒＝10秒

●

一個實例第13頁，課件共19頁，創(chuàng)作于2023年2月9.2關系系統(tǒng)的查詢優(yōu)化查詢優(yōu)化的一般準則選擇運算應盡可能先做

在執(zhí)行連接操作前對關系適當進行預處理投影運算和選擇運算同時做將投影運算與其前后的雙目運算結合選擇運算和笛卡爾積運算結合提取公共子表達式第14頁，課件共19頁，創(chuàng)作于2023年2月9.2關系系統(tǒng)的查詢優(yōu)化關系代數(shù)等價變換規(guī)則l.連接、笛卡爾積交換律2.連接、笛卡爾積的結合律3.投影的串接定律4.選擇的串接定律5.選擇與投影的交換律6.選擇與笛卡爾積的交換律7.選擇與并的交換8.選擇與差運算的交換9.投影與笛卡爾積的交換l0.投影與并的交換第15頁，課件共19頁，創(chuàng)作于2023年2月9.2關系系統(tǒng)的查詢優(yōu)化關系代數(shù)表達式的優(yōu)化算法分解選擇運算通過交換選擇運算，將其盡可能移到葉端通過交換投影運算，將其盡可能移到葉端合并串接的選擇和投影，以便能同時執(zhí)行或在一次掃描中完成對內結點分組生成程序第16頁，課件共19頁，創(chuàng)作于2023年2月9.2關系系統(tǒng)的查詢優(yōu)化優(yōu)化的一般步驟1．把查詢轉換成某種內部表示2．代數(shù)優(yōu)化：把語法樹轉換成標準（優(yōu)化）形式3．物理優(yōu)化：選擇低層的存取路徑4．生成查詢計劃，選擇代價最小的第17頁，課件共19頁，創(chuàng)作于2023年2月9.2關系系統(tǒng)的查詢優(yōu)化優(yōu)化的一般步驟

student.Sno=Sc.Sno

Sc.Sno=‘2’XStudentSC

Snamex

student.Sno=Sc.Sno

Sc.Sno=‘2’

SnameSCStudent

studentSCJoin(student.Sno=SC.Sno)Se