当前位置：首页 > news >正文

《软件设计师》复习笔记（4.2）——关系代数、函数依赖、范式

news 来源：原创 2025/8/15 12:28:26

一、关系代数

基本运算

笛卡尔积（×）

投影（π）

选择（σ）

自然连接（⋈）

真题示例：

二、函数依赖

基本概念

Armstrong公理系统

键与约束

三、范式（Normalization）

第一范式（1NF）

第二范式（2NF）

第三范式（3NF）

BC范式（BCNF）

真题示例：

一、关系代数

基本运算
- 并（∪）：合并两张表的所有记录，重复记录仅显示一次。
  - 示例：S1 ∪ S2 结果包含 S1 和 S2 的所有不重复记录。
- 交（∩）：返回两张表中相同的记录。
  - 示例：S1 ∩ S2 结果为 Sno='No0001', Sname='Mary', Sdept='IS'。
- 差（-）：返回第一张表有而第二张表没有的记录。
  - 示例：S1 - S2 结果为 Sno='No0003' 和 No0004 的记录。
笛卡尔积（×）
- 结果包含两表所有属性列，记录数为两表记录数的乘积。
- 示例：S1 × S2 的每条记录是 S1 和 S2 记录的排列组合。
投影（π）
- 选择某表的特定列（可用列名或列序号表示）。
- 示例：π(Sname)(S1) 返回 S1 的所有学生姓名。
选择（σ）
- 按条件筛选表中的记录。
- 示例：σ(Sdept='IS')(S1) 返回 Sdept 为 IS 的记录。
自然连接（⋈）
- 合并两表中属性相同且值相同的记录，相同属性列仅显示一次。

真题示例：

给定关系R(A, B, C, D)和关系S(C, D, E)，对其进行自然连接运算R⋈S后的属性列为（）个；与σR.B>S.E(R⋈S)等价的关系代数表达式为（）。

A. 4 B. 5 C. 6 D. 7

A. σ₂>₇(R×S) B. π₁,₂,₃,₄,₇(σ'₂' > '₇' ∧₃=₅∧₄=₆(R×S))

C. σ'₂' > '₇'(R×S) D. π₁,₂,₃,₄,₇(σ₂>₇∧₃=₅∧₄=₆(R×S))

1. 计算自然连接运算 R⋈S 后的属性列个数

自然连接是一种特殊的等值连接，它要求两个关系中进行比较的分量必须是相同的属性组，并且在结果中把重复的属性列去掉。关系 R(A,B,C,D) 有 4 个属性，关系 S(C,D,E) 有 3 个属性，其中 C 和 D 是公共属性。进行自然连接时，重复的公共属性 C 和 D 只保留一次，所以 R⋈S 后的属性列为 A、B、C、D、E，共 5 个。

2. 找出与 σR.B>S.E(R⋈S) 等价的关系代数表达式

σR.B>S.E(R⋈S) 表示先对 R 和 S 进行自然连接，然后从连接结果中选择满足 R 中的属性 B 大于 S 中的属性 E 的元组。在进行关系代数运算时，一般先将自然连接转换为笛卡尔积和选择、投影运算。

首先将 R⋈S 转换为笛卡尔积 R×S 并添加等值连接条件，即 σR.C=S.C∧R.D=S.D(R×S) 。
然后要从结果中选择满足 R.B>S.E 的元组，完整的选择条件就是 σR.B>S.E∧R.C=S.C∧R.D=S.D(R×S) 。
用属性的序号表示，R×S 后的属性顺序为 R.A（第 1 列）、R.B（第 2 列）、R.C（第 3 列）、R.D（第 4 列）、S.C（第 5 列）、S.D（第 6 列）、S.E（第 7 列），那么选择条件可写为 σ2>7∧3=5∧4=6(R×S) 。
最后，由于最终结果不需要重复的 C 和 D 列（在自然连接中重复列已被去掉），所以需要对结果进行投影，保留 A、B、C、D、E 对应的列，即 π1,2,3,4,7(σ2>7∧3=5∧4=6(R×S)) 。

