1、习题 2.2.1 Megatron 777 磁盘具有以下特性：1、 有 10 个盘面，每个盘面有 100000 个磁道。2、 磁道平均有 1000 扇区，每个扇区为 1024 字节。3、 每个磁道的 20%被用于间隙。4、 磁盘旋转为 10000 转/min。5、 磁头移动 n 个磁道所需要的时间是 1+0.0002*n ms。回答下列关于 Megatron 777 的问题。a） 磁盘的容量是多少？磁盘容量 = 101000001001024Bytes = 109KBb） 如果磁道是在直径 3.5 英寸的圆面上，那么一个磁道的扇区中的平均位密度是多少？位密度是指磁道上单位距离可记录的比特数，单
2、位 bpi（bits/inch） 。我们选取中间磁道来计算平均位密度，中间磁道的直径为 3.5inch/2 ，该磁道的周长为(3.5/2)inch，扇区所占的周长是 80%(3.5/2)inch。同时，每个磁道的容量是100010248 bits所以一个磁道的扇区中的平均位密度是（100010248）bits/(80%3.5/2)inch = 1861733.6 bpic） 最大寻道时间是多少？当磁头移动 100000 个磁道时，寻道时间最大 1+0.0002100000 ms = 21msd） 最大旋转等待时间是多少？当所需要块的起点刚好从磁头下面越过，则要等待旋转一周的时间。最大旋转等待时
3、间 = （1r）/（10000r/min）= 6 ms/re） 如果一个块是 65536 字节（即 64 扇区） ，一个块的传输时间是多少？磁头必须越过 64 个扇区和扇区之间的 63 个间隙。被 64 个扇区和 63 个间隙覆盖的圆弧的总度数为：36080%64/1000+36020%63/1000 = 22.968 度传输时间是（22.968/360） 6 ms = 0.3828 msf） 平均寻道时间是多少？平均移动距离是移动整个磁盘的 1/3，所以平均寻道时间为：（1000001/3 ）0.0002+1 ms = 7.67 msg） 平均旋转等待时间是多少？平均旋转等待时间为旋转半周所
4、需的时间，由 d）可知，为：6/2 ms = 3 ms习题 2.2.3 证明如果我们将磁头从一个随机的柱面移动到另一个随机的柱面上，平均移动距离是扫描过整个磁盘的 1/3（忽略因有限柱面数目产生的边际效应） 。假设磁头起初以相同的概率被定为在 8192 个柱面的任一位置。如果是在柱面 1 或柱面8192，那么移动的平均磁道数是（1+2+8191）/8191，即大约 4096 磁道。如果是在柱面 4096，即中间位置，则磁头移进或移出的可能性是相同的，而且无论移进还是移出，移动距离平均来说大约是总磁道数的四分之一，即 2048 磁道。计算表明，当磁头的初始位置从柱面 1 到柱面 4094 变化时
5、，磁头需要移动的平均距离按二次方回升到 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 假设我们正在为 Megatron 747 磁盘调度 I/O 请求，磁头的初始位置在磁道32000，图 2-9 的请求已经产生。在下面两种情况下，每一种请求在何时完全得到服务？请求的柱面 到达时间8000
6、 048000 14000 1040000 20a）我们采用电梯算法（起初朝任一方向开始移动都是允许的） 。请求的柱面 完成时间 计算说明8000 11.3 1+(32000-8000)/4000+4.3+04000 17.6 1+(8000-4000)/4000+4.3+11.348000 33.9 1+(48000-4000)/4000+4.3+17.640000 41.2 1+(48000-40000)/4000+4.3+33.9b）我们采用先到达先服务调度。请求的柱面 完成时间 计算说明8000 11.3 1+(32000-8000)/4000+4.3+048000 26.6 1+(4
7、8000-8000)/4000+4.3+11.34000 42.9 1+(48000-4000)/4000+4.3+26.640000 57.2 1+(40000-4000)/4000+4.3+42.9习题 2.3.4 如果我们要从一个柱面上读 k 个随机选定的块，在我们经过所有的块之前，平均来说我们必须绕着柱面走多远？设 k 个块的位置分别以圆周的分数标识 x1，x2，.，xkx1，x2，.，xk 均小于 01 之间某个 t 值的概率为 tk，t 的概率密度为 ktk-1，t 的平均值为 01(ktk-1)tdt = k/(k+1)因此平均来说必须绕着柱面走 k/(k+1)磁道长度。习题 2
8、.4.2 如果我们在一个串末附加一个位作为该串各奇数位置的奇偶校验位，另一个位作为该串各偶数位置的奇偶位，我们就有了与一个串关联的两个奇偶位。对于下列位序列，找出这种方法计算的两个位。a) 0011101110b) 0000000000c) 1010110110习题 2.4.3 假设我们使用例 2.8 中的镜像盘，每年故障率为 5%，更换一个盘要花 10 小时。导致数据丢失的磁盘平均故障时间是多少？替换故障磁盘的过程花 10 小时，相当于一年的 10/（24365）= 1/876由于我们假定磁盘的平均寿命是 20 年，拷贝过程中发生故障的可能性是 5%1/876 = 1/17520如果一个磁盘
9、每 20 年年发生一次故障，那么两个磁盘之一平均 10 年发生一次故障。这些故障的每 17520 个中有一个导致数据丢失。换句话说，导致数据丢失的平均时间是1017520 = 175200 年。习题 2.4.5 假设我们使用 RAID 4 级方案，有 4 个数据盘和一个冗余盘。与例 2.9 一样，假设块为单字节，如果数据盘的相应块如下，给出冗余盘的块。a) 01010110，11000000，00101011 和 1011101100000110b) 11110000，11111000，00111100 和 0100000101110101习题 2.4.7 采用和习题 2.4.5 一样的 RA
10、ID 4 级方案，假设数据盘 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） 字段必须在
11、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+
12、4+48 = 60 字节习题 2.6.5 现在，IP 地址有 4 个字节，假设一个全球范围的地址系统中块地址由主机 IP 地址，1 到 10000 之间的设备号以及各个设备号（假设为 Megatron 747 磁盘）上的块地址组成。块地址需要多少字节？IP 地址 4 字节213柱面号 2 字节磁道号 16 位2 字节磁道内块号 8 位1 字节综上，块地址需要 4+2+2+2+1 = 11 字节习题 2.6.7 假设我们自动混写所有指针，所用的总时间是单独混写每一个指针所用总时间的一半。如果主存中一个指针被至少跟踪一次的概率为 p，p 为何值时自动混写比按需混写更有效？设 c 是单独混写每一个指
13、针所用总时间。则自动混写总时间为 c/2，按需混写的总时间是pc，根据题意，则得到关系 pcc/2，从而 p1/2习题 2.6.9 假设我们有 4096 字节块，块中存储 200 字节长的记录。块首部由一个偏移量表组成，如果 2-19 所示，它使用 2 字节长指针指向块内记录。通常，每天向每块插入两条记录，删除一条记录。删除记录必须使用一个“删除标记”代替它的指针，因为可能会有悬挂指针指向它。更明确地说，假设任何一天删除记录总发生在插入之前。如果刚开始时块是空的，多少天之后，不再有插入记录的空间？第一天，只做插入操作，插入两条记录，同时使用 2 个指针指向记录，总计增加了2（2+200） =
14、404 字节。之后的每一天都先删除一条记录再增加两条记录，净增 404-200 = 204 字节由于（4096-404）/204 = 1820，即在 1+18 = 19 天之后，块中剩余空间为 20 字节。在第 20 天，先删除一条记录，余下 200+20=220 字节空间，这时候只能够再插入一条记录（202 字节） 。习题 2.7.1 一个病人记录包含以下定长字段：病人的出生日期，社会保险号码，病人 ID，每一个字段都是 9 字节长。它还有下列变长字段：姓名，住址和病史。如果记录内一个指针需要 8 字节，记录长度是一个 2 字节整数，不包括变长字段空间，这条记录需要多少字节？你可以假设不需要
15、对字段进行对齐。定长字段需要 39=27 字节，记录长度 2 字节，指向“住址”的指针 8 字节，指向“病史”的指针 8 字节，所以一共需要 27+2+8+8 = 45 字节。习题 2.7.3 假设在习题 2.7.1 的病人记录上添加另外的可重复字段，表示胆固醇化验，每一次胆固醇化验需要一个 24 字节的日期和化验的整数结果。如果a) 重复化验保存在记录中。b) 化验存储在另外一个块中，记录中存储指向化验的指针。分别给出病人记录的格式。a）b）习题 2.8.1 关系数据库系统总是倾向于尽可能使用定长元组，给出这种优先考虑的三种理由。1） 便于修改，当一个定长记录被修改时，对存储系统没有影响，因
16、为我们知道它占用与修改前完全相同的空间。2） 更有效地对记录进行搜索。3） 对定长元组的删除和插入管理相对变长记录来说要简便。习题 6.1.1 假设数据库上的一致性约束是 0A 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 的一系列日志记录：;。请描述恢复管理器的行为，包括对磁盘和日志所做的改变，假设故障发生且出现在磁盘上的最后一条日志记录为：a） 事务 T、U 未提交，要被撤销。向后扫描日志，遇到记录，于是将 A 在
17、磁盘上的值存为 10。最后，记录和被写到日志中且日志被刷新。b） 事务 T 已提交，U 未提交，要被撤销。向后扫描日志，首先遇到记录 ，于是将 C在磁盘上的值存为 30。接着遇到记录，并将 A 在磁盘上的值置为 10。最后，记录被写到日志中且日志被刷新。c） 事务 T 已提交，U 未提交，要被撤销。向后扫描日志，首先遇到记录，将 E 在磁盘上的值存为 50。接着遇到记录，于是将 C 在磁盘上的值存为 30。再遇到记录，并将 A 在磁盘上的值置为 10。最后，记录被写到日志中且日志被刷新。d） 事务 T、U 均被提交。什么都不做。习题 6.2.7 考虑如下日志记录序列：;。假设我们在如下日志记录
18、中的某一条写入（主存）后立即开始一个非静止检查点：a) b) c) d) e) 对其中的每一个，说明：何时写入记录。对于每一个可能发生故障的时刻，为了找到所有可能未完成的事务，我们需要在日志中回溯多远。a）当前活跃的事务只有 S，日志记录为，所以在之后写入记录。如果故障发生在记录之后，那么我们可以扫描直到下一个记录停止。如果故障发生在之前，那么我们要回溯到。b) 当前活跃的事务只有 T，日志记录为，所以在之后写入记录。如果故障发生在记录之后，那么我们可以向后扫描直到下一个记录停止。如果故障发生在之前，那么我们要回溯到。c）当前活跃的事务有 T 和 U，日志记录为，所以在之后写入记录。如果故障发
19、生在记录之后，那么我们可以向后扫描直到下一个记录停止。如果故障发生在之前，那么我们要回溯到。d）当前活跃的事务有 T、U 和 V，日志记录为，所以在之后写入 记录。如果故障发生在记录之后，那么我们可以向后扫描直到下一个记录停止。如果故障发生在之前，那么我们要回溯到。e）当前活跃的事务有 T 和 V，日志记录为，所以在之后写入记录。如果故障发生在记录之后，那么我们可以向后扫描直到下一个记录停止。如果故障发生在之前，那么我们要回溯到。习题 6.3.2 使用习题 6.2.7 的数据，对该习题中(a)到(e) 的各个位置，回答：）何时能写入记录。）对每一个可能发生故障的时刻，为了找到所有可能未完成的事
20、务，我们需要在日志中向后看多远。请考虑记录在崩溃发生之前写入和未写入的两种情况。a）当前活跃的事务只有 S，日志记录为，所以在之前写入记录。如果崩溃发生在记录之后，那么在日志中只要回溯到。如果崩溃发生在记录之前，我们必须向后搜索到倒数第二个 START CKPT 记录并得到其活跃事务列表。在本题中没有前一检查点，因而必须一直走到日志的开头，确定没有已提交的事务。b) 当前活跃的事务只有 T，日志记录为，所以在之前写入记录。如果崩溃发生在记录之后，那么在日志中只要回溯到。如果崩溃发生在记录之前，我们必须向后搜索到倒数第二个 START CKPT 记录并得到其活跃事务列表。在本题中没有前一检查点，
21、因而必须一直走到日志的开头，确定已提交的事务只有 S，重复其动作 ，并在恢复后将记录 写入日志中。c）当前活跃的事务有 T 和 U，日志记录为，所以在之前写入记录。如果崩溃发生在记录之后，那么在日志中只要回溯到。如果崩溃发生在记录之前，我们必须向后搜索到倒数第二个 START CKPT 记录并得到其活跃事务列表。在本题中没有前一检查点，因而必须一直走到日志的开头，确定已提交的事务只有 S，重复其动作 ，并在恢复后将记录 和写入日志中。d）当前活跃的事务有 T、U 和 V，日志记录为，所以在之前写入 记录。如果崩溃发生在记录之后，那么在日志中只要回溯到。如果崩溃发生在记录之前，我们必须向后搜索到
22、倒数第二个 START CKPT 记录并得到其活跃事务列表。在本题中没有前一检查点，因而必须一直走到日志的开头，确定已提交的事务只有 S，重复其动作 ，并在恢复后将记录 、和写入日志中。e）当前活跃的事务有 T 和 V，日志记录为，所以在之前写入记录。如果崩溃发生在记录之后，那么在日志中只要回溯到。如果崩溃发生在记录之前，我们必须向后搜索到倒数第二个 START CKPT 记录并得到其活跃事务列表。在本题中没有前一检查点，因而必须一直走到日志的开头，确定已提交的事务有 S 和 U，重复其动作、 ，并在恢复后将记录和 写入日志中。习题 6.3.4 使用 redo 日志，重复习题 6.2.3。a)
23、 事务 U 和 T 都未提交，什么都不做，磁盘数据无变化，在日志中写入和记录并刷新日志。b）事务 T 已提交，为 B 写入值 20，为 D 写入值 40，在日志中写入记录并刷新日志。c）事务 T 已提交，为 B 写入值 20，为 D 写入值 40，在日志中写入记录并刷新日志。d）事务 T 和 U 已提交，为 A 写入值 10，为 B 写入值 20，为 C 写入值 30，为 D 写入值40。习题 6.4.2 下面是两个事务 T 和 U 的一系列日志记录：;。请描述恢复管理器的行为，包括对磁盘和日志所做的改变，假设故障发生且出现在磁盘上的最后一条日志记录为：a） 事务 U 未提交，回滚 U（从后往
24、前） ，A 的值置为 10。在日志中写入记录并刷新日志。b） 事务 T 已提交，重做 T，将 B 的值置为 21，D 的值置为 41。事务 U 未提交，回滚 U（从后往前） ，将 C 的值置为 30，A 的值置为 10。在日志中写入记录并刷新日志。c） 事务 T 已提交，重做 T，将 B 的值置为 21，D 的值置为 41。事务 U 未提交，回滚 U（从后往前） ，将 E 的值置为 50， C 的值置为 30，A 的值置为 10。在日志中写入记录并刷新日志。d） 事务 T 和 U 都已提交，重做 T、U ，将 A 的值置为 11，B 的值置为 21，C 的值置为31，D 的值置为 41，E 的
25、值置为 51。习题 6.4.4 考虑如下日志记录序列：; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ;。假设我们在如下日志记录中的某一条写入（主存）后立即开始一个非静止检查点：a) b) c) d) e) 对其中的每一个，说明：何时写入记录。对于每一个可能发生故障的时刻，为了找到所有可能未完成的事务，我们需要在日志中回溯多远。请考虑记录在崩溃发生以前写入和未写入的两种情况。a) 记录可以在之后任意位置出现。当前活跃的事务只有 S。如果崩溃发生在记录之后，那么在日志中只要回溯到。如果崩溃发生在 记录之前，我们必须向后搜索到倒数第二个START CKPT 记录并得到其活跃事务列表。在
26、本题中没有前一检查点，因而必须一直走到日志的开头，确定没有已提交的事务。b) 记录可以在之后任意位置出现。当前活跃的事务只有 T。如果崩溃发生在记录之后，那么在日志中只要回溯到。如果崩溃发生在记录之前，我们必须向后搜索到倒数第二个START CKPT 记录并得到其活跃事务列表。在本题中没有前一检查点，因而必须一直走到日志的开头，确定已提交的事务只有 S。c) 记录可以在 之后任意位置出现。当前活跃的事务有 T 和 U。如果崩溃发生在 记录之后，那么在日志中只要回溯到。如果崩溃发生在记录之前，我们必须向后搜索到倒数第二个 START CKPT 记录并得到其活跃事务列表。在本题中没有前一检查点，因
27、而必须一直走到日志的开头，确定已提交的事务只有 S。d) 记录可以在之后任意位置出现。当前活跃的事务有 T、U 和 V。如果崩溃发生在记录之后，那么在日志中只要回溯到。如果崩溃发生在记录之前，我们必须向后搜索到倒数第二个 START CKPT 记录并得到其活跃事务列表。在本题中没有前一检查点，因而必须一直走到日志的开头，确定已提交的事务只有 S。e) 记录可以在之后任意位置出现。当前活跃的事务有 T 和 V。如果崩溃发生在 记录之后，那么在日志中只要回溯到。如果崩溃发生在记录之前，我们必须向后搜索到倒数第二个 START CKPT 记录并得到其活跃事务列表。在本题中没有前一检查点，因而必须一直走到日志的开头，确定已提交的事务有 S 和 U。习题 6.5.1 如果在例 6.14 和例 6.15 中使用的是 redo 日志而不是 undo/redo 日志，那么：a） 日志会是怎样的？Dump completesb） 如果我们需要使用备份以及这一日志进行恢复，T 1 未提交的后果是什么？在 T1 提交之前转储已经完成，对于未提交事务 T1，它所做的修改不能到达磁盘。也就是说，A 和 B 不能变到新值。c） 恢复后数据库的状态是什么？数据库元素 A、B、C、和 D 分别是（1，2，6，4）习题 7.1.1 航班预订系统执行的一个事务 T1 执行以下步骤：
