數(shù)據(jù)庫規(guī)范化理論習題

1、規(guī)范化理論習題1. 解釋下列名詞：函數(shù)依賴、部分函數(shù)依賴、完全函數(shù)依賴、傳遞函數(shù)依賴、候選關鍵字、主關鍵字、全關鍵字、1NF、2NF、3NF、BCNF、多值依賴、4NF、連接依賴、5NF、最小函數(shù)依賴集、無損分解函數(shù)依賴：FD(function dependency)，設有關系模式R(U)，X，Y是U的子集， r是R的任一具體關系，如果對r的任意兩個元組t1,t2,由t1X=t2X導致t1Y=t2Y, 則稱X函數(shù)決定Y,或Y函數(shù)依賴于X，記為XY。XY為模式R的一個函數(shù)依賴。 部分函數(shù)依賴：即局部依賴，對于一個函數(shù)依賴WA，如果存在XW(X包含于W)有XA成立， 那么稱WA是局部依賴，否則稱W

2、A為完全依賴。 完全函數(shù)依賴：見上。傳遞函數(shù)依賴：在關系模式中，如果YX，XA，且XY（X不決定Y）， AX（A不屬于X）,那么稱YA是傳遞依賴。 候選關鍵字：設K為關系模式R（U，F(xiàn)）中的屬性或屬性集合。若KF U，則K稱為R的一個候選碼（Candidate Key），也稱作為候選關鍵字或碼。主關鍵字：若關系模式R有多個候選碼，則選定其中一個作為主關鍵字（Primary Key），有時也稱作為主碼。全關鍵字：若關系模式R整個屬性組都是碼，稱為全關鍵字（All Key）或全碼。1NF：第一范式。如果關系模式R的所有屬性的值域中每一個值都是不可再分解的值, 則稱R是屬于第一范式模式。如果某個數(shù)據(jù)

3、庫模式都是第一范式的，則稱該數(shù)據(jù)庫存模式屬于第一范式的數(shù)據(jù)庫模式。 第一范式的模式要求屬性值不可再分裂成更小部分，即屬性項不能是屬性組合和組屬性組成。 2NF：第二范式。如果關系模式R為第一范式，并且R中每一個非主屬性完全函數(shù)依賴于R的某個候選鍵， 則稱是第二范式模式；如果某個數(shù)據(jù)庫模式中每個關系模式都是第二范式的，則稱該數(shù)據(jù)庫模式屬于第二范式的數(shù)據(jù)庫模式。 (注：如果A是關系模式R的候選鍵的一個屬性，則稱A是R的主屬性，否則稱A是R的非主屬性。) 。3NF：第三范式。如果關系模式R是第二范式，且每個非主屬性都不傳遞依賴于R的候選鍵， 則稱R是第三范式的模式。如果某個數(shù)據(jù)庫模式中的每個關系模式

4、都是第三范式，則稱為3NF的數(shù)據(jù)庫模式。 BCNF：BC范式。如果關系模式R是第一范式，且每個屬性都不傳遞依賴于R的候選鍵，那么稱R是BCNF的模式。 多值依賴：設R(U)是屬性集U上的一個關系模式，X，Y，Z是U的子集，并且Z=U-X-Y, 用x,y,z分別代表屬性集X,Y，Z的值，只要r是R的關系，r中存在元組(x,y1,z1)和(x,y2,z2)時， 就也存在元組(x,y1,z2)和(x,y2,z1),那么稱多值依賴(MultiValued Dependency MVD) XY在關系模式R中成立。4NF：第四范式。設R是一個關系模式，D是R上的多值依賴集合。如果D中成立非平凡多值依賴XY

