第6章关系数据理论 6.1关系模式的设计的问题 6.2 数据依赖的推理规则 6.3规范化 6.4模式分解.

第6章关系数据理论 6.1关系模式的设计的问题 6.2 数据依赖的推理规则 6.3规范化 6.4模式分解

6.1 关系模式的设计的问题 1. 当用户给定了一组数据后，应该构成几个关系？每个关系应由哪些属性组成？这个问题是一个DB设计问题，确切地讲是DB的逻辑设计问题。 2. 由于关系模型有严格的数学理论基础，并且可以向其他模型进行转换，故以关系模型为背景进行这个问题的讨论，也就形成了DB逻辑设计的一个有力工具——关系数据库的规范化理论。 3. 对于一个现实问题，在不同的时刻关系模式的关系（值）也会有变化，但现实世界中许多已知的事实又限定了关系模式的所有可能的关系必须满足一个的完整性约束条件， 6.1 关系模式的设计的问题

这些约束或者通过对属性值的限定，或者通过属性间的属性值的相互关系（称为数据依赖，是语意范畴）反映出来，这就是数据模式设计的关键。
6.1 关系模式的设计的问题 4. 数据依赖前面讲过： R （ U, D, DOM, F）关系属性域属性→域的影射　数据依赖本章讨论R（U、F）

函数依赖（Functional Dependency）FD 多值依赖（Multivalued Dependency）MD
数据依赖：函数依赖（Functional Dependency）FD 多值依赖（Multivalued Dependency）MD 联接依赖（Join Denpendency）JD FD是重点，顾名思义，同数学中的函数，如Y=f(x) 6.1 关系模式的设计的问题 6. 对于任一个不考虑FD的关系模式会有什么不当之处？

R（SNO，CNO，GRADE，SD，MN）
例6-1-1： R（SNO，CNO，GRADE，SD，MN） 6.1 在该关系中：关系模式的设计的问题 U＝｛SNO，CNO ，GRADE ，SD，MN｝已知函数依赖： F＝｛ SNO→SD，SD→MN，（SNO，CNO）→GRADE ｝

如有一系刚成立，尚无学生则系名，系主任无法加入则无法加入如有一门新课，尚无人选 6.1 关系模式的设计的问题如有一学生尚无选择课则无法加入插入异常:该插入的信息无法插入。删除异常：不该删除的信息被删除。插入异常 6

如只有一学生选过某课，而现在毕业（不选）则该课被删除，不存在 6.1 关系模式的设计的问题如某系的学生全毕业则该系不存在插入异常:该插入的信息无法插入。删除异常：不该删除的信息被删除。删除异常 7

如一个系换了系主任，则需对所有该系的学生信息进行修改，若一些元组的信息修改，而另一些元组的相同信息没有修改，导致数据的不一致性……
R（SNO，CNO，GRADE，SD，MN）如一个系换了系主任，则需对所有该系的学生信息进行修改，若一些元组的信息修改，而另一些元组的相同信息没有修改，导致数据的不一致性…… 6.1 关系模式的设计的问题修改异常系名，系主任，（SD，MN）的存储次数同该系的学生的选课人次有关。即：浪费存储，又要付出代价来维护。修改异常：同一信息被存储多次，会发生修改了一个元组的信息，而另一个元组的相同信息没有被修改，导致数据的不一致性。数据冗余：同一信息被存储多次。数据冗余 8

如果R（SNO，CNO，GRADE，SD，MN）分解为:
6.1 R2（SNO，SD）关系模式的设计的问题 R3（SD，MN）则会减少上述的问题，但这也是通过经验分解，是否有理论来支持这一分解呢？本节结束

6.2 数据依赖的推理规则引例： 2013年3月全国计算机三级数据库技术笔试试题
设有关系模式 R ( S,T,C,D,G )，F＝{ (S,C) →T，C→D，(S，C)→G，T→C } 关系模式 R的候选键是。 A. SC B. ST C. SC 和T D. SC 和 ST 6.2 数据依赖的推理规则

英文单个首部大写字母“A、B、C、D、E、…”代表单个属性。英文单个尾部大写字母，“U、V、W、X、Y、Z”代表属性集。
本章的一些符号约定：英文单个首部大写字母“A、B、C、D、E、…”代表单个属性。英文单个尾部大写字母，“U、V、W、X、Y、Z”代表属性集。大写字母R代表关系模式，小字字母r代表其关系（值），也用属性名组合的方式表示关系模式。如属性有A、B、C，则可用ABC表示该关系模式。属性集｛A1，A2，…An｝写为A1，…An 属性集X∪Y 写为XY 属性集X∪A写为XA 6.2 数据依赖的推理规则

6.2.1 函数依赖 1.函数依赖（FD ）的定义：设R（U）是属性集U上的关系模式，X、Y是U的子集，若对R（U）的任意一个可能的关系r，r中不可能存在两个元组在X上属性值相等，而在Y上属性值不等（或对X的每一个具体值，Y都有唯一一个具体值与之相对应）。则X函数决定Y，或Y函数依赖X，记作X→Y 6.2 数据依赖的推理规则注意是语义范畴：关系r的任意两个元组t和s,当t [X]=s [X]时，t [Y]=s [Y] 例：SNO→SEX，SNAME→SEX （当有同名时，则SNAME→SEX）

候选码：设K为R（U，F）中的属性或属性集，若K F U，则K为R的候选码。
2. 完全函数依赖的定义：在R（U）中，如果X→Y，并对X的任一真子集X`，都有X`→Y，则Y对X是完全函数依赖,（Full Functional Dependency ）记作X F Y。 6.2 候选码：设K为R（U，F）中的属性或属性集，若K F U，则K为R的候选码。数据依赖的推理规则

对于满足一组函数依赖F的关系模式R(U,F)，对于任一关系r，若函数依赖X→Y都成立，则称F逻辑蕴含X→Y，记作：F |= X→Y。
6.2 数据依赖的推理规则

