0数据库第七讲lecture

1、范式 normal formu 范式是符合某一种级别的关系模式的集合u 关系数据库中的关系必须满足一定的要求。满足不同程 度要求的为不同范式u 范式的种类：第一范式(1NF)第二范式(2NF)第三范式(3NF) BC范式(BCNF)第四范式(4NF)第五范式(5NF)u 对于各种范式之间的有u 5NFÌ4NFÌBCNF Ì3NF Ì2NF ÌlNF成立，如图5.2所示。范式 normal formu 一个低一级范式的关系模式，通过模式分解可以转换为若干个高一级范式的关系模式的集合，这种过程就叫规范化1NFu 1NF的定义:如果一个关系模式R的所

2、有属性都是不可分的基本数据项，则R1NFu 第一范式是对关系模式的最起码的要求。不满足第一范式的数据库模式不能称为关系数据库u 但是满足第一范式的关系模式并不一定是一个好的关系模式Example: 关系模式 SLC(Sno, Sdept, Sloc, Cno, Grade)Sloc为学生住处，假设每个系的学生住在同一个地方u 函数依赖包括：(Sno, Cno) FSno SdeptGrade(Sno, Cno)Sno SlocPSdept(Sno, Cno) PSdept SlocSlocsnosdeptsloccnog1001计算机一号楼c001881001计算机一号楼c002781001计

3、算机一号楼c003901002英语二号楼c001851002英语二号楼c002801003计算机一号楼c003751003计算机一号楼c002821004管理三号楼c001751005管理三号楼c00188SLCSnoSdeptGradeCnoSlocu S-L-C的码为(Sno, Cno)u S-L-C满足第一范式。u 非主属性Sdept和Sloc部分函数依赖于码 SnoCnoSLCS不L是C不一是个一好个的好关的系关模系式模式1异常假设Sno'1006'，Sdept'英语'，Sloc'二号楼'的学生还未选课，因课程号是主属性，因此该学生的SL

4、C。信息无法(2) 删除异常假定某个学生本来只选修了c003课程这一门课。现在因身体不适，他连c003号课程也不选修了。因课程号是主属性，此操作将导致该学生信息的整个元组都要删除。SLC不是一个好的关系模式(3) 数据冗余度大如果一个学生选修了10门课程，那么他的Sdept和Sloc值就要重复10次。(4) 修改复杂例如学生转系，在修改此学生元组的Sdept值的同时，还可能需要修改住处（Sloc）。如果这个学生选修了K门课，则必须无遗漏地修改K个元组中全部Sdept、Sloc信息。SLCS不L是C不一是个一好个的好关的系关模系式l Sdept、 Sloc部分函数依赖于码。u 解决方法l SLC

5、分解为两个关系模式以消除这些部分函数依赖SC（Sno， Cno， Grade）SL（Sno， Sdept， Sloc）函数依赖图：SLSCSdeptSnoSnoGradeCnoSloc关系模式SC的码为（Sno，Cno）关系模式SL的码为Sno这样非主属性对码都是完全函数依赖2NFu 2NF的定义:若R1NF，且一个非主属性完全函数依赖于码，则R2NF。关键理解点：l 非主属性l 码：指侯选码l 完全函数依赖和部分函数依赖例：SLC(Sno, Sdept, Sloc, Cno, Grade) 1NFSLC(Sno, Sdept, Sloc, Cno, Grade) 2NFSC（Sno， Cno

6、， Grade） 2NF SL（Sno， Sdept， Sloc） 2NF2NFu 采用投影分解法将一个1NF的关系分解为多个2NF的关系，可以在一定程度上减轻原1NF关系中存在的异常、删除异常、数据冗余度大、修改复杂等问题。u 将一个1NF关系分解为多个2NF的关系，并不能完全消除 关系模式中的各种异常情况和数据冗余。u 如前例SL(SNO，SDEPT，SLOC)Î2NFu 1异常：l 新成立一个新系，该系在未招生前就安排好住在哪个楼，此 时由于SNO为空，而无法将该系及其组所SDEPT和SLOC的信息；u 2删除异常：l 当某个系的学生都毕业后，删除学生信息时，也会把SLOC的

7、信息删掉。u 因此，2NF并没有彻底解决上述问题，我们必须寻找更 好的关系模式。3NFu 3NF的定义若R3NF，则每一个非主属性既不部分依赖于码也不传递依赖于码。如果R3NF，则R也是2NF。3NF虽然排除了非主属性对码部分依赖和传递依赖，但是，可能存在有主属性对码的部分依赖或传递依赖example2NF关系模式S-L(Sno,l 函数依赖：Sdept,Sloc)中SnoSdeptSdeptSloc 可得：传递SnoSloc，即S-L中存在非主属性对3NF码的传递函数依赖，S-函数依赖图：S-LSdeptSnoSlocu 解决方法采用投影分解法，把S-L分解为两个关系模式，以 消除传递函数依

