数据库期末复习

关系规范化

• 数据异常包括插入异常，删除异常，数据冗余，更新异常
• 函数依赖，部分函数依赖，完全函数依赖，传递依赖，多值依赖
  
  • 传递函数依赖：$x\rightarrow y, y\rightarrow z,y !\rightarrow x ,z \not\subseteq y$
• 超码，完全决定，可以冗余；候选码，完全依赖；主属性，候选码的并；全码，全体为码
• 范式
  
  • 1NF，粒度细，提升数据质量，是否使用要权衡查询效率，属性不可再分
  • 2NF，非候选码都是完全函数依赖于码，若不是会存在各种异常
  • 3NF，非候选码不存在传递依赖，若不是会存在各种异常
  • $(sno,cno)\rightarrow tno ,tno\rightarrow cno$是3NF，但存在不良特性，例如没有学生选老师的课会损失老师教课信息etc.
  • 由于主属性对码的不良依赖
  • BCNF 所有属性由码直接决定
  • $3NF\rightarrow BCNF$，可能损失函数依赖
  • BCNF仍然存在多值依赖
  • 多值依赖有对称性，函数依赖是多值依赖的特例，平凡的多值依赖
  • 4NF：对于非平凡的多值依赖$X\rightarrow\rightarrow Y$，X含有码
  • 多值依赖，$X\rightarrow Y$，在Z上成立，Y换成其子集不一定成立，Z换为扩充不一定成立
• Armstrong公理
  
  • 自反律，传递律，增广律
• 求属性集闭包 EZ
• 求候选码：先加入左部属性，再慢慢试
• 推出一样的函数依赖就等价
  
  • 最小覆盖：单属性化，无冗余化，既约化
• 联合律：$ifX\rightarrow\rightarrow Y,Z\subseteq Y,\exists W\subseteq R,s.t.W\cap Y=\emptyset, W\rightarrow Z,then X\rightarrow Z$
• 模式分解的定义：将属性集进行分解，函数依赖进行分解上的投影
  
  • 目标：无损连接，函数依赖，达到更高级范式
  • 判别无损连接算法：每个子集为一行，属性为一列，属于则是ai，不属于是bij，换出一行全为a
  • 判断二分解的无损连接：$U1\cap U2\rightarrow U1-U2$
  • 达到无损连接的BCNF分解算法：对每一个非BCNF U , $X\rightarrow A$，分解为XA和U-X
  • 达到4NF：发现非平凡多值依赖，划分
  • 达到3NF，保持函数依赖：
  • 先求最小覆盖，踢出多余属性，按左边分组，进行投影
  • 同时保持无损和函数依赖：3NF并上主码
• 模式调优：看情况

事务

• 事务的ACID特性及定义：
  
  • 一系列操作序列构成的程序执行单元，不可分割的工作单位
  • 原子性，隔离性，一致性，持久性
  • 原子性，持久性由恢复机制，一致性由用户，隔离性由并发控制机制
• 可恢复调度，无级联调度：
  
  • 一个事务失败了，应该能够撤消该事务对数据库的影响。如果有其它事务读取了失败事务写入的数据，则该事务也应该撤消
  • 对于每对事务T1与T2，如果T2读取了T1所写的数据，则T1必须先于T2提交
  • 无级联调度：对于每对事务T1与T2，如果T2读取了T1所写的数据，则T1必须在T2读取之前提交
• 四种隔离性级别：
  
  • serializable：一个调度的执行必须等价于一个串行调度的结果
  • repeatable read：只允许读取已提交的记录，并要求一个事务对同一记录的两次读取之间，其它事务不能对该记录进行更新
  • read committed：只允许读取已提交的记录，但不要求可重复读
  • read uncommitted：允许读取未提交的记录
  • 后三种分别对应：幻象，不可重复读，读脏数据
  • 还有一种丢失修改
• 快照隔离
  
  • 读写互不阻塞，写发生在提交时，发生冲突先提交者赢，任何读取操作得到事务开始一刻的快照
• 冲突等价：
  
  • 定义：不能交换同一变量的WR,RW,WW，进行其他交换所得到的序列冲突等价
  • 冲突可串行化
  • 对每对RW,WR,WW两个事务连条有向边，没环就是冲突可串行化
