数据库期末复习整理

第一章：基本概念和关系代数

关系型数据库 relational database

1. 一些基本特点：

• 关系型数据库是一系列表的集合

• 一张表是一个基本单位

• 表中的一行表示一条关系

1. 码 key

• superkey一个关系中可以唯一标识某个元组的若干属性集合
• 即任意两个元组的超码是不同的
• 若A是某个关系的超码，那么(A,B)也是某个关系的超码

• candidate key任意真子集不是超码的超码，不含任何多余属性
• 最小的超码

• primary key 管理员认定的candidate key

• foreign key 在某个关系R1中作为关系R2的primary key，就可以称为R1的外码

1. 关系运算

2. SQL关系的定义

1. SQL语句的查询操作

• select：支持含有四则运算的算术表达式，运算对象可以是常数或属性。可用select distinct 来去重，也可用select all 显式指明无需去重。默认不去重。用select * 查询表中所有属性

• from：定义了所有列出关系上的笛卡尔积。若列出的多个关系有重名属性，必须以表名为前缀 来区别

• where：支持逻辑连词and or not ，也支持between and 指定查询范围。支持比较运算 符。

• 内连接(natural join)：常用于from 子句中的关系运算，将两个在同名属性上具有相同值的关系对应的操作大大简化。
• join ... using (...) ：只需要在指定属性上的取值匹配。
• join ... on P ：满足谓词 P 即匹配。

• 外连接(out join)： left / right / full outer join 只保留出现在左边/右边/全部关系中的元组。

• 更改名字
• 为了引用简洁或便于区分，可在 from 子句中使用as new_name 进行关系更名，select 也支持更名。

• 元组显示次序
• order by att_name ，用desc 表示降序， asc 表示升序。默认升序。
• order by salary desc, name asc 表示按工资降序排列，然后如果工资相同的情况下，在按照姓名首字母进行升序排列

• 集合之间的运算操作
• union, intersect, except 分别对应集合中的并集、交集、差集运算。可以用来连接两条不同的查询语句。 三者都是自动去重的，若要保留重复项必须在后面加all

• 聚集函数
• 固有聚集函数： avg / max / min / sum / count
• 可以使用distinct 关键字来去重（ count(*) 时不行）
• group by 进行分组聚集，对某个属性而言，将具有相同值的元组放在一个组里
• 省略该语句表示将整个关系视为一个分组。后面也可以用having 子句对分组限定条件，效果等同where 。只有在形成分组后才起作用。select 对最后生成的分组进行筛选
🦄
需保证任何没有出现在group by 子句中的属性，如果出现在select/having 语句 中，则必须在聚集函数中。
下述SQL语句返回表中平均工资大于 10000 的人名并去重。

• 空值unknown/null
• 将涉及空值 null 的任何比较运算的结果视为 unknown（true / false 外的第三种逻辑值），算术运算的结果视为 null。
• 可以通过 is known 和 is null 来测试是否为未知或者是空值
• 除了count(*) 外的所有聚集函数都忽略输出集合中的空值。同时规定空值的count 运算值为 0，其他所有聚集运算在输入为空值的情况下返回一个空值

• 嵌套子循环查询
• 子查询是嵌套在另一个查询中的select - from - where 表达式。对于select / from /where 后面任意关系可以出现的位置，都可以被替换为一个子查询。用in / not in 表示某些属性是否在子查询返回的关系中。
• 来自外层查询中重命名的相关名称可以用在子查询中，称为相关子查询。
• 集合的比较： some + subquery ：存在某值即可； all + subquery ：对所有值进行比较。
• 空关系测试： exists + subquery 判断是否存在某关系。not exists(B except A) 判断关系 A 包含关系 B。
• 重复元组存在性测试： unique 判断查询结果无重复元组。
• from 中的子查询：子查询不能使用子句中其他关系的相关变量，除非用lateral 作为前缀。
• with 子句：定义临时关系，这个定义只对包含with 子句的查询有效。

• SQL语句的修改

第二章节 数据库的设计和ER模型

E-R模型

1. 实体是独特的对象，可以看作是一个类，实体可以用过一些列属性进行描述，而实体集是由一系列相同性质或属性的实体组成的集合。在图中用矩阵进行表示，然后主码用下划线进行表示

2. 关系集是相同类型关系的集合，是多个实体集上的数学关系。参与联系集的实体集数目称为联系集的度。在图中用菱形标识。关系集也可以附带属性，用虚线连接

3. 约束
• 映射函数：在 E-R 图中箭头表示一，直线表示多 三元关系中箭头只能出现一次，否则会导致混淆
• 参与约束：若实体集中的每个实体都参与到关系集的至少一个关系中，则称为完全参与(totalparticipation) ，在 E-R 图中用双直线表示；反之则称为部分参(partial participation)
• 弱实体集：没有足够的属性以形成主码，与强实体集（含有主码）相对。弱实体集必须与强 实体集有关系。弱实体集的分辨符由下划虚线标注，其主码由其分辨符加上标识实体集的主码构成。弱实体集与强实体集的联系需用双线菱形。

