山東理工大學(xué)計算機學(xué)院數(shù)據(jù)庫系統(tǒng)概論第二章關(guān)系數(shù)據(jù)庫課前思考

關(guān)系數(shù)據(jù)模型的數(shù)據(jù)組織結(jié)構(gòu)關(guān)系數(shù)據(jù)模型的基本術(shù)語關(guān)系數(shù)據(jù)模型的特點學(xué)習(xí)目標(biāo)掌握關(guān)系數(shù)據(jù)模型、關(guān)系模式、關(guān)系和關(guān)系數(shù)據(jù)庫基本概念和它們之間的差別關(guān)系模型的完整性掌握基本的關(guān)系代數(shù)運算（并、交、差、投影、選擇、連接等）學(xué)習(xí)難點重點關(guān)系模型、關(guān)系與關(guān)系數(shù)據(jù)庫之間的關(guān)系關(guān)系的數(shù)學(xué)定義及術(shù)語關(guān)系模型的完整性關(guān)系代數(shù)的運算規(guī)則第二章關(guān)系數(shù)據(jù)庫2.1關(guān)系數(shù)據(jù)結(jié)構(gòu)及形式化定義2.2關(guān)系操作2.3關(guān)系的完整性2.4關(guān)系代數(shù)2.5關(guān)系演算2.6小結(jié)關(guān)系數(shù)據(jù)庫簡介系統(tǒng)而嚴(yán)格地提出關(guān)系模型的是美國IBM公司的E.F.Codd1970年提出關(guān)系數(shù)據(jù)模型E.F.Codd,“ARelationalModelofDataforSharedDataBanks”,《CommunicationoftheACM》,1970之后，提出了關(guān)系代數(shù)和關(guān)系演算的概念1972年提出了關(guān)系的第一、第二、第三范式1974年提出了關(guān)系的BC范式關(guān)系數(shù)據(jù)庫簡介關(guān)系數(shù)據(jù)庫應(yīng)用數(shù)學(xué)方法來處理數(shù)據(jù)庫中的數(shù)據(jù)關(guān)系數(shù)據(jù)庫是支持關(guān)系模型的數(shù)據(jù)庫系統(tǒng)關(guān)系模型由數(shù)據(jù)結(jié)構(gòu)、關(guān)系操作集合和完整性約束三部分組成80年代后，關(guān)系數(shù)據(jù)庫系統(tǒng)成為最重要、最流行的數(shù)據(jù)庫系統(tǒng)關(guān)系數(shù)據(jù)庫簡介典型實驗系統(tǒng)SystemRUniversityINGRES典型商用系統(tǒng)ORACLESYBASEINFORMIXDB2SQL/DSINGRES第二章關(guān)系數(shù)據(jù)庫2.1關(guān)系數(shù)據(jù)結(jié)構(gòu)及形式化定義2.2關(guān)系操作2.3關(guān)系的完整性2.4關(guān)系代數(shù)2.5關(guān)系演算2.6小結(jié)2.1關(guān)系數(shù)據(jù)結(jié)構(gòu)及形式化定義2.1.1關(guān)系2.1.2關(guān)系模式2.1.3關(guān)系數(shù)據(jù)庫2.1.1

關(guān)系單一的數(shù)據(jù)結(jié)構(gòu)----關(guān)系現(xiàn)實世界的實體以及實體間的各種聯(lián)系均用關(guān)系來表示邏輯結(jié)構(gòu)----二維表從用戶角度，關(guān)系模型中數(shù)據(jù)的邏輯結(jié)構(gòu)是一張二維表建立在集合代數(shù)的基礎(chǔ)上關(guān)系(續(xù))⒈域（Domain）

2.笛卡爾積（CartesianProduct）

3.關(guān)系（Relation）⒈域（Domain）域是一組具有相同數(shù)據(jù)類型的值的集合。例:整數(shù)實數(shù)介于某個取值范圍的整數(shù)長度指定長度的字符串集合{‘男’，‘女’}……………..2.笛卡爾積（CartesianProduct）笛卡爾積給定一組域D1，D2，…，Dn，這些域中可以有相同的。

D1，D2，…，Dn的笛卡爾積為：

D1×D2×…×Dn＝｛（d1，d2，…，dn）｜di

Di，i＝1，2，…，n｝所有域的所有取值的一個組合不能重復(fù)笛卡爾積（續(xù))

元組（Tuple）笛卡爾積中每一個元素（d1，d2，…，dn）叫作一個n元組（n-tuple）或簡稱元組(Tuple)(張清玫，計算機專業(yè)，李勇)、(張清玫，計算機專業(yè)，劉晨)等都是元組

分量（Component）笛卡爾積元素（d1，d2，…，dn）中的每一個值di叫作一個分量張清玫、計算機專業(yè)、李勇、劉晨等都是分量

笛卡爾積（續(xù))基數(shù)（Cardinalnumber）若Di（i＝1，2，…，n）為有限集，其基數(shù)為mi（i＝1，2，…，n），則D1×D2×…×Dn的基數(shù)M為：笛卡爾積的表示方法笛卡爾積可表示為一個二維表表中的每行對應(yīng)一個元組，表中的每列對應(yīng)一個域

3.關(guān)系（Relation）1)關(guān)系D1×D2×…×Dn的子集叫作在域D1，D2，…，Dn上的關(guān)系，表示為

R（D1，D2，…，Dn）

R：關(guān)系名n：關(guān)系的目或度（Degree）關(guān)系（續(xù)）2)元組關(guān)系中的每個元素是關(guān)系中的元組，通常用t表示。3)單元關(guān)系與二元關(guān)系當(dāng)n=1時，稱該關(guān)系為單元關(guān)系（Unaryrelation）或一元關(guān)系當(dāng)n=2時，稱該關(guān)系為二元關(guān)系（Binaryrelation）關(guān)系（續(xù)）4)關(guān)系的表示關(guān)系也是一個二維表，表的每行對應(yīng)一個元組，表的每列對應(yīng)一個域關(guān)系（續(xù)）5)屬性關(guān)系中不同列可以對應(yīng)相同的域為了加以區(qū)分，必須對每列起一個名字，稱為屬性（Attribute）n目關(guān)系必有n個屬性關(guān)系（續(xù)）6)碼候選碼（Candidatekey）若關(guān)系中的某一屬性組的值能唯一地標(biāo)識一個元組，則稱該屬性組為候選碼簡單的情況：候選碼只包含一個屬性全碼（All-key）最極端的情況：關(guān)系模式的所有屬性組是這個關(guān)系模式的候選碼，稱為全碼（All-key）關(guān)系（續(xù)）碼(續(xù))主碼若一個關(guān)系有多個候選碼，則選定其中一個為主碼（Primarykey）主屬性候選碼的諸屬性稱為主屬性（Primeattribute）不包含在任何侯選碼中的屬性稱為非主屬性（Non-Primeattribute）或非碼屬性（Non-keyattribute）關(guān)系（續(xù)）D1，D2，…，Dn的笛卡爾積的某個子集才有實際含義例：表2.1的笛卡爾積沒有實際意義取出有實際意義的元組來構(gòu)造關(guān)系關(guān)系：SAP(SUPERVISOR，SPECIALITY，POSTGRADUATE)假設(shè)：導(dǎo)師與專業(yè)：1:1，導(dǎo)師與研究生：1:n主碼：POSTGRADUATE（假設(shè)研究生不會重名）

SAP關(guān)系可以包含三個元組｛(張清玫，計算機專業(yè)，李勇)，

(張清玫，計算機專業(yè)，劉晨)，(劉逸，信息專業(yè)，王敏)}關(guān)系（續(xù)）7)三類關(guān)系基本關(guān)系（基本表或基表）實際存在的表，是實際存儲數(shù)據(jù)的邏輯表示查詢表查詢結(jié)果對應(yīng)的表視圖表由基本表或其他視圖表導(dǎo)出的表，是虛表，不對應(yīng)實際存儲的數(shù)據(jù)關(guān)系（續(xù)）8)基本關(guān)系的性質(zhì)①列是同質(zhì)的（Homogeneous）②不同的列可出自同一個域其中的每一列稱為一個屬性不同的屬性要給予不同的屬性名③列的順序無所謂，列的次序可以任意交換④任意兩個元組的候選碼不能相同⑤行的順序無所謂，行的次序可以任意交換基本關(guān)系的性質(zhì)(續(xù))⑥分量必須取原子值這是規(guī)范條件中最基本的一條表2.3非規(guī)范化關(guān)系2.1關(guān)系數(shù)據(jù)結(jié)構(gòu)2.1.1關(guān)系2.1.2關(guān)系模式2.1.3關(guān)系數(shù)據(jù)庫2.1.2關(guān)系模式1．什么是關(guān)系模式2．定義關(guān)系模式3.關(guān)系模式與關(guān)系1．什么是關(guān)系模式關(guān)系模式（RelationSchema）是型關(guān)系是值關(guān)系模式是對關(guān)系的描述元組集合的結(jié)構(gòu)屬性構(gòu)成屬性來自的域?qū)傩耘c域之間的映象關(guān)系元組語義以及完整性約束條件屬性間的數(shù)據(jù)依賴關(guān)系集合2．定義關(guān)系模式關(guān)系的描述稱為關(guān)系模式（RelationSchema），它可以形式化地表示為：