• 视图可串行化
  
  • 保持从读一致性，及数据库终态一致即可
  • 判定方式：
  • 如果$T_j$读取$T_i$写入的数据项值，则加入边$i->j$
  • 删除所有关联无用事务的边（不能到终点）
  • 若对于Q，Tj读取Ti，Tk写Q，Tk!=Tb
    
    • 若ti=tb，tj!=tk，j到k连一条边
    • 若ti!=tb，tj=tf，k到i连一条边
    • 否则，两条边都插入，并标注一个唯一整数k
    • 原则，不能打扰那堆从读
  • 只要一个优先图无环，就可串行化
• tips
  
  • 平面事务不能部分回滚
  • 嵌套事务中，只有父节点提交，所有子事务才提交，子事务对其兄弟不可见
  • 工作流：存在执行顺序依赖，使用补偿事务。

并发控制

• 两段锁协议：事务对于锁的获得分为增长阶段和缩减阶段
  
  • 封锁点：事务获得最后一个锁的时间
  • 若一组事务服从两段锁协议，一定是可串行化的，顺序与封锁点顺序一致
  • 长锁：保持到事务结束；短锁：中途可以释放
  • read uncommitted：无锁，committed：短S锁 repeatable：长S锁
• 锁类型：
  
  • 基本锁： X,S,U
  • 意向锁：IS,IX,IU,SIX
  • 码范围锁：RangeS S ，RangeI N...
• X 写锁 S 读锁
• 增长阶段，获得XS，将S升级为X（问题在于，可以升级吗）
• U锁：更新锁，一次只有一个事务可以获得，修改时变为X锁，允许共享访问
• 封锁粒度影响开销和并发性
  
  • 引入I锁：IS，IX表示后裔节点拟加锁
  • SIX锁：S+IX
• 模式修改锁：Sch-M 执行DDL时加锁； 模式稳定锁：Sch-S 编译查询时加锁（不能修改DDL）
• 大容量更新锁：Bulk insert时使用，并行插入，防止访问
• 码范围锁：RangeS_S RangeS_U RangeI #insert RangeX
• 锁的实现：锁表，已被授予的锁和等待请求的锁，锁升级：将细粒度升级为粗粒度，因此可能一些看似不会阻塞的也会阻塞，可以使用索引提高并行
• 死锁条件：
  
  • 互斥条件
  • 占有等待条件
  • 非抢占条件
  • 循环等待条件
• 在123下，4是充要条件
• 预防死锁：预先占据全部资源or按规定顺序分配资源
• wait-die：发现小等老，回滚小
• wound-wait：发现老等小，回滚老
• 超时法
• 活锁：
  
  • 事务永远处于等待状态得不到执行：避免方法，先来先服务
• 基于时间戳的协议
  
  • 每个事务进入系统的时点被分配时间戳
  • 回滚则重新分配时间戳
  • WT(Q) RD(Q) Q为数据项，分别为当前执行该操作事务中最大时间戳
  • 读
  • if TS(Ti)
  • 否则，正常读，改RD
  • 写
  • if TS(Ti)
  • if TS(Ti)
  • 否则正常写
• 有效性检查协议
  
  • 三个时间戳：start validation finish
  • 前事务写和后事务读的数据项集不能相交，若F1位于V2前，若F1还要再往后，要检查写变量集是否相交

恢复控制

• 故障类型：
  
  • 事务故障：非预期故障：如运算溢出，因死锁而回滚；可预期故障：如事务违反一致性而回滚
  • 系统故障：如停电，异常终止，磁盘上数据还在，软故障
  • 介质故障：硬故障，比如硬盘被砸
• 静态转储，动态转储，海量转储，增量转储
• 数据库备份：创建备份完成是数据库内存在数据的副本
• 事务日志备份：上次备份日志完后对数据库执行事务的一系列记录
• 差异备份：上次数据库备份完后发生更改的数据
  
  • 简单恢复：恢复数据库至最新备份
  • 完全恢复：恢复至故障点
  • 大容量日志记录恢复（bulk insert select into）
• 日志：事务标识符，记录名，旧记录值，新记录值。。。
• 圆满事务，夭折事务：分别redo，undo
• 先写日志原则：同步写日志，异步写缓冲区
• 措施
  
  • 正向扫描日志，找出圆满事务计入重做队列，夭折事务计入撤销队列
  • 反向扫描，redo
  • 正向扫描，undo
• 介质故障恢复：装入最新的后备副本与相应日志副本
• 检查点：检查点时刻日志与数据库内容一致
  
  • 将日志缓冲区写入稳存
  • 写入检查点记录
  • 记录活跃事务
  • 干掉minLSN以前的日志记录
  • 频率由recovery interval决定，恢复数据库所需最大分钟数
  • 将数据缓冲区写入
  • 输出活跃事务列表
  • 日志以循环的方式存储
