1、CSEE in Hunan UniversityJin-Min Yang2016.06,Database Systems Design Part III : Normalization,,Database Design Flow Diagram,Individual Part 1,,Modeling(identify, deduce refine, abstract),,Individual Part n

2、,,,,,ER-diagram,Relations,Rational Relations,,User view 1,User view n,,,,Transformation,,Normalization,,Implement in particular DBMS,,Requirements,,Investigation, analysis, research,,,ViewStored procedure,,期望的關(guān)系模式特性,設(shè)

3、計(jì)得好的關(guān)系模式具有如下3個(gè)重要的屬性： 1) 一個(gè)關(guān)系是由一組邏輯上相關(guān)聯(lián)的屬性構(gòu)成，也就是說(shuō)，一個(gè)關(guān)系（relation）的屬性是指一個(gè)實(shí)體（Entity）或者一個(gè)關(guān)系（Relationship）的屬性. 2) 無(wú)損聯(lián)接性是指將一個(gè)關(guān)系分解成2個(gè)或多個(gè)關(guān)系之后，原有的關(guān)系能夠通過(guò)做自然聯(lián)接來(lái)復(fù)原，這一點(diǎn)是從關(guān)系實(shí)例來(lái)講的，也就是從元組來(lái)說(shuō)的，其具體情形看ER建模中的裂口陷進(jìn)和后面的5范式。 3) 依賴保留性指將一個(gè)關(guān)系分解成2

4、個(gè)或多個(gè)關(guān)系，分解前的函數(shù)依賴性在分解之后仍然存在，其具體情況看后面的BC范式。,函數(shù)依賴?yán)碚摷捌湓跀?shù)據(jù)庫(kù)設(shè)計(jì)合理性驗(yàn)證中的應(yīng)用,已知：對(duì)于一個(gè)關(guān)系R, 它的屬性集合A＝ (A1, A2, …, An)，有函數(shù)依賴集F = {X1 → Y1, …, Xj → Yj },其中Xk ? A，Yk ? A， 1? k ? i； 應(yīng)用：判斷函數(shù)依賴Xt→ Yt是否成立；判斷Xt是否是R的候選鍵；計(jì)算F的閉包F+，推理出其隱含的所有其

5、它函數(shù)依賴(放大)構(gòu)建F的最小集，也即特征集（精簡(jiǎn)）；.判斷兩個(gè)函數(shù)依賴集F和E是否等價(jià)；,解決問(wèn)題的關(guān)鍵策略,對(duì)于屬性集合 X， Xk ? A, 在函數(shù)依賴集F下的X的閉包X+ : 是指使用F能確定的所有屬性的集合；必須掌握的內(nèi)容：X+的計(jì)算；F+的計(jì)算；,Let X+ = X Repeat 如果F中有某個(gè)FD，它的左邊是X+的子集. 添加該FD 的右邊的屬性到 X+. Until ( X+ 不發(fā)生改變 o

6、r X+ 包含了R得所有屬性),判斷屬性集Xk是否是R的候選鍵的方法,對(duì)于關(guān)系R，它的屬性集合A，函數(shù)依賴集F，對(duì)于屬性集合 Xk， Xk ? A： 如果 Xk+ = A；然后計(jì)算Xk的所有真子集的閉包，如果它們都不等于A；那么Xk是R的候選鍵，否則不是；,兩個(gè)函數(shù)依賴集F和E 的等價(jià)性,對(duì)于兩個(gè)函數(shù)依賴集F和E，如果E中的每一個(gè)函數(shù)依賴都在F+中，那么就說(shuō)F覆蓋E；F覆蓋E 的判定方法：對(duì)E中的每一個(gè)函數(shù)依賴X →