函数依赖的推理规则最早出现在1974年W.W.Armstrong 的论文里，这些规则常被称作"Armstrong 公理"
A1 自反律： YXU 则X→Y 6.2 A2 增广律： X→Y ，Z  U，则 XZ→YZ 数据依赖的推理规则 A3 传递律： X→Y ，Y→Z ，则 X→Z 合并规则： X→Y ，X→Z ，则X→YZ 伪传递规则： X→Y，W Y→Z ，则 WX→Z 分解规则： X→Y， ZY ，则 X→Z

6.2.3 F的闭包 1. F闭包的定义被F逻辑蕴含的FD的全体构成的集合称为FD集F的闭包， F＋记作：
数据依赖的推理规则 F＋ ={X→Y| F |=X→Y} 例6-2-1：R(ABC) F={ A→B，B→C} 求F＋。

AB→AC AB→BC AB→C AB→ABC
解： F={ A→B，B→C} A→ A→A A→B A→C A→AB A→AC A→BC A→ABC B→ B→B B→C B→BC C→ C→C AB→ AB→A AB→B AB→AB AB→AC　 AB→BC　 AB→C 　AB→ABC 6.2 数据依赖的推理规则 AC→　 AC→AC　 AC→A　 AC→C AC→B　　AB→BC　 AC→AB　 AC→ABC BC→　 BC→BC　 BC→B　 BC→C ABC→　 ABC→A　 ABC→B　 ABC→C　 ABC→AB　ABC→BC　ABC→AC ABC→ABC →　　共43个FD

上例中，AB,AC,ABC是超键，A是候选键。
2. 求F＋的意义设关系模式R(U,F)，X是U的子集，如果X→U在F＋。那么称X是R的一个超键，如果X的任一真子集 X’ →U都不在F＋中，那么称X是R的一个候选键。上例中，AB,AC,ABC是超键，A是候选键。在实际应用中，从F求F＋是一个NP完全问题（指数级问题），下面引进属性闭包的概念，将使该问题转化为多项式级时间（与全部FD的数目相关）问题。 6.2 数据依赖的推理规则

6.2.4 属性集的闭包 1. 属性集的闭包定义设F是属性组U的FDS，X是U的子集，那么（对F）属性集X的闭包，用XF＋表示，它是一个从F集使用FD的推理规则推出的所有满足 X→A的属性A的集合， 6.2 数据依赖的推理规则 XF＋＝｛属性A｜X→A在F＋中｝

2. 求属性集X相对于FD集F的闭包的算法。与全部 (与FD的个数成正比，是一个多项式级时间复杂度）输入：属性集U，U上FD集F，X U
输出：X相对于FD集F的闭包X＋。方法： result:=X repeat for F中的每一个FD Y →Z do if Y  result then result:= result U Z； until(result没有改变)； result即所求的X＋。 6.2 数据依赖的推理规则

例6-2-2：R（ABC） F＝｛A→B，B→C｝，求所有属性子集的属性闭包。
A＋B ＋ C＋（AB)＋（BC)＋（AC)＋（ABC)＋ A＋　 ∵A→B ∵B→C ∴A＋＝｛ABC｝ B＋　 ∵B→C ∴B＋＝｛BC｝ ∴ C＋＝｛C｝ C+ 6.2 (AB)＋ ∵B→C ∴(AB)＋　＝｛ABC｝数据依赖的推理规则 (AC)＋ ∵A→B 　 ∴ (AC)＋　＝｛ABC｝ (BC)＋ ∴ (BC)＋　＝｛BC｝ (ABC)＋　 ∴ (ABC)＋　＝｛ABC｝得到一个引理： X→Y能用FD推理规则推出的充分必要条件是YX＋。（任意X→Y，Y必会在X＋）

从属性闭包求F的闭包容易。 3.求属性闭包的意义
X的闭包是所有属性U，则X是超键；如果X的任一真子集 X’ 的闭包不是所有属性U，则X是候选键。 6.2 上例6-2-1：R（ABC）　F＝｛A→B，B→C｝，通过求所有属性子集的属性闭包，判断出候选键。在实际应用中对于属性的子集有2n-1个（最多）需要判断。数据依赖的推理规则函数依赖等价，最小函数依赖

目前有以下六种求候选键的常用方法：求候选键基本算法快速求候选键法多属性依赖集候选键求解法依次递推法一般求候选键的算法图论判定方法
6.2 数据依赖的推理规则函数依赖等价，最小函数依赖

6.2.5 求候选键 1. 快速求候选键法在关系模式R(U,F)中，可以将属性分为4类： L类：仅出现在F的函数依赖左部的属性
求候选键 1. 快速求候选键法在关系模式R(U,F)中，可以将属性分为4类： L类：仅出现在F的函数依赖左部的属性 R类：仅出现在F的函数依赖右部的属性 LR类：在F的函数依赖左右两边都出现的属性 N类：在F的函数依赖左右两边都未出现的属性 6.2 数据依赖的推理规则例6-2-2：设关系模式R（A，B，C，D，E，G），其函数依赖集F={DB，B  D，AD  B，AC  D，D  E} L类：A，C R类：E LR类：B，D N类：G

对R（U，F），若X（X ∈ U）是L类属性，则X必为R的任意候选键的成员。推论1：
定理1：对R（U，F），若X（X ∈ U）是L类属性，则X必为R的任意候选键的成员。推论1：对R（U，F），若X（X ∈ U）是L类属性，且X+包含了R的全部属性U，则X为R的唯一候选键。 6.2 例6-2-3：设R（A，B，C，D），F={D  B，B  D，AD  B，ACD},求R的所有候选键。解：L类：A，C R类： LR类：B, D N类： (AC)+={ACBD}，由推论1，AC是R的唯一候选键。数据依赖的推理规则