二、函数依赖

基本概念
- 函数依赖：若属性 X 能唯一确定 Y，则称 Y 依赖于 X（记作 X→Y）。
- 部分函数依赖：若 (A,B)→C，但 A→C 也成立，则 C 部分依赖于 (A,B)。
- 传递函数依赖：若 A→B、B→C 且 A 与 B 不等价，则 A→C 是传递依赖。
Armstrong公理系统

函数依赖的公理系统(Armstrong) 设关系模式R<U，F>，U是关系模式R的属性全集，F是关系模式R的一个函数依赖集。对于R<U，F>来说有以下的：
- 自反律（Reflexivity）
  - 若属性集Y是属性集X的子集（Y⊆X），则必然存在函数依赖X→Y。
  - 示例：若X={A,B,C}，Y={A,B}，则X→Y自动成立。
- 增广律（Augmentation）
  - 若存在X→Y，则对任意属性集Z，有XZ→YZ。
- 传递律（Transitivity）
  - 若X→Y且Y→Z，则必然有X→Z。
- 合并规则（Union）
  - 若X→Y且X→Z，则可合并为X→YZ。
- 伪传递规则（Pseudo-transitivity）
  - 若X→Y且WY→Z，则XW→Z。
  - 示例：若学号→姓名，(姓名,课程)→成绩，则(学号,课程)→成绩。
- 分解规则（Decomposition）
  - 若X→Y且Z⊆Y，则X→Z。
  - 示例：若A→{B,C}，则A→B和A→C均成立。
键与约束
- 超键：能唯一标识此表的属性的组合。
- 候选键：超键中去掉冗余的属性，剩余的属性就是候选键。
- 主键：任选一个候选键，即可作为主键。
- 外键：其他表中的主键。
- 主属性：候选键内的属性为主属性，其他属性为非主属性。
- 实体完整性约束：即主键约束，主键值不能为空，也不能重复。
- 参照完整性约束：即外键约束，外键必须是其他表中已经存在的主键的值，或者为空。
- 用户自定义完整性约束：自定义表达式约束，如设定年龄属性的值必须在0到150之间。

三、范式（Normalization）

第一范式（1NF）
- 表中每个字段不可再分（无嵌套表）。
- 原始表（不符合1NF）：
  
  员工ID 员工姓名薪资/月
  001 张三基本工资:5000, 补贴:1000
  002 李四基本工资:6000, 补贴:800
  
  1NF规范化后：
  
  员工ID 员工姓名基本工资补贴
  001 张三 5000 1000
  002 李四 6000 800
第二范式（2NF）
- 满足1NF，且非主属性完全依赖于候选键（消除部分依赖：每一个非主属性不会依赖复合主键中的某一个列）。
- 原始表（不符合2NF）：
  
  学号课程号课程名称成绩教师
  S001 C001 数学 90 王老师
  S001 C002 英语 85 李老师
  
  问题：课程名称和教师仅依赖于课程号（部分依赖复合主键 (学号, 课程号)）。
  2NF规范化后：
  选课表（完全依赖）：
  
  学号课程号成绩
  S001 C001 90
  S001 C002 85
  
  课程表（消除部分依赖）：
  
  课程号课程名称教师
  C001 数学王老师
  C002 英语李老师
第三范式（3NF）
- 满足2NF，且非主属性不传递依赖于候选键。
- 原始表（不符合3NF）：
  
  学号姓名系编号系主任
  S001 张三 D01 刘主任
  S002 李四 D02 陈主任
  
  问题：系主任传递依赖于学号（学号 → 系编号 → 系主任）。
  3NF规范化后：
  学生表：
  
  学号姓名系编号
  S001 张三 D01
  S002 李四 D02
  
  系表（消除传递依赖）：
  
  系编号系主任
  D01 刘主任
  D02 陈主任