7、Y ，基于F，計(jì)算X＋，然后檢查Y是否在X+中；如果全部成立，那么F覆蓋E；如果 F覆蓋E， F也覆蓋E，那么就說(shuō)E和F等價(jià)( equivalent）；F和E等價(jià)，那么E+ = F+.,函數(shù)依賴集的最小集（縮減函數(shù)依賴，減煉的過(guò)程）,對(duì)函數(shù)依賴集F，如果滿足如下三個(gè)條件，那么它就是最小集：F中的每一個(gè)函數(shù)依賴X → Y，Y只含一個(gè)屬性；.F的任意真子集，都與F不等價(jià)；對(duì)F中的任意函數(shù)依賴X → A，設(shè)X的真子集Y，對(duì)于F，

8、當(dāng)用Y → A替換X → A后得到的函數(shù)依賴集E，F(xiàn)和E不等價(jià)；對(duì)于一個(gè)函數(shù)依賴集，它的最小集，可以說(shuō)是它的一個(gè)特征集；對(duì)于一個(gè)函數(shù)依賴集，它的最小集可能有多個(gè)，也即并不唯一；,完全函數(shù)依賴（Full FD）,定義: 對(duì)于函數(shù)依賴A → B，如果從A中去掉任一個(gè)屬性，依賴關(guān)系不再成立，那么 A → B是一個(gè)完全函數(shù)依賴。也說(shuō)，B完全函數(shù)依賴于A；如果從A中去掉任一個(gè)屬性，依賴關(guān)系依然成立，那么就說(shuō) B部分函數(shù)依賴于A；例

9、子:eno → ename (完全FD)eno, ename → salary, title (部分 FD, 只依賴eno)eno, pno → hours, resp (完全 FD),作業(yè),13.16－13.20；其中13.19中有關(guān)4NF部分的判定基于扇子陷進(jìn)來(lái)思考； 13.20中有關(guān)5NF部分的判定基于裂口陷進(jìn)來(lái)思考；,范式（Normal Forms）,就關(guān)系(Relation)的模式(Schema)合理性

10、而言，可從5個(gè)層面來(lái)檢測(cè)關(guān)系是否會(huì)存在有潛在的冗余和更新異常。當(dāng)達(dá)到第5個(gè)層面時(shí)，則不會(huì)有潛在的冗余和更新異常.共有6個(gè)范式: 1NF, 2NF, 3NF, BCNF ( Boyce-Codd) , 4NF, 5NF;特征：6個(gè)范式中，后面范式比前面范式更嚴(yán)格；比如, 3NF 比 2NF更嚴(yán)格，它對(duì)關(guān)系(Relation)的模式(Schema)，相對(duì)于2NF，能夠更進(jìn)一步去除冗余和操作異常。,第一范式（First Norm

11、al Form ）(1NF),一個(gè)關(guān)系，對(duì)它的任意元組，其所有屬性的取值都是原子型(atomic)時(shí)，就說(shuō)它滿足第一范式。也就是說(shuō)，滿足1NF的關(guān)系，它的任意元組的任意屬性的取值不能是多個(gè)值的集合（即為多值屬性），或者是元組的集合；在關(guān)系型DBMS中，1NF 是基本要求.不滿足1NF的關(guān)系是一個(gè)不規(guī)范(unnormalized)的關(guān)系.,使一個(gè)不滿足1NF的關(guān)系滿足1NF的處理方法,1) 拆分(Splitting)法： 把一個(gè)不滿

12、足1NF的關(guān)系R拆分成2個(gè)關(guān)系R1和R2：關(guān)系R1：由R中滿足1NF的屬性構(gòu)成；關(guān)系R2：由R1的主鍵屬性和R中不滿足1NF的屬性構(gòu)成，重新確立R2的主鍵；R1的主鍵肯定是R2的主鍵的構(gòu)成部分，對(duì)否？為什么R2中要包含R1的主鍵屬性？ 2) 膨脹(Flattening )方法：把一行擴(kuò)展成多行，重新確立關(guān)系的主鍵.,注意：拆分后的表，要重新確立其主鍵！,拆分法,膨脹法,膨脹后的表，要重新確立其主鍵！,第二范式( Second

13、 Normal Form) (2NF),一個(gè)關(guān)系R滿足2NF，當(dāng)且僅當(dāng)：滿足1NF；它的所有非主鍵屬性都完全函數(shù)依賴于它的主鍵；,Second Normal Form (2NF),對(duì)于不滿足2NF的關(guān)系R，進(jìn)行拆分：對(duì) 違背2NF的FD X → Y : 計(jì)算 X+； 將關(guān)系R 拆分成： R1 = X+ 和 R2 = (R - X+) U X 注意： X 是R的主鍵屬性