5、時， X必是R的超鍵，那么稱R是第四范式的模式。連接依賴：關系模式R(U)中，U是全體屬性集，X，Y，Z是U的子集，當且僅當R是由其在X，Y，Z上投影的自然連接組成時，稱R滿足對X，Y，Z的連接依賴。記為JD（X，Y，Z）。5NF：關于模式R中，當且僅當R中每個連接依賴均為R的候選碼所蘊涵時，稱R屬于5NF。最小函數(shù)依賴集：如果函數(shù)集合F滿足以下三個條件：(1)F中每個函數(shù)依賴的右部都是單屬性； (2)F中的任一函數(shù)依賴XA，其F-XA與F是不等價的；(3)F中的任一函數(shù)依賴XA，Z為X的子集，（F-XA）ZA與F不等價。則稱F為最小函數(shù)依賴集合，記為Fmin。無損分解：設R是一個關系模式，F(xiàn)

6、是R上的一個依賴集，R分解為關系模式的集合R1(U1),R2(U2), ,Rn(Un)。如果對于R中滿足F的每一個關系r，都有rR1(r) R2(r) Rn(r)則稱分解相對于F是無損連接分解（lossingless join decomposition），簡稱為無損分解，否則就稱為有損分解（lossy decomposition）。2. 現(xiàn)要建立關于系、學生、班級、學會等信息的一個關系數(shù)據(jù)庫。語義為：一個系有若干專業(yè)，每個專業(yè)每年只招一個班，每個班有若干學生，一個系的學生住在同一個宿舍區(qū)，每個學生可參加若干學會，每個學會有若干學生。描述學生的屬性有：學號、姓名、出生日期、系名、班號、宿舍區(qū)；

7、描述班級的屬性有：班號、專業(yè)名、系名、人數(shù)、入校年份；描述系的屬性有：系名、系號、系辦公室地點、人數(shù)；描述學會的屬性有：學會名、成立年份、地點、人數(shù)、學生參加某會有一個入會年份。 請寫出關系模式。 寫出每個關系模式的最小函數(shù)依賴集，指出是否存在傳遞依賴，在函數(shù)依賴左部是多屬性的情況下，討論函數(shù)依賴是完全依賴，還是部分依賴。 指出各個關系模式的候選關鍵字、外部關鍵字，有沒有全關鍵字。解：各關系模式如下：學生(學號,姓名,出生年月,系名,班級號,宿舍區(qū)) 班級(班級號,專業(yè)名,系名,人數(shù),入校年份) 系(系名,系號,系辦公地點,人數(shù)) 社團(社團名,成立年份,地點,人數(shù))  &

8、#160;   加入社團（社團名，學號，學生參加社團的年份） 學生(學號,姓名,出生年月,系名,班級號,宿舍區(qū)) “學生”關系的最小函數(shù)依賴集為： Fmin=學號姓名,學號班級號,學號出生年月,學號系名，系名宿舍區(qū) 以上關系模式中存在傳遞函數(shù)依賴，如:學號系名，系名宿舍區(qū) 候選鍵是學號,外部鍵是班級號,系名。 注意: 在關系模式中，如果YX，XA，且XY（X不決定Y）， A不屬于X,那么稱YA是傳遞依賴。 班級(班級號,專業(yè)名,系名,人數(shù),入校年份) “班級”關系的最小函數(shù)依賴集為： Fmin=(系名,專業(yè)名)班級號,班級號人數(shù)，班級號入校年份，班級號系名，班級號專業(yè)名 (

9、假設沒有相同的系，不同系中專業(yè)名可以相同) 以上關系模式中不存在傳遞函數(shù)依賴。 “(系名,專業(yè)名)班級號”是完全函數(shù)依賴。 候選鍵是(系名,專業(yè)名),班級號，外部鍵是系名。 系(系名,系號,系辦公地點,人數(shù)) “系”關系的最小函數(shù)依賴集為： Fmin=系號系名,系名系辦公地點,系名人數(shù)，系名系號 以上關系模式中不存在傳遞函數(shù)依賴 候選鍵是系名,系號 社團(社團名,成立年份,地點,人數(shù)) “社團”關系的最小函數(shù)依賴集為： Fmin=社團名成立年份,社團名地點,社團名人數(shù) 以上關系模式中不存在傳遞函數(shù)依賴。 候選鍵是社團名 加入社團（社團名，學號，學生參加社團的年份）“加入社團”關系的最小函數(shù)依賴