R（U，D，DOM，F(xiàn)）

R關(guān)系名

U

組成該關(guān)系的屬性名集合

D

屬性組U中屬性所來自的域

DOM屬性向域的映象集合

F

屬性間的數(shù)據(jù)依賴關(guān)系集合定義關(guān)系模式(續(xù))例:導(dǎo)師和研究生出自同一個域——人，取不同的屬性名，并在模式中定義屬性向域的映象，即說明它們分別出自哪個域：

DOM（SUPERVISOR-PERSON）=DOM（POSTGRADUATE-PERSON）=PERSON定義關(guān)系模式(續(xù))關(guān)系模式通常可以簡記為

R(U)或R(A1，A2，…，An)R:關(guān)系名A1，A2，…，An:屬性名注：域名及屬性向域的映象常常直接說明為屬性的類型、長度3.關(guān)系模式與關(guān)系關(guān)系模式對關(guān)系的描述靜態(tài)的、穩(wěn)定的關(guān)系關(guān)系模式在某一時刻的狀態(tài)或內(nèi)容動態(tài)的、隨時間不斷變化的關(guān)系模式和關(guān)系往往統(tǒng)稱為關(guān)系通過上下文加以區(qū)別2.1關(guān)系數(shù)據(jù)結(jié)構(gòu)2.1.1關(guān)系2.1.2關(guān)系模式2.1.3關(guān)系數(shù)據(jù)庫2.1.3

關(guān)系數(shù)據(jù)庫關(guān)系數(shù)據(jù)庫在一個給定的應(yīng)用領(lǐng)域中，所有實體及實體之間聯(lián)系的關(guān)系的集合構(gòu)成一個關(guān)系數(shù)據(jù)庫關(guān)系數(shù)據(jù)庫的型與值2.關(guān)系數(shù)據(jù)庫的型與值關(guān)系數(shù)據(jù)庫的型:關(guān)系數(shù)據(jù)庫模式對關(guān)系數(shù)據(jù)庫的描述。關(guān)系數(shù)據(jù)庫模式包括若干域的定義在這些域上定義的若干關(guān)系模式關(guān)系數(shù)據(jù)庫的值:關(guān)系模式在某一時刻對應(yīng)的關(guān)系的集合，簡稱為關(guān)系數(shù)據(jù)庫第二章關(guān)系數(shù)據(jù)庫2.1關(guān)系模型概述2.2關(guān)系操作2.3關(guān)系的完整性2.4關(guān)系代數(shù)2.5關(guān)系演算2.6小結(jié)2.2.1基本關(guān)系操作

常用的關(guān)系操作查詢：選擇、投影、連接、除、并、交、差、笛卡爾積數(shù)據(jù)更新：插入、刪除、修改查詢的表達(dá)能力是其中最主要的部分選擇、投影、并、差、笛卡爾積是5種基本操作關(guān)系操作的特點集合操作方式：操作的對象和結(jié)果都是集合，一次一集合的方式（set-at-a-time），非關(guān)系數(shù)據(jù)模型：一次一記錄方式2.2.2關(guān)系數(shù)據(jù)庫語言的分類

關(guān)系代數(shù)語言用對關(guān)系的運算（代數(shù)方式）來表達(dá)查詢要求代表：ISBL（informationsystembaselanguage)關(guān)系演算語言：用謂詞（邏輯方式）來表達(dá)查詢要求元組關(guān)系演算語言謂詞變元的基本對象是元組變量代表：APLHA,QUEL域關(guān)系演算語言謂詞變元的基本對象是域變量代表：QBE(querybyexample)具有關(guān)系代數(shù)和關(guān)系演算雙重特點的語言代表：SQL（StructuredQueryLanguage）第二章關(guān)系數(shù)據(jù)庫2.1關(guān)系數(shù)據(jù)結(jié)構(gòu)及形式化定義2.2關(guān)系操作2.3關(guān)系的完整性2.4關(guān)系代數(shù)2.5關(guān)系演算2.6小結(jié)2.3關(guān)系的完整性2.3.1關(guān)系的三類完整性約束2.3.2實體完整性2.3.3參照完整性2.3.4用戶定義的完整性2.3.1關(guān)系的三類完整性約束實體完整性和參照完整性：關(guān)系模型必須滿足的完整性約束條件稱為關(guān)系的兩個不變性，應(yīng)該由關(guān)系系統(tǒng)自動支持用戶定義的完整性：應(yīng)用領(lǐng)域需要遵循的約束條件，體現(xiàn)了具體領(lǐng)域中的語義約束2.3關(guān)系的完整性2.3.1關(guān)系的三類完整性約束2.3.2實體完整性2.3.3參照完整性2.3.4用戶定義的完整性2.3.2實體完整性規(guī)則2.2實體完整性規(guī)則（EntityIntegrity）若屬性A是基本關(guān)系R的主屬性，則屬性A不能取空值例SAP(SUPERVISOR，SPECIALITY，POSTGRADUATE)POSTGRADUATE屬性為主碼（假設(shè)研究生不會重名），則其不能取空值實體完整性(續(xù))關(guān)系模型必須遵守實體完整性規(guī)則的原因(1)實體完整性規(guī)則是針對基本關(guān)系而言的。一個基本表通常對應(yīng)現(xiàn)實世界的一個實體集或多對多聯(lián)系。(2)現(xiàn)實世界中的實體和實體間的聯(lián)系都是可區(qū)分的，即它們具有某種唯一性標(biāo)識。(3)相應(yīng)地，關(guān)系模型中以主碼作為唯一性標(biāo)識。實體完整性(續(xù))關(guān)系模型必須遵守實體完整性規(guī)則的原因(續(xù))(4)主碼中的屬性即主屬性不能取空值?？罩稻褪恰安恢馈被颉盁o意義”的值。主屬性取空值，就說明存在某個不可標(biāo)識的實體，即存在不可區(qū)分的實體，這與第（2）點相矛盾，因此這個規(guī)則稱為實體完整性。實體完整性(續(xù))注意實體完整性規(guī)則規(guī)定基本關(guān)系的所有主屬性都不能取空值例選修（學(xué)號，課程號，成績）“學(xué)號、課程號”為主碼，則兩個屬性都不能取空值。2.3關(guān)系的完整性2.3.1關(guān)系的三類完整性約束2.3.2實體完整性2.3.3參照完整性2.3.4用戶定義的完整性2.3.3參照完整性1.關(guān)系間的引用2.外碼3.參照完整性規(guī)則1.關(guān)系間的引用在關(guān)系模型中實體及實體間的聯(lián)系都是用關(guān)系來描述的，因此可能存在著關(guān)系與關(guān)系間的引用。例1學(xué)生實體、專業(yè)實體學(xué)生（學(xué)號，姓名，性別，專業(yè)號，年齡）專業(yè)（專業(yè)號，專業(yè)名）主碼主碼專業(yè)（專業(yè)號，專業(yè)名）學(xué)生（學(xué)號，姓名，性別，專業(yè)號，年齡）關(guān)系間的引用(續(xù))例2學(xué)生、課程、學(xué)生與課程之間的多對多聯(lián)系學(xué)生（學(xué)號，姓名，性別，專業(yè)號，年齡）課程（課程號，課程名，學(xué)分）選修（學(xué)號，課程號，成績）

學(xué)生學(xué)生選課課程關(guān)系間的引用(續(xù))例3學(xué)生實體及其內(nèi)部的領(lǐng)導(dǎo)聯(lián)系(一對多)學(xué)生（學(xué)號，姓名，性別，專業(yè)號，年齡，班長）2．外碼（ForeignKey）設(shè)F是基本關(guān)系R的一個或一組屬性，但不是關(guān)系R的碼。如果F與基本關(guān)系S的主碼Ks相對應(yīng)，則稱F是基本關(guān)系R的外碼基本關(guān)系R稱為參照關(guān)系（ReferencingRelation）基本關(guān)系S稱為被參照關(guān)系（ReferencedRelation）或目標(biāo)關(guān)系（TargetRelation）。外碼(續(xù))說明關(guān)系R和S不一定是不同的關(guān)系目標(biāo)關(guān)系S的主碼Ks和參照關(guān)系的外碼F必須定義在同一個（或一組）域上外碼并不一定要與相應(yīng)的主碼同名當(dāng)外碼與相應(yīng)的主碼屬于不同關(guān)系時，往往取相同的名字，以便于識別3.參照完整性規(guī)則若屬性（或?qū)傩越M）F是基本關(guān)系R的外碼它與基本關(guān)系S的主碼Ks相對應(yīng)（基本關(guān)系R和S不一定是不同的關(guān)系），則對于R中每個元組在F上的值必須為：

