全國(guó)計(jì)算機(jī)等級(jí)考試三級(jí)數(shù)據(jù)庫背誦資料

三級(jí)數(shù)據(jù)庫背誦資料

第一章計(jì)算機(jī)基礎(chǔ)知識(shí)

1、馮?諾依曼計(jì)算機(jī)以“存儲(chǔ)程序”原理為基礎(chǔ)，由運(yùn)算器、存儲(chǔ)器、控制器、輸入設(shè)備

和輸出設(shè)備等五大部件組成。

2、計(jì)算機(jī)指令系統(tǒng)：

系列計(jì)算機(jī)：指令系統(tǒng)向下兼容。

復(fù)雜指令系統(tǒng)計(jì)算機(jī)：CISC(ComplexInstructionSetComputer)

精簡(jiǎn)指令系統(tǒng)計(jì)算機(jī)：RISC(ReducedInstructionSetComputer)

指令系統(tǒng)的類型：數(shù)據(jù)傳送類指令、算術(shù)邏輯類指令和判定控制類指令。

指令系統(tǒng)的尋址方式：立即尋址(立即數(shù)尋址)，指令中直接給出操作數(shù)。

寄存器尋址：操作數(shù)在寄存器中。直接尋址：指令中直接給出操作數(shù)地址。寄存器間接尋

址：寄存器給出操作數(shù)地址。

寄存器相對(duì)尋址：指令中給出操作數(shù)的地址偏移量

3、微型處理器分類：通用微處理器、嵌入式微處理器和數(shù)字信號(hào)處理器等

4、總線：

PCI：不依附具體處理器的局部總線。

USB：通用串行總線。

1394總線：FireWire,為家用電器研制的一種高速串行總線。1394總線在數(shù)字視頻設(shè)備(數(shù)

字?jǐn)z像機(jī))中廣泛應(yīng)用。

5、計(jì)算機(jī)的技術(shù)指標(biāo)：

運(yùn)算速度MIPS(每秒百萬條指令)

影響計(jì)算機(jī)運(yùn)算速度的因素很多，主要是CPU的主頻和存儲(chǔ)器的存取周期。

存儲(chǔ)器容量：基本單位B(Byte)lKB=1024Byte1MB=1024KB1GB=1024MB

1TB=1024GB

數(shù)據(jù)傳輸率：基本單位bps（每秒傳輸多少位）lKbps=103bpslMbps=103Kbps

lGbps=103Mbps

6、計(jì)算機(jī)中的信息表示

非數(shù)字信息的表示：ASCII碼漢字的表示：三類代碼體系：輸入碼，如：拼音碼、五

筆字形碼等；機(jī)內(nèi)碼；交換碼，如GB2312-80；

7、計(jì)算機(jī)網(wǎng)絡(luò)基礎(chǔ)

計(jì)算機(jī)網(wǎng)絡(luò)的基本特征：資源共享。廣域網(wǎng)與廣域網(wǎng)的互聯(lián)是通過路由器實(shí)現(xiàn)的。

傳輸技術(shù)分為：廣播式網(wǎng)絡(luò)（通過一條公共信道實(shí)現(xiàn)）點(diǎn)-點(diǎn)式網(wǎng)絡(luò)（通過存儲(chǔ)轉(zhuǎn)發(fā)實(shí)

現(xiàn)）。采用分組存儲(chǔ)轉(zhuǎn)發(fā)與路由選擇是點(diǎn)-點(diǎn)式網(wǎng)絡(luò)與廣播網(wǎng)絡(luò)的重要區(qū)別之一

按規(guī)模分類：局域網(wǎng)（LAN）、城域網(wǎng)（MAN）、廣域網(wǎng)（WAN）

廣域網(wǎng)（遠(yuǎn)程網(wǎng)）以下特點(diǎn)：1適應(yīng)大容量與突發(fā)性通信的要求。2適應(yīng)綜合業(yè)務(wù)服

務(wù)的要求。3開放的設(shè)備接口與規(guī)范化的協(xié)議。4完善的通信服務(wù)與網(wǎng)絡(luò)管理。

幾種常見的廣域網(wǎng)的特點(diǎn)：

X.25：建立在速率低、誤碼率高的電纜介質(zhì)上，X.25協(xié)議包括差錯(cuò)控制、流量控制和

擁塞控制等，由通信子網(wǎng)完成,有時(shí)間延遲。

FR（幀中繼）：建立在速率高、誤碼率低的光纖上，對(duì)X.25協(xié)議進(jìn)行簡(jiǎn)化，差錯(cuò)控

制由用戶終端完成。

B-ISDN（寬帶綜合業(yè)務(wù)數(shù)字網(wǎng)）、N-ISDN（窄帶綜合業(yè)務(wù)數(shù)字網(wǎng)）

ATM（異步傳輸模式，一種數(shù)據(jù)傳輸與分組交換技術(shù)，能滿足多媒體應(yīng)用的高速率

與低延遲的要求，具有線路交換實(shí)時(shí)性好和分組交換靈活性好的雙重優(yōu)點(diǎn)。

各種城域網(wǎng)建設(shè)方案有幾個(gè)相同點(diǎn)：傳輸介質(zhì)采用光纖，交換接點(diǎn)采用基于IP交換的

高速路由交換機(jī)或ATM交換機(jī)，在體系結(jié)構(gòu)上采用核心交換層，業(yè)務(wù)匯聚層與接入層三

層模式。城域網(wǎng)MAN介于廣域網(wǎng)與局域網(wǎng)之間的一種高速網(wǎng)絡(luò)。

8、網(wǎng)絡(luò)協(xié)議為三部分：（1）語法，即用戶數(shù)據(jù)與控制信息的結(jié)構(gòu)和格式；⑵語義,即需要

發(fā)出何種控制信息，以及完成的動(dòng)作與做出的響應(yīng);（3）時(shí)序，即對(duì)事件實(shí)現(xiàn)順序的詳細(xì)說明.

9>Internet的結(jié)構(gòu)和組成

協(xié)議：TCP/IP協(xié)議組

TCP/IP參考模型可以分為：應(yīng)用層，傳輸層（TCP、UDP協(xié)議），互連層（IP協(xié)議），主

機(jī)-網(wǎng)絡(luò)層

應(yīng)用層協(xié)議分為：

a、依賴于面向連接的TCP協(xié)議：主要有：文件傳送協(xié)議FTP、電子郵件協(xié)議SMTP

以及超文本傳輸協(xié)議HTTP等。

b、依賴于面向連接的UDP協(xié)議：主要有簡(jiǎn)單網(wǎng)絡(luò)管理協(xié)議SNMP;簡(jiǎn)單文件傳輸協(xié)

議TFTPo

c、既依賴于TCP協(xié)議，也可以依賴于UDP協(xié)議：域名服務(wù)DNS等。

d、網(wǎng)絡(luò)終端協(xié)議：Telnet；網(wǎng)絡(luò)文件系統(tǒng)NFS；路由信息協(xié)議RIP。

10、域名與IP地址：IP地址由網(wǎng)絡(luò)地址和機(jī)器地址組成：IP地址長(zhǎng)度為32位，X.X.X.X

表示，X為8為，表示0-255,（點(diǎn)分十進(jìn)制地址）。主要分為A類（網(wǎng)絡(luò)地址7位，機(jī)器地

址24位）、B類（網(wǎng)絡(luò)地址14位，機(jī)器地址16位）、C類（網(wǎng)絡(luò)地址21位，機(jī)器地址8

位）；域名格式主機(jī)名.組名.網(wǎng)點(diǎn)名

IkInternet提供的服務(wù)

（1）WWW服務(wù)：采用客戶機(jī)/服務(wù)器模式a、超文本和超媒體是WWW的信息組織形

式

b、HTML（超文本標(biāo)記語言，網(wǎng)頁語言）和HTTP（超文本傳輸協(xié)議）是WWW工作的基礎(chǔ)

c、URL（統(tǒng)一資源定位器）：查找主頁。由三部分組成：協(xié)議類型，主機(jī)名和文件名及路

徑

比如:http：///index.htm,其中http為協(xié)議類型，為主機(jī)名,

index.htm為文件名及路徑

（2）電子郵件服務(wù)：

電子郵件發(fā)送接收協(xié)議：發(fā)送協(xié)議，簡(jiǎn)單郵件傳送協(xié)議（SMTP）,接收協(xié)議，可以使

用郵局協(xié)議（POP3）和交互式郵件存取協(xié)議（InteractiveMailAccessProtocol,IMAP）

電子郵件內(nèi)容協(xié)議MIME（MultipurposeInternetMailExtensions）,可以傳送圖像、聲

音等多媒體信息

12、Internet的接入：ISP（InternetServiceProvider,ISP）Internet服務(wù)提供商

局部網(wǎng)接入、電話線接入

ADSL（AsymmetricalDigitalSubscriberLoop）非對(duì)稱數(shù)字用戶環(huán)路，基于電話線，上、下行

傳輸速率不同，上行可達(dá)1Mbps；下行可達(dá)8Mbps。

