DMS mid-term
1. 绪论
模块化设计
为什么数据管理功能需要被构造成独立运行的系统？
数据管理需要消耗大量资源（包括CPU、内存、硬盘），独立系统可实现独立的资源调配，有利于资源的高效利用。
同一份数据有时候需要被多个应用程序共享，独立的系统有利于共享。
作为独立系统的一个好处是：当应用程序出错时，不容易牵连数据管理系统，造成数据损坏。
$\times$数据管理功能很复杂，复杂的功能需要成为独立的系统。
为什么要强调软件系统中模块与模块之间的隔离性？
便于各个模块的独立开发
当一个模块的实现需要改变时，不至于对其他模块造成较大影响
有利于程序的可读性
$\times$减少模块之间的交互，提升性能
如何让数据管理系统具备较高的隔离性(这里的隔离性是软件模块化意义上的，即让数据管理系统成为独立的与软件其他部分耦合度低的模块。)
让数据管理系统的职责明确
让数据访问的方式尽可能简单
尽可能将所有的数据都交给数据管理系统管理
$\times$让数据管理系统运行在独立的机器上
2. 文档数据库
分页模式的优势？
有利于减少存储空间的碎片化，提升空间利用率。
有利于提升数据访问的性能。
有利于减少空间管理的成本（即减少空间管理对CPU和内存资源的消耗）。
$\times$有利于提升内存缓存的效率。
小页面和大页面？
页缓存和文档缓存？
复合索引。
3. 文档数据库设计
冗余属性的好处和坏处？
- 好处：提升数据查询性能
- 坏处：降低数据更新性能、增加维护成本，增加软件开发复杂度
什么时候适合将一种对象嵌入另一种对象中存储？
- 子对象对父对象有明确的依附关系，比如一个书中的章节或者一个账户中的优惠券。
- 应用总是通过父对象去访问子对象，比如一篇文章的评论
- 一个子对象只属于唯一一个父对象，否则子对象会被多次存储
根据需求场景，设计文档数据库模式
4. 关系数据库
声明式编程语言（SQL）的优势。
程序简单
$\times$程序运行效率高
$\times$程序运行过程可控
关系代数。
- 选择、投影、连接、$\cdots$
索引可以加速哪些计算？
- 选择、投影（索引加速排序）和连接
关系代数的计算对象和结果都是集合。
根据需求场景写出关系代数表达式。
5. SQL
外键约束的作用。
- 告诉数据库系统数据中的引用关系
- 明确外键所在元组存在依赖于它指向的主键的存在
- 告诉数据库系统外键指向的主键不能被随意删除
主键如何定义，定义在单个属性还是复合属性上？
SQL查询和关系代数之间的关系？
- 一个SQL查询的结果不一定是一个关系（非distinct）
根据访问需求写出SQL语句（例）：
Student(s_no, s_name, birthday, gender)
Course(c_no, c_name, credit)
SC(s_no, c_no, grade)
- 找到在所有课程上的成绩都超过课程平均成绩的学生。
SELECT s_no, s_name
FROM Student x
WHERE NOT EXISTS (
SELECT *
FROM SC y
WHERE x.s_no = y.s_no
AND y.grade <= (
SELECT AVG(grade)
FROM SC z
WHERE y.c_no = z.c_no
)
);
嵌套查询和相关子查询。
视图的作用
- 视图的使用可以增加软件开发的效率
- 可以在视图上实施数据的增删改
- 可以在视图之上构建新的视图
6. 查询处理实现技术
给定查询和索引情况，给出执行效率最高的查询计划
- 先投影再连接
- 尽量不破坏索引
投影算子的实现：
- 外部排序
- 哈希
连接算子的三种实现（复杂度计算仅考虑内存与磁盘的IO次数）
$R$：外层循环关系个数，$S$：内层循环关系个数，$M$：内存能容纳的页数，$B(\cdot)$：存放关系需要的总页数
- 嵌套连接：$B(R)+\frac{B(R)}{M}B(S)$（外层关系先读满整个内存，然后循环读取内层关系，所有内层关系都记录后，换一批外层关系，一共$\frac{B(R)}{M}$轮）
- 散列连接：$3B(R)+3B(S)$（可以理解成分别外部排序后归并）
- 索引连接：单次索引代价Height_tree+1
7. 关系数据库设计
ER图
实体类
- 唯一属性（ID）
- 单值属性（记录在实体类对应的表中）
- 多值属性（记录在属性表中）
关系
- 一对一（记录在任意实体类表中）
- 一对多（记录在“多”对应的实体类表中）
- 多对多（记录在关系表中）
联系
- 联系的ID应该由参与联系的所有实体ID共同组成（即某组实体ID应唯一确定一个联系）
数据库设计的规范化
- 范式
数据冗余及如何利用冗余
表拆分
- 让同时被使用到的属性（即出现在同一个SQL中的属性）尽可能位于分拆后的同一张表中。
8. 数据正确性与事务处理
OLTP与OLAP
- OLTP：事务处理
- OLAP：历史数据
数据库系统的操作原子性。
- 两个并发的CRUD操作从效果上一定一个在前一个在后。（此处的原子性指效果上，而不是时间序列上）
- 任意一个CRUD操作要么发生在故障之前，要么发生在故障之后。
- 在故障发生前没有结束的CRUD操作一定会被撤销。
undo日志
- 在修改变量前记录日志，记录修改前的值，用于还原操作开始执行前的状态
- 若某日志结束，如log
redo日志：
- 在修改变量后记录日志，记录修改后的值，用于重新执行未执行完毕的操作，使系统到达执行后的状态
- 若日志未结束，如log
分析undo/redo日志操作执行序列的正确性：分析故障发生在哪个瞬间，对每个瞬间作分析
例：我们用log表示将日志写到硬盘，用write表示把数据写到硬盘。如果系统使用redo日志，那么以下哪个操作执行序列是不正确或不可能发生的？
log(o1,start), log(o1,A=5), log(o1,end), log(o2,start), log(o2,A=6), log(o2,end), write(A=6)
正确，原因：redo日志以log(end)作为操作的瞬间，由end的先后可知o1先于o2发生，即o2应覆盖o1操作的结果。没有write(A=5)是由于系统可能先在内存中缓存数据再写入磁盘，而A=5还在内存中时就被A=6覆盖了。
log(o1,start), log(o2,start), log(o2,A=6), log(o2,end), log(o1,A=5), log(o1,end), write(A=5), write(A=6)
错误，原因：同样的道理，由于日志以log(end)作为操作的瞬间，此处o2先于o1发生，那么o1应覆盖o1操作的结果，但操作中write(A=6)覆盖了write(A=5)，因此不正确
undo/redo日志
- 可以先将变量缓存在内存中，并在任何需要的时候写入磁盘，写入磁盘的时机相对于undo日志或者redo日志更加自由
防止数据异常
- 标志位、消息队列
事务属性
- ACID：原子性 Atomicity、一致性 Consistency、隔离性 Isolation、持久性 Duration
合理使用事务
- 事务应尽可能短小简单
- 避免将用户交互放入事务
- 调整操作顺序，将无需保证原子性的操作移出事务
二阶段锁
- 第一阶段：获得锁（扩展阶段）
- 第二阶段：释放锁（收缩阶段）
- 即在释放第一把锁之前，需要先拿到所有需要的锁
操作幂等性
- 执行任意多次的效果一致
日志和锁如何配合使用来确保操作原子性：
undo日志：log(o1,start); lock(A); log(o1,A=5); write(A=6); log(o1,end); unlock(A);
即需要注意日志结束后才可释放锁，否则考虑释放锁后执行了其他使用到A的操作，且执行时出现故障，那么系统将还原到o1执行前的状态（由于还没有记录o1结束的日志），但释放锁后的操作不一定能成功还原
9. 总结和比较
文档数据库和关系数据库的比较
易用性：
文档数据库对于开发人员更自然（以对象为单位存储）
关系数据库表达能力强（建立在关系模型上，用SQL语言作表达），可以在数据库完成复杂的逻辑，而不是应用层
可控性：
文档数据库更可控，事务处理实现在开发者控制范围内，扩展性较高
关系数据库功能的实现不在应用开发者控制范围内，应用层和数据库实现效率不同，不可控。
数据库实现方式固化，通常不能很好的应对应用需求，扩展后性能下降明显