或者取空值（F的每個屬性值均為空值）

或者等于S中某個元組的主碼值。參照完整性規(guī)則(續(xù))學(xué)生關(guān)系中每個元組的“專業(yè)號”屬性只取下面兩類值：（1）空值，表示尚未給該學(xué)生分配專業(yè)（2）非空值，這時該值必須是專業(yè)關(guān)系中某個元組的“專業(yè)號”值，表示該學(xué)生不可能分配到一個不存在的專業(yè)中參照完整性規(guī)則(續(xù))

選修（學(xué)號，課程號，成績）“學(xué)號”和“課程號”是選修關(guān)系中的主屬性按照實體完整性和參照完整性規(guī)則，它們只能取相應(yīng)被參照關(guān)系中已經(jīng)存在的主碼值參照完整性規(guī)則(續(xù))學(xué)生（學(xué)號，姓名，性別，專業(yè)號，年齡，班長）“班長”屬性值可以取兩類值：（1）空值，表示該學(xué)生所在班級尚未選出班長，或該學(xué)生本人即是班長；（2）非空值，這時該值必須是本關(guān)系中某個元組的學(xué)號值關(guān)系的完整性(續(xù))2.3.1關(guān)系的三類完整性約束2.3.2實體完整性2.3.3參照完整性2.3.4用戶定義的完整性2.3.4用戶定義的完整性用戶定義的完整性是針對某一具體關(guān)系數(shù)據(jù)庫的約束條件，反映某一具體應(yīng)用所涉及的數(shù)據(jù)必須滿足的語義要求。關(guān)系模型應(yīng)提供定義和檢驗這類完整性的機制，以便用統(tǒng)一的系統(tǒng)的方法處理它們，而不要由應(yīng)用程序承擔(dān)這一功能。用戶定義的完整性(續(xù))例:

課程(課程號，課程名，學(xué)分)“課程名”屬性必須取唯一值非主屬性“課程名”也不能取空值“學(xué)分”屬性只能取值{1，2，3，4}小結(jié)關(guān)系數(shù)據(jù)結(jié)構(gòu)

關(guān)系域笛卡爾積關(guān)系關(guān)系，屬性，元組候選碼，主碼，主屬性基本關(guān)系的性質(zhì)關(guān)系模式關(guān)系數(shù)據(jù)庫關(guān)系的數(shù)據(jù)操作集合查詢選擇、投影、連接、除、并、交、差數(shù)據(jù)更新插入、刪除、修改關(guān)系的完整性約束實體完整性參照完整性外碼用戶定義的完整性實體完整性是對應(yīng)元組或行而言的，參照完整性是對不同表之間的屬性或列的參照關(guān)系而言的實現(xiàn)數(shù)據(jù)完整性的方法在關(guān)系模式定義描述中定義數(shù)據(jù)完整性檢查條件使用觸發(fā)器和存儲過程實現(xiàn)數(shù)據(jù)完整性檢查用其它編程工具編寫程序?qū)崿F(xiàn)數(shù)據(jù)完整性檢查第九章

關(guān)系系統(tǒng)及其查詢優(yōu)化9.1關(guān)系數(shù)據(jù)庫系統(tǒng)的查詢處理9.2關(guān)系數(shù)據(jù)庫系統(tǒng)的查詢優(yōu)化9.3代數(shù)優(yōu)化9.4物理優(yōu)化9.5小結(jié)關(guān)系系統(tǒng)及其查詢優(yōu)化（續(xù)）本章目的：RDBMS的查詢處理步驟查詢優(yōu)化的概念基本方法和技術(shù)查詢優(yōu)化分類：代數(shù)優(yōu)化物理優(yōu)化9.1關(guān)系數(shù)據(jù)庫系統(tǒng)的查詢處理9.1.1查詢處理步驟9.1.2實現(xiàn)查詢操作的算法示例9.1.1查詢處理步驟RDBMS查詢處理階段：1.查詢分析2.查詢檢查3.查詢優(yōu)化4.查詢執(zhí)行

查詢處理步驟（續(xù)）查詢處理步驟1.查詢分析對查詢語句進(jìn)行掃描、詞法分析和語法分析

從查詢語句中識別出語言符號

進(jìn)行語法檢查和語法分析

2.查詢檢查根據(jù)數(shù)據(jù)字典對合法的查詢語句進(jìn)行語義檢查

根據(jù)數(shù)據(jù)字典中的用戶權(quán)限和完整性約束定義對用戶的存取權(quán)限進(jìn)行檢查檢查通過后把SQL查詢語句轉(zhuǎn)換成等價的關(guān)系代數(shù)表達(dá)式

RDBMS一般都用查詢樹(語法分析樹)來表示擴展的關(guān)系代數(shù)表達(dá)式把數(shù)據(jù)庫對象的外部名稱轉(zhuǎn)換為內(nèi)部表示

3.查詢優(yōu)化查詢優(yōu)化：選擇一個高效執(zhí)行的查詢處理策略查詢優(yōu)化分類：代數(shù)優(yōu)化：指關(guān)系代數(shù)表達(dá)式的優(yōu)化物理優(yōu)化：指存取路徑和底層操作算法的選擇查詢優(yōu)化方法選擇的依據(jù)：基于規(guī)則(rulebased)基于代價(costbased)基于語義(semanticbased)4.查詢執(zhí)行依據(jù)優(yōu)化器得到的執(zhí)行策略生成查詢計劃代碼生成器(codegenerator)生成執(zhí)行查詢計劃的代碼9.1關(guān)系數(shù)據(jù)庫系統(tǒng)的查詢處理9.1.1查詢處理步驟9.1.2實現(xiàn)查詢操作的算法示例

9.1.2實現(xiàn)查詢操作的算法示例

一、選擇操作的實現(xiàn)二、連接操作的實現(xiàn)一、選擇操作的實現(xiàn)［例1］Select*fromstudentwhere<條件表達(dá)式>； 考慮<條件表達(dá)式>的幾種情況：

C1：無條件；

C2：Sno＝'200215121'；

C3：Sage>20；

C4：Sdept＝'CS'ANDSage>20；選擇操作的實現(xiàn)（續(xù)）選擇操作典型實現(xiàn)方法：1.簡單的全表掃描方法

對查詢的基本表順序掃描，逐一檢查每個元組是否滿足選擇條件，把滿足條件的元組作為結(jié)果輸出適合小表，不適合大表2.索引(或散列)掃描方法適合選擇條件中的屬性上有索引(例如B+樹索引或Hash索引)通過索引先找到滿足條件的元組主碼或元組指針，再通過元組指針直接在查詢的基本表中找到元組選擇操作的實現(xiàn)（續(xù)）［例1-C2］以C2為例，Sno＝‘200215121’，并且Sno上有索引(或Sno是散列碼)使用索引(或散列)得到Sno為‘200215121’元組的指針通過元組指針在student表中檢索到該學(xué)生［例1-C3］以C3為例，Sage>20，并且Sage上有B+樹索引使用B+樹索引找到Sage＝20的索引項，以此為入口點在B+樹的順序集上得到Sage>20的所有元組指針通過這些元組指針到student表中檢索到所有年齡大于20的學(xué)生。選擇操作的實現(xiàn)（續(xù)）［例1-C4］以C4為例，Sdept＝‘CS’ANDSage>20，如果Sdept和Sage上都有索引：算法一：分別用上面兩種方法分別找到Sdept＝‘CS’的一組元組指針和Sage>20的另一組元組指針求這2組指針的交集到student表中檢索得到計算機系年齡大于20的學(xué)生算法二：找到Sdept＝‘CS’的一組元組指針，通過這些元組指針到student表中檢索對得到的元組檢查另一些選擇條件(如Sage>20)是否滿足把滿足條件的元組作為結(jié)果輸出。

