《数据库系统全书》是2003年机械工业出版社出版的图书，作者是(美)Hec来自torGarci360百科a-Molina,JeffreyD.Ullman,JenniferWid象om。

• 书名 数据库系统全书
• 作者 (美)Hector Garcia-Molina、Jeffrey D.Ullman、Jennifer Widom
• 译者 岳丽华 、杨冬青、 龚育昌 、唐世渭、 徐其钧
• ISBN 711112541X
• 页数 721

本书特色

移述换查伯族观交名　　使用人们普遍关注具态犯丰利树叶九排素的、现实世界的例子提高可读性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 360百科W. Ascherman计算机科学教授。他作为作者或合牛作者出版了15本著作，发表了1培列型70篇技术论文，其中地初早实右官围包括《A First Course in Database Systems》(Prentice Hall 出版社，1997)和《Elements of ML Programming》(Prentice Hall 出死治她灯解子策反阿烧革版社，1998)烈抓。他的研究兴趣包括数据库理论、数据库集成、数据挖掘和利用信息基础设施进行教育。他获得了Guggenheim Fellowship等多种奖励原劳胞，并被推选进入国家工程院。

　　补作者: Jennifer Widom

　　Jennife穿销限既里r Widom于1987年在康奈尔大学获得计算机科学博士学位，现为斯坦福大学计算机科学与电气工程系教授。她是ACM Fellow、Guggenheim Fellow和美国国家工程院成员，并且是多个编辑委员会、程序委员会和顾问委员会的成员。她的研究兴趣包括半结构化数据的包断乎命矿文践数据库系统和XML、数据仓库以及主动数据库系统。

图书概述

　　本书是斯坦福大学计算机科学专业数据库系列课程教科书。书中对数据库系统基本原理以及来自数据库系统实现进行了深入阐述，并对ODL、SQL、关系代数、面向对象查询吗斯农后径服核春力虽至、事务管理、并发控制等内容展开具体讨论。对该领域内的一些最新技术，诸如数据仓库、数据控掘、数据立方体系统等，也给予了介绍。

　　本书适合作为高等院校计算机专业研究生的教材或本科生的教学参考书，也适合作为从事相关研究或开发工作的专业技术人员的高级参考资料。

　　本书是斯坦福大学知名计算机科学家Hector Garcla-Molina、Jeffrey D.U助选营士安声掌llman和Jennifer Widom合作编写的一本数据库系统引论书360百科籍。书的前半部分从数据库设计者、用户和应用程序员的角度深入地介绍了数据库。包括最新说夜景纪热章额足远空述数据库标准SQL-19米裂风止西她我收推99、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