关系代数

基本运算

这五种运算是关系代数的基础，可以表达所有关系代数查询。

运算	数学符号	含义	SQL 对应
选择 (Select)	$σ_P(R)$	从关系 R 中选择满足条件 P 的元组（行）。	`WHERE` 子句
投影 (Project)	$Π_{A1,A2,...}(R)$	从关系 R 中选择指定的属性（列）。	`SELECT` 子句
并 (Union)	$R\cupS$	返回两个关系中所有元组的集合，并去除重复。要求 R 和 S 兼容（属性数量和类型相同）。	`UNION`
差 (Set Difference)	$R-S$	返回在关系 R 中但不在关系 S 中的元组。要求 R 和 S 兼容。	`EXCEPT` (或 `MINUS`)
笛卡尔积 (Cartesian Product)	$R\timesS$	将关系 R 和 S 的所有元组进行所有可能的组合。	`FROM R, S` 或 `CROSS JOIN`

附加运算

这些运算可以由基本运算导出，但在实际使用中非常方便。

运算	数学符号	含义	SQL 对应
交 (Intersection)	$R\capS$	返回同时存在于关系 R 和 S 中的元组。要求 R 和 S 兼容。	`INTERSECT`
连接 (Join)
– θ-连接	$R⋈_θS$	相当于 $\sigma_{\theta}(R \times S)$ ，基于任意比较条件 $θ$ 连接。	`... ON condition`
– 自然连接	$R⋈S$	一种特殊的等值连接，自动对同名属性进行连接，并去除重复列。	`NATURAL JOIN` 或 `JOIN ... USING(...)`
除 (Division)	$R\divS$	寻找关系 R 中与关系 S 中所有元组都有关系的元组。常用于“查询…所有…”的场景。	没有直接对应的操作符，通常用 `NOT EXISTS` 或 `GROUP BY ... HAVING COUNT(...)` 实现。
赋值/重命名 (Assignment/Rename)	$ρ_X(E)$	将表达式 E 的结果命名为 X。	`AS` (别名)

SQL 语句

1. 基础查询: SELECT, FROM, WHERE

核心功能: 从表中筛选（WHERE）出符合条件的行，然后提取（SELECT）出指定的列。
关系代数对应: $Π...(σ...(R))$ (先选择，后投影)
用法示例: 检索“计算机科学”系教师的姓名和工资。
```
SELECT name, salary
FROM instructor
WHERE dept_name = 'Comp. Sci.';
```

2. 连接查询: JOIN

核心功能: 基于两个表之间的共同字段将它们合并。
关系代数对应: $R⋈_PS$ ( $θ-$ 连接)

用法示例: 检索所有教师的姓名以及他们所教授的课程 ID。

SELECT name, course_id
FROM instructor
INNER JOIN teaches ON instructor.ID = teaches.ID;

3. 集合运算: UNION, INTERSECT, EXCEPT

核心功能: 对两个查询的结果集进行并、交、差操作。
关系代数对应: $\cup$ (并), $\cap$ (交), $-$ (差)

用法示例: 使用 EXCEPT 找出在2017年秋季开设，但没有在2018年春季开设的课程。

(SELECT course_id FROM section WHERE semester = 'Fall' AND year = 2017)
EXCEPT
(SELECT course_id FROM section WHERE semester = 'Spring' AND year = 2018);

4. 子查询: IN

核心功能: IN 用于判断某个字段的值是否在一个子查询返回的结果集合中。
关系代数对应: 通常可通过连接 (⋈) 操作实现。
用法示例: 找出所有选修了 ‘001’ 号课程的学生的姓名。
```
SELECT Sname FROM Student
WHERE S# IN (SELECT S# FROM SC WHERE C# = '001');
```

5. 相关子查询: EXISTS

核心功能: EXISTS 用于检查子查询是否返回了至少一行数据，常用于需要内外查询联动的场景。
关系代数对应: 逻辑较为复杂，通常也对应连接操作。

用法示例: 找出所有有老师的院系。

SELECT dept_name FROM department D
WHERE EXISTS (
    SELECT * FROM instructor I
    WHERE I.dept_name = D.dept_name
);

6. “包含所有”查询 (除法)

核心功能: 通过双重否定逻辑（NOT EXISTS… EXCEPT … NOT EXISTS）实现“查询…所有…”的复杂需求。
关系代数对应: ÷ (除法)

用法示例: 检索选修了E6号老师所讲授的全部课程的学生学号。

