《数据库管理系统实现技术》

第一章 数据库系统（DBS）的发展回顾及其体系结构综述1

Ⅰ．DBS领域的发展回顾1

目录1

Ⅱ．数据处理的发展和数据库系统2

Ⅲ．DBS体系结构综述5

Ⅳ．数据模型7

Ⅴ．DBS的高级接口的特征16

Ⅵ．数据库系统的分层体系结构20

第二章 DBS的存贮管理23

Ⅰ．数据库的分段23

Ⅱ．DBS的系统缓冲区24

Ⅱ.1．存贮空间的组织和映射24

Ⅰ.1．DB分段的理由24

Ⅰ.2．段的类型24

Ⅱ.2．调页（页替换）算法26

Ⅱ.3．双重调页问题（Double Paging）27

Ⅱ.4．查找算法28

Ⅲ．外存分配和到外存的映射28

Ⅲ.1．直接分配和映射29

Ⅲ.2．间接分配和映射30

Ⅳ．用于恢复的影子存贮方法（Shadow Memory）31

Ⅳ.1．段内页面的修改32

Ⅳ.2．段的恢复33

Ⅳ.3．改进影子存贮方法以改善其簇聚性34

Ⅳ.4．影子存贮法的进一步扩充35

Ⅴ．修改数据库的勘误文件法36

第三章 存贮结构和存取路径结构39

Ⅰ．记录或元组在数据页面上的映射39

Ⅰ.1．固定数目的定长场方法39

Ⅰ.4．场长法40

Ⅰ.5．自由顺序法40

Ⅰ.3．首部指针法40

Ⅰ.2．变长场方法（保留字符法）40

Ⅰ.6．分组存贮法41

Ⅱ．记录编址41

Ⅱ.1．TID法41

Ⅱ.2．分配表间接地址法42

Ⅱ.3．改进分配表间接地址法的指针法44

Ⅲ．DBS中的存取路径结构45

Ⅲ.1．主键的存取路径结构46

Ⅲ.2．查找数据记录集合的存取路径结构50

Ⅲ.3．查找数据记录集合的存取路径的实现53

Ⅲ.4．多属性索引的编码方法60

Ⅰ．引论63

第四章 存取系统的体系结构设计及其各功能子系统63

Ⅱ．单元组接口上的数据对象的结构及其运算64

Ⅲ．标记元组位置的方法67

Ⅳ．存取系统中的排序／合并子系统69

Ⅳ.1．排序操作的用途69

Ⅳ.2．排序子系统的设计和实现71

Ⅳ.3．排序操作作为原语72

Ⅴ．结论72

Ⅰ．数据系统的任务及其体系结构设计73

第五章 DBS的数据系统的实现73

Ⅱ．数据库语言的翻译74

Ⅲ．全解释方法和半解释方法75

Ⅳ．预编译方法78

Ⅴ．描述型语言的编译80

Ⅴ.1．游标法80

Ⅴ.2．源程序的加工81

Ⅴ.3．描述型语言语句的分解和优化81

Ⅴ.4．存取模块示例83

Ⅰ.1．面向报文的系统91

Ⅰ.2．面向信息的系统91

Ⅰ．数据密码化91

第六章 数据安全性的实现方法91

Ⅰ.3．密码变换系统92

Ⅱ．操作系统安全92

Ⅲ．数据库安全93

Ⅲ.1．静态授权式93

Ⅲ.2．动态授权式96

Ⅲ.3．存取检查的束缚时间101

第七章 并发控制的实现方法102

Ⅰ．问题的提出102

Ⅰ.1．事务集合执行的串行化102

Ⅰ.2．失控存取造成的错误103

Ⅱ．并发控制常用的方法——封锁106

Ⅱ.1．事务，调度和三元依赖关系106

Ⅱ.2．相容性封锁协议109

Ⅲ．DBS中的封锁方法113

Ⅲ.1．谓词封锁113

Ⅲ.2．直接封锁114

Ⅲ.3．分层封锁114

Ⅲ.4．直接封锁法和分层封锁法的比较115

Ⅲ.5．意向（预约）封锁及其相容性116

Ⅲ.6．意向封锁的精细化117

