数据库系统概念 - 笔记2

教材：Database System Concepts

参考的博客：

• Kisechan's Blog
• 数据库笔记 | 独角恋歌

涵盖内容：课本Chapter6-7，大致是E-R图和数据库设计部分

Chapter 6 Database Design Using the E-R Model

E-R Model

实体-联系模型 (Entity-Relationship / E-R 模型) 是一种语义建模方法：用意义 / 语义为核心来表述现实世界事物。

一些概念

• 实体：现实世界中，可区别于其他对象/事物的对象/事物；
• 属性：描述实体的性质或特征，实体的每个属性都有一个值；
• 实体集：相同类型或性质的实体集合；
• 联系：多个实体间的相互关联；
• 联系集：同类联系的集合。

举个例子：

• Student是一个实体集；
• 每个学生可以用学号区分，所以每一个学生是实体；
• 具体的学生，比如(ID=10001, name='Alice')才是一个实体；
• 对象之间的业务关系：比如student和course之间有takes联系，这就是联系集；
• takes $\neq$ 某一次具体选课，而是「学生选课这一类关系」的集合，其中的具体联系，是比如学生Alice选了CS61A，这就是一个联系

属性

• 简单属性：不可再分为更小的属性，比如StudentID
• 复合属性：可分，由其他属性组合而成，比如Address

graph TD
    Student --> StudentID
    Student --> Name
    Student --> Age
    Student --> Address

    Name --> FirstName
    Name --> LastName

    Address --> Province
    Address --> City
    Address --> Street

    Street --> StreetName
    Street --> StreetNumber

• 单值属性：针对特定的实体，只能取单一值的属性
• 多值属性：反之
• 派生属性：这个属性的值可以通过其他属性计算 / 推导得出

可以看这个 E-R Diagram，理解这些定义：

erDiagram
    STUDENT {
        string StudentID PK "学号 (单值属性)"
        string Name "姓名 (单值属性)"
        date BirthDate "出生日期 (单值属性)"
        string PhoneNumber "联系电话 (多值属性)"
        int Age "年龄 (派生属性，可由出生日期计算得到)"
    }

Mermaid是可以表示一系列UML的，比如上面这个mermaid图的源码是：

erDiagram
    STUDENT {
        string StudentID PK "学号 (单值属性)"
        string Name "姓名 (单值属性)"
        date BirthDate "出生日期 (单值属性)"
        string PhoneNumber "联系电话 (多值属性)"
        int Age "年龄 (派生属性，可由出生日期计算得到)"
    }

映射基数

• 映射基数：一个实体能通过联系集同时联系的实体的数量，常见映射基数有四类：

  • 一对一（one-to-one）：一个 A 最多对应一个 B，一个 B 也最多对应一个 A。比如“人”和“身份证号”。
  • 一对多（one-to-many）：一个 A 可以对应多个 B，但一个 B 最多对应一个 A。比如“院系”和“学生”。
  • 多对一（many-to-one）：从反方向看的一对多。比如“学生”和“院系”。
  • 多对多（many-to-many）：一个 A 可以对应多个 B，一个 B 也可以对应多个 A。比如“学生”和“课程”。

  

  E-R图里面的箭头指向的是「一」

• 参与约束：一个实体集中的实体是否必须参与到某个关系集中：

  • 全部参与：实体集中的每一个实体都至少参与到联系集中的一个联系；
  • 部分参与：实体集中只有部分实体参与到联系集合的联系中。
  • 如果规定每个学生入学后必须属于某个院系，那么 Student 对 belongs_to 是 全部参与（total participation）。
  • 如果有些教师暂时不参与任何科研项目，那么 Teacher 对 participates_in_project 可能是 部分参与（partial participation）。

绘制

图形符号	表示含义	描述说明
矩形	实体集	表示一个实体集合，如 Student、Course
双矩形	弱实体集	没有主键，依赖其他实体存在
椭圆	属性	表示实体或联系的属性
双椭圆	多值属性	一个实体可能有多个该属性的值（如电话）
虚线椭圆	派生属性	可由其他属性计算得出（如年龄）
菱形	联系集	表示两个或多个实体间的联系
线段	属性或联系的连接线	连接属性和实体，或实体和联系
双线	全部参与	表示该实体参与某个关系

E-R diagram for a university enterprise.

复杂约束

用图像式来描述约束只能描述：

• 箭头指向「一」的一方2
• 双线表示全部参与

不够精确。为了更精确的表达，引入更复杂的约束记法：

l..h

其中：

• l是最小基数，即至少需要参与多少个联系，实则对应参与约束；
• h是最大基数，即至多可以参与多少个联系，实则对应映射基数；
• *表示无上限。