二、連接操作的實現(xiàn)連接操作是查詢處理中最耗時的操作之一本節(jié)只討論等值連接(或自然連接)最常用的實現(xiàn)算法［例2］SELECT*FROMStudent，SC WHEREStudent.Sno=SC.Sno；連接操作的實現(xiàn)（續(xù)）1.嵌套循環(huán)方法(nestedloop)2.排序-合并方法(sort-mergejoin或mergejoin)3.索引連接(indexjoin)方法4.HashJoin方法連接操作的實現(xiàn)（續(xù)）嵌套循環(huán)方法(nestedloop)對外層循環(huán)(Student)的每一個元組(s)，檢索內(nèi)層循環(huán)(SC)中的每一個元組(sc)檢查這兩個元組在連接屬性(sno)上是否相等如果滿足連接條件，則串接后作為結(jié)果輸出，直到外層循環(huán)表中的元組處理完為止連接操作的實現(xiàn)（續(xù)）2.排序-合并方法(sort-mergejoin或mergejoin)適合連接的諸表已經(jīng)排好序的情況排序－合并連接方法的步驟：如果連接的表沒有排好序，先對Student表和SC表按連接屬性Sno排序取Student表中第一個Sno，依次掃描SC表中具有相同Sno的元組連接操作的實現(xiàn)（續(xù)）200215121200215122200215123200215124...200215121192200215121285200215121388200215122290200215122380...排序-合并連接方法示意圖連接操作的實現(xiàn)（續(xù)）排序－合并連接方法的步驟（續(xù)）：當(dāng)掃描到Sno不相同的第一個SC元組時，返回Student表掃描它的下一個元組，再掃描SC表中具有相同Sno的元組，把它們連接起來重復(fù)上述步驟直到Student表掃描完連接操作的實現(xiàn)（續(xù)）Student表和SC表都只要掃描一遍如果2個表原來無序，執(zhí)行時間要加上對兩個表的排序時間對于2個大表，先排序后使用sort-mergejoin方法執(zhí)行連接，總的時間一般仍會大大減少連接操作的實現(xiàn)（續(xù)）3.索引連接(indexjoin)方法步驟：①在SC表上建立屬性Sno的索引，如果原來沒有該索引②對Student中每一個元組，由Sno值通過SC的索引查找相應(yīng)的SC元組③把這些SC元組和Student元組連接起來循環(huán)執(zhí)行②③，直到Student表中的元組處理完為止連接操作的實現(xiàn)（續(xù)）4.HashJoin方法把連接屬性作為hash碼，用同一個hash函數(shù)把R和S中的元組散列到同一個hash文件中步驟：劃分階段(partitioningphase)：對包含較少元組的表(比如R)進(jìn)行一遍處理把它的元組按hash函數(shù)分散到hash表的桶中試探階段(probingphase)：也稱為連接階段(joinphase)對另一個表(S)進(jìn)行一遍處理把S的元組散列到適當(dāng)?shù)膆ash桶中把元組與桶中所有來自R并與之相匹配的元組連接起來

連接操作的實現(xiàn)（續(xù)）上面hashjoin算法前提：假設(shè)兩個表中較小的表在第一階段后可以完全放入內(nèi)存的hash桶中以上的算法思想可以推廣到更加一般的多個表的連接算法上第九章

關(guān)系系統(tǒng)及其查詢優(yōu)化9.1關(guān)系數(shù)據(jù)庫系統(tǒng)的查詢處理9.2關(guān)系數(shù)據(jù)庫系統(tǒng)的查詢優(yōu)化9.3代數(shù)優(yōu)化9.4物理優(yōu)化9.5小結(jié)9.2關(guān)系數(shù)據(jù)庫系統(tǒng)的查詢優(yōu)化查詢優(yōu)化在關(guān)系數(shù)據(jù)庫系統(tǒng)中有著非常重要的地位關(guān)系查詢優(yōu)化是影響RDBMS性能的關(guān)鍵因素由于關(guān)系表達(dá)式的語義級別很高，使關(guān)系系統(tǒng)可以從關(guān)系表達(dá)式中分析查詢語義，提供了執(zhí)行查詢優(yōu)化的可能性9.2關(guān)系數(shù)據(jù)庫系統(tǒng)的查詢優(yōu)化9.2.1查詢優(yōu)化概述9.2.2一個實例

9.2.1查詢優(yōu)化概述關(guān)系系統(tǒng)的查詢優(yōu)化查詢優(yōu)化的優(yōu)點查詢優(yōu)化的總體目標(biāo)查詢優(yōu)化概述（續(xù)）查詢優(yōu)化的優(yōu)點不僅在于用戶不必考慮如何最好地表達(dá)查詢以獲得較好的效率，而且在于系統(tǒng)可以比用戶程序的“優(yōu)化”做得更好(1)優(yōu)化器可以從數(shù)據(jù)字典中獲取許多統(tǒng)計信息，而用戶程序則難以獲得這些信息(2)如果數(shù)據(jù)庫的物理統(tǒng)計信息改變了，系統(tǒng)可以自動對查詢重新優(yōu)化以選擇相適應(yīng)的執(zhí)行計劃。在非關(guān)系系統(tǒng)中必須重寫程序，而重寫程序在實際應(yīng)用中往往是不太可能的。查詢優(yōu)化概述（續(xù)）(3)優(yōu)化器可以考慮數(shù)百種不同的執(zhí)行計劃，程序員一般只能考慮有限的幾種可能性。(4)優(yōu)化器中包括了很多復(fù)雜的優(yōu)化技術(shù)，這些優(yōu)化技術(shù)往往只有最好的程序員才能掌握。系統(tǒng)的自動優(yōu)化相當(dāng)于使得所有人都擁有這些優(yōu)化技術(shù)查詢優(yōu)化概述（續(xù)）RDBMS通過某種代價模型計算出各種查詢執(zhí)行策略的執(zhí)行代價，然后選取代價最小的執(zhí)行方案集中式數(shù)據(jù)庫執(zhí)行開銷主要包括：磁盤存取塊數(shù)(I/O代價)處理機時間(CPU代價)查詢的內(nèi)存開銷I/O代價是最主要的 分布式數(shù)據(jù)庫總代價=I/O代價+CPU代價+內(nèi)存代價＋通信代價查詢優(yōu)化概述（續(xù)）查詢優(yōu)化的總目標(biāo)：選擇有效的策略求得給定關(guān)系表達(dá)式的值使得查詢代價最小(實際上是較小)9.2關(guān)系數(shù)據(jù)庫系統(tǒng)的查詢優(yōu)化9.2.1查詢優(yōu)化概述9.2.2一個實例9.2.2一個實例[例3]求選修了2號課程的學(xué)生姓名。用SQL表達(dá)：

SELECTStudent.Sname FROMStudent，SC WHEREStudent.Sno=SC.SnoAND SC.Cno=‘2’；假定學(xué)生-課程數(shù)據(jù)庫中有1000個學(xué)生記錄，10000個選課記錄其中選修2號課程的選課記錄為50個一個實例（續(xù)）系統(tǒng)可以用多種等價的關(guān)系代數(shù)表達(dá)式來完成這一查詢Q1=πSname(σStudent.Sno=SC.Sno∧Sc.Cno='2'(Student×SC))Q2=πSname(σSc.Cno='2'(StudentSC))Q3=πSname(StudentσSc.Cno='2'(SC)) 一個實例（續(xù)）---第一種情況

Q1=πSname(σStudent.Sno=SC.Sno∧Sc.Cno='2'

Student×SC))1.計算廣義笛卡爾積把Student和SC的每個元組連接起來的做法：在內(nèi)存中盡可能多地裝入某個表(如Student表)的若干塊，留出一塊存放另一個表(如SC表)的元組。把SC中的每個元組和Student中每個元組連接，連接后的元組裝滿一塊后就寫到中間文件上從SC中讀入一塊和內(nèi)存中的Student元組連接，直到SC表處理完。再讀入若干塊Student元組，讀入一塊SC元組重復(fù)上述處理過程，直到把Student表處理完一個實例（續(xù)）---第一種情況設(shè)一個塊能裝10個Student元組或100個SC元組，在內(nèi)存中存放5塊Student元組和1塊SC元組，則讀取總塊數(shù)為

＋=100+20×100=2100塊其中，讀Student表100塊。讀SC表20遍，每遍100塊。若每秒讀寫20塊，則總計要花105s連接后的元組數(shù)為103×104=107。設(shè)每塊能裝10個元組，則寫出這些塊要用106/20=5×104s

