数据库

dl…

引言

Database System(DBS, 数据库系统) 的组成

Database System(DBS, 数据库系统) 由以下部分构成:
- Database(DB, 数据库)
- Database Management System(DBMS, 数据库管理系统)
- Application Programs(应用程序)
- Users(用户),包括 Database Administrator(DBA, 数据库管理员)
DBMS(Database Management System, 数据库管理系统) 是位于 Users(用户) 与 Operating System(OS, 操作系统) 之间的一层数据管理软件,负责对数据库进行统一管理和控制

Data Models(数据模型)

Conceptual Model(概念模型)
- 从用户视角对现实世界中的数据和信息进行建模
- 主要用于数据库设计的需求分析阶段
- 典型代表: E-R Model(Entity-Relationship Model, 实体-联系模型)
Logical Model(逻辑模型)
- 从计算机系统视角对数据进行建模
- 用于描述数据的逻辑结构,不涉及具体存储细节
- 典型代表: Relational Model(关系模型),Network Model(网状模型)
Physical Model(物理模型)
- 描述数据在底层存储介质中的组织方式
- 关注数据的存储路径、存取方法等实现细节

Three-level Architecture(三级模式结构)

External Schema(View, 外模式/视图)
- 面向用户的数据视图
- 不同用户可以有不同的外模式
- 只描述用户关心的数据子集
Schema(Logical Schema, 模式/逻辑模式)
- 描述数据库中全体数据的逻辑结构和特征
- 是数据库设计的核心
- 一个数据库只能有一个 Schema
Internal Schema(Physical Schema, 内模式/物理模式)
- 描述数据在物理存储层的组织方式
- 关注文件结构、索引方式等
- 一个数据库只能有一个 Internal Schema

Data Independence(数据独立性)

Physical Data Independence(物理独立性)
- 当 Internal Schema(内模式) 发生变化(例如存储结构调整)时
- Schema(模式) 及 Application Programs(应用程序) 不需要修改
Logical Data Independence(逻辑独立性)
- 当 Schema(模式) 发生变化(例如增加属性或关系)时
- External Schema(外模式) 及 Application Programs(应用程序) 不需要修改

数据独立性是数据库系统区别于传统文件系统的核心优势之一,也是三级模式结构设计的主要目的

关系模型与 SQL

Relational Model

Key

自上而下范围越来越广:

主键(Primary Key)
- 在候选键中人为选定的
候选键(Candidate Key)
- 最小性: 候选键中不允许有多余的属性
超键(Super Key)
- 唯一性: 超键的值必须唯一地标识关系中的每个元组,不要求最小性

三类完整性约束 (Integrity Constraints)

实体完整性(entity integrity)：主码属性不能为空 (NULL)
参照完整性(referential integrity)：外码的值必须要么为空，要么是已存在的主码值
用户定义完整性(user-defined integrity)：针对具体应用的数据约束(如年龄>0)

外键约束(Foreign Key Constraint)

外键(Foreign Key): 在一个关系中，某个属性(或属性组)的值必须在另一个关系的主键(或候选键)中出现
参照完整性(Referential Integrity): 外键值必须在参照关系的主键(或候选键)中出现，或者为空(NULL)

外键约束

SQL

SELECT [ALL|DISTINCT] <目标列> FROM <表名或视图名> [WHERE <条件表达式>] [GROUP BY <列名1> [HAVING <组筛选条件>]] [ORDER BY <列名2> [ASC|DESC]];

#### select 语句
查询指定列的数据,返回结果集
- `SELECT *`: 查询所有列
- `DISTINCT`: 去除重复记录

#### where 子句
用于指定查询条件,过滤结果集(行)