• ARIES：
  
  • LSN：日志顺序号
  • PageLSN：每个页有一组，记录发生在当页的LOG
  • PrevLSN：前一日志记录的LSN
  • CLR：补偿日志记录 特殊字段：UndoNextLSN
  • 找到最后完整检查点日志记录，并从该记录开始读入脏页表
    将RedoLSN设置为脏页表中页的RecLSN的最小值，如果没有脏页，就将其设置为检查点日志记录的LSN
    将要被undo的事务列表undo-list设置为检查点日志记录中的事务列表及其LastLSN
    从检查点继续向前扫描，每找到一个不在undo-list中的事务日志记录，就将其添加到undo-list，每找到一个事务的end日志记录，就将其从undo-list中删除
    只要发现一个更新页的日志记录，如果该页不在脏页表上，就将它添加进脏页表，并设置该页的RecLSN为该日志记录的LSN。
  • Redo过程通过重演所有没有在磁盘页上反映的动作来重复历史
    Redo过程从RedoLSN开始向前扫描日志，该点之前的日志记录已经反映在磁盘数据库页上
    只要Redo过程找到一个update日志记录，它就执行如下动作：
    如果该页不在脏页表中，或者该update日志记录的LSN小于脏页表中该页的RecLSN，Redo过程就跳过该日志记录
    否则Redo过程就从磁盘调出该页，如果其PageLSN小于该日志记录的LSN，重做该日志记录
  • Undo过程反向扫描日志，取消所有undo-list中的事务
    如果找到一个CLR，它用UndoNextLSN字段跳过一个已经回滚了的事务日志。否则，它用事务日志的PrevLSN字段查找下一个要被撤消的事务日志
    每当一个update日志记录被用于撤消，Undo过程产生一个包含undo执行动作的CLR，并将CLR的UndoNextLSN设置为update日志记录的PreLSN值

数据库存储

• RAID1 带块级拆分磁盘镜像，提供最佳写性能，一般用于日志文件存储
• RAID5 数据和奇偶校验位均匀分布，读写性能好，以读为主
• 数据库文件：
  
  • .mdf 主数据文件 文件1
  • .ndf 辅助数据文件
  • .ldf 日志文件 文件2
  • 最多256个文件组
• 数据文件
  
  • 每个页面8k 页面号的形式为(file#:page#)
  • 8个连续页面构成一个区间，存储分配按区间进行，IO按页或区间进行
  • 页面至多被1个对象拥有
• GAM 全局分配位图 差不多64000位，每一位代表一个区间
  
  • 第一个GAM位于第三页，第二个位于524288+3+1页
• SGAM 共享全局分配位图 0表示要么不是共享区间要么满了
  
  • 第一个SGAM位于第四页，类推
• PFS 空闲页空间，覆盖8088个连续页面
• IAM 索引分配位图 记录对象有哪些区间 每4G一个IAM 属于对象 每一bit表示分配的区间
• DCM 差异变化位图
• BCM 批量变化位图
• 页结构：页面头 96byte 页面体（存储数据行） 页面槽 （每行的偏移量，2byte） 共8096byte
• 行结构：状态位A，B 各1byte 定长部分大小 2 定长数据 Fsize - 4
  列数 2byte nullbits 每列1bit，1表示是null 变长列数 2byte
  可变列的偏移数组 n*2byte 变长数据
• 索引采用B+树结构
  
  • 聚簇索引码唯一，叶节点是数据本身
  • 非聚簇索引叶节点包含索引码，到数据行的标识
• 位图索引
  
  • 针对某一属性的每一种取值建立索引
  • 位片索引：将属性值分割为n个域，每个域一个位图索引
• 按列存储的优点：
  
  • 提高带宽利用率，只读查询的属性
  • 提高局部性，压缩比率
  • 提高了cache局部性
• 缺点：
  
  • 增加了磁盘寻道时间
  • 增加插入操作代价
  • 增加重构元组的代价
• 应用场合：
  
  • 数据仓库：高带宽需求
  • 宽表：太宽了

查询处理

• 索引嵌套循环连接
  
  • 一个输入很小，另一个输入很大而且已在连接列上创建索引
• 归并连接
  
  • 两个输入都很大，而且连接列上有索引
• hash连接
  
  • 连接列做个hash，再在每一个bucket中连接
• hash和归并只能处理等值连接，否则还要靠索引嵌套循环连接

标题