譯者序
前言
第1章   DBMS實現概述	
1.1   Megatr on 2000數據庫系統介紹	
1.1.1   Megatr on 2000實現細節	
1.1.2   Megatron 2000如何執行查詢	
1.1.3   Megatron 2000有什么問題	
1.2   數據庫管理系統概述	
1.2.1   數據定義語言命令	
1.2.2   查詢處理概述	
1.2.3   主存緩沖區和緩沖區管理器	
1.2.4   事務處理	
1.2.5   查詢處理器	
1.3   本書梗概	
1.3.1   預備知識	
1.3.2   存儲管理概述	
1.3.3   查詢處理概述	
1.3.4   事務處理概述	
1.3.5   信息集成概述	
1.4   數據庫模型和語言回顧	
1.4.1   關系模型回顧	
1.4.2      SQL回顧	
1.4.3   關系的和面向對象的數據	
1.5   小結	
1.6   參考文獻	
第2章   數據存儲	
2.1   存儲器層次	
2.1.1   高速緩沖存儲器	
2.1.2   主存儲器	
2.1.3   虛擬存儲器	
2.1.4   第二級存儲器	
2.1.5   第三級存儲器	
2.1.6   易失和非易失存儲器	
習題		
2.2   磁盤	
2.2.1   磁盤結構	
2.2.2   磁盤控制器	
2.2.3   磁盤存儲特性	
2.2.4   磁盤訪問特性	
2.2.5   塊的寫入	
2.2.6   塊的修改	
習題		
2.3   輔助存儲器的有效使用	
2.3.1   計算的I/O模型	
2.3.2   輔助存儲器中的數據排序	
2.3.3   歸并排序	
2.3.4   兩階段多路歸并排序	
2.3.5   擴展多路歸并以排序更大的關系	
習題		
2.4   改善輔助存儲器的訪問時間	
2.4.1   按柱面組織數據	
2.4.2   使用多個磁盤	
2.4.3   磁盤鏡像	
2.4.4   磁盤調度和電梯算法	
2.4.5   預取和大規模緩沖	
2.4.6   各種策略及其優缺點	
習題		
2.5   磁盤故障	
2.5.1間斷性故障	
2.5.2   校驗和	
2.5.3   穩定存儲	
2.5.4   穩定存儲的錯誤處理能力	
習題		
2.6   從磁盤崩潰中恢復	
2.6.1   磁盤的故障模型	
2.6.2   作為冗余技術的鏡像	
2.6.3   奇偶塊	
2.6.4   一種改進：RAID	
2.6.5   多個盤崩潰時的處理	
習題		
2.7   小結	
2.8   參考文獻	
第3章   數據元素的表示	
3.1   數據元素和字段	
3.1.1   關系型數據庫元素的表示	
3.1.2   對象的表示	
3.1.3   數據元素的表示	
3.2   記錄	
3.2.1   定長記錄的構造	
3.2.2   記錄首部	
3.2.3   定長記錄在塊中的放置	
習題		
3.3   塊和記錄地址的表示	
3.3.1   客戶機-服務器系統	
3.3.2   邏輯地址和結構地址	
3.3.3   指針混寫	
3.3.4   塊返回磁盤	
3.3.5   被固定的記錄和塊	
習題		
3.4   變長數據和記錄	
3.4.1   具有變長字段的記錄	
3.4.2   具有重復字段的記錄	
3.4.3   變格式的記錄	
3.4.4   不能裝入一個塊中的記錄	
3.4.5   BLOBS	
習題		
3.5   記錄的修改	
3.5.1   插入	
3.5.2   刪除	
3.5.3   修改	
習題		
3.6   小結	
3.7   參考文獻	
第4章   索引結構	
4.1   順序文件上的索引	
4.1.1   順序文件	
4.1.2   稠密索引	
4.1.3   稀疏索引	
4.1.4   多級索引	
4.1.5   重復鍵的索引	
4.1.6   數據修改期間的索引維護	
習題		
4.2   輔助索引	
4.2.1   輔助索引的設計	
4.2.2   輔助索引的應用	
4.2.3   輔助索引中的間接	
4.2.4   文檔檢索和倒排索引	
習題		
4.3   B樹	
4.3.1   B樹的結構	
4.3.2   B樹的應用	
4.3.3   B樹中的查找	
4.3.4   范圍查詢	
4.3.5   B樹的插入	
4.3.6   B樹的刪除	
4.3.7   B樹的效率	
習題		
4.4   散列表	
4.4.1   輔存散列表	
4.4.2   散列表的插入	
4.4.3   散列表的刪除	
4.4.4   散列表索引的效率	
4.4.5   可擴展散列表	
4.4.6   可擴展散列表的插入	
4.4.7   線性散列表	
4.4.8   線性散列表的插入	
習題		
4.5   小結	
4.6   參考文獻	
第5章   多維索引	
5.1   需要多維的應用	
5.1.1   地理信息系統	
5.1.2   數據立方體	
5.1.3   SQL多維查詢	
5.1.4   使用傳統索引執行范圍查詢	
5.1.5   利用傳統索引執行最鄰近查詢	
5.1.6   傳統索引的其他限制	
5.1.7   多維索引結構綜述	
習題		
5.2   多維數據的類散列結構	
5.2.1   網格文件	
5.2.2   網格文件的查找	
5.2.3   網格文件的插入	
5.2.4   網格文件的性能	
5.2.5   分段散列函數	
5.2.6   網格文件和分段散列的比較	
習題		
5.3   多維數據的類樹結構	
5.3.1   多鍵索引	
5.3.2   多鍵索引的性能	
5.3.3   kd樹	
5.3.4   kd樹的操作	
5.3.5   使kd樹適合輔存	
5.3.6   四叉樹	
5.3.7   R樹	
5.3.8   R樹的操作	
習題		
5.4   位圖索引	
5.4.1   位圖索引的誘因	
5.4.2   壓縮位圖	
5.4.3   游程長度編碼位向量的操作	
5.4.4   位圖索引的管理	
習題		
5.5   小結	
5.6   參考文獻	
第6章   查詢執行	
6.1   一種查詢代數	
6.1.1   并、交和差	
6.1.2   選擇操作符	
6.1.3   投影操作符	
6.1.4   關系的積	
6.1.5   連接	
6.1.6   消除重復	
6.1.7   分組和聚集	
6.1.8   排序操作符	
6.1.9   表達式樹	
習題		
6.2   物理查詢計劃操作符介紹	
6.2.1   掃描表	
6.2.2   掃描表時的排序	
6.2.3   物理操作符計算模型	
6.2.4   衡量代價的參數	
6.2.5   掃描操作符的I/O   代價	
6.2.6   實現物理操作符的迭代器	
6.3   數據庫操作的一趟算法	
6.3.1   一次多元組操作的一趟算法	
6.3.2   全關系的一元操作的一趟算法	
6.3.3   二元操作的一趟算法	
習題		
6.4   嵌套循環連接	
6.4.1   基于元組的嵌套循環連接	
6.4.2   基于元組的嵌套循環連接的迭代器	
6.4.3   基于塊的嵌套循環連接算法	
6.4.4   嵌套循環連接的分析	
6.4.5   迄今為止的算法的小結	
習題		
6.5   基于排序的兩趟算法	
6.5.1   利用排序去除重復	
6.5.2   利用排序進行分組和聚集	
6.5.3   基于排序的并算法	
6.5.4   基于排序的交和差算法	
6.5.5   基于排序的一個簡單的連接算法	
6.5.6   簡單排序連接的分析	
6.5.7   一種更有效的基于排序的連接	
6.5.8   基于排序的算法小結	
習題		
6.6   基于散列的兩趟算法	
6.6.1   通過散列劃分關系	
6.6.2   基于散列的消除重復算法	
6.6.3   基于散列的分組和聚集算法	
6.6.4   基于散列的并、交、差算法	
6.6.5   散列連接算法	
6.6.6   節省一些磁盤I/O	
6.6.7   基于散列的算法小結	
習題		
6.7   基于索引的算法	
6.7.1   聚簇和非聚簇索引	
6.7.2   基于索引的選擇	
6.7.3   使用索引的連接	
6.7.4   使用有排序索引的連接	
習題	
6.8   緩沖區管理	
6.8.1   緩沖區管理結構	
6.8.2   緩沖區管理策略
6.8.3   物理操作符選擇和緩沖區管理的關系	
習題		
6.9   使用超過兩趟的算法	
6.9.1   基于排序的多趟算法	
6.9.2   基于排序的多趟算法的性能	
6.9.3   基于散列的多趟算法	
6.9.4   基于散列的多趟算法的性能	
習題		
6.10   關系操作的并行算法	
6.10.1   并行模型	
6.10.2   一次一個元組的并行操作	
6.10.3   全關系操作的并行算法	
6.10.4   并行算法的性能	
習題		
6.10   小結	
6.11   參考文獻	
第7章   查詢編譯器	
7.1   語法分析	
7.1.1   語法分析與語法分析樹	
7.1.2   SQL的一個簡單子集的語法	
7.1.3   預處理器	
習題		
7.2   用于改進查詢計劃的代數定律	
7.2.1   交換律與結合律	
7.2.2   涉及選擇的定律	
7.2.3   下推選擇	
7.2.4   涉及投影的定律	
7.2.5   有關連接與積的定律	
7.2.6   有關重復消除的定律	
7.2.7   涉及分組與聚集的定律	
習題		
7.3   從語法分析樹到邏輯查詢計劃	
7.3.1   轉換成關系代數	
7.3.2   從條件中去除子查詢	
7.3.3   邏輯查詢計劃的改進	
7.3.4   結合/分配運算符的分組	
習題		
7.4   操作代價的估計	
7.4.1   中間關系大小的估計	
7.4.2   投影大小的估計	
7.4.3   選擇大小的估計	
7.4.4   連接大小的估計	
7.4.5   多連接屬性的自然連接	
7.4.6   多個關系的連接	
7.4.7   其他操作的大小估計	
習題		
7.5   基于代價的計劃選擇介紹	
7.5.1   大小參數估計值的獲取	
7.5.2   統計量的增量計算	
7.5.3   減少邏輯查詢計劃代價的啟發式	
7.5.4   枚舉物理計劃的方法	
習題		
7.6   連接順序的選擇	
7.6.1   連接的左右變元的意義	
7.6.2   連接樹	
7.6.3   左深連接樹	
7.6.4   通過動態編程來選擇連接順序和分組	
7.6.5   帶有更具體的代價函數的動態編程	
7.6.6   選擇連接順序的貪婪算法	
習題		
7.7   物理查詢計劃選擇的完成	
7.7.1   選取選擇方法	
7.7.2   選取連接方法	
7.7.3   流水線操作與物化	
7.7.4   一元流水線操作	
7.7.5   二元流水線操作	
7.7.6   物理查詢計劃的符號	
7.7.7   物理操作的順序	
習題		
7.8   小結	
7.9   參考文獻	
第8章   系統故障對策	
8.1   可回復操作的問題和模型	
8.1.1   故障模式	
8.1.2   關于事務的進一步討論	
8.1.3   事務的正確執行	
8.1.4   事務的原語操作	
習題		
8.2   undo日志	
8.2.1   日志記錄	
8.2.2   undo日志規則	
8.2.3   使用undo日志的恢復	
8.2.4   檢查點	
8.2.5   非靜止檢查點	
習題		
8.3   redo日志	
8.3.1   redo日志規則	
8.3.2   使用redo日志的恢復	
8.3.3   redo日志的檢查點	
8.3.4   使用帶檢查點的redo日志的恢復	
習題		
8.4   undo/redo日志	
8.4.1   undo/redo規則	
8.4.2   使用undo/redo日志的恢復	
8.4.3   undo/redo日志的檢查點	
習題		
8.5   防備介質故障	
8.5.1   備份	
8.5.2   非靜止轉儲	
8.5.3   使用備份和日志的恢復	
習題		
8.6   小結	
8.7   參考文獻	
第9章   并發控制	
9.1   串行調度和可串行化調度	
9.1.1   調度	
9.1.2   串行調度	
9.1.3   可串行化調度	
9.1.4   事務語義的影響	
9.1.5   事務和調度的一種記法	
習題		
9.2   沖突可串行性	
9.2.1   沖突	
9.2.2   優先圖及沖突可串行性判斷	
9.2.3   優先圖測試發揮作用的原因	
習題		
9.3   使用鎖的可串行性實現	
9.3.1   鎖	
9.3.2   封鎖調度器	
9.3.3   兩階段封鎖	
9.3.4   兩階段封鎖發揮作用的原因	
習題		
9.4   用多種鎖方式的封鎖系統	
9.4.1   共享鎖與排他鎖	
9.4.2   相容性矩陣	
9.4.3   鎖的升級	
9.4.4   更新鎖	
9.4.5   增量鎖	
習題		
9.5   封鎖調度器的一種體系結構	
9.5.1   插入鎖動作的調度器	
9.5.2   鎖表	
習題		
9.6   數據庫元素層次的管理	
9.6.1   多粒度的鎖	
9.6.2   警示鎖	
9.6.3   幻象與插入的正確處理	
習題		
9.7   樹協議	
9.7.1   基于樹的封鎖的動機	
9.7.2   訪問樹結構數據的規則	
9.7.3   樹協議發揮作用的原因	
習題		
9.8   使用時間戳的并發控制	
9.8.1   時間戳	
9.8.2   物理上不可實現的行為	
9.8.3   臟數據的問題	
9.8.4   基于時間戳調度的規則	
9.8.5   多版本時間戳	
9.8.6   時間戳與封鎖	
習題		
9.9   使用有效性確認的并發控制	
9.9.1   基于有效性確認的調度器的結構	
9.9.2   有效性確認規則	
9.9.3   三種并發控制機制的比較	
習題		
9.10   小結	
9.11   參考文獻	
第10章   再論事務管理	
10.1   讀未提交數據的事務	
10.1.1   臟數據問題	
10.1.2   級聯回滾	
10.1.3   回滾的管理	
10.1.4   成組提交	
10.1.5   邏輯日志	
習題		
10.2   視圖可串行性	
10.2.1   視圖等價性	
10.2.2   多重圖與視圖可串行性的判斷	
10.2.3   視圖可串行性的判斷	
習題		
10.3   死鎖處理	
10.3.1   超時死鎖檢測	
10.3.2   等待圖	
10.3.3   通過元素排序預防死鎖	
10.3.4   時間戳死鎖檢測	
10.3.5   死鎖管理方法的比較	
習題		
10.4   分布式數據庫	
10.4.1   數據的分布	
10.4.2   分布式事務	
10.4.3   數據復制	
10.4.4   分布式查詢優化	
習題		
10.5   分布式提交	
10.5.1   分布式原子性的支持	
10.5.2   兩階段提交	
10.5.3   分布式事務的恢復	
習題		
10.6   分布式封鎖	
10.6.1   集中封鎖系統	
10.6.2   分布式封鎖算法的代價模型	
10.6.3   封鎖多副本的元素	
10.6.4   主副本封鎖	
10.6.5   局部鎖構成的全局鎖	
習題		
10.7   長事務	
10.7.1   長事務的問題	
10.7.2   saga（系列記載）	
10.7.3   補償事務	
10.7.4   補償事務發揮作用的原因	
習題		
10.8   小結	
10.9   參考文獻	
第11章   信息集成	
11.1   信息集成的方式	
11.1.1   信息集成的問題	
11.1.2   聯邦數據庫系統	
11.1.3   數據倉庫	
11.1.4   Mediator	
習題		
11.2   基于Mediator系統的包裝器	
11.2.1   查詢模式的模板	
11.2.2   包裝器生成器	
11.2.3   過濾器	
11.2.4   其他在包裝器上進行的操作	
習題		
11.3   聯機分析處理	
11.3.1   OLAP應用	
11.3.2   OLAP數據的多維視圖	
11.3.3   星型模式	
11.3.4   切片和切塊	
習題		
11.4   數據立方體	
11.4.1   立方體操作符	
11.4.2   通過物化視圖實現立方體	
11.4.3   視圖的格	
習題		
11.5   數據挖掘	
11.5.1   數據挖掘的應用	
11.5.2   關聯規則的挖掘	
11.5.3   A-Priori算法	
11.6   小結	
11.7   參考文獻