数据库理论
[TOC]
基本概念与关系模型
基本概念
两层映像：
- E-C Mapping
- C-I Mapping
数据独立性：指 用户应用程序 和 存放在外存数据库的数据 是独立的。
- 逻辑数据独立性：只改变ECM
- 物理数据独立性：只改变CIM
数据模型的三要素：
- 数据结构
- 数据操作
- 完整性约束
关系模型
关系模型概念：
- 域的基数：属性域内元素个数
- 关系的度/目：属性个数
- 关系的基数：tuple的数量
- 联系的度：参与的实体种类数
- 联系的基数：几对几的关系
关系模型的组成：
- 数据结构：关系
- 数据操作：
- 基本操作：并、差、积、选择、投影（投影会去重，相当于
select distinct） - 扩展操作：交、连接。$\theta$ 连接运算是由 笛卡尔积 和 选择 操作组合的。
- 基本操作：并、差、积、选择、投影（投影会去重，相当于
- 完整性约束
- 实体完整性：主码不为空
- 参照完整性：外码与主码对应
- 用户自定义完整性
并相容性：参与并、差、交等操作需要满足。
- 关系R和关系S的属性数目相同
- Ri个属性与Si个属性的域相同
关系模式的定义格式：
- 关系名（属性名1，属性名2，…，属性名n）
关系选择与SQL语言
数据库设计
函数依赖
定义
属性集合：所有属性构成的集合。如U={学号，班级，老师，课号}
关系模式：关系的总合。U上的关系模式，记为R(U)。
函数依赖：
- 对于R(U)上的一个可能的关系r，以及U的子集X，Y
- X中的两个元组相同，则对应的Y也会相同。
- 称为X–>Y
- 如，{学号}–>{姓名，年龄}。两个人如果学号相同，姓名年龄也一定相同。
寻找函数依赖的方法：
- 先确定单个的，也就是A–>B
- 找到属性A当中的相同项，如果B当中的也相同，就形成函数依赖。
- 如果存在不同，尝试补充C，构成{A, C}再看是否有{A, C}–>B。
完全与部分函数依赖：{A, B} –> C
- 完全：{A, B}缺一不可，才能推出C。如{学号，课程号}-f->成绩
- 部分：{A, B}当中的部分就可以推出C。如{学号，课程号}-p->姓名。显然课程号是不必要的
候选键：
- K-f->U。即 最小的 能够完全推出一条确定的记录的属性组合。
- 主键是候选键的一种。
- we may have lots of candidate keys
逻辑蕴涵：
- F |= X–>Y
- F是函数依赖的集合，意思是对于F中所有的函数依赖，都能够推出X–>Y。
闭包：
- 通过逻辑蕴涵，我们可以产生新的函数依赖，也就是F|=f1
- F就这样不断自交自交自交，到最后会形成一个自洽的函数依赖集合，称之为闭包。记F+
- 如果F+ = F，说明F是完备的。
覆盖：
- 如果 $F^+=G^+$，则F和G 等价 ，或者说相互 覆盖 。
求最小函数依赖集
aka 最小覆盖 。
算法如下：
- 首先分解F当中依赖式的右部，为单个元素
- 尝试，如对于某依赖式 $X=A\to B$，删除X。在F-X中求左部A的闭包：
- 如果A+包含了B，则说明不需要X，也能推出 $A\to B$，将X删除
- 否则，必须要X，因此X应当保留
- 重复上面的步骤，直到不可删除。
范式
第一、二、三范式及BCNF。四者的关系是前包含后，第一范式的范围最大。
_0.jpg)
- 1NF：不允许复合属性，如地址{省，市，县}
- 2NF：不允许部分依赖，也就是说非主属性必须 完全依赖 于候选键
- 3NF：不允许传递依赖，也就是说非主属性必须 直接依赖 于候选键
- BCNF：任何依赖的左部必须是超键，或者说sub属性不允许出现在左部。例子
模式分解
无损连接分解检验算法：
- 构造一个k行n列的表，其中k为关系的数量，n为属性的数量。
- 其中第j列对应 $A_j$ ，第i行对应 $R_i$
- 如果 $A_j\in R_i$，置(i, j)为 $a_j$ (accept)。否则置为 $b_{ij}$ (boycott)
- 对于依赖 $A_j\to A_k$，从 $A_j$ 列当中寻找相同的元素，将对应的 $A_k$ 列置为相同
目标是把 $b_{ij}$，变成 $a$
- 经过修改，如果有一行全为a，就是无损连接分解。否则不是。
无损连接分解成BCNF算法：
- Let $\rho = {R}$
- For $s\in \rho$, 如果s有依赖 $X\to A$，X不是超码，则把s拆成 $s_1={X,A}, \quad s_2=s-s_1$
- 重复上面的步骤
保持依赖分解成3NF算法：
- 对于R和F，把R有F没有的属性单独抽出来，形成一个模式
- F当中，相同左部的依赖式合成一个模式
- 所有模式组合起来，得到一个分解。
存储与查找
文件组织方法
- 无序文件组织
- 无序记录
- 更新效率高（有空间即可，不必考虑顺序），检索效率低
- 需要周期性重新组织数据库
- 有序文件组织
- 有序记录
- 检索效率高，但是更新效率低
- 用于排序的属性叫做 排序字段，aka 排序码，可以是主码
- 改进：使用溢出
- 散列文件组织
- 把某个属性进行散列函数计算，得到位置（桶号），这样的属性叫做 散列码，通常是主码。
- 检索和更新效率都有提高
- 在同一个桶内需要顺序检索
- 聚簇文件组织
- 把具有相同或者相似属性值的记录存放于连续的磁盘簇块当中，优化连接代价。
事务与故障恢复
概念
事务处理当中的三个问题：
- 丢失修改：一个写1被另外一个写2覆盖，则写1发生了「丢失修改」
- 脏读：读到回滚的脏数据
- 不可重复读：读1-写-读2，读1与读2的结果不同
基于锁的并发控制
锁协议，有三种锁：
- 共享锁S（读锁）
- 排他锁X（写锁）
- 更新锁U（
select ... for update先是S，后面可以升级成X）
SS互容，SX/XS/XX互斥。
SU互容，US互排斥。这意味着可以「事务1获得S，事务2获得U」但是顺序反之不行。
总之，只有SS、SU是互容的，其他互斥。
基于锁的并发控制：
- 0级协议：给写加上X，写完马上释放。
- 不能解决任何问题
- 1级协议：给写加上X，commit之后释放。
- 可以解决 丢失修改，不能解决脏读和不可重复读。
- 2级协议：给读加上S，读后释放。
- 可以 再 解决 脏读 ，不能解决不可重复读。
- 3级协议：给读加上S，commit后释放。
- 可以解决上面的三个问题。
基于时间戳的并发控制
不用锁。
时间戳：与时间有关的序列号，具有 唯一性 、 单调递增性 。
对于事务T，$TS(T)$ 表示事务T的时间戳，即事务T开始的时间。
对于DB中的元素 $x$, $WT(x)$ 表示最近一次被写的时间戳，$RT(x)$ 表示最近一次被读的时间戳。
简单时间戳控制
对于读操作，需要避免读-写冲突：
- 如果 $TS(T)\ge WT(x)$ 则允许读，并更新 $RT(x)=\max{RT(x), TS(T)}$
- 否则拒绝读，回滚
对于写操作，需要避免读-写冲突和写-写冲突：
- 如果 $ TS(T)\ge RT(x)\land TS(T)\ge WT(x)$ 则允许写，并更新$WT(x)=\max{WT(x), TS(T)}$
- 否则拒绝写，回滚/忽略
Notice. 简单调度会产生两种不一致的错误： 脏读 和 丢失修改 。
优化时间戳控制
增加一个 提交位 $C(x)$:
- $C(x)=1$ 表示最近一个 写 $x$ 的事务已经提交。
对于事务T的请求，调度器除了 同意、回滚 ，还可以 推迟 ，在以后决定要回滚还是重新判断。
对于读操作，需要避免读-写冲突：
- 如果 $TS(T)\ge WT(x)$ 则还需要判断最近的写是否提交，防止脏读（读到回滚的数据）
- 如果 $C(x)=1$，则允许读，并更新 $RT(x)=\max{RT(x), TS(T)}$
- 否则推迟T（将其阻塞），直到 $C(x)=1$ 或者写 $x$ 事务终止。重新判断。
- 否则拒绝读，回滚
对于写操作，需要避免读-写冲突和写-写冲突：
- 如果 $TS(T)\ge WT(x) \land TS(T)\ge RT(x)$ 则允许写，并更新$WT(x)=\max{WT(x), TS(T)}$
- 如果 $TS(T)\ge RT(x) \land TS(T)< WT(x)$，此时说明在T之后有个事务T’想写 $x$，判断：
- $C(x)=1$，说明T’已经提交，忽略T的写
- 否则推迟T，直到 $C(x)=1$（此时忽略），或者T’终止（此时允许写）
- 否则拒绝写，回滚
可以看到，任何一个想要操作 $x$ 的事务有可能会被阻塞，需要等待一个 提交/终止 的信号。因此：
- 当调度器收到T的 提交 请求，他必须找到所有与T绑定的 $C(x)$，将 $C(x)=1$，然后通知在 $x$ 处阻塞的所有事务
- 当调度器收到T的 终止 请求，他同样要找到所有与T绑定的 $x$，然后通知在 $x$ 处阻塞的所有事务
缓冲区策略
Force：在commit之后，必须写入磁盘
No Force：在commit之后，可以拖延一段时间写入。需要 redo
Steal：在commit之后可以偷偷写入磁盘，需要 undo
No steal：不允许偷偷写。