13信息安全基礎(chǔ)

信息安全包括四方面內(nèi)容：信息保密、完整性、可用性、可控性

（1）密碼體制：加密或密碼體制由5部分組成：明文空間（明文的集合）、密文空間（密

文集合）、加密密鑰空間、解密密鑰空間、加密和解密算法集

單鑰加密體制分為兩類：流密碼（明文逐位加密）和分組密碼（明文分組，逐組加密）。

密鑰的分配和存儲(chǔ)是最關(guān)鍵和困難的問題。

（2）信息認(rèn)證

有關(guān)認(rèn)證的實(shí)用技術(shù)中，主要的有數(shù)字簽名技術(shù)、身份識(shí)別技術(shù)和信息的完整性校驗(yàn)技

術(shù)（消息認(rèn)證）

（3）惡意軟件：特洛依木馬、登錄陷阱（網(wǎng)絡(luò)釣魚，虛假頁面）、邏輯炸彈（在程序中

設(shè)置的破環(huán)代碼）

后門陷阱（在程序中設(shè)置的繞開登錄進(jìn)入系統(tǒng)）、緩沖區(qū)溢出、僵尸網(wǎng)絡(luò)：一對(duì)多進(jìn)

行控制

網(wǎng)絡(luò)防病毒軟件：允許用戶設(shè)置3中掃描方式：實(shí)時(shí)掃描、預(yù)置掃描、人工掃描

（4）網(wǎng)絡(luò)安全

網(wǎng)絡(luò)安全服務(wù)的主要內(nèi)容：安全攻擊、安全機(jī)制、安全服務(wù)

網(wǎng)絡(luò)服務(wù)攻擊分類：服務(wù)攻擊和非服務(wù)攻擊

服務(wù)攻擊：對(duì)服務(wù)器發(fā)起攻擊，喪失服務(wù)能力，比如對(duì)WWW服務(wù)器攻擊，主頁

被篡改。拒絕服務(wù)DoS或DdoS分布式拒絕服務(wù)。

非服務(wù)攻擊：對(duì)通信設(shè)備攻擊，使設(shè)備癱瘓

網(wǎng)絡(luò)信息攻擊：攻擊類型：截獲、竊聽、篡改和偽造等

14、操作系統(tǒng)安全

操作系統(tǒng)的安全措施一般可以從隔離、分層和內(nèi)控3個(gè)方面來進(jìn)行考慮。

隔離可分為：（注意后面的解釋）

①物理隔離：使不同安全要求的進(jìn)程使用不同物理實(shí)體。

②時(shí)間隔離：使不同進(jìn)程在不同時(shí)間運(yùn)行。

③邏輯隔離：限制程序存取。

④密碼隔離：進(jìn)程以其他進(jìn)程不知的方式隱蔽數(shù)據(jù)和計(jì)算。

操作系統(tǒng)安全措施：訪問控制、存儲(chǔ)保護(hù)及文件保護(hù)與保密。

訪問控制：認(rèn)證、訪問權(quán)限、文件保護(hù)、審計(jì)。存儲(chǔ)保護(hù)：防止地址越界、防止操作越權(quán)。

第二章數(shù)據(jù)結(jié)構(gòu)算法

1、數(shù)據(jù)：數(shù)據(jù)的基本單位是數(shù)據(jù)元素。數(shù)據(jù)元素可由一個(gè)或多個(gè)數(shù)據(jù)項(xiàng)組成。數(shù)據(jù)項(xiàng)是

數(shù)據(jù)的不可分割的最小單位

2、數(shù)據(jù)結(jié)構(gòu)：數(shù)據(jù)的邏輯結(jié)構(gòu)、數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)、數(shù)據(jù)的運(yùn)算

3、主要的數(shù)據(jù)存儲(chǔ)方式：順序存儲(chǔ)結(jié)構(gòu)（邏輯和物理相鄰，存儲(chǔ)密度大）和鏈?zhǔn)酱鎯?chǔ)結(jié)

構(gòu)

順序存儲(chǔ)結(jié)構(gòu)：

順序存儲(chǔ)計(jì)算公式Li=L0+（i-l）XK順序結(jié)構(gòu)可以進(jìn)行隨機(jī)存取；插人、刪除運(yùn)

算會(huì)引起相應(yīng)節(jié)點(diǎn)的大量移動(dòng)

鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)：a、指針域可以有多個(gè)，可以指向空，比比順序存儲(chǔ)結(jié)構(gòu)的存儲(chǔ)密度

小

b、邏輯上相鄰的節(jié)點(diǎn)物理上不一定相鄰。c、插人、刪除等不需要

大量移動(dòng)節(jié)點(diǎn)

4、順序表：一般情況下，若長(zhǎng)度為n的順序表，在任何位置插入或刪除的概率相等，元

素移動(dòng)的平均次數(shù)為n/2(插入)和(n-l)/2(刪除)。

5、鏈表：■鏈表和雙向鏈表等等)和非線性鏈表

■B■稱為單鏈表，其每個(gè)-節(jié)點(diǎn)中只包含-個(gè)指針域，雙鏈表中，每個(gè)節(jié)點(diǎn)中設(shè)置

有兩個(gè)指針域。(注意結(jié)點(diǎn)的插入和刪除操作)

6、棧：“后進(jìn)先出"(LIFO)表。棧的應(yīng)用：表達(dá)式求解、二叉樹對(duì)稱序周游、快速排序算

法、遞歸過程的實(shí)現(xiàn)等

7、隊(duì)列：“先進(jìn)先出”線性表。應(yīng)用：樹的層次遍歷

8、串：由零個(gè)或多個(gè)字符組成的有限序列。

9、多維數(shù)組的順序存儲(chǔ)：

(1)行優(yōu)先順序下

LOC(atf)=LOC(an)+((i-1)xn+(y-l))xA

(2)列優(yōu)先腰序下

LOC(ay)=LOC(atl)+((7-1)xm+(j-1))xA

式中，。和m分別為數(shù)組每行和每列的元素個(gè)數(shù),A為每個(gè)數(shù)組元素占用的存儲(chǔ)單元個(gè)數(shù)。

10、稀疏矩陣的存儲(chǔ)：下三角矩陣順序存儲(chǔ)

LOC(aw)=LOC(a?)++(；-l)jxA,1WiW/Wn

其他常見的存儲(chǔ)方法還有三元組法和十字鏈表法

11、廣義表：由零個(gè)或多個(gè)單元素或子表所組成的有限序列。廣義表的元素可以是子表，

而子表的元素還可以是子表

12、樹型結(jié)構(gòu)：非線性結(jié)構(gòu)。常用的樹型結(jié)構(gòu)有樹和二叉樹。

二叉樹與樹的區(qū)別：二叉樹不是樹的特殊情況，樹和二叉樹之間最主要的區(qū)別是：二

叉樹的節(jié)點(diǎn)的子樹要區(qū)分左子樹和右子樹，即使在節(jié)點(diǎn)只有一棵子樹的情況下也要明確指

出該子樹是左子樹還是右子樹。

13、樹（森林）與二叉樹之間的轉(zhuǎn)換（要會(huì)轉(zhuǎn)換）

14、二叉樹和樹的周游（遍歷）

二叉樹的周游主要有以下3種方式：前序法（NLR）、對(duì)稱序法（LNR）、后序法（LRN）

周游樹和樹林：深度優(yōu)先和按廣度優(yōu)先兩種方式進(jìn)行。深度優(yōu)先方式又可分為按先根

次序和按后根次序周游

樹與二叉樹周游之間的對(duì)應(yīng)關(guān)系：按先根次序周游樹正好與按前序法周游樹對(duì)應(yīng)的二

叉樹等同，后根次序周游樹正好與按對(duì)稱序法周游對(duì)應(yīng)的二叉樹等同

按廣度優(yōu)先方式就是層次次序周游

15、二叉樹的存儲(chǔ)和線索

二叉樹的存儲(chǔ)結(jié)構(gòu)：二叉樹的Hink—rlink法存儲(chǔ)表示

線索二叉樹：在有n個(gè)節(jié)點(diǎn)的二叉樹的且Hink-rlink法存儲(chǔ)表示中，必定有n+1個(gè)空

指針域

16、哈夫曼樹：一類帶權(quán)路徑長(zhǎng)度最短的樹。樹的帶權(quán)路徑長(zhǎng)度為樹中所有葉子節(jié)點(diǎn)的帶

權(quán)路徑長(zhǎng)度之和WPLo

17、查找：

（1）順序查找：平均查找長(zhǎng)度為（n+1）/2次，時(shí)間復(fù)雜度為O（n）

（2）二分法查找：線性表節(jié)點(diǎn)必須按關(guān)鍵碼值排序，且線性表是以順序存儲(chǔ)方式存儲(chǔ)

的。查找成功比較次數(shù)log2n,查找失敗比較次數(shù)log2n+l

（3）分塊查找：先是塊間查找，然后塊內(nèi)查找。

