数据库课程设计之无损连接性.docx

课 程 设 计 说 明 书设计题目： 数据库课程设计 专 业： 计算机科学与技术 班级： 2010级5班 设 计 人： 王露 山 东 科 技 大 学2012年04月07 日山 东 科 技 大 学课 程 设 计 任 务 书计算机科学与技术 专业10级 班5班一、 课程设计题目：数据库课程设计二、 设计原始资料：数据库系统概论 java技术教程三、 设计应解决下列各主要问题：选择一种高级语言实现判别一个分解的无损连接性。输入：某一个关系模式的属性集、函数依赖集和该关系模式的一个分解。 输出：分解是否保持无损连接性。 题目要求:(1)按算法6.2和6.4实现 （2）能给出根据模式的分解形成初始表格 （3）给出根据每一个函数依赖表格的变化情况 （4）提供课程设计报告 四、 设计说明书应附有下列图纸：五、 命题发出日期：2012/03/14 设计应完成日期：2012/06/26设计指导教师（签章）：系主任（签章）：指导教师对课程的评语 指导教师（签章）： 年 月 日 摘要：本次课程设计，研究了如何判断输入的模式分解是否保持无损连接性，提示用户输入关系模式的属性集，函数依赖集以及模式分解，利用算法6.的表格法，运行程序，输出是否具有无损连接性。用java语言实现，在eclipse上运行，且只考虑了分解的无损连接性而没有考虑函数依赖的保持性。目录： 任务书-2 教师评语-3 摘要-4 题目要求-4 需求分析-4 程序设计-6 结果分析-15 实验总结-20 附录（使用说明）-21正文：1. 题目:选择一种高级语言实现判别一个分解的无损连接性 输入:某一个关系模式的属性集、函数依赖集和该关系模式的一个分解 输出:分解是否保持无损连接性 要求:(1)按算法6.2和6.4实现(P190) (2)能给出根据模式的分解形成初始表格 (3)给出根据每一个函数依赖表格的变化情况 (4)提供课程设计报告 2.需求分析1.关系模式R(U,F)，r=R1(U1,F1)，R2(U2,F2)， Rk(Uk,Fk)是R(U,F)的一组子集，若U1U2Uk=U，则称 r 是R(U,F)的一个分解(Decomposition)。分解有两个准则，无损连接性和函数依赖的保持性。无损连接性的定义为设关系模式R(U,F)， r=R1，R2，Rk是分解R所得的一组关系模式，对于R的满足F的任一个关系实例r，都有：成立。即r等于它在Ri上投影的自然连接，则称此分解为满足F的具有无损连接性的分解。2.分解的无损连接性判断定理6.4：设关系模式R(U,F)， r=R1，R2是R的一个分解，当且仅当U1U2U1-U2或 U1U2U2-U1F+时，则分解r具有无损连接性。3.算法6.2 判断分解r的无损连接性输入：R(U,F)，U=A1A2An ; r=R1，R2，Rk输出：如果r具有无损连接性，输出True，否则输出False。 (1) 构造一个n列k行的二维表T。若Aj Ri，则Tij=aj；否则Tij=bij。 (2) flag:=True; Do While Flag Flag:=False; For 每一个XYF Do For T中的任意两行tj，tm Do If tjX=tmX And tjYtmY Then EQUAY(tj，tm)；Flag:=True； (3) For T的每一行t Do If t=a1a2an Then Return(True)； Return(False).故根据定理6.2和6.4的算法和定理，可以得出判断关系模式的分解是否保持无损连接性的充分必要条件是U1U2U1-U2或 U1U2U2-U1F+时，则分解r具有无损连接性。 所以问题转变成为集合的并差问题，然后根据6.2算法再加以完善，就可以编写程序来实现这一功能了。当然，关系模式分解的另一个准则是函数依赖的保持性，这两个准则虽然没有什么直接的关系，却决定了一个关系模式可以达到哪一个范式，不能单一的进行讨论，都需要进行分析，现在，为简便起见，我们只讨论一个关系模式的分解是否保持着无损连接性，暂时不讨论其函数依赖的保持性3.程序设计 3.1粗略设计根据算法6.2，利用表格法进行判断，以下是表格法的详细步骤。算法：=R1,R2,.,Rk是关系模式R的一个分解，U=A1,A2,.,An，F=FD1,FD2,.,FDp，并设F是一个最小依赖集，记FDi为XiAlj，其步骤如下：建立一张n列k行的表，每一列对应一个属性，每一行对应分解中的一个关系模式。若属性AjUi，则在j列i行上真上aj，否则填上bij；对于每一个FDi做如下操作：找到Xi所对应的列中具有相同符号的那些行。考察这些行中li列的元素，若其中有aj，则全部改为aj，否则全部改为bmli，m是这些行的行号最小值。如果在某次更改后，有一行成为：a1,a2,.,an，则算法终止。且分解具有无损连接性，否则不具有无损连接性。对F中p个FD逐一进行一次这样的处理，称为对F的一次扫描。比较扫描前后，表有无变化，如有变化，则返回第步，否则算法终止。如果发生循环，那么前次扫描至少应使该表减少一个符号，表中符号有限，因此，循环必然终止。举例1：已知R，U=A,B,C，F=AB，如下的两个分解：1=AB,BC2=AB,AC判断这两个分解是否具有无损连接性。用无损连接的定理来解。方法一：因为ABBC=B，AB-BC=A，BC-AB=C所以BAF+，BCF+故1是有损连接。方法二：因为ABAC=A，AB-AC=B，AC-AB=C所以ABF+，ACF+故2是无损连接。下面举个例子来说明表格法【例】已知R，U=A,B,C,D,E，F=AC,BC,CD,DEC,CEA，R的一个分解为R1(AD)，R2(AB)，R3(BE)，R4(CDE)，R5(AE)，判断这个分解是否具有无损连接性。解：用判断无损连接的算法来解。 构造一个初始的二维表，若“属性”属于“模式”中的属性，则填aj，否则填bij。见表1. 表1. 根据AC，对上表进行处理，由于属性列A上第1、2、5行相同均为a1，所以将属性列C上的b13、b23、b53改为同一个符号b13（取行号最小值）。 表2 根据BC，对上表进行处理，由于属性列B上第2、3行相同均为a2，所以将属性列C上的b13、b33改为同一个符号b13（取行号最小值）。 表4. 根据CD，对上表进行处理，由于属性列C上第1、2、3、5行相同均为b13，所以将属性列D上的值均改为同一个符号a4。表5.根据DEC，对上表进行处理，由于属性列DE上第3、4、5行相同均为a4a5，所以将属性列C上的值均改为同一个符号a3。 表7 根据CEA，对上表进行处理，由于属性列CE上第3、4、5行相同均为a3a5，所以将属性列A上的值均改为同一个符号a1。 表7通过上述的修改，使第三行成为a1a2a3a4a5，则算法终止。且分解具有无损连接性。3.2详细设计（2000）要使本程序正确运行下去，需要解决的问题很多，下面，举个例子，来演示本程序的运行。【例】已知R，U=A,B,C,D,E，F=AC,BC,CD,DEC,CEA，R的一个分解为R1(AD)，R2(AB)，R3(BE)，R4(CDE)，R5(AE)，判断这个分解是否具有无损连接性。（1）首先，需要解决的问题是关系模式属性集，关系模式函数依赖集，模式分解的输入，此时需要有个用户说明书，告诉用户该怎么输入，输入什么，输入的东西是什么格式的，例如，必须输入U= A,B,C,D,E，定义一个字符型数组stringAttribute，InputStreamReader isra=new InputStreamReader(System.in); charstringAttribute=new char20; isra.read(stringAttribute);依次存入ABCDE五个属性。为了方便输出，定义一个字符型变量comma=, 还有定义一个字符型数组brace为左右大括号。其次定义字符数组dependence来储存输入的函数依赖，modecomposition来储存输入的模式分解。最后在用一个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(输入是否正确？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； 若是输入正确，则执行表格生成Table.java 见结果分析中的截图4.Package TableChangepublic class Table 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=new 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();fields2.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( DBFField.FIELD_TYPE_C);fields4.setFieldLength( 5);public class Functionpublic static void main(string args) /这个函数的目的是用来判断用输出表格中的数据Char data=new char35; /二维数组记录表格中的数据 System.out.print(属性 ); for(int temp=0;temp5;temp+) System.out.print( +stringAttributetemp); System.out.print(n); System.out.println(-);这样输出的结果就是 属性 A B C D E -表格的最左边是函数依赖dependence若“属性”属于“模式”中的属性，则填aj，否则填bijSystem.out.print(dependence0); for(int j=0;j5;j+) if(stringAttribute0=dependencej) /判断属性是否属于模式中的属性，若是，则填aj data0j=aj; else data0j=bij; /若不属于，则填bij for(int i=0;i5;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);这样执行输出结果为第二行ABC a1 a2 a3 b14 b15依次判断关系依赖集中的各个属性System.out.print(dependence1); for(int j=0;j5;j+) if(stringAttribute1=dependencej) data1j=aj; else data1j=bij; for(int i=0;i5;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.out.print(n); 同理，输出第三行CD b12 b22 a3 a4 b25System.out.print(dependence2); for(int j=0;j5;j+) if(stringAttribute2=dependencej) data2j=aj; else data2j=bij; for(int i=0;i5;i+) System.out.print( ); if(data2i=a) System.out.print(data2i); System.out.print(i); else System.out.print(data2i); System.out.print(2+i); System.out.print(n); DE b31 b32 b33 a4 a5在Function函数中直接输出，见图1. 图1.（3）改表对于每一个FDi做如下操作：找到Xi所对应的列中具有相同符号的那些行。考察这些行中li列的元素，若其中有aj，则全部改为aj，否则全部改为bmli，m是这些行的行号最小值。如果在某次更改后，有一行成为：a1,a2,.,an，则算法终止。且分解具有无损连接性，否则不具有无损连接性。对F中p个FD逐一进行一次这样的处理，称为对F的一次扫描。定义一个函数Cycleflag:=True; /指示布尔类型，若为True则停止循环 Do While Flag Flag:=False; For 每一个XYF Do For T中的任意两行tj，tm Do If tjX=tmX And tjYtmY Then EQUAY(tj，tm)；Flag:=True；二次循环时 表8. 二次循环后表格属性ABCDEABCa1a2a3a4b15CDb21b22a3a4b25DEb31b32b33a4a5Excel中打开change1.dbf可以看到，b14改为了a4.第三次循环时，表3. 表9.最终循环形成的表格属性ABCDEABCa1a2a3a4a5CDb21b22a3a4a5DEb31b32b33a4a5Excel中打开change2.dbf可以看到，b15改为了a5 b25改为了a5.（4）判断表是否循环终止比较扫描前后，表有无变化，如有变化，则返回上一步，否则算法终止。如果发生循环，那么前次扫描至少应使该表减少一个符号，表中符号有限，因此，循环必然终止。For T的每一行t Do If t=a1a2an Then Return(True)； Return(False).可以看到，表格的第一行变成了a1, a2,a3,a4,a5,该表格循环终止，且该分解具有无损连接性。故根据定理6.2和6.4的算法和定理，可以得出判断关系模式的分解是否保持无损连接性的充分必要条件是U1U2U1-U2或 U1U2U2-U1F+时，则分解r具有无损连接性。 所以问题转变成为集合的并差问题，然后根据6.2算法再加以完善，就可以编写程序来实现这一功能了。4.结果分析双击.exe可执行程序，以下显示的是初始结果截图图2. 图2.执行程序初始结果由于此程序是用来判断模式分解的无损连接性，下面我们举个例子来演示一下判断的过程及判断结果以数据库系统概论第四版 190页例5为例【例5】已知R,U=A,B,C,D,E , F=ABC,CD,DE , R的一个分解为R1(A,B,C) , R2(C,D) , R3(D,E)。分析：(1)首先构造初始表，如表2. 表10. 根据题目形成的初始表格属性ABCDEABCa1a2a3b14b15CDb21b22a3a4b25DEb31b32b33a4a5将题目中的关系模式属性集，函数依赖集，函数分解按照提示依次输入，运行程序，得到如下截图 图3. 提示将信息输入的截图为了确保用户输入的信息正确，此处会重新显示用户输入的信息，可以检查一下，然后会提示是否输入正确，如果正确，输入y即可以继续执行。 然后程序会运行一个可以生成dbf格式表格的程序,package TableChange里边有个Table.java，生成一个excel表格命名为Start.dbf ,以下是截图4和截图5 图4.TableChange 图5. 生成的excel表格Start.dbf(2)对表格进行修改（基于p189算法6.2无损连接性的判定定理） 对ABC,因各元祖的第一、二列没有相同的分量，所以表不改变。由CD可以把b14改为a4。程序继续执行,将Start.dbf改成Change1.dbf 图5.change1.dbf可以清楚地看到，图5中的b14变成了a4，（3）程序继续执行，又根据DE可以使b15，b25全改为a5.change1.dbf变为change2.dbf 图7.change2.dbf可以看到，b15，b25都变成了a5。（4）最后结果为图6所示，表中第一行成为a1，a2，a3，a4，a5，所以根据算法6.2 ，可以判断这个分解具有无损连接性。如图8. 图8.最终输出结果5实验报告总结 从拿到题目，到开始查资料，研究算法，这几个星期的时间过得还是很值的，因为涉及到建表和改表，用java编写有着明显的优势，因为可以生成dbf文件，实现起来比较简单。但是还是存在很多问题，本身这个算法比较复杂，虽然有个表格