Cardinality limits on relationship sets.

即：

• 一个instructor可以指导$[0, \infin]$个student
• 一个student必须有，且有且仅有一个advisor

概括地来说：

1..*

是全部参与，

0..*

是部分参与。

三元关系中的约束

假如某个联系涉及三个实体集，比如：

student -- project -- instructor

表示：某个学生在某个项目中由某个老师指导。

对于三元关系，规定最多只允许一个箭头，比如写成(student, project) -> instructor。

因为会有歧义。

Primary Key 主码

这里是从 E-R 图的角度去理解什么是主码。

实体集的主码：一组足以区分实体的属性。

联系集的主码：为了区分一个联系集中的不同联系，使用参与该联系的实体集的主码。

举个例子：

有联系集advisor(instructor, student)

• 其中instructor(ID, name)
• student(ID, name)
• 一个具体的advisor：(instructor.ID = 22222, student.ID = 10001)

这个联系集的超码就可以是(instructor.ID, student.ID)

回忆：super key

一个或多个属性的集合，其中可能包含冗余的属性。

在一个关系中唯一标识一个元组。

更一般地说，如果联系集 $R$ 涉及实体集 $E_1,E_2,\ldots,E_n$，那么 $R$ 的一个超码可以由这些实体集主码的并集组成：

$$ \operatorname{superkey}(R)=\operatorname{primary_key}(E_1)\cup\operatorname{primary_key}(E_2)\cup\cdots\cup\operatorname{primary_key}(E_n) $$

二元联系集的主码选择

对于二元关系 $$ A ;-; R ;-; B $$ 讨论联系集 $R$ 的主码如何选择，取决于映射基数。

简单概括：

• 多对多：两边的主码的并集作为主码；
• 一对多 / 多对一：用「多」的一方的主码（比如一个部门对应多个学生，当然用学生的主码）；
• 一对一：任意一方的主码均可。

弱实体集与冗余属性

何为冗余

从一个例子出发：大学数据库的section，一门课程在某个学期的具体开课班级。

我们可能这样设计section： $$ \text{section}(\text{course_id},\text{sec_id},\text{semester},\text{year}) $$ 同时设计一个联系集sec_course： $$ \text{sec_course}(\text{section},\text{course}) $$ 结果我们发现：

• section.course_id已经说明了这个section属于哪个course；
• sec_course也说明这个section属于哪门course。

并且，我们不能直接删掉联系集sec_course，因为：

• 如果删掉联系集，那么section和course这两个实体集之间的联系就不会再显式出现在 E-R 图中。
• 这不符合 E-R 图的目标，因为 E-R 图的目标就是清晰地展示对象之间的关系。

这就是「冗余」。

解决方案：只保留 $$ \text{section}(\text{sec_id},\text{semester},\text{year}) $$ 然后通过 sec_course 把 section 和 course 联系起来。这样只靠这些属性无法唯一识别一个section。

比如不同课程都会有 $(1,\text{Fall},2026)$，这就是弱实体集。

强实体集、弱实体集、标识实体集、分辨符

强实体集：可以用自己的属性形成主码的实体集，比如 $$ \text{course}(\underline{\text{course_id}},\text{title},\text{credits}) $$ 则 $\text{course_id}$ 唯一识别一门课程；

弱实体集：反之。比如 $$ \text{section}(\text{sec_id},\text{semester},\text{year}) $$ 这个实体集依赖于一个强实体集而存在，只能在某一门 course 内部区分 section。

标识实体集：帮助弱实体集完成唯一识别的强实体集。

分辨符：对于一个弱实体集，在一个标识实体内部区分不同的弱实体。

举例子：对于 section，${\text{sec_id},\text{semester},\text{year}}$就是一个分辨符，可以做到在同一门 course 内部，区分不同的 section。

可以理解为： $$ \operatorname{primary_key}(\text{section})=\operatorname{primary_key}(\text{course})\cup\operatorname{discriminator}(\text{section}) $$ 这里务必区分清楚弱实体集的分辨符、弱实体集的主码、弱实体集的标识实体集的主码之间的关系。

识别联系

识别联系 identifying relationship：弱实体集通过一个特殊联系连接到标识实体集。

从上面的例子而言，就是 $$ \text{sec_course}(\text{section},\text{course}) $$ 这个意义是告诉一个弱实体集的标识实体集，即：弱实体身份=标识实体主码+弱实体分辨符。

section 自己只知道：我是 sec_id=1, semester=Fall, year=2026 sec_course 告诉它：你属于 course_id=CS101 合起来才知道：你是 CS101 在 Fall 2026 的 section 1