对R（U，F），若X（X ∈ U）是R类属性，则X不在任意候选键中。
定理2：对R（U，F），若X（X ∈ U）是R类属性，则X不在任意候选键中。定理3：对R（U，F），若X（X ∈ U）是N类属性，则X必包含在R的任意候选键中。推论2：对R（U，F），若X（X ∈ U）是L类和N类组成的属性集，且X+包含了R的全部属性U，则X为R的唯一候选键。 6.2 数据依赖的推理规则

例6-2-4：设R（A，B，C，D，E，P），F={A  D，E  D，D  B，BC  D，DC  A}，求R的候选键。
解：L类：C，E； R类： LR类：A , B, D N类：P 由定理1，CE为任意候选键成员由定理3，P为任意候选键成员（CEP）+=ABCDEP，由推论2，CEP为R的唯一候选键。 6.2 数据依赖的推理规则

2. 多属性依赖集候选键求解法具体步骤： (1)把R的所有属性分为L、R、N和LR四类，并令X代表L、N类，Y 代表LR类。
(2)求X+，如果X +包含了R的全部属性，则X为R的唯一候选码，转(5)；否则，转(3)。 (3)在Y中取一个属性A，求（XA) + ，如果它包含了R的全部属性，则转⑷；否则，调换另一个属性反复进行这一过程，直到试完所有Y中的属性。 (4)如果已经找到所有的候选码，则转(5)；否则在Y中依次去两个、三个……求它们的属性闭包，直到其闭包包含R的所有属性。 (5)停止，输出结果。 6.2 数据依赖的推理规则

简而言之：取一个X属性（X为L、N类）求闭包，如果包含R全部属性则为候选键，否则取一个LR类的Y属性A，求XA闭包，未包含R全属性则调换A，包含R全属性且找到所有候选键则结束，否则依次取2、3个......。 6.2 数据依赖的推理规则

例6-2-5： R（ABCD）F={AB→C，C→D，D→A} 求：R的候选键解： L类：B LR类：A,C,D R类： N类：
B+={B} 不是候选键。 (AB)+={ABCD} (BC)+={BCDA} (BD)+={BDAC} 候选键：AB、BC、BD 6.2 数据依赖的推理规则

练习1：已知：R（ABCDE） F={AB→C, C→D，D→BE} 求：码。 L类：A LR类：B,C,D R类：E N类：解：
A+={A} (AB) +={ABCDE} (AC) +={ACDBE} (AD) +={ADBEC} 码：AB、AC、 AD。 6.2 数据依赖的推理规则

练习2：已知：R（ABCDE） F={AB→C，DE→C，B→D} 求：R的码。 L类：A,B,E LR类：D R类：C N类：解：
(ABE)+={ABCDE} 根据推论A 码：ABE 6.2 数据依赖的推理规则

已知：R（ABCD）F={A→BC，B→D} 求：候选键解： L类：A LR类：B R类：C,D N类： A+={ABCD}
练习3：已知：R（ABCD）F={A→BC，B→D} 求：候选键解： L类：A LR类：B R类：C,D N类： A+={ABCD} 由推论1， A是R的唯一候选键。 6.2 数据依赖的推理规则

设有关系模式 R ( S,T,C,D,G )，F＝{ (S,C) →T，C→D，(S，C)→G，T→C } 关系模式 R的候选码是。
2013年3月全国计算机三级数据库技术笔试试题设有关系模式 R ( S,T,C,D,G )，F＝{ (S,C) →T，C→D，(S，C)→G，T→C } 关系模式 R的候选码是。 A. SC B. ST C. SC 和T D. SC 和 ST 6.2 数据依赖的推理规则

小结 1. 函数依赖 2. Armstrong推理公理 3. F+ 4. 属性X+ 5. 求候选键 6.2 数据依赖的推理规则

作业： 1. 任一关系模式可能会出现哪些问题？ 2. 已知：R（ABCDEG） F={D→G, C→A，CD→E，A→B}
求：D+ 、C +、 A + 、(CD) + 、(AD) +、 (AC) + 、 (ACD )+。 3. 已知：R（ABCDE） F={AB→C，DE→C，B→D} 求：R的候选键 4. 已知：R（ABCD）F={A→BC，B→D} 求：候选键 5. 已知：R（ABCDE）F={AB→C, C→D,D→B，D→E} 6.2 数据依赖的推理规则本节结束

6.3 规范化 1971年，E．F．Codd提出该理论，即使数据库设计走向完备的规范化理论。一般按属性间的依赖情况来区分。
6.3 规范化 1971年，E．F．Codd提出该理论，即使数据库设计走向完备的规范化理论。一般按属性间的依赖情况来区分。分为：1NF，2NF，3NF BCNF… 6.3 规范化

函数依赖（FD ）回顾 1. 定义：设R（U）是属性集U上的关系模式，X、Y是U的子集，若对R（U）的任意一个可能的关系r，r中不可能存在两个元组在X上属性值相等，而在Y上属性值不等（或对X的每一个具体值，Y都有唯一一个具体值与之相对应）。则X函数决定Y，或Y函数依赖X，记作X→Y 6.3 2. 语义范畴：关系r的任意两个元组t和s,当t [X]=s [X]时，t [Y]=s [Y] 规范化例：SNO→SEX，SNAME→SEX （当有同名时，则SNAME→SEX）

X→Y，但Y  X，则称X→Y是非平凡的FD。
3. 一些术语和记号 X→Y，但Y  X，则称X→Y是非平凡的FD。 X→Y，YX，则 X→Y称平凡的FD。 X→Y中，X为决定因素。 X→Y，Y→X，则XY。 6.3 规范化若Y不FD于X，则X Y。