```sql
SELECT column1, column2, ...
FROM table_name
WHERE condition;

condition 可以使用AND, OR, NOT等逻辑连接词,= <> != < <= > >=等比较运算符,IN等集合谓词

SELECT *
FROM Employees
WHERE Age > 30 AND Department = 'Sales';

like

用于在WHERE子句中搜索列中的指定模式

%: 代表零个或多个字符
_: 代表单个字符
ESCAPE 'c': 指定转义字符

SELECT * FROM table_name
WHERE column_name LIKE 'A%B_\\_' ESCAPE '\\';
-- 匹配以A开头,后跟任意长字符,再跟B,再跟任意一个字符,最后跟一个下划线的字符串

别名

用于为表或列指定临时名称,提高可读性

SELECT column_name AS alias_name
FROM table_name AS alias_table;

AS 关键字可以省略,但是需要避免和关键字混淆

聚合函数

用于对一组值进行计算并返回单个值

COUNT(column_name): 计算指定列的非NULL值的数量
SUM(column_name): 计算指定列的总和
AVG(column_name): 计算指定列的平均值
MAX(column_name): 返回指定列的最大值
MIN(column_name): 返回指定列的最小值

SELECT COUNT(*), AVG(salary), MAX(age) FROM employees;

分组查询

用于将结果集按一个或多个列进行分组,通常与聚合函数一起

SELECT department, COUNT(*), AVG(salary)
FROM employees
[WHERE 条件]
GROUP BY department
[HAVING 分组条件];

where 在分组前进行过滤,而 having 在分组后的结果进行过滤且可以使用聚合函数进行判断

-- 对组的条件筛选用 HAVING
SELECT Sno
    FROM SC
    WHERE Grade>=80
    GROUP BY Sno
    HAVING (COUNT(Cno)>=3);

子查询与谓词

ANY , ALL,EXISTS 用于在子查询中进行条件判断

ANY: 如果子查询返回的结果集中至少有一个值满足条件，则返回TRUE
ALL: 如果子查询返回的结果集中所有值都满足条件，则返回TRUE
EXISTS: 如果子查询返回至少一行结果，则返回TRUE

SELECT Sname, Sage
    FROM Student
    WHERE Sage < ANY(
        SELECT Sage
            FROM Student
            WHERE Sdept = 'CS'
    ) AND Sdept != 'CS';

SELECT Sname, Sage
    FROM Student
    WHERE Sage < ALL(
        SELECT Sage
            FROM Student
            WHERE Sdept = 'CS'
    ) AND Sdept != 'CS';

SELECT Sname
    FROM Student
    WHERE EXISTS(
        SELECT *
            FROM SC
            WHERE Sno=Student.Sno AND Cno='1'
    );

exist 也有用IN和’JOIN`的等价写法

SELECT DISTINCT s.Sname
FROM Student s
JOIN SC sc ON sc.Sno = s.Sno
WHERE sc.Cno = '1';

SELECT Sname
FROM Student
WHERE Sno IN (SELECT Sno FROM SC WHERE Cno='1');

设计与范式

ER模型

实体(Entity): 具有独立存在意义的事物，可以是具体的(如学生、课程)或抽象的(如课程安排、成绩单)
属性(Attribute): 实体的特征或性质
实体集(Entity Set): 同类实体的集合，如所有学生组成的学生实体
- 强实体集: 独立存在，有自己的主键
- 弱实体集: 依赖于其他实体，不能独立存在，没有自己的主键(对应关系数据库中的从表)
关系(Relationship): 实体之间的联系，如学生选修课程
关系集(Relationship Set): 同类关系的集合

约束

基数(Cardinality): 描述实体间关系的数量特征
- 一对一(1:1): 一个实体A对应一个实体B，反之亦然
- 一对多(1:N): 一个实体A对应多个实体B，但一个实体B只对应一个实体A
- 多对多(M:N): 一个实体A对应多个实体B，反之亦然

E-R 图

E-R 概念	转换后数据库对象
实体集	表（Table）
属性	列（Column）
关系集	外键或中间表
主键	主键约束（Primary Key）

转化为关系模型