在 E-R 图中的表示

弱实体集在 E-R 图中的表示

• 弱实体用双矩形表示；
• 分辨符用虚线下划线表示；
• 识别联系用双菱形表示。

弱实体集的存在依赖

所谓存在依赖：每个弱实体都必须关联到一个标识实体的性质。

也可以理解为：弱实体集对识别联系是全部参与。

冗余属性

回到何为冗余的部分，我们会在 E-R 图中移除这个冗余属性。

但是，在实现表的时候，还是会经常把这个冗余属性加回去。这是因为一个联系，在还原成表的时候，是不确定的。

E-R 图到关系模式的转换

这里还是得区分一下 E-R 图和关系模式：

• E-R 图的作用是表达现实语义；
• 关系型数据库存储数据使用的是关系模式，也就是表结构。

转换的基本思想

Entity sets and relationship sets can be expressed uniformly as relation schemas.

• 每个实体集或联系集都会被分配一个同名 schema，每个 schema 有若干列，列名一般来自属性名，而且列名必须唯一；
• 但是有些联系集对应的 schema 是冗余的，不一定真的需要保留成一张表。

实体集的转换

强实体集：直接转换成一个同名的关系模式，而各种属性保持不变。

理解：强实体集本来就可以独立存在，且存在主码。

弱实体集：保留两部分：

• 标识实体集的主码，
• 弱实体集自己的属性，尤其是分辨符。

即：弱实体集的属性： $$ \operatorname{schema}(\text{weak entity})=\operatorname{primary_key}(\text{identifying entity})\cup\operatorname{attributes}(\text{weak entity}) $$ 而弱实体集的主码： $$ \operatorname{primary_key}(\text{weak entity})=\operatorname{primary_key}(\text{identifying entity})\cup\operatorname{discriminator}(\text{weak entity}) $$

复合属性

复合属性不能作为一个列单独保留，举个例子，instructor有复合属性name，而name又分first_name和last_name，则在转换成关系模式时，全部展开来写。

多值属性

多值属性：针对特定的实体可以取多种值的属性。

如果实体集 $E$ 有多值属性 $M$，则为其单独创建一个关系模式 $EM$，包含：

• 实体集 $E$ 的主码；
• 多值属性 $M$ 本身。

举一个例子：

• instructor(ID, dept, phone_number)，其中phone_number是多值属性；
• 则，建立关系模式inst_phone(ID, phone_number)
• 比如说某个instructor的主码是12345，有两个电话号码，则这个表会存在两个关系，分别是(12345, 手机号1)和(12345, 手机号2)。

多对多联系集

必须单独建表。

比如 $\text{student} ;-; \text{takes} ;-; \text{section}$，一个学生可以对应多个section，一个section也可以对应多个学生。

• section是某门课在某年某个学期的具体开课
• takes是学生选了某个section并且可能有成绩

所以需要联系表： $$ \text{takes}(\underline{\text{student_id},\text{course_id},\text{sec_id},\text{semester},\text{year}},\text{grade}) $$ 从这里可以看出一般规则是： $$ \operatorname{schema}(R)=\operatorname{primary_key}(E_1)\cup\operatorname{primary_key}(E_2)\cup\operatorname{attributes}(R) $$ 且 $$ \operatorname{primary_key}(R)=\operatorname{primary_key}(E_1)\cup\operatorname{primary_key}(E_2) $$

一对多 / 多对一联系集

通常把外键放到「多」的一方。

比如 $\text{instructor} ;-; \text{inst_dept} ;-; \text{department}$：

• 一个 instructor 属于一个 department
• 一个 department 可以有多个 instructor
• 典型的多对一联系

无需建立一张 $\text{inst_dept}(\text{ID},\text{dept_name})$ 的表，只需把dept_id放入instructor表中即可。

联系集本身的属性也通常放入多方表中。

一对一联系表

任选一边放外键即可，但优先选全部参与的一边放外键，防止产生NULL。

什么时候联系集模式是冗余的

主要分成三类：

• 如果外键已经放入了多方表，则单独的联系表不再需要；
• 一对一的联系在任意一边加完外键之后，单独联系表也可以被省掉；
• 弱实体集的识别联系通常不再单独建表，因为通常的做法是直接把识别联系放入弱实体中。

扩展 E-R

1. 特殊化（specialization）：从一个大类拆出更具体的小类。
2. 一般化（generalization）：从多个小类抽象出共同的大类。
3. 聚集（aggregation）：把一个联系整体当成一个更高层对象来参与新的联系。

特殊化 & 一般化

就是 OOP 里面的「继承」关系。