若X→Y，但Y不完全FD于X，则称Y对X部分函数依赖（Partial Functional Dependency ），记作：X P Y
4. 定义：在R（U）中，如果X→Y，并对X的任一真子集X`，都有X`→Y，则Y对X是完全函数依赖,（Full Functional Dependency ）记作X F Y。若X→Y，但Y不完全FD于X，则称Y对X部分函数依赖（Partial Functional Dependency ），记作：X P Y 6.3 规范化

例6-3-1： R（SNO，CNO，GRADE，SD，MN）已知：F＝｛SNO→SD，SD→MN，（SNO，CNO）→GRADE｝ SNO GRADE 因为 CNO GRADE 6.3 所以（SNO，CNO）F GRADE 规范化（SNO，CNO）→SD，因为SNO→SD 所以（SNO，CNO） P SD

5. 定义：在R（U）中，如果X→Y ，（YX），Y→Z则称Z传递函数依赖于X（Transitive Functional Dependency ）。记作：X T Z 例6-3-2： R（SNO，CNO，GRADE，SD，MN）已知：F＝｛SNO→SD，SD→MN，（SNO，CNO）→GRADE｝ 6.3 规范化因为：SNO→SD, SD→MN 则：SNO T MN

伪传递规则： X→Y，W Y→Z ，则 WX→Z
6. FD的推理规则回顾： A1 自反律： YXU 则X→Y A2 增广律： X→Y ，Z  U，则 XZ→YZ A3 传递律： X→Y ，Y→Z ，则 X→Z 合并规则： X→Y ，X→Z ，则X→YZ 伪传递规则： X→Y，W Y→Z ，则 WX→Z 6.3 分解规则： X→Y， ZY ，则 X→Z 规范化

6.3.2 范式 1. 规范化：以更单纯，结构更规则的关系逐步取代原有关系的过程（其过程是一个模式分解的过程）。 2. 范式：
在规范化过程中所产生的满足不同的约束条件的关系的结构，称为第N范式（Normal Form）。范式为： 1NF，2NF，3NF，BCNF，4NF， NF（PJNF），DKNF, 6NF。 6.3 规范化

范式间关系式：6NF  DKNF  5NF  4NF  BCNF  3NF  2NF  1NF
1971至1972年,E.F.Codd于提出1NF、2NF、3NF 1974年, Boyce 和E.F.Codd提出BCNF(3NF的修正) 1976年，Fagin提出4NF，后来提出5NF（PJNF）目前还有 DKNF、 6NF。范式间关系式：6NF  DKNF  5NF  4NF  BCNF  3NF  2NF  1NF 6.3 INF 2NF 3NF BCNF … 规范化

6.3.3 1NF 定义：如果关系模式R的每一个属性值都是不可分的原子值，那么称R是第1范式，记作R∈1NF。例：出现了嵌套 6.3
学号课程号成绩 S1 C1 30 60 90 C2 28 52 80 S2 25 50 75 学号课程号平时成绩期末成绩总评 S1 C1 30 60 90 C2 28 52 80 S2 25 50 75 6.3 规范化出现了嵌套

例：出现了重复组 1NF是关系模式应具备的最起码的条件。学号课程号成绩 S1 C1 80 C2 90 S2 C3 70 60 6.3
规范化出现了重复组 1NF是关系模式应具备的最起码的条件。

6.3.4 2NF 定义：若R∈1NF，且每一个非主属性完全函数依赖于码，则R∈2NF。
例6-1-1： S（SNO，CNO，GRADE，SD，MN） 6.3 规范化码：（SNO，CNO）非主属性：GRADE，SD，MN

该关系模式不是2NF，会产生相应的四个问题。
（SNO，CNO） F GRADE （SNO，CNO） P SD　（SNO，CNO） P/T MN 该关系模式不是2NF，会产生相应的四个问题。取消部分函数依赖。 S1（SNO，CNO，GARDE）∈2NF 6.3 规范化 S2（SNO，SD，MN）∈2NF

6.3.5 3NF 1. 定义： R∈2NF，且每个非主属性都不传递依赖于码，则R∈3NF。
规范化

一般情况下，3NF已经解决绝大多数数据的冗余、插入、删除、修改异常。
2. 继续6-3-2例 S2（SNO，SD，MN）∈2NF， SNO T MN 进行分解： S21　（SNO，SD） S22　（SD，MN）到此，S关系所分解得到了以下三个关系： 6.3 S1 （SNO，CNO，GRADE） ∈3NF 规范化 S21（SNO，SD）∈3NF S22 （SD，MN） ∈3NF 一般情况下，3NF已经解决绝大多数数据的冗余、插入、删除、修改异常。

例6-3-3 ：R（BNO，BNAME，AUTHOR）
3. 出现异常的问题例6-3-3 ：R（BNO，BNAME，AUTHOR）书号　　书名　　　作者约定：一本书只有一个书号（即：一个书号对应一个书名）。一个书名可有多个书号（即：不同书号可以有相同的书名）。 6.3 每本书可由多个作者，但一个作者编的书名应不同。规范化从语义得到 F={BNO→BNAME，（AUTHOR，BNAME）→BNO} 求：码

因为：BNO→BNO，BNO→BNAME 所以：BNO→BNO，BNAME
F={BNO→BNAME，（AUTHOR，BNAME）→BNO} 解：因为：BNO→BNO，BNO→BNAME 所以：BNO→BNO，BNAME 据A2：BNO，AUTHOR→BNO，BNAME， AUTHOR 候选键：（BNO，AUTHOR）又因为：AUTHOR，BNAME→BNO 6.3 据A1：AUTHOR，BNAME→AUTHOR，BNAME 规范化据A4：AUTHOR，BNAME→BNO，BNAME，AUTHOR 侯选键：（AUTHOR，BNAME）因为该关系模式中无非主属性，所以R∈3NF。

6.3.6 BCNF（Boyce Codd Normaol Form）
1. 定义： R（U，F）∈1NF，若X→Y，且Y∈X时，X必含有码，则R∈BCNF。即：每一个决定因素必含有码。可以推出以下结论：R∈BCNF , 则所有非主属性对每一个码都是完全函数依赖。 6.3 所有主属性对每一个不包含它的码，也是完全函数依赖。规范化没有任何属性完全依赖于非码的任何一组属性。