实体集转换为表
- 实体集的属性转换为表的列
联系转换为外键或中间表
- 一对一(1:1)关系: 在任一实体集的表中添加外键，指向另一个实体集的主键
- 一对多(1:N)关系: 在“多”端的实体集表中添加外键，指向“一”端的主键
- 多对多(M:N)关系: 创建一个新表，包含两个实体集的主键作为外键，并将它们联合起来作为新表的主键

Normalization

对于一个schema $R$,怎么让其既不冗余又能正确反映表结构

函数依赖

在关系 $R$ 中，属性集$X$函数决定属性集$Y$，记作 $X$ -> $Y$，当且仅当对于$R$中的任意两个元组$t_1$和$t_2$，如果$t_1[X] = $t_2$[X]，则$t_1[Y] = $t_2$[Y]

Partial Functional Dependency / Full Functional Dependency

如果属性集$Y$依赖于$X$的一个真子集,则称$Y$部分函数依赖于$X$
如果属性集$Y$依赖于$X$,且不依赖于$X$的任何真子集,则称$Y$完全函数依赖于$X$

Armstrong 公理

自反性 (Reflexivity) : 如果 $Y$ 是 $X$ 的子集，则 $X \to Y$
增强性 (Augmentation) : 如果 $X \to Y$，则 $XZ \to YZ$
传递性 (Transitivity) : 如果 $X \to Y$ 且 $Y \to Z$，则 $X \to Z$

函数依赖找候选键

先找必选属性M
- 出现在所有函数依赖右部的属性(RHS)
- $M = 属性全集R - RHS(F)$
计算$M$的属性闭包$M^+$
若$M^+ = R$，则M是候选键且没有其他候选键,结束
否则,从$R-M$中选取属性加入$M$,直到$M^+=R$

正确性条件

Lossless Decomposition(无损分解)

分解后的关系可以通过自然连接恢复为原始关系,即

\[r = \Pi_{R_1}(r) \bowtie \Pi_{R_2}(r) \bowtie \cdots \bowtie \Pi_{R_n}(r)\]

在 3NF 分解中，只要分解结果 ρ 中存在一个关系模式包含原关系 R 的候选键，由于候选键的属性闭包覆盖整个 R，分解后的关系在自然连接时不会丢失信息，因此该分解一定是无损的

Dependency Preservation(依赖保持)

分解后的关系模式集合能够保持原始关系模式的所有函数依赖,即 $(F_1 \cup F_2 \cup ... \cup F_n)^+ = F^+$

规范覆盖(Canonical Cover)

定义

给定依赖集 $F$，若存在 $F_c$ 满足：

$F_c^+ = F^+$；
$F_c$ 中没有冗余依赖；
每个依赖右部仅包含单个属性；
不存在冗余（extraneous）属性；
左部唯一（不存在相同左部的两条依赖），
则称 $F_c$ 为 $F$ 的规范覆盖（Canonical Cover）

冗余属性(Extraneous Attribute)

属性 $A$ 在 $\alpha \to \beta$ 中是冗余的若：

若 $A \in \alpha$ 且 $(F - {\alpha \to \beta}) \cup {(\alpha - A) \to \beta}$ 推出 $F$；
或 $A \in \beta$ 且 $(F - {\alpha \to \beta}) \cup {\alpha \to (\beta - A)}$ 推出 $F$

算法

对于给定的函数依赖集 F

分解：将每个函数依赖 $α→β$ 中的右部拆分为单属性依赖
$\alpha \rightarrow Y_1Y_2…Y_n$ 转化为 $\alpha \rightarrow Y_1$, $\alpha \rightarrow Y_2$, …, $\alpha \rightarrow Y_n$
左部去冗余：对于每个函数依赖 $α→Y$ 中的每个属性 $A \in \alpha$，检查 $A$ 是否冗余，若是则移除
检查在$F-{α→Y} \cup {(α - A)→Y}$中是否能推出$Y \in (α - A)^{+}$
删除冗余依赖：对于每个函数依赖 $α→Y$，检查其是否冗余，若是则删除
检查在$F-{α→Y}$中是否能推出$Y \in \alpha^{+}$
合并：对于具有相同左部的函数依赖，合并其右部
$\alpha \rightarrow Y_1$, $\alpha \rightarrow Y_2$ 合并为 $\alpha \rightarrow Y_1Y_2$