一個實例（續(xù)）---第一種情況2.作選擇操作依次讀入連接后的元組，按照選擇條件選取滿足要求的記錄假定內(nèi)存處理時間忽略。讀取中間文件花費的時間(同寫中間文件一樣)需5×104s滿足條件的元組假設(shè)僅50個，均可放在內(nèi)存一個實例（續(xù)）3.作投影操作把第2步的結(jié)果在Sname上作投影輸出，得到最終結(jié)果第一種情況下執(zhí)行查詢的總時間≈105+2×5×104≈105s所有內(nèi)存處理時間均忽略不計一個實例（續(xù)）---第二種情況Q2=πSname(σSc.Cno='2'(StudentSC))1.計算自然連接執(zhí)行自然連接，讀取Student和SC表的策略不變，總的讀取塊數(shù)仍為2100塊花費105s自然連接的結(jié)果比第一種情況大大減少，為104個寫出這些元組時間為104/10/20=50s，為第一種情況的千分之一2.讀取中間文件塊，執(zhí)行選擇運算，花費時間也為50s。3.把第2步結(jié)果投影輸出。第二種情況總的執(zhí)行時間≈105+50+50≈205s一個實例（續(xù)）---第三種情況Q3=πSname(StudentσSc.Cno='2'(SC))1.先對SC表作選擇運算，只需讀一遍SC表，存取100塊花費時間為5s，因為滿足條件的元組僅50個，不必使用中間文件。2.讀取Student表，把讀入的Student元組和內(nèi)存中的SC元組作連接。也只需讀一遍Student表共100塊，花費時間為5s。3.把連接結(jié)果投影輸出第三種情況總的執(zhí)行時間≈5+5≈10s一個實例（續(xù)）假如SC表的Cno字段上有索引第一步就不必讀取所有的SC元組而只需讀取Cno=‘2’的那些元組(50個)存取的索引塊和SC中滿足條件的數(shù)據(jù)塊大約總共3～4塊若Student表在Sno上也有索引第二步也不必讀取所有的Student元組因為滿足條件的SC記錄僅50個，涉及最多50個Student記錄讀取Student表的塊數(shù)也可大大減少

總的存取時間將進(jìn)一步減少到數(shù)秒一個實例（續(xù)）把代數(shù)表達(dá)式Q1變換為Q2、Q3，即有選擇和連接操作時，先做選擇操作，這樣參加連接的元組就可以大大減少，這是代數(shù)優(yōu)化在Q3中SC表的選擇操作算法有全表掃描和索引掃描2種方法，經(jīng)過初步估算，索引掃描方法較優(yōu)對于Student和SC表的連接，利用Student表上的索引，采用indexjoin代價也較小，這就是物理優(yōu)化

第九章

關(guān)系系統(tǒng)及其查詢優(yōu)化9.1關(guān)系數(shù)據(jù)庫系統(tǒng)的查詢處理9.2關(guān)系數(shù)據(jù)庫系統(tǒng)的查詢優(yōu)化

9.3代數(shù)優(yōu)化

9.4物理優(yōu)化9.5小結(jié)9.3代數(shù)優(yōu)化基于關(guān)系代數(shù)等價變換規(guī)則的優(yōu)化方法，即代數(shù)優(yōu)化9.3.1關(guān)系代數(shù)表達(dá)式等價變換規(guī)則

9.3.2查詢樹的啟發(fā)式優(yōu)化9.3.1關(guān)系代數(shù)表達(dá)式等價變換規(guī)則代數(shù)優(yōu)化策略：通過對關(guān)系代數(shù)表達(dá)式的等價變換來提高查詢效率關(guān)系代數(shù)表達(dá)式的等價：指用相同的關(guān)系代替兩個表達(dá)式中相應(yīng)的關(guān)系所得到的結(jié)果是相同的兩個關(guān)系表達(dá)式E1和E2是等價的，可記為E1≡E2

關(guān)系代數(shù)表達(dá)式等價變換規(guī)則（續(xù)）常用的等價變換規(guī)則：1.連接、笛卡爾積交換律設(shè)E1和E2是關(guān)系代數(shù)表達(dá)式，F(xiàn)是連接運算的條件，則有

E1×E2≡E2×E1

E1

E2≡E2

E1

E1

E2≡E2

E12.連接、笛卡爾積的結(jié)合律設(shè)E1，E2，E3是關(guān)系代數(shù)表達(dá)式，F(xiàn)1和F2是連接運算的條件，則有

(E1×E2)×E3≡E1×(E2×E3)(E1

E2)E3≡E1(E2

E3)(E1

E2)E3≡E1(E2

E3)關(guān)系代數(shù)表達(dá)式等價變換規(guī)則（續(xù)）3.投影的串接定律

((E))≡(E)

這里，E是關(guān)系代數(shù)表達(dá)式，Ai(i=1，2，…，n)，Bj(j=1，2，…，m)是屬性名且{A1，A2，…，An}構(gòu)成{B1，B2，…，Bm}的子集。4.選擇的串接定律

((E))≡(E)

這里，E是關(guān)系代數(shù)表達(dá)式，F(xiàn)1、F2是選擇條件。選擇的串接律說明選擇條件可以合并。這樣一次就可檢查全部條件。關(guān)系代數(shù)表達(dá)式等價變換規(guī)則（續(xù)）5.選擇與投影操作的交換律

σF((E))≡(σF(E))

選擇條件F只涉及屬性A1，…，An。 若F中有不屬于A1，…，An的屬性B1，…，Bm則有更一般的規(guī)則：

(σF(E))≡(σF((E)))關(guān)系代數(shù)表達(dá)式等價變換規(guī)則（續(xù)）6.選擇與笛卡爾積的交換律 如果F中涉及的屬性都是E1中的屬性，則

(E1×E2)≡(E1)×E2

如果F=F1∧F2，并且F1只涉及E1中的屬性，F(xiàn)2只涉及E2中的屬性，則由上面的等價變換規(guī)則1，4，6可推出：

(E1×E2)≡(E1)×(E2)

若F1只涉及E1中的屬性，F(xiàn)2涉及E1和E2兩者的屬性，則仍有

(E1×E2)≡((E1)×E2)

它使部分選擇在笛卡爾積前先做。關(guān)系代數(shù)表達(dá)式等價變換規(guī)則（續(xù)）7.選擇與并的分配律 設(shè)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的公共屬性關(guān)系代數(shù)表達(dá)式等價變換規(guī)則（續(xù)）10.投影與笛卡爾積的分配律 設(shè)E1和E2是兩個關(guān)系表達(dá)式，A1，…，An是E1的屬性，B1，…，Bm是E2的屬性，則

(E1×E2)≡(E1)×(E2)11.投影與并的分配律 設(shè)E1和E2有相同的屬性名，則

(E1∪E2)≡(E1)∪(E2)9.3代數(shù)優(yōu)化9.3.1關(guān)系代數(shù)表達(dá)式等價變換規(guī)則9.3.2查詢樹的啟發(fā)式優(yōu)化9.3.2查詢樹的啟發(fā)式優(yōu)化典型的啟發(fā)式規(guī)則：1.選擇運算應(yīng)盡可能先做。在優(yōu)化策略中這是最重要、最基本的一條2.把投影運算和選擇運算同時進(jìn)行如有若干投影和選擇運算，并且它們都對同一個關(guān)系操作，則可以在掃描此關(guān)系的同時完成所有的這些運算以避免重復(fù)掃描關(guān)系查詢樹的啟發(fā)式優(yōu)化（續(xù)）3.把投影同其前或其后的雙目運算結(jié)合起來4.把某些選擇同在它前面要執(zhí)行的笛卡爾積結(jié)合起來成為一個連接運算5.找出公共子表達(dá)式如果這種重復(fù)出現(xiàn)的子表達(dá)式的結(jié)果不是很大的關(guān)系并且從外存中讀入這個關(guān)系比計算該子表達(dá)式的時間少得多，則先計算一次公共子表達(dá)式并把結(jié)果寫入中間文件是合算的當(dāng)查詢的是視圖時，定義視圖的表達(dá)式就是公共子表達(dá)式的情況查詢樹的啟發(fā)式優(yōu)化（續(xù)）遵循這些啟發(fā)式規(guī)則，應(yīng)用9.3.1的等價變換公式來優(yōu)化關(guān)系表達(dá)式的算法。 算法：關(guān)系表達(dá)式的優(yōu)化 輸入：一個關(guān)系表達(dá)式的查詢樹 輸出：優(yōu)化的查詢樹 方法：

(1)利用等價變換規(guī)則4把形如σF1∧F2∧…∧Fn(E)變換為σF1(σF2(…(σFn(E))…))。

(2)對每一個選擇，利用等價變換規(guī)則4～9盡可能把它移到樹的葉端。查詢樹的啟發(fā)式優(yōu)化（續(xù)） (3)對每一個投影利用等價變換規(guī)則3，5，10，11中的一般形式盡可能把它移向樹的葉端。注意：等價變換規(guī)則3使一些投影消失規(guī)則5把一個投影分裂為兩個，其中一個有可能被移向樹的葉端