Specialization and generalization

employee is a person，这里是 ISA 关系。

Overlapping and Disjoint

一个实体能不能同时属于多个底层实体集？

• overlapping：允许重叠，比如一个person可以同时是employee和student；
• disjoint：不允许重叠，子类之间互斥

完备性约束

一个高层实体是否必须属于至少一个底层实体集？

• total：每个高层实体都必须属于某个低层实体集，比如 All student entities must be either graduate or undergraduate.
• partial：反之。比如允许一个 person 既不是 employee 也不是 student。partial 是默认情况。

特殊化如何转化为关系模式

方法一

1. 为高层实体集建一个 schema。
2. 为每个低层实体集建一个 schema。
3. 低层实体集的 schema 包含高层实体集的主码和它自己的局部属性。

比如有 $$ \text{person}(\underline{\text{ID}},\text{name},\text{street},\text{city}) $$ 和底层实体集 $\text{student}(\text{tot_cred})$。

则可以转换为 $\text{student}(\underline{\text{ID}},\text{tot_cred})$。

此处 student.ID 是主码，也是 person.ID 的外键。

• 优点：避免重复存储高层属性；
• 缺点：访问低层实体的完整信息的时候需要连接两个关系

方法二

为每个实体集建表，包含所有继承属性和自身属性。

在 overlapping 场景下容易冗余。

聚集

将一个联系集和它涉及到的实体集整体当作一个新的高层实体来使用。

比如存在 $$ \text{proj_guide}(\text{student},\text{project},\text{instructor}) $$ 当成一个抽象实体，参与新的联系： $$ \text{eval_for}(\text{proj_guide},\text{evaluation}) $$

聚集转换为关系模式

创建一个 schema，包含：

• 被聚集联系的主码；
• 与它关联的实体集的主码；
• 描述属性。

$$ \operatorname{schema}(\text{aggregation relationship})=\operatorname{primary_key}(\text{aggregated relationship})\cup\operatorname{primary_key}(\text{associated entity})\cup\operatorname{descriptive_attributes} $$

E-R 设计判断

这里摘录一些我觉得比较容易误解 / 比较重要的点。

实体集与联系集

如果某个概念是在描述实体之间发生的动作或事实，通常应该建成联系集。，比如：

• 学生选课
• 老师指导学生
• 员工属于部门
• 课程开设 section

如果这个动作本身需要被单独管理、拥有身份或参与其他联系，才考虑提升为实体集。

联系属性的放置位置

与映射基数有关。

• 多对多联系：放在联系集上，比如 takes 的 grade；
• 一对多 / 多对一联系：放在多方；
• 一对一联系：任意。

Chapter 7 Relational Database Design

规范化总览

所谓「规范化」：

• 给定一个关系模式，判断其优劣；
• 若劣，如何分解成更好的关系模式同时不丢失信息？

坏设计的典型症状：同一份信息在 join 的时候被重复储存，导致维护困难、数据异常。比如department去 join instructor，则前者的 building 和 budget 会重复很多。

坏的设计带来的三类异常：

• 更新异常，比如想更新 Comp. Sci. 的预算，那么需要更新这张大表所有 dept_name = Comp. Sci. 的行，一旦漏改就会出现矛盾；
• 插入异常：如果要新增一个还没有老师的院系，这个大表的老师相关的属性不得不是一堆 NULL；
• 删除异常：如果某个院系最后一个老师被删除，院系的 building、budget 信息也会随之消失。

不能随便分解

比如刚刚说的设计，in_dep是冗余的，分解为两张表就好了。

但是，有些分解 join 回去却会产生错误的，多余的组合，这就是有损分解。

给出无损分解的定义：

设原关系模式为 $R$，分解为 $R_1$ 和 $R_2$​： $$ R = R_1 \cup R_2 $$ 对于 $R$ 上的一个关系实例 $r$，如果先把 $r$ 投影到 $R_1$ 和 $R_2$ 上，再自然连接回来，能够得到原来的 $r$，那么这个分解是无损的： $$ \Pi_{R_1}(r) \Join \Pi_{R_2}(r) = r $$ 如果连接回来比原来多了，那么就是有损分解： $$ r \subset \Pi_{R_1}(r) \Join \Pi_{R_2}(r) $$ 多的部分叫做假元组。

规范化理论的任务

1. 判断一个关系模式是否是好的形式
2. 如果不好，就将其分解成一组关系模式

函数依赖

引入

比如说对于 instructor ，只要其 ID 确定，那么 name 也就被唯一确定了。

这可以写作 $$ \text{ID} \rightarrow \text{name} $$ 念作：ID 函数决定 name。

