數(shù)據(jù)庫系統(tǒng)全書

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