數(shù)據(jù)庫系統(tǒng)實現(xiàn)復習提綱.doc

復習提綱20151.數(shù)據(jù)庫管理系統(tǒng)主要包括存儲管理器、查詢處理器和事務(wù)管理器等幾個子系統(tǒng)。2.DBMS從接受查詢請求到返回結(jié)果的整個運行過程。（有圖）（簡答，問答）Step 1:用戶向DBMS發(fā)出調(diào)用數(shù)據(jù)庫數(shù)據(jù)的命令Step 2:DBMS對命令進行語法檢查、語義檢查、存取權(quán)限檢查，決定是否執(zhí)行該命令Step 3:DBMS執(zhí)行查詢優(yōu)化，把命令轉(zhuǎn)換為一串單記錄的存取操作序列Step 4:執(zhí)行存取操作序列（反復執(zhí)行以下各步，直至結(jié)束）Step 5:DBMS首先在緩沖區(qū)內(nèi)查找記錄，若找到轉(zhuǎn)10，否則轉(zhuǎn)6Step 6:DBMS查看存儲模式，決定從哪個文件存取哪個物理記錄Step 7:DBMS根據(jù)6的結(jié)果，向操作系統(tǒng)發(fā)出讀取記錄的命令Step 8:操作系統(tǒng)執(zhí)行讀取數(shù)據(jù)的命令Step 9:操作系統(tǒng)將數(shù)據(jù)從數(shù)據(jù)庫存儲區(qū)送到系統(tǒng)緩沖區(qū)Step 10:DBMS根據(jù)用戶命令和數(shù)據(jù)字典的內(nèi)容導出用戶所要讀取的數(shù)據(jù)格式Step 11:DBMS將數(shù)據(jù)記錄從系統(tǒng)緩沖區(qū)傳送到用戶工作區(qū)Step 12:DBMS將執(zhí)行狀態(tài)信息返回給用戶3.存儲管理器負責管理的數(shù)據(jù)包括目標數(shù)據(jù)、元數(shù)據(jù)、索引和日志等，這些數(shù)據(jù)保存在磁盤上。4.磁盤結(jié)構(gòu)及磁盤容量的計算。（填空題）磁盤控制器： 控制一個或多個磁盤的小處理器，功能如下,l 定位磁頭到一個特定的半徑位置。l 選擇一個準備讀寫的盤面，從位于該盤面的磁頭下的磁道上選擇一個扇區(qū)。并識別何時該扇區(qū)正開始移動到磁頭下面。l 將從該扇區(qū)讀取的二進制位傳送到主存儲，或?qū)闹鞔嬉獙懭氲亩M制位傳送到該扇區(qū)。l 為所寫扇區(qū)附加校驗和，并在讀取扇區(qū)時檢查它。l 進行壞扇區(qū)的重映射。硬盤容量 = 柱面數(shù) (表示每面盤面上有幾條磁道，一般總數(shù)是1024) 磁頭數(shù)(表示盤面數(shù)) 扇區(qū)數(shù)（表示每條磁道有幾個扇區(qū)，一般總數(shù)是64） 扇區(qū)(存儲基本單元，大小一般為512B/4KB)5.一次磁盤訪問（I/O）的時間包括尋道時間（占時多）、定位時間（中）和讀取時間（?。?，相互關(guān)系。6.磁盤塊存取的優(yōu)化方法。（調(diào)度那些，雙緩沖，什么鬼）（填空，簡答）n 在主存儲器中對塊進行緩沖以減少塊的讀寫次數(shù)n 按柱面組織數(shù)據(jù)n 使用多個磁盤n 磁盤鏡像n 磁盤臂調(diào)度- 電梯算法n 利用非易失性RAM作為寫緩沖n 預讀和雙緩沖n 日志磁盤7.RAID具有提高性能和提高可靠性能兩方面的作用。（填空題）Redundant Arrays of Inexpensive Disks價格上，大量廉價的磁盤比少量昂貴的大磁盤合算得多性能上，使用大量磁盤可以提高數(shù)據(jù)的并行存取可靠性上，冗余數(shù)據(jù)可以存放在多個磁盤上，因此一個磁盤的故障不會導致數(shù)據(jù)丟失RAID級別RAID 0級：塊級拆分，無冗余RAID 1級：帶塊級拆分的磁盤鏡像RAID 2級：內(nèi)存風格的糾錯碼組織結(jié)構(gòu)RAID 3級：位交叉的奇偶校驗組織結(jié)構(gòu)RAID 4級：塊交叉的奇偶校驗組織結(jié)構(gòu)RAID 5級：塊交叉的分布奇偶校驗位的組織結(jié)構(gòu)RAID 6級：P+Q冗余方案8.重點掌握RAID4（塊級拆分，奇偶校驗）、RAID5（塊級拆分，）和RAID6（提供兩個冗余盤，允許兩個盤出現(xiàn)故障）優(yōu)缺點（填空簡答）RAID 4假定:有4個數(shù)據(jù)盤和一個冗余盤讀出數(shù)據(jù)，與從任何一個磁盤讀塊沒有差別；寫數(shù)據(jù)需要2次磁盤讀和2次磁盤寫操作。RAID 5將數(shù)據(jù)和奇偶校驗位都分布到所有的N+1個磁盤上；對每個塊，一個磁盤存儲奇偶校驗位，其余磁盤存儲數(shù)據(jù)例如由5個磁盤組成的陣列，第n塊的奇偶校驗位存儲在第(n mod 5)+1上，其余4個磁盤的第n塊存儲了對應(yīng)這個塊的實際數(shù)據(jù)奇偶校驗塊不能和這個塊對應(yīng)的數(shù)據(jù)存儲在同一個磁盤上所有磁盤都參與對讀請求的服務(wù)，而RAID 4中奇偶校驗磁盤不參與讀操作RAID 5包容了RAID 4，同時在相同成本下，提供了更好的讀寫性能RAID 6類似于RAID 5，存儲了額外的冗余信息不采用奇偶校驗位的方法，使用類似Reed-Solomon碼的編碼對每4位數(shù)據(jù)存儲2位冗余信息可以容忍兩個磁盤發(fā)生故障9.緩沖區(qū)管理工作流程。（還有數(shù)據(jù)結(jié)構(gòu)，填空簡答）數(shù)據(jù)結(jié)構(gòu)和流程:每個frame包括：pin_count,dirtypin_count:正在訪問該frame的事務(wù)的個數(shù)Dirty:已經(jīng)被修改過的Frame請求處理的流程查看Buffer pool是否包含此頁，如沒有，則找一個pin_count為0的frame，pin_count+如dirty為true,則將其寫入磁盤將相應(yīng)的頁讀入此frame將frame的地址返回10.文件中定長紀錄的組織方法，紀錄id（頁號，塊號）的組成。11.文件中變長紀錄的組織方法，紀錄id（頁號，塊號，塊內(nèi)起始地址，長度）的組成。（填空）12.文件中組織紀錄的幾種方法：堆文件組織、順序文件組織、散列文件組織、聚簇文件組織。（填空）堆文件組織（heap file organization） 一條記錄可以放在文件中的任何地方，只要有空間存放這條記錄。記錄是無序的。通常一個關(guān)系是一個單獨的文件。順序文件組織（sequential file organization） 記錄根據(jù)“搜索碼”的值順序存儲。散列文件組織（hashing file organization） 在每條記錄的某些屬性上計算一個散列函數(shù)。散列函數(shù)的結(jié)果確定了記錄應(yīng)該放到文件的哪個塊中。聚簇文件組織（clustering file organization） 幾個不同關(guān)系的記錄存儲在同一文件中（通常用一個文件存儲一個關(guān)系的記錄。）甚至不同關(guān)系中的相關(guān)記錄存儲在相同的塊中，于是一個I/O操作可以從多個關(guān)系中取到相關(guān)記錄。13.順序文件組織中，為什么在進行大量插刪改后需要重組？（溢出塊溢出表里）（簡答題）索引順序文件上的修改動作:創(chuàng)建或刪除一個空存儲塊創(chuàng)建或刪除一個溢出塊插入一條記錄到一個空塊中刪除記錄將記錄移動相鄰的塊中14.索引是支持對于所要求的數(shù)據(jù)進行快速定位的附加的數(shù)據(jù)結(jié)構(gòu)。聚集索引與非聚集索引稠密索引與稀疏索引多級索引（填空）15.B+樹的樹結(jié)點的大小一般取塊的大小。16.B+樹的查詢及構(gòu)造方法，插入、刪除方法，效率。（簡答，問答）17.動態(tài)散列索引的實現(xiàn)原理（可擴充散列，實現(xiàn)方法，桶分裂）（簡答，問答）思想原理:動態(tài)散列技術(shù)允許散列函數(shù)動態(tài)改變，通過桶的合并和分解實現(xiàn)數(shù)據(jù)庫的增大或縮小的需求，這樣既繼承了散列高效查找效率又保持了良好的空間壓縮率。 動態(tài)散列是逐步擴充散列值的位數(shù)來構(gòu)造索引，它通過位比較來實現(xiàn)散列值的定位，這種比較方式計算機通過幾個CPU機器指令即可實現(xiàn)，故它的效率很高。18.在位圖索引中，從位向量得到壓縮編碼位向量的方法以及從壓縮編碼位向量重新構(gòu)造實際的位向量的方法（填空）K.O.19.位圖索引的構(gòu)造及維護方法（簡答）K.O.20.查詢優(yōu)化是為關(guān)系代數(shù)表達式的計算選擇最有效的查詢計劃的過程。（填空題）21.選擇運算算法及代價分析（主要考慮帶有B+樹索引的情況）（填空題，分析題）22.外部排序的算法（初始歸并段的數(shù)目、歸并的趟數(shù)）及代價分析（填空題，多空）23.各種連接算法的實現(xiàn)及其代價分析（塊嵌套循環(huán)連接算法、散列連接算法、排序-歸并連接算法）（占比例高，分析題）24.對于基于主碼、外碼連接的情況：結(jié)果集的元組數(shù)等于外碼所在表的元組數(shù)。（填空題）25.為什么要進行結(jié)果集大小的估計？（判斷要不要用索引）26.DBMS中存儲的統(tǒng)計信息（最大最小值，分布情況什么鬼）的作用是什么？（制定執(zhí)行計劃時，計算代價需要）（簡答題）27.啟發(fā)式優(yōu)化的步驟。（簡答題）28.事務(wù)的ACID特性，以及分別有什么機制保證（填空題）事務(wù)定義：事務(wù)是由一系列操作序列構(gòu)成的程序執(zhí)行單元，這些操作要么都做，要么都不做，是一個不可分割的工作單位，例如銀行轉(zhuǎn)帳。SQL中事務(wù)的定義：事務(wù)以Begin transaction開始，以Commit work或 Rollback work結(jié)束。Commit work表示提交，事務(wù)正常結(jié)束Rollback work表示事務(wù)非正常結(jié)束，撤消事務(wù)已做的操作，回滾到事務(wù)開始時狀態(tài)事務(wù)特性(ACID)：原子性(Atomicity)：事務(wù)中包含的所有操作要么全做，要么全不做；原子性由恢復機制實現(xiàn)一致性(Consistency)：事務(wù)的隔離執(zhí)行必須保證數(shù)據(jù)庫的一致性事務(wù)開始前，數(shù)據(jù)庫處于一致性的狀態(tài)；事務(wù)結(jié)束后，數(shù)據(jù)庫必須仍處于一致性狀態(tài)數(shù)據(jù)庫的一致性狀態(tài)由用戶來負責，由并發(fā)控制機制實現(xiàn)隔離性(Isolation)：系統(tǒng)必須保證事務(wù)不受其它并發(fā)執(zhí)行事務(wù)的影響對任何一對事務(wù)T1，T2，在T1看來，T2要么在T1開始之前已經(jīng)結(jié)束，要么在T1完成之后再開始執(zhí)行隔離性通過并發(fā)控制機制實現(xiàn)持久性(Durability)：一個事務(wù)一旦提交之后，它對數(shù)據(jù)庫的影響必須是永久的系統(tǒng)發(fā)生故障不能改變事務(wù)的持久性持久性通過恢復機制實現(xiàn)29.事務(wù)可串行化的判斷一般采用優(yōu)先圖來實現(xiàn)，優(yōu)先圖的構(gòu)造方法及可串行化的判斷方法。（什么鬼圖，有沒有環(huán)可不可串行化）（填空）可串行化：若調(diào)度S與一個串行調(diào)度的執(zhí)行有相同的效果，則稱調(diào)度S是可串行化的。沖突可串行化： 視圖可串行化：如果某個調(diào)度視圖等價于一個串行調(diào)度，則稱該調(diào)度是視圖可串行化的，沖突可串行化調(diào)度一定是視圖可串行化的，存在視圖可串行化但非沖突可串行化的調(diào)度。30.死鎖（產(chǎn)生）及其解決方法（填空）死鎖：如果系統(tǒng)中存在一個事務(wù)集，集合中的每個事務(wù)在等待該集合中的另一個事務(wù)所鎖住的數(shù)據(jù)項，則稱系統(tǒng)處于死鎖狀態(tài)。處理死鎖的兩種主要方法：n 死鎖預防：采用死鎖預防協(xié)議保證系統(tǒng)永不進入死鎖狀態(tài)1：對加鎖請求加以限制2：強占與事務(wù)回滾n 死鎖檢測與死鎖恢復：允許系統(tǒng)進入死鎖狀態(tài)，然后進行檢測和恢復。-死鎖恢復選擇犧牲者：應(yīng)使事務(wù)回滾帶來的代價最小。影響事務(wù)回滾代價的因素：事務(wù)已計算了多久，在完成之前還將計算多長時間， 事務(wù)已使用了多少數(shù)據(jù)項，為完成事務(wù)還需使用多少數(shù)據(jù)項，回滾時將牽涉多少事務(wù)回滾：徹底回滾，或只回滾到可以解除死鎖處?；诔瑫r的機制：一種介于死鎖預防與死鎖檢測之間的折中的機制。31.鎖表結(jié)構(gòu)（散列表？）及其工作原理（在申請加鎖，釋放鎖是怎樣的）（簡答題，問答）封鎖的實現(xiàn) 鎖管理器中重要的數(shù)據(jù)結(jié)構(gòu)：鎖表(lock table)。n 為目前已加鎖的每個數(shù)據(jù)項維護一個鏈表，鏈表中每一個記錄表示對該數(shù)據(jù)項的一個加鎖請求。記錄按請求到達的順序排序。n 鏈表中的每個記錄主要包括如下內(nèi)容：哪個事務(wù)提出的請求，請求的鎖類型，該請求是否已被授予鎖。n 采用一個以數(shù)據(jù)項名稱為索引的散列表作為鏈表入口。鎖管理器工作方式n 當一個封鎖請求到達時，如果相應(yīng)數(shù)據(jù)項的鏈表存在，則在該鏈表末尾增加一個記錄，否則新建一個僅包含該請求的鏈表。（數(shù)據(jù)項上的第一次加鎖請求總是被授予，但當事務(wù)向已被加鎖的數(shù)據(jù)項申請加鎖時，只有當該請求與先前請求相容，并且所有先前的請求都已被授予鎖的條件下，鎖管理器才為該請求授予鎖，否則令請求等待。）n 當收到一個事務(wù)的解鎖消息時，則將相應(yīng)的鏈表記錄刪除，然后檢查隨后的記錄，如果有正在等待的封鎖請求，則看該請求能否被授權(quán)，如果能，則授權(quán)該請求并處理其后記錄，如果還有，類似地一個接一個的處理。n 如果一個事務(wù)中止，則刪除該事務(wù)產(chǎn)生的正在等待加鎖的所有請求。當數(shù)據(jù)庫系統(tǒng)撤消了該事務(wù)，則該中止事務(wù)持有的所有鎖將被釋放。32.同數(shù)據(jù)庫交互的三個地址空間.（磁盤地址空間，緩沖區(qū)地址空間，事務(wù)內(nèi)部的地址空間）（填空）33.數(shù)據(jù)庫中主要有哪幾類故障。（填空）故障分類：事務(wù)故障：邏輯錯誤，事務(wù)由于某些內(nèi)部條件而無法繼續(xù)正常執(zhí)行。系統(tǒng)錯誤，系統(tǒng)進入一種不良狀態(tài)（如，死鎖），使事務(wù)無法繼續(xù)正常執(zhí)行。系統(tǒng)崩潰，硬件或數(shù)據(jù)庫軟件或操作系統(tǒng)故障，易失性存儲器內(nèi)容的丟失，事務(wù)處理終止。磁盤故障，由于磁頭損壞或故障造成磁盤塊上的內(nèi)容丟失。34.使用undo/redo日志進行恢復（系統(tǒng)故障的）的方法。（掃描文件，撤銷隊列，重做隊列，對沒完成的事務(wù)加終止標記）（簡答）undo日志保證事務(wù)的原子性redo日志保證事務(wù)的持久性undo/redo日志保證事務(wù)的原子性和持久性使用undo/redo日志的恢復： 1. 從后往前掃描日志，構(gòu)造undo-list 和redolist： 對每一個形如的記錄，將Ti 加入redo-list。 對每一個形如的記錄，如果Ti不屬于redo-list，則將Ti加入undo-list。 2. 由后至前重新掃描日志，對undo-list中的每個事務(wù)Ti的每一個日志記錄執(zhí)行undo操作。 3. 由前至后重新掃描日志，并且對redo-list中每個事務(wù)Ti的每一個日志記錄執(zhí)行redo操作。推遲提交的一個問題： 使用undo/redo日志的系統(tǒng)中可能出現(xiàn)這樣的行為： 事務(wù)在用戶看來已經(jīng)提交， 但由于記錄尚未刷新到磁盤，后來的一次崩潰使該事務(wù)被撤銷而不是重做。 最好為undo/redo日志使用一條附加的規(guī)則：記錄一旦出現(xiàn)在日志中就必須被刷新到磁盤上。35.undo / redo日志中，為什么要引入檢查點，檢查點的創(chuàng)建需要做的工作。（避免讀取整個日志文件，避免早就提交的事務(wù)的工作）（當前所有日志緩沖和數(shù)據(jù)緩沖）（恢復工作怎么樣？）（填空題，簡答題）故障恢復時掃描整個日志所帶來的問題：掃描日志耗費時間長重做所有已提交事務(wù)耗費時間長，事實上許多事務(wù)對數(shù)據(jù)庫的修改已經(jīng)寫到磁盤，不必再重做。解決辦法：周期性地對日志做檢查點，以避免故障恢復時檢查整個日志。undo / redo日志檢查點的做法： 1）寫入日志記錄，其中T1, , Tk是所有的活躍事務(wù)，并刷新日志。 2）將所有臟緩沖區(qū)寫到磁盤，臟緩沖區(qū)即包含一個或多個修改過的數(shù)據(jù)庫元素的緩沖區(qū)。 3）寫入日志記錄并刷新日志。系統(tǒng)使用檢查點方法進行恢復的步驟：1、找到最后一個檢查點記錄在日志文件中的地址，由該地址在日志文件中找到最后一個檢查點記錄。2、由該檢查點記錄得到檢查點建立時刻所有正在執(zhí)行的事務(wù)清單ACTIVE-LIST，把ACTIVE-LIST暫時放入UNDO-LIST，REDO-LIST暫為空。3、從檢查點開始正向掃描日志文件。如有新開始的事物Ti，把Ti暫時放入UNDO-LIST；如有提交的事務(wù)Tj，把Tj從UNDO-LIST移到REDO-LIST，直到日志文件結(jié)束。4、對UNDO-LIST中的每個事務(wù)執(zhí)行UNDO操作，對REDO-LIST中的每個事務(wù)執(zhí)行REDO操作。36.數(shù)據(jù)在分布式數(shù)據(jù)庫的存儲途徑有哪三種。（分片組，復制，分片+復制）數(shù)據(jù)在分布式數(shù)據(jù)庫的存儲途徑：復制：系統(tǒng)維護關(guān)系的幾個完全相同的副本，這些副本存儲在不同的結(jié)點上分片：關(guān)系被劃分為幾個片段，各個片段存儲在不同的結(jié)點上復制+分片：關(guān)系被劃分為幾個片段，系統(tǒng)為每個片段維護幾個副本37.分布式數(shù)據(jù)庫中數(shù)據(jù)訪問的瓶頸（CPU,磁盤I/O,網(wǎng)絡(luò)傳輸）38.分布式數(shù)據(jù)庫中，數(shù)據(jù)分片的四種方式。（水平，垂直分片；）（填空題）數(shù)據(jù)分片優(yōu)點：將關(guān)系分片，有利于按用戶需求組織數(shù)據(jù)的分布。如產(chǎn)品（內(nèi)銷產(chǎn)品，出口產(chǎn)品）。分片方式：水平分片（并運算）,垂直分片（連接運算）,導出分片,混合分片39.分片透明性和位置透明性的含義（講義例子）（填空題，簡答題）分布（網(wǎng)絡(luò)）透明性：分片透明性：用戶或應(yīng)用程序只對全局關(guān)系進行操作而不必考慮關(guān)系的分片。如果分片模式改變了，通過調(diào)整全局模式與分片模式之間的映象關(guān)系來保持全局模式不變位置透明性：用戶或應(yīng)用程序不必了解片段的存儲位置局部數(shù)據(jù)模型透明性：用戶或應(yīng)用程序不必了解局部場地上使用的是哪種數(shù)據(jù)模型40.半連接的實現(xiàn)方法（講義中的示例）（重點）（簡答題，問答題）41.信息集成的三個方面的問題（）具體含義也要（問答題，簡答題）動機:提供對分布、自治且通常是異質(zhì)的多個信息源的共享與統(tǒng)一訪問。自治性: 信息源系統(tǒng)獨立地決定其自身特性，保持其分開的獨立控制，隨著時間改變數(shù)據(jù)與功能這種改變不應(yīng)受到集成系統(tǒng)過多制約。