《软件设计师》复习笔记(4.2)——关系代数、函数依赖、范式
目录
一、关系代数
基本运算
笛卡尔积(×)
投影(π)
选择(σ)
自然连接(⋈)
真题示例:
二、函数依赖
基本概念
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 李老师 教师-课程表(教师为候选键):
教师 课程 王老师 数学 李老师 英语
真题示例:
给定关系模式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):这些组合的闭包都无法推导出所有属性,因此不是候选关键字
- 尝试 AD:
-
结论:
- 候选关键字有 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
-