第九章數(shù)據(jù)庫(kù)

第九章數(shù)據(jù)庫(kù)第1頁(yè)，共28頁(yè)，2023年，2月20日，星期三 當(dāng)今的技術(shù)已經(jīng)能夠存儲(chǔ)相當(dāng)大數(shù)量的數(shù)據(jù)，但是，如果我們不能提取與手頭工作相關(guān)的有用信息項(xiàng)，那么這樣的數(shù)據(jù)集就是無(wú)用的。在本章中，我們將研究數(shù)據(jù)庫(kù)系統(tǒng)，并弄清這些系統(tǒng)是怎樣利用抽象工具從龐大的數(shù)據(jù)集合中提取出有用的信息。作為相關(guān)主題，我們還要研究數(shù)據(jù)挖掘，即一個(gè)與數(shù)據(jù)庫(kù)技術(shù)密切相關(guān)的快速發(fā)展的領(lǐng)域，其目標(biāo)是發(fā)展在數(shù)據(jù)集上確定和尋找數(shù)據(jù)的模式。此外，我們還將學(xué)習(xí)傳統(tǒng)文件結(jié)構(gòu)的原理，因?yàn)樗瘟爽F(xiàn)在的數(shù)據(jù)庫(kù)和數(shù)據(jù)挖掘系統(tǒng)。第2頁(yè)，共28頁(yè)，2023年，2月20日，星期三9.1數(shù)據(jù)庫(kù)基礎(chǔ)

數(shù)據(jù)庫(kù)（database）是指一種多維的數(shù)據(jù)集合。傳統(tǒng)的文件系統(tǒng)，有時(shí)也稱(chēng)為平面文件（flatfile），是一種一維的存儲(chǔ)系統(tǒng)，因?yàn)樗粡囊环N觀點(diǎn)來(lái)展示信息。9.1.1數(shù)據(jù)庫(kù)的重要性管理層市場(chǎng)部客服部財(cái)務(wù)部采購(gòu)部人事部集成的數(shù)據(jù)庫(kù)第3頁(yè)，共28頁(yè)，2023年，2月20日，星期三9.1.2模式的作用

