數(shù)據(jù)庫課程設(shè)計之無損連接性

1、課 程 設(shè) 計 說 明 書設(shè)計題目： 數(shù)據(jù)庫課程設(shè)計 專 業(yè)： 計算機(jī)科學(xué)與技術(shù) 班級： 2010級5班 設(shè) 計 人： 王露 山 東 科 技 大 學(xué)2012年04月07 日山 東 科 技 大 學(xué)課 程 設(shè) 計 任 務(wù) 書計算機(jī)科學(xué)與技術(shù) 專業(yè)10級 班5班一、 課程設(shè)計題目：數(shù)據(jù)庫課程設(shè)計二、 設(shè)計原始資料：數(shù)據(jù)庫系統(tǒng)概論 java技術(shù)教程三、 設(shè)計應(yīng)解決下列各主要問題：選擇一種高級語言實現(xiàn)判別一個分解的無損連接性。輸入：某一個關(guān)系模式的屬性集、函數(shù)依賴集和該關(guān)系模式的一個分解。 輸出：分解是否保持無損連接性。 題目要求:(1)按算法6.2和6.4實現(xiàn) （2）能給出根據(jù)模式的分解形成初始表格

2、（3）給出根據(jù)每一個函數(shù)依賴表格的變化情況 （4）提供課程設(shè)計報告 四、 設(shè)計說明書應(yīng)附有下列圖紙：五、 命題發(fā)出日期：2012/03/14 設(shè)計應(yīng)完成日期：2012/06/26設(shè)計指導(dǎo)教師（簽章）：系主任（簽章）：指導(dǎo)教師對課程的評語 指導(dǎo)教師（簽章）： 年 月 日 摘要：本次課程設(shè)計，研究了如何判斷輸入的模式分解是否保持無損連接性，提示用戶輸入關(guān)系模式的屬性集，函數(shù)依賴集以及模式分解，利用算法6.的表格法，運(yùn)行程序，輸出是否具有無損連接性。用java語言實現(xiàn)，在eclipse上運(yùn)行，且只考慮了分解的無損連接性而沒有考慮函數(shù)依賴的保持性。目錄： 任務(wù)書-2 教師評語-3 摘要-4 題目要求-

3、4 需求分析-4 程序設(shè)計-6 結(jié)果分析-15 實驗總結(jié)-20 附錄（使用說明）-21正文：1. 題目:選擇一種高級語言實現(xiàn)判別一個分解的無損連接性 輸入:某一個關(guān)系模式的屬性集、函數(shù)依賴集和該關(guān)系模式的一個分解 輸出:分解是否保持無損連接性 要求:(1)按算法6.2和6.4實現(xiàn)(P190) (2)能給出根據(jù)模式的分解形成初始表格 (3)給出根據(jù)每一個函數(shù)依賴表格的變化情況 (4)提供課程設(shè)計報告 2.需求分析1.關(guān)系模式R(U,F)，r=R1(U1,F1)，R2(U2,F2)， Rk(Uk,Fk)是R(U,F)的一組子集，若U1ÈU2ÈÈUk=U，則稱 r 是R

4、(U,F)的一個分解(Decomposition)。分解有兩個準(zhǔn)則，無損連接性和函數(shù)依賴的保持性。無損連接性的定義為設(shè)關(guān)系模式R(U,F)， r=R1，R2，Rk是分解R所得的一組關(guān)系模式，對于R的滿足F的任一個關(guān)系實例r，都有：成立。即r等于它在Ri上投影的自然連接，則稱此分解為滿足F的具有無損連接性的分解。2.分解的無損連接性判斷定理6.4：設(shè)關(guān)系模式R(U,F)， r=R1，R2是R的一個分解，當(dāng)且僅當(dāng)U1ÇU2®U1-U2或 U1ÇU2®U2-U1ÎF+時，則分解r具有無損連接性。3.算法6.2 判斷分解r的無損連接性輸入：R(U,F)

5、，U=A1A2An ; r=R1，R2，Rk輸出：如果r具有無損連接性，輸出True，否則輸出False。 (1) 構(gòu)造一個n列k行的二維表T。若Aj ÎRi，則Tij=aj；否則Tij=bij。 (2) flag:=True; Do While Flag Flag:=False; For 每一個X®YÎF Do For T中的任意兩行tj，tm Do If tjX=tmX And tjY¹tmY Then EQUAY(tj，tm)；Flag:=True； (3) For T的每一行t Do If t=a1a2an Then Return(True)；

