DBMS 入门（复习）

Posted on 2025-05-10 繁/简： set

这门课我其实体验一般。不过 Chen Yi 老师是新加入 HKU 的，第一堂课，教学经验难免不足，希望之后能越来越好。

This article is a self-administered course note.

It will NOT cover any exam or assignment related content.

Introduction

为什么我们需要数据库管理系统 (Database Management System, DBMS) 以及 DBMS 的基本构成。

Vanilla 数据系统的六大问题：

Inefficiency. DBMS 使用 $B^+$ 树等数据结构！
Concurrent access problems. 诶，我更新呢？
Data isolation. 我的分隔符是 ;，你的分隔符是 /
Data redundancy & inconsistency. 数据散落在多个文件中很容易产生冗余/不一致。
Atomicity problems. 转账需要时间；取款账户扣款成功以后存款账户 crash 掉了怎么办？
Integrity problems. 对数据施加约束 (每个人的账户至少有 $200 存款) 的代价很高。

DBMS 的三个抽象层 (level of abstraction)：

物理层 (Physical level)
逻辑层 (Logical level)：描述数据间的关系，与下层的 physical data 相互独立。结构 Schema 与实例 Instance 都是该层的概念。
视图层 (View level)：类似 encapsulation，不同用户有不同视图，且不关心内部实现。简化了数据库的交互性。

DDL 解释器 (Data Definition Language Interpreter) 执行 CREATE, DROP 等数据定义语言并生成 schema。
DML 编译器 (Data Manipulation Language Compiler) 执行 ADD, DELETE, UPDATE 等数据操纵语言。查询优化 (query optimization) 也是在此进行的。

ER-Model

两个大知识点：如何画实体-关系图 (ER diagram) 与将如何将其翻译成架构 (schema)。

将 ER diagram 翻译为 schema；主键 (primary key) 用下划线表示，外键 (foreign key) 用斜体表示。

普通实体集 (entity set)：
- Customer (customer_id, name, address)
复合属性 (composite attribute) 展开：
- Customer (customer_id, name.first_name, name.last_name, address)
多值属性单开一个 table 表示 (Customer 里就不用写 Phone 了)：
- CustomerPhone (customer_id, phone)
弱实体集 (weak entity set) 的 table 中要加入强实体集的主键：
- Player (team_name, player_number, player_name)
多对多关系集 (many-to-many relationship set) 单开一个 table 表示 (两个外键构成复合主键 composite primary key)：
- Team_asoc_player (team_id, sponsor_id, sponsor_date)
一对多关系集且多边侧完全参与 (one-to-many RS with total on the many-side) 的关系集，多边侧的 table 中要加入单边侧的主键 (与弱实体集不同，这里单边侧的主键不构成复合主键)：
- Car (car_number, owner_id, price, ...)
部分参与的专门化 (specialization)
- Person (name, address, age)
- Customer (name, credit)
- Employee (name, salary)
完全参与的专门化 (total specialization)
- Customer (name, credit, address, age)
- Employee (name, salary, address, age)
- 注意，这里 name 并不是外键！很好理解，完全参与下 Person 的 table 没有必要保留了。(如需保留，前一种方法也可以继续使用)

关于超键 super keys $\to$ 候选键 candidate keys $\to$ 主键 primary key。

SQL

基本 SQL。详细的介绍每个语法意义不大。

掌握 CTE (Common Table Expression) WITH...AS...AS...SELECT... 与 nested query 会很有益处。

Relational Algebra

SQL 的底层逻辑是一系列关系代数 (relational algebra)。Query processor 基于此进行查询转换 (transformation) 与查询优化 (optimization)。它本身是一阶逻辑的分支，是闭合于运算下的关系的集合。

六个基本运算符 (Basic RA operators)：

Select $\sigma$
- 选择满足条件 $p$ 的行 $\sigma_p(R)=\{t | t\in R \land p(t)\}$
Project $\pi$
- 选择列 $\pi_{A_1,A_2,...,A_k}(R)$
Union $\cup$
- 求并集 $R\cup S=\{t|t\in R\lor t\in S\}$. $R$ 和 $S$ 的表头必须完全一致
Set difference $-$
- 求差集 $R-S=\{t|t\in R \land t\notin S\}$，$R$ 与 $S$ 的表头必须完全一致
Cartesian product $\times$
- 求笛卡尔积 $R\times S=\{tq|t\in R \land q\in S\}$，$R$ 与 $S$ 不能有同名字段 (实际操作中数据库会自动为同名字段加前缀如 R.id, S.id)
Rename $\rho$
- 重命名符 $\rho_X(E)$，$E$ 是一个关系代数表达式

五组额外运算符与 aggregation：