第3步做完可以得出最小函数依赖集

范式分解

范式

第一范式(1NF): 所有属性值都是原子值
第二范式(2NF): 满足1NF，且所有非主属性完全依赖于主键
第三范式(3NF): 满足2NF，且不存在传递依赖
博茨-科得范式(BCNF): 满足3NF，$F^{+}$中的每个函数依赖 X → Y 中，X 都是超键

范式	主要目标	对所有非平凡函数依赖 X → A 的判定条件
1NF	保证属性值原子性	A 的取值必须是原子值
2NF	消除部分依赖	X 不是任何候选键 K 的真子集或 A 是主属性
3NF	消除传递依赖	X 是超码或 A 是主属性
BCNF	决定因素必须是候选键	X 是超码 (X → Y 可以分解)

平凡依赖在任何时候都不检查

3NF

3NF能消除大部分冗余,同时保持依赖和无损分解

分解算法

计算函数依赖集 $F$ 的规范覆盖 $F_{c}$
初始化分解结果$\rho \leftarrow \emptyset$
由$F_{c}$的每个函数依赖$\alpha \to \beta$，构造关系模式$R’ = \alpha \cup \beta$，并将其加入分解结果$\rho$
检查$\rho$中是否存在包含原关系$R$的候选键的关系模式, 如果不存在，选择$R$的任意一个候选键$K$，构造关系模式$R_{k} = K$，并将其加入分解结果$\rho$
若存在 $R_i, R_j \in \rho$，且 $R_i \subseteq R_j$（$i \neq j$），则删除 $R_i$

第三步保证依赖保持,第四步保证无损, $\rho$ 包含候选键是无损分解的充分条件

检测

对于每个FD $X \to A \in F$:

如果$X$是超键,则继续下一个依赖
否则,检查$A$是否为主属性(候选键中的属性)
- 如果是,继续下一个依赖
- 否则,关系不满足3NF

BCNF

BCNF是最强的范式,但不一定能保持依赖,所以实际应用中常退而求3NF

分解算法

检查当前关系R是否满足BCNF:
- 如果满足BCNF，停止分解，返回R
- 如果不满足BCNF，找到一个违反BCNF的非平凡函数依赖$X -> Y$
分解关系 $R$ 为两个子关系
- $R_{1} = X ∪ Y$
- $R_{2} = R - (Y - X)$

存储与索引

Storage

感觉更像OS的内容了

media / Hierarchy

Volatile : cache / memory
Non-volatile : disk / SSD / flash / tape
performance
T = seek time + rotational latency + data transfer time

RAID

RAID 0: Striping, 提高性能, 无冗余
RAID 1: Mirroring, 提高可靠性, 无性能提升
RAID 4: 块级条带化 + 专用奇偶校验盘
RAID 5: 块级条带化 + 分布式奇偶校验
RAID 6: 块级条带化 + 双重分布式奇偶校验

File Org & Buffer

略

Indexing

索引分类

clustered index / non-clustered index