SELECT DISTINCT S.S#
FROM Student S
WHERE NOT EXISTS (
    -- (不存在 E6老师教的课) - (该学生选的课) 这个差集不为空
    (SELECT C# FROM Course WHERE T# = 'E6') -- E6老师教的所有课
    EXCEPT
    (SELECT C# FROM SC WHERE SC.S# = S.S#)  -- 该学生选的所有课
);

7. 分组与聚合: GROUP BY, HAVING

核心功能: GROUP BY 用于将数据行分组，HAVING 用于在分组后对组进行条件筛选。
扩展关系代数对应: G (分组聚合运算)
用法示例: 查询选修课程超过2门且平均成绩大于80分的学生学号及平均分。
```
SELECT S#, AVG(Score) AS avg_score
FROM SC
GROUP BY S#
HAVING COUNT(C#) > 2 AND AVG(Score) > 80;
```

例题解析

数据库关系模式:

职工表: EMP(E#, ENAME, AGE, SEX, ECITY)
工作表: WORKS(E#, C#, SALARY)
公司表: COMP(C#, CNAME, CITY)

1. 检索超过 50 岁的男职工的工号和姓名。

关系代数:
- 首先，在 EMP 表中选择 AGE > 50 并且 SEX = '男' 的职工。
- 然后，投影出这些职工的 E# 和 ENAME。

SELECT E#, ENAME
FROM EMP
WHERE AGE > 50 AND SEX = '男';

2. 检索在编号为 C4 和 C8 公司兼职的职工工号和姓名。

关系代数:
- 找出在 C4 公司工作的职工工号。
- 找出在 C8 公司工作的职工工号。
- 对上述两个结果取交集，得到同时在两家公司工作的工号。
- 将结果与 EMP 表进行自然连接，以获取姓名。
Π_{E#,ENAME}\left((Π_{E#}(σ_{C#=\text{‘C4’}}(WORKS)))∩(Π_{E#}(σ_{C#=\text{‘C8’}}(WORKS)))⋈EMP\right)

SELECT E#, ENAME FROM EMP WHERE E# IN (
    SELECT E# FROM WORKS WHERE C# = 'C4'
    INTERSECT
    SELECT E# FROM WORKS WHERE C# = 'C8'
);

3. 检索每个职工的兼职公司数目和工资总数。

SELECT E#, COUNT(C#) AS NUM, SUM(SALARY) AS SUM_SALARY
FROM WORKS
GROUP BY E#;

4. 求不在 C3 公司工作的职工姓名。

关系代数:
- 找出所有职工的姓名。
- 找出在 C3 公司工作的职工姓名。
- 从所有职工姓名中减去在 C3 工作的职工姓名。
Π_{ENAME}(EMP)−Π{ENAME}(σ\{C#=\text{‘C3’}}(WORKS)⋈EMP)

SELECT ENAME FROM EMP
EXCEPT
    SELECT E.ENAME
    FROM EMP E, WORKS W
    WHERE E.E# = W.E# AND W.C# = 'C3';

SELECT ENAME
FROM EMP
WHERE E# NOT IN (
    SELECT E# FROM WORKS WHERE C# = 'C3'
);

5. 检索至少在 E6 职工兼职的所有公司工作的职工工号。

这是一个典型的“包含所有”的查询，需要使用除法。

关系代数:
- 目标：找到一个职工 E#，他工作的公司集合（WORKS 表中的 (E#, C#) 对）包含了 E6 职工工作的所有公司 C#。
- 首先，找出 E6 工作的所有公司的编号集合 C_E6。
- 然后，用 WORKS 表中的 (E#, C#) 对集合去除以 C_E6 集合。

设 $C{E6}=Π{C#}(σ{E#=\text{‘E6’}}(WORKS))$ ，则查询为： $\Pi{E#, C#}(WORKS) \div C_{E6}$ 。

SQL (使用 GROUP BY):

SELECT W.E#
FROM WORKS W
WHERE W.C# IN (SELECT C# FROM WORKS WHERE E# = 'E6')
GROUP BY W.E#
HAVING COUNT(DISTINCT W.C#) = (SELECT COUNT(C#) FROM WORKS WHERE E# = 'E6');

SQL (使用 NOT EXISTS):

SELECT DISTINCT E#.E#
FROM WORKS E#
WHERE NOT EXISTS (
    SELECT C# FROM WORKS WHERE E# = 'E6'
    EXCEPT
    SELECT C# FROM WORKS WHERE E# = E#.E#
);

6. 检索联华公司中低于本公司平均工资的职工工号和姓名

SELECT E.E#, E.ENAME
FROM WORKS W
JOIN COMP C ON W.C# = C.C# 
JOIN EMP E ON W.E# = E.E#
WHERE C.CNAME = '联华'
  AND W.SALARY < (
      SELECT AVG(SALARY) 
      FROM WORKS W2 
      WHERE W2.C# = W.C#
  );

7. 为50岁以上职工在每一公司加薪100元

UPDATE WORKS
SET SALARY = SALARY + 100
WHERE E# IN (
    SELECT E# FROM EMP WHERE AGE > 50
);

8. 删除年龄大于60岁的职工相关元组

DELETE EMP, WORKS
FROM EMP
JOIN WORKS ON EMP.E# = WORKS.E#
WHERE EMP.AGE > 60;

ER 模型

1. 识别实体 (Entity)

定义: 实体是现实世界中客观存在且可以相互区分的事物，如一个学生、一家商店、一件商品。在E-R图中用矩形表示。
规范:
- 从需求描述中找出名词，这些通常是实体。例如，“仓库”、“商店”、“商品”、“经理”、“收银员”。
- 实体应该是独立存在的，有自己明确的属性。

2. 识别属性 (Attribute)

定义: 属性是实体所具有的某一特性，如学生的姓名、商品的名称。
规范:
- 为每个实体确定描述其特征的属性。
- 确定主键 (Primary Key): 从属性中选择一个或一组能够唯一标识实体的属性作为主键（或称主码），主键属性应有下划线。例如，商品实体的“商品编号”。
- 区分不同类型的属性：
  - 简单属性 vs. 复合属性: 复合属性可以再细分，如“姓名”可以分为“姓”和“名”。
  - 单值属性 vs. 多值属性: 多值属性可以有多个值，如一个商品可以有多个销售价格。

3. 识别并定义联系 (Relationship)

定义: 联系反映了实体之间的相互关联。例如，商店“销售”商品。在E-R图中用菱形表示。
规范:
- 从需求描述中找出动词或介词短语，这些通常是联系。例如，“管理”、“工作在”、“销售”、“供应”。
- 联系本身也可以有属性。例如，“销售”联系可以有“销售数量”属性。

4. 确定联系的基数 (Cardinality)

定义: 基数描述了参与一个联系的各个实体集之间能关联的实体数量。这是E-R设计的关键，决定了表之间的转换关系。
常见类型:
- 一对一 (1:1): 一个商店只有一个经理，一个经理只管理一个商店。
  
  商店 –(1)– 管理 –(1)– 经理
- 一对多 (1:N): 一个商店有多个收银员，但一个收银员只在一个商店工作。
  
  商店 –(1)– 拥有 –(N)– 收银员
- 多对多 (M:N): 一个商店销售多种商品，一种商品也可以在多个商店销售。
  
  商店 –(M)– 销售 –(N)– 商品

5. 处理特殊情况

弱实体 (Weak Entity): 如果一个实体的存在依赖于另一个实体（标识性实体），则称其为弱实体。例如，“家属”实体的存在依赖于“职工”实体。弱实体用双线矩形表示，其标识性联系用双线菱形表示。

例题：超市业务信息系统 E-R 模型设计

业务规则分析与E-R设计映射:

“该超市公司有若干仓库，若干连锁商店，供应若干商品。”
- 识别出三个核心实体: 仓库、商店、商品。
- “供应”是一个联系，但具体是仓库供应商店，还是仓库供应商品，需要进一步明确。通常是仓库存储商品，再由仓库向商店配送。这里可以简化为仓库与商品之间、商店与商品之间存在联系。
“每个商店有一个经理和若干收银员，每个收银员只在一个商店工作。”
- 识别出实体: 经理、收银员。
- 联系1: 商店与经理是“管理”关系，基数为 1:1。
- 联系2: 商店与收银员是“雇佣”关系，基数为 1:N。
“每个商店销售多种商品，每种商品可在不同的商店销售。”
- 联系3: 商店与商品是“销售”关系，基数为 M:N。
“每个商品编号只有一个商品名称，但不同的商品编号可以有相同的商品名称。每种商品可以有多种销售价格。”
- 为商品实体确定属性：商品编号 (主键)、商品名称。
- “销售价格”是多值属性。更好的处理方式是，价格与商店有关，即同一种商品在不同商店的售价可能不同。因此，“销售价格”更适合作为“销售”（商店与商品）这个联系的属性。
“超市公司的业务员负责商品的进货业务。”
- 识别出实体: 业务员。
- 联系4: 业务员与商品之间是“进货”关系。一个业务员可以进多种商品，一种商品也可以被多个业务员负责。基数为 M:N。

E-R 模型图设计:

根据以上分析，我们可以绘制出如下的E-R图：

图例说明:

实体 (矩形):
- 商店 (主键: 商店编号)
- 经理 (主键: 经理编号)
- 收银员 (主键: 收银员编号)
- 商品 (主键: 商品编号)
- 业务员 (主key: 业务员编号)
- 仓库 (主键: 仓库编号)
联系 (菱形) 与基数:
- 管理 (1:1): 连接 商店 和 经理。
- 雇佣 (1:N): 连接 商店 和 收银员。
- 销售 (M:N): 连接 商店 和 商品。这个联系有一个属性：销售价格。
- 负责进货 (M:N): 连接 业务员 和 商品。
- 存储 (M:N): 连接 仓库 和 商品。这个联系有一个属性：库存数量。

范式

1.1 为什么需要规范化？—— 不良设计的弊端

一个“坏”的关系模式设计会导致多种问题：

数据冗余 (Data Redundancy)：相同的信息被重复存储在多个地方。
- 例子：在一个包含教师和其所在系的表中 inst_dept(ID, name, salary, dept_name, building, budget)，一个系的信息会随着该系的每一位教师重复出现。
- 缺点：浪费存储空间，并可能导致数据不一致。
更新异常 (Update Anomaly)：当修改某条冗余信息时，需要修改所有出现该信息的地方，否则数据将不一致。
- 例子：若要修改 Computer Sci. 系的 budget，必须更新所有 Computer Sci. 系教师的记录。
插入异常 (Insertion Anomaly)：无法存储某些信息，除非同时存储另一些不相关的信息。
- 例子：如果想新增一个还没有教师的系，则无法插入，因为教师的 ID 和 name 不能为空。
删除异常 (Deletion Anomaly)：当删除某条记录时，可能会丢失另一些本应保留的信息。
- 例子：如果删除了最后一名 Music 系的教师，那么关于 Music 系本身的信息也会随之丢失。

1.2 目标：模式分解 (Decomposition)

为了解决以上问题，我们需要将一个大的、有问题的关系模式 R 分解为一组更小、更“好”的关系模式 {R₁, R₂, …, Rₙ}。

1.3 第一范式 (1NF)

定义：关系模式R的所有属性域都是 原子 (atomic) 的，即属性值不可再分。
这是关系数据库的最基本要求，我们之后讨论的范式都默认建立在1NF之上。

1.4 函数依赖 (Functional Dependency, FD)

核心思想：属性之间的约束关系。
定义：对于关系模式R中的属性集 α 和 β，如果对于R中任意两个元组，只要它们在 α 上的值相同，它们在 β 上的值就必然相同，则称 β 函数依赖于 α 或 α 函数决定 β，记作 α → β。
平凡FD：如果 β ⊆ α，则 α → β 是平凡的。例如 (ID, name) → ID。
键与FD的关系：
- 超码 (Superkey)：如果属性集 K 能函数决定关系中的所有属性（即 K → R），则 K 是超码。
- 候选码 (Candidate Key)：是最小的超码，其任何真子集都不是超码。

第二章：函数依赖的理论与计算

2.1 Armstrong 公理

一套用于从已知的FD集合F推导出所有隐含的FD（即闭包F⁺）的规则。

自反律 (Reflexivity)：若 β ⊆ α，则 α → β。
增补律 (Augmentation)：若 α → β，则 γα → γβ。
传递律 (Transitivity)：若 α → β 且 β → γ，则 α → γ。

2.2 属性集闭包 (Attribute Closure, α⁺)

定义：在函数依赖集F下，由属性集α函数决定的所有属性的集合。
用途：
1. 判断超码：如果 α⁺ 包含了关系R的所有属性，那么α是R的超码。
2. 判断FD是否成立：要判断 α → β 是否能由F推出，只需计算 α⁺，检查 β 是否包含于 α⁺ 中。
计算算法：
```
result := α;
while (result 有变化) do
  for each (β → γ) in F do
    if (β ⊆ result) then
      result := result ∪ γ;
return result;
```
- 示例：R=(A,B,C,G,H,I)，F={A→B, A→C, CG→H, CG→I, B→H}。求 (AG)⁺：
  1. result = {A, G}
  2. 应用 A→B, A→C，result = {A, B, C, G}
  3. 应用 CG→H，result = {A, B, C, G, H}
  4. 应用 CG→I，result = {A, B, C, G, H, I}
  5. result 不再变化，所以 (AG)⁺ = {A, B, C, G, H, I}。

2.3 候选码的求解

通过属性闭包，系统地找出所有候选码。基本思想是：将所有属性分为L（只在左部）、R（只在右部）、N（左右都出现）、I（都不出现）四类。所有候选码一定包含 I 和 L 类中的所有属性。

2.4 正则覆盖 (Canonical Cover, Fc)

定义：与F等价的一个“极小”的FD集合，不含冗余依赖和冗余属性。
计算步骤：
1. 合并：使用合并律，将所有左部相同的FD合并。例如，A → B 和 A → C 合并为 A → BC。
2. 去冗余属性：
  - 左部：检查 Aβ → γ 中的A是否冗余。计算 β 在原F下的闭包 β⁺，看是否包含γ。如果包含，则A冗余。
  - 右部：检查 α → Bγ 中的B是否冗余。在 F' = (F - {α → Bγ}) ∪ {α → γ} 下，计算α的闭包 α⁺，看是否包含B。如果包含，则B冗余。
3. 去冗余依赖：对Fc中的每个FD α → β，检查在 F' = F - {α → β} 中，是否仍能推导出 α → β（即检查 α⁺ 是否包含 β）。如果可以，则该FD冗余。

第三章：范式与分解算法

3.1 分解的两个重要特性

无损连接 (Lossless Join)：分解后，通过自然连接必须能恢复出原关系，不多也不少。
- 检验：对于 R 分解为 R₁ 和 R₂，当 (R₁ ∩ R₂) → R₁ 或 (R₁ ∩ R₂) → R₂ 在 F⁺ 中成立时，分解是无损的。简言之，交集必须是其中一个的超码。
依赖保持 (Dependency Preservation)：原关系F中的所有FD，都应该能在分解后的某个子模式中被单独验证。

3.2 BCNF (Boyce-Codd Normal Form)

定义：对于关系R中所有 非平凡 的FD α → β，α 都必须是R的超码。
优点：消除了所有由函数依赖引起的冗余。
BCNF分解算法：
1. 检查关系R是否属于BCNF。
2. 如果不是，找到一个违反BCNF的FD α → β。
3. 将R分解为 R₁ = α⁺（即α和β以及所有能被α决定的属性）和 R₂ = (R - (α⁺ - α))。
4. 对分解出的新关系递归地执行此过程。
特性：分解一定是 无损连接 的，但 不一定保持依赖。

3.3 3NF (Third Normal Form)

定义：对于关系R中所有 非平凡 的FD α → β，必须满足以下条件之一：
1. α 是R的超码。
2. β - α 中的每个属性都是 主属性（即包含在R的某个候选码中）。
与BCNF的区别：3NF放宽了条件，允许决定簇不是超码，只要它决定的都是主属性即可。
3.4 3NF分解算法：
1. 计算F的 正则覆盖 Fc。
2. 对Fc中的每一个FD α → β，生成一个关系模式 Rᵢ = αβ。
3. 检查所有已生成的 Rᵢ 是否包含了R的某个候选码。如果没有，则将R的任意一个候选码作为新的关系模式加入。
特性：分解一定是 无损连接 且 保持依赖 的。

3.4 BCNF vs. 3NF 对比

特性	BCNF	3NF
定义	决定簇必须是超码	决定簇是超码，或被决定的是主属性
冗余	消除所有FD冗余	可能存在少量冗余
无损连接	保证	保证
依赖保持	不保证	保证
权衡	规范化程度最高，但可能牺牲依赖保持	实践中最常用的选择，在冗余和依赖保持间取得平衡

第四章：高级范式

4.1 多值依赖 (Multivalued Dependency, MVD)

背景：有时一个关系即使在BCNF，仍存在冗余。
定义：α →→ β 表示，对于一个α值，有一组β值与之对应，且这组β值与关系中其它属性（R-α-β）的取值相互独立。
例子：classes(course, teacher, book)，一个课程有多个老师，也需要多本书，但老师和书无关。此时存在 course →→ teacher 和 course →→ book。

4.2 第四范式 (4NF)