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

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

數(shù)據(jù)庫（database）是指一種多維的數(shù)據(jù)集合。傳統(tǒng)的文件系統(tǒng)，有時也稱為平面文件（flatfile），是一種一維的存儲系統(tǒng)，因為它只從一種觀點來展示信息。9.1.1數(shù)據(jù)庫的重要性管理層市場部客服部財務(wù)部采購部人事部集成的數(shù)據(jù)庫第三頁，共二十八頁，2022年，8月28日9.1.2模式的作用

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

SELECT運算是從一個關(guān)系中提取行。 例如：NEW←SELECTfromEMPLOYEEwhereEmplid=“34Y70” 此語句的語義是：創(chuàng)建一個名為NEW的新關(guān)系，它包含從EMPLOYEE關(guān)系選得的其Emplid屬性等于34Y70的那些元組。第十二頁，共二十八頁，2022年，8月28日

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

1.select語句 每條SQL查詢語句可以包含3條字句，即select字句、from字句和where字句。 例如：selectName，AdressfromEMPlOYEE第十四頁，共二十八頁，2022年，8月28日

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

3.delete語句 deletefromEMPLOYEE whereName=‘G.JerrySmith’

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

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

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

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