因为BNO→BNAME，而BNO不是码。所以R∈BCNF。
例6-8中：因为BNO→BNAME，而BNO不是码。所以R∈BCNF。分解： R1（BNO，BNAME） ∈BCNF 6.3 R2（BNO，AUTHOR）∈BCNF 规范化但会丢失（AUTHOR，BNAME）→BNO，产生语义矛盾。

如例6-3-3在分解前： BNO BNAME AUTHOR 1 OS A B 2 C D 3 DB E 6.3 规范化

即：同一作者可以编写同名的两本书，违背了语义，丢失了（AUTHOR，BNAME）→BNO函数依赖。故：范式级别并非越高越好。
在分解后： BNO AUTHOR 1 A B 2 BNO BNAME 1 OS 2 即：同一作者可以编写同名的两本书，违背了语义，丢失了（AUTHOR，BNAME）→BNO函数依赖。故：范式级别并非越高越好。 6.3 规范化

（SNO，CNO，GRADE）∈BCNF
学生　课程　名次例6-3-4：R（S， C， P）约定：每一个学生选一课有一名次，（S，C）→P 每门课每一名只有一个人（无并列）（C，P）→S 码是（S，C），（C，P）。即决定因素含有码。 6.3 符合BCNF的定义。R∈BCNF 规范化例6-1-1经过分解得到的：（SNO，CNO，GRADE）∈BCNF （SNO，SD）∈BCNF　　　（SD，MN）∈BCNF　　　

小结求码。 1NF、2NF、3NF、BCNF的判断。 6.3 规范化

作业如何判断一个关系模式的范式级别？ P195 2 上次作业增加判断范式级别 2. 已知：R（ABCDE）
上次作业增加判断范式级别 2. 已知：R（ABCDE） F={AB→C，DE→C，B→D} 求：R的候选键和范式级别 3. 已知：R（ABCD）F={A→BC，B→D} 求：候选键和范式级别 4. 已知：R（ABCDE）F={AB→C, C→D,D→B，D→E} 本节结束

6.3.7　多值依赖引例例6-3-5：R（C， T， B）课程　老师　教课书约定：某一门课有多个老师教，他们使用相同一套书，每个老师可以教多门课，一种参考书可以供多门课用。 C T B C1 T1 T2 B1 B2 B3 C2 T3 B4 B5 C3 T4 B6 6.3 规范化

在R（C，T，B）中，码为(C，T，B) 是全码。
2.变为二维表： C T B C1 T1 B1 B2 B3 T2 C2 B4 B5 T3 C3 B6 T4 6.3 规范化在R（C，T，B）中，码为(C，T，B) 是全码。

② 增加复杂：每增加一老师，就要增加若干记录。
3. 存在问题： ①冗余大。 ② 增加复杂：每增加一老师，就要增加若干记录。 ③ 删除复杂：每门课去一门参考书，就要删去若干记录。 ④ 修改复杂：每门课改一门参考书，就要改若干记录。 6.3 上述的问题，因为B和T的取值毫无关系，只取决于C，即R中存在着一种称为多值依赖的数据依赖。规范化

4. 定义：设R（U）是属性集U上的一个关系模式。X，Y，Z是U的子集，并且Z＝U－X－Y，关系模式R（U）中多值依赖X→→Y成立，当且仅当对R（U）的任一关系r，给定的一对（X，Z）值，有一组Y的值，这组值仅仅决定于X的值而与Z无关。（X，Y1，Z1）或：如果存在 6.3 （X，Y2，Z2）规范化（X，Y1，Z2）则存在（X，Y2，Z1）则称为多值依赖X→→Y。

有 w[Y]=t[Y] 和 v[Y]=s[Y] w[Z]=s[Z] v[Z]=t[Z] 存在
另定义： R（U）中的任一关系r中，X，Y，Z＝U－X－Y，任意两个元组t、s，有t[X] = s[X]，就存在元组w，v∈r（w，v可以与t，s相同）使得： w[X]=v[X]=t[X] 有 w[Y]=t[Y] 和 v[Y]=s[Y] w[Z]=s[Z] v[Z]=t[Z] 存在 6.3 规范化即交换s，t元组中的Y值即得的两个新元组必在r中，则X→→Y。

把r投影到XY和R-XY上，连接两投影，如果仍为r，则是MVD。当且仅当R无损分解为XY，XZ。
另定义：把r投影到XY和R-XY上，连接两投影，如果仍为r，则是MVD。当且仅当R无损分解为XY，XZ。 6.3 规范化

上例中：C →→ T, C →→ B 6. MVD的性质： ⑴. 对称性：X→→Y则X→→Z，其中Z＝U－X－Y
⑵. 传递性：X→→Y则Y→→Z，则X→→Z－Y ⑶. FD是MVD的特殊情况：若X→Y则X→→Y 6.3 平凡的MVD：如果X→→Y，而Z＝，则X→→Y为平凡的MVD。规范化

6. FD和MVD的区别、联系（1）联系： FD可以看作是MVD的一个子集。
因为X→Y描述了X和Y之间1：1的联系，而X→→Y是描述X与Y之间1：M的联系。如果X→→Y中规定每个X只有一个Y与之对应，那么X→→Y就成了X→Y。 6.3 规范化

① FD：X→Y的有效性仅取决于X，Y，只要在W上成立，则在U上也成立（XYWU）。
（2）区别： MVD的有效性与属性集范围有关。 ① FD：X→Y的有效性仅取决于X，Y，只要在W上成立，则在U上也成立（XYWU）。 MVD：X→→Y不仅与X有关，还与U－X－Y有关，X→→Y在W上成立，在U上不一定成立。（WU） 6.3 ② FD：X→Y在R（U）上成立，则对Y`Y，有X→Y` 规范化 MVD：X→→Y在R（U）上成立，则Y`Y，不一定有X→→Y`。