（4）散列表（哈希表Hash）的存儲(chǔ)和查找：處理沖突的方法：開地址法（線性探測(cè)

法）、拉鏈法等

負(fù)載因子（裝填因子戶表實(shí)際存儲(chǔ)的結(jié)點(diǎn)個(gè)數(shù)/表的最大能存儲(chǔ)結(jié)點(diǎn)個(gè)數(shù)（即表長(zhǎng)）

二叉排序樹：每個(gè)結(jié)點(diǎn)左子樹的所有關(guān)鍵碼值都小于該結(jié)點(diǎn)關(guān)鍵碼值，右子樹所有結(jié)

點(diǎn)關(guān)鍵碼值都大于該結(jié)點(diǎn)關(guān)鍵碼值。對(duì)稱周游二叉排序樹，得到一個(gè)有序序列，時(shí)間復(fù)雜

度O(log2n)

B樹和B+樹：M階樹，每個(gè)結(jié)點(diǎn)至多有M-1個(gè)關(guān)鍵碼，至少有M/2(取上界)-1個(gè)關(guān)鍵

碼。B樹適合隨機(jī)查找，不適合順序查找。B+樹適合順序查找。

18、排序

直接插入排序、希爾排序、直接選擇排序、堆排序、起泡排序、快速排序等排序算法

要了解。

?2.1常用排序方法性臉比較表

方法平均時(shí)間垃壞情況時(shí)間輔助存儲(chǔ)

起泡排序、摘單選擇排序、

0(ns)0(?1)0(1)

桶人排序(除shell排序)

快速排序O(nlog3n)0(J)0(,n)og2n)

堆排呼O(nlog2n)0(nlog3n)0(1)

歸并排序0(nlog2n)-

直接選擇排序、希爾排序、快速排序和堆排序是不穩(wěn)定排序，其他排序?yàn)榉€(wěn)定排序

第三章操作系統(tǒng)

1、操作系統(tǒng)概念：一是管理系統(tǒng)中的各種資源；二是給用戶提供一個(gè)友好的界面。

2、操作系統(tǒng)包括以下3個(gè)基本特征：并發(fā)性、共享性、隨機(jī)性。

3、功能：進(jìn)程管理、存儲(chǔ)管理、作業(yè)管理、文件管理、設(shè)備管理

4、操作系統(tǒng)類型

(1)批處理操作系統(tǒng)：成批、多道，交互性不強(qiáng)。系統(tǒng)目標(biāo)：提高資源利用率、作業(yè)

吞吐量和作業(yè)流程自動(dòng)化。

(2)分時(shí)操作系統(tǒng)：多路、交互性、獨(dú)立性、及時(shí)性

(3)實(shí)時(shí)系統(tǒng)(實(shí)時(shí)控制、實(shí)時(shí)信息處理)：及時(shí)、可靠

(4)嵌入式操作系統(tǒng)：高可靠性、實(shí)時(shí)性、占資源少、智能化、易連接、低成本等。

5、操作系統(tǒng)與用戶的接口：程序級(jí)接口：系統(tǒng)調(diào)用命令組成。操作級(jí)接口：提供操作

命令

6、操作系統(tǒng)的硬件環(huán)境（CPU、存儲(chǔ)體系、中斷系統(tǒng)、I/O控制和時(shí)鐘）

（1）CPU：CPU狀態(tài)：管態(tài)（CPU執(zhí)行操作系統(tǒng)程序）和目態(tài)（CPU執(zhí)行用戶程序）

目態(tài)到管態(tài)的轉(zhuǎn)變的唯一途徑是中斷，通過修改程序狀態(tài)字實(shí)現(xiàn)管態(tài)和目態(tài)的轉(zhuǎn)

換

（2）中斷機(jī)制：

中斷的實(shí)現(xiàn)需要硬件和軟件結(jié)合完成。中斷類型：強(qiáng)迫性中斷和自愿性中斷。

強(qiáng)迫性中斷：不期望或不可預(yù)料的中斷.如：輸入輸出中斷、硬件故障中斷、時(shí)

鐘中斷、程序性中斷。

自愿性中斷：程序有意安排的訪管指令或系統(tǒng)調(diào)用。

中斷向量：中斷處理程序的入口地址及運(yùn)行環(huán)境（程序狀態(tài)字PSW）

中斷優(yōu)先級(jí)由硬件規(guī)定，中斷屏蔽由程序狀態(tài)字的中斷屏蔽位決定。通過中斷

屏蔽可以調(diào)整中斷事件的響應(yīng)次序

（3）定時(shí)裝置：定時(shí)裝置硬件時(shí)鐘通常分為兩類：即絕對(duì)時(shí)鐘和相對(duì)時(shí)鐘。

CPU對(duì)外部設(shè)備的控制方式：

1、循環(huán)測(cè)試I/O2、中斷3、DMA（直接內(nèi)存存取）：高速外設(shè)與內(nèi)存批量處理數(shù)據(jù)4、

通道處理（I/O處理機(jī)）

7、進(jìn)程管理

（1）進(jìn)程與程序的區(qū)別與聯(lián)系：a.進(jìn)程是程序的執(zhí)行，是動(dòng)態(tài)的；而程序是指令的

集合，是靜態(tài)的。

b.進(jìn)程有生命周期，即進(jìn)程的存在是有限的，從運(yùn)行到結(jié)束，是暫時(shí)的；而程序

則是永久存在的。

c.進(jìn)程包括程序、數(shù)據(jù)和進(jìn)程控制塊（PCB）。

d.一個(gè)程序可以有多個(gè)進(jìn)程，一個(gè)進(jìn)程也可以包含多個(gè)程序。

進(jìn)程控制塊PCB是一個(gè)數(shù)據(jù)結(jié)構(gòu)，進(jìn)程在內(nèi)存中存在的唯一標(biāo)志

（2）進(jìn)程狀態(tài)：運(yùn)行態(tài)，就緒態(tài)，等待狀態(tài)（阻塞狀態(tài)）

（3）線程：CPU調(diào)度和分派的基本單位。共享進(jìn)程資源。

（4）進(jìn)程的通信

臨界資源是指一次只允許一個(gè)進(jìn)程使用的資源：一個(gè)進(jìn)程中訪問臨界資源的那段

程序代碼稱為臨界區(qū)。它們不允許兩個(gè)及以上的進(jìn)程同時(shí)訪問或修改。

進(jìn)程同步：多個(gè)進(jìn)程協(xié)同完成任務(wù)。進(jìn)程互斥：多個(gè)進(jìn)程使用同一資源（臨界資

源）。

低級(jí)通信：少量信息的交換（P操作和V操作）

高級(jí)通信：大信息交換（消息機(jī)制（消息緩沖、信箱通信）、共享內(nèi)存，管道）

進(jìn)程（線程）調(diào)度：先來先服務(wù)、時(shí)間片輪轉(zhuǎn)、最高優(yōu)先級(jí)（緊迫度高的進(jìn)程）、

多級(jí)隊(duì)列反饋算法：綜合了FCFS、時(shí)間片輪轉(zhuǎn)和可搶占最高優(yōu)先數(shù)算法。

（5）死鎖:

產(chǎn)生死鎖的必要條件：互斥條件、不可剝奪條件、部分分配、循環(huán)等待

死鎖的預(yù)防：破環(huán)必要條件之一：靜態(tài)預(yù)分配（破壞部分分配）、資源有序分配（破

壞環(huán)路等待）、可剝奪資源（破壞不可剝奪性）

死鎖的避免：銀行家算法

死鎖的檢測(cè)：進(jìn)程等待時(shí)檢測(cè)、定時(shí)檢測(cè)、系統(tǒng)利用率降低時(shí)檢測(cè)

死鎖的解除：資源剝奪和撤銷進(jìn)程

8、存儲(chǔ)管理

（1）功能：內(nèi)存的分配和回收、內(nèi)存共享、存儲(chǔ)保護(hù)（防止地址越界和操作越權(quán)）、

地址映射（地址重定位）

內(nèi)存擴(kuò)充：讓外存當(dāng)作內(nèi)存來使用

（2）碎片管理：解決碎片的方法是移動(dòng)技術(shù)或緊湊（拼接）技術(shù)

（3）靜態(tài)地址重定位：程序裝入內(nèi)存時(shí)，進(jìn)行邏輯地址轉(zhuǎn)換物理地址轉(zhuǎn)換

動(dòng)態(tài)地址重地位：程序運(yùn)行過程中，要訪問指令和數(shù)據(jù)才進(jìn)行地址轉(zhuǎn)換，需要

硬件地址映射機(jī)制（基址寄存器和限長(zhǎng)寄存器）

（4）空閑分區(qū)的分配策略：最先適應(yīng)算法（地址從小到大找第一個(gè)滿足進(jìn)程空間大小

的分區(qū)）

最佳適應(yīng)算法：分區(qū)表按容量從小到排序；最壞適應(yīng)算法：分區(qū)按容量從大到小排

序。

（5）虛擬存儲(chǔ)管理：虛擬存儲(chǔ)得以實(shí)現(xiàn)是由程序的局部性原理來決定的。程序的局部