Ⅲ.7．一种特定的封锁方式118

Ⅳ．封锁管理程序120

Ⅲ.8．分层封锁小结120

Ⅴ．封锁作为资源122

Ⅴ.1．资源的分类123

Ⅴ.2．死锁123

Ⅴ.3．解决死锁的方法124

Ⅵ．事务一致性的分级127

Ⅵ.1．按一致性级别来划分事务127

Ⅵ.2．不同一致性级别下的问题129

Ⅶ．时间戳方法130

Ⅸ．乐观方法133

Ⅷ．时间戳方法中的活锁133

Ⅸ．1．三阶段事务及其等价性规则134

Ⅸ.2．关于事务号的讨论135

Ⅸ.3．串行检验和并行检验136

Ⅸ.4．只读事务的处理137

Ⅸ.5．乐观方法的进一步改进138

Ⅸ.6．小结142

第八章 完整性检查的实现144

Ⅰ．语义完整性144

Ⅱ．完整性约束的种类147

Ⅱ.1．数据模型的完整性约束147

Ⅱ.2．客观世界的完整性约束148

Ⅲ．完整性约束的检查149

Ⅲ.1．检查时间149

Ⅲ.2．违约反应149

Ⅲ.3．例行检查和特殊检查150

Ⅳ．完整性检查的实现技术150

Ⅳ.1．INGRES的询问修改方法150

Ⅳ.2．通用过程法150

Ⅳ.3．未定值对完整性约束的影响及其处理151

Ⅳ.4．存取路径的支持151

Ⅰ．数据的物理完整性153

第九章 恢复管理的实现方法153

Ⅱ．事务154

Ⅲ．故障分类154

Ⅲ.1．事务故障154

Ⅲ.2．系统故障155

Ⅲ.3．介质故障155

Ⅳ．日志（log）和档案库（Archive）155

Ⅴ．处理故障的原则157

Ⅵ．先写log的协议WAL（Write—Ahead—Log Protocol）158

Ⅶ．检验点（Checkpoint）158

Ⅷ．检验点——恢复过程的精细化159

Ⅸ．数据的逻辑一致检验点160

Ⅹ．磁带式恢复法161

Ⅺ．日志的其它功能162

Ⅺ.1．审计追踪（Audit Trail）162

Ⅺ.2．测试性能162

Ⅺ.3．小结162

第十章 描述型语言询问的优化164

Ⅰ．代数优化164

Ⅰ.1．关系代数中的运算165

Ⅰ.2．移动算符树中的运算符166

Ⅰ.3．运算符的合并167

Ⅰ.4．连接运算与集合运算的联合169

Ⅰ.6．代数优化小结173

Ⅰ.5．公共子树的识别及处理173

Ⅱ．非代数优化174

Ⅱ.1．关系运算的非代数优化174

Ⅱ.2．以单元组方式加工运算序例178

Ⅱ.3．引入排序算符179

Ⅲ．关系运算的实现算法180

Ⅲ.1．存取一个关系的全部元组181

Ⅲ.2．选择运算的实现算法181

Ⅲ.3．连接运算的实现算法184

Ⅲ.4．连接运算实现算法的分析186

Ⅲ.5．其它关系运算和集合运算的实现191

Ⅰ．三种可能的配置方案193

第十一章 应用程序，数据库系统和操作系统的相互关系及其配置193

Ⅱ．数据库系统作为操作系统的扩充194

Ⅲ．数据库系统作为子程序195

Ⅳ．独立的数据库系统196

Ⅴ．几种方案的比较202

Ⅵ．数据库管理系统对操作系统的要求205

Ⅵ.1．缓冲区管理205

Ⅵ.2．文件系统207

第十二章 用户接口208

Ⅰ．引言208

Ⅱ．集成化开发环境——Turbo Pascal209

Ⅳ．微型机数据库管理系统CDB［107］210

Ⅲ．LOTUS 123210

Ⅴ．窗口系统212

Ⅴ.1．窗口系统的一般描述214

Ⅴ.2．窗口系统的结构214

Ⅴ.3．几种著名的窗口系统215

Ⅵ．用户接口的一般考虑218

Ⅶ．用户接口的评价219

附录一221

附录二235

参考文献240