第三章 关系数据模型

3.1 关系数据模型的基本概念

3.1.1关系数据模型概述

关系数据模型结构单一，只有关系。
关系操作：集合操作，一次一集合方式（而非关系数据模型是一次一记录方式）
关系代数：用关系的运算来表达查询需求
关系演算：用谓词来表达查询要求，分为元组关系演算和域关系演算
介于关系代数和关系演算之间：SQL（关系数据库的标准语言）

关系数据语言的分类

3.1.2 关系数据结构

• 笛卡尔积

笛卡尔积在离散数学里提到过，它其实就是按顺序将不同集合中的元素相连。将上面的定义画出来，就是这样子：

并非所有元组都有意义，通常只有笛卡尔积的子集才有实际意义

关系的性质：1）每一列的值是同类型数据 2）不同列的值可以有相同的域，每列称为属性 3）元组中每个分量不可分 4）元组不能重复 5）元组无序

• 候选键与主键

候选键：属性或属性组的值能唯一标识出一个元组
候选键可以多个，选其一个作为主键，主键只能一个
全键关系：全部属性构成唯一候选键
外键：不是本关系的主键，但它是另外一个关系的主键

• 关系模式
  是对一类实体特征的结构性描述，也是对关系的结构性描述，该描述一般包括关系名，属性名，属性域的类型和长度，属性之间固有的依赖关系等

3.1.3 完整性规则

• 实体完整性规则
  对关系中的每一个元组，其主键属性对应的各个分量不能为空值
• 参照完整性规则
  （设关系R的外键与关系S的主键对应）
  外键必须为关系S中某一元组的主键值或者为空值
• 用户定义的完整性规则
  这是针对某一具体数据的约束条件，由应用环境决定

3.2 关系代数

用关系的运算来表达查询要求和条件

3.2.1 传统的集合运算

（emmm，学过离散数学的话应该很好理解，可以直接跳，在计算机中离散数学等等各种数学是真的好有用，可惜我当年没有好好学，下次有空再出一个系列）
并、交、差、笛卡尔积。除笛卡尔积外，其他运算要求参与运算的关系相容（关系有相同的度，对应属性的域相同）
一下运算对象均为R关系与S关系，并且R与S相容

• 并运算 R∪S

这个就是求并集，属于R或属于S

• 差运算 R-S

属于R但不属于S

• 交运算 R∩S

属于R也属于S

等价的形式：R∩S=R-（R-S）=S-（S-R），因为交运算要求剩下公共部分，那就是自己减去不属于公共部分

• 修改运算，差与并的复合运算

要将R中的R1改成R2：

怎么集合运算表示修改呢？直观的一种方法是，将要修改的部分删掉，加上修改后的结果，这样看起来就好像在原数据上修改了一样。

• 广义笛卡尔积

之前介绍的笛卡尔积是在集合中的元素上面操作的（D1XD2X···Dn），这里要介绍的是在两个不同关系上作笛卡尔积运算

直观来看，用这张图来解释，就是R中的一个关系和S中的每一个关系组合过去

画得不丑

3.2.2 专门的关系运算

• 选择运算

根据条件从某一关系中选出元组构成一个新的关系

σ是选择符号，F是限定条件的布尔表达式

• 投影运算

从一个关系R中选取所需要的列组成一个新关系

相当于创建了一个新视图

• 连接运算

从两个关系的广义笛卡尔积中选取满足一定连接条件的元组

• 自然连接

是一种特殊的等值连接，把两个关系中重复的属性列去掉，以后若没有特殊说明，连接均值等值连接

举个例子

以结果中第二行为例，R和S进行自然连接，他们相同的属性列是B、C，那么就只能保留B、C相等的值，所以结果中B、C的值分别为b2、2，他们在关系R和S中的值相等

• 除法运算
  这是一个比较难的知识点，我将尽可能简单地讲，如有误，欢迎指正

在广义笛卡尔积的乘法下，我们将除法看作乘法的逆运算，记住，始终记住这点
我们要求的是R÷S=Q，那么必有Q×S⊆R，不然的话我就可以修改结果中的值，除法将没有意义。如果我们要求除法的结果不为空的话，那它要满足①R中的属性个数＞S中的属性个数，②S中的属性⊆R的属性，不然除出来就没东西了
所以，我们的目标就是要找到这样一个元组，让它与S做乘积后的元组都属于R

首先，我们缩小范围，结果的值一定是R中有的属性而S中没有的属性，这样笛卡尔乘积才能还原R的子集。还有结果的值不会落在R属性的值域外。好，我们先取R中有的属性而S中没有的属性，并且去重，得到关系T。