R1（SNO，SAGE） R2（SNO，SSEX，SAGE）
例6-3-6: R1（SNO，SAGE） R2（SNO，SSEX，SAGE） SAGE SNO 18 S1 S2 19 S3 S4 SAGE SNO SSEX 18 S1 女 S2 男 19 S3 S4 对R1：SAGE→→SNO成立。对R2： SAGE→→SNO 成立吗？（X，Y1，Z1）则存在（X，Y1，Z2） 6.3 规范化（X，Y2，Z2）（X，Y2，Z1）则有：18 s1 女 s1 男 18 s2 男 s2 女存在显然是不可能的。所以： SAGE→→SNO

小结 BCNF的判断。 MVD。 MVD和FD的区别。 6.3 规范化本节结束

6.3.8 4NF 1. 定义： R（U）∈1NF，如果对于R的每个非平凡的MVD，X→→Y（YX），X都含有码，则R（U）∈4NF。
（因为X含有码，则X→Y。 6.3 4NF所允许的非平凡的MVD实际上就是FD。）规范化

2. 举例例6-3-7： R（C，T，B） R∈BCNF C→→T（非平凡）而码为CTB C→→B（非平凡）而码为CTB
R ∈ 4NF 6.3 分解为：规范化 R1（C，T）　　C→→T（平凡）码为CT R2（C，B）　　C→→B（平凡）码为CB 所以R1∈4NF 　　R2∈4NF

老师、学生只能属于一个系，T→SD，S→SD 该关系的码为（T，S）
例6-3-8： R（SD， T， S）系名　老师　学生一个系有多个老师　SD→→T 一个系有多个学生　SD→→S 老师、学生只能属于一个系，T→SD，S→SD 6.3 该关系的码为（T，S）规范化 SD→→T SD不含有码所以，R4NF SD→→S SD不含有码 R1（SD，T）∈4NF 分解为： R2（SD，S）∈4NF

例6-3-9： R（W， S， C）一个仓库有多个保管员： W→→S 一个仓库有多个商品： W→→C 保管员只能属于是某一仓库： S→W，
仓库　保管员　商品一个仓库有多个保管员： W→→S 一个仓库有多个商品： W→→C 保管员只能属于是某一仓库： S→W，则码是（S， C） 6.3 规范化 W→→S 不含有码（S，C） W→→C 不含有码（S，C）分解为： R1（W，S）∈4NF R2（W，C）∈4NF

在FD范畴内，BCNF是最高范式。结论：在MVD范畴内，4NF是最高范式。 6.3 规范化

6.3.9 联接依赖（JD）定义：设U是关系模式R的属性域，R1，R2…Rｎ为U的子集，满足U＝R1∪R2∪…∪Rｎ，＝{R1，R2，…Rｎ}是R的一分解，如果对于R的每个关系r都有M (r)=r，即 r＝∏R1(r) ∏R2(r)…∏Rn(r) 6.3 那么，称联接依赖在模式R上成立，记作：规范化＊（R1，R2，…Rn）

设R（SPJ）有一个JD ＊（SP，PJ，JS）
例6-3-10：设R（SPJ）有一个JD ＊（SP，PJ，JS）如果R的关系中已有两个元组（S1，P1，J2）和（S1，P2，J1）现在要插入一个元组（S2，P1，J1），据JD的定义，只有再插入一个元组（S1，P1，J1）才能保持JD。 R1 R2 S P J S1 P1 J2 P2 J1 S P J S1 P1 J2 P2 J1 S2 6.3 规范化图1 图2

R2不符合＊（SP，PJ，JS）因为R2分解为： R2 S P J S1 P1 J2 P2 J1 S2 S P S1 P1 P2 S2 P
6.3 规范化 S P S1 P1 P2 S2 P J P1 J2 P2 J1 J S J2 S1 J1 S2

同理，要删除一个元组，也必须删除其他元组，才能保持JD，对这种异常，用分解方法，提出一个比4NF提高的范式5NF。
S P S1 P1 P2 S2 P J P1 J2 P2 J1 J S J2 S1 J1 S2 SP∞PJ SP∞PJ∞JS S P J S1 P1 J2 J1 P2 S2 S P J S1 P1 J2 P2 J1 S2 6.3 规范化同理，要删除一个元组，也必须删除其他元组，才能保持JD，对这种异常，用分解方法，提出一个比4NF提高的范式5NF。

投影连接范式PJNF（5NF）定义：如果关系模式R的每个JD均由R的候选键隐含，那么称R是投影连接范式（Project join NF）PJNF或5NF。如果＊（R1，R2，…Rn）中某个Ri是R，则JD称为平凡的JD。 ① JD是现实世界中属性间的一种抽象，是语义的体现。但较之FD，MVD不直观，很难断定是一个模式是否是5NF。 6.3 ② 但R∈5NF，则R∈4NF。规范化 ③ 现在还没有完备的推理规则。 ④ JD只有在关系的连接运算时才反映出来。

6.3.11 关系模式的规范化步骤 1NF ↓ 取消非主属性对码的部分FD 2NF ↓ 取消非主属性对码的传递FD 3NF ↓
关系模式的规范化步骤 1NF ↓ 取消非主属性对码的部分FD 2NF ↓ 取消非主属性对码的传递FD 3NF ↓ 取消主属性对码的部分、传递FD 6.3 BCNF 规范化取消非平凡的MVD不是FD的（即非平凡的MVD都是FD） ↓ 4NF ↓ 取消不是由候选码所蕴涵的JD 本节结束 5NF

