譯者序
譯者簡介
齣版前言
第1章 DBMS係統概述
1.1 數據庫係統的發展
1.1.1 早期的數據庫管理係統
1.1.2 關係數據庫係統
1.1.3 越來越小的係統
1.1.4 越來越大的係統
1.1.5 信息集成
1.2 數據庫管理係統概述
1.2.1 數據定義語言命令
1.2.2 查詢處理概述
1.2.3 主存和緩衝區管理器
1.2.4 事務處理
1.2.5 查詢處理器
1.3 本書概述
1.4 數據庫模型和語言迴顧
1.4.1 關係模型迴顧
1.4.2 SQL迴顧
1.5 參考文獻
第一部分 數據庫係統實現
第2章 輔助存儲管理
2.1 存儲器層次
2.1.1 存儲器層次
2.1.2 在存儲器層次間傳送數據
2.1.3 易失和非易失存儲器
2.1.4 虛擬存儲器
2.1.5 習題
2.2 磁盤
2.2.1 磁盤結構
2.2.2 磁盤控製器
2.2.3 磁盤存取特性
2.2.4 習題
2.3 加速對輔助存儲器的訪問
2.3.1 計算的I/O模型
2.3.2 按柱麵組織數據
2.3.3 使用多個磁盤
2.3.4 磁盤鏡像
2.3.5 磁盤調度和電梯算法
2.3.6 預取和大規模緩衝
2.3.7 習題
2.4 磁盤故障
2.4.1 間斷性故障
2.4.2 校驗和
2.4.3 穩定存儲
2.4.4 穩定存儲的錯誤處理能力
2.4.5 從磁盤崩潰中恢復
2.4.6 作為冗餘技術的鏡像
2.4.7 奇偶塊
2.4.8 一種改進：RAID 5
2.4.9 多個盤崩潰時的處理
2.4.10 習題
2.5 組織磁盤上的數據
2.5.1 定長記錄
2.5.2 定長記錄在塊中的放置
2.5.3 習題
2.6 塊和記錄地址的錶示
2.6.1 客戶機-服務器係統中的地址
2.6.2 邏輯地址和結構地址
2.6.3 指針混寫
2.6.4 塊返迴磁盤
2.6.5 被釘住的記錄和塊
2.6.6 習題
2.7 變長數據和記錄
2.7.1 具有變長字段的記錄
2.7.2 具有重復字段的記錄
2.7.3 可變格式的記錄
2.7.4 不能裝入一個塊中的記錄
2.7.5 BLOB
2.7.6 列存儲
2.7.7 習題
2.8 記錄的修改
2.8.1 插入
2.8.2 刪除
2.8.3 修改
2.8.4 習題
2.9 小結
2.10 參考文獻
第3章 索引結構
3.1 索引結構基礎
3.1.1 順序文件
3.1.2 稠密索引
3.1.3 稀疏索引
3.1.4 多級索引
3.1.5 輔助索引
3.1.6 輔助索引的運用
3.1.7 輔助索引中的間接
3.1.8 文檔檢索和倒排索引
3.1.9 習題
3.2 B-樹
3.2.1 B-樹的結構
3.2.2 B-樹的應用
3.2.3 B-樹的查找
3.2.4 範圍查詢
3.2.5 B-樹的插入
3.2.6 B-樹的刪除
3.2.7 B-樹的效率
3.2.8 習題
3.3 散列錶
3.3.1 輔存散列錶
3.3.2 散列錶的插入
3.3.3 散列錶的刪除
3.3.4 散列錶索引的效率
3.3.5 可擴展散列錶
3.3.6 可擴展散列錶的插入
3.3.7 綫性散列錶
3.3.8 綫性散列錶的插入
3.3.9 習題
3.4 多維索引
3.4.1 多維索引的應用
3.4.2 利用傳統索引執行範圍查詢
3.4.3 利用傳統索引執行最近鄰查詢
3.4.4 多維索引結構綜述
3.5 多維數據的散列結構
3.5.1 網格文件
3.5.2 網格文件的查找
3.5.3 網格文件的插入
3.5.4 網格文件的性能
3.5.5 分段散列函數
3.5.6 網格文件和分段散列的比較
3.5.7 習題
3.6 多維數據的樹結構
3.6.1 多鍵索引
3.6.2 多鍵索引的性能
3.6.3 kd-樹
3.6.4 kd-樹的操作
3.6.5 使kd-樹適閤輔助存儲器
3.6.6 四叉樹
3.6.7 R-樹
3.6.8 R-樹的操作
3.6.9 習題
3.7 位圖索引
3.7.1 位圖索引的動機
3.7.2 壓縮位圖
3.7.3 分段長度編碼位嚮量的操作
3.7.4 位圖索引的管理
3.7.5 習題
3.8 小結
3.9 參考文獻
第4章 查詢執行
4.1 物理查詢計劃操作符介紹
4.1.1 掃描錶
4.1.2 掃描錶時的排序
4.1.3 物理操作符計算模型
4.1.4 衡量代價的參數
4.1.5 掃描操作符的I/O代價
4.1.6 實現物理操作符的迭代器
4.2 一趟算法
4.2.1 一次單個元組操作的一趟算法
4.2.2 整個關係的一元操作的一趟算法
4.2.3 二元操作的一趟算法
4.2.4 習題
4.3 嵌套循環連接
4.3.1 基於元組的嵌套循環連接
4.3.2 基於元組的嵌套循環連接的迭代器
4.3.3 基於塊的嵌套循環連接算法
4.3.4 嵌套循環連接的分析
4.3.5 迄今為止的算法的總結
4.3.6 習題
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.4.9 基於排序的算法的總結
4.4.10 習題
4.5 基於散列的兩趟算法
4.5.1 通過散列劃分關係
4.5.2 基於散列的消除重復算法
4.5.3 基於散列的分組和聚集算法
4.5.4 基於散列的並、交、差算法
4.5.5 散列連接算法
4.5.6 節省一些磁盤I/O
4.5.7 基於散列的算法的總結
4.5.8 習題
4.6 基於索引的算法
4.6.1 聚簇和非聚簇索引
4.6.2 基於索引的選擇
4.6.3 使用索引的連接
4.6.4 使用有序索引的連接
4.6.5 習題
4.7 緩衝區管理
4.7.1 緩衝區管理結構
4.7.2 緩衝區管理策略
4.7.3 物理操作符選擇和緩衝區管理的關係
4.7.4 習題
4.8 使用超過兩趟的算法
4.8.1 基於排序的多趟算法
4.8.2 基於排序的多趟算法的性能
4.8.3 基於散列的多趟算法
4.8.4 基於散列的多趟算法的性能
4.8.5 習題
4.9 小結
4.10 參考文獻
第5章 查詢編譯器
5.1 語法分析和預處理
5.1.1 語法分析與語法分析樹
5.1.2 SQL的一個簡單子集的語法
5.1.3 預處理器
5.1.4 預處理涉及視圖的查詢
5.1.5 習題
5.2 用於改進查詢計劃的代數定律
5.2.1 交換律與結閤律
5.2.2 涉及選擇的定律
5.2.3 下推選擇
5.2.4 涉及投影的定律
5.2.5 有關連接與積的定律
5.2.6 有關消除重復的定律
5.2.7 涉及分組與聚集的定律
5.2.8 習題
5.3 從語法分析樹到邏輯查詢計劃
5.3.1 轉換成關係代數
5.3.2 從條件中去除子查詢
5.3.3 邏輯查詢計劃的改進
5.3.4 可結閤/可分配的運算符的分組
5.3.5 習題
5.4 運算代價的估計
5.4.1 中間關係大小的估計
5.4.2 投影運算大小的估計
5.4.3 選擇運算大小的估計
5.4.4 連接運算大小的估計
5.4.5 多連接屬性的自然連接
5.4.6 多個關係的連接
5.4.7 其他運算大小的估計
5.4.8 習題
5.5 基於代價的計劃選擇介紹
5.5.1 大小參數估計值的獲取
5.5.2 統計量的計算
5.5.3 減少邏輯查詢計劃代價的啓發式估計
5.5.4 枚舉物理計劃的方法
5.5.5 習題
5.6 連接順序的選擇
5.6.1 連接的左右參數的意義
5.6.2 連接樹
5.6.3 左深連接樹
5.6.4 通過動態規劃來選擇連接順序和分組
5.6.5 帶有更具體的代價函數的動態規劃
5.6.6 選擇連接順序的貪婪算法
5.6.7 習題
5.7 物理查詢計劃選擇的完成
5.7.1 選取一個選擇方法
5.7.2 選取連接方法
5.7.3 流水操作與物化
5.7.4 一元流水運算
5.7.5 二元運算的流水操作
5.7.6 物理查詢計劃的符號
5.7.7 物理運算的排序
5.7.8 習題
5.8 小結
5.9 參考文獻
第6章 係統故障對策
6.1 可恢復操作的問題和模型
6.1.1 故障模式
6.1.2 關於事務的進一步討論
6.1.3 事務的正確執行
6.1.4 事務的原語操作
6.1.5 習題
6.2 undo日誌
6.2.1 日誌記錄
6.2.2 undo日誌規則
6.2.3 使用undo日誌的恢復
6.2.4 檢查點
6.2.5 非靜止檢查點
6.2.6 習題
6.3 redo日誌
6.3.1 redo日誌規則
6.3.2 使用redo日誌的恢復
6.3.3 redo日誌的檢查點
6.3.4 使用帶檢查點redo日誌的恢復
6.3.5 習題
6.4 undo/redo日誌
6.4.1 undo/redo規則
6.4.2 使用undo/redo日誌的恢復
6.4.3 undo/redo日誌的檢查點
6.4.4 習題
6.5 針對介質故障的防護
6.5.1 備份
6.5.2 非靜止轉儲
6.5.3 使用備份和日誌的恢復
6.5.4 習題
6.6 小結
6.7 參考文獻
第7章 並發控製
7.1 串行調度和可串行化調度
7.1.1 調度
7.1.2 串行調度
7.1.3 可串行化調度
7.1.4 事務語義的影響
7.1.5 事務和調度的一種記法
7.1.6 習題
7.2 衝突可串行化
7.2.1 衝突
7.2.2 優先圖及衝突可串行化判斷
7.2.3 優先圖測試發揮作用的原因
7.2.4 習題
7.3 使用鎖的可串行化實現
7.3.1 鎖
7.3.2 封鎖調度器
7.3.3 兩階段封鎖
7.3.4 兩階段封鎖發揮作用的原因
7.3.5 習題
7.4 有多種鎖模式的封鎖係統
7.4.1 共享鎖與排他鎖
7.4.2 相容性矩陣
7.4.3 鎖的升級
7.4.4 更新鎖
7.4.5 增量鎖
7.4.6 習題
7.5 封鎖調度器的一種體係結構
7.5.1 插入鎖動作的調度器
7.5.2 鎖錶
7.5.3 習題
7.6 數據庫元素的層次
7.6.1 多粒度的鎖
7.6.2 警示鎖
7.6.3 幻象與插入的正確處理
7.6.4 習題
7.7 樹協議
7.7.1 基於樹的封鎖的動機
7.7.2 訪問樹結構數據的規則
7.7.3 樹協議發揮作用的原因
7.7.4 習題
7.8 使用時間戳的並發控製
7.8.1 時間戳
7.8.2 事實上不可實現的行為
7.8.3 髒數據的問題
7.8.4 基於時間戳調度的規則
7.8.5 多版本時間戳
7.8.6 時間戳與封鎖
7.8.7 習題
7.9 使用有效性確認的並發控製
7.9.1 基於有效性確認調度器的結構
7.9.2 有效性確認規則
7.9.3 三種並發控製機製的比較
7.9.4 習題
7.10 小結
7.11 參考文獻
第8章 再論事務管理
8.1 可串行性和可恢復性
8.1.1 髒數據問題
8.1.2 級聯迴滾
8.1.3 可恢復的調度
8.1.4 避免級聯迴滾的調度
8.1.5 基於鎖對迴滾的管理
8.1.6 成組提交
8.1.7 邏輯日誌
8.1.8 從邏輯日誌中恢復
8.1.9 習題
8.2 死鎖
8.2.1 超時死鎖檢測
8.2.2 等待圖
8.2.3 通過元素排序預防死鎖
8.2.4 通過時間戳檢測死鎖
8.2.5 死鎖管理方法的比較
8.2.6 習題
8.3 長事務
8.3.1 長事務的問題
8.3.2 saga（係列記載）
8.3.3 補償事務
8.3.4 補償事務發揮作用的原因
8.3.5 習題
8.4 小結
8.5 參考文獻
第9章 並行與分布式數據庫
9.1 關係的並行算法
9.1.1 並行模型
9.1.2 一次一個元組的操作的並行
9.1.3 整個關係的操作的並行算法
9.1.4 並行算法的性能
9.1.5 習題
9.2 mapreduce並行架構
9.2.1 存儲模式
9.2.2 映射函數
9.2.3 歸約函數
9.2.4 習題
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.4.6 為什麼完全化簡算法有效
9.4.7 習題
9.5 分布式提交
9.5.1 支持分布式原子性
9.5.2 兩階段提交
9.5.3 分布式事務的恢復
9.5.4 習題
9.6 分布式封鎖
9.6.1 集中封鎖係統
9.6.2 分布式封鎖算法的代價模型
9.6.3 封鎖多副本的元素
9.6.4 主副本封鎖
9.6.5 局部鎖構成的全局鎖
9.6.6 習題
9.7 對等分布式查找
9.7.1 對等網絡
9.7.2 分布式散列問題
9.7.3 分布式散列的集中式解決方案
9.7.4 帶弦的圓
9.7.5 帶弦的圓上的鏈接
9.7.6 使用手指錶查找
9.7.7 加入新結點
9.7.8 當一個端離開網絡
9.7.9 當一個端崩潰瞭
9.7.10 習題
9.8 小結
9.9 參考文獻
第二部分 現代數據庫係統專題
第10章 信息集成
10.1 信息集成介紹
10.1.1 為什麼要進行信息集成
10.1.2 異質性問題
10.2 信息集成的方式
10.2.1 聯邦數據庫係統
10.2.2 數據倉庫
10.2.3 mediator
10.2.4 習題
10.3 基於mediator的係統中的包裝器
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.4.5 習題
10.5 優化mediator查詢
10.5.1 簡化的修飾符記號
10.5.2 獲得子目標的迴答
10.5.3 Chain算法
10.5.4 在mediator上結閤並視圖
10.5.5 習題
10.6 以局部作為視圖的mediator
10.6.1 LAV mediator的動機
10.6.2 LAV mediator的術語
10.6.3 擴展解決方案
10.6.4 閤取查詢的包含
10.6.5 為什麼包含映射測試有效
10.6.6 發現mediator查詢的解決方法
10.6.7 為什麼LMSS定理能成立
10.6.8 習題
10.7 實體解析
10.7.1 決定是否記錄代錶一個共同實體
10.7.2 閤並相似記錄
10.7.3 相似性和閤並函數的有用性質
10.7.4 ICAR記錄的RSwoosh算法
10.7.5 為什麼RSwoosh算法會有效
10.7.6 實體解析的其他方法
10.7.7 習題
10.8 小結
10.9 參考文獻
第11章 數據挖掘
11.1 頻繁項集挖掘
11.1.1 市場-購物籃模型
11.1.2 基本定義
11.1.3 關聯規則
11.1.4 頻繁項集的計算模型
11.1.5 習題
11.2 發現頻繁項集的算法
11.2.1 頻繁項集的分布
11.2.2 尋找頻繁項集的樸素算法
11.2.3 APriori算法
11.2.4 APriori算法的實現
11.2.5 更好地使用主存
11.2.6 何時使用PCY算法
11.2.7 多級算法
11.2.8 習題
11.3 發現近似的商品
11.3.1 相似度的Jaccard度量
11.3.2 Jaccard相似度的應用
11.3.3 最小散列
11.3.4 最小散列與Jaccard相似度
11.3.5 為什麼能用最小散列估計相似度
11.3.6 最小散列的實現
11.3.7 習題
11.4 局部敏感散列
11.4.1 LSH實例：實體分辨
11.4.2 標簽的局部敏感散列
11.4.3 最小散列法和局部敏感散列的結閤
11.4.4 習題
11.5 大規模數據的聚簇
11.5.1 聚簇的應用
11.5.2 距離的定義
11.5.3 凝聚式聚簇
11.5.4 kMeans算法
11.5.5 大規模數據的kMeans方法
11.5.6 內存中滿載點後的處理過程
11.5.7 習題
11.6 小結
11.7 參考文獻
第12章 數據庫係統與互聯網
12.1 搜索引擎體係結構
12.1.1 搜索引擎的組成
12.1.2 Web爬蟲
12.1.3 搜索引擎中的查詢處理
12.1.4 對網頁進行排名
12.2 用於識彆重要網頁的PageRank
12.2.1 PageRank的直觀思想
12.2.2 PageRank的遞歸公式——初步嘗試
12.2.3 爬蟲陷阱和死角
12.2.4 考慮爬蟲陷阱和死角的PageRank
12.2.5 習題
12.3 特定主題的PageRank
12.3.1 “遠距離移動”集
12.3.2 計算主題相關的PageRank
12.3.3 鏈接作弊
12.3.4 主題相關的PageRank和鏈接作弊
12.3.5 習題
12.4 數據流
12.4.1 數據流管理係統
12.4.2 數據流應用
12.4.3 數據流數據模型
12.4.4 數據流轉換為關係
12.4.5 關係轉換為數據流
12.4.6 習題
12.5 數據流挖掘
12.5.1 動機
12.5.2 統計二進製位數
12.5.3 統計不同元素的個數
12.5.4 習題
12.6 小結
12.7 參考文獻
· · · · · · (收起)