8、赖：S-D（n，Sdept）D-L（Sdept，Sloc）S-D的码为Sno，D-L的码为Sdept。n 分解后的关系模式S-D与D-L中不再存在传递依赖S-D的码为Sno， D-L的码为SdeptSnoSdeptSdeptSlocS-DD-LS-L(Sno, Sdept, Sloc) 2NF S-L(Sno, Sdept, Sloc) 3NFS-D(Sno，Sdept) 3NF D-L(Sdept， Sloc) 3NF3NF3NFu 采用投影分解法将一个2NF的关系分解为多个3NF的关系，可以在一定程度上解决原2NF关系中存在的、删除异常、数据冗余度大、修改复杂等问题。异常一2NF关系分解为

9、多个3NF的关系后，仍然不能完全消除关系模式中的各种异常情况和数据冗余。u 3NF是一个可用的关系模式应满足的最低范式。u 思考:u 1 怎样关系模式R 2NF?u 2 怎样关系模式R 3NF?u 3 2NF和3NF主要研究了关系模式R中,哪两种属性组间的什么类型的函数依赖关系?22例u 关系模式STJ(S，T，J)中，S表示学生，T表示教师，J表示课程。u 每一教师只教一门课。u 每门课可以有若干教师教，u 一名学生只能在某位教师那里学习某门课程，某一学生选定某门课，就对应一个固定的教师。由语义可得到如下的函数依赖。u (S，J)T;(S，T)J:TJ，u 该关系的码有两个（S，T）和(S，

10、J)?l 所以，S，T，J都是主属性，它没有非主属性。所以该关系必然是3NF(即没有任何非主属性对码传递依赖或部分依赖)u 当以（S，T）作为主码，如果知道T，J的值，而不知道S的值，则这样的元组无法，产生异常现象u 因此：一个3NF的关系模式也会产生异常等问题u 可见，3NF虽然排除了非主属性对码的部分依赖和传递依赖，但是，可能其它问题。BCNFu 关系模式R1NF，若XY且Y Í X时X必含，则RBCNF。关键理解点：123XYY ÍXX必含u 等价于：每一个决定属性因素都包含码25BCNFu 若RBCNFl 所有非主属性对每一个码都是完全函数依赖l 所有的主属性对每一

11、个不包含它的码，也是完全函数依赖l 没有任何属性完全函数依赖于非码的任何一组属性26BCNF充分u R BCNFR 3NF不必要u 因此：l 如果R3NF且每一个决定因素都包含码，则RBCNF27例u 关系模式STJ(S，T，J)中，S表示学生，T表示教师，J表示课程。u 每一教师只教一门课。u 每门课可以有若干教师教，u 一名学生只能在某位教师那里学习某门课程，某一学生选定某门课，就对应一个固定的教师。由语义可得到如下的函数依赖。u (S，J)T;(S，T)J:TJ，u 该关系的码有两个（S，T）和(S，J)u 该关系是3NF?是BCNF?BCNF-example关系模式C(Cno,Cnam

12、e,Grade)是3NF?n 分析：BCNF?n 关系模式C只有一个主码Cno, 没有任何属性对码Cno部门函数依赖或传递函数依赖。所以C3NFn 另外C中Cno是唯一的决定因素，当然包含码, 所以CBCNFBCNF-examplen 关系模式S(Sno,Sname,Sdept,Sage)n 假定S的码是Sno和Sname，两者都唯一标识元组n 3NF?BCNF?：n 非主属性Sdept,Sage不存在对码的部分依赖或传递依赖，所以S3NFn 关系模式S中决定因素只有2个Sno和Sname，每一个决定因素都包含码，所以S BCNF在关系模式STJ（S，T，J）中，S表示学生，T表示教师，J表示

13、课程。l 假设有函数依赖：(S，J)T，(S，T)J，TJl (S，J)和(S，T)都是候选码l STJ属于3NF吗？属于BCNF吗？SSTJJTSTJ中的函数依赖STJ3NF没有任何非主属性对码传递依赖或部分依赖STJBCNFT是决定因素，T不包含码BCNF（续）解决方法：将STJ分解为二个关系模式：ST(S，T) BCNF， TJ(T，J) BCNFSTTJSTTJ没有任何属性对码的部分函数依赖和传递函数依赖333NF与BCNF的关系充分不必要u R BCNFR 3NFu 如果R3NF，且R只有一个候选码充分必要R BCNFR 3NF34BCNF与3NF的区别u BCNF不仅强调其它属性对

14、码的完全直接依赖，而且强调主属性对码的完全直接依赖。u 3NF只强调非主属性对码的完全直接依赖。353NF与BCNF的关系u 3NF和BCNF是在函数依赖的条件下对模式分解所能达到的分离程度的测度。l 一个模式中的关系模式如果都属于BCNF，那么在函数依赖范畴内，它已实现了彻底的分离，已消除和删除的异常。3NF的“不彻底”性表现在可了能存在主属性对码的部分依赖和传递依赖。u 许多开发者认为，通常关系模式只要满足第三范式的要求就可以使用了；当然，满足BCNF更好。但是，在有些情况下，我们必须寻找更高级的关系模式才能解决问题。36l 指出R是否为3NF,是否为BCNF,为什么?BNOBNAMEAU

15、THORNO1C语言张三NO1C语言李四NO2C语言刘海NO2C语言王五NO3数据库李四NO3数据库王五练:设关系模式R(BNO,BNAME,AUTHOR)的属性分别表示 书号,书名和作者名.l 规定,每个书号只有一个书名,但不同书号可以有相同 书名,每本书可以有多个作者合写,但每个作者参与编 著的书名应该互不相同.u 问题：l 写出R的侯选码，主码，主属性，非主属性?u 函数依赖：l BNO® BNAMEl （AUTHOR, BNAME）®BNOl （AUTHOR, BNO） ®BNAMEu 侯选码为l (BNO,AUTHOR)和（ BNAME,AUTHOR)l

16、 BNO BNAME AUTHOR都是主属性u 所以R是3NF，u R不是BCNF，因为BNO® BNAME ，而BNO不是码。Closure of a Set of Functional Dependenciesu Given a set Fof functional dependencies, thereare certaiother functional dependencieshatare logically implied by F.If A ® B andB ® C,l For example:then we caninfer that A ®

17、; Cu The set of all functional dependencies logicallyimlied bF is the closure of F.u We denote the closure of F by F+.u F+ is a superset of F.Boyce-Codd Normal FormA relation schema R is in BCNF with respect to a set F offunctionaldependencies if for all functional dependenciesin F+ of the forma

18、74;where a Í R and b Í R, at least one of the following holds:u a ® bi.e. b Í a)is trivialu a is a superkey for R意思是所有决定属性都包含码!Boyce-Codd Normal FormExample schema not in BCNF:instr_dept (ID, name, salary, dept_name, building, budget )because dept_name® building, budgetholds

19、 on instr_dept, but dept_name is not a superkeyDecomposing a Schema into BCNFu Suppose we have a schema R and a non-trivial de endenca ®b causes a violation of BCNF.We decompose R into:(a U b ) ( R - ( b - a ) )u In our example,l a = dept_name= building, budgetzand inst_dept is replaced byl (a

20、U b ) = ( dept_namding, budget )l ( R - ( b - a ) ) = ( ID, name, salary, dept_name )Third Normal Formu A relation schema R is in third normal form (3NF) if for all:a ® b in F+at least one of the following holds:l a ® b is trivial (i.e., b Í a)l a is a superkey for Rl Each attribute A

21、 in b a is contained in a candidate key for R.(NOTE: each attribute may be in a different candidate key)意思所有非主属性都完全依赖于码Goals of Normalizationu Let R be a relation scheme with a set F of functional dependencies.u Decide whether a relation scheme R is in “good” form.u In the case that a relation schem

22、e R is not in“good” form, decompose it into a set of relationschemeR1R2., Rn such thatl each relation scheme is in good forml the decomposition is a lossless-join decompositionl Preferably, the decomposition should be dependency preserving.u 3NFBCNF:消除主属性对侯选码的部分和传递函数依赖u 2NF3NFu 1NF2NF:消除非主属性对侯选码的传递函

23、数依赖:消除非主属性对侯选码的部分函数依赖在函数依赖的范围内,主要研究2NF,3NF,BCNF.其中3NF是业界标准,据统计,3NF的关系模式能解决90%左右的问题.但近几年,越来越要求关系模式达到BCNF,关系模式能达到BCNF,就实现了彻底的分离,消除和删除的异常,达到了完美的境界.所以,对了于数据库设计者来说,最重要的是3NF和BCNF两种范式.8.4Functional-dependency theoryFunctional-Dependency Theoryu We now consider the formal theory that tells us which function

24、al dependencies are implied logically by a given set of functional dependencies.u We then develop algorithms to generate losslessdecompositions into BCNF and 3NF and highernormal form.Closure of a Set of Functional Dependenciesu Given a set F set of functional dependencies, there are certain other f

25、unctional depenthat are logically implied by F.If A ® B andB ® C,l For e.g.:then we caninfer that A ® Cu The set of all functional depicallyimplied by F is the closure of F, we denote theclosure of F by F+.Closure of a Set of Functional Dependenciesu We can find F+, applyingthe closur

26、e of F, by repeatedlyArmstrongs Axioms:Í a, then a ®l if(reflexivity 自反律)l if a ® b, then g a ®g b(augmentation 增广律)l if a ®® g, then a ®g, and(transitivity 传递律)u These rules arel sound (do not generate any incorrect functional dependencies)l complete (generate all

27、 functional dependencies that hold).u R = (A, B, C, G, H, I) F = A ® BA ® C CG ® H CG ® IB ® Hu some members of F+l A ® H , by transitivity from A ® B and B ® Hl AG ® I by augmenting A ® C with G, to get AG ® CGand then transitivity with CG ® Il CG ® HI by augmenting CG ® I to infer CG ® CGI,and augmenting of CG ® H to infer CGI ® HI,and then transitivityProcedure for Computing F+u To compute the closure of