软件学院高级数据库考试攻略(金培权数据库系统实现)

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,University of Science and Technology of China,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,软件学院,2015,级高级数据库技术,(,金培权,-,数据库系统实现,),Homework 1,使用关系代数表达式实现下列,1,3,小题：,给定下面的关系：图书（图书号，书名，作者，单价，库存量），读者（读者号，姓名，工作单位，地址），借阅（图书号，读者号，借期，还期，备注）,注：还期为,NULL,表示该书未还。,检索读者,Rose,的工作单位和地址,检索读者,Rose,所借阅读书（包括已还和,未,还图书）的图书名和借期,Homework 1,检索未借阅图书的读者姓名,用,SQL,语言完成,4,8,小题：,查询语句结果可以计算如下：,1.,取,FROM,子句中列出的各个关系的元组的所有可能的组合,2.,将不符合,WHERE,子句中给出的条件的元组去掉,3.,如果有,GROUP BY,子句，则将剩下的元组按,GROUP BY,子句中给出的属性值分组,4.,如果有,HAVING,子句，则按照,HAVING,子句中给出的条件检查每一组，去掉不符合条件的组,5.,按照,SELECT,子句的说明，对于指定的属性和属性上的聚集（例如一组中的和）计算出结果元组,6.,按照,ORDER BY,子句中的属性列的值对结果元组进行排序,Homework 1,检索,Ullman,所写的书的书名和单价,SELECT,书名，单价,FROM,图书,WHERE,作者,=,Ullman,检索读者“李林”借阅未还的图书的图书号和书名,SELECT,图书号，书名,FROM,图书，读者，借阅,WHERE,图书,.,图书号,=,借阅,.,图书号,AND,读者,.,读者号,=,借阅,.,读者号,AND,读者,.,姓名,=,“李林”,AND,借阅,.,还期,=NULL,；,Homework 1,检索借阅图书数目超过,3,本的读者姓名,SELECT,姓名,FROM,读者，借阅,WHERE,借阅,.,读者号,=,读者,.,读者号,GROUP BY,读者号,HAVING COUNT(*)3;,Homework 1,检索没有借阅读者,“,李林,”,所借的任何一本书的读者姓名和读者号,SELECT,姓名，读者号,FROM,读者，借阅,WHERE,借阅,.,读者号,=,读者,.,读者号,AND,借阅,.,图书号,NOT IN,(SELECT,图书号,FROM,借阅，读者,WHERE,借阅,.,读者号,=,读者,.,读者号,AND,读者,.,姓名,=,李林,);,Homework 1,检索书名中包含“,Oracle,”的图书书名及图书号。,SELECT,图书号，书名,FROM,图书,WHERE,书名,LIKE%Oracle%;,Homework 1,现有如下关系模式：,R(A,，,B,，,C,，,D,，,E,，,F,，,G),，,R,上存在的函数依赖有：,AB,E,，,A,B,，,B,C,，,C,D,该关系模式满足第几范式吗,?,为什么,?,满足,1NF,范式。因为每一个属性值都只含有一个值，所以满足,1NF,。由于,R,的候选码为（,A,F,G,），而,B,、,C,、,D,局部依赖于,A,，所以不满足,2NF,。,如果将关系模式,R,分解为：,R1(A,，,B,，,E),，,R2(B,，,C,，,D),，,R3(A,，,F,，,G),，该数据库模式最高满足第几范式,?,最高满足,2NF,范式。因为对于模式,R2,，,B,C,，,C,D,，存在传递依赖，,所以不满足,3NF,。,Homework 1,请将关系模式,R,无损连接并且保持函数依赖地分解到,3NF,，要求给出具体步骤。,1.,求,R,上函数依赖集,F,的最小,FD,集合：,F=AB,E,A,B,B,C,C,D,；,U=A,B,C,D,E,先,将,R,保持函数依赖地分解到,3NF,。,2.,所有不在,F,中出现的属性组成,R(F,G),Homework 1,3.,对,F,按相同的左部分组,，并去除子集，得到：,p=R1,（,A,B,E,）；,R2,（,B,C,）；,R3(C,D),；,R(F,G),Homework 1,无损连接且保持函数依赖地分解到,3NF,Homework 1,5.,而,R,是,R4,的子集，所以从,p,中去掉,R,（,F,G,）,6.,p=R1,（,A,B,E,）,R2,（,B,C,），,R3,（,C,D,），,R4,（,A,F,G,）,为最终结果,Homework 1,Megatron 777,磁盘具有以下特性：,（,1,）,有,10,个盘面，每个盘面有,100000,个磁道；,（,2,）,磁道平均有,1000,个扇区，每个扇区为,1024,字节；,（,3,）,每个磁道的,20%,用于间隙；,（,4,）,磁盘旋转为,10000,转,/min,；,（,5,）,磁头移动,n,个磁道所需要的时间是,1+0.0002n ms,回答下列有关,Megatron 777,的问题：,磁盘的容量是多少？,Homework 1,如果磁道是在直径,3.5,英寸的圆面上，那么一个磁道的扇区中的平均位密度是多少？,我们选取中间磁道来计算平均位密度，中间磁道的直径为,3.5inch/2,，该磁道的周长为,(3.5,/2)inch,，扇区所占的周长是,80%,(3.5,/2)inch,。同时，每个磁道的容量是,1000,1024,8 bits,所以一个磁道的扇区中的平均位密度是,（,1000,1024,8,）,bits/(80%,3.5,/2)inch=1861733.6 bpi,最大寻道时间是多少？,最大寻道时间,1+0.0002*99 999=21ms,Homework 1,最大旋转等待时间是多少？,最大旋转等待时间：,60 x 1000ms/10 000=6ms,如果一个块是,65536,字节（即,64,扇区），一个块的传输时间是多少？,如果一个块是,65536,字节（即,64,扇区）,则磁头必须越过,64,个扇区以及扇区之间的,63,个间隙。需要的时间为：,64,（扇区,+,间隙）,-1,（间隙）,=64*,（,6/1000,）,-(6/1000)*0.2,=0.3828ms,Homework 1,平均寻道时间是多少？,平均旋转等待时间为：,6ms/2=3ms,平均旋转等待时间是多少？,1+0.0002*99999/3=7.67ms,Homework2,假设一条记录有如下顺序的字段：一个长度为,23,的字符串，一个,2,字节整数，一个,SQL,日期，一个,SQL,时间（无小数点）。,字段可在任何字节处开始？,一个,SQL,日期是,10,个字节的字符串，一个,SQL,时间是,8,个字节的字符串。,因为是任何字节处开始的，所以记录长度需要,23+2+10+8=43,字节。,Homework2,字段必须在,8,的倍数的字节处开始？,Homework2,字段必须在,4,的倍数的字节处开始？,因为必须是,4,的倍数，而长度为,23,的字符串需要分配,24,个字节，,2,字节的整数需要分配,4,个字节，,SQL,日期需要分配,12,个字节，,SQL,时间需要分配,8,个字节。所以：,24+4+12+8=48,字节。,Homework2,假设我们有,4096,字节块，块中存储,200,字节长的记录。块首部由一个偏移量表组成，它使用,2,字节长指针指向块内记录。通常，每天向每块插入两条记录，删除一条记录。删除记录必须使用一个“删除标记”代替它的指针，因为可能会有悬挂指针指向它。更明确地说，假设任何一天删除记录总发生在插入之前。如果刚开始时块是空的，多少天之后，不再有插入记录的空间？,第一天，只做插入操作，插入两条记录，同时使用,2,个指针指向记录，总计增加了,2,（,2+200,）,=404,字节。,Homework2,之后的每一天都先删除一条记录再增加两条记录，净增,404-200=204,字节。由于（,4096-404,）,/204=18,20,，即在,1+18=19,天之后，块中剩余空间为,20,字节。,在第,20,天，先删除一条记录，余下,200+20=220,字节空间，这时候只能够再插入一条记录（,202,字节）。,Homework2,一个病人记录包含以下定长字段：,病人的出生日期,，,社会保险号码,，,病人,ID,，每一个字段都是,9,字节长。它还有下列变长字段：,姓名，住址和病史,。如果记录内一个指针需要,8,字节，记录长度是一个,2,字节整数，不包含变长字段空间，这条记录需要多少字节？你可以假设不需要对字节进行对齐。,记录长度,出生日期,住址指针,病史指针,保险号码,病人,ID,姓名,住址,病史,Homework2,定长字段有,3,个，每个有,9,个字节长，所以需要,3,9=27,字节。,而记录的首部需要写入记录的长度和指向所有除第一个以外的变长字段起始处的指针。而记录长度,2,字节，指向“住址”的指针,8,字节，指向“病史”的指针,8,字节。所以一共需要,27+2+8+8=45,字节。,Homework3,Homework3,T(W)/V(W,a)=400/50=8,T(Y)/V(Y,c)=200/50=4,Homework3,T(W)*T(Y)=400*200=80000,T(Z)/3=100/3=33.3,T(W)/V(W,a)*V(W,b)=400/(50*40)=0.2,Homework3,T(W)/3*V(W,a)=400/,（,3*50,）,=2.67,T(X)*T(Y)/3=300*200/3=20000,Homework4,如果,R,和,S,都是非聚集的，似乎嵌套循环连将需要大约,T(R)T(S)/M,次磁盘,I/O,时间。,你怎样做才能明显好于这个代价？,假设,S(R)=S(S),每次迭代时读取,R,的元组塞满,M-1,块的,chunk,此时迭代次数为,T(R)*S(R)/(,M-1,),，那么总的磁盘,I/O,时间为,T(R),+T(R)*T(S)*S(R)/(,M-1,),。,近似为：,T(R)*T(S)*S(R)/M,.,例如：,1,个,block,中能存放,10,个元组,即,S(R)=1/10*block,，那么效率提高,10,倍。,Homework4,如果,R,和,S,中只有一个是非聚集的，你应该怎样执行嵌套循环连接？考虑两种情况：较大的关系是非聚集的和较小的事非聚集的,假定,R,为较小关系，,S,为较大关系,（,1,）,S,是非聚集的：,方案,1,：,For each loop:,Read M-1 blocks of R,Read all of S(using 1 block)+join,代价为：,B(R)+B(R)*T(S)/(M-1),Homework4,方案,2,：,Read M-1 blocks(M-1),1/S(S)tuples)of S,Read all of R(using 1 block)+join,代价为：,T(S)+B(R)*T(S)*S(S)/(M-1),选择代价最小的方案,（,2,）,R,是非聚集的,：,方案,1,：,For each loop:,Read M-1 blocks(M-1),1/S,（,R,）,tuples)of R,Read all of S(using 1 block)+join,代价为：,T(R)+T(R)*B(S)*S(R)/(M-1),Homework4,方案,2,：,For each loop:,Read M-1 blocks of S,Read all of R(using 1 block)+join,代价为：,B(S)+T(R)*B(S)/(M-1),选择代价最小的方案,比较,2,种情况下的最优代价,Homework4,假设这节中所描述算法的第二趟不需要所有的