但是如果就这样让T与S相乘，会有一些值在R关系之外，这与我们当初定义除法的初衷是相违背，所以，我们得将T中去掉一些值让满足这个条件。现在，我们将开始寻找哪些值不能保留在T中
显然，如果我将S×T与R相比多出来的那部分属性值删去不就好了，这样S×T'⊆R，这就是我们想要的结果！！
我们令W=T×S-R，也就是多出来的元组，然后投影在属性A、B上（关系T的属性），得到V，最后，让T减去这多余的V，就是最终结果。

看到这里的你，再回过头来看书中的步骤，是不是觉得很简单了呢？

关系代数运算在实现检索、删除、插入操作，修改可由删除+添加两部分实现，所以：
关系代数具有关系完备性，即以关系代数运算为基础的数据语言可以实现人们对数据库的所有查询和更新操作。

关系演算

关系演算是以数理逻辑中的谓词为基础的关系数据语言。

3.3.1 元组关系演算

其中t为元组变量，ψ（t）是元组关系演算公式，有原子公式和运算符组成。

• 原子公式

1）R（t），t是关系R中的一个元组
2）t[i]θs[j]，θ为比较运算符，t[i]和s[j]分别表示t的第i个分量和s的第j个分量
3）t[i]θa或aθt[i]，a为常量

• 关系演算公式

1）每个原子公式都是公式
2）设ψ1和ψ2是原子公式，则ψ1∧ψ2、ψ1∨ψ2、￢ψ1都是公式
3）设ψ(t)是原子公式，t是元组变量，∀ψ(t)、∃ψ(t)都是公式
4）有限次使用1）2）3）条规则得到的表达式都是公式
要点：原子公式，∧∨￢∀∃，有限次

3.3.2 域关系演算

同理，对比一下元组关系演算，就是将元组替换成了域
域关系演算的一般形式：

3.3.3 关系演算的安全限制

安全表达式：不产生无限关系和无穷验证过程的表达式
安全措施：为了得到安全表达式所采取的措施
定义DOM（ψ），是一个有限符号，由ψ中的常量符号和ψ中涉及的所有关系的所有元组的各个分量值构成。如果觉得上面的繁琐，记住下面的内容即可：
在DOM（ψ）限制下的关系演算是安全的
一个元组表达式{t|ψ(t)}安全所满足的条件：

1）如果元组t能使ψ(t)为真，则t的每一个分量是DOM(ψ)中的元素（因为它们的真值都确定了）
2）对于ψ中的每个形如(∃)ω(t)的子表达式，如果t使ω(t)为真，则t的每一个分量是DOM（ψ）中的元素
  因为只要有一个为真，那么(∃)ω(t)就为真，就不用继续验证下去了
3）对于ψ中的每个形如(∀)ω(t)的子表达式，如果t使ω(t)为假，则t的每一个分量必属于DOM（ψ）
  因为只要有一个为假，那么(∀)ω(t)就为假，就不用继续验证下去了

3.4 查询优化

3.4.2 查询处理与优化技术

关系数据库的数据查询过程：

特点是系统自动优化路径，这是因为：
1）优化器可以从数据字典中获取许多统计信息
2）如果数据库的物理统计信息改变了，系统可以对查询进行重新优化以选择相适应的执行计划
3）优化器可以考虑数百种不同的执行计划
4）优化器中包括很多复杂的优化技术
DBMS优化查询的一般方法：
1）将查询需求转化成某种内部表示，通常是语法树
2）根据一定的等价变换规则吧语法树转换成标准形式
3）选择低层的操作算法
4）生成最佳查询计划

基于代价的优化算法

集中式数据库：总代价=I/O代价+CPU代价
多用户环境下：总代价=I/O代价+CPU代价+内存代价

查询优化技术

1）代数优化：通过代数表达式的等价变换提高查询效率
2）物理优化：根据系统提供的物理组织结构和存储路径来选取较好的查询方案
3）规则优化：总结出的一些启发式规则
4）代价优化：对多个候选查询计划进行代价估算，选择执行代价最小的查询计划

3.4.3 关系代数等价公式

1）笛卡尔积的等价公式

2）连接运算的等价公式

3）投影运算串接的等价公式

4）选择运算串接的等价公式

5）选择运算与投影运算交换的等价公式

6）选择运算与笛卡尔积交换的串接等价公式

7）投影运算与笛卡尔积交换的等价公式

3.4.4 查询优化策略

1）选择运算或投影运算应尽早执行
2）把投影运算和选择运算同时进行
3）把投影操作与它前面或后面的一个双目运算结合起来，不必为投影而专门扫描一遍关系
4）在执行连接运算之前，可对需要连接的关系进行适当的预处理如索引或排序
5）把笛卡尔乘积与其前、后的选择运算合并成为连接运算，以避免扫描笛卡尔乘积的中间结果
6）存储公用子表达式

3.4.5 查询优化计算步骤

1）把查询需求转换成内部表示。常用的内部表示是语法树
2）代数优化
3）物理优化
4）生成多个查询计划，选择代价最小的执行

参考资料：《数据库原理及其应用教程》（黄德才主编，科学出版社，第四版）