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

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,软件学院,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,假设这节中所描述算法的第二趟不需要所有的,M,个缓冲区，因为子表数小于,M,。我们怎样通过使用额外的缓冲区来节省磁盘,I/O,？,原本我们需要将第一趟中得到的有序子表都写回磁盘，现在由于子表数小于,M,，可以将部分子表不写回，直接存储在内存缓冲区中，从而减少第二趟中的读子表操作，对于这样每块我们节省了,2,次,IO.,Test 1,假设某磁盘块参数如下：容量,36.7GB,传输速率,45MB/S,，旋转一圈时间,4ms,，平均寻道时间,5ms,，最小寻道时间,0.65ms,，一个磁道大小,180KB,。如果磁盘块大小,4KB,请回答下面问题：,（,1,）随机读取,1000,个磁盘块需要多少时间（,ms,）？,（,2,）假定（,1,）中的,1000,个磁盘块在单个磁道上连续存储，并且所有磁盘块存储在相邻的磁道上，此时读取这,1000,个磁盘块需要多少时间？,Test 1,Test 1,顺序读取,1000,个块,Test,B+-Tree,设定如下：,N:,记录数,n:B+-Tree,的阶，即节点所能容纳的键数,R:,读取一个磁盘块的旋转延迟,S:,读取一个磁盘块的寻道时间,T:,读取一个磁盘块的传输时间,m:,在内存的,m,条记录查找一条记录的时间,假设所有磁盘块都不在内存中,现在考虑压缩,B+-Tree,，假设每个节点的键值压缩,1,倍，即同样空间可压缩存储,2n,个键值和,2n+1,个指针。额外代价是解压缩，设每个压缩键值的内存解压时间为,c,，请问在一棵满的,n,阶压缩,B+-Tree,中查找给定记录地址的时间多少？（,n+1,可近似表示为,n,）,Test,2.,读块的时间,=R+S+T,3.,每块有,n,条记录，内存查找时间为,n,6.,增加了解压时间,2cn,，内存查找时间变为,2n,Final Exam,考试形式不同于往年，往年为开卷考试，今年为闭卷考试，总共,10,个判断题，及,4,个大题。,10,个判断，,30,分，个人感觉不容易，考点比较细，都是一些概念的判断，考的基本都是前三章的内容，请大家仔细复习。（,eg:ER,图是自下向顶设计的；关系模型中候选码一定要存在；一个只有,2,个属性的关系模式一定满足第三范式吗）,第一个大题考的是,PPT,第七章的内容，查询优化，老师上课讲的,PPT,上不全，只要把书上,P153,页,5.4.3,内容掌握即可完美答题。题目难度：一颗星,Final Exam,第二个大题考的是,PPT,第十章的内容，并发调度，考察冲突可串性及优先图的画法，掌握,PPT,即可。题目难度：一颗星,第三个大题考的是模糊查询结合,B+,树索引查询（问题是否能用,B+,树索引查询应用于模糊查询能否提高查询效率），金老师上课基本没提到模糊查询，因此需要自己结合,SQL,中模糊查询的原理和,B+,树索引查询原理解答。题目难度：四颗星,第四个大题考的是,PPT,第八章的内容，查询执行，主要考察优化的归并排序算法。题目难度：五颗星（题目见附录）,附第五题,我们想将关系,R,按某个字段排序。已知,R,的下列信息：,R,包含,100000,个元组，即,T(R)=100000.,一个磁盘块大小为,4000 bytes.,R,的元组大小为,400 bytes,，即,S(R),400.,关系,R,在磁盘上是非连续（,contiguous,）存放的,排序字段的大小为,32 bytes.,记录指针的大小为,8,bytes.,（普通硬盘读写一个块的时间都是,30t,，固态硬盘读取一个块的时间是,t,，写出一个块的时间为,50t,。,),考虑下面改进的归并排序算法。原来的两阶段归并排序的第一阶段是将排序后的整个元组写到,chunk,中，现在我们仅将排序后的,写出。第一阶段，我们在内存中将记录按,排序，当,记录填满内存时将其写到,chunk,中。第二阶段，读入各个,chunk,中的,并在内存中归并。通过记录指针,(recordPointer),我们可以读取记录的其它部分,(,从,R,的存储块中,),，并将排好序的记录写回磁盘。,附第五题,回答下面的问题：,（,1,）普通硬盘使用两阶段优化归并排序需要多少次磁盘,I/O,？（包括最后将排序文件写回磁盘的代价，用,t,表示）这个改进算法的,I/O,代价优于原来的归并排序算法吗？为什么？,（,2,）,SSD,使用两阶段优化归并排序需要多少次磁盘,I/O,？（包括最后将排序文件写回磁盘的代价，用,t,表示）这个改进算法的,I/O,代价优于原来的归并排序算法吗？为什么？,