性原理包括時(shí)間局部性和空間局部

（6）頁面淘汰算法包括以下幾種：最佳淘汰算法（OPT）、先進(jìn)先出淘汰算法（FIFO）、

最近最久末使用淘汰算法（LRU）

最近使用最少淘汰算法（LFU）（訪問次數(shù)少）

（7）影響缺頁中斷次數(shù)因素：a、分配給進(jìn)程的物理頁面數(shù)b.頁面大小c.程序本

身的編制方法

c、頁面淘汰算法：最佳淘汰算法（OPT）能使缺頁中斷率最低

（8）顛簸（抖動(dòng)）：缺頁率高引起。工作集模型解決顛簸（抖動(dòng)）

9、文件管理

（1）邏輯結(jié)構(gòu)：流式文件（基本單位字符）（如：源程序文件、目標(biāo)代碼文件，Unix

的文件）和記錄文件（定長(zhǎng)和不定長(zhǎng)記錄），記錄包含一個(gè)記錄鍵和其他屬性

（2）文件的物理結(jié)構(gòu)：連續(xù)結(jié)鉤、鏈接結(jié)構(gòu)、索引結(jié)構(gòu)及Hash結(jié)構(gòu)等，文件的存取

方式與物理結(jié)構(gòu)有關(guān)。

UNIX三級(jí)索引表的計(jì)算：如果一個(gè)物理塊可以存放256個(gè)塊號(hào)，則三級(jí)索引表表示

文件的大小2563+2562+256+10

（3）文件目錄：文件系統(tǒng)的最大特點(diǎn)就是“按名”存取

（4）文件控制塊FCB是文件在內(nèi)存中存在的唯一標(biāo)志，文件目錄是文件控制塊的有

序集合。

（5）多級(jí)目錄結(jié)構(gòu)，有利于避免文件重名；當(dāng)前目錄：可以提高檢索速度。目錄項(xiàng)分

解法，它可以提高文件檢索速度

（6）記錄的成組：若干個(gè)邏輯記錄合成在一個(gè)物理塊中，每個(gè)塊中的邏輯記錄個(gè)數(shù)為

塊因子。

10、設(shè)備管理

（1）按設(shè)備的工作特性可以分為存儲(chǔ)設(shè)備和輸人/輸出設(shè)備兩種

（2）按照資源分配方式可以分為獨(dú)享設(shè)備、共享設(shè)備和虛擬設(shè)備3種

虛設(shè)備技術(shù)，一類設(shè)備模擬另一類設(shè)備的技術(shù)。在高速設(shè)備（如高速大容量磁盤）

上模擬低速設(shè)備：SPOOLING是典型的虛設(shè)備技術(shù)，被模擬的設(shè)備稱為虛擬設(shè)備。

（3）按設(shè)備的數(shù)據(jù)組織分類：塊設(shè)備（磁盤、磁帶）和字符設(shè)備（打印機(jī)）。

（4）通道可以分為以下3種類型：字節(jié)多路通道、選擇通道和成組多路通道。

（5）單緩沖區(qū)，雙緩沖區(qū)，多緩沖區(qū)和緩沖池：解決外設(shè)與CPU速度不匹配問題

（6）磁盤調(diào)度：訪問磁盤時(shí)間：尋道時(shí)間、旋轉(zhuǎn)定位時(shí)間和數(shù)據(jù)傳輸時(shí)間。

磁盤調(diào)度由移臂調(diào)度和旋轉(zhuǎn)調(diào)度組成。移臂調(diào)度：先來先服務(wù)FCFS（大幅度移動(dòng)）、

最短尋道時(shí)間優(yōu)先（饑餓，考慮了尋道優(yōu)化），掃描算法（考慮方向和距離，考慮了

尋道優(yōu)化）

旋轉(zhuǎn)調(diào)度：目的較少旋轉(zhuǎn)延遲時(shí)間。

第四章數(shù)據(jù)庫系統(tǒng)技術(shù)基礎(chǔ)

1、信息與數(shù)據(jù)的關(guān)系：數(shù)據(jù)是信息的符號(hào)表示，或稱載體；信息是數(shù)據(jù)的內(nèi)涵，是數(shù)據(jù)

的語義解釋

2、數(shù)據(jù)庫系統(tǒng)：一般由數(shù)據(jù)庫、操作系統(tǒng)、數(shù)據(jù)庫管理系統(tǒng)（及其工具）、應(yīng)用系統(tǒng)、數(shù)

據(jù)庫管理人員和用戶構(gòu)成。

3、數(shù)據(jù)模型：數(shù)據(jù)模型是數(shù)據(jù)庫系統(tǒng)的數(shù)學(xué)形式框架，是數(shù)據(jù)庫系統(tǒng)的核心和基礎(chǔ).

4、數(shù)據(jù)模型的分類：概念模型，也稱信息模型；邏輯模型，主要包括網(wǎng)狀模型、層次模

型和關(guān)系模型等；物理模型。

5、數(shù)據(jù)模型的三要素：數(shù)據(jù)結(jié)構(gòu)、數(shù)據(jù)操作和完整性約束。

6、概念模型，信息世界建模，E-R模型是常用的概念模型。EER擴(kuò)充E-R模型，面向?qū)?/p>

象模型、謂詞模型。

E-R圖提供了表示實(shí)體型、屬性和聯(lián)系的方法。

(1)實(shí)體型：用矩形表示，矩形框內(nèi)寫明實(shí)體名。

(2)屬性：用橢圓形表示，并用無向邊將其與相應(yīng)的實(shí)體連接起來。

(3)聯(lián)系：用菱形表示，菱形框內(nèi)寫明聯(lián)系名，并用無向邊分別與有關(guān)實(shí)體連接起來,

同時(shí)在無向邊旁標(biāo)上聯(lián)系的類型

7、邏輯模型，面向數(shù)據(jù)庫管理系統(tǒng)。傳統(tǒng)邏輯模型(層次、網(wǎng)狀、關(guān)系)基于記錄的模

型。層次、網(wǎng)狀模型用記錄和鏈接表示數(shù)據(jù)和聯(lián)系，關(guān)系模型用二維表表示數(shù)據(jù)，記錄值

表示表間聯(lián)系。

面向?qū)ο蟮哪Ｐ?，?duì)象-關(guān)系模型都屬于邏輯模型，面向?qū)ο竽Ｐ图仁歉拍钅Ｐ陀质?/p>

邏輯模型。

8、數(shù)據(jù)庫系統(tǒng)的三級(jí)模式結(jié)構(gòu)：由外模式、模式和內(nèi)模式三級(jí)構(gòu)成的。

9、模式(Schema)：一個(gè)數(shù)據(jù)庫只有一個(gè)模式；外模式也稱子模式或用戶模式，一個(gè)數(shù)據(jù)

庫可以有多個(gè)外模式。外模式是保證數(shù)據(jù)庫安全性的一個(gè)有力措施。內(nèi)模式也稱存儲(chǔ)模式

或物理模式，一個(gè)數(shù)據(jù)庫只有一個(gè)內(nèi)模式。

10.數(shù)據(jù)庫的二層映像與數(shù)據(jù)獨(dú)立性：外模式/模式映像，包含在各自的外模式描述中。

外模式/模式映像保證了數(shù)據(jù)與程序的邏輯獨(dú)立性(模式變，外模式不變)；模式/內(nèi)模

式映像，包含在模式描述中，模式/內(nèi)模式映像保證了數(shù)據(jù)與程序的物理獨(dú)立性(物理模

式變，模式不變，外模式不變)。

第五章關(guān)系數(shù)據(jù)庫系統(tǒng)

1、關(guān)系模型由關(guān)系數(shù)據(jù)結(jié)構(gòu)、關(guān)系操作集合和關(guān)系完整性約束3部分組成。

2、關(guān)系模型中的關(guān)系操作的理論依據(jù)為關(guān)系代數(shù)和關(guān)系演算。

關(guān)系操作的特點(diǎn)是集合操作方式。

3、關(guān)系數(shù)據(jù)語言可以分為如下3類：關(guān)系代數(shù)語言、關(guān)系演算語言(包括元組關(guān)系演算語

言和域關(guān)系演算語言)及具有關(guān)系代數(shù)和關(guān)系演算雙重特點(diǎn)的SQL語言。

4、關(guān)系模型中有3類完整性約束：實(shí)體完整性、參照完整性(引用完整性)和域完整性

約束(用戶自定義的完整性)

5、關(guān)系數(shù)據(jù)庫對(duì)關(guān)系的限定

當(dāng)關(guān)系作為關(guān)系數(shù)據(jù)模型的數(shù)據(jù)結(jié)構(gòu)時(shí)，關(guān)系數(shù)據(jù)庫對(duì)關(guān)系有如下的限制。

(1)列是同質(zhì)的.即每一列中的分量是同一類型的數(shù)據(jù)，來自同一個(gè)域。

(2)不同的列可以出自同一個(gè)域，稱其中的每一列為一個(gè)屬性，不同的屬性要給予不