BC范式（BCNF）
- 满足3NF，且所有依赖的左侧必须包含候选键。
- BC范式要求在满足第三范式的条件下，进一步消除主属性对于码的部分函数依赖和传递依赖。简单通俗地讲，对于关系模式中的任意一个函数依赖X→Y（X是决定因素，Y是被决定因素），X必须是候选键或者包含候选键。也就是说，每一个函数依赖的左边决定因素都必然包含候选键，只有满足这样的条件，关系模式才符合BCNF。
  - 在给定的例子中有一个涉及S、T、J三个属性的关系模式，通过分析其依赖关系和候选键来判断是否符合BCNF：
  - 候选键与依赖集：该关系模式的候选键有两种情况，分别是组合键(S, T)和(S, J)，依赖集为{SJ→T，T→J} 。由于S、T、J这三个属性都能通过候选键组合确定，所以它们都是主属性，因此该关系模式达到了3NF（因为不存在非主属性，也就不存在非主属性对码的部分依赖和传递依赖）。
  - BCNF判断：当以(S, J)作为候选键时，看依赖T→J，其中T在(S, J)这种候选键情况下并不是候选键，即T→J这个函数依赖的决定因素T不包含任意候选码，所以这个关系模式不符合BCNF的要求。
  - 转换为BCNF：为了使该关系模式满足BCNF，将依赖T→J修改为TS→J 。这样修改后，在新的依赖TS→J中，左边的决定因素TS包含了候选键之一S，满足了BCNF中每一个依赖的左边决定因素都包含候选键的条件，此时该关系模式就达到了BCNF。
- 原始表（不符合BCNF）：
  
  学生ID 课程教师
  S001 数学王老师
  S002 英语李老师
  
  假设依赖：
  
  教师 → 课程（每个教师只教一门课，但教师不是候选键）。
  问题：存在非平凡依赖（教师 → 课程），左侧不是候选键。
  
  BCNF规范化后：
  
  学生-教师表（候选键为 (学生ID, 教师)）：
  
  学生ID 教师
  S001 王老师
  S002 李老师
  
  教师-课程表（教师为候选键）：
  
  教师课程
  王老师数学
  李老师英语

员工ID	员工姓名	薪资/月
001	张三	基本工资:5000, 补贴:1000
002	李四	基本工资:6000, 补贴:800

员工ID	员工姓名	基本工资	补贴
001	张三	5000	1000
002	李四	6000	800

学号	课程号	课程名称	成绩	教师
S001	C001	数学	90	王老师
S001	C002	英语	85	李老师

学号	课程号	成绩
S001	C001	90
S001	C002	85

课程号	课程名称	教师
C001	数学	王老师
C002	英语	李老师

学号	姓名	系编号	系主任
S001	张三	D01	刘主任
S002	李四	D02	陈主任

学号	姓名	系编号
S001	张三	D01
S002	李四	D02

系编号	系主任
D01	刘主任
D02	陈主任

学生ID	课程	教师
S001	数学	王老师
S002	英语	李老师

学生ID	教师
S001	王老师
S002	李老师

教师	课程
王老师	数学
李老师	英语

真题示例：

给定关系模式R(U,F)，U={A,B,C,D}，F={AB→C,CD→B}。关系R（），且分别有（）。

A.只有1个候选关键字ACB B.只有1个候选关键字BCD

C.有2个候选关键字ACD和ABD D.有2个候选关键字ACB和BCD

A.0个非主属性和4个主属性 B.1个非主属性和3个主属性

C.2个非主属性和2个主属性 D.3个非主属性和1个主属性

候选关键字的求法

根据函数依赖集 F = {AB→C, CD→B}，我们可以按照以下步骤求候选关键字：