4. 特化与概化 在实体内部进行分组的过程称为特化，自顶向下，实体内容不断细分，但继承上一级的属性。 多个实体集根据共有的特征综合成一个较高层的实体集，称为概化，自底向上。

5. 聚集
一个部分中所有的实体集均与同一个关系集相关联，则可把这部分合成为一个实体，在 E-R 图中用一个大方框框起来表示。

6. 关于E-R图

范式(Normal Form)

XML

1. XML语言的定义和结构

索引与查询

1. 替换策略
1. LRU策略
2. MRU策略

2. 文件组织
1. 数据库存储在一系列的文件中
2. 每一个文件是一系列的records，每条记录包含一系列的fields
3. Free List 用链表的形式来存储records
4. 存储和读取访问寻址比较简单
5. 记录的长度不能超过block

• 顺序索引索引记录按顺序存储 如：稠密索引、稀疏索引

• 散列索引
如：索引记录随机分布

事务

• 性质 原子性(Atomicity)：事务中的所有步骤只能 commit 或者回滚 rollback 一致性(Consistency)：单独执行事务可以保持数据库的一致性 隔离性(Isolation)：事务在并行执行的时候不能感知到其他事务正在执行，中间结果 对于其他并发执行的事务是隐藏的。 持续性(Durability)：更新之后哪怕软硬件出了问题，更新的数据也必须存在。

• 状态
active：初始状态，执行中的事务都处于这个状态。 partially committed：在最后一句指令被执行之后。 failed：在发现执行失败之后。 aborted：回滚结束，会选择是重新执行事务还是结束。 committed：事务被完整的执行。

• 并发执行
同时执行多个事务，可以提高运行的效率，减少平均执行时间。
调度(Schedule)：一系列用于指定并发事务的执行顺序的指令。需包含事务中的所有指令，且 保证单个事务中指令的相对顺序。 事务的最后一步 成功执行：commit instruction 执行失败：abort instruction 串行调度(Serial Schedule)：一个事务调度完成之后再进行下一个。 等价调度(Equivalent Schedule)：改变处理的顺序但是和原来等价。 冲突等价(Conflict Equivalent)：如果调度 S 可以通过一系列非冲突指令交换转换为 S' ，则称 S 与 S' 等价。
对同一数据项而言，当且仅当两个指令都是读时不引发冲突，其执行顺序无关紧要若两条指令针对的数据项不同，则读写都不冲突。
冲突可串行化(Conflict Serializability)：当 S 与一个串行调度等价时，称 S 是冲突可串行化的。 优先图(Precedence graph)：顶点集由所有参与调度的事务组成，当事务 冲突 并且 先访问出现冲突的数据的时候，则有边 。一个调度是冲突可串行化的当且仅当优先图是无环图。对于无环图，可以使用拓扑排序获得一个合适的执行顺序。

• 恢复系统
更新日志记录描述一次数据库写操作，字段如下： 1. 事务标识：是执行 write 操作的事务的唯一标识。 2. 数据项标识：是所写数据项的唯一标识，通常是数据项在磁盘上的位置。 3. 新值/旧值：是数据项写前/后值。
表示为 ，表明事务 对数据项 执行一次写操作，写前值为 ，写后值为 。 数据库修改 延迟修改(deferred-modification)：事务直到提交的那一刻才对数据库进行修改。 立即修改(immediate-modification)：在事务活跃期间便对数据库进行修改。 检查点： 用来提高恢复过程的效率，其中 是执行检查点时正活跃的事务的 列表。对于检查点前的事务不执行操作，其后的事务根据有无 commit 或 abort 来执行重做 (redo)或撤销(undo)操作。在崩溃发生后，只需反向搜索日志，找到最后一条检查点记录即 可。 重做：将数据项的值设为新值。 撤销：将数据项的值设为旧值。

ARIES

1. 什么是数据库恢复？

1. ARIES算法的基本概念
1. 事务日志 log 记录所有事务操作的日志，确保可以追踪到每一个操作。
2. 检查点 checkpoint 定期记录系统的状态，减少恢复的时间
3. 页 page 数据库的数据存储单位，通常是数据块。

2. ARIES算法的三个步骤
1. 分析阶段
2. 重做阶段 redo
1. 确保所有已经提交的事务所做的操作都被应用到数据库中
2. 从分析阶段确定的起点开始，重新执行已经提交的事务的所有操作，确保数据库反映出这些操作的结果。
3. 撤销阶段 undo
1. 撤销所有未提交的事务，保证它们的操作不会影响数据库的最终状态
2. 按照事务日志的逆序，撤销未提交事务的操作，使数据库回到一致的状态

🦄