6、Return(False).故根據(jù)定理6.2和6.4的算法和定理，可以得出判斷關(guān)系模式的分解是否保持無損連接性的充分必要條件是U1ÇU2®U1-U2或 U1ÇU2®U2-U1ÎF+時，則分解r具有無損連接性。 所以問題轉(zhuǎn)變成為集合的并差問題，然后根據(jù)6.2算法再加以完善，就可以編寫程序來實現(xiàn)這一功能了。當(dāng)然，關(guān)系模式分解的另一個準(zhǔn)則是函數(shù)依賴的保持性，這兩個準(zhǔn)則雖然沒有什么直接的關(guān)系，卻決定了一個關(guān)系模式可以達(dá)到哪一個范式，不能單一的進(jìn)行討論，都需要進(jìn)行分析，現(xiàn)在，為簡便起見，我們只討論一個關(guān)系模式的分解是否保持著無損連接性，暫時不討論其函數(shù)依

7、賴的保持性3.程序設(shè)計 3.1粗略設(shè)計根據(jù)算法6.2，利用表格法進(jìn)行判斷，以下是表格法的詳細(xì)步驟。算法：=R1<U1,F1>,R2<U2,F2>,.,Rk<Uk,Fk>是關(guān)系模式R<U,F>的一個分解，U=A1,A2,.,An，F(xiàn)=FD1,FD2,.,FDp，并設(shè)F是一個最小依賴集，記FDi為XiAlj，其步驟如下： 建立一張n列k行的表，每一列對應(yīng)一個屬性，每一行對應(yīng)分解中的一個關(guān)系模式。若屬性Aj Ui，則在j列i行上真上aj，否則填上bij； 對于每一個FDi做如下操作：找到Xi所對應(yīng)的列中具有相同符號的那些行

8、?？疾爝@些行中l(wèi)i列的元素，若其中有aj，則全部改為aj，否則全部改為bmli，m是這些行的行號最小值。如果在某次更改后，有一行成為：a1,a2,.,an，則算法終止。且分解具有無損連接性，否則不具有無損連接性。對F中p個FD逐一進(jìn)行一次這樣的處理，稱為對F的一次掃描。 比較掃描前后，表有無變化，如有變化，則返回第步，否則算法終止。如果發(fā)生循環(huán)，那么前次掃描至少應(yīng)使該表減少一個符號，表中符號有限，因此，循環(huán)必然終止。舉例1：已知R<U,F>，U=A,B,C，F(xiàn)=AB，如下的兩個分解： 1=AB,BC 2=AB,AC判斷這兩個分解是否具有無損連接性。用無

9、損連接的定理來解。方法一：因為ABBC=B，AB-BC=A，BC-AB=C所以BA F+，BC F+故1是有損連接。方法二：因為ABAC=A，AB-AC=B，AC-AB=C所以AB F+，AC F+故2是無損連接。下面舉個例子來說明表格法【例】已知R<U,F>，U=A,B,C,D,E，F(xiàn)=AC,BC,CD,DEC,CEA，R的一個分解為R1(AD)，R2(AB)，R3(BE)，R4(CDE)，R5(AE)，判斷這個分解是否具有無損連接性。解：用判斷無損連接的算法來解。 構(gòu)造一個初始的二維表，若“屬性”屬于“模式”中的屬性，則填aj，否則填bi

10、j。見表1. 表1. 根據(jù)AC，對上表進(jìn)行處理，由于屬性列A上第1、2、5行相同均為a1，所以將屬性列C上的b13、b23、b53改為同一個符號b13（取行號最小值）。 表2 根據(jù)BC，對上表進(jìn)行處理，由于屬性列B上第2、3行相同均為a2，所以將屬性列C上的b13、b33改為同一個符號b13（取行號最小值）。 表4. 根據(jù)CD，對上表進(jìn)行處理，由于屬性列C上第1、2、3、5行相同均為b13，所以將屬性列D上的值均改為同一個符號a4。表5. 根據(jù)DEC，對上表進(jìn)行處理，由于屬性列DE上第3、4、5行相同均為a4a5，所以將屬性列C上的值均改為同一個符號a3。 表7 根據(jù)CEA，對上表進(jìn)

11、行處理，由于屬性列CE上第3、4、5行相同均為a3a5，所以將屬性列A上的值均改為同一個符號a1。 表7 通過上述的修改，使第三行成為a1a2a3a4a5，則算法終止。且分解具有無損連接性。3.2詳細(xì)設(shè)計（2000）要使本程序正確運(yùn)行下去，需要解決的問題很多，下面，舉個例子，來演示本程序的運(yùn)行?！纠恳阎猂<U,F>，U=A,B,C,D,E，F(xiàn)=AC,BC,CD,DEC,CEA，R的一個分解為R1(AD)，R2(AB)，R3(BE)，R4(CDE)，R5(AE)，判斷這個分解是否具有無損連接性。（1）首先，需要解決的問題是關(guān)系模式屬性集，關(guān)系模式函數(shù)依賴集，模式分解的輸入