模式（schema）是整個(gè)數(shù)據(jù)庫(kù)結(jié)構(gòu)的一個(gè)描述，數(shù)據(jù)庫(kù)軟件用它來(lái)維護(hù)數(shù)據(jù)庫(kù)。子模式（subschema）只是與特定用戶(hù)需求相關(guān)的那部分?jǐn)?shù)據(jù)庫(kù)的一個(gè)描述。 例如：一個(gè)大學(xué)數(shù)據(jù)庫(kù)的模式應(yīng)當(dāng)說(shuō)明，每個(gè)學(xué)生記錄包含的條目除了學(xué)習(xí)成績(jī)外，還有現(xiàn)階段的聯(lián)系地址、電話(huà)，還要說(shuō)明每個(gè)學(xué)生的記錄要與其指導(dǎo)教師的記錄相鏈接。同樣，每個(gè)教師的記錄要包含個(gè)人地址、工作經(jīng)歷等。基于這樣一個(gè)模式，要維持一個(gè)鏈接系統(tǒng)，最終使得學(xué)生的信息與教師的工作經(jīng)歷相關(guān)聯(lián)。第4頁(yè)，共28頁(yè)，2023年，2月20日，星期三9.1.3數(shù)據(jù)庫(kù)管理系統(tǒng) 一個(gè)典型的數(shù)據(jù)庫(kù)應(yīng)用涉及多個(gè)軟件層，我們將其分組成兩個(gè)主要的層，即應(yīng)用層和數(shù)據(jù)庫(kù)管理層。 應(yīng)用軟件并不是直接操縱數(shù)據(jù)庫(kù)，對(duì)數(shù)據(jù)庫(kù)的實(shí)際操縱由數(shù)據(jù)庫(kù)管理系統(tǒng)（DBMS）的軟件層來(lái)完成。用戶(hù)應(yīng)用軟件層數(shù)據(jù)庫(kù)管理系統(tǒng)實(shí)際的數(shù)據(jù)庫(kù)第5頁(yè)，共28頁(yè)，2023年，2月20日，星期三 應(yīng)用軟件與DBMS分離有幾個(gè)好處。一個(gè)好處就是允許構(gòu)建和使用抽象工具。應(yīng)用軟件與DBMS分離的第二個(gè)好處就是，這樣的結(jié)構(gòu)提供了對(duì)數(shù)據(jù)庫(kù)訪(fǎng)問(wèn)進(jìn)行控制的一種手段。把用戶(hù)界面與實(shí)際數(shù)據(jù)庫(kù)操縱分離成兩個(gè)不同的軟件層，還有另一個(gè)原因，就是為了獲得數(shù)據(jù)獨(dú)立性（dataindependence），即改變數(shù)據(jù)庫(kù)組織本身而不改變應(yīng)用軟件的能力。第6頁(yè)，共28頁(yè)，2023年，2月20日，星期三9.1.4數(shù)據(jù)庫(kù)模型 數(shù)據(jù)庫(kù)的概念視圖就稱(chēng)之為數(shù)據(jù)庫(kù)模型（databasemodel）。 在關(guān)系數(shù)據(jù)庫(kù)模型的情況下，數(shù)據(jù)庫(kù)的概念視圖是一組由行和列組成的表格。例如，關(guān)于公司員工的信息可以看成這樣的一個(gè)表格，即每行表示一名員工，各列分別表示姓名、地址、員工代碼等。 第7頁(yè)，共28頁(yè)，2023年，2月20日，星期三學(xué)號(hào)Sno姓名Sname性別Ssex年齡Sage所在系Sdept95001李勇男20CS95002劉晨女19IS95003王敏女18MA95004張立男19IS第8頁(yè)，共28頁(yè)，2023年，2月20日，星期三課程號(hào)Cno課程名Cname先行課Cpno學(xué)分Credit1數(shù)據(jù)庫(kù)542數(shù)學(xué)23信息系統(tǒng)144操作系統(tǒng)635數(shù)據(jù)結(jié)構(gòu)746數(shù)據(jù)處理27PASCAL語(yǔ)言64第9頁(yè)，共28頁(yè)，2023年，2月20日，星期三學(xué)號(hào)Sno課程號(hào)Cno成績(jī)Grade9500119295001285950013889500229095002380第10頁(yè)，共28頁(yè)，2023年，2月20日，星期三9.2關(guān)系模型 關(guān)系數(shù)據(jù)庫(kù)模型用矩形表格存放數(shù)據(jù)，稱(chēng)之為關(guān)系（relation）。 關(guān)系中的一行稱(chēng)為一個(gè)元組（tuple），因?yàn)槊苛忻枋龅氖菍?duì)應(yīng)的元組所表示的實(shí)體的一些特征或?qū)傩?，所以關(guān)系中的列稱(chēng)為屬性（attribute）。9.2.1關(guān)系設(shè)計(jì)中的問(wèn)題 把一個(gè)關(guān)系分解成幾個(gè)比較小的關(guān)系時(shí)，信息不會(huì)丟失的分解稱(chēng)為無(wú)損分解（losslessdecomposition）。第11頁(yè)，共28頁(yè)，2023年，2月20日，星期三9.2.2關(guān)系運(yùn)算

SELECT運(yùn)算是從一個(gè)關(guān)系中提取行。 例如：NEW←SELECTfromEMPLOYEEwhereEmplid=“34Y70” 此語(yǔ)句的語(yǔ)義是：創(chuàng)建一個(gè)名為NEW的新關(guān)系，它包含從EMPLOYEE關(guān)系選得的其Emplid屬性等于34Y70的那些元組。第12頁(yè)，共28頁(yè)，2023年，2月20日，星期三

PROJECT運(yùn)算則是提取列。 例如：MAIL←PROJECTName，AdressfromEMPLOYEE 此語(yǔ)句的語(yǔ)義是：創(chuàng)建一個(gè)名為MAIL的新關(guān)系，它包含從EMPLOYEE關(guān)系選得的其屬性包含Name，Adress的兩列。 JOIN運(yùn)算用于連接關(guān)系數(shù)據(jù)庫(kù)。 例如：C←JOINAandBwhereA.W=B.X第13頁(yè)，共28頁(yè)，2023年，2月20日，星期三9.2.3SQL SQL（StructuredQueryLanguage）結(jié)構(gòu)化查詢(xún)語(yǔ)言。

1.select語(yǔ)句 每條SQL查詢(xún)語(yǔ)句可以包含3條字句，即select字句、from字句和where字句。 例如：selectName，AdressfromEMPlOYEE第14頁(yè)，共28頁(yè)，2023年，2月20日，星期三

2.insertinto語(yǔ)句 insertintoEMPLOYEE values（’42z12’，‘SueA.Burt’，’33FairSt.’，‘444661111’）

3.delete語(yǔ)句 deletefromEMPLOYEE whereName=‘G.JerrySmith’

