关系数据库相关概念
三级模式结构与二级映射
- 概念模式：全体数据的逻辑结构和特征描述。一个数据库只能有一个概念模式，一般是指数据库形成的表。
- 外模式：用户所能看到的部分数据的逻辑结构合特征描述。一个数据库科研有多个外模式，一般是概念模式经过数据库对用户形成的接口映射后的内容，外模式的属性可能由模式中的多个属性运算而成。
- 内模式：数据的物理结构和存储方式。一个数据库只有一个内模式，一般是指数据库的索引结构。
- 外模式/模式映像：保证了数据库的逻辑独立性。
- 模式/内模式映像：保证了数据库的物理独立性。
举例：
select E# as EMP, D# as DEPT, name from Employee.
EMP属于外模式，Employee属于模式，Employee表的索引结构属于内模式。
关系数据库的几个术语
- 超码：能唯一标识一个元组的属性集叫超码，超码中可能存在冗余属性。
- 候选码：不含冗余属性的超码叫候选码。位于候选码中的叫主属性，不在候选码中的叫非主属性。
- 主码：用户选定的一个候选码作为主码，其它的候选码叫替换码。
- 关系模式：数据之间关系的逻辑结构和特征描述，一般用二维表来表示。
- 关系：关系模式的一个实例，即一张具体的二维表。
- 关系数据库模式：关系模式的集合。
- 关系数据库：关系数据库模式的实例。
关系数据库的形式化定义
关系数据库的形式化定义表示为：R(U, D, Dom, F)。
- R为关系模式名。
- U表示属性集。
- D为U中属性的值所来自的域，一般指属性集中出现过的数据类型，如char、int。
- Dom代表U中属性向D中值域的映射的集合，一般指每个属性的数据类型。
- F表示属性间的依赖，一般只考虑函数依赖FD（Function Dependency）。
函数依赖
- 函数依赖集的闭包：被函数依赖集F所能推出的全部函数依赖所构成的集合叫函数依赖集的闭包，记作$F^+$.
- 属性集的闭包：属性集X是属性集U的一个子属性集，X经过函数依赖集F所能推出来的全部属性集，记作$X^+$.
设属性集X的闭包为Y，则属性集闭包的求法：
- 将Y初始化为X，即令$Y=X$。
- 遍历函数依赖集F，若F中的函数依赖项的左项全部位于Y中，则将该函数依赖项的右项属性加入属性集Y。
- 重复1、2项直至遍历完函数依赖集F，最终得到$Y=X^+$.
- 最小函数依赖集：1.每个函数依赖右边只有一个属性。2.F不可约，即去掉任何一个函数依赖，则函数依赖集F的闭包会改变。3.每个函数依赖的左部不可约，即删除函数依赖左部任何一个元素都会改变F的闭包结果。
最小函数依赖集的求法：
- 先将函数依赖的右部分解，将FD右部分解为单一元素。如：
A->BC分解为A->B, A->C. - 去掉左部冗余属性。如：
ABC->D，若$(AB)^+$包含D，则C冗余，可以去掉。 - 去掉F集合中的冗余FD。若在F集合中去掉
X->Y，在$X^+$中仍然包含Y，则X->Y冗余，可以去掉。 - 实现1、2、3步，最终得到最小函数依赖集。
- 先将函数依赖的右部分解，将FD右部分解为单一元素。如：
关系代数
交 $\cap$, 并 $\cup$, 差 -, 笛卡尔积 $\times$, 选择 $\sigma$, 投影 $\pi$, 连接 $\Join$。
- 选择 $\sigma$ 对应sql语句中的where.
- 投影 $\pi$ 对应sql语句中的select.
- 连接 $\Join$ 不加限制条件默认为自然连接，会消去重复列；若加上限制条件则不会消去重复列。
- 重命名 $\rho_x(E)$
三类完整性
- 实体完整性：主码不得为空值。
- 参照完整性：任何一个非空的外键都存在一个候选码与其对应。
- 用户自定义完整性：用户自定义的约束条件。
SQL语句
- DDL：create
- DML：insert、delete、update、select
- DCL：grant、revoke、deny
数据库设计
数据库设计的相关概念
- 无损连接：一张关系表分解成的多个表，再通过自然连接能完全恢复成原来的表，数据量不能多也不能少。
$p={R_1,R_2}$是无损连接的条件是：$（R_1\cap R_2）-> (R_1-R_2)$或$（R_1\cap R_2）-> (R_2-R_1)$
- 保持函数依赖：分解之后的各个函数依赖集$F_i$的并集的闭包等于原函数依赖集的闭包。
- 完全函数依赖：$X->Y$，Y依赖于X中的全部属性值，X中不存在冗余属性。
- 部分函数依赖：Y只依赖于X中的部分属性值。
- 传递函数依赖：$X->Y, Y->Z$, 则$X->Z$称为传递函数依赖。
关系模式的范式
- 1NF：对于每个元组的每一个属性值都只含有一个值。每一个关系模式都满足1NF。
- 2NF：非主属性都完全函数依赖与主码。
- 3NF：非主属性不传递函数依赖于主码。
- BCNF：所有不平凡的、完全的函数依赖的决定因素（左边的属性集）都是候选码。
模式分解的算法
- 保持函数依赖地分解到3NF的算法
- 把不在函数依赖集F中出现地属性分为一类。
- 把F中左部相同地所有函数依赖所涉及地属性分为一类。
- 最终得到的分解保持函数依赖，且满足3NF。
- 无损连接且保持函数依赖地分解到3NF的算法
- 先使用保持函数依赖分解到的3NF算法进行分解，得到$q={R_1,R_2,…,R_k}$。
- 将R的所有候选码X作为分解后得到的属性集，若某个候选码构成的属性集R是q中的一个子集，则去掉该属性集R。
- 最终得到无损连接且保持函数依赖地分解到3NF的结果。
- 求候选码的算法
- 将函数依赖集F中出现的属性分为四种：只出现在左端的L类、只出现在右端的R类、同时出现在左右两端的LR类、未在F中出现的N类。
- L类和N类一定属于候选码，R类一定不是候选码，LR类可能是候选码也可能不是。
- 判断LR类是不是候选码。求出第一步中得到的一定属于候选码的属性集的闭集$R^+$，若$R^+=U$，则得到最终结果，若不等于，则执行第4步。
- 从LR类中分别取出属性加入候选码中，分别计算此时得到的闭集是否满足$R^+=U$，若满足则R即为候选码。注意：可能求得多个属性集R都是候选码，候选码可能存在多个。
- 无损连接地分解到BCNF
- 先检查各关系模式是否都属于BCNF，若都是，则算法终止。
- 若存在不满足BCNF地关系模式，则必定存在关系模式$R_k$，其中有$X->A$，X不是候选码，则将$R_k$分解为$R_k1={X, A}$和$R_k2={R_k-A}$.
- 重复1、2步，直到都满足BCNF。
数据库设计的步骤
- 先完成需求分析，设计出E-R图。
- 再完成逻辑设计，形成数据库表，并进行修正和优化（范式分解）。
逻辑设计中的步骤：
- 1：1的关系：将任意一个实体的主键加入另一实体，两个实体的主键保持不变，只有一个实体增加了一个属性。
- 1：N的关系：将1端的实体主键加入N端的实体，两个实体的主键保持不变。
- M：N的关系：新建一个关系模式，将两端的实体主键与两端的联系属性一起组成新关系模式，该关系模式的主码为两端属性的主码的组合。
- 弱实体关系：将强实体的主键加入弱实体，与弱实体原本的主键一起形成新的主键。
- 子类（继承关系）：将父类的主键加入子类中，并将父类的主键作为子类的主键。
- 对最终形成的关系模式进行模式分解以及规范化处理。
- 最后实现物理设计，选择存储结构、存取方法以及索引设计.
数据存储
磁盘存取优化
-
减少寻道时间：将随机I/O变为有序I/O: 缓冲机制，先将I/O命令不执行放入缓冲中，再在缓冲中进行排序变成局部有序I/O。主要有单缓冲、双缓冲
-
磁盘调度算法：先来先服务算法、最短寻道时间优先算法、扫描算法、循环扫描算法…
数据组织方式
- 定长vs不定长
- 跨块vs不跨块：跨块块利用率高，但访问速度慢（取一次数据可能需要访问多个块，多次I/O），耗费空间存储地址。
- 数据聚簇：把经常访问的数据尽量放在一个块中，不同类型的数据聚簇通常与跨块搭配，只对局部数据访问如
select student.name from table效率可能会提高，但对于select * from table总体访问效率降低。
缓冲区管理
缓冲区替换策略
- 最佳置换算法OPT：把理论上最不可能使用的缓冲块进行置换，理论上的最优算法。
- LRU算法：维护一个链表，访问后的块移动到链尾，每次从链头取出frame进行置换。LRU算法没有考虑访问频率。
- LRU-K算法：优先使用LRU算法置换访问次数小于K次的块，访问次数大于K次的块尽量不置换。缺点：记录frame的被访问次数需要额外开销。
- 2Q算法：与LUR-2类似，访问次数为1次的frame用FIFO队列维护进行置换，访问次数大于1次的frame块用LRU队列进行维护置换。
- Second-Chance FIFO算法：所有的frame块用FIFO队列进行维护，给了每个frame两次机会，当一个frame块第一次位于队列头时（选择替换出去的次数），移到队尾并用一个bit标记，只有当第二次位于队列头时才被换出并清空bit位标记。缺点：置换时需要移动多个元素，且需要额外的bit位，理论性能比LRU性能差。
- CLOCK算法：将Second-Chance FIFO算法中的队列改造成环形，只需要移动头指针而不需要移动队列元素，减小了移动开销。
闪存SSD置换算法
- CFLRU算法：Clean-first算法，将一个LRU队列分为两部分，相当于维护两个LRU队列，一个由dirty块组成，一个由未修改过的Clean块组成，优先将Clean-LRU队列中的块置换出去，若不存在未修改过的块，再从Dirty-LRU队列中执行LRU算法。
- LRU-WSR算法：在CFLRU算法的基础上，将Dirty队列执行Second-Chance算法，Clean-LRU队列任然执行LRU算法。
数据库索引
顺序文件上的索引
- 密集索引：适用于记录大小远大于索引的时候。缺点：索引空间占用过大。
- 稀疏索引：稀疏索引仅适用于顺序文件，仅部分记录有索引，一般为每个数据块的第一个记录建立索引。
- 多级索引：索引上再建索引。二级索引空间更小，可以常驻内存。二级索引仅为稀疏索引，若二级索引为密集索引则无意义。
无序文件上的索引
- 辅助索引：辅助索引只能是密集索引。在记录无序的情况下建立密集索引，并对索引进行排序。缺点：若记录存在重复键值，则使用密集索的基础上进一步建立二级索引也不方便。
- 间接桶：对于重复的记录建立一个间接桶，辅助索引只记录非重复值，辅助索引指向间接桶，间接桶才指向最终数据，这样可以在辅助索引上建立多级索引。
- 倒排索引：应用于文档搜索的间接桶，为每个检索词建立一个间接桶，桶的指针指向检索词出现的文档。
- B+树：
- 根节点的指针数$2$~$n+1$.
- 中间节点的指针数范围为$\lceil \frac{n+1}{2} \rceil$~$n+1$.
- 叶节点中$\lfloor \frac{n+1}{2} \rfloor$~$n$个指针指向键值，再加上最后一个节点指向兄弟节点。
- 所有非叶子节点只有索引作用，不指向真实值，叶节点才指向真实值。
- B+树的插入：先插入叶节点对应的位置，若超过一个节点所能容纳的最大元素范围，则第$\lceil \frac{k+1}{2} \rceil$个元素向上分裂（从1开始计数），k表示该节点容纳的元素数目；若分裂后导致上一层非叶子节点超出容纳范围，则该非叶子节点分裂，直到全都满足B+树的限制。
- B+树的删除：先插入叶节点对应的值，若低于B+树最低容纳量，优先向左右兄弟节点借，若不够借则合并。 B+树的插入删除可以参考B+树演示网站
- 散列索引：散列表删除数据一般不直接删除，而是用符号标记进行逻辑删除。
- 可扩展散列表：散列函数是一个二进制序列，用前（左）i 位区分桶，桶的数量始终等于$2^i$。当其中一个桶的容量已满时，则将i加1，即将桶数量翻倍。优点：当查找记录时，可以根据二进制序列的前i位查找，只需访问一个存储块。缺点：桶是成倍增长的，增长速度过快，且可能存在大量空闲桶，利用率低。
- 线性散列表：使用二进制序列的后（右）i 位区分桶，桶的数量不一定等于$2^i$。
设桶的数量位n，当前i位区分桶，后i位表示的十进制值位m。
- 若 m<=n , 则记录位于第m个桶。
- 若 n< m < $2^i$，则记录位于$m-2^{i-1}$个桶。
- 只有桶的填充度超过某个比例时才增加1个新桶，若所有桶总的填充度未达到该比例，但当前桶已经塞满的情况下，使用溢出块，当达到增加新桶的标准时，才将溢出块中的数据移入对应的桶中。
- 当桶的数量n > $2^i$时，才将i加1，增加一位数位来区分桶。
查询优化
- 语法分析：构造基于sql语句的语法分析树
- 初始逻辑查询计划生成：将语法分析树转化为关系代数
- 生成逻辑查询计划：构造基于关系代数的语法分析树
- 查询重写：基于代数转换规则优化逻辑查询。
转换规则：
- 连接的转换规则：让生成的中间数据较少的两张表优先连接。
- 选择上的转换规则：$\sigma_{C1\cap C2}(R)=\sigma_{C1}(\sigma_{C2}(R))$, $\sigma_{C1\cup C2}(R)=\sigma_{C1}(R)\cup \sigma_{C2}(R)$
- 选择+自然连接转换规则：$\sigma_{C1}(R\Join S)= [\sigma_{C1}(R)]\Join S = [\sigma_{C1}(S)]\Join R$，$\sigma_{C1\cap C2}(R\Join S)= [\sigma_{C1}(R)]\Join [\sigma_{C2}(S)]$，$\sigma_{C1\cup C2}(R\Join S)= [\sigma_{C1}(R\Join S)]\cup [\sigma_{C2}(R\Join S)]$
- 投影+自然连接的转换规则：$\pi_{xy}(R\Join S) = \pi_{xy}(\pi_{xz}(R)\Join \pi_{yz}(S))$
- 查询代价估计：
相关参数：
T(R)：R的元组数
S(R)：R中每个元组的大小
V(R, A)：R中属性A上的不同值数
B(R)：容纳R中所有元组所需的块数
- $W = R1 * R2$:
T(W) = T(R1) * T(R2)
S(W) = S(R1) + S(R2)
- $W = \sigma_{A=a}(R)$:
S(W) = S(R)
$T(W) = \frac{T(R)}{V(R,A)}$
- $W = \sigma_{A>a}(R)$:
S(W) = S(R)
$T(W) = \frac{T(R)}{2}$ 或 $\frac{T(R)}{3}$ 或范围命中率$f$
- $W = \sigma_{A!=a}(R)$:
S(W) = S(R)
$T(W) = T(R) -\frac{T(R)}{V(R,A)}$
- W = $R_1\Join R_2$:
S(W) = $S(R_1) + S(R_2) - S(A)$，其中A表示两个表在属性A上建立自然连接
$T(W) = \frac{T(R_1)\bullet T(R_2)}{max{V(R_1, A),V(R_2,A)}}$
$V(W,A) = min{V(R_1,A),V(R_2,A)}$，其余属性集在W上的V与在原属性集上的V保持一致
- 物理查询计划选择
参考查询执行章节
查询执行
若数据存放不连续则一次I/O只能读取一个块，若连续存放一次I/O能读取多个块。
- 嵌套循环连接
- 基于排序的算法：归并连接：两阶段多路连接归并算法。代价：每个块4次I/O，最少需要块$\sqrt{R}$个。归并连接算法 = 归并排序算法 + 连接，若连接后不需要写回disk直接传给用户，则每个块多一次I/O，总共5次I/O。
- 基于散列的算法：散列连接：一次read + write完成哈希映射的建立，再来一次read实现连接，总共3次I/O。
- 基于索引的算法：索引连接
事务进程
- 事物的四大性质：原子性、一致性、隔离性、持久性
- 串行调度：穿行执行事务，而不是并发执行。如果一个调度的结果与某串行调度的结果相同，则称该调度是可串化调度
- 事务冲突：如果两个属于不同事务操作（事务并行执行过程中的一部分）是冲突的，那么交换这两个操作的执行顺序至少会改变其中一个事务的结果；若两个操作不冲突，在这两个操作的执行顺序可交换（同一事务的不同操作顺序不可交换）。
- 冲突等价：一个冲突若能通过一系列不冲突的操作顺序交换成另一个冲突，则陈这两个冲突等价。
- 冲突可串性：一个冲突若等价于一个串行序列的冲突，在称该冲突具有可串性。
- 优先图：专用于冲突可串性的判断，节点表示事务，用有向边连接可能发生冲突的事务，有向边的方向记录事务的时间顺序。若优先图中无环，则该调度满足冲突可串性。若具有冲突可串性，则优先图的拓扑排序即为一组等价串行调度序列。
- 视图等价：若不同的调度方式对同一个数据的操作及先后顺序都一致，则称该两个调度方式视图等价。
- 视图可串性：某个调度与某一个串行调度视图等价，则称该调度具有视图可串性。具有冲突可串性的所有调度都具有冲突可串性。
锁
2PL锁
2PL两阶段锁：一个阶段加锁，然后对数据进行操作，在另一个阶段解锁。若所有事务都遵循2PL，则该调度是可串化调度。2PL锁影响了事务的并发性。
- X锁：排它锁
- S锁：共享锁，允许其它事务读，但不允许写。加了S锁的数据不允许再加X锁，但允许其它事务加S锁，即允许其它事务读。
事务一旦释放了一个锁，就不再请求任何锁，因为事务具有原子性。
若事务读完数据后还需要修改，若直接从S锁升级成X锁，由于S锁不具有排它性，若此时多个S锁请求升级成X锁，则容易造成死锁，因此可以使用U锁先预定要修改数据，读完后若需要写，则由U锁升级成X锁。
- U锁：升级锁，持有U锁的事务允许读操作，并会在以后升级成X锁（相当于预定要修改数据），具有排它性，加了U锁后不能再加S锁、X锁和U锁。即<S, U>可以相容，但<U, S>不可约相容。
多粒度锁
加锁的对象不一定是整个数据，可以更加细化，可以是块、元组、索引、索引项等等
- 显式加锁：对该粒度的对象显示地加锁
- 隐式加锁：由于该粒度地上层节点加了锁而使当前对象被加了锁。如：对块加了锁，则该块中地元组被加了锁。
意向锁
- IS锁：意向共享锁
- IX锁：意向排它锁
如果对某个节点加IS或IX锁，说明事务要对该节点的某个下层节点加S锁或X锁。
若要对某个节点加S锁或X锁，需要从根节点开始对路径上每个节点都加IS锁或IX锁。
日志
先写日志再执行操作
-
Undo记录了commit失败的需要撤销的事务，Redo记录了执行成功了但需要重新执行的事务。
- Undo取old value， Redo取new value
- 发生错误时根据日志恢复数据，先Undo再Redo
- 每次日志检查完毕没有错误就加入checkpoint检查点，下次恢复数据时不需要考虑checkpoint前的数据，因为绝对安全。
Undo日志
写入commit之前必须先将数据写入磁盘，Undo日志中记录的旧值，表示需要撤销的事务，恢复到以前的数据，立即更新
优缺点：内存代价小，恢复代价高
Redo日志
先写commit日志再把数据写入磁盘，Redo中记录的新值，表示要重新执行的事务，延迟更新
checkpoint点保证了之前的数据全部写入了数据库disk中。
优缺点：内存代价大，恢复代价小