12、，此時需要有個用戶說明書，告訴用戶該怎么輸入，輸入什么，輸入的東西是什么格式的，例如，必須輸入U= A,B,C,D,E，定義一個字符型數(shù)組stringAttribute，InputStreamReader isra=new InputStreamReader(System.in); charstringAttribute=new char20; isra.read(stringAttribute);依次存入ABCDE五個屬性。為了方便輸出，定義一個字符型變量comma=, 還有定義一個字符型數(shù)組brace為左右大括號。其次定義字符數(shù)組dependence來儲存輸入的函數(shù)依賴，modecompo

13、sition來儲存輸入的模式分解。最后在用一個isra.read(stringAttribute)輸出就好了。 （2）為了確保輸入的信息是否正確，依次輸出System.out.println(“您輸入的模式的屬性集為：”+new String(stringAttribute)；System.out.println(“您輸入的模式的屬性集為：”+new String(dependence)；System.out.println(“您輸入的模式的屬性集為：”+new String(modecomposition)；提示用戶檢查是否輸入正確System.out.print("輸入是否正確？

14、y/n"); Scanner scanner = new Scanner(System.in); char character = (char) scanner.nextByte(); if (scanner.equals('y') System.out.print("go on");continue label； else System.out.print("error");Break； 若是輸入正確，則執(zhí)行表格生成Table.java 見結(jié)果分析中的截圖4.Package TableChangepublic class Ta

15、ble public static void main( String args) throws DBFException, IOException DBFField field = new DBFField(); field.setName("Table"); / give a name to the field field.setDataType( DBFField.FIELD_TYPE_C); / and set its type field.setFieldLength( 5); / and length of the fieldDBFField fields=ne

16、w DBFField5;fields0 = new DBFField();fields0.setName("A");fields0.setDataType( DBFField.FIELD_TYPE_C);fields0.setFieldLength( 5);再依次fields1 = new DBFField();fields1.setName("B");fields1.setDataType( DBFField.FIELD_TYPE_C);fields1.setFieldLength( 5);fields2 = new DBFField();fields

17、2.setName("C");fields2.setDataType( DBFField.FIELD_TYPE_C);fields2.setFieldLength( 5);fields3 = new DBFField();fields3.setName("D");fields3.setDataType( DBFField.FIELD_TYPE_C);fields3.setFieldLength( 5); fields4 = new DBFField();fields4.setName("E");fields4.setDataType(

18、 DBFField.FIELD_TYPE_C);fields4.setFieldLength( 5);public class Functionpublic static void main(string args) /這個函數(shù)的目的是用來判斷用輸出表格中的數(shù)據(jù)Char data=new char35; /二維數(shù)組記錄表格中的數(shù)據(jù) System.out.print("屬性 " ); for(int temp=0;temp<5;temp+) System.out.print(" "+stringAttributetemp); System.out.p

19、rint("n"); System.out.println("-");這樣輸出的結(jié)果就是 屬性 A B C D E -表格的最左邊是函數(shù)依賴dependence若“屬性”屬于“模式”中的屬性，則填aj，否則填bijSystem.out.print(dependence0); for(int j=0;j<5;j+) if(stringAttribute0=dependencej) /判斷屬性是否屬于模式中的屬性，若是，則填aj data0j='aj' else data0j='bij' /若不屬于，則填bij for(

20、int i=0;i<5;i+) System.out.print(" "); if(data0i='a') System.out.print(data0i); System.out.print(i); else System.out.print(data0i); System.out.print("0"+i); System.out.print("n");這樣執(zhí)行輸出結(jié)果為第二行ABC a1 a2 a3 b14 b15依次判斷關(guān)系依賴集中的各個屬性System.out.print(dependence1); fo

21、r(int j=0;j<5;j+) if(stringAttribute1=dependencej) data1j='aj' else data1j='bij' for(int i=0;i<5;i+) System.out.print(" "); if(data1i='a') System.out.print(data1i); System.out.print(i); else System.out.print(data1i); System.out.print("1"+i); System.o

22、ut.print("n"); 同理，輸出第三行CD b12 b22 a3 a4 b25System.out.print(dependence2); for(int j=0;j<5;j+) if(stringAttribute2=dependencej) data2j='aj' else data2j='bij' for(int i=0;i<5;i+) System.out.print(" "); if(data2i='a') System.out.print(data2i); System.ou

23、t.print(i); else System.out.print(data2i); System.out.print("2"+i); System.out.print("n"); DE b31 b32 b33 a4 a5在Function函數(shù)中直接輸出，見圖1. 圖1.（3）改表對于每一個FDi做如下操作：找到Xi所對應(yīng)的列中具有相同符號的那些行。考察這些行中l(wèi)i列的元素，若其中有aj，則全部改為aj，否則全部改為bmli，m是這些行的行號最小值。如果在某次更改后，有一行成為：a1,a2,.,an，則算法終止。且分解具有無損連接性，否則不具有無損連接性

24、。對F中p個FD逐一進(jìn)行一次這樣的處理，稱為對F的一次掃描。定義一個函數(shù)Cycleflag:=True; /指示布爾類型，若為True則停止循環(huán) Do While Flag Flag:=False; For 每一個X®YÎF Do For T中的任意兩行tj，tm Do If tjX=tmX And tjY¹tmY Then EQUAY(tj，tm)；Flag:=True；二次循環(huán)時 表8. 二次循環(huán)后表格屬性ABCDEABCa1a2a3a4b15CDb21b22a3a4b25DEb31b32b33a4a5Excel中打開change1.dbf可以看到，b14改為

25、了a4.第三次循環(huán)時，表3. 表9.最終循環(huán)形成的表格屬性ABCDEABCa1a2a3a4a5CDb21b22a3a4a5DEb31b32b33a4a5Excel中打開change2.dbf可以看到，b15改為了a5 b25改為了a5.（4）判斷表是否循環(huán)終止比較掃描前后，表有無變化，如有變化，則返回上一步，否則算法終止。如果發(fā)生循環(huán)，那么前次掃描至少應(yīng)使該表減少一個符號，表中符號有限，因此，循環(huán)必然終止。For T的每一行t Do If t=a1a2an Then Return(True)； Return(False).可以看到，表格的第一行變成了a1, a2,a3,a4,a5,該表格循環(huán)終

26、止，且該分解具有無損連接性。故根據(jù)定理6.2和6.4的算法和定理，可以得出判斷關(guān)系模式的分解是否保持無損連接性的充分必要條件是U1ÇU2®U1-U2或 U1ÇU2®U2-U1ÎF+時，則分解r具有無損連接性。 所以問題轉(zhuǎn)變成為集合的并差問題，然后根據(jù)6.2算法再加以完善，就可以編寫程序來實現(xiàn)這一功能了。4.結(jié)果分析雙擊.exe可執(zhí)行程序，以下顯示的是初始結(jié)果截圖圖2. 圖2.執(zhí)行程序初始結(jié)果由于此程序是用來判斷模式分解的無損連接性，下面我們舉個例子來演示一下判斷的過程及判斷結(jié)果以數(shù)據(jù)庫系統(tǒng)概論第四版 190頁例5為例【例5】已知R<U,F

27、>,U=A,B,C,D,E , F=ABC,CD,DE , R的一個分解為R1(A,B,C) , R2(C,D) , R3(D,E)。分析：(1)首先構(gòu)造初始表，如表2. 表10. 根據(jù)題目形成的初始表格屬性ABCDEABCa1a2a3b14b15CDb21b22a3a4b25DEb31b32b33a4a5將題目中的關(guān)系模式屬性集，函數(shù)依賴集，函數(shù)分解按照提示依次輸入，運(yùn)行程序，得到如下截圖 圖3. 提示將信息輸入的截圖為了確保用戶輸入的信息正確，此處會重新顯示用戶輸入的信息，可以檢查一下，然后會提示是否輸入正確，如果正確，輸入y即可以繼續(xù)執(zhí)行。 然后程序會運(yùn)行一個可以生成dbf格式表格

28、的程序,package TableChange里邊有個Table.java，生成一個excel表格命名為Start.dbf ,以下是截圖4和截圖5 圖4.TableChange 圖5. 生成的excel表格Start.dbf(2)對表格進(jìn)行修改（基于p189算法6.2無損連接性的判定定理） 對ABC,因各元祖的第一、二列沒有相同的分量，所以表不改變。由CD可以把b14改為a4。程序繼續(xù)執(zhí)行,將Start.dbf改成Change1.dbf 圖5.change1.dbf可以清楚地看到，圖5中的b14變成了a4，（3）程序繼續(xù)執(zhí)行，又根據(jù)DE可以使b15，b25全改為a5.change1.dbf變?yōu)閏hange2.dbf 圖7.change2.dbf可以看到，b15，b25都變成了a5。（4）最后結(jié)果為圖6所示，表中第一行成為a1，a2，a3，a4，a5，所以根據(jù)算法6.2 ，可以判斷這個分解具有無損連接性。如圖8. 圖8.最終輸出結(jié)果5實驗報告總結(jié) 從拿到題目，到開始查資料，研究算法，這幾個星期的時間過得還是很值的，因為涉及到