范式

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

4、個或多個關(guān)系，分解前的函數(shù)依賴性在分解之后仍然存在，其具體情況看后面的BC范式。,函數(shù)依賴?yán)碚摷捌湓跀?shù)據(jù)庫設(shè)計合理性驗證中的應(yīng)用,已知：對于一個關(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的候選鍵；計算F的閉包F+，推理出其隱含的所有其

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

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

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

8、當(dāng)用Y → A替換X → A后得到的函數(shù)依賴集E，F(xiàn)和E不等價；對于一個函數(shù)依賴集，它的最小集，可以說是它的一個特征集；對于一個函數(shù)依賴集，它的最小集可能有多個，也即并不唯一；,完全函數(shù)依賴（Full FD）,定義: 對于函數(shù)依賴A → B，如果從A中去掉任一個屬性，依賴關(guān)系不再成立，那么 A → B是一個完全函數(shù)依賴。也說，B完全函數(shù)依賴于A；如果從A中去掉任一個屬性，依賴關(guān)系依然成立，那么就說 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部分的判定基于扇子陷進來思考； 13.20中有關(guān)5NF部分的判定基于裂口陷進來思考；,范式（Normal Forms）,就關(guān)系(Relation)的模式(Schema)合理性

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

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

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

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

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

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

16、不是主鍵屬性；但是滿足完備的3NF，因為SSN 屬性是候選鍵；.,Emp relation:,,,,,,,,,,fd1,fd2,,,,,,,,回答問題,關(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),一個關(guān)系滿足 BCNF，當(dāng)且僅當(dāng)：任一確定因子(determinant)都是候選鍵;對關(guān)系R, FD: X → Y ，那么X就為確定因子；3NF 和 BCNF 的差異在于：對FD: X → Y，如果Y是一個主鍵的成員屬性，并且X不是候選鍵，3NF對該情況是允許的；BCNF 要求X是一個候選鍵;BCNF 比 3NF 更嚴(yán)格.,不滿足BCNF的基本條件,滿足3NF而不滿足BCNF的情況非常少見；滿足

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

19、rvation） ；滿足3NF而不滿足BCNF的情況非常非常少見；就是存在，也可以不考慮；,無損聯(lián)接依賴Lossless-join Dependency,,無損聯(lián)接屬性是指，當(dāng)分解一個關(guān)系后，原有的關(guān)系能夠通過聯(lián)接運算復(fù)原； 無損聯(lián)接依賴是指，當(dāng)分解一個關(guān)系后，原有的關(guān)系能夠通過聯(lián)接運算復(fù)原，不會導(dǎo)致多余的元組（即行）出現(xiàn)； 要保障無損聯(lián)接屬性，有時有必要把一個關(guān)系分解成兩個以上的關(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)中的主鍵是哪一個呢？該關(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, 對應(yīng)的應(yīng)該分別是sName,oName。這是為什么呢？求解,答疑解答,brachNo-

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

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

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