AnIntroductiontoDatabaseSystem中國(guó)人民大學(xué)信息學(xué)院

王珊數(shù)據(jù)庫(kù)系統(tǒng)概論AnIntroductiontoDatabaseSystem第三章關(guān)系數(shù)據(jù)庫(kù)標(biāo)準(zhǔn)語(yǔ)言SQLAnIntroductiontoDatabaseSystem第三章

關(guān)系數(shù)據(jù)庫(kù)標(biāo)準(zhǔn)語(yǔ)言SQL3.1SQL概述3.2學(xué)生-課程數(shù)據(jù)庫(kù)3.3數(shù)據(jù)定義3.4數(shù)據(jù)查詢3.5數(shù)據(jù)更新3.6視圖3.7小結(jié)AnIntroductiontoDatabaseSystem關(guān)系數(shù)據(jù)庫(kù)的3級(jí)模式結(jié)構(gòu)SQL視圖2視圖1基本表2基本表1基本表3基本表4存儲(chǔ)文件2存儲(chǔ)文件1外模式模式內(nèi)模式復(fù)習(xí)第1章外模式—視圖+部分基本表

3級(jí)模式的概念：模式——基本表

內(nèi)模式—存儲(chǔ)文件AnIntroductiontoDatabaseSystem關(guān)系模型的數(shù)據(jù)結(jié)構(gòu)基本表本身獨(dú)立存在的表SQL中一個(gè)關(guān)系就對(duì)應(yīng)一個(gè)基本表一個(gè)(或多個(gè))基本表對(duì)應(yīng)一個(gè)存儲(chǔ)文件一個(gè)表可以帶若干索引存儲(chǔ)文件邏輯結(jié)構(gòu)組成了關(guān)系數(shù)據(jù)庫(kù)的內(nèi)模式物理結(jié)構(gòu)是任意的，對(duì)用戶透明視圖從一個(gè)或幾個(gè)基本表導(dǎo)出的表數(shù)據(jù)庫(kù)中只存放視圖的定義而不存放視圖對(duì)應(yīng)的數(shù)據(jù)視圖是一個(gè)虛表用戶可以在視圖上再定義視圖AnIntroductiontoDatabaseSystem3.3數(shù)據(jù)定義3.3.1模式的定義與刪除3.3.2基本表的定義、刪除與修改3.3.3索引的建立與刪除SequentialFile201040306050807010090SequentialFile按照某個(gè)屬性排序的文件順序文件上的索引SequentialFile201040306050807010090稠密索引（DenseIndex）102030405060708090100110120OneitemforeachRecordItem:(Searchkey,pointertorecord)B樹和B+樹B樹能自動(dòng)保持與數(shù)據(jù)文件大小適應(yīng)的索引層次平衡樹能對(duì)所使用的存儲(chǔ)空間進(jìn)行管理，使每個(gè)塊處于全滿半滿之間B+樹特殊的B樹，內(nèi)部結(jié)點(diǎn)只存儲(chǔ)索引塊葉結(jié)點(diǎn)用指針連接4.3.1B+樹指向碼值為

31的記錄指向碼值為

37的記錄指向碼值為

41的記錄指向順序集上的

下一個(gè)葉結(jié)點(diǎn)典型的葉結(jié)點(diǎn)指向碼值

K<23指向碼值

23≤K<31指向碼值

31≤K<43指向碼值

K≥43典型的非葉結(jié)點(diǎn)參數(shù)n=3:每個(gè)塊存放碼值的最大個(gè)數(shù):3最小碼數(shù)：m最小指針數(shù)：pB+樹指針和碼的數(shù)量最大指針數(shù)最大碼數(shù)最小指針數(shù)(指向數(shù)據(jù))最小碼數(shù)內(nèi)部結(jié)點(diǎn)n+1n(n+1)/2(n+1)/2-1葉結(jié)點(diǎn)n+1n(n+1)/2(n+1)/2根結(jié)點(diǎn)n+1n11AnIntroductiontoDatabaseSystemB+樹中的查找查找鍵為37的記錄13<3731<37<43找到37鍵值為37的記錄IO數(shù)：4若把第一、第二層結(jié)點(diǎn)保存在緩沖區(qū)

IO數(shù)：2AnIntroductiontoDatabaseSystemB+樹中的查找(若索引塊全在磁盤)查找鍵為37的記錄讀入root節(jié)點(diǎn),IO=1根據(jù)條件13<37,讀取下一節(jié)點(diǎn)塊讀入下一節(jié)點(diǎn),IO=2根據(jù)條件31<37<43,讀取下一節(jié)點(diǎn)塊讀入下一節(jié)點(diǎn),IO=3,找到鍵值37,讀取記錄指針,讀取記錄所在的塊MainMemoryDisk讀入數(shù)據(jù)塊,IO=4,根據(jù)記錄指針找到鍵值為37的記錄AnIntroductiontoDatabaseSystemB+樹中的查找

