DBMS
一.绪论
基于文件系统的数据管理方法
特点
1 | 数据存储于文件中 |
缺点
1 | 每当文件格式发生变化，就要修改应用程序 |
基于数据库管理系统的数据管理方法
特点
1 | 数据存储在数据库中 |
基于二者的对比
（1）FS:每当文件格式发生变化，就要修改应用程序
DBMS：只要数据模式不发生重大变化，应用程序基本无需修改
（2）FS:文件中存在冗余数
DBMS：冗余数据较少
（3）FS:文件修改可能造成数据不一致
DBMS：在数据库规范情况下基本不会造成
（4）FS:文件修改可能会破坏数据正确性
DBMS：会对数据更新进行完整行进检查
（5）FS:没有索引，访问效率低
DBMS：提供索引
（6）FS:只能对整个文件进行访问控制，数据安全性差
DBMS：可规定用户对于数据库哪一部分进行操作
（7）FS:文4没有并发控制
DBMS：提供并发控制机制
数据库功能
数据库：有组织的、共享的、持久存储的数据集合。
数据库系统
由数据库、数据库管理系统、应用程序和数据库用户在一起构成的系统。
数据库的三层模式结构
数据库模式通常分三个层次定义，从低到高分别是:
内模式/存储模式
概念模式
外模式/视图
内模式/存储模式
描述数据库的物理存储结构和存取方式
数据库只有一个内模式
定义内模式时通常使用物理数据模型提供的概念
概念模式
为全体数据库用户描述整个数据库的结构和约束
数据库只有一个概念模式
定义概念模式时使用实现数据模型提供的概念
外模式/视图
从不同类别用户的视角描述数据库结构
可以有多个外模式
定义外模式时也可以使用实现数据模型提供的概念
模式映射
在三层模式结构中，不同层次模式之间的映射用于完成应用程序与数据库之间的数据转换和请求转换。
分类
外模式-概念模式映射
概念模式-内模式映射
数据独立性
逻辑数据独立性
物理数据独立性
数据库语言分类
数据定义语言
数据操作语言
事务
由数据库上的一系列操作完成的复杂任务，这些操作要么全执行，要么全不执行
性质
1 | 原子性 |
并发控制
为了充分利用，允许多个事务并发执行。
多个事务并发可能会破坏数据一致性。
二.关系数据库
关系数据模型
三要素：关系数据结构、关系操作、关系完整性约束。
关系数据结构
关系中属性的个数即为关系的度。
只有符合客观实际的关系才是正确的关系。
键：关系的某些属性集合具有区分不同元组的作用。
超键：可以唯一标识每个元组的属性。
候选键：任意真子集都不是超键的超键。即极小的超键。
主键：每个关系都有至少一个候选键，人为指定其中一个作为主键。
外键：设F为关系R的属性子集。若F与关系S的主键K相对，则称F为R的外键。
关系操作
查询语言的类型：关系代数、关系演算、结构化查询语言SQL。
关系完整性约束
完整性约束的类型：实体完整性、参照完整性、用户定义完整性。
实体完整性约束规则
1 | 主键值唯一且非空。 |
参照完整性约束
1 | 对于外键的约束，外键值为空或不为空则必须在S存在。 |
用户定义完整性约束
1 | 根据需求定义。 |
关系代数
选择操作
投影操作
并操作
差操作
笛卡尔积操作
笛卡尔积作用仅仅是将R和S无条件连接起来。
重命名操作
派生关系代数操作
交操作
$\theta$连接
等值连接：连接条件仅涉及相等比较的连接称作等值连接。
自然连接
自然连接与$\theta$连接的区别
| 自然连接 | $\theta$连接 | |
|---|---|---|
| 连接条件 | 隐含给出 | 明确给出 |
| 结果属性 | 去掉重复的同名属性 | 保留重名的同名属性 |
左外连接
右外连接
全外连接
除
扩展关系代数操作
分组操作
eg：
赋值操作
关系演算
eg：
eg：
三、结构化查询语言
SQL数据定义
声明用户定义完整性约束
1 | 规定属性值非空 |
定义视图
从用户视角所看到的数据
数据更新
修改：update 关系名 set
数据完整性检查
1 | 目的：数据修改可能导致数据库违反完整性约束，需要对数据完整性进行检查 |
数据查询
选择查询条件
注意：空值判断，应用 is null,不可以用 =或者！=
集合操作
查询结果排序
限制查询结果数量
聚集查询
注：聚集函数不能出现在where子句中
分组查询
注意事项
连接查询
内连接
自然连接
自连接
外连接
嵌套查询
使用exists关键字进行查询的时候，首先，我们先查询的不是子查询的内容，而是查我们的主查询的表，然后，根据表的每一条记录，依次去判断where后面的条件是否成立。
in在查询的时候，首先查询子查询的表，然后将内表和外表做一个笛卡尔积，然后按照条件进行筛选。所以相对内表比较小的时候，in的速度较快。
嵌套查询的写法
派生
四、概念数据库设计
数据库设计的过程
实体-联系模型
实体-联系模型：简称ER模型，用于将现实世界抽象为实体及实体间的联系。
ER模型概念：
与实体相关的概念
实体：数据库中表示的现实世界中的具体对象或事物。
属性：用于刻画实体的特性。
属性的类型
1 | 简单属性 |
实体型的ER图表示
弱实体型：没有键属性的实体型。
标识实体型、属主实体型：由于弱实体型没有键属性，需要依赖于其他实体型进行区分。
标识联系型：弱实体型与其标识实体型通过标识联系型关联。
部分键：用于区分和同一标识实体相关联的弱实体的属性集合。
与联系相关的概念
联系：一个联系表示多个实体之间有意义的关联关系。
联系型：同一类联系共同具有的类型。
联系型的度：参与到一个联系型中的实体型的个数。
联系集：数据库中当前存储的联系型的实例的集合。
联系型的约束
存在依赖约束/参与度约束：刻画实体型参与到联系型中的最小基数。
联系型的属性
多元联系：3个以上实体参与的联系
增强ER模型
子类/超类
不相交子类：若超类的每个实体属于最多一个子类，则子类是不相交的。
重叠子类：若超类的每个实体可以属于多个子类，则子类是重叠的。
全部特化：超类的每个实体必须属于至少一个子类。
部分特化；超类的某些实体可以不属于任何子类。
五、逻辑数据库设计
ER模型转换为关系数据库模式
实体型的转换
复合属性的转换
多值属性的转换
弱实体型的转换
M:N二元联系型的转换
N:1二元联系型的转换
1:1二元联系型的转换
与N:1相同
二元自联系型的转换
标识联系型的转换
设计不合理的关系可能产生的异常问题
1 | 数据更新问题 |
知识要点图
函数依赖
定义
类型
函数依赖的公理系统
逻辑蕴含
等价函数依赖集
相关概念
最小覆盖
关系模式的范式
第一范式
若关系模式R的每个属性都是不可分的，则称R为第一范式关系模式。
存在问题
1 | 数据插入异常 |
原因
1 | 非主属性部分函数依赖于候选键 |
第二范式
存在问题
1 | 数据插入异常 |
原因
1 | 非主属性传递函数依赖于候选键 |
第三范式
存在问题
1 | 数据插入异常 |
原因
1 | 主属性部分依赖于候选键 |
BCNF
消除主属性间的传递依赖。
关系模式分解
分解准则1：无损连接性
分解准则2：函数依赖保持性
无损连接性判定
函数依赖保持性判定
关系模式分解方法
六、物理数据库设计
物理数据库设计概述
1 | 在逻辑数据库设计的基础上，为数据库中的关系选择合适的存储结构和存取方法，并进行数据库调优，使数据库上的事务能够高效执行。 |
工作负载分析
工作负载是一组混合在一起的查询和更新。
选择度：满足条件的结果元组在全部候选元组中所占的比例。
索引设计
索引设计的基本过程
索引设计的准则
1.是否建索引
2.索引键的确定
3.复合索引的设计
B+树支持的查询
全值匹配：和所有索引属性进行匹配
匹配最左前缀：和前面几个索引属性进行匹配
匹配属性前缀：只匹配前缀属性的前缀部分
范围匹配：在给定范围内对前缀进行匹配
精确匹配某一属性并范围匹配另一属性
B+树还支持索引属性排序
B+树的限制
必须从B+树的最左属性开始匹配
条件中不能包含表达式
不能跳过B+树的属性
如果索引中有关某个属性的范围查询，则其右边所有属性都无法使用索引查找
覆盖索引
如果一个索引包含一个查询需要用到的所有属性，则称该索引为覆盖索引
单个复合索引 vs 多个单属性索引
方案一：建立一个符合索引
方案二：建立多个单属性索引
多个单属性索引的缺点
1 | 没有在单个复合索引上做查询效率高 |
4.是否使用聚簇索引
- 聚簇索引：将数据存储与索引放到了一块，找到索引也就找到了数据
- 非聚簇索引：将数据存储于索引分开结构，索引结构的叶子节点指向了数据的对应行，myisam通过key_buffer把索引先缓存到内存中，当需要访问数据时（通过索引访问数据），在内存中直接搜索索引，然后通过索引找到磁盘相应数据，这也就是为什么索引不在key buffer命中时，速度慢的原因
不同存取路径区别
5.用哈希表还是B+树
哈希表的限制
1 | 不支持部分索引属性匹配 |
6.权衡索引代价维护
7.不唯准则
索引调优
MYSQL索引设计技巧1：前缀索引
索引选择性：
MYSQL索引设计技巧2：聚簇索引
MYSQL索引设计技巧3：伪哈希索引
内模式设计
关系是否采用聚簇索引？
若使用聚簇索引，应按哪些属性聚簇索引？
同聚簇索引设计准则。
查询改写
恒真/假的选择条件
含表达式的选择条件
无用的去重操作
无用的分组操作：分组操作昂贵
无用的投影操作
无用的连接操作
临时关系：占用额外存储空间，且其上没有索引
嵌套查询；查询器优化嵌套查询能力弱
类型转换
概念模式调优
数据类型选择
1 | 1.尽量使用可以正确存储的最小数据类型 |
标识符的选择
1 | 整型：最好的选择，占用空间少，速度快 |
七、存储管理
按CPU访问存储介质的方式，可将存储器分为三类。
1 | 主存储器 |
主存
1 | 包括：寄存器、高速缓存、内存 |
二级存储器
1 | 包括：磁盘/机械硬盘、闪存/固态硬盘 |
三级存储器
1 | 包括：磁带、光盘、网络存储 |
存储层次间的数据传输
数据局部性：同一单元的数据经常被同时访问到
虚拟内存不是存储层级中的一层。
按存储介质的易失性/持久性，可分为
1 | 易失性存储器：计算机重启后，易失性存储器的数据会丢失 |
持久性内存又称非易失性内存：按字节寻址、非易失
磁盘
数据库的文件存储
将一个数据库存储为一个或多个文件；每个文件包含多个页。
数据库文件的页可以存储元组、元数据、索引、日志记录等。
1 | 大多数DBMS在一个页中只存储一种类型对象。 |
每个页拥有唯一编号，称作页号。
DBMS的存储管理器负责管理数据库文件
1 | 记录页中元组的读/写 |
文件存储的分类
1 | 面向行的存储 |
各种表示
数
字符串
元组
元组头
元组数据
变长元组的布局
页布局
页头
页数据
面向元组的组织方法
分槽页是最常见的面向元组的数据组织方法
1 | 槽数据 |
槽的元数据存储在页头中
1 | 槽的数量：用于确定下一个空闲槽的编号 |
记录号
溢出页
页碎片化
1 | 随着元组删除或版本过期，其中会产生碎片：浪费磁盘空间、增加磁盘I/O |
日志结构页布局
1 | 文件中只存储数据更新操作的日志记录，而不存储元组 |
1 | 新的日志记录只能写到文件末尾 |
读元组
日志记录索引
日志记录合并
文件组织
法一：堆文件组织
法二：顺序/有序文件组织
法三：哈希文件组织
堆文件组织
基于链表的页组织方式
基于页目录的堆文件页组织方式
顺序/有序文件组织
哈希文件组织
缓冲区管理
缓冲池的页称作页框
页表
DBMS用两个变量记录缓冲池中每个页框的状态
缓冲区功能
1 | 请求页；修改页；释放页 |
请求页
1.
2.
3.
实际在情况3下，DBMS会终止提出该请求的事务，为了避免资源浪费
页替换策略
缓冲池与虚拟内存的相同点
缓冲池与虚拟内存的不同点
1.
2.
面向行的存储
面向列的存储
缺点：面向列的存储适合于联机分析处理，不适合于联机事务处理。元组重构代价高，元组删除和修改代价高；解压代价
八、索引结构
索引
有序索引：通过按索引键有序排列索引项来实现索引
哈希索引：通过按索引键哈希值分桶来实现索引
有序索引
哈希索引
有序索引
一
根据数据文件中的元组是否按索引键值排序，分为聚簇索引与非聚簇索引。
聚簇索引
文件中的元组按索引键排序的，则索引为聚簇索引。
1 | 聚簇索引的索引键通常为关系主键； |
非聚簇索引
文件中的元组不按索引键排序的，则索引为非聚簇索引。
1 | 一个关系上可以有多个非聚簇索引 |
索引组织表
索引组织表=聚簇索引文件+数据文件
1 | 在索引组织表中，聚簇索引的索引项中存储元组本身，而不是地址 |
二
根据关系中每个元组在索引中是否都有一个对应索引项，可将有序索引分为两类：稠密索引、稀疏索引
稠密索引
稀疏索引
三
根据索引键是否为关系的主键，可将有序索引分为两类：主索引，二级索引
主索引
1 | 索引键为主键；一个关系只有一个 |
二级索引
1 | 索引键不是主键： |
其他索引及创建方法
创建主索引：
创建二级索引：
唯一索引：索引键值不能重复
外键索引
索引结构
有序索引结构
1 | 平衡树 |
哈希索引数据结构
1 | 哈希表 |
哈希索引数据结构
外存哈希表
外存哈希表分类
可扩展哈希表
插入
删除
线性哈希表
二者对比
树索引结构
B+树
B+树插入、删除，看教程，此处不详细说明。
B+树演示
1 | https://cmudb.io/btree |
其余
键压缩
前缀压缩
后缀截断
批量加载
LSM-Trees
B+树的原地更新
日志结构合并树
LSM树的基本结构
LSM的查找
缺点：当不可变文件非常大时，在文件上查找效率很慢
LSM的更新
分层LSM
位图索引
空间索引
九.查询执行
查询处理的基本过程
原语操作：带有如何执行注释的关系代数操作。
查询执行计划：用于执行一个查询的原语操作序列
外排
按照排序键对元组进行排序是DBMS非常重要的操作。
外排序
两趟多路外存归并排序
第一阶段：创建归并段
第二阶段：归并
记法
创建归并段
演示看PPT
算法分析
多趟多路外存归并排序
优化
双缓冲
关系代数操作的执行
选择操作的执行
1 | 1.基于扫描的选择算法 |
记法
基于扫描的选择算法
基于哈希的选择算法
前提
基于索引的选择算法
前提
投影操作
去重操作
1 | 1.一趟去重算法 |
一趟去重算法
可在内存中用哈希表记录见过的元组，哈希键为整个元组。
基于排序的去重算法
基于哈希的去重算法
聚集操作的执行
与去重一样
集合差操作的执行
一趟集合差算法
基于哈希的集合差算法
基于排序的集合差算法
连接操作的执行
一趟连接算法
基于元组的嵌套循环连接
基于块的嵌套循环连接
排序归并连接
经典哈希连接
索引连接
查询计划的执行方法
物化执行
流水线执行
迭代器模型
十、查询优化
概论
查询优化：将一个关系代数表达式转换成一个可以快速执行的查询执行计划的过程。
查询优化的两个阶段：
1 | 逻辑查询优化； |
逻辑查询计划：关系代数表达式
物理查询计划：带有“如何执行”注释的关系代数表达式
逻辑查询计划
代价
基于代价的查询优化
查询计划枚举
等价关系代数表达式
若两个关系代数式在任意数据库实例上的结果都相同，则这两个关系代数表达式等价。
关系代数表达式的等价变换规则
$\theta$连接满足交换律，但不满足结合律。
选择下推
有关投影的等价变换规则
投影下推
逻辑查询计划的代价模型
逻辑查询计划的代价模型 VS 物理查询计划的代价模型
基数估计
基数估计：估计查询结果的元组数
要求：准确；易计算；逻辑一致
逻辑一致性
1 | 单调性：一个操作的输入越大，操作结果的基数估计值越大 |
笛卡尔积操作的基数估计
投影操作数的基数估计
选择操作的基数估计
二路自然连接的基数估计
集合操作的基数估计
去重操作的基数估计
属性值分布的精确近似
实际数据经常不满足均匀分布假设，导致基数估计的误差较大
直方图
等宽直方图
等高直方图
压缩直方图
连接顺序优化
连接关系的角色
连接树
左深连接树
物理查询优化
确定选择操作的物理执行算法
索引扫描+过滤
多索引扫描+求交集
仅用索引
顺序扫描
确定连接操作的物理执行算法
一趟连接：适用于左关系可以全部读入缓冲池的可用页面。
索引连接：适用于左关系较小，右关系在连接属性上建有索引
排序归并连接：
哈希连接：
嵌套循环连接：
查询计划的执行模型
十一、并发控制
事务
事务的ACID性质
持久性
一致性
隔离性
并发控制
调度
调度：调度是一个或多个事务的重要操作的序列。
串行调度：如果一个调度中不同事务的操作没有交叉，则该调度是串行调度
调度的正确性：单独执行每个事务都会将数据库从一种一致状态变为另一种一致状态
串行调度的正确性：任意串行调度都能保持数据库的一致性；不同的串行调度可能导致数据库处于不同的状态，但都是一致状态
异常
脏写
脏读
不可重复读
等价调度
可串行化调度
可串行化调度的优点
可串行化调度的缺点
并发控制隔离级别
在不同隔离级别下，一个事务修改过的对象的值对其他并发事务的可见程度不同
读未提交
未提交事务所做的修改对其他事务可见。
此级别下的异常
读提交
只有已提交的事务所做的修改才对其他事物可见。
此级别下的异常
可重复读
此级别下的异常
可串行化
并发控制可串行化
冲突可串行化
冲突
冲突等价
冲突可串行化调度
冲突可串行化测试
视图可串行化比冲突可串行化松
并发控制协议
并发控制协议分类
基于锁的并发控制
两阶段锁协议
基于2PL的调度是冲突可串行化调度
2PL的优缺点
级联终止
强两阶段锁SS2PL
严格调度
锁
死锁
死锁处理
死锁检测
等待图
死锁解除
死锁预防
锁的效率问题
锁的粒度
意向锁
相容矩阵
多粒度锁协议
锁升级
幻读
动态数据库
幻读
谓词锁
next- key锁
时间戳
Basic TO
Thomas写规则
不可恢复调度
Basic不足
OCC(不重要)
MVCC多版本并发控制
只有写和写冲突。
十二、故障恢复
故障
故障类型
事务故障
系统故障
存储介质故障
缓冲池策略
steal/no-steal 策略
force/no-force 策略
no-force是不强制在提交前写回磁盘
no-steal是不允许在事务提交前写回磁盘
缓冲池策略
WAL
预写式日志(write-ahead log)WAL
只有当日志写到磁盘上，才能代表事务提交。
基于WAL的故障恢复
事务的分类
故障恢复时的行为
WAL协议分类
Undo Logging
故障恢复
Redo Logging
故障恢复
Redo+Undo Logging
故障恢复
策略比较
组提交
检查点
WAL的问题
检查点
模糊检查点
涉及检查点的故障恢复
