數(shù)據(jù)庫(kù)系統(tǒng)原理課件

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

關(guān)系數(shù)據(jù)模型的數(shù)據(jù)組織結(jié)構(gòu)關(guān)系數(shù)據(jù)模型的基本術(shù)語(yǔ)關(guān)系數(shù)據(jù)模型的特點(diǎn)學(xué)習(xí)目標(biāo)掌握關(guān)系數(shù)據(jù)模型、關(guān)系模式、關(guān)系和關(guān)系數(shù)據(jù)庫(kù)基本概念和它們之間的差別關(guān)系模型的完整性掌握基本的關(guān)系代數(shù)運(yùn)算（并、交、差、投影、選擇、連接等）學(xué)習(xí)難點(diǎn)重點(diǎn)關(guān)系模型、關(guān)系與關(guān)系數(shù)據(jù)庫(kù)之間的關(guān)系關(guān)系的數(shù)學(xué)定義及術(shù)語(yǔ)關(guān)系模型的完整性關(guān)系代數(shù)的運(yùn)算規(guī)則第二章關(guān)系數(shù)據(jù)庫(kù)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ù)庫(kù)簡(jiǎn)介系統(tǒng)而嚴(yán)格地提出關(guān)系模型的是美國(guó)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ù)庫(kù)簡(jiǎn)介關(guān)系數(shù)據(jù)庫(kù)應(yīng)用數(shù)學(xué)方法來(lái)處理數(shù)據(jù)庫(kù)中的數(shù)據(jù)關(guān)系數(shù)據(jù)庫(kù)是支持關(guān)系模型的數(shù)據(jù)庫(kù)系統(tǒng)關(guān)系模型由數(shù)據(jù)結(jié)構(gòu)、關(guān)系操作集合和完整性約束三部分組成80年代后，關(guān)系數(shù)據(jù)庫(kù)系統(tǒng)成為最重要、最流行的數(shù)據(jù)庫(kù)系統(tǒng)關(guān)系數(shù)據(jù)庫(kù)簡(jiǎn)介典型實(shí)驗(yàn)系統(tǒng)SystemRUniversityINGRES典型商用系統(tǒng)ORACLESYBASEINFORMIXDB2SQL/DSINGRES第二章關(guān)系數(shù)據(jù)庫(kù)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ù)庫(kù)2.1.1

關(guān)系單一的數(shù)據(jù)結(jié)構(gòu)----關(guān)系現(xiàn)實(shí)世界的實(shí)體以及實(shí)體間的各種聯(lián)系均用關(guān)系來(lái)表示邏輯結(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ù)介于某個(gè)取值范圍的整數(shù)長(zhǎng)度指定長(zhǎng)度的字符串集合{‘男’，‘女’}……………..2.笛卡爾積（CartesianProduct）笛卡爾積給定一組域D1，D2，…，Dn，這些域中可以有相同的。

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

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

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

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

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

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

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

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

(張清玫，計(jì)算機(jī)專業(yè)，劉晨)，(劉逸，信息專業(yè)，王敏)}關(guān)系（續(xù)）7)三類關(guān)系基本關(guān)系（基本表或基表）實(shí)際存在的表，是實(shí)際存儲(chǔ)數(shù)據(jù)的邏輯表示查詢表查詢結(jié)果對(duì)應(yīng)的表視圖表由基本表或其他視圖表導(dǎo)出的表，是虛表，不對(duì)應(yīng)實(shí)際存儲(chǔ)的數(shù)據(jù)關(guān)系（續(xù)）8)基本關(guān)系的性質(zhì)①列是同質(zhì)的（Homogeneous）②不同的列可出自同一個(gè)域其中的每一列稱為一個(gè)屬性不同的屬性要給予不同的屬性名③列的順序無(wú)所謂，列的次序可以任意交換④任意兩個(gè)元組的候選碼不能相同⑤行的順序無(wú)所謂，行的次序可以任意交換基本關(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ù)庫(kù)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)系模式是對(duì)關(guān)系的描述元組集合的結(jié)構(gòu)屬性構(gòu)成屬性來(lái)自的域?qū)傩耘c域之間的映象關(guān)系元組語(yǔ)義以及完整性約束條件屬性間的數(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中屬性所來(lái)自的域

DOM屬性向域的映象集合

F

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

DOM（SUPERVISOR-PERSON）=DOM（POSTGRADUATE-PERSON）=PERSON定義關(guān)系模式(續(xù))關(guān)系模式通?？梢院?jiǎn)記為