(若第一、二層索引塊在內(nèi)存)查找鍵為37的記錄讀取root節(jié)點(diǎn),根據(jù)條件13<37,讀取下一節(jié)點(diǎn)塊讀取下一節(jié)點(diǎn),根據(jù)條件31<37<43,讀取下一節(jié)點(diǎn)塊讀入下一節(jié)點(diǎn),IO=1,找到鍵值37,讀取記錄指針,讀取記錄所在的塊MainMemoryDisk讀入數(shù)據(jù)塊,IO=2,根據(jù)記錄指針找到鍵值為37的記錄B+樹的插入三種情況：葉結(jié)點(diǎn)滿內(nèi)部結(jié)點(diǎn)滿動(dòng)作否否把碼放在葉結(jié)點(diǎn)合適的位置是否1.分裂葉結(jié)點(diǎn)2.把碼的中間值放在內(nèi)部結(jié)點(diǎn)合適的位置3.左側(cè)的葉結(jié)點(diǎn)包括小于中間值的碼4.右側(cè)的葉結(jié)點(diǎn)包括大于或等于中間值的碼是是1.分裂葉節(jié)點(diǎn)2.左側(cè)的葉結(jié)點(diǎn)包括小于中間值的碼3.右側(cè)的葉結(jié)點(diǎn)包括大于或等于中間值的碼4.分裂內(nèi)部結(jié)點(diǎn)5.左側(cè)的內(nèi)部結(jié)點(diǎn)包括小于中間值的碼6.右側(cè)的內(nèi)部結(jié)點(diǎn)包括大于中間值的碼7.把碼的中間值放在上一級(jí)內(nèi)部結(jié)點(diǎn)合適的位置如果上一級(jí)內(nèi)部結(jié)點(diǎn)已滿，則繼續(xù)分裂上一級(jí)結(jié)點(diǎn)B+樹的插入插入碼40

（屬于情況3）401.分裂葉結(jié)點(diǎn)2.碼中間值上提

分裂內(nèi)部結(jié)點(diǎn)3.碼中間值上提(40,b)B+樹的插入插入碼40

（屬于情況3）1.分裂葉結(jié)點(diǎn)2.碼中間值上提

分裂內(nèi)部結(jié)點(diǎn)3.碼中間值上提13>4031<40<434041葉結(jié)點(diǎn)滿4340B+樹的刪除三種情況：葉結(jié)點(diǎn)小于最小充滿度內(nèi)部結(jié)點(diǎn)小于最小充滿度動(dòng)作否否1.刪除葉結(jié)點(diǎn)中的碼2.對(duì)碼重新排序3.如果碼在上一級(jí)內(nèi)部結(jié)點(diǎn)出現(xiàn)，則用下一個(gè)碼替換是否1.組合葉結(jié)點(diǎn)和它的兄弟結(jié)點(diǎn)2.相應(yīng)更改內(nèi)部結(jié)點(diǎn)以反映這種改變是是1.組合葉結(jié)點(diǎn)和它的兄弟結(jié)點(diǎn)2.相應(yīng)更改內(nèi)部結(jié)點(diǎn)以反映這種改變3.組合內(nèi)部結(jié)點(diǎn)和它的兄弟結(jié)點(diǎn)

繼續(xù)組合內(nèi)部結(jié)點(diǎn)，直到找到一個(gè)滿足充滿度的結(jié)點(diǎn)或者到達(dá)根結(jié)點(diǎn)B+樹的刪除刪除碼7（屬于情況2）551.組合葉結(jié)點(diǎn)2.更改內(nèi)部結(jié)點(diǎn)以反映這種改變B+樹的刪除-刪除碼77<137<=74143577刪除碼7（屬于情況2）1.組合葉結(jié)點(diǎn)2.更改內(nèi)部結(jié)點(diǎn)以反映這種改變5B+樹的刪除刪除碼11（屬于情況3，需要遞歸更改內(nèi)部結(jié)點(diǎn)）1.組合葉結(jié)點(diǎn)5132.更改內(nèi)部結(jié)點(diǎn)以反映這種改變（需要遞歸）233143B+樹的刪除-刪除碼1111<135<11414351.組合葉結(jié)點(diǎn)2.更改內(nèi)部結(jié)點(diǎn)以反映這種改變5133123刪除碼11（屬于情況3，需要遞歸更改內(nèi)部結(jié)點(diǎn)）1113AnIntroductiontoDatabaseSystem3.4數(shù)據(jù)查詢3.4.1單表查詢3.4.2連接查詢3.4.3嵌套查詢3.4.4集合查詢3.4.5Select語(yǔ)句的一般形式

