DB-05 关系数据理论

一、函数依赖

函数依赖是关系数据理论的核心概念。它描述了关系中属性之间的"决定"关系。

定义：设关系模式R(U,F)，U是属性全集。如果对于U的子集X和Y，对于R的任意一个实例，X的每个值都对应Y的唯一值，则称X函数决定Y，记作X→Y。

一个直观的理解：函数依赖类似于数学中的函数概念。如果我们知道一个人的学号X，就能唯一确定他的姓名Y，那么学号→姓名就是一个函数依赖。

函数依赖的分类

平凡依赖：如果Y是X的子集，那么X→Y是平凡的。例如(学号,姓名)→学号。平凡依赖总是成立的，没有实际意义。

非平凡依赖：如果Y不是X的子集，那么X→Y是非平凡的。例如学号→姓名。我们通常只关心非平凡的函数依赖。

完全函数依赖：如果X→Y，且X的任何真子集都不能决定Y，则称Y完全依赖于X。

部分函数依赖：如果X→Y，且X的某个真子集也能决定Y，则称Y部分依赖于X。

传递函数依赖：如果X→Y，Y→Z，且Y不能决定X（即Y→X不成立），则称Z传递依赖于X。

函数依赖的分类理解

假设有一个关系模式SCD(Sno, Cno, Grade, Age)，其中(Sno, Cno)是主码。

Grade完全依赖于(Sno, Cno)——只知道学号或只知道课程号都无法确定成绩，必须两者同时知道才能确定
Age部分依赖于(Sno, Cno)——因为Sno单独就能决定Age（学号决定年龄），所以Age部分依赖于主码
如果Sno→Dep（系别），Dep→Dean（系主任），则Dean传递依赖于Sno

二、范式及其判定

范式是衡量关系模式规范化程度的等级。从第一范式到第五范式，规范化程度越来越高。

2.1 第一范式（1NF）

要求：关系中的每个属性都是不可再分的原子值。

这是一张表成为"关系"的基本条件。违反的例子："电话号码"字段中存储了"手机：138xxxx，座机：0851-xxxx"这样的复合值。这样的设计会导致查询和更新变得非常困难。

2.2 第二范式（2NF）

要求：满足1NF，且每个非主属性都完全函数依赖于主码。

如果主码是联合主码（由多个属性构成），需要检查是否有非主属性只依赖于主码的一部分。如果有，就不满足2NF，需要进行模式分解。

例题：关系R(Sno, Cno, Grade, Age)，主码是(Sno, Cno)。其中Sno→Age（学号决定年龄），即Age部分依赖于主码。因此R不满足2NF。

分解方案：将R分解为R1(Sno, Cno, Grade)和R2(Sno, Age)。这样R1和R2都满足2NF。

2.3 第三范式（3NF）

要求：满足2NF，且每个非主属性都不传递依赖于主码。

如果有非主属性可以通过其他非主属性间接依赖于主码，就不满足3NF。

例题：关系R(Sno, Sname, Dept, Dean)，主码是Sno。假设Sno→Dept，Dept→Dean，那么Dean传递依赖于Sno。因此R不满足3NF。

分解方案：R1(Sno, Sname, Dept)和R2(Dept, Dean)。

2.4 BCNF

要求：满足1NF，且所有函数依赖X→Y中，X必须包含候选码。

BCNF比3NF更严格。一个关系满足3NF但不一定满足BCNF。

范式判定步骤

三、闭包算法与候选码求解

3.1 属性集闭包

属性集闭包X+是从X出发，通过函数依赖能够推导出的所有属性的集合。

算法：
result = X
while (result发生变化) {
    for (F中的每个函数依赖Y→Z) {
        if (Y ⊆ result) result = result ∪ Z
    }
}
return result

例题：R(U,F)，U={A,B,C,D,E}，F={AB→C, B→D, C→E, EC→B, AC→B}，求(AB)+

(AB)+
初始：AB
AB→C → ABC
B→D → ABCD
C→E → ABCDE
结果 = ABCDE = U，所以AB是一个候选码

3.2 候选码求解

要找到关系模式的所有候选码，可以按照以下步骤：

第一步：将属性分为四类：

L类：只在函数依赖左边出现的属性
R类：只在右边出现的属性
LR类：两边都出现的属性
N类：两边都不出现的属性

第二步：候选码必包含所有L类和N类属性。

第三步：从L+N类属性的闭包开始，如果闭包不等于U，则逐步加入LR类属性进行扩展，直到闭包等于U。

例题：R(U,F)，U={A,B,C,D,E}，F={AB→C, B→D, C→E, EC→B, AC→B}

L类：A
R类：D
LR类：B, C, E
(A)+ = A ≠ U
(AB)+ = ABCDE = U ✓ (AB是候选码)
(AC)+ = ACEBD = U ✓ (AC也是候选码)
候选码：AB和AC
主属性：A, B, C
非主属性：D, E
因为B→D，D部分依赖于码AB，所以不满足2NF，最高为1NF

四、最小函数依赖集

最小函数依赖集Fm是一个与F等价但"更精简"的函数依赖集。它的三个条件：

单属性化：右部只有一个属性
无冗余化：没有多余的函数依赖
左边既约化：左边的属性不能化简

求解步骤：

例：F = {A→BC, E→C, D→AEF, ABF→BD}

① 右部分解：
   F = {A→B, A→C, E→C, D→A, D→E, D→F, ABF→B, ABF→D}

② 去掉冗余：
   ABF→B是平凡的（B⊆ABF），去掉
   ABF→D，检查(AF)+ = {ABFD}，所以AF→D，化简为AF→D

③ 结果：
   Fm = {A→B, A→C, E→C, D→A, D→E, D→F, AF→D}