R(U)或R(A1，A2，…，An)R:關(guān)系名A1，A2，…，An:屬性名注：域名及屬性向域的映象常常直接說(shuō)明為屬性的類型、長(zhǎng)度3.關(guān)系模式與關(guān)系關(guān)系模式對(duì)關(guān)系的描述靜態(tài)的、穩(wěn)定的關(guān)系關(guān)系模式在某一時(shí)刻的狀態(tài)或內(nèi)容動(dòng)態(tài)的、隨時(shí)間不斷變化的關(guān)系模式和關(guān)系往往統(tǒng)稱為關(guān)系通過(guò)上下文加以區(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ù)庫(kù)2.1.3

關(guān)系數(shù)據(jù)庫(kù)關(guān)系數(shù)據(jù)庫(kù)在一個(gè)給定的應(yīng)用領(lǐng)域中，所有實(shí)體及實(shí)體之間聯(lián)系的關(guān)系的集合構(gòu)成一個(gè)關(guān)系數(shù)據(jù)庫(kù)關(guān)系數(shù)據(jù)庫(kù)的型與值2.關(guān)系數(shù)據(jù)庫(kù)的型與值關(guān)系數(shù)據(jù)庫(kù)的型:關(guān)系數(shù)據(jù)庫(kù)模式對(duì)關(guān)系數(shù)據(jù)庫(kù)的描述。關(guān)系數(shù)據(jù)庫(kù)模式包括若干域的定義在這些域上定義的若干關(guān)系模式關(guān)系數(shù)據(jù)庫(kù)的值:關(guān)系模式在某一時(shí)刻對(duì)應(yīng)的關(guān)系的集合，簡(jiǎn)稱為關(guān)系數(shù)據(jù)庫(kù)第二章關(guān)系數(shù)據(jù)庫(kù)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)系操作的特點(diǎn)集合操作方式：操作的對(duì)象和結(jié)果都是集合，一次一集合的方式（set-at-a-time），非關(guān)系數(shù)據(jù)模型：一次一記錄方式2.2.2關(guān)系數(shù)據(jù)庫(kù)語(yǔ)言的分類

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

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

或者取空值（F的每個(gè)屬性值均為空值）

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

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

課程(課程號(hào)，課程名，學(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ù)庫(kù)關(guān)系的數(shù)據(jù)操作集合查詢選擇、投影、連接、除、并、交、差數(shù)據(jù)更新插入、刪除、修改關(guān)系的完整性約束實(shí)體完整性參照完整性外碼用戶定義的完整性實(shí)體完整性是對(duì)應(yīng)元組或行而言的，參照完整性是對(duì)不同表之間的屬性或列的參照關(guān)系而言的實(shí)現(xiàn)數(shù)據(jù)完整性的方法在關(guān)系模式定義描述中定義數(shù)據(jù)完整性檢查條件使用觸發(fā)器和存儲(chǔ)過(guò)程實(shí)現(xiàn)數(shù)據(jù)完整性檢查用其它編程工具編寫程序?qū)崿F(xiàn)數(shù)據(jù)完整性檢查第九章