下面我们给出一道例题：

Aries recovery method is used in a DBMS. Following figure is a log file just after the DBMS crashes. The log file consists of 14 log records with LSN from 6001 to 6014. The PrevLSN and UndoNextLSN values in the log records are not shown in the figure. Assuming that the last completed checkpoint is the log record with LSN 6008. Please answers following questions about the Aries recovery process.

1. From which log record does the Analysis Pass start?
分析阶段从最近的检查点（Checkpoint）开始。在图中，最近的检查点是6008，因此分析阶段从日志记录6008开始。

2. When the Analysis Pass is complete, what is the content of the DirtyPageTable?
分析阶段的主要任务是构建Transaction Table和Dirty Page Table。
在检查点6008时：
• Transaction Table包含：
• T1的LastLSN是6002
• T2的LastLSN是6007
• T3的LastLSN是6006
• Dirty Page Table包含：
• 页1001的PageLSN是6004，RecLSN是6002
• 页1002的PageLSN是6005，RecLSN是6005
• 页1003的PageLSN是6007，RecLSN是6006
从检查点6008开始，到最后一个日志记录6014，继续更新Dirty Page Table：
• 6009: T1 commit，不影响Dirty Page Table。
• 6010: 页1004的操作，PageLSN是6010，RecLSN是6010，加入Dirty Page Table。
• 6011: T4 begin，不影响Dirty Page Table。
• 6012: 页1003的操作，更新页1003的PageLSN为6012。
• 6013: 页1004的操作，更新页1004的PageLSN为6013。
• 6014: T3 commit，不影响Dirty Page Table。
最终Dirty Page Table的内容是：
• 页1001: PageLSN是6004，RecLSN是6002
• 页1002: PageLSN是6005，RecLSN是6005
• 页1003: PageLSN是6012，RecLSN是6006
• 页1004: PageLSN是6013，RecLSN是6010
答案：

PageID	PageLSN	RecLSN
1001	6004	6002
1002	6005	6005
1003	6012	6006
1004	6013	6010

3. From which log record does the Redo Pass start?

4. Which transactions should be Undone?
T2和T4需要被撤销

5. Which log records is the start point of the Undo Pass? Which log record is the end point of the Undo Pass?

问题1：分析阶段从哪个日志记录开始？

问题2：分析阶段结束时，DirtyPageTable的内容是什么？

• Transaction Table包含：
• T1的LastLSN是6002
• T2的LastLSN是6007
• T3的LastLSN是6006

• Dirty Page Table包含：
• 页1001的PageLSN是6004，RecLSN是6002
• 页1002的PageLSN是6005，RecLSN是6005
• 页1003的PageLSN是6007，RecLSN是6006

• 6009: T1 commit，不影响Dirty Page Table。

• 6010: 页1004的操作，PageLSN是6010，RecLSN是6010，加入Dirty Page Table。

• 6011: T4 begin，不影响Dirty Page Table。

• 6012: 页1003的操作，更新页1003的PageLSN为6012。

• 6013: 页1004的操作，更新页1004的PageLSN为6013。

• 6014: T3 commit，不影响Dirty Page Table。

• 页1001: PageLSN是6004，RecLSN是6002

• 页1002: PageLSN是6005，RecLSN是6005

• 页1003: PageLSN是6012，RecLSN是6006

• 页1004: PageLSN是6013，RecLSN是6010

问题3：重做阶段从哪个日志记录开始？

问题4：哪些事务需要撤销？

问题5：撤销阶段的起点和终点日志记录是什么？

• T2的最后一个LSN是6007（从检查点中可以看出）。

• T4的最后一个LSN是6013（从日志中可以看出）。

• T4从6013开始撤销。

• T2从6007开始撤销。

• 撤销阶段起点：日志记录6013。

• 撤销阶段终点：日志记录6003。

1. 分析阶段从日志记录6008开始。

2. 分析阶段结束时，DirtyPageTable内容如下：

1. 重做阶段从日志记录6002开始。

2. 需要撤销的事务是T2和T4。

3. 撤销阶段的起点是日志记录6013，终点是日志记录6003。

具体应用场景

在重做阶段：

• 重做阶段从Dirty Page Table中最小的RecLSN开始，遍历日志记录。

• 对于每一个日志记录，检查其对应页面的PageLSN。
• 如果日志记录的LSN大于页面的PageLSN，表示该页面没有应用该日志记录中的修改，需要重做该操作。
• 如果日志记录的LSN小于或等于页面的PageLSN，表示该页面已经包含了该日志记录中的修改，无需重做。

• Which log record is the start point of Redo Pass?

• Which log record is the end point of Undo Pass?

复习课

SJL期末复习

hash-join

1. 有哪些算法 merge hash

2. 关于join的基数估计，会返回多少元组

3. 选中率

4. hash join
1. 最小要分成几块

5. 竞争假定，均匀分布