10、集為： Fmin=（社團名，學號）學生參加社團的年份 “（社團名，學號）學生參加社團的年份”是完全函數(shù)依賴。以上關系模式中不存在傳遞函數(shù)依賴。 候選鍵是（社團名，學號）。3. 設關系模式R(A，B，C，D)，函數(shù)依賴集FAC，CA，BAC，DAC，BDA。1) 求出R的候選碼；2) 求出F的最小函數(shù)依賴集；3) 將R分解為3NF，使其既具有無損連接性又具有函數(shù)依賴保持性。解：(1)根據(jù)函數(shù)依賴可得：屬性B、D、BD為L類(僅出現(xiàn)在F的函數(shù)依賴左部)。且在函數(shù)依賴的左部和右部均未出現(xiàn)的屬性為0。根據(jù)定理：對于給定的關系模式R及其函數(shù)依賴集F，若X(XR)是L類屬性，則X必為R 的任一候選碼的成員

11、。因此屬性B、D必為候選碼的成員。且它們的閉包為：BF+=ABC，D F+=ACD,BD F+=ABCD再根據(jù)推論：對于給定的關系模式R及其函數(shù)依賴集F，若X(XR)是L類屬性，且X F+包含了R的全部屬性，則X必為R的唯一候選碼。故BD是R的唯一候選碼。所以R的候選碼為BD。(2)將F中所有函數(shù)依賴的依賴因素寫成單屬性集形式：FAC，CA，BA，BC，DA，DC，BDAF中的BC可以從BA和AC推導出來，BC是冗余的，刪掉BC可得：FAC，CA，BA，DA，DC，BDAF中的DC可以從DA 和 AC推導出來，DC是冗余的，刪掉DC可得：FAC，CA，BA，DA，BDAF中的BDA可以從BA

12、和 DA推導出來，是冗余的，刪掉BDA可得：FAC，CA，BA，DA 所以F的最小函數(shù)依賴集FminAC，CA，BA，DA 。(3) 由于R中的所有屬性均在Fmin中都出現(xiàn)，對F按具有相同左部的原則分為：R1=AC，R2=BA，R3=DA。其中，U1=A，C，U2=B，A，U3=D，A，F(xiàn)1= F1U1AC，F(xiàn)2U2BA，F(xiàn)3U3DA。所以=R1(AC),R2(BA),R3(DA) 。4. 設關系模式R(A，B，C，D，E，F(xiàn))，函數(shù)依賴集FA BE，BCD，BEC，CDB，CEAF，CFBD，CA，DEF，求F的最小函數(shù)依賴集。解： 利用分解規(guī)則，將所有的函數(shù)依賴變成右邊都是單個屬性的函數(shù)依

13、賴，得F為：F A BE，BCD，BEC，CDB，CEA，CEF，CFB，CFD，CA，DE，DF 去掉F中多余的函數(shù)依賴A設ABE為冗余的函數(shù)依賴，則從F中去掉ABE，得：F1= BCD，BEC，CDB，CEA，CEF，CFB，CFD，CA，DE，DF計算(AB)F1+：設X(0)=AB計算X(1)：掃描F1中各個函數(shù)依賴，找到左部為AB或AB子集的函數(shù)依賴，因為找不到這樣的函數(shù)依賴。故有X(1)=X(0)=AB，算法終止。(AB)F1+= AB不包含E，故ABE不是冗余的函數(shù)依賴，不能從F中去掉。即：F1= A BE，BCD，BEC，CDB，CEA，CEF，CFB，CFD，CA，DE，DF

