• ER模型转换的关系是否就是最优的关系？不一定。

  关系模型潜在的问题：

  • 添加异常

• 修改异常

  • 删除异常
  • 数据冗余

冗余

• 当数据的某些部分能由其他部分推导出来，就意味着存在冗余
• 冗余的存在是因为存在完整性约束

如何解决冗余问题

• 由于存在约束，特别是函数依赖，导致冗余的产生。
• 如果存在冗余，就需要对关系模式进行优化。
  • 主要优化技术: 模式分解 (比如， ABCD 用 AB和BCD, 或者 ACD 和 ABD替代)。
• 如何正确地使用模式分解:
  • 是否有必要分解一个模式?
  • 分解以后会不会出现什么问题?

如何评价一个关系是好的还是坏的？

• 坏关系到好关系

  • 对关系模式进行优化
  • 主要优化技术：模式分解(比如ABCD用AB和BCD，或者ACD和ABD代替)

• 函数依赖概念
  • 函数依赖可形式化表示为X->Y, 其中X and Y是属性集
  • 例如：rating->hrly_wage, AB->C
  • 如果对于关系实例r中的任意一对元组t1和t2，有t1.X = t2.X逻辑蕴含t1.Y = t2.Y，那么函数依赖X->Y在关系r中成立
  • 即关系r中给定两个元组，如果X属性值相等则Y的值也必须相等（X和Y是属性集）
  • 如果对关系R中的每个实例r，都满足函数依赖，则该函数依赖在关系R上成立。
    • 函数依赖必须由应用的语义所决定。
    • 对于给定关系R的某实例r，我们能判断它是否违反了某个函数依赖。
    • 但是不能仅仅根据一个满足函数依赖的实例来断定该函数依赖在关系模式R上成立。
• 函数依赖起到检测冗余是否存在的作用

完全函数依赖

在一张表中，若 $X\to Y$，且对于 X 的任何一个真子集（假如属性组 X 包含超过一个属性的话），$X^{\prime }\to Y$ 不成立，那么我们称 Y 对于 X 完全函数依赖，记作 $X\stackrel{F}{\to }Y$

例如：

• 学号$\stackrel{F}{\to }$姓名
• （学号，课名） $\stackrel{F}{\to }$分数 （注：因为同一个的学号对应的分数不确定，同一个课名对应的分数也不确定）

部分函数依赖

假如 Y 函数依赖于 X，但同时 Y 并不完全函数依赖于 X，那么我们就称 Y 部分函数依赖于 X，记作 $X\stackrel{P}{\to }Y$

例如：

• （学号，课名） $\stackrel{P}{\to }$姓名

主属性

包含在任意一个码中的属性称为主属性。

非主属性

不包含在任何一个码中的属性称为非主属性。

范式

如果一个关系满足一种范式（BCNF，3NF等），就能判断该关系模式是否避免了某类问题。这样就能知道该关系是否需要分解。

• 任何符合BCNF的关系也符合 2NF

第一范式（1NF）

• 每个属性都是原子属性
• 本质上所有关系都满足第一范式

第二范式（2NF）

• 任何满足第二范式的关系满足第一范式
• 所有非主属性必须依赖于整个主码而不能依赖于主码的部分属性
• 例如：关系模式 Inventory(part, warehouse, quantity,warehouse_address).
  假设 {part, warehouse}是主码. warehsouse_address 单独依赖于 warehouse -则违反了第二范式。 解决方法: 分解关系模式

第三范式(3NF)

• 任何符合BCNF的关系也符合 3NF
• 符合3NF要求的数据库设计，基本上解决了数据冗余过大，插入异常，修改异常，删除异常的问题。
• 有一些情况
  • BCNF 不能保持函数依赖,
  • 在更新上有效的检查函数依赖是否违背是非常重要的。
• 解决方法: 定义一个弱的关系, 叫做第三范式 (3NF)

  • 允许存在一些冗余

  • 函数依赖是否保持可以在单独的关系上检查，而不需要进行连接计算.

  • 3NF一般是保持无损连接分解和保持函数依赖

• R符合BCNF, 那么R符合3NF
• 如果 R 符合 3NF, 可能会存在一定的冗余，它是分解和性能的一种折中
• 将R分解为满足3NF的关系集合，是保持了无损连接分解和保持函数依赖的

3NF分解

• 显然, 分解为BCNF的无损连接分解的算法能够用来获取无损连接分解的3NF.
• 为了保持函数依赖, 一个思想是:
  • 如果 X → Y 不保持, 增加关系XY.
  • 问题是XY可能会违背 3NF!
• 细化: 不考虑 FDs F, 而是使用F的最小的函数依赖集.

3NF分解算法的其它例子

Boyce-Codd 范式(BCNF)

• 对于 R 有函数依赖集 FDs F ，如果R符合BCNF 当且仅当每一个非平凡的 FD

  • X → A in F , X 是R的超键 (i.e., X → R in F+).

  • 对于 FD X → A 是平凡的，当且仅当 A ? X.

• 也就是说, R 符合BCNF 当且仅当非平凡的FDs 箭头左侧是键.
  BCNF:

• R中没有数据能够使用FDs预测.

• Why:

  • X是超键, 不会有两个元组的X值相同

• 如果R只有两个属性, 那么它符合BCNF

• 如果F只包括R中的属性:

  • R 符合BCNF 当且仅当每一个F中的函数依赖 X → Y (not F+!), X 是 R的超键, i.e., X → R is in F+ (not F!).

BCNF的检测

• 列出所有的非平凡函数依赖
• 确认每一个函数依赖箭头左边的属性集是R的超键。
• 注意：我们需要首先找出R的超键!

例：Courses(course_num, dept_name, course_name, classroom, enrollment, student_name, address) 符合BCNF?
FDs 包括:

• course_num, dept_name → course_name

• course_num, dept_name → classroom

• course_num, dept_name → enrollment

那么(course_num, dept_name)+?

• {course_num, dept_name, course_name, classroom, enrollm ent}
  Therefore, the key is {course_num, dept_name, student_name}

不符合BCNF

BCNF范式分解

• 当一个关系不符合BCNF: 那么分解它.
• 假定关系R 包含属性A1 … An. R的分解会分解为两个或者多个关系:
  • 每个新的关系的属性为R属性的子集 (不会有属性不属于 R), 并且R 中的每一个属性至少会在一个新的关系中.
• 考虑关系R 和函数依赖集 FDs F. 如果F中的函数依赖 X → A 违背 BCNF, 那么: 分解R 为R – A 和XA.
• 重复这个思想，我们会得到一个符合BCNF的关系集合.
• 保持无损连接分解。

将关系模式R<U,F>分解为一个BCNF的基本步骤

快速求候选码的方法

首先对于给定的R(U)和函数依赖集F,可以将它的属性划分为4类:

• L类,仅出现在F的函数依赖左部的属性。
• R类,仅出现在F的函数依赖右部的属性。
• N类,在F的函数依赖左部和右部均未出现的属性。
• LR类,在F的函数依赖左部和右部两部均出现的属性。

根据以下定理和推论来求解候选码。

• 定理1:对于给定的关系模式R及其函数依赖集F,若X(X∈R)是L类属性,则X必为R的任一候选码的成员。
• 推论1:对于给定的关系模式R及其函数依赖集F,若X(X∈R)是L类属性,且X+包含了R的全部属性,则X必为R的唯一候选码。
• 定理2:对于给定的关系模式R及其函数依赖集F,若X(X∈R)是R类属性,则X不在任何候选码中。
• 定理3:设有关系模式R及其函数依赖集F,如果X是R的N类属性,则X必包含在R的任一候选码中。
• 推论2:对于给定的关系模式R及其函数依赖集F,如果X是R的N类和L类组成的属性集,且X+包含了R的有属性,则X是R的唯一候选码。

例：

如果把例题中关系模式R(U)中的属性E去掉,那么再求R的候选码的话可以根据推论1得出BD为R的唯一候选码。

快速求解方法适用于判断有属性是属于L类、N类或其中一种的情况下求解。如果有L类和N类的属性,则求解候选码速度非常快。

简而言之：

L、R、N、LR类。根据定理，L、N类必为侯选码之一，如果L+包含全部R，则L为唯一侯选。R类不在任何侯选码中。

L+N类且（L+N）+包含所有R，则L+N为唯一侯选。（适于有L、N类至少一种的情况。）

BCNF 和 依赖保持

• 分解得到的关系，符合BCNF，但可能不满足保持函数依赖.
• 例子: 关系CSZ (city, street_name, zip_code) 函数依赖 FDs: CS → Z, Z → C
  (city, street_name) → zip_code
  zip_code → city
• 要保持CS → Z，则不能分解, 但是CSZ 不符合BCNF.

函数依赖理论：Armstrong公理

从一个给定的函数依赖集推导出它所逻辑蕴含的所有函数依赖

4.1 函数依赖和键

• 给定R(A,B,C)

  • A->ABC意味着A是一个键（码）

• 通常,

  • X → R 意味着 X 是一个超键.

• 键的约束

  • ssn → did

4.2 函数依赖集的闭包F+

• 函数依赖集的闭包？由F逻辑蕴含的所有函数依赖的集合
• 计算函数依赖集的闭包：

F+例子

F = {A → B, B → C, C D → E }

• Step 1: F中的每一个函数依赖, 使用自反律

  • 得到:CD → C; CD → D

  • 加到F上: F = {A → B, B → C, C D → E; CD → C; CD → D }

• Step 2: F中的每一个函数依赖, 使用增补率
  • A → B 得到: A → AB; AB → B; AC → BC; AD→ BD; ABC →BC; ABD → BD; ACD →BCD
  • B → C 得到: AB → AC; BC → C; BD → CD; ABC → AC; ABD → ACD, etc.
• Step 3: 使用传递率
• 重复1~3步骤…

可以看出计算F+代价太高.

4.3 求最小依赖集

关系模式R(U,F)中，R=ABCDEG F={BE→G,BD→G,CD→A,CE→G,CDE→AB,BC→A,B→D}

1. 首先把右边的属性都变成单个属性

   函数依赖集F={BE→G,BD→G,CD→A,CE→G,CDE→A,CDE→B,BC→A,B→D}