AnIntroductiontoDatabaseSystem一、等值與非等值連接查詢等值連接：連接運(yùn)算符為=[例33]查詢每個(gè)學(xué)生及其選修課程的情況

SELECTStudent.*，SC.* FROMStudent，SC WHEREStudent.Sno=SC.Sno；

/*連接謂詞*/AnIntroductiontoDatabaseSystem等值與非等值連接查詢（續(xù)）Student.SnoSnameSsexSageSdeptSC.SnoCnoGrade200215121李勇男20CS200215121192200215121李勇男20CS200215121285200215121李勇男20CS200215121388200215122劉晨女19CS200215122290200215122劉晨女19CS200215122380查詢結(jié)果：AnIntroductiontoDatabaseSystem等值與非等值連接查詢（續(xù)）自然連接：[例34]對(duì)[例33]用自然連接完成。

SELECTStudent.Sno，Sname，Ssex，Sage，Sdept，

Cno，GradeFROMStudent，SCWHEREStudent.Sno=SC.Sno；AnIntroductiontoDatabaseSystem連接操作的執(zhí)行:嵌套循環(huán)法(NESTED-LOOP)

select*froms,spjwheres.sno=spj.sno;S表SNOSNAMESTATUSCITYS1精益20天津S2盛錫10北京S3東方紅30北京S4豐泰盛20天津S5為民30上海SPJ表SNOPNOJNOQTYS1P1J1200S2P1J3100S1P1J4700S1P2J2100S2P3J1400S2P3J2200S2P3J4500S2P3J5400S2P5J1400S2P5J2100S5P1J1200S3P3J1200S4P5J1100S4P6J3300S4P6J4200S3P2J4100S5P3J1200S1P6J2200S5P6J4500resultsSNOSNAMECITYQTYS1精益天津200S1精益天津700S1精益天津100S1精益天津200S2盛錫北京100……AnIntroductiontoDatabaseSystem連接操作的執(zhí)行過程嵌套循環(huán)法(NESTED-LOOP)首先在表1中找到第一個(gè)元組，然后從頭開始掃描表2，逐一查找滿足連接件的元組，找到后就將表1中的第一個(gè)元組與該元組拼接起來，形成結(jié)果表中一個(gè)元組。表2全部查找完后，再找表1中第二個(gè)元組，然后再?gòu)念^開始掃描表2，逐一查找滿足連接條件的元組，找到后就將表1中的第二個(gè)元組與該元組拼接起來，形成結(jié)果表中一個(gè)元組。重復(fù)上述操作，直到表1中的全部元組都處理完畢

AnIntroductiontoDatabaseSystem連接操作的執(zhí)行:排序合并法(SORT-MERGE)S表SNOSNAMESTATUSCITYS1精益20天津S2盛錫10北京S3東方紅30北京S4豐泰盛20天津S5為民30上海SPJ表SNOPNOJNOQTYS1P1J1200S1P1J3100S1P1J4700S1P2J2100S2P3J1400S2P3J2200S2P3J4500S2P3J5400S2P5J1400S2P5J2100S3P1J1200S3P3J1200S4P5J1100S4P6J3300S4P6J4200S5P2J4100S5P3J1200S5P6J2200S5P6J4500resultsSNOSNAMECITYQTYS1精益天津200S1精益天津700S1精益天津100S1精益天津200S2盛錫北京100……AnIntroductiontoDatabaseSystem排序合并法(SORT-MERGE)常用于=連接首先按連接屬性對(duì)表1和表2排序?qū)Ρ?的第一個(gè)元組，從頭開始掃描表2，順序查找滿足連接條件的元組，找到后就將表1中的第一個(gè)元組與該元組拼接起來，形成結(jié)果表中一個(gè)元組。當(dāng)遇到表2中第一條大于表1連接字段值的元組時(shí)，對(duì)表2的查詢不再繼續(xù)AnIntroductiontoDatabaseSystem排序合并法找到表1的第二條元組，然后從剛才的中斷點(diǎn)處繼續(xù)順序掃描表2，查找滿足連接條件的元組，找到后就將表1中的第一個(gè)元組與該元組拼接起來，形成結(jié)果表中一個(gè)元組。直接遇到表2中大于表1連接字段值的元組時(shí)，對(duì)表2的查詢不再繼續(xù)重復(fù)上述操作，直到表1或表2中的全部元組都處理完畢為止

AnIntroductiontoDatabaseSystem索引連接(INDEX-JOIN)

select*froms,spjwheres.sno=spj.sno;S表SNOSNAMESTATUSCITYS1精益20天津S2盛錫10北京S3東方紅30北京S4豐泰盛20天津S5為民30上海SPJ表SNOPNOJNOQTYS1P1