数据库系统课件：ch7 Relational Database Design (2)

1、Chapter 7: Relational Database Design (2)关系模式的分解和问题SCD(SNO,SN,AGE,DEPT,MN,CNO,SCORE)S(SNO,SN,AGE,DEPT)SC(SNO,CNO,SCORE)D(DEPT,MN)我们可以通过把一个关系模式的分解成多个关系模式，以解决它的插入、删除和更新操作所带来的一些问题。为了在分解要保证原来模式所满足的特性，要求分解处理具有无损连接和保持函数依赖。模式的分解定义 关系模式R的一个分解：= R1，R2，Rn U=U1U2Un，且不存在 Ui Uj，Fi 为 F在 Ui 上的投影模式的分解SnoSdeptSloc95

2、001CSA95002ISB95003MAC95004ISB95005PHB模式的分解SnoSdeptSloc95001CSA95002ISB95003MAC95004ISB95005PHB1. SL分解为下面三个关系模式： SN(Sno) SD(Sdept) SO(Sloc)分解后的关系为：Sno9500195002950039500495005分解后的数据库丢失了许多信息。例如无法查询95001学生所在学院或所在宿舍。 如果分解后的关系可以通过自然连接恢复为原来的关系，那么这种分解就没有丢失信息。SdeptCSISMAPHSlocABC模式的分解SnoSdeptSloc95001CSA95

3、002ISB95003MAC95004ISB95005PHB2. SL分解为下面二个关系模式： NL(Sno, Sloc) DL(Sdept, Sloc)分解后的关系为：SnoSloc95001A95002B95003C95004B95005BSdeptSlocCSAISBMACPHB模式的分解NL DLNL DL比原来的SL关系多了3个元组无法知道95002、95004、95005究竟是哪个学院的学生元组增加了，信息丢失了SnoSlocSdept95001ACS95002BIS95002BPH95003CMA95004BIS95004BPH95005BIS95005BPH模式的分解3. 将S

4、L分解为下面二个关系模式： ND(Sno, Sdept) NL(Sno, Sloc) 分解后的关系为：SnoSdeptSloc95001CSA95002ISB95003MAC95004ISB95005PHBSnoSdept95001CS95002IS95003MA95004IS95005PHSnoSloc95001A95002B95003C95004B95005BSnoSdeptSloc95001CSA95002ISB95003MAC95004ISB95005PHB信息没有丢失关系模式分解的标准三种模式分解的等价定义 分解具有无损连接性 分解要保持函数依赖 分解既要保持函数依赖，又要具有无损连

5、接性具有无损连接性的模式分解关系模式R的一个分解 = R1，R2， ，Rn若R与R1、R2、Rn自然连接的结果相等，则称关系模式R的这个分解具有无损连接性(Lossless join)具有无损连接性的分解保证不丢失信息无损连接性不一定能解决插入异常、删除异常、修改复杂、数据冗余等问题模式分解中存在的问题R(A, B, C)ABC112221AB1122BC1221ABC112221AB(R)BC(R)AB(R)BC(R)R(A, B, C)ABC111212AB1121BC1112ABC111112211212AB(R)BC(R)AB(R)BC(R)有损分解无损分解定理如果R的分解为R1,R2

6、，F为R上的函数依赖集合，分解具有无损连接性的充分必要条件为： R1 R2 (R1-R2)或 R1 R2 (R2-R1)两个模式的公共属性可以函数确定其中一个模式举例：设R=, U=ABC,F=AB,证明1R1(AB), R2(AC) 是无损连接，2R1(AB),R3(BC)不是无损连接。解：1=R1(AB), R2(AC)R1R2 = A, R1R2 = B由A B ，得到1是无损连接分解2=R1(AB), R2(BC)R1R2 = B, R1R2 = A, R2R1 = CBA, BC均不成立，所以1不是无损连接分解保持函数依赖的分解保持关系模式分解等价的另一个重要条件是关系模式的函数依赖