(4)利用等價變換規(guī)則3～5把選擇和投影的串接合并成單個選擇、單個投影或一個選擇后跟一個投影。使多個選擇或投影能同時執(zhí)行，或在一次掃描中全部完成查詢樹的啟發(fā)式優(yōu)化（續(xù)）(5)把上述得到的語法樹的內(nèi)節(jié)點分組。每一雙目運算(×，，∪，-)和它所有的直接祖先為一組(這些直接祖先是(σ，π運算)。如果其后代直到葉子全是單目運算，則也將它們并入該組但當(dāng)雙目運算是笛卡爾積(×)，而且后面不是與它組成等值連接的選擇時，則不能把選擇與這個雙目運算組成同一組，把這些單目運算單獨分為一組查詢樹的啟發(fā)式優(yōu)化（續(xù)）［例4］下面給出［例3］中SQL語句的代數(shù)優(yōu)化示例。

(1)把SQL語句轉(zhuǎn)換成查詢樹，如下圖所示

查詢樹查詢樹的啟發(fā)式優(yōu)化（續(xù)）

為了使用關(guān)系代數(shù)表達(dá)式的優(yōu)化法，假設(shè)內(nèi)部表示是關(guān)系代數(shù)語法樹，則上面的查詢樹如下圖所示。

關(guān)系代數(shù)語法樹

查詢樹的啟發(fā)式優(yōu)化（續(xù)）(2)對查詢樹進(jìn)行優(yōu)化利用規(guī)則4、6把選擇σSC.Cno=‘2’移到葉端，查詢樹便轉(zhuǎn)換成下圖所示的優(yōu)化的查詢樹。這就是9.2.2節(jié)中Q3的查詢樹表示優(yōu)化后的查詢樹

第九章

關(guān)系系統(tǒng)及其查詢優(yōu)化9.1關(guān)系數(shù)據(jù)庫系統(tǒng)的查詢處理9.2關(guān)系數(shù)據(jù)庫系統(tǒng)的查詢優(yōu)化

9.3代數(shù)優(yōu)化

9.4物理優(yōu)化9.5小結(jié)9.4物理優(yōu)化代數(shù)優(yōu)化改變查詢語句中操作的次序和組合，不涉及底層的存取路徑對于一個查詢語句有許多存取方案，它們的執(zhí)行效率不同，僅僅進(jìn)行代數(shù)優(yōu)化是不夠的物理優(yōu)化就是要選擇高效合理的操作算法或存取路徑，求得優(yōu)化的查詢計劃物理優(yōu)化（續(xù)）選擇的方法：基于規(guī)則的啟發(fā)式優(yōu)化基于代價估算的優(yōu)化兩者結(jié)合的優(yōu)化方法9.4物理優(yōu)化9.4.1基于啟發(fā)式規(guī)則的存取路徑選擇優(yōu)化9.4.2基于代價的優(yōu)化9.4.1基于啟發(fā)式規(guī)則的存取路徑選擇優(yōu)化一、選擇操作的啟發(fā)式規(guī)則二、連接操作的啟發(fā)式規(guī)則基于啟發(fā)式規(guī)則的存取路徑選擇優(yōu)化(續(xù))一、選擇操作的啟發(fā)式規(guī)則: 1.對于小關(guān)系，使用全表順序掃描，即使選擇列上有索引 對于大關(guān)系，啟發(fā)式規(guī)則有：

2.對于選擇條件是主碼＝值的查詢查詢結(jié)果最多是一個元組，可以選擇主碼索引一般的RDBMS會自動建立主碼索引。

基于啟發(fā)式規(guī)則的存取路徑選擇優(yōu)化(續(xù))3.對于選擇條件是非主屬性＝值的查詢，并且選擇列上有索引要估算查詢結(jié)果的元組數(shù)目如果比例較小(<10%)可以使用索引掃描方法否則還是使用全表順序掃描基于啟發(fā)式規(guī)則的存取路徑選擇優(yōu)化(續(xù)) 4.對于選擇條件是屬性上的非等值查詢或者范圍查詢，并且選擇列上有索引要估算查詢結(jié)果的元組數(shù)目如果比例較小(<10%)可以使用索引掃描方法否則還是使用全表順序掃描

基于啟發(fā)式規(guī)則的存取路徑選擇優(yōu)化(續(xù)) 5.對于用AND連接的合取選擇條件如果有涉及這些屬性的組合索引優(yōu)先采用組合索引掃描方法如果某些屬性上有一般的索引則可以用［例1-C4］中介紹的索引掃描方法否則使用全表順序掃描。

6.對于用OR連接的析取選擇條件，一般使用全表順序掃描基于啟發(fā)式規(guī)則的存取路徑選擇優(yōu)化(續(xù))二、連接操作的啟發(fā)式規(guī)則：

1.如果2個表都已經(jīng)按照連接屬性排序選用排序-合并方法

2.如果一個表在連接屬性上有索引選用索引連接方法

3.如果上面2個規(guī)則都不適用，其中一個表較小選用Hashjoin方法

基于啟發(fā)式規(guī)則的存取路徑選擇優(yōu)化(續(xù))4.可以選用嵌套循環(huán)方法，并選擇其中較小的表，確切地講是占用的塊數(shù)(b)較少的表，作為外表(外循環(huán)的表)。理由：設(shè)連接表R與S分別占用的塊數(shù)為Br與Bs連接操作使用的內(nèi)存緩沖區(qū)塊數(shù)為K分配K-1塊給外表如果R為外表，則嵌套循環(huán)法存取的塊數(shù)為Br+(Br/K-1)Bs顯然應(yīng)該選塊數(shù)小的表作為外表9.4物理優(yōu)化（續(xù)）9.4.1基于啟發(fā)式規(guī)則的存取路徑選擇優(yōu)化9.4.2基于代價的優(yōu)化9.4.2基于代價的優(yōu)化

啟發(fā)式規(guī)則優(yōu)化是定性的選擇，適合解釋執(zhí)行的系統(tǒng)解釋執(zhí)行的系統(tǒng)，優(yōu)化開銷包含在查詢總開銷之中編譯執(zhí)行的系統(tǒng)中查詢優(yōu)化和查詢執(zhí)行是分開的可以采用精細(xì)復(fù)雜一些的基于代價的優(yōu)化方法基于代價的優(yōu)化（續(xù)）一、統(tǒng)計信息二、代價估算示例基于代價的優(yōu)化（續(xù)）一、統(tǒng)計信息基于代價的優(yōu)化方法要計算各種操作算法的執(zhí)行代價，與數(shù)據(jù)庫的狀態(tài)密切相關(guān)數(shù)據(jù)字典中存儲的優(yōu)化器需要的統(tǒng)計信息：1.對每個基本表該表的元組總數(shù)(N)元組長度(l)占用的塊數(shù)(B)占用的溢出塊數(shù)(BO)基于代價的優(yōu)化（續(xù)） 2.對基表的每個列該列不同值的個數(shù)(m)選擇率(f)如果不同值的分布是均勻的，f＝1/m如果不同值的分布不均勻，則每個值的選擇率＝具有該值的元組數(shù)/N該列最大值該列最小值該列上是否已經(jīng)建立了索引索引類型(B+樹索引、Hash索引、聚集索引)

基于代價的優(yōu)化（續(xù)）3.對索引(如B+樹索引)索引的層數(shù)(L)不同索引值的個數(shù)索引的選擇基數(shù)S(有S個元組具有某個索引值)索引的葉結(jié)點數(shù)(Y)基于代價的優(yōu)化（續(xù)）二、代價估算示例全表掃描算法的代價估算公式如果基本表大小為B塊，全表掃描算法的代價cost＝B如果選擇條件是碼＝值，那么平均搜索代價cost＝B/2基于代價的優(yōu)化（續(xù)）2.索引掃描算法的代價估算公式如果選擇條件是碼＝值如［例1-C2］，則采用該表的主索引若為B+樹，層數(shù)為L，需要存取B+樹中從根結(jié)點到葉結(jié)點L塊，再加上基本表中該元組所在的那一塊，所以cost=L+1如果選擇條件涉及非碼屬性如［例1-C3］，若為B+樹索引，選擇條件是相等比較，S是索引的選擇基數(shù)(有S個元組滿足條件)最壞的情況下，滿足條件的元組可能會保存在不同的塊上，此時，cost=L+S基于代價的優(yōu)化（續(xù)）如果比較條件是＞，＞＝，＜，＜＝操作假設(shè)有一半的元組滿足條件就要存取一半的葉結(jié)點通過索引訪問一半的表存儲塊cost=L+Y/2+B/2如果可以獲得更準(zhǔn)確的選擇基數(shù)，可以進(jìn)一步修正Y/2與B/2基于代價的優(yōu)化（續(xù)）3.嵌套循環(huán)連接算法的代價估算公式9.4.1中已經(jīng)討論過了嵌套循環(huán)連接算法的代價

cost＝Br+Bs/(K-1)Br如果需要把連接結(jié)果寫回磁盤，

cost＝Br+Bs/(K-1)Br+(Frs*Nr*Ns)/Mrs其中Frs為連接選擇性(joinselectivity)，表示連接結(jié)果元組數(shù)的比例Mrs是存放連接結(jié)果的塊因子，表示每塊中可以存放的結(jié)果元組數(shù)目?；诖鷥r的優(yōu)化（續(xù)）4.排序-合并連接算法的代價估算公式如果連接表已經(jīng)按照連接屬性排好序，則

cost＝Br+Bs+(Frs*Nr*Ns)/Mrs。如果必須對文件排序需要在代價函數(shù)中加上排序的代價對于包含B個塊的文件排序的代價大約是(2*B)+(2*B*log2B)第九章

關(guān)系系統(tǒng)及其查詢優(yōu)化9.1關(guān)系數(shù)據(jù)庫系統(tǒng)的查詢處理9.2關(guān)系數(shù)據(jù)庫系統(tǒng)的查詢優(yōu)化

9.3代數(shù)優(yōu)化9.4物理優(yōu)化9.5小結(jié)

9.5小結(jié)查詢處理是RDBMS的核心，查詢優(yōu)化技術(shù)是查詢處理的關(guān)鍵技術(shù)本章講解的優(yōu)化方法啟發(fā)式代數(shù)優(yōu)化基于規(guī)則的存取路徑優(yōu)化基于代價的優(yōu)化本章的目的：希望讀者掌握查詢優(yōu)化方法的概念和技術(shù)小結(jié)（續(xù)）比較復(fù)雜的查詢，尤其是涉及連接和嵌套的查詢不要把優(yōu)化的任務(wù)全部放在RDBMS上應(yīng)該找出RDBMS的優(yōu)化規(guī)律，以寫出適合RDBMS自動優(yōu)化的SQL語句對于RDBMS不能優(yōu)化的查詢需要重寫查詢語句，進(jìn)行手工調(diào)整以優(yōu)化性能SelectN,TfromB,S,LwhereB.BN=L.BN andS.LN=L.LNandD<‘20010101’πN,T(σD<’20010101’(σS.Sno=SC.Sno

C.Cno=SC.Cno(L╳B╳S)))例題2檢索使用上海供應(yīng)商生產(chǎn)的紅色零件的工程號山東理工大學(xué)計算機學(xué)院數(shù)據(jù)庫系統(tǒng)概論第六章關(guān)系數(shù)據(jù)理論學(xué)習(xí)目標(biāo)給定一個關(guān)系模式和已知的語義，能夠找出該關(guān)系模式的函數(shù)依賴關(guān)系、關(guān)系模式的候選碼、主碼、主屬性、非主屬性給定一個關(guān)系模式和已知的語義，能夠判斷該關(guān)系模式屬于第幾范式，能把該關(guān)系模式分解為符合2NF、3NF或BCNF要求的關(guān)系模式集合難重點：關(guān)系數(shù)據(jù)庫規(guī)范化第六章關(guān)系數(shù)據(jù)理論6.1問題的提出6.2規(guī)范化6.3數(shù)據(jù)依賴的公理系統(tǒng)*6.4模式的分解6.5小結(jié)6.1問題的提出關(guān)系數(shù)據(jù)庫邏輯設(shè)計針對具體問題，如何構(gòu)造一個適合于它的數(shù)據(jù)模式數(shù)據(jù)庫邏輯設(shè)計的工具──關(guān)系數(shù)據(jù)庫的規(guī)范化理論問題的提出一、概念回顧二、關(guān)系模式的形式化定義三、什么是數(shù)據(jù)依賴四、關(guān)系模式的簡化定義五、數(shù)據(jù)依賴對關(guān)系模式影響一、概念回顧關(guān)系：描述實體、屬性、實體間的聯(lián)系。從形式上看，它是一張二維表，是所涉及屬性的笛卡爾積的一個子集。關(guān)系模式：用來定義關(guān)系。關(guān)系數(shù)據(jù)庫：基于關(guān)系模型的數(shù)據(jù)庫，利用關(guān)系來描述現(xiàn)實世界。從形式上看，它由一組關(guān)系組成。關(guān)系數(shù)據(jù)庫的模式：定義這組關(guān)系的關(guān)系模式的全體。二、關(guān)系模式的形式化定義關(guān)系模式由五部分組成，即它是一個五元組：

R(U,D,DOM,F)R：關(guān)系名U：組成該關(guān)系的屬性名集合D：屬性組U中屬性所來自的域DOM：屬性向域的映象集合F：屬性間數(shù)據(jù)的依賴關(guān)系集合三、什么是數(shù)據(jù)依賴1.完整性約束的表現(xiàn)形式限定屬性取值范圍：例如學(xué)生成績必須在0-100之間定義屬性值間的相互關(guān)連（主要體現(xiàn)于值的相等與否），這就是數(shù)據(jù)依賴，它是數(shù)據(jù)庫模式設(shè)計的關(guān)鍵什么是數(shù)據(jù)依賴（續(xù)）2.數(shù)據(jù)依賴一個關(guān)系內(nèi)部屬性與屬性之間的約束關(guān)系現(xiàn)實世界屬性間相互聯(lián)系的抽象數(shù)據(jù)內(nèi)在的性質(zhì)語義的體現(xiàn)什么是數(shù)據(jù)依賴（續(xù)）3.數(shù)據(jù)依賴可以作為關(guān)系模式取值的任何一個關(guān)系所必須滿足的一種約束條件，是透過一個關(guān)系中數(shù)值間的相等與否體現(xiàn)出來的相互關(guān)系舉例：在一個學(xué)生關(guān)系中，客觀存在每個學(xué)生必須有一個唯一的學(xué)號，當(dāng)一個學(xué)生的學(xué)號確定以后，該學(xué)生的其他屬性，如姓名、性別、班級等值就唯一的確定了。在關(guān)系模式學(xué)生的任何一個關(guān)系中，都不可能存在兩個元組，他們的學(xué)號取值相等，而他們的姓名、性別和班級取值不相等。這就是一種數(shù)據(jù)依賴什么是數(shù)據(jù)依賴（續(xù)）4.數(shù)據(jù)依賴的類型函數(shù)依賴（FunctionalDependency，簡記為FD）多值依賴（MultivaluedDependency，簡記為MVD）其他四、關(guān)系模式的簡化表示關(guān)系模式R（U,D,DOM,F）簡化為一個三元組：

R（U,F）當(dāng)且僅當(dāng)U上的一個關(guān)系r滿足F時，r稱為關(guān)系模式R（U,F）的一個關(guān)系五、數(shù)據(jù)依賴對關(guān)系模式的影響[例1]建立一個描述學(xué)校教務(wù)的數(shù)據(jù)庫： 學(xué)生的學(xué)號（Sno）、所在系（Sdept） 系主任姓名（Mname）、課程名（Cname） 成績（Grade）單一的關(guān)系模式：Student<U、F>U＝｛Sno,Sdept,Mname,Cname,Grade｝數(shù)據(jù)依賴對關(guān)系模式的影響（續(xù)）

屬性組U上的一組函數(shù)依賴F：

F＝｛Sno→Sdept,Sdept→Mname,(Sno,Cname)→Grade｝

SnoCnameSdeptMnameGrade關(guān)系模式Student<U,F>中存在的問題1.數(shù)據(jù)冗余太大2.更新異常（UpdateAnomalies）3.插入異常（InsertionAnomalies）4.刪除異常（DeletionAnomalies）數(shù)據(jù)依賴對關(guān)系模式的影響（續(xù)）結(jié)論：Student關(guān)系模式不是一個好的模式?！昂谩钡哪Ｊ剑翰粫l(fā)生插入異常、刪除異常、更新異常，數(shù)據(jù)冗余應(yīng)盡可能少原因：由存在于模式中的某些數(shù)據(jù)依賴引起的解決方法：通過分解關(guān)系模式來消除其中不合適的數(shù)據(jù)依賴分解關(guān)系模式把這個單一模式分成3個關(guān)系模式：

S（Sno，Sdept，Sno→Sdept）;SC（Sno，Cno，Grade，（Sno，Cno）→Grade）;DEPT（Sdept，Mname，Sdept→Mname）第六章關(guān)系數(shù)據(jù)理論6.1問題的提出6.2規(guī)范化6.3數(shù)據(jù)依賴的公理系統(tǒng)*6.4模式的分解6.5小結(jié)6.2規(guī)范化

規(guī)范化理論正是用來改造關(guān)系模式，通過分解關(guān)系模式來消除其中不合適的數(shù)據(jù)依賴，以解決插入異常、刪除異常、更新異常和數(shù)據(jù)冗余問題。6.2規(guī)范化6.2.1函數(shù)依賴6.2.2碼6.2.3范式6.2.42NF6.2.53NF6.2.6BCNF6.2.7多值依賴6.2.84NF6.2.9規(guī)范化小結(jié)6.2.1函數(shù)依賴函數(shù)依賴平凡函數(shù)依賴與非平凡函數(shù)依賴完全函數(shù)依賴與部分函數(shù)依賴傳遞函數(shù)依賴一、函數(shù)依賴定義6.1設(shè)R(U)是一個屬性集U上的關(guān)系模式，X和Y是U的子集。若對于R(U)的任意一個可能的關(guān)系r，r中不可能存在兩個元組在X上的屬性值相等，而在Y上的屬性值不等，則稱“X函數(shù)確定Y”或“Y函數(shù)依賴于X”，記作X→Y。

說明

1.

所有關(guān)系實例均要滿足2.語義范疇的概念3.數(shù)據(jù)庫設(shè)計者可以對現(xiàn)實世界作強制的規(guī)定二、平凡函數(shù)依賴與非平凡函數(shù)依賴在關(guān)系模式R(U)中，對于U的子集X和Y，如果X→Y，但Y

X，則稱X→Y是非平凡的函數(shù)依賴若X→Y，但Y

X,則稱X→Y是平凡的函數(shù)依賴?yán)涸陉P(guān)系SC(Sno,Cno,Grade)中，非平凡函數(shù)依賴：(Sno,Cno)→