4.update語(yǔ)句 updateEMPLOYEE setAddress=‘1812NapoleanAve.’ whereName=’JoeE.Baker‘第15頁(yè)，共28頁(yè)，2023年，2月20日，星期三9.3面向?qū)ο髷?shù)據(jù)庫(kù) 運(yùn)用面向?qū)ο蠓椒?gòu)建的數(shù)據(jù)庫(kù)稱(chēng)為面向?qū)ο髷?shù)據(jù)庫(kù)（object-orienteddatabase），它由對(duì)象構(gòu)成，對(duì)象之間通過(guò)相互鏈接來(lái)反映它們之間的聯(lián)系。 例如，書(shū)中員工數(shù)據(jù)庫(kù)的面向?qū)ο髮?shí)現(xiàn)可以包含3個(gè)類(lèi)（對(duì)象的類(lèi)型）：EMPLOYEE、JOB和ASSIGNMENT。EMPLOYEE類(lèi)的對(duì)象可以包含Emplid、Name、Address及SSNum這樣的一些屬性；JOB類(lèi)的對(duì)象可以包含JobID、JobTitle、SkillCode及Dept這些屬性；ASSIGNMENT類(lèi)的對(duì)象可以包含StartDate及TermDate這些屬性。第16頁(yè)，共28頁(yè)，2023年，2月20日，星期三EMPLOYEEASSIGNMENTASSIGNMENTASSIGNMENTJOBJOBJOB第17頁(yè)，共28頁(yè)，2023年，2月20日，星期三 在數(shù)據(jù)庫(kù)中創(chuàng)建或添加的對(duì)象，在創(chuàng)建它們的程序終止后必須保存。這樣的對(duì)象稱(chēng)為是持久的（persistent）對(duì)象。 面向?qū)ο髷?shù)據(jù)庫(kù)和關(guān)系數(shù)據(jù)庫(kù)相比： 1.面向?qū)ο蠓椒ㄊ拐麄€(gè)軟件系統(tǒng)用同樣的范型來(lái)設(shè)計(jì)。 2.面向?qū)ο髷?shù)據(jù)庫(kù)把不同的數(shù)據(jù)格式進(jìn)行封裝的能力。 3.面向?qū)ο笤O(shè)計(jì)方法對(duì)數(shù)據(jù)庫(kù)而言，還有一個(gè)好處，就是它有存儲(chǔ)智能對(duì)象的潛力而不僅僅只是數(shù)據(jù)。第18頁(yè)，共28頁(yè)，2023年，2月20日，星期三9.4維護(hù)數(shù)據(jù)庫(kù)的完整性9.4.1提交/回滾協(xié)議 把一個(gè)事務(wù)的所有步驟記錄進(jìn)日志文件的那個(gè)點(diǎn)，稱(chēng)為提交點(diǎn)（commitpoint）。 如果問(wèn)題出現(xiàn)在事務(wù)達(dá)到其提交點(diǎn)之前，那么DBMS可能會(huì)發(fā)現(xiàn)自己不能完成已經(jīng)執(zhí)行了一部分的事務(wù)。這種情況可以利用日志回滾（rollback）（也稱(chēng)為撤銷(xiāo)）實(shí)際上已被事務(wù)實(shí)施的活動(dòng)。第19頁(yè)，共28頁(yè)，2023年，2月20日，星期三 一個(gè)事務(wù)的回滾可能會(huì)影響到別的事務(wù)，造成這些事務(wù)也需要回滾，結(jié)果就產(chǎn)生了級(jí)聯(lián)回滾（cascadingrollback）。9.4.2鎖定 數(shù)據(jù)庫(kù)可能出現(xiàn)錯(cuò)誤決算問(wèn)題（incorrectsummaryproblem）和更新丟失問(wèn)題（lostupdateproblem）。

鎖定協(xié)議（lockingprotocol），該協(xié)議規(guī)定，數(shù)據(jù)庫(kù)中當(dāng)前正在被某個(gè)事務(wù)使用的項(xiàng)目都要加以標(biāo)記。第20頁(yè)，共28頁(yè)，2023年，2月20日，星期三 常見(jiàn)的有兩種類(lèi)型的鎖，及共享鎖（sharedlock）和排它鎖（exclusivelock），它們分別對(duì)應(yīng)于事務(wù)需要訪(fǎng)問(wèn)數(shù)據(jù)的兩種訪(fǎng)問(wèn)形式，及共享訪(fǎng)問(wèn)和互斥訪(fǎng)問(wèn)。 如果一個(gè)稍后的事務(wù)一直被搶占，那么隨著過(guò)程的進(jìn)展它也會(huì)變老，最終成為一個(gè)具有較高優(yōu)先級(jí)的老事務(wù)。這個(gè)協(xié)議，稱(chēng)之為受傷等待協(xié)議（wound-waitprotocol）。第21頁(yè)，共28頁(yè)，2023年，2月20日，星期三9.5傳統(tǒng)的文件結(jié)構(gòu)9.5.1順序文件