7、集在分解后仍在数据库模式中保持不变。即关系模式R 到=R1,R2Rk的分解，应使函数依赖集F，被F在这些Ri上的投影蕴涵保持函数依赖的模式分解设关系模式R被分解为若干个关系模式R1，R2，Rn (其中U=U1U2Un，且不存在Ui Uj，Fi为F在Ui上的投影)，若F所逻辑蕴含的函数依赖一定也由分解得到的某个关系模式中的函数依赖Fi所逻辑蕴含，则称关系模式R的这个分解是保持函数依赖的(Preserve dependency)。保持函数依赖的分解保持函数依赖的模式分解Z是U的子集，函数依赖集合F在Z上的投影定义为Z(F) = XY | XYF+ XY Z设 = R1, R2, , Rn是关系模式

8、R的一个分解，如果F+ = ( Ri(F)+，则称是保持函数依赖的分解保持函数依赖的分解如何判断分解保持函数依赖？回忆： F+ = ( Fi)+ F ( Fi )+， Fi F+如对于ABC，AB , BC的分解，思考：BC AB，AC+ ?检验：C ？模式的分解如果一个分解具有无损连接性，则它能够保证不丢失信息。如果一个分解保持了函数依赖，则它可以减轻或解决各种异常情况。分解具有无损连接性和分解保持函数依赖是两个互相独立的标准。具有无损连接性的分解不一定能够保持函数依赖。同样，保持函数依赖的分解也不一定具有无损连接性。保持函数依赖的分解关系模式RU = CITY, ST, ZIP,F = (

9、CITY, ST) ZIP, ZIP CITY = R1 = ST, ZIP, R2 = CITY, ZIPR1R2 =ZIP, R2R1 =CITY R1R2 R2R1 分解是无损的R1(F) = ， R2(F) = ZIP CITYR1(F) R2(F) = ZIP CITY丢失了函数依赖(CITY, ST) ZIP练习分析下列分解是否具有无损连接和保持FD的特点。1、R(ABC),F=CA, =AC,BC2、R(ABC),F=CB,AB, =AC,BC3、R(ABC),F=CA, =AB,AC4、R(ABC),F=CA,BC, =AB,AC1、无损，保持FD2、无损，不保持FD,丢失AB

10、3、有损分解，保持FD4、有损，不保持FD(丢失BC)F在AB,AC, BD,CD上的投影分别为AB,AC,DC丢失了BC,AD,所以此分解不保持FD题目：设关系模式R(A,B,C,D)F是R上成立的FD集，F=AB,BC,AD,DC, =AB,AC,BD,CD是R的一个分解。1、试求F在的每个模式上的投影？2、保持FD吗？为什么？不良的模式设计不良的数据依赖范式范式的判定模式分解各种异常部分函数依赖、传递函数依赖、多值依赖1NF、2NF、3NF、BCNF、4NFArmstrong公理、属性集的闭包、函数依赖的推导、候选码的计算、函数依赖集的等价和最小覆盖、模式分解的定义、保持函数依赖分解和保

11、持无损连接分解的判定和分解算法良好的模式设计范式定义范式是对关系的不同数据依赖程度的要求通过模式分解将一个低级范式转换为若干个高级范式的过程称作规范化（概念的纯粹化）1NF2NF3NF4NFBCNF5NF1NF定义关系中每一分量不可再分。即不能以集合、序列等作为属性值SNOCNOS1C1，C2，C3SNOCNOS1C1S1C2S1C31NF对象关系数据库嵌套关系传统数据库平面关系1NFSNOCNOS1C1，C2，C3适合于查询每个学生的选修课程SNOCNOS1, S2, S3C1适合于查询每门课程的选修学生两个都保存，数据冗余，更新困难只保存一个，某些查询困难1NF原子粒度的选择分量是否需要再

12、分，与具体应用有关。如果用到值的一部分，则需要进一步分割否则需要应用编码解析姓名生日王军68.7.10张立69.7.10李明80.3.28姓名年月日王军687.10张立697.10李明803.28只是查询出生日期比较两人生肖是否相同姓名年月日王军68710张立69710李明80328比较两人生日是否相同1NF较细的原子粒度有助于标准化，施加约束，避免输入错误，从而提高数据质量北京大学，北京，中国，100871，11/25/2006中国，北京，北京大学，100871，25/11/2006国家城市单位邮编年月日中国北京北京大学100871200611252NFSNOSNSDDEANCNOGSNOS

13、NSDDEANCNOGS01杨明D01思齐C0190S02李婉D01思齐C0187S01杨明D01思齐C0292S03刘海D02述圣C0195S04安然D02述圣C0278S05乐天D03省身C01822NF不良特性插入异常：如果学生没有选课，关于他的个人信息及所在系的信息就无法插入删除异常：如果删除学生的选课信息，则有关他的个人信息及所在系的信息也随之删除了更新异常：如果学生转系，若他选修了k门课，则需要修改k次数据冗余：如果一个学生选修了k门课，则有关他的所在系的信息重复SNOSNSDDEANCNOG2NF定义若R1NF，且每个非主属性完全依赖于R的每一个候选关键字 ，则称R2NF消除非主

14、属性对码的部分依赖如S2NF，因为（SNO，CNO） SN （SNO，CNO） SD2NF改造非主属性有两种，一种完全依赖于码，一种部分依赖于码。将S分解为：SC(SNO , CNO , G)S_SD(SNO, SN , SD , DEAN)快速热身关系模式R（A，B，C，D），码为AB，给出它的一个函数依赖集，使得R属于1NF而不属于2NF分解说明一个1NF，但非2NF的关系总是可以被分解成为一组2NF的关系规范化过程中通过一组投影运算消除部分依赖，建议作如下分解(第一步分解)已知关系R(A,B,C,D), (A,B)为主码，即(A,B) C, (A,B) D，且A D, 则将R分解成为两个

15、投影:R1(A,D), A为主码R2(A,B,C), (A,B)为主码，A为外码这样，R可以通过R1和R2的自然连接运算得以恢复，即满足分解的无损连接性3NFSNOSNSDDEANS01杨明D01思齐S02李婉D01思齐S03刘海D02述圣S04安然D02述圣S05乐天D03省身SNOCNOGS01C0190S02C0187S01C0292S03C0195S04C0278S05C0182SNOSNSDDEANSNOCNOG3NFS_SD(SNO , SN , SD , DEAN)不良特性插入异常：如果系中没有学生，则有关系的信息就无法插入删除异常：如果学生全部毕业了，则在删除学生信息的同时有关

16、系的信息也随之删除了更新异常：如果学生转系，不但要修改SD，还要修改DEAN，如果换系主任，则该系每个学生元组都要做相应修改数据冗余：每个学生都存储所在系的系主任的信息3NF定义关系模式R中，若不存在这样的码X，属性组Y及非主属性Z(Z Y)，使得下式成立，XY , YZ , YX则称R3NF如果R的任何一个非主属性都不传递依赖于它的任何一个侯选关键字，则称R是第三范式，简记为3NF。 消除非主属性对码的传递依赖 如S_SD 3NF，因为有SNOSD，SDDEAN3NF改造将S分解为STUDENT(SNO , SN , SD)DEPT(SD , DEAN)快速热身关系模式R（A，B，C，D），

17、码为AB，给出它的一个函数依赖集，使得R属于2NF而不属于3NFSNOSNSDS01杨明D01S02李婉D01S03刘海D02S04安然D02S05乐天D03SDDEAND01思齐D02述圣D03省身分解说明一个2NF，但非3NF的关系总是可以被分解成为一组3NF的关系规范化过程中通过一组投影运算消除传递依赖，建议作如下分解(第二步分解)已知关系R(A,B,C), A为主码(A B, A C)，且 B C,则将R分解成为两个投影:R1(B,C), B为主码R2(A,B), A为主码，B为外码这样，R可以通过R1和R2的自然连接运算得以恢复，分解满足分解的无损连接性BCNFCNOTNOSNOST

18、C(SNO , TNO , CNO)每位老师只教授一门课某学生选定一门课，就对应一位老师STC 3NF ？TNO CNO(SNO，CNO) TNO候选码(SNO，TNO) or (SNO，CNO)BCNFSNOTNOCNOs1t1c1s2t2c2s3t3c2s3t1c1BCNF不良特性插入异常：如果没有学生选修某位老师的任课，则该老师担任课程的信息就无法插入删除异常：删除学生选课信息，会删除掉老师的任课信息更新异常：如果老师所教授的课程有所改动，则所有选修该老师课程的学生元组都要做改动数据冗余：每位学生都存储了有关老师所教授的课程的信息症由：TNO CNO，属性对码的不良依赖STC(SNO ,

19、 TNO , CNO)BCNF定义关系模式R中，对于属性组X，Y，若XY且 Y X时X必含有码，则RBCNF如STC BCNF，因为TNO CNO，而TNO不含有码改造将S分解为(SNO，TNO)，(TNO，CNO)SNOTNOs1t1s2t2s3t3s3t1TNOCNOt1c1t2c2t3c2关系模式的分解算法算法：（达到BCNF无损连接分解算法）给定关系模式R ，令 = R检查中各关系模式是否属于BCNF，若是，则算法终止 设 中Ri不属于BCNF，则存在函数依赖XA ，且X不是Ri的码，则XA是Ri的真子集，将Ri分解为=S1，S1，其中US1 = XA， US2 = Ui A以代替Ri

20、 ，返回到志能总结：把不合格的两个放到一个集合，再将推出者放回到原集合中关系模式的分解算法示例：R=，U=A，B，C，D，EF=AB，BC，(A,D)E ,求R的一个BCNF分解解：1. 求候选码码是AD2. 检查AB，由于A不是码，因此U1=A，B , F1=AB U2=A, C, D, E, F2=AC, (A,D)E3. 检查AC，由于A不是码，因此U1 = A, B, F1=AB U2 = A, C, F2=AC U3 = A, D, E, F3 = (A,D)E关系模式的分解算法示例：U=(SNO，TNO，CNO)F=(SNO，CNO)TNO, TNOCNO解：不属于BCNF，分解为

21、U1=(SNO，TNO)，U2=(TNO，CNO)，F2=TNOCNO丢失了函数依赖(SNO，CNO)TNO，原来一个学生选修一门课程时，只能对应一个老师；在新的关系模式下现在一个学生选修一门课程时，可能会对应多个老师。关系分解为BCNF，不一定能保持函数依赖关系模式的分解算法结论：若要求分解保持函数依赖，那么分解后的模式总可以达到3NF，但不一定能达到BCNF算法：（达到3NF且保持函数依赖的分解）求F的最小覆盖Fmin 找出不在Fmin中出现的属性，将它们构成一个关系模式，并从U中去掉它们(剩余属性仍记为U)若有XA Fmin，且XA=U，则=R，算法终止关系模式的分解算法对Fmin按具有相同左部的原则进行分组（设为k组），每一组函数依赖所涉及的属性全体为Ui，令Fi为Fmin在Ui上的投影，则=R1 , , Rk是R的一个保持函数依赖的分解，并且每个Ri 3NFP-PROVINCE,C-CITY,S-STREET,Z-ZIP设有关系模式R(SNO, SN, P, C, S, Z)F=SNOSN, SNOP, SNOC, SNOS, SNOZ, P,C,SZ, ZP, Z C，试分解R为3NF。解：求F的最小覆盖Fc=SNOSN,P,C,S, P,C,SZ, ZP,C根据上述算法，则分解为