Grade

平凡函數(shù)依賴：(Sno,Cno)→

Sno(Sno,Cno)→Cno平凡函數(shù)依賴與非平凡函數(shù)依賴（續(xù)）若X→Y，則X稱為這個函數(shù)依賴的決定屬性組，也稱為決定因素（Determinant）。若X→Y，Y→X，則記作X←→Y。若Y不函數(shù)依賴于X，則記作X→Y。三、完全函數(shù)依賴與部分函數(shù)依賴定義6.2在R(U)中，如果X→Y，并且對于X的任何一個真子集X’，都有X’Y,則稱Y對X完全函數(shù)依賴，記作

XFY。若X→Y，但Y不完全函數(shù)依賴于X，則稱Y對X部分函數(shù)依賴，記作XPY。

完全函數(shù)依賴與部分函數(shù)依賴（續(xù)）[例1]中(Sno,Cno)→Grade是完全函數(shù)依賴，

(Sno,Cno)→Sdept是部分函數(shù)依賴因為Sno→Sdept成立，且Sno是（Sno，Cno）的真子集

FP四、傳遞函數(shù)依賴定義6.3在R(U)中，如果X→Y，(Y

X),Y→XY→Z，則稱Z對X傳遞函數(shù)依賴。記為：X→Z

注:如果Y→X，即X←→Y，則Z直接依賴于X。例:在關(guān)系Std(Sno,Sdept,Mname)中，有：