順序文件（sequentialfile），即它從頭到尾都是以順序的方式進(jìn)行訪(fǎng)問(wèn)的，好像文件中的信息都排成一行。 把順序文件的末尾稱(chēng)之為文件結(jié)束（end-of-file，EOF）。有許多方法可以用來(lái)標(biāo)識(shí)EOF，一種方法是在文件的末尾放置一個(gè)專(zhuān)用的標(biāo)記，稱(chēng)為哨兵（sentinel）。另一種方法是利用操作系統(tǒng)的目錄系統(tǒng)中的信息來(lái)確定一個(gè)文件的EOF。第22頁(yè)，共28頁(yè)，2023年，2月20日，星期三 歸并算法： procedureM二個(gè)Files（InputFileA，InputFileB，OutputFile） if（兩個(gè)輸入文件都處于EOF）then（停止，OutputFile為空） if（InputFileA，不在EOF）then（聲明它的第一個(gè)記錄為當(dāng)前記錄） if（InputFileB，不在EOF）then（聲明它的第一個(gè)記錄為當(dāng)前記錄） while（兩個(gè)輸入文件都不在EOF）do （將鍵字段值較小的當(dāng)前記錄放在OutputFile； if（該當(dāng)前記錄是其對(duì)應(yīng)輸入文件的最后一個(gè)記錄） then（聲明該輸入文件在EOF） else（聲明該輸入文件中的下一個(gè)記錄是該文件的當(dāng)前記錄） ） 從不在EOF的輸入文件的當(dāng)前記錄開(kāi)始復(fù)制其余記錄到OutputFile第23頁(yè)，共28頁(yè)，2023年，2月20日，星期三9.5.2索引文件 為文件建立一個(gè)索引用來(lái)定位邏輯記錄的位置，這樣的文件系統(tǒng)稱(chēng)之為索引文件（indexedfile）。9.5.3散列文件

散列（hashing）技術(shù)也能提供較快的訪(fǎng)問(wèn)機(jī)制。 散列系統(tǒng)可以概括如下：數(shù)據(jù)存儲(chǔ)空間被分成幾個(gè)區(qū)，稱(chēng)為存儲(chǔ)桶（bucket），每個(gè)桶放幾條記錄。根據(jù)一個(gè)將鍵的值轉(zhuǎn)換為桶號(hào)的算法，可以將記錄分散存放于這些桶中。這里，將鍵的值轉(zhuǎn)換為桶號(hào)的算法稱(chēng)為散列函數(shù)（hashingfunction）。第24頁(yè)，共28頁(yè)，2023年，2月20日，星期三 當(dāng)散列用在海量存儲(chǔ)器中的存儲(chǔ)結(jié)構(gòu)時(shí)，其結(jié)果稱(chēng)為散列文件（hashfile）。當(dāng)散列用在主存中的存儲(chǔ)結(jié)構(gòu)時(shí)，其結(jié)果通常稱(chēng)為散列表（hashtable）。 如果發(fā)生一個(gè)不成比例的鍵數(shù)目恰巧散列到同一個(gè)桶里，這種現(xiàn)象稱(chēng)為群集（clustering）。兩個(gè)鍵經(jīng)過(guò)散列后得到同一個(gè)值，這個(gè)現(xiàn)象被稱(chēng)為碰撞（collision）。 前8條記錄都被放進(jìn)空桶的概率為： （41/41）（40/41）……（34/41）=0.482第25頁(yè)，共28頁(yè)，2023年，2月20日，星期三 碰撞或者溢出的解決方法：一是允許擴(kuò)展桶的大小，二是允許桶溢出到一個(gè)專(zhuān)門(mén)為解決這種問(wèn)題二保留的溢出區(qū)。 記錄的數(shù)目與文件中總的記錄容量之比稱(chēng)為負(fù)載因子（loadfactor）。 例如：14,34,7,6,9,21,44,27,，散列函數(shù)Xmod11,在來(lái)數(shù)據(jù)32。01234567891044,3414276792132第26頁(yè)，共28頁(yè)，2023年，2月20日，星期三9.6數(shù)據(jù)挖掘 數(shù)據(jù)挖掘操作的是靜態(tài)的數(shù)據(jù)集合，稱(chēng)為數(shù)據(jù)倉(cāng)庫(kù)（datawarehouse）。 數(shù)據(jù)挖掘有兩種常見(jiàn)的形式：類(lèi)型描述（classdescription）和類(lèi)型識(shí)別（classdiscr