clustered index: 数据存储顺序与索引顺序相同,索引叶即数据本体,每个表只能有一个聚集索引,默认引索是主键
non-clustered index: 数据物理顺序跟索引键无关,索引叶不存数据本体，而是存指向数据的指针,每个表可以有多个非聚集索引(范围查询产生大量random I/O)
dense index / sparse index
dense index: 每个搜索码值都有索引项,非聚集索引通常必须稠密
sparse index: 只有部分搜索码值有索引项,通常每个数据页/每个区间一个索引项
B+-Tree
平衡树的一种, 叶节点存数据指针/数据,非叶节点存索引键和子节点指针
B树 vs B+树
B树: 叶节点和非叶节点都存数据/数据指针
B+树: 只有叶节点存数据/数据指针, 内部只存子节点指针
Hash Index
Static Hashing: 固定桶数, 容易产生溢出(使用Overflow chaining 解决)
Dynamic/Extendable Hashing: 桶满了只分裂该桶, 不需要重建整个哈希表

查询优化

Algebra Optimization

SQL to Relational Algebra

select -> $\Pi$ (Projection)
where -> $\sigma$ (Selection)
from -> $\times$ (Cartesian Product)

通常一个未经优化的SQL查询会被转化为以下顺序的关系代数表达式: $\Pi_{A_{1}, ...}(\sigma_{condition}(R_{1} \times R_{2} \times ...))$

Initial Expression Tree

叶子节点:放置所有from子句中的基础表
内部节点
- 最底层是笛卡尔积节点($\times$),把叶子节点两两连接起来
- 笛卡尔积节点之上是选择节点($\sigma$),把where中的所有条件作为一个大的选择条件放在一起
- 最上层是投影节点($\Pi$),把select中的列放在一起

Optimization Rules

“Do selection as early as possible”: 将选择操作尽可能下推到靠近叶子节点的位置,减少中间结果集的大小,包括选择下推和投影下推

Equivalent Rules

常用的有：

$σ_{F1 \wedge F2}(E)=σ_{F1}(σ_{F2}(E))$
- 把一个复杂 where 拆成多个 σ，方便往下推
$σ_F(R×S)=σ_F(R)×S$
- σ 从 × 的上面 → 推到某个叶子表上
$\Pi_A(\Pi_{A,B}(E))=\Pi_A(E)$
- 一般反着用,用来添加不会改变结果的中间投影
$\Pi_{A,B}(R×S)=\Pi_A(R)×\Pi_B(S)$
- $\Pi$ 从 × 的上面 → 推到对应的叶子表上,形式上不允许A,B重叠

Steps

拆分选择

使用规则1将复杂选择条件拆分成多个串起来的$σ$

下推选择

使用规则2将只涉及某一关系的$\sigma$下推到对应的叶子节点上,穿过$\times$,直接移到对应的表或者$\times$上

下推投影

摘选出最终和连接条件相关的列,使用规则3创造中间投影节点
使用规则4将$\Pi$下推到对应的叶子节点上,穿过$\times$,在$\sigma$或者表上边

group,启发式优化

通过改变连接顺序进一步优化,减少中间结果集的大小

事务与并发

Transaction(事务)

ACID Properties

Acomicity: 要么全部完成,要么全部不完成
Consistency: 事务执行前后,数据库必须处于一致性状态,即仍满足所有约束
Isolation: 并发执行的事务彼此隔离,互不干扰
Durability: 事务一旦提交,其结果是永久性的

Failure and Recovery

Type	Recovery Action
Transaction failure	UNDO 未提交事务
System crash	UNDO 未提交，REDO 已提交（log 保证 transaction 幂等）
Disk Failure	依赖 backup，REDO 已提交
病毒&攻击	😎

Redundancy

Backup

Static Backup
Dynamic Backup(不阻塞操作)
Massive Backup
Incremental Backup(增量备份)
Log
在修改数据之前,先将日志记录写入稳定存储,为了确保原子性，若修改了数据库但日志没写，crash后无法回滚

记录Old and New value

recovery strategy

Transaction failure Backword scan日志, 加入UNDO队列并撤销
System crash
- Forward scan日志, 未提交加入UNDO队列, 已提交加入REDO队列
- Forward scan REDO队列,重做
- Backword scan UNDO队列,撤销

checkpoint

执行