同的屬性名。

(3)列的順序無關(guān)緊要，即列的次序可以任意交換。

(4)任意兩個(gè)元組不能完全相同。

(5)行的順序無關(guān)緊要，即行的次序可以任意交換。

(6)每一個(gè)屬性是不可分解的這是關(guān)系數(shù)據(jù)庫對(duì)關(guān)系的最基本的一條限定。分量必須取

原子值，即每一個(gè)分量都必須是不可拆分的數(shù)據(jù)項(xiàng)。

6、關(guān)系模型的完整性約束：實(shí)體完整性關(guān)系的所有主屬性都不能取空值，而不僅是主碼

整體不能取空值

參照完整性規(guī)則：外鍵要么取空值，要么等于被參照關(guān)系中某個(gè)元組的主碼值。

7、域完整性約束(用戶有定義的完整性)：對(duì)其他屬性值域的約束，也稱為域完整性規(guī)則，

包括數(shù)據(jù)類型、精度、取值范圍、是否允許空值等。

8、關(guān)系代數(shù)(了解操作的執(zhí)行結(jié)果)

并、差、笛卡兒積、投影和選擇為五種基本運(yùn)算。

9、傳統(tǒng)的集合運(yùn)算包括并、交、差和廣義笛卡兒積4種運(yùn)算。

10、專門的關(guān)系運(yùn)算包括：對(duì)單個(gè)關(guān)系進(jìn)行垂直分解（投影操作）或水平分解（選擇操作）和

對(duì)多個(gè)關(guān)系進(jìn)行結(jié)合（連接操作）等。

11、廣義投影

賦值、外連接（左外連接、右外連接）、半連接，聚集：G表示，外部并

第六章關(guān)系數(shù)據(jù)庫標(biāo)準(zhǔn)語言SQL

1、SQL（StructuredQueryLanguage）稱為結(jié)構(gòu)化查詢語言，SQL已經(jīng)成為關(guān)系數(shù)據(jù)

庫領(lǐng)域中的一種主流語言，1987年被國(guó)際標(biāo)準(zhǔn)化組織（ISO）采納為國(guó)際標(biāo)準(zhǔn)

1992年公布了SQL92（SQL2）,1999年公布了SQL93（SQL3,對(duì)象-關(guān)系SQL）,2003

年公布SQL2003（SQL4）

2、SQL特點(diǎn)：SQL語言集數(shù)據(jù)查詢、數(shù)據(jù)操縱、數(shù)據(jù)定義和數(shù)據(jù)控制功能于一體

綜合統(tǒng)一、高度非過程化、面向集合的操作方式、以同一種語法結(jié)構(gòu)提供兩種使用方

式（自含式和嵌入式SQL）、語言簡(jiǎn)潔，易學(xué)易用。

寂6.1SQL的盲的動(dòng)詞

SQL功能動(dòng)網(wǎng)

數(shù)據(jù)查詢SELECT

數(shù)據(jù)定義CREATE,DROP,ALTER

數(shù)據(jù)掾縱INSERT,UPDATE.DELETl

故據(jù)控制GRANT,REVOKE

3、SQL數(shù)據(jù)庫體系結(jié)構(gòu)：外模式對(duì)應(yīng)于視圖和部分基本表、模式對(duì)應(yīng)于基本表，內(nèi)

模式對(duì)應(yīng)于存儲(chǔ)文件

基本表是本身獨(dú)立存在的表，一個(gè)關(guān)系就是一個(gè)基本表（存放實(shí)際數(shù)據(jù)），行對(duì)應(yīng)元

組，列對(duì)應(yīng)屬性；一個(gè)基本表可以跨一個(gè)或多個(gè)存儲(chǔ)文件存放，一個(gè)存儲(chǔ)文件可以存放多

個(gè)基本表；所有基本表的集合構(gòu)成了模式；基本表是模式和外模式的一部分。

一個(gè)SQL表可以是一個(gè)基本表，也可以是一個(gè)視圖。視圖是一個(gè)或幾個(gè)基本表導(dǎo)出

的表，數(shù)據(jù)庫中存放視圖的定義，視圖的數(shù)據(jù)仍然在基本表中。視圖是一個(gè)虛表，是外模

式的一部分。

一個(gè)SQL表可以有若干索引，索引放在存儲(chǔ)文件中。存儲(chǔ)文件的邏輯結(jié)構(gòu)組成了SQL

數(shù)據(jù)庫的內(nèi)模式。物理結(jié)構(gòu)由操作系統(tǒng)管理，對(duì)用戶透明。

SQL用戶可以是一個(gè)應(yīng)用程序，可以一個(gè)SQL用戶。

4、SQL的數(shù)據(jù)類型：預(yù)定義數(shù)據(jù)類型、構(gòu)造數(shù)據(jù)類型、用戶定義數(shù)據(jù)類型

5、基本的SQL定義語句：關(guān)系數(shù)據(jù)庫的基本對(duì)象是模式、表、視圖、索引和域

基本對(duì)象創(chuàng)建刪除修改

模式CREATEDROPSCHEMA

SCHEMA

基本表CREATETABLEDROPTABLEALTER

TABLE

視圖CREATEVIEWDROPTABLE

索引CREATEINDEXDROPINDEX

域CREATEDROPDOMAIN

DOMAIN

6、基本操作語句

（1）模式的定義與刪除CreateSchema〈模式名〉A(chǔ)UTHORIZATION（用戶名〉