14、B設BCD為冗余的函數(shù)依賴，則從F1中去掉BCD，得：F2=A BE，BEC，CDB，CEA，CEF，CFB，CFD，CA，DE，DF計算(BC)F2+：設X(0)=BC計算X(1)：掃描F2中的各個函數(shù)依賴，找到左部為BC或BC子集的函數(shù)依賴，得到一個CA函數(shù)依賴。故有X(1)=X(0)A=BCA=ABC。計算X(2)：掃描F2中的各個函數(shù)依賴，找到左部為ABC或ABC子集的函數(shù)依賴，得到一個A BE函數(shù)依賴。故有X(2)=X(1)E=ABCE。計算X(3)：掃描F2中的各個函數(shù)依賴，找到左部為ABCE或ABCE子集的函數(shù)依賴，得到三個BEC，CEA和 CEF 函數(shù)依賴。故有X(3)=X(2

15、)CAF=ABCEF。計算X(4)：掃描F2中的各個函數(shù)依賴，找到左部為ABCEF或ABCEF子集的函數(shù)依賴，得到二個CFB和CFD 函數(shù)依賴。故有X(3)=X(2)BD=ABCDEF。因為X(3)=U，算法終止。(BC)F2+=ABCDEF包含D，故BCD是冗余的函數(shù)依賴，從F1中去掉。即：F2=A BE，BEC，CDB，CEA，CEF，CFB，CFD，CA，DE，DFC設BEC為冗余的函數(shù)依賴，從F2中去掉BEC，得：F3=A BE， CDB，CEA，CEF，CFB，CFD，CA，DE，DF計算(BE)F3+：設X(0)=BE計算X(1)：掃描F3中的各個函數(shù)依賴，找到左部為BE或BE子集

16、的函數(shù)依賴，因為找不到這樣的函數(shù)依賴。故有X(1)=X(0)=BE，算法終止。(BE)F3+= BE不包含C，故BEC不是冗余的函數(shù)依賴，不能從F2中去掉。即：F3=A BE， BEC，CDB，CEA，CEF，CFB，CFD，CA，DE，DFD設CDB為冗余的函數(shù)依賴，從F3中去掉CDB，得：F4=A BE，BEC，CEA，CEF，CFB，CFD，CA，DE，DF計算(CD)F4+：設X(0)=CD計算X(1)：掃描F4中的各個函數(shù)依賴，找到左部為CD或CD子集的函數(shù)依賴，得到三個CA，DE和 DF函數(shù)依賴。故有X(1)=X(0) AEF =ACDEF。計算X(2)：掃描F4中的各個函數(shù)依賴，

17、找到左部為ACDEF或ACDEF子集的函數(shù)依賴，得到四個CEA，CEF，CFB，CFD 函數(shù)依賴。故有X(2)=X(1)ABDF=ABCDEF。因為X(2)=U，算法終止。(CD)F4+=ABCDEF包含B，故CDB是冗余的函數(shù)依賴，從F3中去掉。即：F4=A BE，BEC，CEA，CEF，CFB，CFD，CA，DE，DFE設CEA為冗余的函數(shù)依賴，從F4中去掉CEA，得：F5=A BE，BEC，CEF，CFB，CFD，CA，DE，DF計算(CE)F5+：設X(0)=CE計算X(1)：掃描F5中的各個函數(shù)依賴，找到左部為CE或CE子集的函數(shù)依賴，得到一個CA函數(shù)依賴。故有X(1)=X(0)A=

18、ACE。計算X(2)：掃描F5中的各個函數(shù)依賴，找到左部為ACE或ACE子集的函數(shù)依賴，得到一個CEF函數(shù)依賴。故有X(2)=X(1)F=ACEF。計算X(3)：掃描F5中的各個函數(shù)依賴，找到左部為ACEF或ACEF子集的函數(shù)依賴，得到二個CFB和CFD 函數(shù)依賴。故有X(3)=X(2)BD=ABCDEF。因為X(3)=U，算法終止。(CE)F5+=ABCDEF包含A，故CEA是冗余的函數(shù)依賴，從F4中去掉。即：F5=A BE，BEC， CEF，CFB，CFD，CA，DE，DFF設CEF為冗余的函數(shù)依賴，從F5中去掉CEF，得：F6=A BE，BEC，CFB，CFD，CA，DE，DF計算(CE

19、)F6+：設X(0)=CE計算X(1)：掃描F6中的各個函數(shù)依賴，找到左部為CE或CE子集的函數(shù)依賴，得到一個CA函數(shù)依賴。故有X(1)=X(0)A=ACE。計算X(2)：掃描F6中的各個函數(shù)依賴，找到左部為ACE或ACE子集的函數(shù)依賴，因為找不到這樣的函數(shù)依賴。故有X(2)=X(1)=ACE，算法終止。(CE)F6+=ACE不包含F(xiàn)，故CEF不是冗余的函數(shù)依賴，不能從F5中去掉。即：F6=A BE，BEC，CEF，CFB，CFD，CA，DE，DFG設CFB為冗余的函數(shù)依賴，從F6中去掉CFB，得：F7=A BE，BEC，CEF，CFD，CA，DE，DF計算(CF)F7+：設X(0)=CF計算

