《数据库理论及新领域》

第一章 数据库概述1

第二章关系和关系模式6

2.1实例6

2.2关系的形式定义8

2.3键（Key）9

2.4关系的更新10

习题12

第三章关系操作15

3.1布尔操作15

3.2选择、投影和连接操作18

3.3 商操作26

3.4常关系和更名属性28

3.5等值连接操作和扩充操作功能30

3.6关系代数34

习题36

第四章无损分解38

4.1 问题提出——关系分解38

4.2投影与自然连接的关系40

4.3函数依赖（Functional Dependence）42

4.4多值依赖（Multivalue Dependence）43

4.5连接依赖（Join Dependence）45

习题49

第五章依赖理论52

5.1带依赖集的关系模式52

5.2数依赖公理53

5.3多值依赖公理57

5.4依赖基60

5.5多值依赖公理的完备性定理63

5.6嵌入连接依赖65

习题66

第六章关系数据库范式68

6.1只与函数依赖有关的关系数据库范式68

6.2分解式规范化算法72

6.3保持依赖的无损分解74

6.4依赖集的等价变换（一）：无冗余化和既约化76

6.5依赖集的等价变换（二）：最小化78

6.6保持依赖的无损分解的完整算法83

6.7第四范式86

6.8第五范式87

习题88

7.1投影连接映照90

第七章符号表和跟踪算法90

7.2符号表92

7.3符号表等价性与模式等价性94

7.4带限制的符号表等价性98

7.5跟踪算法102

7.6检验隐含依赖104

7.7跟踪算法的计算复杂度111

习题112

8.1合理表示的概念115

第八章表示理论115

8.2数据库模式的数据等价性123

8.3测试合理表示126

8.4测试数据等价性132

习题135

第九章无环数据库模式137

9.1数据库模式的性质137

9.1.1完全归约的存在性137

9.1.2 连接依赖与多值依赖间的等价性140

9.1.3唯？4NF 分解141

9.1.4成对一致性蕴涵完全一致性142

9.1.5较小的中间连接143

9.2数据库模式的语法条件145

9.2.1无环超图145

9..2.2 连接树150

9.2.3 连续交集性质152

9.3各种条件的等价性152

9.3.1 Graham归约152

9.3.2找出连接树154

9.3.3 无环数据库模式的等价性定理156

参考文献157

第十章分布式数据库的查询处理158

10.1记号和定义158

10.2相等连接查询160

10.3半连接归约对查询的解161

10.3.1 归约（Reduction）161

10.3.2树查询162

10.3.3环查询168

10.4树类查询的成员测试算法169

10.5半连接在分布式数据库中应用的基本概念174

10.5.1数据库略图（Profile）和对半连接运算的估计175

10.5.2把半连接用于连接查询176

10.6确定半连接程序的SDD-1算法179

10.6.1基本SDD-1算法179

10.6.2事后优化184

10.7确定半连接程序的AHY（Apers,Hevner,Yao）算法185

10.7.1简单查询187

10.7.2调度的综合191

参考文献193

第十一章并行控制（Concurrency Control）194

11.1概念与记号195

11.2 正确性理论197

11.2.1终态可串行性（Final—State Serializability）197

11.2.2视图可串行性（View Serializability）199

11.2.3冲突可串行性（Conflict Serializability）200

11.3调度器算法202

11.3.1封锁方法（Locking）202

11.3.2时间印方法（Timestamp）204

11.3.3 冲突图方法205

11.3.4分布式调度器206

11.4多版本并行控制（MultiversionConcurrency Control）207

11.4.1多版本系统的正确性208

11.4.2多版本调度器的能力210

11.4.3多版本调度器算法213

参考文献214

第十二章可靠性（Reliability）216

12.1集中式系统的可靠性理论216

12.1.1强化的调度器217

12.1.2数据管理器（Data Manager）222

12.2分布式系统的确认协议（CommitProtocol）226

12.2.1原子性确认协议（Atomic Commitment Protocol）227

12.2.2两段确认协议（Two—phase Commit Protocol）229

12.2.3三段确认协议（Three—phase Commit Protocol）232

参考文献236

第十三章逻辑数据库查询语言的实现238

13.1逻辑数据库的查询239

13.2规则／目标图和基本俘获规则249

13.3基于递归的俘获规则255

参考文献259

14.1引言260

第十四章逻辑数据库查询求值过程的优化260

14.2边侧信息传递262

14.3装饰规则集267

14.4 魔集法（Magic Set Method）270

14.5计数方法（Counting Method）277

参考文献281

第十五章面向对象的数据库系统282

1 5.1新的应用领域及其对数据库技术的要求282

1 5.1.1新的应用领域282

1 5.1.2新的应用领域对数据库技术的要求284

15.2 面向对象技术与数据库技术的结合286

15.2.1 面向对象的概念与特点287

15.2.2面向对象的数据库管理系统（OODBMS）297

15.3 几个典型的OODBMS300

15.3.1 VBASE300

15.3.2 GemStone306

15.3.3 Iris311

15.3.4 ORION317

15.4.1关系数据库系统326

15.4 与OODB有关的研究领域326

15.4.2语义数据模型327

15.4.3嵌套关系（Nested Relations）327

15.4.4数据库程序设计语言与持久性程序设计语言327

15.4.5可扩充的数据库系统327

参考文献328

第十六章可扩充的数据库系统329

16.1实现可扩充性的途径330

16.1.1扩充DBMS功能的三种方式330

16.1.2构造可扩充的DBMS的两种方式331

16.2可扩充的各个方面333

16.2.1 面向应用的扩充333

16.2.2 面向系统的扩充336

16.3 几个可扩充的DBMS339

16.3.1 POSTGRES340

16.3.2 Exodus351

16.3.3 GENESIS357

16.3.4其他可扩充的DBMS原型系统361

16.4可扩充的数据库与面向对象的数据库的比较366

参考文献367