定义

设 $R$ 是一个关系模式，$\alpha$ 和 $\beta$ 是 $R$ 的属性集，即 $\alpha \subseteq R,\quad \beta \subseteq R$。

函数依赖写作 $$ \alpha \subseteq R,\quad \beta \subseteq R $$ 在 $R$ 上成立当且仅当对任意合法关系实例 $r(R)$，任意两个元组 $t_1,t_2$，只要它们在 $\alpha$ 上取值相同，就必须在 $\beta$ 上取值相同。

这可以理解为左边是定义域右边是值域，所以叫函数依赖。

函数依赖集与闭包

假设有这样一个函数依赖集： $$ F={A\rightarrow B,\ B\rightarrow C} $$ 则可以推出 $A\rightarrow C$，「由已有的依赖推出新的依赖」，这叫做逻辑蕴含。

由 $F$ 可以推出的所有函数依赖的集合，叫做 $F$ 的闭包，记作 $F^+$。

函数依赖与超码 / 候选码

若属性集 $K$ 可以决定关系模式 $R$ 的所有属性，则 $K$ 是 $R$ 的超码。

而 $K$ 是候选码，当且仅当 $K\rightarrow R$ 并且不存在真子集 $\alpha \subset K$ 使得 $\alpha\rightarrow R$。

函数依赖的用途

• 测试某个具体关系实例是否合法：测试其是否满足其中所有函数依赖；
• 指定关系模式上的合法约束：$F \text{ holds on } R$ 当且仅当关系模式 $R$ 上的所有合法实例都满足 $F$。

平凡函数依赖

$$ \alpha\rightarrow\beta \text{ is trivial if } \beta\subseteq\alpha $$

比如说 $$ (A,B)\rightarrow A $$

依赖保持

用函数依赖证明二元分解是无损的

给定了函数依赖集 $F$ 和 二元分解 $R=R_1\cup R_2$，只需证明 $R_1\cap R_2 \rightarrow R_1$ 或 $R_1\cap R_2 \rightarrow R_1$，亦即只需证明上面这两个依赖至少有一个属于 $F^+$。

这是无损连接的充分条件。

依赖保持

原来关系模式上的函数依赖，在分解后的各个子关系中仍然可以直接检查，不需为了检查约束而将表连接。

举个例子，原来的关系模式有函数约束 $A \rightarrow B $：

• 假设分解之后，存在同时包含 $A$ 和 $B$ 的子表，则依赖可以直接检查，即存在依赖保持；
• 反之，则需要 join 几个表，才能检查。

形式化说法：

设原关系模式是 $R$，函数依赖集是 $F$，分解后得到 $R_1,R_2,\ldots,R_n$；对每个子模式 $R_i$，只保留那些完全落在 $R_i$ 内，可以在 $R_i$ 上检查的依赖，得到 $F_i$；若满足 $$ (F_1\cup F_2\cup\cdots\cup F_n)^+=F^+ $$ 则就说这个分解保持依赖。

范式

判断：

• 如何判断一个表是否有冗余
• 如何保证分解无损
• 如何保证依赖保持

BCNF

设 $R$ 是一个关系模式，$F$ 是 $R$ 上的函数依赖集。$R$ 关于 $F$ 满足 BCNF，当且仅当：对 $F^+$ 中所有形如 $\alpha \rightarrow \beta$ 的函数依赖，其中 $\alpha \subseteq R,\quad \beta \subseteq R$，满足以下条件之一：

• 这个函数依赖平凡，即 $\beta \subseteq \alpha$；
• $\alpha$ 是 $R$ 的超码，即 $\alpha \rightarrow R$。

举例：$\text{in_dep}$ 不满足 BCNF： $$ \text{in_dep}(\text{ID},\text{name},\text{salary},\text{dept_name},\text{building},\text{budget}) $$ 因为依赖 $\text{dept_name}\rightarrow(\text{building},\text{budget})$ 不平凡，同时 $\text{dept_name}$ 也不是其超码。

不符合范式带来的问题：数据冗余、增删查改的异常

有范式：1 2 3 BC 4 5(NF)，前面的包含后面的。

1NF：不能表中有表

2NF：消除所有对主属性的部分函数依赖关系

3NF：存在非主属性对主属性的传递函数依赖关系

BCNF：列出所有依赖关系，当且仅当左边全是候选码的时候满足 / 主属性内部不存在部分依赖和传递依赖关系

需要注意的是1 2 3都是和非主属性相关，而BCNF是只关注主属性内部

拆：跟谁好，复制自己，把它带走。

1 2 3 BC 都是函数依赖。

4NF：