本書特色
使用人們普遍關注的、現實世界的例子提高可讀性SQL PSM(持久存儲模組)、JDBC(Java接口)和SQL CLI(ODBC或開放式資料庫連線)等內容為本書所特有用ODMG標準ODL介紹了面向對象設計，用SQL—99標準介紹了對象—關係設計藉助關係代數，講述了查詢處理和查詢最佳化的擴展內容討論了信息集成技術，包括數據倉庫、協調器、OLAP、數據立方體和數據挖掘技術解釋了很多重要的專門技術，如RAID糟的錯誤糾正、點陣圖索引、統計數據的套用以及指針混合
作 者 簡 介
作者: Jeffrey D. Ullman
1996年Sigmod貢獻獎和1998年Karl V. Karstrom傑出教育家獎獲得者。 Jeffrey D. Ullman是史丹福大學的Stanford W. Ascherman計算機科學教授。他作為作者或合作者出版了15本著作，發表了170篇技術論文，其中包括《A First Course in Database Systems》（Prentice Hall 出版社，1997）和《Elements of ML Programming》（Prentice Hall 出版社，1998）。他的研究興趣包括資料庫理論、資料庫集成、數據挖掘和利用信息基礎設施進行教育。他獲得了Guggenheim Fellowship等多種獎勵，並被推選進入國家工程院。
作者: Jennifer Widom
Jennifer Widom於1987年在康奈爾大學獲得計算機科學博士學位，現為史丹福大學計算機科學與電氣工程系教授。她是ACM Fellow、Guggenheim Fellow和美國國家工程院成員，並且是多個編輯委員會、程式委員會和顧問委員會的成員。她的研究興趣包括半結構化數據的資料庫系統和XML、數據倉庫以及主動資料庫系統。
圖書概述
本書是史丹福大學計算機科學專業資料庫系列課程教科書。書中對資料庫系統基本原理以及資料庫系統實現進行了深入闡述，並對ODL、SQL、關係代數、面向對象查詢、事務管理、並發控制等內容展開具體討論。對該領域內的一些最新技術，諸如數據倉庫、數據控掘、數據立方體系統等，也給予了介紹。
本書適合作為高等院校計算機專業研究生的教材或本科生的教學參考書，也適合作為從事相關研究或開發工作的專業技術人員的高級參考資料。
本書是史丹福大學知名計算機科學家Hector Garcla-Molina、Jeffrey D．Ullman和Jennifer Widom合作編寫的一本資料庫系統引論書籍。書的前半部分從資料庫設計者、用戶和應用程式員的角度深入地介紹了資料庫。包括最新資料庫標準SQL—1999、SQL PSM、SQL CLI、ODL和XML，相比其他大多數書籍，更多地介紹了SQL內容。本書的後半部分是從DBMS實現的角度來介紹資料庫的，覆蓋了這個領域內的基本技術，並且比其他大多數書籍更多地介紹了查詢最佳化。高級論題包括多維和點陣圖索引、分散式事務處理和信息集成技術。本書既可用作大學教科書，也可作為該領域專業人員的參考書。
圖書目錄
出版者的話
專家指導委員會
譯者序
作者簡介
前言
第1章 資料庫系統世界 1
1.1 資料庫系統的發展 1
1.1.1 早期的資料庫管理系統 1
1.1.2 關係資料庫系統 2
1.1.3 越來越小的系統 3
1.1.4 越來越大的系統 4
1.1.5 客戶-伺服器和多層體系結構 4
1.1.6 多媒體數據 5
1.1.7 信息集成 5
1.2 資料庫管理系統概述 6
1.2.1 數據定義語言命令 6
1.2.2 查詢處理概述 6
1.2.3 存儲器和緩衝區管理器 8
1.2.4 事務處理 8
1.2.5 查詢處理器 9
1.3 資料庫系統研究概述 9
1.3.1 資料庫設計 10
1.3.2 資料庫程式設計 10
1.3.3 資料庫系統實現 11
1.3.4 信息集成概述 12
1.4 小結 12
1.5 參考文獻 12
第2章 實體-聯繫數據模型 15
2.1 e/r模型的要素 15
2.1.1 實體集 15
2.1.2 屬性 16
2.1.3 聯繫 16
2.1.4 實體－聯繫圖 16
2.1.5 e/r圖實例 17
2.1.6 二元e/r聯繫的多樣性 17
2.1.7 多路聯繫 18
2.1.8 聯繫中的角色 18
2.1.9 聯繫的屬性 19
2.1.10 多路聯繫到二元聯繫的轉換 20
2.1.11 e/r模型中的子類 21
2.1.12 習題 22
2.2 設計原則 24
2.2.1 忠實性 24
2.2.2 避免冗餘 24
2.2.3 簡單性考慮 25
2.2.4 選擇正確的聯繫 25
2.2.5 選擇正確的元素種類 26
2.2.6 習題 27
2.3 約束的建模 28
2.3.1 約束的分類 29
2.3.2 e/r模型中的鍵 29
2.3.3 e/r模型中鍵的表示 30
2.3.4 單值約束 31
2.3.5 引用完整性 31
2.3.6 e/r圖中的引用完整性 31
2.3.7 其他類型的約束 32
2.3.8 習題 32
2.4 弱實體集 33
2.4.1 弱實體集的來源 33
2.4.2 弱實體集的要求 34
2.4.3 弱實體集的符號 35
2.4.4 習題 35
2.5 小結 35
2.6 參考文獻 36
第3章 關係數據模型 37
3.1 關係模型的基礎 37
3.1.1 屬性 37
3.1.2 模式 37
3.1.3 元組 38
3.1.4 域 38
3.1.5 關係的等價描述 38
3.1.6 關係實例 38
3.1.7 習題 39
3.2 從e/r圖到關係設計 39
3.2.1 實體集到關係的轉化 40
3.2.2 e/r聯繫到關係的轉化 41
3.2.3 組合關係 42
3.2.4 處理弱實體集 43
3.2.5 習題 45
3.3 子類結構到關係的轉化 46
3.3.1 e/r方式轉化 46
3.3.2 面向對象的方法 47
3.3.3 使用空值組合關係 48
3.3.4 各種方法的比較 48
3.3.5 習題 48
3.4 函式依賴 49
3.4.1 函式依賴的定義 50
3.4.2 關係的鍵 50
3.4.3 超鍵 52
3.4.4 找出關係中的鍵 52
3.4.5 習題 53
3.5 函式依賴的規則 54
3.5.1 分解/結合規則 54
3.5.2 平凡函式依賴 55
3.5.3 計算屬性的閉包 55
3.5.4 為什麼能用閉包算法 57
3.5.5 傳遞規則 58
3.5.6 函式依賴的閉包集合 59
3.5.7 投影函式依賴 59
3.5.8 習題 60
3.6 關係資料庫模式設計 61
3.6.1 異常 62
3.6.2 分解關係 62
3.6.3 boyce-codd範式 63
3.6.4 分解為 bcnf 65
3.6.5 從分解中恢覆信息 68
3.6.6 第三範式 69
3.6.7 習題 71
3.7 多值依賴 71
3.7.1 屬性獨立及伴隨其產生的冗餘 71
3.7.2 多值依賴的定義 72
3.7.3 多值依賴的推論 73
3.7.4 第四範式 74
3.7.5 分解到第四範式 75
3.7.6 範式間的聯繫 76
3.7.7 習題 76
3.8 小結 77
3.9 參考文獻 78
第4章 其他數據模型 81
4.1 面向對象概念的複習 81
4.1.1 類型系統 82
4.1.2 類與對象 82
4.1.3 對象標識 82
4.1.4 方法 82
4.1.5 類的層次 83
4.2 odl簡介 83
4.2.1 面向對象設計 83
4.2.2 類聲明 84
4.2.3 odl中的屬性 84
4.2.4 odl中的聯繫 85
4.2.5 反向聯繫 86
4.2.6 聯繫的多重性 87
4.2.7 odl中的方法 88
4.2.8 odl中的類型 89
4.2.9 習題 90
4.3 odl中的其他概念 91
4.3.1 odl中的多路聯繫 92
4.3.2 odl中的子類 92
4.3.3 odl中的多繼承 93
4.3.4 範圍 94
4.3.5 odl中鍵聲明 94
4.3.6 習題 96
4.4 從odl設計到關係設計 96
4.4.1 從odl屬性到關係屬性 97
4.4.2 類中的非原子類型屬性 97
4.4.3 集合類型屬性的表示 98
4.4.4 其他類型構建器的表示 99
4.4.5 odl中聯繫的表示 100
4.4.6 如果沒有鍵會怎樣? 102
4.4.7 習題 102
4.5 對象關係模型 103
4.5.1 從關係到對象關係 104
4.5.2 嵌套關係 104
4.5.3 引用 105
4.5.4 面向對象與對象關係的比較 106
4.5.5 odl設計到對象關係設計的轉化 107
4.5.6 習題 107
4.6 半結構化數據 107
4.6.1 為何需要半結構化數據模型 108
4.6.2 半結構化數據表示 108
4.6.3 信息集成與半結構化數據 109
4.6.4 習題 110
4.7 xml及其數據模型 110
4.7.1 語義標籤 111
4.7.2 格式規範的xml 111
4.7.3 文檔類型定義（dtd） 112
4.7.4 使用dtd 113
4.7.5 屬性列表 114
4.7.6 習題 115
4.8 小結 116
4.9 參考文獻 116
第5章 關係代數 119
5.1 一個資料庫模式的例子 119
5.2 關係代數操作 120
5.2.1 關係代數基礎 121
5.2.2 關係中的集合操作 121
5.2.3 投影 122
5.2.4 選擇 123
5.2.5 笛卡兒積 124
5.2.6 自然連線 124
5.2.7 q連線 125
5.2.8 使用組合操作生成查詢 126
5.2.9 重命名 127
5.2.10 依賴的和非依賴的操作 128
5.2.11 關係代數表達式中的線性符號 129
5.2.12 習題 129
5.3 包上的關係操作 134
5.3.1 為什麼採用包 134
5.3.2 包的並、交、差 135
5.3.3 包的投影操作 136
5.3.4 包的選擇 137
5.3.5 包的笛卡兒積 137
5.3.6 包的連線 137
5.3.7 習題 138
5.4 關係代數的擴展操作 139
5.4.1 消除重複 139
5.4.2 聚集操作符 140
5.4.3 分組 140
5.4.4 分組操作符 141
5.4.5 擴展的投影操作符 142
5.4.6 排序操作符 143
5.4.7 外連線 143
5.4.8 習題 144
5.5 關係的約束 145
5.5.1 作為約束語言的關係代數 145
5.5.2 引用完整性約束 146
5.5.3 其他的約束舉例 147
5.5.4 習題 148
5.6 小結 149
5.7 參考文獻 149
第6章 資料庫語言sql 151
6.1 sql中的簡單查詢 151
6.1.1 sql中的投影 152
6.1.2 sql中的選擇 154
6.1.3 字元串比較 155
6.1.4 日期和時間 156
6.1.5 空值和涉及空值的比較 157
6.1.6 布爾值unknown 158
6.1.7 輸出排序 159
6.1.8 習題 159
6.2 多個關係上的查詢 160
6.2.1 sql中的積和連線 161
6.2.2 避免屬性歧義 161
6.2.3 元組變數 162
6.2.4 多關係查詢的解釋 163
6.2.5 查詢的並、交、差 165
6.2.6 習題 166
6.3 子查詢 167
6.3.1 產生標量值的子查詢 167
6.3.2 含有關係的條件表達式 168
6.3.3 含有元組的條件表達式 169
6.3.4 關聯子查詢 170
6.3.5 from子句中的子查詢 171
6.3.6 sql 的連線表達式 171
6.3.7 自然連線 172
6.3.8 外連線 173
6.3.9 習題 174
6.4 全關係操作 176
6.4.1 消除重複 176
6.4.2 交、並、差中的重複 176
6.4.3 sql 中的分組和聚集 177
6.4.4 聚集操作符 177
6.4.5 分組 178
6.4.6 having子句 179
6.4.7 習題 180
6.5 資料庫更新 181
6.5.1 插入 181
6.5.2 刪除 183
6.5.3 更新 183
6.5.4 習題 184
6.6 sql中的關係模式定義 185
6.6.1 數據類型 185
6.6.2 簡單表定義 186
6.6.3 修改關係模式 186
6.6.4 默認值 187
6.6.5 索引 187
6.6.6 索引選擇簡介 188
6.6.7 習題 190
6.7 視圖定義 191
6.7.1 視圖聲明 191
6.7.2 視圖查詢 192
6.7.3 重命名屬性 193
6.7.4 視圖更新 193
6.7.5 涉及視圖的查詢解釋 195
6.7.6 習題 197
6.8 小結 197
6.9 參考文獻 198
第7章 約束和觸發器 201
7.1 鍵和外鍵 201
7.1.1 主鍵聲明 201
7.1.2 用unique聲明鍵 202
7.1.3 強制鍵約束 203
7.1.4 外鍵約束聲明 203
7.1.5 維護引用完整性 204
7.1.6 延遲約束檢查 205
7.1.7 習題 207
7.2 屬性和元組上的約束 208
7.2.1 非空值約束 208
7.2.2 基於屬性的 check 約束 209
7.2.3 基於元組的 check 約束 210
7.2.4 習題 211
7.3 修改約束 212
7.3.1 給約束命名 212
7.3.2 修改表上約束 212
7.3.3 習題 213
7.4 模式層的約束和觸發器 214
7.4.1 斷言 214
7.4.2 事件-條件-動作規則 216
7.4.3 sql中的觸發器 216
7.4.4 替換觸發器（instead of triggers） 219
7.4.5 習題 219
7.5 小結 221
7.6 參考文獻 221
第8章 sql 的系統特徵 223
8.1 編程環境下的 sql 223
8.1.1 阻抗不匹配問題 224
8.1.2 sql/宿主語言接口 224
8.1.3 declare節 225
8.1.4 使用共享變數 225
8.1.5 單元組選擇語句 226
8.1.6 游標 226
8.1.7 游標修改 229
8.1.8 防止並發更新 229
8.1.9 卷型游標 230
8.1.10 動態sql 231
8.1.11 習題 232
8.2 模式中的存儲過程 233
8.2.1 創建psm函式和過程 233
8.2.2 psm中的簡單語句格式 234
8.2.3 分支語句 235
8.2.4 psm中的查詢 236
8.2.5 psm中的循環 236
8.2.6 for 循環 238
8.2.7 psm的異常處理 238
8.2.8 使用psm函式和過程 240
8.2.9 習題 240
8.3 sql 環境 242
8.3.1 環境 242
8.3.2 模式 242
8.3.3 目錄 243
8.3.4 sql 環境中的客戶和伺服器 244
8.3.5 連線 244
8.3.6 會話 245
8.3.7 模組 245
8.4 使用調用層接口 245
8.4.1 sql/cli簡介 246
8.4.2 處理語句 247
8.4.3 從查詢結果中取數據 248
8.4.4 向查詢傳遞參數 250
8.4.5 習題 250
8.5 java資料庫連線 250
8.5.1 jdbc 簡介 250
8.5.2 jdbc 中的創建語句 251
8.5.3 jdbc 中的游標操作 252
8.5.4 參數傳遞 252
8.5.5 習題 253
8.6 sql 中的事務 253
8.6.1 可串列性 253
8.6.2 原子性 255
8.6.3 事務 256
8.6.4 唯讀事務 257
8.6.5 讀髒數據 258
8.6.6 其他隔離級別 259
8.6.7 習題 260
8.7 sql 中的安全機制和用戶認證 261
8.7.1 許可權 261
8.7.2 創建許可權 262
8.7.3 檢查許可權的處理 263
8.7.4 授權 264
8.7.5 授權圖 265
8.7.6 銷權 266
8.7.7 習題 268
8.8 小結 269
8.9 參考文獻 270
第9章 面向對象查詢語言 271
9.1 oql簡介 271
9.1.1 一個面向對象的電影例子 271
9.1.2 路徑表達式 271
9.1.3 oql 中 select-from-where 表
達式 273
9.1.4 修改結果的類型 273
9.1.5 複雜輸出類型 274
9.1.6 子查詢 275
9.1.7 習題 276
9.2 oql 表達式的其他格式 278
9.2.1 量詞表達式 278
9.2.2 聚集表達式 279
9.2.3 分組表達式 279
9.2.4 having 子句 281
9.2.5 並、交和差操作 281
9.2.6 習題 282
9.3 oql 中對象的賦值與創建 283
9.3.1 宿主語言變數的賦值 283
9.3.2 集合元素的提取 283
9.3.3 獲取集合的每一個成員 283
9.3.4 oql 中的常量 284
9.3.5 創建新對象 285
9.3.6 習題 286
9.4 sql 中的用戶定義類型 286
9.4.1 在sql 中定義類型 286
9.4.2 用戶定義類型中的方法 287
9.4.3 用udt聲明關係 288
9.4.4 引用 288
9.4.5 習題 290
9.5 對象關係數據上的操作 290
9.5.1 引用的跟隨（following refe-
rence） 290
9.5.2 訪問udt類型元組的屬性 291
9.5.3 生成器和轉換器函式 292
9.5.4 udt類型聯繫的排序 293
9.5.5 習題 294
9.6 小結 295
9.7 參考文獻 295
第10章 邏輯查詢語言 297
10.1 一種關係邏輯 297
10.1.1 謂詞和原子 297
10.1.2 算術原子 297
10.1.3 datalog 規則和查詢 298
10.1.4 datalog 規則的意義 299
10.1.5 擴展謂詞和內涵謂詞 300
10.1.6 datalog規則套用於包 301
10.1.7 習題 302
10.2 從關係代數到datalog 302
10.2.1 交 302
10.2.2 並 302
10.2.3 差 303
10.2.4 投影 303
10.2.5 選擇 303
10.2.6 積 305
10.2.7 連線 305
10.2.8 用 datalog 模擬多重操作 306
10.2.9 習題 307
10.3 datalog 的遞歸編程 308
10.3.1 遞歸規則 309
10.3.2 計算遞歸datalog 規則 309
10.3.3 遞歸規則中的非 313
10.3.4 習題 315
10.4 sql 中的遞歸 316
10.4.1 在sql 中定義idb關係 316
10.4.2 分層非 318
10.4.3 有問題的遞歸sql表達式 319
10.4.4 習題 321
10.5 小結 322
10.6 參考文獻 322
第11章 數據存儲 325
11.1 megatron 2002資料庫系統 325
11.1.1 megatron 2002實現細節 325
11.1.2 megatron 2002如何執行查詢 326
11.1.3 megatron 2002有什麼問題 327
11.2 存儲器層次 327
11.2.1 高速緩衝存儲器 327
11.2.2 主存儲器 328
11.2.3 虛擬存儲器 329
11.2.4 二級存儲器 329
11.2.5 三級存儲器 330
11.2.6 易失和非易失存儲器 332
11.2.7 習題 332
11.3 磁碟 332
11.3.1 磁碟結構 332
11.3.2 磁碟控制器 334
11.3.3 磁碟存儲特性 334
11.3.4 磁碟訪問特性 335
11.3.5 塊的寫操作 338
11.3.6 塊的修改 338
11.3.7 習題 338
11.4 有效使用二級存儲器 339
11.4.1 計算的i/o模型 339
11.4.2 二級存儲器中的數據排序 340
11.4.3 歸併排序 341
11.4.4 兩趟多路歸併排序 342
11.4.5 更大型關係的多路歸併 343
11.4.6 習題 344
11.5 加速二級存儲的訪問 345
11.5.1 按柱面組織數據 346
11.5.2 使用多個磁碟 346
11.5.3 磁碟鏡像 347
11.5.4 磁碟調度和電梯算法 348
11.5.5 預取和大規模緩衝 350
11.5.6 對策略和折中的小結 351
11.5.7 習題 352
11.6 磁碟故障 353
11.6.1 間斷性故障 353
11.6.2 校驗和 353
11.6.3 穩定存儲 354
11.6.4 穩定存儲的錯誤處理能力 354
11.6.5 習題 355
11.7 從磁碟崩潰中恢復 355
11.7.1 磁碟的故障模型 355
11.7.2 鏡像冗餘技術 356
11.7.3 奇偶塊 356
11.7.4 一種改進：raid 5 359
11.7.5 多個盤崩潰時的處理 359
11.7.6 習題 361
11.8 小結 363
11.9 參考文獻 364
第12章 數據元素的表示 365
12.1 數據元素和欄位 365
12.1.1 關係資料庫元素的表示 365
12.1.2 對象的表示 366
12.1.3 數據元素的表示 366
12.2 記錄 368
12.2.1 定長記錄的構造 368
12.2.2 記錄首部 370
12.2.3 定長記錄在塊中的放置 371
12.2.4 習題 371
12.3 塊和記錄地址的表示 372
12.3.1 客戶-伺服器系統 372
12.3.2 邏輯地址和結構地址 373
12.3.3 指針混寫 374
12.3.4 塊返回磁碟 376
12.3.5 被固定的記錄和塊 377
12.3.6 習題 378
12.4 變長數據和記錄 379
12.4.1 具有變長欄位的記錄 379
12.4.2 具有重複欄位的記錄 380
12.4.3 可變格式記錄 381
12.4.4 不能裝入一個塊中的記錄 382
12.4.5 blobs 383
12.4.6 習題 383
12.5 記錄的修改 384
12.5.1 插入 384
12.5.2 刪除 385
12.5.3 更新 386
12.5.4 習題 386
12.6 小結 387
12.7 參考文獻 387
第13章 索引結構 389
13.1 順序檔案上的索引 389
13.1.1 順序檔案 390
13.1.2 稠密索引 390
13.1.3 稀疏索引 391
13.1.4 多級索引 392
13.1.5 重複查找鍵的索引 393
13.1.6 數據修改期間的索引維護 395
13.1.7 習題 398
13.2 輔助索引 399
13.2.1 輔助索引的設計 399
13.2.2 輔助索引的套用 400
13.2.3 輔助索引的間接性 401
13.2.4 文檔檢索和倒排索引 403
13.2.5 習題 405
13.3 b樹 406
13.3.1 b樹的結構 406
13.3.2 b樹的套用 409
13.3.3 b樹中的查找 410
13.3.4 範圍查詢 410
13.3.5 b樹的插入 411
13.3.6 b樹的刪除 413
13.3.7 b樹的效率 415
13.3.8 習題 416
13.4 散列表 417
13.4.1 輔存散列表 418
13.4.2 散列表的插入 418
13.4.3 散列表的刪除 419
13.4.4 散列表索引的效率 419
13.4.5 可擴展散列表 419
13.4.6 可擴展散列表的插入 420
13.4.7 線性散列表 421
13.4.8 線性散列表的插入 422
13.4.9 習題 423
13.5 小結 425
13.6 參考文獻 425
第14章 多維索引和點陣圖索引 427
14.1 需要多維的套用 427
14.1.1 地理信息系統 428
14.1.2 數據立方體 428
14.1.3 sql多維查詢 428
14.1.4 使用傳統索引執行範圍查詢 430
14.1.5 利用傳統索引執行最鄰近查詢 430
14.1.6 傳統索引的其他限制 431
14.1.7 多維索引結構綜述 432
14.1.8 習題 432
14.2 多維數據的類散列結構 433
14.2.1 格線檔案 433
14.2.2 格線檔案的查找 434
14.2.3 格線檔案的插入 434
14.2.4 格線檔案的性能 435
14.2.5 分段散列函式 436
14.2.6 格線檔案和分段散列的比較 438
14.2.7 習題 438
14.3 多維數據的樹形結構 440
14.3.1 多鍵索引 440
14.3.2 多鍵索引的性能 441
14.3.3 kd樹 441
14.3.4 kd樹的操作 442
14.3.5 使kd樹適合輔存 444
14.3.6 四叉樹 444
14.3.7 r樹 446
14.3.8 r樹的操作 446
14.3.9 習題 448
14.4 點陣圖索引 449
14.4.1 點陣圖索引的誘因 449
14.4.2 壓縮點陣圖 451
14.4.3 遊程長度編碼位向量的操作 452
14.4.4 點陣圖索引的管理 452
14.4.5 習題 454
14.5 小結 454
14.6 參考文獻 455
第15章 查詢執行 457
15.1 物理查詢計畫操作符介紹 458
15.1.1 掃描表 458
15.1.2 掃描表時的排序 459
15.1.3 物理操作符計算模型 459
15.1.4 衡量代價的參數 459
15.1.5 掃描操作符的i/o代價 460
15.1.6 實現物理操作符的疊代器 461
15.2 資料庫操作的一趟算法 463
15.2.1 一次多元組操作的一趟算法 464
15.2.2 全關係的一元操作的一趟算法 464
15.2.3 二元操作的一趟算法 466
15.2.4 習題 468
15.3 嵌套循環連線 469
15.3.1 基於元組的嵌套循環連線 469
15.3.2 基於元組的嵌套循環連線的迭
代器 470
15.3.3 基於塊的嵌套循環連線算法 470
15.3.4 嵌套循環連線的分析 471
15.3.5 迄今為止的算法小結 472
15.3.6 習題 472
15.4 基於排序的兩趟算法 472
15.4.1 利用排序消除重複 473
15.4.2 利用排序進行分組和聚集 474
15.4.3 基於排序的並算法 475
15.4.4 基於排序的交和差算法 475
15.4.5 基於排序的一個簡單的連線
算法 476
15.4.6 簡單排序連線的分析 478
15.4.7 一種更有效的基於排序的連線 478
15.4.8 基於排序的算法小結 479
15.4.9 習題 479
15.5 基於散列的兩趟算法 480
15.5.1 通過散列劃分關係 481
15.5.2 基於散列的消除重複算法 481
15.5.3 基於散列的分組和聚集算法 481
15.5.4 基於散列的並、交、差算法 482
15.5.5 散列連線算法 482
15.5.6 節省一些磁碟i/o 483
15.5.7 基於散列的算法小結 484
15.5.8 習題 485
15.6 基於索引的算法 485
15.6.1 聚簇和非聚簇索引 485
15.6.2 基於索引的選擇 486
15.6.3 使用索引的連線 488
15.6.4 使用有排序索引的連線 488
15.6.5 習題 489
15.7 緩衝區管理 490
15.7.1 緩衝區管理結構 491
15.7.2 緩衝區管理策略 491
15.7.3 物理操作符選擇和緩衝區管理的
關係 493
15.7.4 習題 494
15.8 使用超過兩趟的算法 494
15.8.1 基於排序的多趟算法 494
15.8.2 基於排序的多趟算法的性能 495
15.8.3 基於散列的多趟算法 495
15.8.4 基於散列的多趟算法的性能 496
15.8.5 習題 496
15.9 關係操作的並行算法 497
15.9.1 並行模型 497
15.9.2 一次一個元組的並行操作 498
15.9.3 全關係操作的並行算法 499
15.9.4 並行算法的性能 500
15.9.5 習題 501
15.10 小結 502
15.11 參考文獻 503
第16章 查詢編譯器 505
16.1 語法分析 505
16.1.1 語法分析與語法分析樹 505
16.1.2 sql的一個簡單子集的語法 506
16.1.3 預處理器 508
16.1.4 習題 509
16.2 用於改進查詢計畫的代數定律 510
16.2.1 交換律與結合律 510
16.2.2 涉及選擇的定律 512
16.2.3 下推選擇 513
16.2.4 涉及投影的定律 514
16.2.5 有關連線與積的定律 516
16.2.6 有關消除重複的定律 517
16.2.7 涉及分組與聚集的定律 517
16.2.8 習題 518
16.3 從語法分析樹到邏輯查詢計畫 520
16.3.1 轉換成關係代數 520
16.3.2 從條件中去除子查詢 520
16.3.3 邏輯查詢計畫的改進 524
16.3.4 結合/交換操作符的分組 525
16.3.5 習題 525
16.4 操作代價的估計 526
16.4.1 中間關係大小的估計 526
16.4.2 投影大小的估計 527
16.4.3 估計選擇的大小 527
16.4.4 連線大小的估計 529
16.4.5 多連線屬性的自然連線 531
16.4.6 多個關係的連線 532
16.4.7 其他操作的大小估計 533
16.4.8 習題 534
16.5 基於代價的計畫選擇介紹 535
16.5.1 大小參數估計值的獲取 535
16.5.2 計算統計量 538
16.5.3 減少邏輯查詢計畫代價的啟
髮式 538
16.5.4 物理計畫的枚舉技術 539
16.5.5 習題 541
16.6 連線順序的選擇 543
16.6.1 連線的左右變元的意義 543
16.6.2 連線樹 543
16.6.3 左深連線樹 544
16.6.4 通過動態規劃來選擇連線順序
和分組 546
16.6.5 帶有更具體的代價函式的動態
規劃法 549
16.6.6 選擇連線順序的貪婪算法 549
16.6.7 習題 550
16.7 物理查詢計畫選擇的完成 551
16.7.1 選取選擇方法 551
16.7.2 選取連線方法 552
16.7.3 流水線操作與實體化 553
16.7.4 一元流水線操作 553
16.7.5 二元流水線操作 554
16.7.6 物理查詢計畫的符號 556
16.7.7 物理操作的順序 557
16.7.8 習題 558
16.8 小結 559
16.9 參考文獻 560
第17章 系統故障對策 561
17.1 可回復操作的問題和模型 561
17.1.1 故障模式 561
17.1.2 關於事務的進一步討論 562
17.1.3 事務的正確執行 563
17.1.4 事務的原語操作 564
17.1.5 習題 566
17.2 undo日誌 566
17.2.1 日誌記錄 567
17.2.2 undo日誌規則 568
17.2.3 使用undo日誌的恢復 569
17.2.4 檢查點 571
17.2.5 非靜止檢查點 571
17.2.6 習題 573
17.3 redo日誌 574
17.3.1 redo日誌規則 574
17.3.2 使用redo日誌的恢復 575
17.3.3 redo日誌的檢查點 576
17.3.4 使用帶檢查點的redo日誌的
恢復 577
17.3.5 習題 577
17.4 undo/redo日誌 578
17.4.1 undo/redo規則 578
17.4.2 使用undo/redo日誌的恢復 579
17.4.3 undo/redo日誌的檢查點 579
17.4.4 習題 580
17.5 防備介質故障 581
17.5.1 備份 581
17.5.2 非靜止轉儲 582
17.5.3 使用備份和日誌的恢復 583
17.5.4 習題 584
17.6 小結 584
17.7 參考文獻 585
第18章 並發控制 587
18.1 串列調度和可串列化調度 587
18.1.1 調度 587
18.1.2 串列調度 588
18.1.3 可串列化調度 588
18.1.4 事務語義的影響 589
18.1.5 事務和調度的一種記法 590
18.1.6 習題 590
18.2 衝突可串列性 591
18.2.1 衝突 591
18.2.2 優先圖及衝突可串列性判斷 592
18.2.3 優先圖測試發揮作用的原因 593
18.2.4 習題 594
18.3 使用鎖的可串列性實現 595
18.3.1 鎖 596
18.3.2 封鎖調度器 597
18.3.3 兩階段封鎖 598
18.3.4 兩階段封鎖發揮作用的原因 598
18.3.5 習題 599
18.4 用多種鎖方式的封鎖系統 600
18.4.1 共享鎖與排他鎖 601
18.4.2 相容性矩陣 602
18.4.3 鎖的升級 602
18.4.4 更新鎖 603
18.4.5 增量鎖 604
18.4.6 習題 605
18.5 封鎖調度器的一種體系結構 607
18.5.1 插入鎖動作的調度器 607
18.5.2 鎖表 609
18.5.3 習題 611
18.6 資料庫元素層次的管理 611
18.6.1 多粒度的鎖 611
18.6.2 警示鎖 612
18.6.3 幻像與插入的正確處理 613
18.6.4 習題 614
18.7 樹協定 615
18.7.1 基於樹的封鎖的動機 615
18.7.2 訪問樹結構數據的規則 615
18.7.3 樹協定發揮作用的原因 616
18.7.4 習題 618
18.8 使用時間戳的並發控制 618
18.8.1 時間戳 619
18.8.2 物理上不可實現的行為 619
18.8.3 髒數據的問題 620
18.8.4 基於時間戳調度的規則 621
18.8.5 多版本時間戳 622
18.8.6 時間戳與封鎖 623
18.8.7 習題 623
18.9 使用有效性確認的並發控制 624
18.9.1 基於有效性確認的調度器的
結構 624
18.9.2 有效性確認規則 625
18.9.3 三種並發控制機制的比較 627
18.9.4 習題 627
18.10 小結 628
18.11 參考文獻 629
第19章 再論事務管理 631
19.1 讀未提交數據的事務 631
19.1.1 髒數據問題 631
19.1.2 級聯回滾 632
19.1.3 可恢復調度 633
19.1.4 避免級聯回滾的調度 633
19.1.5 回滾的管理 634
19.1.6 成組提交 635
19.1.7 邏輯日誌 636
19.1.8 根據邏輯日誌恢復 637
19.1.9 習題 638
19.2 視圖可串列性 639
19.2.1 視圖等價性 639
19.2.2 多重圖與視圖可串列性的判斷 640
19.2.3 視圖可串列性的判斷 643
19.2.4 習題 643
19.3 死鎖處理 643
19.3.1 逾時死鎖檢測 644
19.3.2 等待圖 644
19.3.3 通過元素排序預防死鎖 645
19.3.4 時間戳死鎖檢測 646
19.3.5 死鎖管理方法的比較 648
19.3.6 習題 649
19.4 分散式資料庫 649
19.4.1 數據的分布 649
19.4.2 分散式事務 650
19.4.3 數據複製 651
19.4.4 分散式查詢最佳化 651
19.4.5 習題 652
19.5 分散式提交 652
19.5.1 分散式原子性的支持 652
19.5.2 兩階段提交 653
19.5.3 分散式事務的恢復 654
19.5.4 習題 655
19.6 分散式封鎖 656
19.6.1 集中封鎖系統 656
19.6.2 分散式封鎖算法的代價模型 656
19.6.3 封鎖多副本的元素 657
19.6.4 主副本封鎖 658
19.6.5 局部鎖構成的全局鎖 658
19.6.6 習題 659
19.7 長事務 659
19.7.1 長事務的問題 659
19.7.2 saga（系列記載） 661
19.7.3 補償事務 662
19.7.4 補償事務發揮作用的原因 663
19.7.5 習題 663
19.8 小結 663
19.9 參考文獻 665
第20章 信息集成 667
20.1 信息集成的方式 667
20.1.1 信息集成的問題 667
20.1.2 聯邦資料庫系統 668
20.1.3 數據倉庫 669
20.1.4 協調器 671
20.1.5 習題 673
20.2 基於協調器系統的包裝器 674
20.2.1 查詢模式的模板 674
20.2.2 包裝器生成器 675
20.2.3 過濾器 676
20.2.4 其他在包裝器上進行的操作 677
20.2.5 習題 678
20.3 協調器基於能力的最佳化 678
20.3.1 數據源能力有限的問題 678
20.3.2 描述數據源能力的符號 679
20.3.3 基於能力的查詢計畫選擇 680
20.3.4 增加基於代價的最佳化 681
20.3.5 習題 681
20.4 在線上分析處理 682
20.4.1 olap套用 682
20.4.2 olap數據的多維視圖 683
20.4.3 星型模式 684
20.4.4 切片和切塊 685
20.4.5 習題 687
20.5 數據立方體 687
20.5.1 立方體操作符 687
20.5.2 通過物化視圖實現立方體 689
20.5.3 視圖的格 691
20.5.4 習題 692
20.6 數據挖掘 693
20.6.1 數據挖掘的套用 694
20.6.2 尋找頻繁項目集 695
20.6.3 a-priori算法 696
20.6.4 習題 698
20.7 小結 698
20.8 參考文獻 699
索引 701
