內容簡介
本書是關於資料庫系統實現方面內容最為全面的著作之一，是美國史丹福大學計算機科學專業資料庫系列課程第二門課程的指定教材。史丹福大學計算機科學專業資料庫系列課程第一門課程的內容包括資料庫設計和資料庫編程。本書的後兩位作者JeffreyD.UIIman和JenniferWidom為該課程編寫的教材《資料庫系統基礎教程》（AFirstCourseinDatabaseSystems）第3版的中文翻譯版和英文影印版已由機械工業出版社出版。本書內容深入且全面，技術實用且先進，敘述深入淺
資料庫系統實現作者簡介
加西亞－莫利納（HectorGarcia-Molina）史丹福大學計算機科學與電子工程系的LeonardBosack和SandraLerner教授。他在資料庫系統、分散式系統和數字圖書館領域中發表了大量論文。研究興趣包括分散式計算系統、資料庫系統和數字圖書館。他是ACM會士、美國藝術與科學院會士和美國國家工程院成員。他在1999年獲得TACMSIGMOD創新獎。目錄
出版者的話譯者序
譯者簡介
出版前言
第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.2sql回顧
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一種改進：raid5
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.5blob
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.2b-樹
3.2.1b-樹的結構
3.2.2b-樹的套用
3.2.3b-樹的查找
3.2.4範圍查詢
3.2.5b-樹的插入
3.2.6b-樹的刪除
3.2.7b-樹的效率
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.3kd-樹
3.6.4kd-樹的操作
3.6.5使kd-樹適合輔助存儲器
3.6.6四叉樹
3.6.7r-樹
3.6.8r-樹的操作
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.2sql的一個簡單子集的語法
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.2undo日誌
6.2.1日誌記錄
6.2.2undo日誌規則
6.2.3使用undo日誌的恢復
6.2.4檢查點
6.2.5非靜止檢查點
6.2.6習題
6.3redo日誌
6.3.1redo日誌規則
6.3.2使用redo日誌的恢復
6.3.3redo日誌的檢查點
6.3.4使用帶檢查點redo日誌的恢復
6.3.5習題
6.4undo/redo日誌
6.4.1undo/redo規則
6.4.2使用undo/redo日誌的恢復
6.4.3undo/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.2saga（系列記載）
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.2map?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.3mediator
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.3chain算法
10.5.4在mediator上結合併視圖
10.5.5習題
10.6以局部作為視圖的mediator
10.6.1lavmediator的動機
10.6.2lavmediator的術語
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.4icar記錄的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.3a?priori算法
11.2.4a?priori算法的實現
11.2.5更好地使用主存
11.2.6何時使用pcy算法
11.2.7多級算法
11.2.8習題
11.3發現近似的商品
11.3.1相似度的jaccard度量
11.3.2jaccard相似度的套用
11.3.3最小散列
11.3.4最小散列與jaccard相似度
11.3.5為什麼能用最小散列估計相似度
11.3.6最小散列的實現
11.3.7習題
11.4局部敏感散列
11.4.1lsh實例：實體分辨
11.4.2標籤的局部敏感散列
11.4.3最小散列法和局部敏感散列的結合
11.4.4習題
11.5大規模數據的聚簇
11.5.1聚簇的套用
11.5.2距離的定義
11.5.3凝聚式聚簇
11.5.4k?means算法
11.5.5大規模數據的k?means方法
11.5.6記憶體中滿載點後的處理過程
11.5.7習題
11.6小結
11.7參考文獻
第12章資料庫系統與網際網路
12.1搜尋引擎體系結構
12.1.1搜尋引擎的組成
12.1.2web爬蟲
12.1.3搜尋引擎中的查詢處理
12.1.4對網頁進行排名
12.2用於識別重要網頁的pagerank
12.2.1pagerank的直觀思想
12.2.2pagerank的遞歸公式——初步嘗試
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參考文獻