2. 对于函数依赖F中的每个函数X->A,设G=F-{X->A},如果A属于关于函数依赖集G的闭包，将X->A从F中删除，否则保留，然后得出新的F。

   BE+=BEDG，包含G，删除。

   BD+=BD,不包含G，保留。

   CD+=CD，不包含A，保留。

   CE+=CE，不包含G，保留。

   CDE+=CDEAGBA，包含A，删除。

   CDE+=CDEAG，不包含B，保留。

   BC+=BCDGA,包含A，删除。

   B+=B，不包含D，保留。

   得到新的F={BD→G,CD→A,CE→G,CDE→B,B→D}

3. 对于F中每一个左端包含多个属性的X->A（即去掉各依赖左部多余的属性。一个一个地检查函数依赖左部非单个属性的依赖），选择X的每个子集Z,如果A属于Z的闭包,则用Z->A代替X->A。

   BD→G：B+=BDG，包含G，去掉；D+=D，不包含G，保留。

   CD→A：C+=C，不包含A，保留；D+=D，不包含A，保留。

   CE→G：C+=C，不包含G，保留；E+=E，不包含G，保留。

   CDE→B：C+=C，不包含B，保留；D+=DG，不包含B，保留；E+=E，不包含B，保留。

最后得出关系模式R(U,F)的最小依赖集Fm={D→G,CD→A,CE→G,CDE→B,B→D}

4.3 属性集闭包

• (函数依赖集闭包的大小是（属性的）指数级的)
• 很多时候, 我们仅仅是想判断一个 FD X →Y 是否在F的闭包中. 一个有效的方式是:
  • 计算属性X的闭包 (记为X+) :
    • X的闭包 就是由X在F上蕴含的所有属性的集合。
    • 计算属性的闭包仅仅需要一个线性的时间算法就够了.
  • F = {A → B, B → C, C D → E } A → E成立吗?

属性集闭包的作用

1. 测试超键
   • – 判断X是否是一个超键？只需要计算 X+, 检查 X+ 是否包括R的所有属性.
2. 检测函数依赖
   • 判断X → Y 是否成立 (或者说, 是否在F+中), 只需要判断Y ? X+.
   • 因此, 我们计算X+, 然后检测这个属性集闭包是否包括 Y.
   • 简单有用的方法
3. 计算F的函数依赖集闭包

分解的问题

• 模式分解可能存在三种问题:

  1. 一些查询可能会代价变高.
     e.g., Attishoo 挣了多少钱? (earn = W*H)
  2. 分解后，根据分解的实例, 我们可能不能重新构建分解前的实例!
  3. 检查某些依赖需要考虑分解后的多个关系.

• 折中: 考虑这些问题 vs. 冗余.

分解

• 将分解符合3NF或更高的范式是一种很好的保证方法.
• 所有分解应该是无损的! (Avoids Problem (2))

无损连接分解

• 将R 分解为 R1 和R2 ，如果是无损连接分解，那么应该满足：

例子（不是无损的）

例子（无损的）

保持函数依赖

• 保持函数依赖的分解（直观上）：
  • R 分解为X, Y 和Z, 函数依赖集FDs在X，Y，Z上成立，那么FDs也会在R上成立。

分解后的函数依赖?

• 函数依赖集的投影: R 分解为 X, … F 在X上的投影 (denoted FX ) 是如下的 FDs U → V in F+ (closure of F ) ，U, V 是X中的属性.

保持函数依赖的分解

• 将R分解为X和Y是保持函数依赖的，当且仅当$(F_X\cup F_Y{)}^{+}=F^{+}$
• 注意是$F^{+}$，而不是$F$
• 保持函数依赖并不能保证保持无损连接分解
• 反之亦然

判断两个函数依赖集是否等价

• 如果 F1+ = F2+, 那么F1和F2等价.
• 例如, F1={A →B, A →C} 和 F2={A → BC}等价

例子

• F={ A → BC, B →C }. 判断 C →AB 是否在 F+?
• Answer: 不在.
  Reason 1) C+=C, 不包括 AB.
  Reason 2) 反例，不存在 C → AB.

• 将一个关系分解为符合3NF的关系集合：
  • 分解是无损的
  • 分解是保持函数依赖的
• 将一个关系分解为符合BCNF的关系集合：
  • 分解是无损的
  • 可能不保持函数依赖

设计目标

• BCNF
• 无损连接
• 保持函数依赖

如果不能得到这些

• 函数依赖的保持
• 使用3NF产生冗余

• R(A,B,F), F = {AC → E, B → F}.
  • Candidate key? AB
  • BCNF? No, because of B → F (B is not a superkey).
  • 3NF? No, because of B → F (F is not part of a candidate key).

• R(D, C, H, G), F = {A → I, I → A}
  • Candidate key? DCHG
  • BCNF? Yes
  • 3NF? Yes

• R(A,B,C,D,E,F)，F={A->C,C->A,B->AC,D->AC}
  • 找出R的键
  • 是否符合3NF，如果是，说明原因，如果否，分解。

• 解法一

• 解法二