關(guān)系系統(tǒng)及其查詢優(yōu)化9.1關(guān)系數(shù)據(jù)庫(kù)系統(tǒng)的查詢處理9.2關(guān)系數(shù)據(jù)庫(kù)系統(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ù)庫(kù)系統(tǒng)的查詢處理9.1.1查詢處理步驟9.1.2實(shí)現(xiàn)查詢操作的算法示例9.1.1查詢處理步驟RDBMS查詢處理階段：1.查詢分析2.查詢檢查3.查詢優(yōu)化4.查詢執(zhí)行

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

從查詢語(yǔ)句中識(shí)別出語(yǔ)言符號(hào)

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

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

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

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

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

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

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

C1：無(wú)條件；

C2：Sno＝'200215121'；

C3：Sage>20；

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

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

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

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

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

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

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

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

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

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

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

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

第九章

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

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

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

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

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

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

E2)E3≡E1(E2

E3)(E1

E2)E3≡E1(E2

E3)關(guān)系代數(shù)表達(dá)式等價(jià)變換規(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是選擇條件。選擇的串接律說(shuō)明選擇條件可以合并。這樣一次就可檢查全部條件。關(guān)系代數(shù)表達(dá)式等價(jià)變換規(guī)則（續(xù)）5.選擇與投影操作的交換律

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

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

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

(E1×E2)≡(E1)×E2

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

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

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

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

它使部分選擇在笛卡爾積前先做。關(guān)系代數(shù)表達(dá)式等價(jià)變換規(guī)則（續(xù)）7.選擇與并的分配律 設(shè)E=E1∪E2，E1，E2有相同的屬性名，則

σF(E1∪E2)≡σF(E1)∪σF(E2)8.選擇與差運(yùn)算的分配律 若E1與E2有相同的屬性名，則

σF(E1-E2)≡σF(E1)-σF(E2)9.選擇對(duì)自然連接的分配律

σF(E1

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

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

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

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

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

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

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

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

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

第九章

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

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

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

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

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

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

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

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

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

3.如果上面2個(gè)規(guī)則都不適用，其中一個(gè)表較小選用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基于代價(jià)的優(yōu)化9.4.2基于代價(jià)的優(yōu)化

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

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

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(jià)的優(yōu)化（續(xù)）4.排序-合并連接算法的代價(jià)估算公式如果連接表已經(jīng)按照連接屬性排好序，則

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

關(guān)系系統(tǒng)及其查詢優(yōu)化9.1關(guān)系數(shù)據(jù)庫(kù)系統(tǒng)的查詢處理9.2關(guān)系數(shù)據(jù)庫(kù)系統(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)化基于代價(jià)的優(yōu)化本章的目的：希望讀者掌握查詢優(yōu)化方法的概念和技術(shù)小結(jié)（續(xù)）比較復(fù)雜的查詢，尤其是涉及連接和嵌套的查詢不要把優(yōu)化的任務(wù)全部放在RDBMS上應(yīng)該找出RDBMS的優(yōu)化規(guī)律，以寫出適合RDBMS自動(dòng)優(yōu)化的SQL語(yǔ)句對(duì)于RDBMS不能優(yōu)化的查詢需要重寫查詢語(yǔ)句，進(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)的紅色零件的工程號(hào)山東理工大學(xué)計(jì)算機(jī)學(xué)院數(shù)據(jù)庫(kù)系統(tǒng)概論第六章關(guān)系數(shù)據(jù)理論學(xué)習(xí)目標(biāo)給定一個(gè)關(guān)系模式和已知的語(yǔ)義，能夠找出該關(guān)系模式的函數(shù)依賴關(guān)系、關(guān)系模式的候選碼、主碼、主屬性、非主屬性給定一個(gè)關(guān)系模式和已知的語(yǔ)義，能夠判斷該關(guān)系模式屬于第幾范式，能把該關(guān)系模式分解為符合2NF、3NF或BCNF要求的關(guān)系模式集合難重點(diǎn)：關(guān)系數(shù)據(jù)庫(kù)規(guī)范化第六章關(guān)系數(shù)據(jù)理論6.1問(wèn)題的提出6.2規(guī)范化6.3數(shù)據(jù)依賴的公理系統(tǒng)*6.4模式的分解6.5小結(jié)6.1問(wèn)題的提出關(guān)系數(shù)據(jù)庫(kù)邏輯設(shè)計(jì)針對(duì)具體問(wèn)題，如何構(gòu)造一個(gè)適合于它的數(shù)據(jù)模式數(shù)據(jù)庫(kù)邏輯設(shè)計(jì)的工具──關(guān)系數(shù)據(jù)庫(kù)的規(guī)范化理論問(wèn)題的提出一、概念回顧二、關(guān)系模式的形式化定義三、什么是數(shù)據(jù)依賴四、關(guān)系模式的簡(jiǎn)化定義五、數(shù)據(jù)依賴對(duì)關(guān)系模式影響一、概念回顧關(guān)系：描述實(shí)體、屬性、實(shí)體間的聯(lián)系。從形式上看，它是一張二維表，是所涉及屬性的笛卡爾積的一個(gè)子集。關(guān)系模式：用來(lái)定義關(guān)系。關(guān)系數(shù)據(jù)庫(kù)：基于關(guān)系模型的數(shù)據(jù)庫(kù)，利用關(guān)系來(lái)描述現(xiàn)實(shí)世界。從形式上看，它由一組關(guān)系組成。關(guān)系數(shù)據(jù)庫(kù)的模式：定義這組關(guān)系的關(guān)系模式的全體。二、關(guān)系模式的形式化定義關(guān)系模式由五部分組成，即它是一個(gè)五元組：

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

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

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

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

SnoCnameSdeptMnameGrade關(guān)系模式Student<U,F>中存在的問(wèn)題1.數(shù)據(jù)冗余太大2.更新異常（UpdateAnomalies）3.插入異常（InsertionAnomalies）4.刪除異常（DeletionAnomalies）數(shù)據(jù)依賴對(duì)關(guān)系模式的影響（續(xù)）結(jié)論：Student關(guān)系模式不是一個(gè)好的模式。“好”的模式：不會(huì)發(fā)生插入異常、刪除異常、更新異常，數(shù)據(jù)冗余應(yīng)盡可能少原因：由存在于模式中的某些數(shù)據(jù)依賴引起的解決方法：通過(guò)分解關(guān)系模式來(lái)消除其中不合適的數(shù)據(jù)依賴分解關(guān)系模式把這個(gè)單一模式分成3個(gè)關(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問(wèn)題的提出6.2規(guī)范化6.3數(shù)據(jù)依賴的公理系統(tǒng)*6.4模式的分解6.5小結(jié)6.2規(guī)范化

規(guī)范化理論正是用來(lái)改造關(guān)系模式，通過(guò)分解關(guān)系模式來(lái)消除其中不合適的數(shù)據(jù)依賴，以解決插入異常、刪除異常、更新異常和數(shù)據(jù)冗余問(wè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.1函數(shù)依賴函數(shù)依賴平凡函數(shù)依賴與非平凡函數(shù)依賴完全函數(shù)依賴與部分函數(shù)依賴傳遞函數(shù)依賴一、函數(shù)依賴定義6.1設(shè)R(U)是一個(gè)屬性集U上的關(guān)系模式，X和Y是U的子集。若對(duì)于R(U)的任意一個(gè)可能的關(guān)系r，r中不可能存在兩個(gè)元組在X上的屬性值相等，而在Y上的屬性值不等，則稱“X函數(shù)確定Y”或“Y函數(shù)依賴于X”，記作X→Y。

說(shuō)明

1.

所有關(guān)系實(shí)例均要滿足2.語(yǔ)義范疇的概念3.數(shù)據(jù)庫(kù)設(shè)計(jì)者可以對(duì)現(xiàn)實(shí)世界作強(qiáng)制的規(guī)定二、平凡函數(shù)依賴與非平凡函數(shù)依賴在關(guān)系模式R(U)中，對(duì)于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稱為這個(gè)函數(shù)依賴的決定屬性組，也稱為決定因素（Determinant）。若X→Y，Y→X，則記作X←→Y。若Y不函數(shù)依賴于X，則記作X→Y。三、完全函數(shù)依賴與部分函數(shù)依賴定義6.2在R(U)中，如果X→Y，并且對(duì)于X的任何一個(gè)真子集X’，都有X’Y,則稱Y對(duì)X完全函數(shù)依賴，記作

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

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

(Sno,Cno)→Sdept是部分函數(shù)依賴因?yàn)镾no→Sdept成立，且Sno是（Sno，Cno）的真子集

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

X),Y→XY→Z，則稱Z對(duì)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）。若候選碼多于一個(gè)，則選定其中的一個(gè)做為主碼（PrimaryKey）。F碼（續(xù)）主屬性與非主屬性包含在任何一個(gè)候選碼中的屬性，稱為主屬性（Primeattribute）不包含在任何碼中的屬性稱為非主屬性（Nonprimeattribute）或非碼屬性（Non-keyattribute）全碼整個(gè)屬性組是碼，稱為全碼（All-key）碼（續(xù)）[例2]

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

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

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

P：演奏者W：作品A：聽(tīng)眾一個(gè)演奏者可以演奏多個(gè)作品某一作品可被多個(gè)演奏者演奏聽(tīng)眾可以欣賞不同演奏者的不同作品碼為(P，W，A)，即All-Key外部碼定義6.5關(guān)系模式R中屬性或?qū)傩越MX并非R的碼，但X是另一個(gè)關(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范式范式是符合某一種級(jí)別的關(guān)系模式的集合關(guān)系數(shù)據(jù)庫(kù)中的關(guān)系必須滿足一定的要求。滿足不同程度要求的為不同范式范式的種類：

第一范式(1NF)

第二范式(2NF)

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

第四范式(4NF)

第五范式(5NF)6.2.3范式各種范式之間存在聯(lián)系：某一關(guān)系模式R為第n范式，可簡(jiǎn)記為R∈nNF。一個(gè)低一級(jí)范式的關(guān)系模式，通過(guò)模式分解可以轉(zhuǎn)換為若干個(gè)高一級(jí)范式的關(guān)系模式的集合，這種過(guò)程就叫規(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的定義 如果一個(gè)關(guān)系模式R的所有屬性都是不可分的基本數(shù)據(jù)項(xiàng)，則R∈1NF第一范式是對(duì)關(guān)系模式的最起碼的要求。不滿足第一范式的數(shù)據(jù)庫(kù)模式不能稱為關(guān)系數(shù)據(jù)庫(kù)但是滿足第一范式的關(guān)系模式并不一定是一個(gè)好的關(guān)系模式2NF（續(xù)）[例4]關(guān)系模式S-L-C(Sno,Sdept,Sloc,Cno,Grade)Sloc為學(xué)生住處，假設(shè)每個(gè)系的學(xué)生住在同一個(gè)地方函數(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不是一個(gè)好的關(guān)系模式（續(xù)）(1)插入異常(2)刪除異常(3)數(shù)據(jù)冗余度大(4)修改復(fù)雜S-L-C不是一個(gè)好的關(guān)系模式（續(xù)）原因

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

S-L-C分解為兩個(gè)關(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這樣非主屬性對(duì)碼都是完全函數(shù)依賴

2NF（續(xù)）2NF的定義 定義6.6若R∈1NF，且每一個(gè)非主屬性完全函數(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ù)）采用投影分解法將一個(gè)1NF的關(guān)系分解為多個(gè)2NF的關(guān)系，可以在一定程度上減輕原1NF關(guān)系中存在的插入異常、刪除異常、數(shù)據(jù)冗余度大、修改復(fù)雜等問(wèn)題。將一個(gè)1NF關(guān)系分解為多個(gè)2NF的關(guān)系，并不能完全消除關(guān)系模式中的各種異常情況