找出从未在右边出现过的属性：
- 在 F 中，右边出现的属性是 C 和 B
- 因此，A 和 D 从未在右边出现过，它们必然是候选键的一部分
以 A 和 D 为基础，尝试构建候选关键字：
- 尝试 AD：
  - AD⁺ = AD
  - 无法推导出 B 或 C（因为 AB→C 和 CD→B 都需要额外的属性）
  - 所以 AD 不是候选关键字
- 尝试 ABD：
  - ABD⁺ = ABD → C (AB→C) → ABCD
  - 可以推导出所有属性，因此 ABD 是候选关键字
- 尝试 ACD：
  - ACD⁺ = ACD → B (CD→B) → ABCD
  - 可以推导出所有属性，因此 ACD 是候选关键字
- 其他组合（如 AB、AC、AD、BC、BD、CD）：这些组合的闭包都无法推导出所有属性，因此不是候选关键字
结论：
- 候选关键字有 2 个：ABD 和 ACD

主属性和非主属性

主属性：出现在任何候选关键字中的属性
- ABD 包含 A、B、D
- ACD 包含 A、C、D
- 因此主属性是 A、B、C、D（所有属性都是主属性）
非主属性：不包含在任何候选关键字中的属性
- 由于所有属性都是主属性，非主属性数量为 0

设有关系模式R（E，N，M，L，Q），其函数依赖集为F={E→N,EM→Q,M→L}。则关系模式R达到了______；该关系模式_________。

A. 1NF B. 2NF C. 3NF D. BCNF

A. 无需进行分解，因为已经达到了3NF

B. 无需进行分解，因为已经达到了BCNF

C. 尽管不存在部分函数依赖，但还存在传递依赖，所以需要进行分解

D. 需要进行分解，因为存在冗余、修改操作的不一致性、插入和删除异常

第一步：识别所有属性

属性集 U = {E, N, M, L, Q}

第二步：分析函数依赖集 F

F = { E → N, EM → Q, M → L }

第三步：找出从未出现在右边的属性（候选键的必须属性）

在 F 中，右边出现的属性：N, Q, L
从未出现在右边的属性：E, M
因此，E 和 M 必须包含在候选键中

第四步：以 E 和 M 为基础构建候选键

尝试 EM：
- 计算 EM⁺：
  - 初始：EM
  - 应用 E→N：EMN
  - 应用 EM→Q：EMNQ
  - 应用 M→L：EMNQL
- EM⁺ = EMNQL = U（覆盖所有属性）
- 因此，EM 是候选键

范式分析（基于候选键 EM）

1. 主属性和非主属性

主属性：E, M（出现在候选键中）
非主属性：N, L, Q

2. 检查 2NF（消除部分函数依赖）

检查非主属性对候选键的部分依赖：
- E→N：N 依赖于候选键的一部分（E），属于部分函数依赖 → 违反 2NF
- M→L：L 依赖于候选键的一部分（M），属于部分函数依赖 → 违反 2NF
- EM→Q：Q 完全依赖于整个候选键 → 符合 2NF
结论：不满足 2NF

是否需要分解

存在部分函数依赖和传递依赖，会导致：
- 数据冗余（如 E→N 导致 N 重复存储）
- 更新异常（修改 E 对应的 N 需要修改多条记录）
- 插入异常（无法单独插入 M→L 的信息）
- 删除异常（删除 EM 会丢失 M→L 的信息）
需要进行分解，因为存在冗余、修改操作的不一致性、插入和删除异常

分解方法

将部分依赖单独分解：
- R1(E, N)：满足 E→N
- R2(M, L)：满足 M→L
- R3(E, M, Q)：满足 EM→Q
- 每个关系模式都满足 BCNF

一、关系代数

基本运算

笛卡尔积（×）

投影（π）

选择（σ）

自然连接（⋈）

真题示例：

二、函数依赖

基本概念

Armstrong公理系统

键与约束

三、范式（Normalization）

第一范式（1NF）

第二范式（2NF）

第三范式（3NF）

BC范式（BCNF）

真题示例：

相关文章：