20、X(1)：掃描F7中的各個函數(shù)依賴，找到左部為CF或CF子集的函數(shù)依賴，得到二個CFD和CA函數(shù)依賴。故有X(1)=X(0)AD=ACDF。計算X(2)：掃描F7中的各個函數(shù)依賴，找到左部為ACDF或ACDF子集的函數(shù)依賴，得到二個DE和DF函數(shù)依賴。故有X(2)=X(1)EF=ACDEF。計算X(3)：掃描F7中的各個函數(shù)依賴，找到左部為ACDEF或ACDEF子集的函數(shù)依賴，得到一個CEF函數(shù)依賴。故有X(3)=X(2)F=ACDEF= X(2)，算法終止。(CF)F7+=ACDEF不包含B，故CFB不是冗余的函數(shù)依賴，不能從F6中去掉。即：F7=A BE，BEC，CEF，CFB，CFD，C

21、A，DE，DFH設CFD為冗余的函數(shù)依賴，從F7中去掉CFD，得：F8=A BE，BEC，CEF，CFB，CA，DE，DF計算(CF)F8+：設X(0)=CF計算X(1)：掃描F8中的各個函數(shù)依賴，找到左部為CF或CF子集的函數(shù)依賴，得到二個CFB和CA函數(shù)依賴。故有X(1)=X(0)AB=ABCF。計算X(2)：掃描F8中的各個函數(shù)依賴，找到左部為ABCF或ABCF子集的函數(shù)依賴，得到一個A BE函數(shù)依賴。故有X(2)=X(1)E=ABCEF。計算X(3)：掃描F8中的各個函數(shù)依賴，找到左部為ABCEF或ABCEF子集的函數(shù)依賴，得到二個BEC和CEF函數(shù)依賴。故有X(3)=X(2)CF=

22、ABCEF = X(2)，算法終止。(CF)F7+= ABCEF不包含D，故CFD不是冗余的函數(shù)依賴，不能從F7中去掉。即：F8=A BE，BEC，CEF，CFB，CFD，CA，DE，DF 去掉F8中各函數(shù)依賴左邊多余的屬性（只檢查左部不是單個屬性的函數(shù)依賴）由于F8中各函數(shù)依賴左邊無多余的屬性，故：Fmin=ABE，BEC，CEF，CFB，CFD，CA，DE，DF5. 判斷下面的關系模式是不是BCNF，為什么？ 任何一個二元關系。 關系模式選課(學號，課程號，成績)，函數(shù)依賴集F(學號，課程號) 成績。關系模式R(A，B，C，D，E，F(xiàn))，函數(shù)依賴集FABC，BCA，BCDEF，EC。解：(1) 是BCNF。二元關系中或為全關鍵字，或為一個單屬性候選關鍵字。 (2) 是BCNF。關系模式中只有一個候選關鍵字。 (3) 不是BCNF。因為模式中存在候選關鍵字為AD、BCD和BE，顯然C對AD是部分依賴。 U1U2E U1U2AB U1U2U1U2=EAB=EA，EB U1U2U1U2F+ 該分解具備無損連接。 6. 設關系模式R(B，O，I，S，Q，D)，函數(shù)依賴集FSD，IS，ISQ，BQ。 求出R的主碼。 把R分解為BCNF，且具有無損連接性。解：(1) R的主關鍵字為IBO。 (2) FminSD，IS，IQ，BQ 令=BOISQD 由于R的關鍵字為I