Sno→Sdept，Sdept→MnameMname傳遞函數(shù)依賴于Sno傳遞6.2規(guī)范化6.2.1函數(shù)依賴6.2.2碼6.2.3范式6.2.42NF6.2.53NF6.2.6BCNF6.2.7多值依賴6.2.84NF6.2.9規(guī)范化小結(jié)6.2.2碼定義6.4設(shè)K為R<U,F>中的屬性或?qū)傩越M合。若K

U，則K稱為R的侯選碼（CandidateKey）。若候選碼多于一個，則選定其中的一個做為主碼（PrimaryKey）。F碼（續(xù)）主屬性與非主屬性包含在任何一個候選碼中的屬性，稱為主屬性（Primeattribute）不包含在任何碼中的屬性稱為非主屬性（Nonprimeattribute）或非碼屬性（Non-keyattribute）全碼整個屬性組是碼，稱為全碼（All-key）碼（續(xù)）[例2]

關(guān)系模式S(Sno,Sdept,Sage)，單個屬性Sno是碼，

SC（Sno，Cno，Grade）中，（Sno，Cno）是碼[例3]

關(guān)系模式R（P，W，A）

P：演奏者W：作品A：聽眾一個演奏者可以演奏多個作品某一作品可被多個演奏者演奏聽眾可以欣賞不同演奏者的不同作品碼為(P，W，A)，即All-Key外部碼定義6.5關(guān)系模式R中屬性或?qū)傩越MX并非R的碼，但X是另一個關(guān)系模式的碼，則稱X是R的外部碼（Foreignkey）也稱外碼如在SC（Sno，Cno，Grade）中，Sno不是碼，但Sno是關(guān)系模式S（Sno，Sdept，Sage）的碼，則Sno是關(guān)系模式SC的外部碼主碼與外部碼一起提供了表示關(guān)系間聯(lián)系的手段6.2規(guī)范化6.2.1函數(shù)依賴6.2.2碼6.2.3范式6.2.42NF6.2.53NF6.2.6BCNF6.2.7多值依賴6.2.84NF6.2.9規(guī)范化小結(jié)6.2.3范式范式是符合某一種級別的關(guān)系模式的集合關(guān)系數(shù)據(jù)庫中的關(guān)系必須滿足一定的要求。滿足不同程度要求的為不同范式范式的種類：

第一范式(1NF)

第二范式(2NF)

第三范式(3NF) BC范式(BCNF)

第四范式(4NF)

第五范式(5NF)6.2.3范式各種范式之間存在聯(lián)系：某一關(guān)系模式R為第n范式，可簡記為R∈nNF。一個低一級范式的關(guān)系模式，通過模式分解可以轉(zhuǎn)換為若干個高一級范式的關(guān)系模式的集合，這種過程就叫規(guī)范化

6.2規(guī)范化6.2.1函數(shù)依賴6.2.2碼6.2.3范式6.2.42NF6.2.53NF6.2.6BCNF6.2.7多值依賴6.2.84NF6.2.9規(guī)范化小結(jié)6.2.42NF1NF的定義 如果一個關(guān)系模式R的所有屬性都是不可分的基本數(shù)據(jù)項，則R∈1NF第一范式是對關(guān)系模式的最起碼的要求。不滿足第一范式的數(shù)據(jù)庫模式不能稱為關(guān)系數(shù)據(jù)庫但是滿足第一范式的關(guān)系模式并不一定是一個好的關(guān)系模式2NF（續(xù)）[例4]關(guān)系模式S-L-C(Sno,Sdept,Sloc,Cno,Grade)Sloc為學(xué)生住處，假設(shè)每個系的學(xué)生住在同一個地方函數(shù)依賴包括：

(Sno,Cno)FGradeSno→Sdept(Sno,Cno)PSdeptSno→Sloc(Sno,Cno)PSlocSdept→Sloc2NF（續(xù)）S-L-C的碼為(Sno,Cno)S-L-C滿足第一范式。非主屬性Sdept和Sloc部分函數(shù)依賴于碼(Sno,Cno)SnoCnoGradeSdeptSlocS-L-CS-L-C不是一個好的關(guān)系模式（續(xù)）(1)插入異常(2)刪除異常(3)數(shù)據(jù)冗余度大(4)修改復(fù)雜S-L-C不是一個好的關(guān)系模式（續(xù)）原因

Sdept、Sloc部分函數(shù)依賴于碼。解決方法

S-L-C分解為兩個關(guān)系模式，以消除這些部分函數(shù)依賴

SC（Sno，Cno，Grade）

S-L（Sno，Sdept，Sloc）2NF（續(xù)）函數(shù)依賴圖：SnoCnoGradeSCS-LSnoSdeptSloc關(guān)系模式SC的碼為（Sno，Cno）關(guān)系模式S-L的碼為Sno這樣非主屬性對碼都是完全函數(shù)依賴

2NF（續(xù)）2NF的定義 定義6.6若R∈1NF，且每一個非主屬性完全函數(shù)依賴于碼，則R∈2NF。 例：S-L-C(Sno,Sdept,Sloc,Cno,Grade)∈1NFS-L-C(Sno,Sdept,Sloc,Cno,Grade)∈2NF SC（Sno，Cno，Grade）∈

2NF S-L（Sno，Sdept，Sloc）∈

2NF2NF（續(xù)）采用投影分解法將一個1NF的關(guān)系分解為多個2NF的關(guān)系，可以在一定程度上減輕原1NF關(guān)系中存在的插入異常、刪除異常、數(shù)據(jù)冗余度大、修改復(fù)雜等問題。將一個1NF關(guān)系分解為多個2NF的關(guān)系，并不能完全消除關(guān)系模式中的各種異常情況