6.4 模式分解在关系模式分解过程中，低一级关系模式分解为若干个高一级的模式的方法并不是标准。例6-4-1：R（SNO，SD，MN）
6.4 模式分解在关系模式分解过程中，低一级关系模式分解为若干个高一级的模式的方法并不是标准。例6-4-1：R（SNO，SD，MN） F＝｛SNO→SD，SD→MN｝ 6.4 分解一： R1（SNO）∈5NF 模式分解 R2（SD）∈5NF R3（MN）∈5NF 但分解后，丢失了许多信息，如查：学生的系主任，连接成了笛卡儿积。

分解二： R1（SNO，SD） R2（SNO，MN）但丢失SD→MN。分解三： R1（SNO，SD） R2（SD，MN） ∴分解：
6.4 R2（SD，MN）模式分解 ∴分解：既要保持“无损连接”（和原来的r一样）又要保持“函数依赖”（和FD等价）

那么称分解δ相对于F是“无损连接分解”，否则称为“损失连接分解”。
　1. 无损连接分解的形式定义　　无损连接分解的形式定义如下：设R是一个关系模式，F是R上的一个函数依赖(FD)集。R分解成数据库模式δ={R1,……,Rk}。如果对R中每一个满足F的关系r都有下式成立：　　那么称分解δ相对于F是“无损连接分解”，否则称为“损失连接分解”。　　从上述形式定义中可知，若直接根据定义来判断某个分解是否具有无损连接性，那么就得“对R中每一个满足F的关系r”进行测试，看是否满足上面的等式，这显然不可操作，因为“对R中每一个满足F的关系r”进行测试就意味着“对R中所有满足F的关系r”进行测试，显然是不可能的。这里所说的“关系”就是指一张具体的表。　　因此，必须寻求其它的可操作性方法来判别分解的无损连接性。 6.4 模式分解

设关系模式R=A1,…,An，R上成立的FD集F，R的一个分解p={R1,…,Rk}。无损连接分解的判断步骤如下：
2. 无损连接分解的普通判别方法——表格法设关系模式R=A1,…,An，R上成立的FD集F，R的一个分解p={R1,…,Rk}。无损连接分解的判断步骤如下：　　(1)构造一张k行n列的表格，每列对应一个属性Aj(1≤j≤n)，每行对应一个模式Ri(1≤i≤k)。如果Aj在Ri中，那么在表格的第i行第j列处填上符号aj，否则填上符号bij。　　(2)把表格看成模式R的一个关系，反复检查F中每个FD在表格中是否成立，若不成立，则修改表格中的元素。修改方法如下：对于F中一个FD：X→Y，如果表格中有两行在X分量上相等，在Y分量上不相等，那么把这两行在Y分量上改成相等。如果Y的分量中有一个是aj，那么另一个也改成aj;如果没有aj，那么用其中的一个bij替换另一个(尽量把ij改成较小的数，亦即取i值较小的那个)。 6.4 模式分解

　　　若在修改的过程中，发现表格中有一行全是a，即a1,a2,…,an，那么可立即断定p相对于F是无损连接分解，此时不必再继续修改。若经过多次修改直到表格不能修改之后，发现表格中不存在有一行全是a的情况，那么分解就是有损的。特别要注意，这里有个循环反复修改的过程，因为一次修改可能导致表格能继续修改。　　修改过程中要特别注意，若某个bij被改动，那么它所在列的所有bij都需要做相应的改动。为了明确这一点，举例说明。例如，我们根据FD“H→I”、“ K→L”来修改表格之前时的表格如表1所示(已经过多次修改，非初始表，空的单元表示省略)： 6.4 模式分解

H I J K L R1 b12 b35 R2 a1 a2 a4 b25 R3 a1 b12 a4 b35 R4 b12 b35 表1
　　　　　表1 H I J K L R b b35 R2 a a a b25 R3 a b a b35 R b b35 6.4 模式分解

　R2、R3所在行的H分量都为a1，根据FD“H→I”，需要修改这两行对应的I分量，而R2所在行的I分量为a2，因此，要将R3所在行的I分量b12修改为a2，注意到，R1、R4所在行的H分量也为b12，因此，这两行对应的I分量也必须修改为a2。R2、R3所在行的K分量都为a4，根据FD“K→L”，需要修改这两行对应的L分量，于是将R3所在行的L分量b35修改为较小的b25，同时注意到，R1、R4所在行的L分量也为b35，因此，这两行对应的L分量也必须修改为b25。修改后的表格如表2所示： 6.4 模式分解

表2 H I J K L R1 a2 b25 R2 a1 a2 a4 b25 R3 a1 a2 a4 b25 R4 a2 b25 6.4
　　　表2 H I J K L R a b25 R2 a a a b25 R3 a a a b25 R a b25 6.4 模式分解

设关系模式 R为 R(H,I,J,K,L)，R上的一个函数依赖集为 F={H→J,J→K,I→J,JL→H}，分解 (38) 是无损连接的。
　　　例题：(软件设计师试题38) 设关系模式 R为 R(H,I,J,K,L)，R上的一个函数依赖集为 F={H→J,J→K,I→J,JL→H}，分解 (38) 是无损连接的。　　供选择的答案：　　(38) A. p={HK，HI，IJ，JKL，HL} B. p={HIL，IKL，IJL} 　　C. p={HJ，IK，HL} D. p={HI，JK，HL} 　　试题分析：　　根据上述判断方法，我们列出选项B(分解成三个关系模式R1(HIL)、R2(IKL)、R3(IJL) )的初始表如表3所示： 6.4 模式分解

表3 选项B的初始表 H I J K L HIL a1 a2 b13 b14 a5 IKL b21 a2 b23 a4 a5
IJL b a a b a5 　　对于函数依赖集中的H→J、J→K对表3进行处理，由于属性列H和属性列J上无相同的元素，所以无法修改。但对于I→J在属性列I上对应的1、2、3行上全为a2元素，所以，将属性列J的第一行b13和第二行b23改为a3。修改后如表4所示： 6.4 模式分解