DropSchema(模式名>|CASCADE|RESTRICT

揪2瀛俄操作：創(chuàng)建：CREATETABLE［模式名.］〈表名〉（V列名〉〈數(shù)據(jù)類型〉（列

玉2>［列級(jí)完整性約束］…

貓1U牛

牛〉：涉及相應(yīng)!禹1

>：法及一年或多

CREATETABLES_SC_C.SC

(S#CHAR(8),C#CHAR(8),GRADEINTNOTNULL,

PRIMARYKEY(S#,C#),FOREIGNKEY(S#)REFERENCESSTU(S#)

)?

PRIMARYKEY(S#,C#),FOREIGNKEY(S#)REFERENCESSTU(S#)為表完整性約束

修改：ALTERTABLEV表名〉

：DROP^l

MODIFY之為（j名'W數(shù)據(jù)類型

刪除：當(dāng)某個(gè)基本表不再需J,可以角DROPTABLE語句進(jìn)行刪除，其格式為:

DROPTABLEV表名》

黎鸚I翹群噩羲嬲嬲

有事WJIOW能執(zhí)行刪除操作

(3)鼐避限和性看抑速懿斟再裁，、堤貨多種存取路徑

詢的瞿夠逆嵩蠢臃盛斗記錄的物理順序一致,適合在經(jīng)常查

>J

<次序〉指定索引值的排列次序，可選ASC(升序)或DESC(降序)，默認(rèn)值為ASC

如：CREATEUNIQUEINDEXSCnoONSC(SnoASC,CnoDESC)；

刪除索引：DROPINDEXV索引名〉；刪除索引時(shí)一，系統(tǒng)會(huì)同時(shí)從數(shù)據(jù)字典中刪去有

關(guān)該索引的描述

4、SQL的數(shù)據(jù)操縱語句

SQL語言的數(shù)據(jù)操縱包括INSERT(插人)、DELETE(冊(cè)邨余)、UPDATE(更新)和

SELETE(檢索，又稱查詢)4個(gè)語句

SELECT語句是數(shù)據(jù)操作的核心。

(1)數(shù)據(jù)查詢SELECT[ALLIDISTINCT]V目標(biāo)歹U表達(dá)式>],〈目標(biāo)列表達(dá)式》]…

FROMV基本表或視圖>[,<基本表或視圖》]…

[WHEREV條件表達(dá)式>]

[GROUPBY<列名1>[HAVING<條件表達(dá)式>]]

[ORDERBYC歹U名2>[ASC1DESC]]；

a.簡(jiǎn)單查詢

簡(jiǎn)單查詢涉及數(shù)據(jù)庫中的一個(gè)表，包括以下幾種:

(1)查詢表中的若干列。

(2)查詢經(jīng)過計(jì)算的值。

(3)消除取值重復(fù)的行。DISTINCT

(4)查詢滿足條件的元組。WHERE

(5)利用LIKE的查詢。_、%

(6)涉及空值NULL的查詢。ISNULL、ISNOTNULL

(7)對(duì)查詢結(jié)果排序。ORDERBYASC/DESC

(8)使用集函數(shù)。Count、SUM、AVG、MAX、MIN

(9)對(duì)查詢結(jié)果分組。Groupbyhaving

b.連接查詢

外連接的三種類型：左外連接、右外連接、全外連接

左外連接(LEFTOUTERJOIN):結(jié)果表中保留連接條件左邊關(guān)系中的所有元組

右外連接(RIGHTOUTERJOIN):結(jié)果表中保留連接條件右邊關(guān)系中的所有元組

全外連接(FULLOUTERJOIN):結(jié)果表中保留連接條件左右兩邊關(guān)系中的所有元組

某些系統(tǒng)中用+=表示左外連接、=+表示右外連接、+=+表示全外連接

c.嵌套查詢⑴由謂詞IN引導(dǎo)的子查詢：IN是最常用的謂詞。

(2)謂詞是比較運(yùn)算符的子查詢o

⑶由［NOT］EXISITS謂詞引導(dǎo)的子查詢。

d.集合查詢。

UNIONS）、INTERSECT（交）、EXCEPT（差）

5、SQL的修改語句

(1)插入操作（insert）insertinto表名（字段名，…）values（常量,…）

insertinto表名(字段名，…)select...from

(2)刪除操作(delete)deletefrom表名［whereF］刪除表中的數(shù)據(jù)，表的結(jié)構(gòu)還存在

數(shù)據(jù)字典中

(3)更新操作(update)update表名set列名=表達(dá)式，列名=表達(dá)式whereF

6、視圖

(1)創(chuàng)建視圖CREATEVIEWC視圖名〉列名〉(,〈列名〉…)

,AS＜子香詢＞

[WITHCHECKOPTION）：

其中子查詢可以是任意復(fù)雜的SELECT諳句，但通第不允許含有ORDERBY子句和

DISTINCT^豆語no。WITHCHECKOPTION表不對(duì)視圖進(jìn)彳￡【TDCATE、INTSQEKRPTT和DnmELEUTUE

操作時(shí)要優(yōu)證更新、插人或刪除的行滿足機(jī)圖定義中南情i條件袤達(dá)

(2)幾種特殊的視圖：行列子集視圖、表達(dá)式視圖、分組視圖、連接視圖

(3)查詢視圖：將對(duì)視圖的查詢轉(zhuǎn)換為對(duì)基本表的查詢的過程稱為視圖的消解(View

Resolution)o

視圖物化(ViewMaterialization)：是指在視圖第一次被查詢的時(shí)候物理地建立一個(gè)臨

時(shí)的視圖表(實(shí)表)，但必須保證更新基本表時(shí)自動(dòng)更新視圖表，保持物化視圖的最新性。

(4)修改視圖

為防止用戶通過視圖對(duì)數(shù)據(jù)進(jìn)行增、冊(cè)h改操作時(shí)，無意或有意操作不屬于視圖范圍

內(nèi)的基本表數(shù)據(jù)可在定義視圖時(shí)加上WITHCHECKOPTION子句，這樣在視圖上增、冊(cè)人

改數(shù)據(jù)時(shí)，DBMS會(huì)進(jìn)一步檢查視圖定義中的條件，若不滿足條件，則拒絕執(zhí)行該操作。

改視圖包括插入(INSERT)、冊(cè)邨余(DELETE)和更新(UPDATE)3類操作。行列子集視圖可

以修改，帶表達(dá)式視圖、連接視圖和分組視圖不能修改。

(5)視圖的作用

(1)能夠簡(jiǎn)化用戶的操作。

(2)使用戶能以多種角度看待同一數(shù)據(jù)。

(3)對(duì)重構(gòu)數(shù)據(jù)庫提供了一定程度的邏輯獨(dú)立性。

(4)能夠?qū)C(jī)密數(shù)據(jù)提供安全保護(hù)。

7、數(shù)據(jù)控制語句和嵌入式SQL

(1)GRANT語句和REVOKE語句實(shí)現(xiàn)權(quán)限授予和權(quán)限回收

GRANT權(quán)限ON對(duì)象名to用戶[withgrantoption];withgrantoption獲得權(quán)限的用

戶允許授予其他用戶

(2)REVOKEV權(quán)限》[,〈權(quán)限…[ONV對(duì)象類型〉〈對(duì)象名＞]FROMV用戶〉

[,＜用戶

(3)SQL語言分為獨(dú)立語言和嵌入式語言

SQL語言嵌入主語言解決的3個(gè)問題：

SQL語言與主語言的區(qū)分：EXECSQIXSQL語句〉

數(shù)據(jù)庫工作單元與程序工作單元的通信(通過主變量)

游標(biāo)解決集合操作與記錄操作的矛盾

DBMS可采用兩種方法處理嵌入式SQL,一種是預(yù)編譯，另一種是修改和擴(kuò)充主

;t五a等口

(4)動(dòng)態(tài)SQL：程序在執(zhí)行過程中動(dòng)態(tài)生成SQL語句。動(dòng)態(tài)SQL的兩種執(zhí)行方式：1、

立即執(zhí)行；2、先準(zhǔn)備后執(zhí)行

第七章關(guān)系數(shù)據(jù)庫的規(guī)范化理論與數(shù)據(jù)庫設(shè)計(jì)

1、“不好”的關(guān)系模式有以下4個(gè)問題：

a、數(shù)據(jù)冗余b、更新異常c、插入異常d、刪除異常

2、函數(shù)依賴

數(shù)據(jù)依賴中重要的是函數(shù)依賴和多值依賴

(1)函數(shù)依賴定義：設(shè)R(U)是屬性集U上的一個(gè)關(guān)系模式，X和Y均為U的子集。

若對(duì)于R(U)的任一個(gè)可能的關(guān)系r,r中不可能有兩個(gè)元組在X中的屬性值相等，而在

Y中的屬性值不等，那么稱X函數(shù)決定YX->Y,或Y函數(shù)依賴于X,X為決定因素(函

數(shù)中的一一映射關(guān)系)

(2)函數(shù)依賴包括非平凡的函數(shù)依賴、平凡的函數(shù)依賴、完全函數(shù)依賴、部分函數(shù)依賴

及傳遞函數(shù)依賴

平凡函數(shù)依賴：如果LY,但Y&X,則稱X-*Y是非平凡的函數(shù)依賴

非平凡函數(shù)依賴：如果XfY,但YX,則稱X-Y是平凡的函數(shù)依賴

完全騏［依賴：在關(guān)系模式R(U)中，如果X-Y,并且對(duì)于X的任何一個(gè)真子集

X',都有

X'Y,則稱Y完全函數(shù)依賴手XI定作:丫

部分函數(shù)依賴：若X-Y,但Y不完全函數(shù)依賴于X,則稱Y部分點(diǎn)數(shù)依減FX.記

作:

傳遞函數(shù)依賴：在關(guān)系模式R(U)中，證I果XfY(Y=X),Y-X,Y-Z,則稱Z傳遞函

數(shù)依賴于X。

(3)函數(shù)依賴的邏輯蘊(yùn)含

設(shè)RVU,F>是一個(gè)關(guān)系模式,X可以由F推導(dǎo)出Y,則稱F邏輯蘊(yùn)含X-Y

(4)碼：設(shè)K為關(guān)系模式R<U,F>中的屬性或?qū)傩越M合。若K-Lu,并且不存在K

的真子集決定U,則K稱為R的一個(gè)侯選碼(CandidateKey)。若關(guān)系模式R有多個(gè)候

選碼，則選定其中的一個(gè)做為主碼(Primarykey)。

主屬性與非主屬性

全碼(ALLKEY)：主碼為關(guān)系模式所有屬性

如何找候選碼：a.找出F集合的所有僅出現(xiàn)在左邊的屬性和左右兩邊都沒出現(xiàn)的屬性,

組合為UI,U1必包含在候選碼中；b.如果U1->U,則U1為一個(gè)候選碼，否則然后增加其

他屬性到U1中組成屬性組K,使K->U,則K為候選碼，再找出其他候選碼

(5)函數(shù)依賴的公理系統(tǒng)

b.SFB：Sx->Y嘉舞普矗落F臂爨普,%XZ->YZ為F所邏輯蘊(yùn)含。

c.傳遞律：若X->Y及Y->Z為F所邏輯蘊(yùn)含，則X->Z為F所邏輯蘊(yùn)含。

堤

普則

曷：X->Y,X->Z,則X->YZ

規(guī)

分則：X->YWY->Z,則xw->z

：X->Y及ZuY廁X->Z

3、INF、2NF,3NF,BCNF

(1)1NF:1NF的模式是關(guān)系數(shù)據(jù)庫的最基本要求

如果關(guān)系模式R的所有屬性都是不可再分解的，則稱R屬于第一范式，簡(jiǎn)稱1NF,記做

ReiNFo

(2)2NF:若R￡INF,且每一個(gè)非主屬性完全函數(shù)依賴于碼，貝ljRE2NF

(3)3NF:關(guān)系模式R￡2NF,且每個(gè)非主屬性都不傳遞依賴于碼，則RG3NF

(4)BCNF:若關(guān)系模式RG1NF,且對(duì)于每個(gè)非平凡的函數(shù)依賴X->Y都有X包含碼，則

ReBCNFo在函數(shù)依賴的范圍內(nèi)，BCNF達(dá)到了最高的規(guī)范化程度。

4、多值依賴和4NF

(1)多值依賴：設(shè)R(U)是一個(gè)屬性集U上的一個(gè)關(guān)系模式，X、Y和Z是U的子集,

并且Z=U—X—Y,多值依賴XffY成立當(dāng)且僅當(dāng)對(duì)R的任一關(guān)系r,r在(X,Z)上

的每個(gè)值對(duì)應(yīng)一組Y的值，這組值僅僅決定于X值而與Z值無關(guān)。

平凡多值依賴和非平凡的多值依賴

若XffY,而Z=6,則稱XffY為平凡的多值依賴，否則稱XffY為非平

凡的多值依賴

特性：a.多值依賴具有對(duì)稱性若Xf—Y,則Xf-Z,其中Z=U—X—Y

b.函數(shù)依賴是多值依賴的特殊情況。若XfY,則X-fY。

c.若函數(shù)依賴XfY在R(U)上成立，則對(duì)于任何Y'uY均有XfY，成立

多值依賴Xf-Y若在R(U)上成立，不能斷言對(duì)于任何Y，uY有XffY，成立

d.多值依賴的有效性與屬性集的范圍有關(guān).若XffY在U上成立，則在W(XY=W=

U)上一定成立；反之則不然，即XffY在W(WuU)上成立，在U上并不一定成立.

(2)4NF關(guān)系模式R<U,F>G1NF,如果對(duì)于R的每個(gè)非平凡多值依賴X-—Y(Y=X),

X都含有候選碼，則RW4NF。

根據(jù)定義：不允許有非平凡且非函數(shù)依賴的多值依賴，X包含碼，即X->Y,實(shí)際就是函

數(shù)依賴

4ZFUBCZFU3ZFU2ZFU1NF

如果R￡4NF,則ReBCNF

5、關(guān)系模式分解

常用的等價(jià)標(biāo)準(zhǔn)有要求分解具有無損連接性的和分解是保持函數(shù)依賴的兩種。

關(guān)系模式R〈U,F)分解為關(guān)系模式R,〈Q,F,〉,冬〈心,尸。是具有無損連接性的分解的充

分必要條件是-uj”?，或(4nUL%-q)€F.0

關(guān)于模式分解的幾個(gè)事實(shí)

(1)分解具有無損連接性和分解保持函數(shù)依賴是兩個(gè)互相獨(dú)立的標(biāo)準(zhǔn)。

(2)若要求分解具有無損連接性，那么模式分解一定可以達(dá)到BCNFo

(3)若要求分解保持函數(shù)依賴，那么模式分解可以達(dá)到3NF,但不一定能達(dá)到BCNF。

(4)若要求分解既具有無損連接性，又保持函數(shù)數(shù)依賴，則模式分解可以達(dá)到3NF,

但不一定能達(dá)到BCNF

6、數(shù)據(jù)庫的分析與設(shè)計(jì)

(1)數(shù)據(jù)庫設(shè)計(jì)的6個(gè)階段：需求階段、概念結(jié)構(gòu)階段、邏輯結(jié)構(gòu)設(shè)計(jì)、物理結(jié)構(gòu)設(shè)計(jì)、

數(shù)據(jù)庫實(shí)施、運(yùn)行維護(hù)

(2)設(shè)計(jì)概念結(jié)構(gòu)通常有4類方法：自頂向下、自底向上、由里向外和混合策略。

E-R模型為工具來描述概念結(jié)構(gòu)。最常用的設(shè)計(jì)策略是自底向上設(shè)計(jì)策略

E-R方法的步驟

a.設(shè)計(jì)局部E-R圖b.設(shè)計(jì)全局E-R圖解決屬性沖突、結(jié)構(gòu)沖突、命名沖突c.全局

E-R圖的優(yōu)化

(3)邏輯結(jié)構(gòu)設(shè)計(jì)

E-R模型向關(guān)系模型轉(zhuǎn)換:a.實(shí)體轉(zhuǎn)換為關(guān)系，屬性轉(zhuǎn)換為關(guān)系的屬性，實(shí)體碼轉(zhuǎn)換為關(guān)

系的碼

b.l：1的聯(lián)系，可以轉(zhuǎn)換為一個(gè)關(guān)系，也可以與聯(lián)系的任意一端實(shí)體關(guān)系模式合并

c.l:n的聯(lián)系可以轉(zhuǎn)換為一個(gè)獨(dú)立關(guān)系(屬性為1端和n端實(shí)體的碼和聯(lián)系本身屬性)(碼為

n端實(shí)體碼)，也可以與聯(lián)系的n端實(shí)體關(guān)系模式合并(加入1端實(shí)體碼)

d.m:n聯(lián)系轉(zhuǎn)換為一個(gè)關(guān)系模式(碼為各實(shí)體碼組合)

e.3個(gè)或3個(gè)以上的多元聯(lián)系轉(zhuǎn)換為一個(gè)關(guān)系模式，模式的碼由聯(lián)系的實(shí)體碼組成。

7、物理結(jié)構(gòu)設(shè)計(jì)

(1)存儲(chǔ)記錄的格式設(shè)計(jì)：記錄的垂直分割法、記錄的水平分割法。

(2)存儲(chǔ)方法設(shè)計(jì)：順序存放、散列存放和聚簇存放。

（3）存取方法設(shè)計(jì)：索引是一種非常重要的存取路徑（建立在經(jīng)常查詢和連接的屬性組

上）

8、規(guī)范化理論是數(shù)據(jù)庫設(shè)計(jì)的理論基礎(chǔ)，可以應(yīng)用到數(shù)據(jù)庫設(shè)計(jì)的不同階段。

第8章數(shù)據(jù)庫系統(tǒng)實(shí)現(xiàn)技術(shù)

1、數(shù)據(jù)庫管理系統(tǒng)概述

（1）DBMS的基本功能：a.數(shù)據(jù)庫定義功能（DDL）：外模式、模式、內(nèi)模式、完整性、

安全保密、索引、視圖定義，定義存儲(chǔ)在數(shù)據(jù)字典（系統(tǒng)目錄），是DBMS運(yùn)行的基

本依據(jù)。

b.數(shù)據(jù)操縱功能（DML）:檢索、插入、更新和刪除操作。

c.數(shù)據(jù)存儲(chǔ)和管理：

d.事務(wù)管理：并發(fā)和故障恢復(fù)。

e.通信功能和數(shù)據(jù)轉(zhuǎn)換功能等

（2）DBMS的程序模塊：數(shù)據(jù)定義模塊、數(shù)據(jù)操縱模塊、數(shù)據(jù)庫運(yùn)行管理模塊、數(shù)據(jù)庫

組織、存儲(chǔ)和管理模塊、數(shù)據(jù)庫建立、維護(hù)和其他方面模塊。

（3）DBMS的層次結(jié)構(gòu)：最上層是應(yīng)用層位于DBMS核心之外。

（2）第二層是語言翻譯處理層它處理的對(duì)象是數(shù)據(jù)庫語言SQL,

（3）第三層是數(shù)據(jù)存取層：該層處理的對(duì)象是單個(gè)元組。

（4）第四層是數(shù)據(jù)存儲(chǔ)層。該層處理的對(duì)象是數(shù)據(jù)頁和系統(tǒng)緩沖區(qū)。

（5）操作系統(tǒng)是DBMS的基礎(chǔ)。提供的存取原語和基本的存取方法通常作為與DBMS

存儲(chǔ)層的接口。它處理的對(duì)象是數(shù)據(jù)文件的物理塊。

2、數(shù)據(jù)庫管理系統(tǒng)的主要成分：

三個(gè)主要成分：存儲(chǔ)管理器（負(fù)責(zé)外存和內(nèi)存緩沖區(qū)管理）、查詢處理器（DDL編譯、

安全定義和查詢、完整定義和控制、查詢編譯優(yōu)化和執(zhí)行）、事務(wù)管理器（ACID特性，

事務(wù)管理、并發(fā)控制、日志管理和故障恢復(fù)）

存儲(chǔ)管理器重要模塊：存儲(chǔ)管理、緩沖區(qū)管理、索引/文件/記錄管理器

查詢處理器重要模塊：DDL編譯器、查詢編譯器、執(zhí)行引擎

事務(wù)管理器重要模塊：事務(wù)管理、日志和恢復(fù)、并發(fā)控制。

緩沖區(qū)和鎖表是DBMS管理的重要內(nèi)存結(jié)構(gòu)。

（1）存儲(chǔ)管理器：負(fù)責(zé)管理的數(shù)據(jù)包括：目標(biāo)數(shù)據(jù)、元數(shù)據(jù)、索引和日志等。

a.物理存儲(chǔ)介質(zhì)層次：高速緩沖存儲(chǔ)器、主存儲(chǔ)器、第二級(jí)存儲(chǔ)器、第三級(jí)存儲(chǔ)器，依

次訪問速度降低，價(jià)格也降低。

其中高速緩沖存儲(chǔ)器、主存儲(chǔ)器為基本存儲(chǔ)（易失性存儲(chǔ)），第二級(jí)存儲(chǔ)器（例如磁盤）稱

為輔助存儲(chǔ)器或聯(lián)機(jī)存儲(chǔ)器，第三級(jí)存儲(chǔ)器（如磁帶、光盤機(jī)）也叫脫機(jī)存儲(chǔ)器。第二級(jí)

和第三級(jí)存儲(chǔ)器為外存。

磁盤塊為磁盤空間分配的基本單位，也是磁盤與主存?zhèn)鬏敂?shù)據(jù)的邏輯單元。

b.數(shù)據(jù)組織：一個(gè)數(shù)據(jù)庫映為多個(gè)不同文件，為了將不同大小記錄組織在同一個(gè)磁盤

塊中，常采用分槽的頁結(jié)構(gòu)，即塊開始有塊頭（包括塊中記錄個(gè)數(shù)、塊中空閑空間尾指針、

記錄的位置和大小的數(shù)組）、中間為空閑區(qū)、尾部為分配的記錄。

C.緩沖區(qū)管理：緩沖區(qū)替換策略（最近最少使用LRU,先進(jìn)先出FIFO、時(shí)鐘算法、

系統(tǒng)控制法等.

d.數(shù)據(jù)字典：存儲(chǔ)關(guān)于數(shù)據(jù)庫的描述信息。必須存儲(chǔ)的目錄信息包括：關(guān)系基本信息、

用戶信息、索引信息和統(tǒng)計(jì)信息。

e.索引結(jié)構(gòu)：支持對(duì)所要求的數(shù)據(jù)進(jìn)行快速定位的附加數(shù)據(jù)結(jié)構(gòu)稱為索引。

一個(gè)文件可以有多個(gè)索引，一個(gè)索引包括一個(gè)屬性和多個(gè)屬性（查找碼或搜索碼），以

及對(duì)應(yīng)記錄的位置。

順序索引：查找碼按順序存儲(chǔ)如B+樹索引，在順序索引中，如果對(duì)應(yīng)的記錄也按查找

碼排列，則稱為聚集索引（主索引）。

對(duì)單個(gè)關(guān)系中元組的查詢可分為點(diǎn)查詢和范圍查詢：

點(diǎn)查詢：查詢特定屬性上指定值的元組，一般為查詢結(jié)果為單個(gè)記錄比如select*

fromstudentfroms#='001'

范圍查詢：查詢給定屬性值在指定范圍的所有元組，一般查詢結(jié)果為多個(gè)記錄select*

fromstudentfroms#between'OOTand'009'

順序索引支持點(diǎn)查詢和范圍查詢，散列索引支持點(diǎn)查詢，不支持范圍查詢(注意)

(2)查詢處理：查詢處理器最主要的模塊查詢編譯器和查詢執(zhí)行引擎.

a.查詢處理過程：分析查詢語句語法(生成語法分析樹，翻譯為關(guān)系表達(dá)式，形成初

始查詢計(jì)劃)、選擇邏輯查詢計(jì)劃(生成邏輯查詢計(jì)劃樹或擴(kuò)展的關(guān)系代數(shù)表達(dá)式)、選擇

物理查詢計(jì)劃(生成物理查詢計(jì)劃樹)、查詢執(zhí)行。

邏輯查詢選擇：初始查個(gè)詢計(jì)劃轉(zhuǎn)化為一個(gè)預(yù)期執(zhí)行執(zhí)行時(shí)間較小的等價(jià)計(jì)劃過程。

b.選擇邏輯查詢計(jì)劃和選擇物理查詢計(jì)劃的步驟通稱為查詢優(yōu)化。

物理查詢計(jì)劃選擇常采用基于代價(jià)的查詢計(jì)劃選擇方法(根據(jù)選定的邏輯查詢計(jì)劃

派生多個(gè)不同物理查詢計(jì)劃，并選擇代價(jià)最小或接近最小的物理查詢計(jì)劃)。

關(guān)系代數(shù)表達(dá)式等價(jià)：選擇運(yùn)算對(duì)并、交、差具有分配律：

oP(E1UE2)=op(El)UoP(E2)。P(E1AE2)=oP(El)AoP(E2)

oP(E1-E2)=op(El)-oP(E2)

投影對(duì)并運(yùn)算分配律：nL(ElUE2)=TIL(E1)UTIL(E2)

c.查詢執(zhí)行:查詢執(zhí)行的最基本動(dòng)作是關(guān)系運(yùn)算的執(zhí)行。選擇運(yùn)算的兩種實(shí)現(xiàn)方式：全

表掃描(依次訪問表中的每一塊)，索引掃描。

(3)事務(wù)管理

a.事務(wù)的概念:數(shù)據(jù)庫的一些操作的集合通常是一個(gè)獨(dú)立單元，這種具有獨(dú)立性的邏輯

單元即是事務(wù)

b.事務(wù)的特性:

1)原子性(Atomicity)。事務(wù)的所有操作在數(shù)據(jù)庫中是不可分割的，或全部反映出來或

全部不反映。

2)一致性(Consistency)o事務(wù)執(zhí)行的結(jié)果必須是使數(shù)據(jù)庫從一個(gè)一致性狀態(tài)轉(zhuǎn)變到另

一個(gè)一致性狀態(tài)。即數(shù)據(jù)庫中只包含成功事務(wù)提交的結(jié)果。

3)隔離性(Isolation)。事務(wù)的執(zhí)行不能被其他事務(wù)所干擾，一個(gè)事務(wù)內(nèi)部的操作及使用

的數(shù)據(jù)對(duì)其他并發(fā)事務(wù)是隔離的，互不影響。

4)持久性(Durability)。事務(wù)一旦提交并執(zhí)行后，它對(duì)數(shù)據(jù)庫中數(shù)據(jù)的改變是永久的。

事務(wù)特性：原子性(Atomicity)、一致性(Consistency)、隔離性(Isolation)-,持久性

(durability)o

原子性、持久性：事務(wù)管理器中故障恢復(fù)機(jī)制責(zé)任。一致性：應(yīng)用程序員的責(zé)任。隔

離性：事務(wù)管理器中并發(fā)控制部件責(zé)任。

(4)事務(wù)的并發(fā)控制

a.事務(wù)的并發(fā)執(zhí)行

并發(fā)執(zhí)行時(shí)可能會(huì)破壞數(shù)據(jù)庫的一致性，主要問題包括以下三方面：

1)丟失更新。2)對(duì)未提交更新的依賴。(讀臟數(shù)據(jù))3)不一致的分析。(不可重

復(fù)讀)

b.并發(fā)事務(wù)的調(diào)度

如果多個(gè)事務(wù)在某個(gè)調(diào)度下的執(zhí)行結(jié)果與這些事務(wù)在某個(gè)串行調(diào)度下的執(zhí)行結(jié)果相

同，則稱這個(gè)調(diào)度為可串行化的調(diào)度。若用等價(jià)的概念來表示就是指某個(gè)調(diào)度等價(jià)于一個(gè)

串行調(diào)度。

可串行化是多個(gè)事務(wù)并發(fā)執(zhí)行的正確性準(zhǔn)則。

事務(wù)的可恢復(fù)調(diào)度：對(duì)于每對(duì)事務(wù)Ti和Tj,如果Tj讀取了Ti所寫的數(shù)據(jù)，則Ti先于Tj

提交。

級(jí)聯(lián)回滾：一個(gè)事務(wù)導(dǎo)致依賴它的一系列事務(wù)回滾的現(xiàn)象。

無級(jí)聯(lián)回滾（調(diào)度）：由于級(jí)聯(lián)回滾導(dǎo)致大量工作撤銷，所以對(duì)調(diào)度加以限制，避免級(jí)聯(lián)

回滾發(fā)生，這樣的調(diào)度為無級(jí)聯(lián)調(diào)度。

可串行化且無級(jí)聯(lián)（可恢復(fù)）調(diào)度保證數(shù)據(jù)庫一致性，是我們所需要的。

（5）.封鎖

在事務(wù)的并發(fā)執(zhí)行過程中為保證數(shù)據(jù)庫的一致性，常采用封鎖的方法來限制其他事務(wù)

對(duì)該事務(wù)數(shù)據(jù)項(xiàng)的訪問。對(duì)數(shù)據(jù)項(xiàng)加鎖的方式主要有兩種。

1）共享鎖。如果事務(wù)T獲得了數(shù)據(jù)項(xiàng)Q上的共享型鎖（記為S）,則Ti可讀Q但不能

寫e。

2）排他鎖。如果事務(wù)Ti獲得了數(shù)據(jù)項(xiàng)Q上的排他型鎖（記為X）,則T既可讀Q又可

寫Q。

注意：加了共享鎖的數(shù)據(jù)項(xiàng)可以再加共享鎖，不能加排他鎖。

加了排他鎖的數(shù)據(jù)項(xiàng)不能再加共享鎖和排他鎖。

簡(jiǎn)言之：共享鎖與共享鎖相容，與排他鎖不相容

排他鎖與任何鎖不相容。

兩階段封鎖協(xié)議保證可串行性，它要求每個(gè)事務(wù)分兩個(gè)階段提出加鎖和解鎖申請(qǐng)?？?/p>

保證可串行化。

1）增長(zhǎng)階段。事務(wù)可以獲得