输出日志到稳定存储
输出所有修改过的缓冲区到磁盘
写入checkpoint L记录到日志,此纪录需包含此刻活跃事务列表
恢复
找到最后一个L 记录, 取出所有L及之后执行的事务,recover

concurrency(并发)

problems

Lost Update(丢失更新): 两个事务同时读取同一数据项,然后都对其进行修改,最后一个提交的事务覆盖了第一个事务的修改
Dirty Read(脏读): 一个事务读取了另一个未提交事务修改的数据,如果后者回滚,前者读取的数据就变成了无效数据
Non-repeatable Read(不可重复读): 一个事务在两次读取同一数据项之间,另一个事务修改了该数据项,导致前者两次读取的结果不同
Phantom Read(幻读): 一个事务在两次执行相同的查询之间,另一个事务插入了满足查询条件的新记录,导致前者两次查询的结果不同

Locking Protocols

Shared Lock: S共享锁, 只允许读,可同时读,但是不可以同时写,可以加S锁
Exclusive Lock: X排他锁,允许读和写,不可继续锁

注:默认锁行,但是具体锁粒度可变

Isolation Levels

Isolation Level	Dirty Read	Non-repeatable Read	Phantom Read
Read Uncommitted	😭	😭	😭
Read Committed	👌	😭	😭
Repeatable Read	👌	👌	😭
Serializable	👌	👌	👌

Three-Level Locking Protocol

Level 1

修改数据+X锁,事务结束释放锁

读数据直接读

$\approx $ Read Uncommitted

Level 2

修改数据+X锁,事务结束释放锁

读数据+S锁,读完释放锁

$\approx $ Read Committed

Level 3

修改数据+X锁,事务结束释放锁

读数据+S锁,事务结束释放锁

$\approx $ Repeatable Read

2PL (Two-Phase Locking)

Conflict Serializability

如果一个调度可以通过交换不冲突指令的顺序变成串行调度, 则它是冲突可串行化的.

遵循 2PL 的调度一定是冲突可串行化的(和隔离等级那个不同,这个只保证之后后结果等价于串行调度)

Growing Phase: 事务可以获取锁,但不能释放锁
Shrinking Phase: 事务可以释放锁,但不能获取锁

Deadlock

当两个或多个事务互相等待对方释放锁时,就会发生死锁,死锁不可避免,只能预防和检测

疑似不怎么考,能判定即可,参考操作系统

引言

Database System(DBS, 数据库系统) 的组成

Data Models(数据模型)

Three-level Architecture(三级模式结构)

Data Independence(数据独立性)

关系模型与 SQL

Relational Model

Key

三类完整性约束 (Integrity Constraints)

外键约束(Foreign Key Constraint)

SQL

like

别名

聚合函数

分组查询

子查询与谓词

设计与范式

ER模型

约束

E-R 图

转化为关系模型

Normalization

函数依赖

Partial Functional Dependency / Full Functional Dependency

Armstrong 公理

函数依赖找候选键

正确性条件

Lossless Decomposition(无损分解)

Dependency Preservation(依赖保持)

规范覆盖(Canonical Cover)

定义

冗余属性(Extraneous Attribute)

算法

范式分解

范式

3NF

分解算法

检测

BCNF

分解算法

存储与索引

Storage

media / Hierarchy

performance

RAID

File Org & Buffer

Indexing

索引分类

clustered index / non-clustered index

dense index / sparse index

B+-Tree

B树 vs B+树

Hash Index

查询优化

SQL to Relational Algebra

Initial Expression Tree

Optimization Rules

Equivalent Rules

Steps

拆分选择

下推选择

下推投影

group,启发式优化

事务与并发

Transaction(事务)

ACID Properties

Failure and Recovery

Redundancy

Backup

Log

recovery strategy

checkpoint

执行

恢复

concurrency(并发)

problems

Locking Protocols

Isolation Levels

Three-Level Locking Protocol

Level 1