14、集的真子集.,Third Normal Form (3NF),3NF是基于傳遞依賴概念而來(lái)的. 傳遞依賴：是指函數(shù)依賴：A → C 是基于 FD： A → B 和FD： B → C推理出來(lái)的.一個(gè)關(guān)系R滿足3NF，當(dāng)且僅當(dāng)：滿足2NF；不存在非主鍵屬性傳遞依賴于它的主鍵；,Third Normal Form (3NF),處理方法：按照去除傳遞依賴的策略是拆分關(guān)系R：對(duì)于R中的所有傳遞依賴X → Y，構(gòu)建新關(guān)系Ri（X，Y）；

15、去除R中的屬性集Y；,更完備的2NF和3NF,前面的 2NF and 3NF 僅就關(guān)系的主鍵而言，其實(shí)還可以考慮所有的候選鍵（ candidate keys）完備的2NF:對(duì)關(guān)系R，滿足1NF；它的任意候選鍵X，其它不在X中的屬性都完全函數(shù)依賴于X；.完備的3NF:對(duì)關(guān)系R，滿足2NF；它的任意候選鍵X，對(duì)其它不在X中的屬性，不存在傳遞依賴于X情況；,更完備的3NF例子,根據(jù)3NF的定義，此例不滿足3NF，原因是SSN屬性

16、不是主鍵屬性；但是滿足完備的3NF，因?yàn)镾SN 屬性是候選鍵；.,Emp relation:,,,,,,,,,,fd1,fd2,,,,,,,,回答問(wèn)題,關(guān)系R(A, B, C, D, E, F, G, H, I, J) ，函數(shù)依賴集F= { A,B → C ; A → D, E ; B → F ; F → G,H ; D → I,J }求出R的候選鍵；把R分解成第二范式和第三范式.,Boyce-Codd Normal F

17、orm (BCNF),一個(gè)關(guān)系滿足 BCNF，當(dāng)且僅當(dāng)：任一確定因子(determinant)都是候選鍵;對(duì)關(guān)系R, FD: X → Y ，那么X就為確定因子；3NF 和 BCNF 的差異在于：對(duì)FD: X → Y，如果Y是一個(gè)主鍵的成員屬性，并且X不是候選鍵，3NF對(duì)該情況是允許的；BCNF 要求X是一個(gè)候選鍵;BCNF 比 3NF 更嚴(yán)格.,不滿足BCNF的基本條件,滿足3NF而不滿足BCNF的情況非常少見；滿足

18、3NF而不滿足BCNF的基本條件是：至少有兩個(gè)或以上的組合性候選鍵；候選鍵之間存在交集，即它們之間有公共屬性。,BCNF versus 3NF,分解到BCNF時(shí)，不能保證函數(shù)依賴性保留（即dependency preservation 不能保證），即對(duì)FD: X → Y，BCNF分解后可能會(huì)出現(xiàn)X，Y分別位于不同的關(guān)系中，即失去了函數(shù)依賴約束；而對(duì)于3NF，就不會(huì)出現(xiàn)該情況，它能保持住函數(shù)依賴性（dependency prese