Set intersection $\cap$
- 求交集并非基础运算符 $R\cap S=R-(R-S)$，$R$ 和 $S$ 的表头要完全一致。
Natural join $\bowtie$
- 自然连接 $R\bowtie S=\pi_{R\cup S}(\sigma_{R.A_1=S.A_1\land ...\land R.A_n=S.A_n}(R\times S))$ where $R\cap S=\{A_1,A_2,...,A_n\}$
Assignment $\leftarrow$
- 定义关系变量如 $temp_1\leftarrow \pi_a(R)$, $temp_2\leftarrow \pi_a(S)$, $result\leftarrow temp_1-temp_2$
Left outer join $⟕$, Right outer join $⟖$
- 就是 LEFT JOIN 与 RIGHT JOIN 啦。LEFT JOIN 保留左侧所有 entry 右边补 null；RIGHT JOIN 反之。
Division $\div$
- 很重要的运算符。$R=\{\text{student}, \text{course}\}$ (学生的选课记录)，$S=\{\text{course}\}$ (一个必修课 list)，那么 $R\div S$ 表示所有选择了所有必修课的学生。
- $R\div S=\{t|t\in \pi_{R-S}(R)\land (\forall s\in S, ((t\cup s)\in R))\}$
- 实现：$R(X,Y), S(Y): R\div S=\pi_{X}(R)-\pi_X(\pi_X(R)\times S - R)$
- $R\times S\div S=R$
Aggregation $g$
- 即 GROUP BY。$ {G_1,...,G_n}g_{F_1,...,F_n}$，其中 $G_1,...,G_n$ 是分组属性，$F_1,...,F_n$ 则可以是一系列汇总函数如 AVG, SUM, COUNT, COUNT-DISTINCT 等等。

几个等价原则 (Equivalence rules)，用于查询优化 (这学期不考，无敌了)。

Database Normalization

函数依赖 (functional dependency, FD)。

数据库关系 $R$ 中两个属性集合间的约束。FD $X\to Y$，当且仅当 $R$ 上的每一个 $X$ 精确的关联 $R$ 上的一个 $Y$ (uniquely determine)。
形如 $XY\to X$ 的 FD 是平凡的。
依赖 (function dependency, FD) 并没有 explicit 的在 SQL 中表示，而是通过一系列超键的对应关系组织起来的。

Armstrong's Axiom.

自反性 reflexivity：若 $\beta\subseteq \alpha$，有 $\alpha\to \beta$
传递性 transitivity：若 $\alpha\to\beta,\beta\to\gamma$，有 $\alpha\to\gamma$
增广 augmentation：若 $\alpha\to\beta$，有 $\gamma\alpha\to\gamma\beta$
交 union：若 $\alpha\to\beta$ 且 $\alpha\to\gamma$，有 $\alpha\to\beta\gamma$
分解 decomposition：若 $\alpha\to\beta\gamma$，有 $\alpha\to\beta$ 与 $\alpha\to\gamma$
伪传递性 pseudo-transitivity：若 $\alpha\to\beta$ 且 $\gamma\beta\to\delta$，有 $\gamma\alpha\to\delta$

给定关系集 $R(\alpha,\beta,...)$ 与函数依赖集 $F$：

属性闭包 attribute closure $\alpha^+=\{\text{attributes functionally determined by }\alpha\}$。
函数依赖闭包 functional dependency closure $F^+=\{\text{all FDs logically implied by }F\}$。

无损连接 Lossless-join：关系 $R$ 分解后得到一系列子关系 $R_1,R_2,...,R_n$，将它们自然连接 (natural join) 起来后能完全还原 $R$ (如果有关 $R$ 的信息在分解后损失掉了，自然连接后的结果将会包括很多新的元组)。

无冗余 No redundancy：所有的 FDs 都由某个候选键决定，避免由于部份依赖或依赖的传递性造成的数据冗余。$R$ 有无冗余可以通过检查其是否符合 BC 正规形式 (Boyce-Codd Normal Form, BCNF) 来判定。

对于所有形如 $\alpha \to \beta$ 且属于 $F^+$ 的函数依赖，检查 $\alpha^+ = R$ 是否成立，即判断 $\alpha$ 是否为关系模式 $R$ 的超键。若存在任一 $\alpha$ 不是超键，则 $R$ 不符合 BCNF。

依赖保留 Dependency preserving：比如 $R(\alpha,\beta,\gamma), F=\{\alpha\to\beta,\alpha\to\gamma\}$。若把 $R$ 分解成 $R_1(\alpha,\beta)$ 与 $R_2(\gamma)$，那么 $\alpha\to\beta$ 在 $R_1$ 中被保留，$\alpha\to\gamma$ 则丢失了。所以我们想要在分解后仍然能保留所有的 FDs。在做题的时候可以发现，有些 FD 好像被丢失了，但其实可以通过 Armstrong's Axiom 还原，这点要注意。

若 $R$ 被分解为 $R_1,...,R_n$，对应的 $F$ 被拆成 $F_1,...,F_n$；依赖保留当且仅当 $(F_1\cup {...}\cup F_n)^+=F^+$。

解这类题目的算法：

唯一的变量在于选取 \alpha\to\beta 的顺序 — 唯一的变量在于选取 $\alpha\to\beta$ 的顺序

这只能保证 lossless-join 与 BCNF，因此在结束后要加一个 dependency preserving verification 的步骤。

Reference

This article is a self-administered course note.

References in the article are from corresponding course materials if not specified.

Course info: COMP3278 Introduction to Database Management Systems. Prof. Chen Yi

-----------------------------------そして、次の曲が始まるのです。-----------------------------------

Introduction

ER-Model

SQL

Relational Algebra

Database Normalization

More On...

Reference