0數(shù)據(jù)庫(kù)第七講lecture

1、范式 normal formu 范式是符合某一種級(jí)別的關(guān)系模式的集合u 關(guān)系數(shù)據(jù)庫(kù)中的關(guān)系必須滿足一定的要求。滿足不同程 度要求的為不同范式u 范式的種類：第一范式(1NF)第二范式(2NF)第三范式(3NF) BC范式(BCNF)第四范式(4NF)第五范式(5NF)u 對(duì)于各種范式之間的有u 5NFÌ4NFÌBCNF Ì3NF Ì2NF ÌlNF成立，如圖5.2所示。范式 normal formu 一個(gè)低一級(jí)范式的關(guān)系模式，通過(guò)模式分解可以轉(zhuǎn)換為若干個(gè)高一級(jí)范式的關(guān)系模式的集合，這種過(guò)程就叫規(guī)范化1NFu 1NF的定義:如果一個(gè)關(guān)系模式R的所

2、有屬性都是不可分的基本數(shù)據(jù)項(xiàng)，則R1NFu 第一范式是對(duì)關(guān)系模式的最起碼的要求。不滿足第一范式的數(shù)據(jù)庫(kù)模式不能稱為關(guān)系數(shù)據(jù)庫(kù)u 但是滿足第一范式的關(guān)系模式并不一定是一個(gè)好的關(guān)系模式Example: 關(guān)系模式 SLC(Sno, Sdept, Sloc, Cno, Grade)Sloc為學(xué)生住處，假設(shè)每個(gè)系的學(xué)生住在同一個(gè)地方u 函數(shù)依賴包括：(Sno, Cno) FSno SdeptGrade(Sno, Cno)Sno SlocPSdept(Sno, Cno) PSdept SlocSlocsnosdeptsloccnog1001計(jì)算機(jī)一號(hào)樓c001881001計(jì)算機(jī)一號(hào)樓c002781001計(jì)

3、算機(jī)一號(hào)樓c003901002英語(yǔ)二號(hào)樓c001851002英語(yǔ)二號(hào)樓c002801003計(jì)算機(jī)一號(hào)樓c003751003計(jì)算機(jī)一號(hào)樓c002821004管理三號(hào)樓c001751005管理三號(hào)樓c00188SLCSnoSdeptGradeCnoSlocu S-L-C的碼為(Sno, Cno)u S-L-C滿足第一范式。u 非主屬性Sdept和Sloc部分函數(shù)依賴于碼 SnoCnoSLCS不L是C不一是個(gè)一好個(gè)的好關(guān)的系關(guān)模系式模式1異常假設(shè)Sno'1006'，Sdept'英語(yǔ)'，Sloc'二號(hào)樓'的學(xué)生還未選課，因課程號(hào)是主屬性，因此該學(xué)生的SL

4、C。信息無(wú)法(2) 刪除異常假定某個(gè)學(xué)生本來(lái)只選修了c003課程這一門(mén)課?，F(xiàn)在因身體不適，他連c003號(hào)課程也不選修了。因課程號(hào)是主屬性，此操作將導(dǎo)致該學(xué)生信息的整個(gè)元組都要?jiǎng)h除。SLC不是一個(gè)好的關(guān)系模式(3) 數(shù)據(jù)冗余度大如果一個(gè)學(xué)生選修了10門(mén)課程，那么他的Sdept和Sloc值就要重復(fù)10次。(4) 修改復(fù)雜例如學(xué)生轉(zhuǎn)系，在修改此學(xué)生元組的Sdept值的同時(shí)，還可能需要修改住處（Sloc）。如果這個(gè)學(xué)生選修了K門(mén)課，則必須無(wú)遺漏地修改K個(gè)元組中全部Sdept、Sloc信息。SLCS不L是C不一是個(gè)一好個(gè)的好關(guān)的系關(guān)模系式l Sdept、 Sloc部分函數(shù)依賴于碼。u 解決方法l SLC

5、分解為兩個(gè)關(guān)系模式以消除這些部分函數(shù)依賴SC（Sno， Cno， Grade）SL（Sno， Sdept， Sloc）函數(shù)依賴圖：SLSCSdeptSnoSnoGradeCnoSloc關(guān)系模式SC的碼為（Sno，Cno）關(guān)系模式SL的碼為Sno這樣非主屬性對(duì)碼都是完全函數(shù)依賴2NFu 2NF的定義:若R1NF，且一個(gè)非主屬性完全函數(shù)依賴于碼，則R2NF。關(guān)鍵理解點(diǎn)：l 非主屬性l 碼：指侯選碼l 完全函數(shù)依賴和部分函數(shù)依賴?yán)篠LC(Sno, Sdept, Sloc, Cno, Grade) 1NFSLC(Sno, Sdept, Sloc, Cno, Grade) 2NFSC（Sno， Cno

6、， Grade） 2NF SL（Sno， Sdept， Sloc） 2NF2NFu 采用投影分解法將一個(gè)1NF的關(guān)系分解為多個(gè)2NF的關(guān)系，可以在一定程度上減輕原1NF關(guān)系中存在的異常、刪除異常、數(shù)據(jù)冗余度大、修改復(fù)雜等問(wèn)題。u 將一個(gè)1NF關(guān)系分解為多個(gè)2NF的關(guān)系，并不能完全消除 關(guān)系模式中的各種異常情況和數(shù)據(jù)冗余。u 如前例SL(SNO，SDEPT，SLOC)Î2NFu 1異常：l 新成立一個(gè)新系，該系在未招生前就安排好住在哪個(gè)樓，此 時(shí)由于SNO為空，而無(wú)法將該系及其組所SDEPT和SLOC的信息；u 2刪除異常：l 當(dāng)某個(gè)系的學(xué)生都畢業(yè)后，刪除學(xué)生信息時(shí)，也會(huì)把SLOC的

7、信息刪掉。u 因此，2NF并沒(méi)有徹底解決上述問(wèn)題，我們必須尋找更 好的關(guān)系模式。3NFu 3NF的定義若R3NF，則每一個(gè)非主屬性既不部分依賴于碼也不傳遞依賴于碼。如果R3NF，則R也是2NF。3NF雖然排除了非主屬性對(duì)碼部分依賴和傳遞依賴，但是，可能存在有主屬性對(duì)碼的部分依賴或傳遞依賴example2NF關(guān)系模式S-L(Sno,l 函數(shù)依賴：Sdept,Sloc)中SnoSdeptSdeptSloc 可得：傳遞SnoSloc，即S-L中存在非主屬性對(duì)3NF碼的傳遞函數(shù)依賴，S-函數(shù)依賴圖：S-LSdeptSnoSlocu 解決方法采用投影分解法，把S-L分解為兩個(gè)關(guān)系模式，以 消除傳遞函數(shù)依

8、賴：S-D（n，Sdept）D-L（Sdept，Sloc）S-D的碼為Sno，D-L的碼為Sdept。n 分解后的關(guā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 采用投影分解法將一個(gè)2NF的關(guān)系分解為多個(gè)3NF的關(guān)系，可以在一定程度上解決原2NF關(guān)系中存在的、刪除異常、數(shù)據(jù)冗余度大、修改復(fù)雜等問(wèn)題。異常一2NF關(guān)系分解為

9、多個(gè)3NF的關(guān)系后，仍然不能完全消除關(guān)系模式中的各種異常情況和數(shù)據(jù)冗余。u 3NF是一個(gè)可用的關(guān)系模式應(yīng)滿足的最低范式。u 思考:u 1 怎樣關(guān)系模式R 2NF?u 2 怎樣關(guān)系模式R 3NF?u 3 2NF和3NF主要研究了關(guān)系模式R中,哪兩種屬性組間的什么類型的函數(shù)依賴關(guān)系?22例u 關(guān)系模式STJ(S，T，J)中，S表示學(xué)生，T表示教師，J表示課程。u 每一教師只教一門(mén)課。u 每門(mén)課可以有若干教師教，u 一名學(xué)生只能在某位教師那里學(xué)習(xí)某門(mén)課程，某一學(xué)生選定某門(mén)課，就對(duì)應(yīng)一個(gè)固定的教師。由語(yǔ)義可得到如下的函數(shù)依賴。u (S，J)T;(S，T)J:TJ，u 該關(guān)系的碼有兩個(gè)（S，T）和(S，

10、J)?l 所以，S，T，J都是主屬性，它沒(méi)有非主屬性。所以該關(guān)系必然是3NF(即沒(méi)有任何非主屬性對(duì)碼傳遞依賴或部分依賴)u 當(dāng)以（S，T）作為主碼，如果知道T，J的值，而不知道S的值，則這樣的元組無(wú)法，產(chǎn)生異?，F(xiàn)象u 因此：一個(gè)3NF的關(guān)系模式也會(huì)產(chǎn)生異常等問(wèn)題u 可見(jiàn)，3NF雖然排除了非主屬性對(duì)碼的部分依賴和傳遞依賴，但是，可能其它問(wèn)題。BCNFu 關(guān)系模式R1NF，若XY且Y Í X時(shí)X必含，則RBCNF。關(guān)鍵理解點(diǎn)：123XYY ÍXX必含u 等價(jià)于：每一個(gè)決定屬性因素都包含碼25BCNFu 若RBCNFl 所有非主屬性對(duì)每一個(gè)碼都是完全函數(shù)依賴l 所有的主屬性對(duì)每一

11、個(gè)不包含它的碼，也是完全函數(shù)依賴l 沒(méi)有任何屬性完全函數(shù)依賴于非碼的任何一組屬性26BCNF充分u R BCNFR 3NF不必要u 因此：l 如果R3NF且每一個(gè)決定因素都包含碼，則RBCNF27例u 關(guān)系模式STJ(S，T，J)中，S表示學(xué)生，T表示教師，J表示課程。u 每一教師只教一門(mén)課。u 每門(mén)課可以有若干教師教，u 一名學(xué)生只能在某位教師那里學(xué)習(xí)某門(mén)課程，某一學(xué)生選定某門(mén)課，就對(duì)應(yīng)一個(gè)固定的教師。由語(yǔ)義可得到如下的函數(shù)依賴。u (S，J)T;(S，T)J:TJ，u 該關(guān)系的碼有兩個(gè)（S，T）和(S，J)u 該關(guān)系是3NF?是BCNF?BCNF-example關(guān)系模式C(Cno,Cnam

12、e,Grade)是3NF?n 分析：BCNF?n 關(guān)系模式C只有一個(gè)主碼Cno, 沒(méi)有任何屬性對(duì)碼Cno部門(mén)函數(shù)依賴或傳遞函數(shù)依賴。所以C3NFn 另外C中Cno是唯一的決定因素，當(dāng)然包含碼, 所以CBCNFBCNF-examplen 關(guān)系模式S(Sno,Sname,Sdept,Sage)n 假定S的碼是Sno和Sname，兩者都唯一標(biāo)識(shí)元組n 3NF?BCNF?：n 非主屬性Sdept,Sage不存在對(duì)碼的部分依賴或傳遞依賴，所以S3NFn 關(guān)系模式S中決定因素只有2個(gè)Sno和Sname，每一個(gè)決定因素都包含碼，所以S BCNF在關(guān)系模式STJ（S，T，J）中，S表示學(xué)生，T表示教師，J表示

13、課程。l 假設(shè)有函數(shù)依賴：(S，J)T，(S，T)J，TJl (S，J)和(S，T)都是候選碼l STJ屬于3NF嗎？屬于BCNF嗎？SSTJJTSTJ中的函數(shù)依賴STJ3NF沒(méi)有任何非主屬性對(duì)碼傳遞依賴或部分依賴STJBCNFT是決定因素，T不包含碼BCNF（續(xù)）解決方法：將STJ分解為二個(gè)關(guān)系模式：ST(S，T) BCNF， TJ(T，J) BCNFSTTJSTTJ沒(méi)有任何屬性對(duì)碼的部分函數(shù)依賴和傳遞函數(shù)依賴333NF與BCNF的關(guān)系充分不必要u R BCNFR 3NFu 如果R3NF，且R只有一個(gè)候選碼充分必要R BCNFR 3NF34BCNF與3NF的區(qū)別u BCNF不僅強(qiáng)調(diào)其它屬性對(duì)

14、碼的完全直接依賴，而且強(qiáng)調(diào)主屬性對(duì)碼的完全直接依賴。u 3NF只強(qiáng)調(diào)非主屬性對(duì)碼的完全直接依賴。353NF與BCNF的關(guān)系u 3NF和BCNF是在函數(shù)依賴的條件下對(duì)模式分解所能達(dá)到的分離程度的測(cè)度。l 一個(gè)模式中的關(guān)系模式如果都屬于BCNF，那么在函數(shù)依賴范疇內(nèi)，它已實(shí)現(xiàn)了徹底的分離，已消除和刪除的異常。3NF的“不徹底”性表現(xiàn)在可了能存在主屬性對(duì)碼的部分依賴和傳遞依賴。u 許多開(kāi)發(fā)者認(rèn)為，通常關(guān)系模式只要滿足第三范式的要求就可以使用了；當(dāng)然，滿足BCNF更好。但是，在有些情況下，我們必須尋找更高級(jí)的關(guān)系模式才能解決問(wèn)題。36l 指出R是否為3NF,是否為BCNF,為什么?BNOBNAMEAU

15、THORNO1C語(yǔ)言張三NO1C語(yǔ)言李四NO2C語(yǔ)言劉海NO2C語(yǔ)言王五NO3數(shù)據(jù)庫(kù)李四NO3數(shù)據(jù)庫(kù)王五練:設(shè)關(guān)系模式R(BNO,BNAME,AUTHOR)的屬性分別表示 書(shū)號(hào),書(shū)名和作者名.l 規(guī)定,每個(gè)書(shū)號(hào)只有一個(gè)書(shū)名,但不同書(shū)號(hào)可以有相同 書(shū)名,每本書(shū)可以有多個(gè)作者合寫(xiě),但每個(gè)作者參與編 著的書(shū)名應(yīng)該互不相同.u 問(wèn)題：l 寫(xiě)出R的侯選碼，主碼，主屬性，非主屬性?u 函數(shù)依賴：l BNO® BNAMEl （AUTHOR, BNAME）®BNOl （AUTHOR, BNO） ®BNAMEu 侯選碼為l (BNO,AUTHOR)和（ BNAME,AUTHOR)l

16、 BNO BNAME AUTHOR都是主屬性u(píng) 所以R是3NF，u R不是BCNF，因?yàn)锽NO® BNAME ，而B(niǎo)NO不是碼。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:消除主屬性對(duì)侯選碼的部分和傳遞函數(shù)依賴u 2NF3NFu 1NF2NF:消除非主屬性對(duì)侯選碼的傳遞函

23、數(shù)依賴:消除非主屬性對(duì)侯選碼的部分函數(shù)依賴在函數(shù)依賴的范圍內(nèi),主要研究2NF,3NF,BCNF.其中3NF是業(yè)界標(biāo)準(zhǔn),據(jù)統(tǒng)計(jì),3NF的關(guān)系模式能解決90%左右的問(wèn)題.但近幾年,越來(lái)越要求關(guān)系模式達(dá)到BCNF,關(guān)系模式能達(dá)到BCNF,就實(shí)現(xiàn)了徹底的分離,消除和刪除的異常,達(dá)到了完美的境界.所以,對(duì)了于數(shù)據(jù)庫(kù)設(shè)計(jì)者來(lái)說(shuō),最重要的是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