19、rvation） ；滿足3NF而不滿足BCNF的情況非常非常少見；就是存在，也可以不考慮；,無(wú)損聯(lián)接依賴Lossless-join Dependency,,無(wú)損聯(lián)接屬性是指，當(dāng)分解一個(gè)關(guān)系后，原有的關(guān)系能夠通過(guò)聯(lián)接運(yùn)算復(fù)原； 無(wú)損聯(lián)接依賴是指，當(dāng)分解一個(gè)關(guān)系后，原有的關(guān)系能夠通過(guò)聯(lián)接運(yùn)算復(fù)原，不會(huì)導(dǎo)致多余的元組（即行）出現(xiàn)； 要保障無(wú)損聯(lián)接屬性，有時(shí)有必要把一個(gè)關(guān)系分解成兩個(gè)以上的關(guān)系.,4NF and 5NF in

20、 Practice,In practice, 4NF and especially 5NF are rare.在ER建模中，注意了Fan trap, 就能滿足4NF；在ER建模中，注意了Chasm trap, 就能滿足5NF；,4NF 答疑,老師，在書上第四范式給出的例子中BranchStaffOwner(branchNo, sName, cName)中的主鍵是哪一個(gè)呢？該關(guān)系有多值依賴如下：brachNo->>sNam

21、e, brachNo->>oName, 如果是這樣的，那么它的主鍵應(yīng)該就是branchNo??？可是看書上它的關(guān)系表覺得應(yīng)該又是(sName, cName).而它滿足第四范式后就變成了BranchStaff(branchNo, sName)和BranchOwner(branchNO, oName)同樣看其關(guān)系表，主鍵也不是branchNo, 對(duì)應(yīng)的應(yīng)該分別是sName,oName。這是為什么呢？求解,答疑解答,brachNo-

22、>>sName是一對(duì)多關(guān)系, 即一個(gè)分支機(jī)構(gòu)有多個(gè)員工，brachNo->>oName也是一對(duì)多關(guān)系, 即一個(gè)分支機(jī)構(gòu)接待有多個(gè)房東。而實(shí)際業(yè)務(wù)需求中，要求關(guān)注員工和他負(fù)責(zé)接待的房東。剛好滿足扇子陷阱，因此拆分成BranchStaff(branchNo, sName)和BranchOwner(branchNO, oName)后還不夠，沒有精準(zhǔn)表達(dá)（sName, oName)之間的關(guān)系，即哪個(gè)員工負(fù)責(zé)接待

23、哪個(gè)房東，因此還需要StaffOwner(sName, cName)關(guān)系。當(dāng)然這里有一個(gè)假設(shè)，也就是branchNO, sName, oName分別充當(dāng)了實(shí)體分支機(jī)構(gòu)，員工，房東的主鍵。,答疑解答,在這個(gè)多值依賴branchNo->>sName中branchNo是鍵嗎？答：鍵是就關(guān)系而言的，基本準(zhǔn)則就是關(guān)系中的元組具有唯一性，唯一性又要根據(jù)語(yǔ)義來(lái)判斷，對(duì)BranchStaffOwner(branchNo,sName,cN

24、ame)而言，鍵自然是(branchNo,sName,cName)；,范式和ER建模,規(guī)范化和ER建模是兩個(gè)獨(dú)立的概念數(shù)據(jù)庫(kù)設(shè)計(jì)中，應(yīng)先執(zhí)行ER建模來(lái)設(shè)計(jì)數(shù)據(jù)庫(kù)，然后使用3范式來(lái)核查是否存在冗余隱患，并消除之；ER建模做得好，自然會(huì)滿足3范式；在理論上，也可通過(guò)范式驗(yàn)證理論來(lái)設(shè)計(jì)數(shù)據(jù)庫(kù)，其中牽涉標(biāo)識(shí)屬性，標(biāo)識(shí)函數(shù)依賴，任用范式化理論來(lái)拆分表；實(shí)際并不這樣做，而是做ER建模.對(duì)一個(gè)已經(jīng)上線的，設(shè)計(jì)得很差的數(shù)據(jù)庫(kù)進(jìn)行改造時(shí)，通常使用