习题2.2.1Megatron777磁盘具有以下特性:1、有10个盘面,每个盘面有100000个磁道。2、磁道平均有1000扇区,每个扇区为1024字节。3、每个磁道的20%被用于间隙。4、磁盘旋转为10000转/min。5、磁头移动n个磁道所需要的时间是1+0.0002*nms。回答下列关于Megatron777的问题。a)磁盘的容量是多少?磁盘容量=10×100000×100×1024Bytes=109KBb)如果磁道是在直径3.5英寸的圆面上,那么一个磁道的扇区中的平均位密度是多少?位密度是指磁道上单位距离可记录的比特数,单位bpi(bits/inch)。我们选取中间磁道来计算平均位密度,中间磁道的直径为3.5inch/2,该磁道的周长为(3.5π/2)inch,扇区所占的周长是80%×(3.5π/2)inch。同时,每个磁道的容量是1000×1024×8bits所以一个磁道的扇区中的平均位密度是(1000×1024×8)bits/(80%×3.5π/2)inch=1861733.6bpic)最大寻道时间是多少?当磁头移动100000个磁道时,寻道时间最大1+0.0002×100000ms=21msd)最大旋转等待时间是多少?当所需要块的起点刚好从磁头下面越过,则要等待旋转一周的时间。最大旋转等待时间=(1r)/(10000r/min)=6ms/re)如果一个块是65536字节(即64扇区),一个块的传输时间是多少?磁头必须越过64个扇区和扇区之间的63个间隙。被64个扇区和63个间隙覆盖的圆弧的总度数为:360×80%×64/1000+360×20%×63/1000=22.968度传输时间是(22.968/360)×6ms=0.3828msf)平均寻道时间是多少?平均移动距离是移动整个磁盘的1/3,所以平均寻道时间为:(100000×1/3)×0.0002+1ms=7.67msg)平均旋转等待时间是多少?平均旋转等待时间为旋转半周所需的时间,由d)可知,为:6/2ms=3ms习题2.2.3证明如果我们将磁头从一个随机的柱面移动到另一个随机的柱面上,平均移动距离是扫描过整个磁盘的1/3(忽略因有限柱面数目产生的边际效应)。假设磁头起初以相同的概率被定为在8192个柱面的任一位置。如果是在柱面1或柱面8192,那么移动的平均磁道数是(1+2+···+8191)/8191,即大约4096磁道。如果是在柱面4096,即中间位置,则磁头移进或移出的可能性是相同的,而且无论移进还是移出,移动距离平均来说大约是总磁道数的四分之一,即2048磁道。计算表明,当磁头的初始位置从柱面1到柱面4094变化时,磁头需要移动的平均距离按二次方回升到4096,如上图所示。我们令r=8192,初始磁道x,平均行进距离y,则计算该二次函数可得y=(1/r)x2–x+r/2对所有初始位置进行积分∫0r(x2/r–x+r/2)dx=(x3/3r-x2/2+rx/2)|0r=r2/3所以平均行进距离=r2/3/r=r/3,即越过整个磁盘的1/3习题2.3.1假设我们正在为Megatron747磁盘调度I/O请求,磁头的初始位置在磁道32000,图2-9的请求已经产生。在下面两种情况下,每一种请求在何时完全得到服务?请求的柱面到达时间800004800014000104000020a)我们采用电梯算法(起初朝任一方向开始移动都是允许的)。请求的柱面完成时间计算说明800011.31+(32000-8000)/4000+4.3+0400017.61+(8000-4000)/4000+4.3+11.34800033.91+(48000-4000)/4000+4.3+17.64000041.21+(48000-40000)/4000+4.3+33.9b)我们采用先到达先服务调度。请求的柱面完成时间计算说明800011.31+(32000-8000)/4000+4.3+04800026.61+(48000-8000)/4000+4.3+11.3400042.91+(48000-4000)/4000+4.3+26.64000057.21+(40000-4000)/4000+4.3+42.9习题2.3.4如果我们要从一个柱面上读k个随机选定的块,在我们经过所有的块之前,平均来说我们必须绕着柱面走多远?设k个块的位置分别以圆周的分数标识x1,x2,...,xkx1,x2,...,xk均小于0—1之间某个t值的概率为tk,t的概率密度为ktk-1,t的平均值为∫01(ktk-1)tdt=k/(k+1)因此平均来说必须绕着柱面走k/(k+1)磁道长度。习题2.4.2如果我们在一个串末附加一个位作为该串各奇数位置的奇偶校验位,另一个位作为该串各偶数位置的奇偶位,我们就有了与一个串关联的两个奇偶位。对于下列位序列,找出这种方法计算的两个位。a)0011101110b)0000000000c)1010110110习题2.4.3假设我们使用例2.8中的镜像盘,每年故障率为5%,更换一个盘要花10小时。导致数据丢失的磁盘平均故障时间是多少?替换故障磁盘的过程花10小时,相当于一年的10/(24×365)=1/876由于我们假定磁盘的平均寿命是20年,拷贝过程中发生故障的可能性是5%×1/876=1/17520如果一个磁盘每20年年发生一次故障,那么两个磁盘之一平均10年发生一次故障。这些故障的每17520个中有一个导致数据丢失。换句话说,导致数据丢失的平均时间是10×17520=175200年。习题2.4.5假设我们使用RAID4级方案,有4个数据盘和一个冗余盘。与例2.9一样,假设块为单字节,如果数据盘的相应块如下,给出冗余盘的块。a)01010110,11000000,00101011和1011101100000110b)11110000,11111000,00111100和0100000101110101习题2.4.7采用和习题2.4.5一样的RAID4级方案,假设数据盘1有故障。在下列情况下恢复该磁盘的块:a)盘2至盘4的内容为01110110,11000000和00101011,同时冗余盘保存着1111001101101110b)盘2至盘4的内容为11110000,11111000和00110011,同时冗余盘保存着1000000110111010习题2.5.1假设一条记录有如下顺序的字段:一个长度为23的字符串,一个2字节整数,一个SQL日期,一个SQL时间(无小数点)。如果a)字段可以在任何字节处开始,b)字段必须在8的倍数的字节处开始,c)字段必须在4的倍数的字节处开始,这条记录占用多少字节?长度为23的字符串占用23字节,整数2字节,一个SQL日期10字节,一个SQL时间8字节。a)23+2+10+8=43字节b)24+8+16+8=56字节c)24+4+12+8=48字节习题2.5.2假设字段同习题2.5.1,但是记录有一个首部,它由两个4字节的指针和一个字符组成,对习题2.5.1中字段对齐的(a)至(c)3种情况,计算记录长度。假设字符为英文字符,则占1字节。首部长度为4+4+1a)4+4+1+43=52字节b)8+8+8+56=80字节c)4+4+4+48=60字节习题2.6.5现在,IP地址有4个字节,假设一个全球范围的地址系统中块地址由主机IP地址,1到10000之间的设备号以及各个设备号(假设为Megatron747磁盘)上的块地址组成。块地址需要多少字节?IP地址4字节21310000214,磁盘的设备id14位,设备号占用2字节有16384个柱面——柱面号2字节磁道号16位——2字节磁道内块号8位——1字节综上,块地址需要4+2+2+2+1=11字节习题2.6.7假设我们自动混写所有指针,所用的总时间是单独混写每一个指针所用总时间的一半。如果主存中一个指针被至少跟踪一次的概率为p,p为何值时自动混写比按需混写更有效?设c是单独混写每一个指针所用总时间。则自动混写总时间为c/2,按需混写的总时间是pc,根据题意,则得到关系pcc/2,从而p1/2习题2.6.9假设我们有4096字节块,块中存储200字节长的记录。块首部由一个偏移量表组成,如果2-19所示,它使用2字节长指针指向块内记录。通常,每天向每块插入两条记录,删除一条记录。删除记录必须使用一个“删除标记”代替它的指针,因为可能会有悬挂指针指向它。更明确地说,假设任何一天删除记录总发生在插入之前。如果刚开始时块是空的,多少天之后,不再有插入记录的空间?第一天,只做插入操作,插入两条记录,同时使用2个指针指向记录,总计增加了2×(2+200)=404字节。之后的每一天都先删除一条记录再增加两条记录,净增404-200=204字节由于(4096-404)/204=18···20,即在1+18=19天之后,块中剩余空间为20字节。在第20天,先删除一条记录,余下200+20=220字节空间,这时候只能够再插入一条记录(202字节)。习题2.7.1一个病人记录包含以下定长字段:病人的出生日期,社会保险号码,病人ID,每一个字段都是9字节长。它还有下列变长字段:姓名,住址和病史。如果记录内一个指针需要8字节,记录长度是一个2字节整数,不包括变长字段空间,这条记录需要多少字节?你可以假设不需要对字段进行对齐。定长字段需要3×9=27字节,记录长度2字节,指向“住址”的指针8字节,指向“病史”的指针8字节,所以一共需要27+2+8+8=45字节。习题2.7.3假设在习题2.7.1的病人记录上添加另外的可重复字段,表示胆固醇化验,每一次胆固醇化验需要一个24字节的日期和化验的整数结果。如果a)重复化验保存在记录中。b)化验存储在另外一个块中,记录中存储指向化验的指针。分别给出病人记录的格式。a)b)习题2.8.1关系数据库系统总是倾向于尽可能使用定长元组,给出这种优先考虑的三种理由。1)便于修改,当一个定长记录被修改时,对存储系统没有影响,因为我们知道它占用与修改前完全相同的空间。2)更有效地对记录进行搜索。3)对定长元组的删除和插入管理相对变长记录来说要简便。习题6.1.1假设数据库上的一致性约束是0≤A≤B。判断以下各事务是否保持一致性。a)B:=A+B;A:=A+B;不能保持一致性b)A:=B+1;B:=A+1;保持一致性c)A:=A+B;B:=A+B;保持一致性习题6.2.3下面是两个事务T和U的一系列日志记录:STARTU;U,A,10;STARTT;T,B,20;U,C,30;T,D,40;COMMITT;U,E,50;COMMITU;。请描述恢复管理器的行为,包括对磁盘和日志所做的改变,假设故障发生且出现在磁盘上的最后一条日志记录为:a)STARTT事务T、U未提交,要被撤销。向后扫描日志,遇到记录U,A,10,于是将A在磁盘上的值存为10。最后,记录ABORTU和ABORTT被写到日志中且日志被刷新。b)COMMITT事务T已提交,U未提交,要被撤销。向后扫描日志,首先遇到记录U,C,30,于是将C在磁盘上的值存为30。接着遇到记录U,A,10,并将A在磁盘上的值置为10。最后,记录ABORTU被写到日志中且日志被刷新。c)U,E,50事务T已提交,U未提交,要被撤销。向后扫描日志,首先遇到记录U,E,50,将E在磁盘上的值存为50。接着遇到记录U,C,30,于是将C在磁盘上的值存为30。再遇到记录U,A,10,并将A在磁盘上的值置为10。最后,记录ABORTU被写到日志中且日志被刷新。d)COMMITU事务T、U均被提交。什么都不做。习题6.2.7考虑如下日志记录序列:STARTS;S,A,60;COMMITS;STARTT;T,A,10;STARTU;U,B,20;T,C,30;STARTV;U,D,40;V,F,70;COMM