从表5可以看出，第二行为a1、a2、a3、a4、a5，所以分解p是无损的。
表4 选项B的中间表 H I J K L HIL a a a b a5 IKL b a a a a5 IJL b a a b a5　　对于函数依赖集中的JL→H在属性列J和L上对应的1、2、3行上为a3、a5元素，所以，将属性列H的第二行b21和第三行b31改为a1。修改后如表5所示：　　表5 选项B的结果表 H I J K L HIL a a a b a5 IKL a a a a a5 IJL a a a b a5　　从表5可以看出，第二行为a1、a2、a3、a4、a5，所以分解p是无损的。 6.4 模式分解

　　有一种特殊情况要注意：分解后的各个关系模式两两均无公共属性。由于是模式分解，那么任一一个分解后的关系模式覆盖的属性集不可能是分解前的整个全部属性U，因此初始表中不存在全是a的行。又注意到，分解后的各个关系模式两两均无公共属性，表明任两行在任一列上都没有相同的分量，这导致整个表格无法修改，保持初始状态。而初始状态不存在全是a的行，因此这种特殊情况的分解是有损的。　　例如，函数依赖集合FD，将关系模式R(ABCDEF)分解成R1(AB)、R2(CDE)、R3(F)，那么这种分解肯定是有损的。考试中可能碰到这种情况，那么一眼就可以判断出结果，从而节省了时间。 6.4 模式分解

首先要申明，这种快捷方法是有前提的，前提就是分解后的关系模式只有两个。其内容为：
　　3. 无损连接分解的快捷判别方法首先要申明，这种快捷方法是有前提的，前提就是分解后的关系模式只有两个。其内容为：　　设ρ={R1，R2｝是R的一个分解，F是R上的FD集，那么分解ρ相对于F是无损分解的充分必要条件是：(R1∩R2)→(R1–R2)或(R1∩R2)→(R2–R1)。这个“或”字很重要，这里表示(R1∩R2)→(R1–R2)、(R1∩R2)→(R2–R1)中只要有一个成立就行。这里的求交和相减运算的对象是关系模式的属性。 6.4 模式分解

关系模式R(U，F)，其中U={W,X,Y,Z},F={WX→Y,W→X, X→Z,Y→W}。那么下列分解中是无损分解的是。
　　　例题　　关系模式R(U，F)，其中U={W,X,Y,Z},F={WX→Y,W→X, X→Z,Y→W}。那么下列分解中是无损分解的是。　　供选择的答案：　　A.p={R1(WY),R2(XZ)} B.p={R1(WZ),R2(XY)} 　　C.p={R1(WXY),R2(XZ)} D.p={R1(WX),R2(YZ)} 　　试题分析：　　A选项，R1∩R2为空，肯定不满足条件。　　B选项，R1∩R2为空，肯定不满足条件。　　C选项，R1∩R2={X}，R1-R2={WY}，R2-R1={Z}，根据函数依赖集，X→Z成立，所以满足条件。　　D选项，R1∩R2为空，肯定不满足条件。 6.4 模式分解

　　　　4. 总结　　模式分解无损性判别的源泉仍然是普通的表格法。这种快捷方法只不过是根据这种表格法推断出来的而已，是它的一个特列。但是这种快捷方法却往往非常有用。 6.4 模式分解

小结 1. 推理公理 2. F的闭包 3. 属性闭包要保持“无损连接” 又要保持“函数依赖” 6.4 模式分解本节结束

1. 已知：R（ABCDEG） F={D→G, C→A，CD→E，A→B} 求：D+ 、C +、 A + 、CD + 、AD +、 AC + 、 ACD +。解： D+={DG} C+={CAB} A+={AB} CD+={CDAGEB} AD+={ADBG} AC+={ACB} ACD+={ACDBEG}

(1)学生（学号,姓名,出生年月,系名,班号,宿舍区） F={系名→宿舍区} 码:学号学号→系名,系名→宿舍区,有传递FD 学生∈2NF
2. (1)学生（学号,姓名,出生年月,系名,班号,宿舍区） F={系名→宿舍区} 码:学号学号→系名,系名→宿舍区,有传递FD 学生∈2NF (2)班级(班号,专业名,系名,人数,入校年份) F={(专业名,入校年份) ←→班号} 码: (专业名,入校年份) 班号因为专业名→系名, 所以(专业名,入校年份) →系名班级∈1NF P

(3) 系(系名,系号,系办公地点,人数) F={系名←→系号} 码:系名, 系号系∈BCNF 学会(学会名,成立年份,地点,人数) 码: 学会名学会∈BCNF (5) 参加(学生,学会名,入会年份) F={ (学生,学会名) →入会年份} 码: (学生,学会名) 参加∈BCNF

Click to edit company slogan .
Thank You ! Click to edit company slogan .

第6章关系数据理论 6.1关系模式的设计的问题 6.2 数据依赖的推理规则 6.3规范化 6.4模式分解.

Similar presentations

Presentation on theme: "第6章关系数据理论 6.1关系模式的设计的问题 6.2 数据依赖的推理规则 6.3规范化 6.4模式分解."— Presentation transcript:

Similar presentations

About project

反馈

请登录

Auth with social network:

第6章 关系数据理论 6.1关系模式的设计的问题 6.2 数据依赖的推理规则 6.3规范化 6.4模式分解.

Similar presentations

Presentation on theme: "第6章 关系数据理论 6.1关系模式的设计的问题 6.2 数据依赖的推理规则 6.3规范化 6.4模式分解."— Presentation transcript:

Similar presentations

About project

反馈

第6章关系数据理论 6.1关系模式的设计的问题 6.2 数据依赖的推理规则 6.3规范化 6.4模式分解.

Presentation on theme: "第6章关系数据理论 6.1关系模式的设计的问题 6.2 数据依赖的推理规则 6.3规范化 6.4模式分解."— Presentation transcript: