数据库作业答案.

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) 磁盘的容量是多少？磁盘容量 =10 X 100000 X 100 X 1024Bytes = 109KBb) 如果磁道是在直径 3.5英寸的圆面上，那么一个磁道的扇区中的平均位密度是多少？位密度是指磁道上单位距离可记录的比特数，单位bpi (bits/i

2、nch )。我们选取中间磁道来计算平均位密度，中间磁道的直径为3.5inch/2，该磁道的周长为(3.5n /2)inch ，扇区所占的周长是 80%X (3.5 n /2)inch 。同时，每个磁道的容量是 1000X 1024 X 8 bits所以一个磁道的扇区中的平均位密度是(1000 X 1024 X 8) bits/ (80%X 3.5 n /2)inch =1861733.6 bpic) 最大寻道时间是多少？当磁头移动100000个磁道时，寻道时间最大 1+0.0002 X 100000 ms = 21msd) 最大旋转等待时间是多少？当所需要块的起点刚好从磁头下面越过，则要等待旋

3、转一周的时间。最大旋转等待时间=(1r) / (10000r/min ) = 6 ms/re) 如果一个块是65536字节(即64扇区)，一个块的传输时间是多少？磁头必须越过64个扇区和扇区之间的 63个间隙。被64个扇区和63个间隙覆盖的圆弧的总度数为：360X 80% X 64/1000+360 X 20%X 63/1000=22.968 度传输时间是(22.968/360 )X 6 ms = 0.3828 msf) 平均寻道时间是多少？平均移动距离是移动整个磁盘的1/3,所以平均寻道时间为：(100000 X 1/3) X 0.0002+1 ms =7.67 msg) 平均旋转等待时间是

4、多少？平均旋转等待时间为旋转半周所需的时间，由d)可知，为：6/2 ms = 3 ms平均移动距习题223证明如果我们将磁头从一个随机的柱面移动到另一个随机的柱面上, 离是扫描过整个磁盘的 1/3 (忽略因有限柱面数目产生的边际效应)起谢磁逍假设磁头起初以相同的概率被定为在8192个柱面的任一位置。如果是在柱面 1或柱面8192，那么移动的平均磁道数是(1+2+ +8191)/8191，即大约4096磁道。如果是在柱 面4096，即中间位置，则磁头移进或移出的可能性是相同的，而且无论移进还是移出，移 动距离平均来说大约是总磁道数的四分之一，即2048磁道。计算表明，当磁头的初始位置从柱面1到柱

5、面4094变化时，磁头需要移动的平均距离按二次方回升到4096，如上图所示。我们令r = 8192，初始磁道x，平均行进距离y,则计算该二次函数可得y = (1/r)x 2 -x + r/2对所有初始位置进行积分 /0r(x2/r -x + r/2)dx = (x 3/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的请求已经产生。在下面两种情况下，每一种请求在何时完全得到服务？请求的柱面到达时间80000

6、4800014000104000020a)我们采用电梯算法(起初朝任一方向开始移动都是允许的)请求的柱面完成时间计算说明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

7、.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的平均值为AI. A/ 0 (kt- )tdt = k/(k+1)因此平均来说必须绕着柱面走k/(k+1)磁道长度。习题2.4.2如果我们在一个串末附加一个位作为该串各奇数位置的奇偶校验位， 另一个位作

8、 为该串各偶数位置的奇偶位, 我们就有了与一个串关联的两个奇偶位。 对于下列位序列，找 出这种方法计算的两个位。a) 0011101110b) 0000000000c) 1010110110习题2.4譚 假设我们使用例2.8中的镜像盘，每年故障率为5%,更换一个盘要花 10小时。导致数据丢失的磁盘平均故障时间是多少？替换故障磁盘的过程花 10小时，相当于一年的 10/ (24X 365) = 1/876由于我们假定磁盘的平均寿命是20年，拷贝过程中发生故障的可能性是5% X 1/876 =1/17520如果一个磁盘每20年年发生一次故障，那么两个磁盘之一平均 10年发生一次故障。这些故 障的每

9、17520个中有一个导致数据丢失。换句话说，导致数据丢失的平均时间是10X 17520=175200 年。习题2.4.5假设我们使用 RAID 4级方案，有4个数据盘和一个冗余盘。与例2.9 一样，假设块为单字节，如果数据盘的相应块如下，给出冗余盘的块。a) 01010110, 11000000, 00101011 和 1011101100000110b) 11110000, 11111000, 00111100和 0100000101110101习题2.4.7采用和习题2.4.5 一样的RAID 4级方案，假设数据盘1有故障。在下列情况下恢 复该磁盘的块：a) 盘2至盘4的内容为011101

10、10, 11000000和00101011，同时冗余盘保存着1111001101101110b) 盘2至盘4的内容为11110000, 11111000和00110011,同时冗余盘保存着 10000001 10111010习题2.5.1|假设一条记录有如下顺序的字段：一个长度为23的字符串，一个2字节整数，一个SQL日期，一个SQL时间（无小数点）。如果a）字段可以在任何字节处开始，b）字段必须在8的倍数的字节处开始，c）字段必须在4的倍数的字节处开始，这条记录占用多少字节？长度为23的字符串占用23字节，整数2字节，一个SQL日期10字节，一个SQL时间8 字节。a）23+2+10+8 =

11、 43 字节b）24+8+16+8 = 56 字节c）24+4+12+8 = 48 字节习题2.5諾假设字段同习题 2.5.1，但是记录有一个首部，它由两个4字节的指针和一个字符组成，对习题2.5.1中字段对齐的（a ）至（。）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之间的设备号以及各个设备号（假设为Megatron 747磁盘）上的块地址组成。块

12、地址需要多少字节？IP地址4字节213 10000 柱面号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字节长指针指向块内

13、记录。通常，每天向每块插入两条记 录，删除一条记录。删除记录必须使用一个“删除标记”代替它的指针，因为可能会有悬挂 指针指向它。更明确地说，假设任何一天删除记录总发生在插入之前。如果刚开始时块是空的，多少天之后，不再有插入记录的空间？第一天，只做插入操作，插入两条记录，同时使用2个指针指向记录，总计增加了 2X（2+200） =404字节。之后的每一天都先删除一条记录再增加两条记录，净增404-200 = 204字节由于（4096-404） /204 = 1820,即在1 + 18 = 19天之后，块中剩余空间为 20字节。在第20天，先删除一条记录，余下200+20=220字节空间，这时候只

14、能够再插入一条记录（202字节）。习题2.7.1 个病人记录包含以下定长字段：病人的出生日期，社会保险号码，病人ID ,每一个字段都是9字节长。它还有下列变长字段：姓名，住址和病史。如果记录内一个指针需要8字节，记录长度是一个2字节整数，不包括变长字段空间，这条记录需要多少字节？你可以假设不需要对字段进行对齐。定长字段需要 3X 9=27字节，记录长度2字节，指向“住址”的指针 8字节，指向“病史” 的指针8字节，所以一共需要 27+2+8+8 = 45字节。习题2.7.3假设在习题2.7.1的病人记录上添加另外的可重复字段，表示胆固醇化验，每 次胆固醇化验需要一个24字节的日期和化验的整数结

15、果。如果a）重复化验保存在记录中。b）化验存储在另外一个块中，记录中存储指向化验的指针。分别给出病人记录的格式。a）拈诃曲匂希祠b)r:l曳吧沉土 碣伺习题2.8.1|关系数据库系统总是倾向于尽可能使用定长元组，给出这种优先考虑的三种理 由。1) 便于修改，当一个定长记录被修改时，对存储系统没有影响，因为我们知道它占用与修 改前完全相同的空间。2) 更有效地对记录进行搜索。3) 对定长元组的删除和插入管理相对变长记录来说要简便。习题假设数据库上的一致性约束是0 A B。判断以下各事务是否保持一致性。a) B:=A+B; A:=A+B;不能保持一致性b) A:=B+1; B:=A+1;保持一致性

16、c) A:=A+B; B:=A+B;保持一致性习题6.2.3下面是两个事务T和U的一系列日志记录： ;。请描述恢复管理器的行为，包括对磁盘和日志所做的改变，假设故障发生且出现在磁盘上的最后一条日志记录为：a) 事务T、U未提交，要被撤销。向后扫描日志，遇到记录，于是将A在磁盘上的值存为10。最后，记录和被写到日志中且日志被刷新。b) 事务T已提交，U未提交，要被撤销。向后扫描日志，首先遇到记录，于是将C在磁盘上的值存为 30。接着遇到记录，并将A在磁盘上的值置为 10。最后，记录 被写到日志中且日志被刷新。c) 事务T已提交，U未提交，要被撤销。向后扫描日志，首先遇到记录，将E在磁盘上的值存为

17、 50。接着遇到记录，于是将 C在磁盘上的值存为30。再遇到记录 ,并将A在磁盘上的值置为 10。最后，记录被写到日志中且日志被刷 新。d) 事务T、U均被提交。什么都不做。习题 6.2.7 考虑如下日志记录序列：;。假设我们在如下日志记录中的某一条写入（主存）后立即开始一个非静止检查点：a）b) T,A,10c) U,B,20d) U,D,40e) T,E,50对其中的每一个，说明：i何时写入END CKPT记录。ii对于每一个可能发生故障的时刻，为了找到所有可能未完成的事务，我们需要在日志中回溯多远。a) 当前活跃的事务只有 S,日志记录为START CKPT(S)，所以在COMMIT S

18、之后写入 END CKPT 记录。如果故障发生在END CKPT记录之后，那么我们可以扫描直到下一个START CKPT(S)记录停止。如果故障发生在 COMMIT S之前，那么我们要回溯到 START S。b) 当前活跃的事务只有 T,日志记录为START CKPT(T)，所以在COMMIT T之后写入 END CKPT 记录。如果故障发生在 END CKPT记录之后，那么我们可以向后扫描直到下一个STARTCKPT(T)记录停止。如果故障发生在 COMMIT T之前，那么我们要回溯到 START T。c) 当前活跃的事务有 T和U，日志记录为START CKPT(T,U)，所以在COMMI

19、T T之后 写入END CKPT记录。如果故障发生在 END CKPT记录之后，那么我们可以向后扫描直到下一个STARTCKPT(T,U)记录停止。如果故障发生在COMMIT T之前，那么我们要回溯到START T。d) 当前活跃的事务有 T、U和V,日志记录为START CKPT(T,U,V)，所以在COMMIT V 之后写入END CKPT记录。如果故障发生在 END CKPT记录之后，那么我们可以向后扫描直到下一个STARTCKPT(T,U,V)记录停止。如果故障发生在 COMMIT V之前，那么我们要回溯到 START T。e) 当前活跃的事务有 T和V，日志记录为START CKPT

20、(T,V)，所以在COMMIT V之后 写入END CKPT记录。如果故障发生在 END CKPT记录之后，那么我们可以向后扫描直到下一个STARTCKPT(T,V)记录停止。如果故障发生在COMMIT V之前，那么我们要回溯到START T。习题6.3.2使用习题6.2.7的数据，对该习题中 到(e)的各个位置，回答：i) 何时能写入 CKPT记录。ii) 对每一个可能发生故障的时刻，为了找到所有可能未完成的事务，我们需要在日志中向后看多远。请考虑END CKPT记录在崩溃发生之前写入和未写入的两种情况。a) 当前活跃的事务只有 S,日志记录为START CKPT(S)，所以在COMMIT

21、S之前写入 END CKPT 记录。如果崩溃发生在END CKPT记录之后，那么在日志中只要回溯到 START S。如果崩溃发 生在END CKPT记录之前，我们必须向后搜索到倒数第二个START CKPT记录并得到其活跃事务列表。在本题中没有前一检查点， 因而必须一直走到日志的开头， 确定没有已提交 的事务。b) 当前活跃的事务只有 T,日志记录为START CKPT(T)，所以在COMMIT T之前写入 END CKPT 记录。如果崩溃发生在END CKPT记录之后，那么在日志中只要回溯到 START T。如果崩溃发生在END CKPT记录之前，我们必须向后搜索到倒数第二个START CK

22、PT记录并得到其活跃事务列表。在本题中没有前一检查点，因而必须一直走到日志的开头， 确定已提交的事 务只有S,重复其动作S,A,60，并在恢复后将记录ABORT T写入日志中。C）当前活跃的事务有 T和U，日志记录为START CKPT（T,U），所以在COMMIT U之前 写入END CKPT记录。如果崩溃发生在END CKPT记录之后，那么在日志中只要回溯到 START T。如果崩溃发 生在END CKPT记录之前，我们必须向后搜索到倒数第二个START CKPT记录并得到其活跃事务列表。在本题中没有前一检查点，因而必须一直走到日志的开头， 确定已提交的事 务只有S，重复其动作S,A,60

23、，并在恢复后将记录ABORT T和ABORT U写入日志中。d） 当前活跃的事务有 T、U和V ,日志记录为START CKPT（T,U,V） ，所以在COMMIT U 之前写入END CKPT记录。如果崩溃发生在END CKPT记录之后，那么在日志中只要回溯到 START T。如果崩溃发 生在END CKPT记录之前，我们必须向后搜索到倒数第二个START CKPT记录并得到其活跃事务列表。在本题中没有前一检查点，因而必须一直走到日志的开头， 确定已提交的事 务只有S,重复其动作S,A,60，并在恢复后将记录 ABORT T 、ABORT U和ABORT V写入日志中。e）当前活跃的事务有

24、T和V，日志记录为START CKPT（T,V），所以在COMMIT T之前 写入END CKPT记录。如果崩溃发生在END CKPT记录之后，那么在日志中只要回溯到 START T。如果崩溃发 生在END CKPT记录之前，我们必须向后搜索到倒数第二个START CKPT记录并得到其活跃事务列表。在本题中没有前一检查点，因而必须一直走到日志的开头，确定已提交的事务有S和U，重复其动作S,A,60、U,B,20、U,D,40，并在恢复后将记录 ABORT T 和ABORT V写入日志中。习题6.3.4使用redo日志，重复习题 623。和a）事务U和T都未提交，什么都不做，磁盘数据无变化，在日

25、志中写入ABORT T记录并刷新日志。b）事务T已提交，为B写入值20，为D写入值40,在日志中写入ABORT U记录并刷新 日志。C）事务T已提交，为B写入值20,为D写入值40,在日志中写入ABORT U记录并刷新 日志。d）事务T和U已提交，为A写入值10,为B写入值20,为C写入值30，为D写入值40。习题6.4.2下面是两个事务 T和U的一系列日志记录：START U;U,A,10,11;STARTT;T,B,20,21;U,C,30,31;T,D,40,41;COMMITT;U,E,50,51;COMMITU;。请描述恢复管理器的行为，包括对磁盘和日志所做的改变，假设故障发生且出现

26、在磁盘上的最后 一条日志记录为：a）START T事务U未提交，回滚 U （从后往前），A的值置为10。在日志中写入ABORT U记录并刷 新日志。b）COMMIT T事务T已提交，重做T,将B的值置为21, D的值置为41。事务U未提交，回滚U(从后往前)，将C的值置为30, A的值置为10。在日志中写入VABORT U记录并刷新日志。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的值

27、置为31，D 的值置为41，E的值置为51。习题 6.4.4 考虑如下日志记录序列：; ; ; ; ; ; ; ; ; ; ; ; ; ; ;。假设我们在如下日志记录中的某一条写入(主存)后立即开始一个非静止检查点：a) b) c) d) e) 对其中的每一个，说明：i何时写入记录。ii对于每一个可能发生故障的时刻，为了找到所有可能未完成的事务，我们需要在日志中回溯多远。请考虑记录在崩溃发生以前写入和未写入的两种情况。a) 记录可以在之后任意位置出现。当前活跃的事务只有 S。如果崩溃发生在记录之后，那么在日志中只要回溯到 。如果崩溃发生在 记录之前，我们必须向后搜索到倒数第二个 START C

28、KPT记录并得到其活跃事务列表。在本题中没有前一检查点，因而必须一直走到 日志的开头，确定没有已提交的事务。b) 记录可以在之后任意位置出现。当前活跃的事务只有 T。如果崩溃发生在记录之后，那么在日志中只要回溯到 。如果崩溃发生在 记录之前，我们必须向后搜索到倒数第二个 START CKPT记录并得到其活跃事务列表。在本题中没有前一检查点，因而必须一直走到 日志的开头，确定已提交的事务只有Soc) 记录可以在之后任意位置出现。当前活跃的事务有 T和U。如果崩溃发生在记录之后，那么在日志中只要回 溯到。如果崩溃发生在记录之前，我们必须向后搜索到倒数第二个 START CKPT记录并得到其活跃事务

29、列表。在本题中没有前一检查点，因而必须一直走到 日志的开头，确定已提交的事务只有Sod) 记录可以在之后任意位置出现。当前活跃的事务有 T、U和V。如果崩溃发生在记录之后，那么在日志中只要 回溯到。如果崩溃发生在记录之前，我们必须向后搜索到倒数第二 个START CKPT记录并得到其活跃事务列表。在本题中没有前一检查点，因而必须一直走 到日志的开头，确定已提交的事务只有Soe) 记录可以在之后任意位置出现。当前活跃的事务有 T和V。如果崩溃发生在记录之后，那么在日志中只要回 溯到。如果崩溃发生在记录之前，我们必须向后搜索到倒数第二个 START CKPT记录并得到其活跃事务列表。在本题中没有前

30、一检查点，因而必须一直走到 日志的开头，确定已提交的事务有S和U。习题6.5.1如果在例6.14和例6.15中使用的是redo日志而不是undo/redo日志，那么：a) 日志会是怎样的？START DUMPDump completesb) 如果我们需要使用备份以及这一日志进行恢复，Ti未提交的后果是什么？在T1提交之前转储已经完成，对于未提交事务 T1，它所做的修改不能到达磁盘。 也就是说,A和B不能变到新值。c) 恢复后数据库的状态是什么？数据库元素A、B、C、和D分别是(1，2，6，4)习题7.1.1|航班预订系统执行的一个事务T1执行以下步骤：i .询问顾客希望的航班时间和城市。所需航

31、班信息位于数据库元素(可能是磁盘块)A和B中，系统在磁盘上检索所需信息。ii. 告诉顾客供选择的选项，顾客选择一个航班， 该航班的数据在 B中，包括该航班的预订 号。为该顾客预订该航班。iii. 顾客为该航班选择一个座位；该航班的座位信息位于数据库元素C中。iv .系统获得顾客的信用卡号，并将该航班的账单附加到数据库元素D的账单列表上。v.顾客的电话和航班数据被加到数据库元素E上的另一个列表中，这是为了向顾客发确认航班的传真。将事务T1表示为r和w动作的一个序列。r1(A); r 1(B); w 1(B); r 1(C); w 1(C); r 1(D); w 1(D); r 1(E); w 1

32、(E).习题7.2.1|下面是用对数据库元素A和B的影响来描述的两个事务，我们可以假设数据库兀素A和B是整数。T1 : READ(A,t); t:=t+2; WRITE(A,t); READ(B,t); t:=t*3; WRITE(B,t);T2 : READ(B,s); s:=s*2; WRITE(B,s); READ(A,s); s:=s+3; WRITE(A,s);我们假设不管数据库上的一致性约束是什么，这些事务在隔离的情况下能够保持这些约束。 注意，A=B不是一致性约束。a）给出上面12个动作的一个串行调度的例子和一个非串行调度的例子。b）这12个动作共有多少串行调度？c）这12个动作

33、共有多少可串行化调度？d）这两个串行顺序对数据库的影响是相同的，即（T1,T2 ）和（T2,T1）等价。通过给出任意数据库初态时这两个事务的结果，说明这一事实。a）串行调度的例子T1T2ABREAD(A,t)1015t:=t+2WRITE(A,t)12READ(B,t)t:=t*3WRITE(B,t)45READ(B,s)s:=s*2WRITE(B,s)90READ(A,s)s:=s+3WRITE(A,s)15非串行调度的例子T1T2READ(A,t)t:=t+2WRITE(A,t)READ(B,s)s:=s*2WRITE(B,s)READ(B,t)t:=t*3WRITE(B,t)READ(A

34、,s)s:=s+3WRITE(A,s)b）这12个动作共有2种串行调度，即（T1,T2 ）和（T2,T1 ）。c）如果一事务先读 A，则写操作必须在另一事务读A之前完成。对B也一样。1、如果T1先读A和B,则写操作也要在 T2之前完成，也就是说T2只能在T1之后操作。由于T1和T2中的每一个动作都要保持自身定义中出现的顺序，所以这种情况下只有一个冲突可串行化调度。2、如果T2先读A和B,同1中可知这种情况下也只有一个冲突可串行化调度。3、如果T1先读B，接着T2读A，这种情况不会出现。4、女口果 T1 先读 A，接着 T2 读 B，Now, the first three steps of e

35、ach transaction may in terleave in any way, and the last three of each may in terleave in any way, but the two groups of six actions must not interleave. The crucial observation is that the fourth step of each transaction (their sec ond reads) must follow the third step of each transaction (their fi

36、rst writes), either to avoid reading A or B before it is written, or because actions of the same transaction cannot be reordered. The nu mber of serializable orders of this type is (6 choose 3)*(6 choose 3) = 20*20 =400.The total nu mber of serial orders is thus 402.d) 假设初始A=10 , B=15，则(T1,T2 )的结果如a

37、)中所示。下面是(T2,T1 )的结果。T1T2ABREAD(B,s)1015s:=s*2WRITE(B,s)30READ(A,s)s:=s+3WRITE(A,s)13READ(A,t)t:=t+2WRITE(A,t)15READ(B,t)t:=t*3WRITE(B,t)90对比可知，最后结果一致，均是A=15 , B=90习题7.2.5对以下的每一个调度：a) w3(A) ;r1(A) ; w1(B) ;r2(B) ; w2(C) 丁3(C);b) r1(A) ; r2(A) ;w1(B) ; w2(B) ;r1(B) ; r2(B) ; w2(C) ; w1(D);c) r1(A) ; r

38、2(A) ;r1(B) ; r2(B) 丁3(A) ; r4(B) ; w1(A) ; w2(B);d) r1(A) ; r2(A) 丁3(B) ;w1(A) ;r2(C) ; r2(B) ; w2(B) ; w1(C);e) r1(A) ; w1(B) ; r2(B) ;w2(C) ; r3(C) ; w3(A);回答如下问题：i. 调度的优先图是什么？ii. 调度是冲突可串行化的吗？如果是，等价的串行调度有哪些？iii. 是否有等价的调度(不管事务对数据做什么)，但又不是冲突等价的？a)优先图是 T1 - T2 - T3该图有环，所以调度不是冲突可串行化的。没有等价且不为冲突等价的调度。假

39、设A, B和C的初值都为10, T3将A置为A+C , T2将C设为B+C , T1是将B设为A+B。如果T1不优先于T2,那么C的赋值将出错。如果 T2不优先于T3，那么A的赋值将出错。如果 T3不优先于T1，那么B的赋值将出错。b)优先图是T1=- T2该图有环，所以调度不是冲突可串行化的。假设A, B, C和D的初值都为10, T1将B置为A+B , D置为20, T2也将B置为A+B ,C置为20。调度(Ti, T2)和(T2, T1)是等价的。c)优先图(precede nee graph)是 T3 T1 T2 T2 T1该图是无环的，所以调度是冲突可串行化的。等价的串行调度只有(T

40、3, T2, T1)没有等价且不为冲突等价的调度。假设A, B和C的初值都为10, T1将A和C置为20，T2将B设为A+B+C，T3是打印B。如果T3不优先于T2，则T3打印出来B的值是错误的。 如果T2不优先于T1，则它对B的赋值就出错了。e) 一优先图是 T1 一- T2 -该图无环，所以调度是冲突可串行化的。等价的串行调度只有(T1, T2, T3)。没有等价且不为冲突等价的调度。假设A, B和C的初值都为10, T3将A置为A+C，T2将C设为B+C，T1是将B设为A+B。如果T1不优先于T2,那么C的赋值将出错。如果 T2不优先于T3，那么A的赋值将出错。如果 T1不优先于T3，那

41、么B的赋值将出错。习题7.3.1|下面是两个事务，其中给出了封锁请求和事务的语义。回忆一下习题7.2.1中,这些事务具有特殊的性质,即它们被调度的方式可以是非冲突可串行化的，但由于其语义又是可串行化的。厂I：仆(*)；】()；A A+2;馆(/!)： uiC4): JJB)；门(); B .:= B*3; 叭W);丁Fa-fl); B := B*2； toa(S);b(j4);A : A+3:如U下面的问题中，只考虑读写动作的调度，而不要考虑封锁、解锁或赋值步骤。a)给出被锁禁止的调度的一个例子。r1(A); r 2(B)； W2(B)； r 2(A); w 1(A); r 1(B); W1(

42、B); W2(A)习题7.3.3对于习题7.2.5种的每个调度，假设每个事务刚好在读或写每个数据库元素以前 获得该元素上的锁,并且每个事务在最后一次访问一个元素后立即释放其锁。说一说封锁调度器对这些调度中的每一个会怎么做；即哪些请求将被推迟，而什么时候它们又将被允许继续？a) 没有操作被推迟，调度顺序为w3(A) ;r1(A) ; w1(B) ;r2(B) ; w2(C) ;r3(C);b) 请求r1(B)将被推迟，因为T1对数据库元素B加锁了，等到r1(B),之后将释放B上的 锁，这时候 r1(B)将被允许继续。调度顺序为:r1(A) ; r2(A) ;w1(B) ; r1(B) ;w2(B

43、) ; r2(B) ; w2(C); w1(D);c) 请求r2(A)将被推迟，因为T1对数据库元素A加锁了，等到wA),之后将释放A上的 锁，这时候2(A)将被允许继续。同样请求 r3(A)也将被推迟，因为 T1对数据库元素 A加锁 了，T1解锁之后有T2对A加锁，等到r2(A)，之后T?将释放A上的锁，这时候 3(A)将被允 许继续。另外r4(B)也被推迟，要在 w2(B)之后才将被允许继续。调度顺序为：r1(A) ; r1(B) ;w1(A) ; r2(A) ; r2(B) 丁3(A) ; w2(B) ; r4(B);d) 请求r2(A)将被推迟，因为T1对数据库元素 A加锁了，等到wi

44、(A),之后Ti将释放A上的 锁，这时候 3(A)将被允许继续。调度顺序为：ri(A);3(B)； wi(A); “(A);2(C); “(B)； W2(B)； wi(C).e) 没有操作被推迟，调度顺序为ri(A) ; wi(B) ; r2(B) ;w2(C) ; r3(C) ; w3(A);习题7.4.1|对下面事务Ti、T2和T3的每一个调度：a) ri(A);r2(B);r3(C);wi(B);w2(C);w3(A);b) ri(A);r2(B);r3(C); ri(B);r2(C);r3(D);wi(C);w2(D);w3(E);做以下各件事情： IS人共享锁和排他锁.并描入解锁动作

45、“如杲一个读动柞厉没有同一事务对同一元護的 写动作、请在该读动作嚴紧靠它舱地方放一个共拿锁q在其他的每一个读动柞或写动作 前放-个排他锁。在每个爭务的末尾放上必需的解锁2) 说明支持共享锁和排他锁的调度器运行每个调度时会发生什么3) 以一种允许升级的方式插入共冥锁和排他锁。在每个读动作前放一个共学锁，在铮个 打动柞前放一个排他锁*井枉爭务的未尾放上必需的解锁联轲说囲3)中的支持共酬筑排他倾和升级的调度器运行每个调度旳会发主什么，勺桶人共享锁、排他锁和更新锁以及解锁动作弋在毎一个五会升级的读动作前放-个武亨 W,在毎一个擀升级的淒动作前放一个更新锁*并在每一牛写幼作前故个排他锁 ft 爭务的耒底

46、照钏放丄刑们说明弭屮的支持找学锁、排他锁和虫新锁的调僧器运行毎个调度时会发龟fl么；a)(i) : sli(A); ri(A); sl2(B); r2(B); sl3(C); r3(C); xli(B); wi(B); ui(A); ui(B); xl2(C); w2(C); u2(B); u2(C); xl3(A); w3(A); u3(C); u3(A);(ii) :前面3个加锁和读操作是正确的，但xli(B)和xl2(C)操作被推迟，在 B存在共享锁的情况下T1不能再加排它锁，同理在C存在共享锁的情况下T2不能再加排它锁。出现死锁现象。如果要执行w1(B)，则需在T2事务完成后；但 T2

47、事务完成的前提是w2(C)要执行完，这一操作要求之前T3要对C解锁；T3要对C解锁的话则w3(A)要执行完，这一操作要求之前T1要对A解锁，T1要对A解锁的话则w1(B)要执行完，陷入死循环。(iii) : sl1(A); r1(A); sl2(B); r2(B); sl3(C); r3(C); xl1(B); w1(B); u1(A); u1(B); xl2(C); w2(C); u2(B); u2(C); xl3(A); w3(A); u3(C); u3(A);(iv) :前面3个加锁和读操作是正确的，但xl1(B)和xl2(C)操作被推迟，在B存在共享锁的情况下T1不能再加排它锁，同理在

48、C存在共享锁的情况下T2不能再加排它锁。出现死锁现象。如果要执行w1(B)，则需在T2事务完成后；但 T2事务完成的前提是w2(C)要执行完，这一操作要求之前T3要对C解锁；T3要对C解锁的话则w3(A)要执行完，这一操作要求之前T1要对A解锁，T1要对A解锁的话则w1(B)要执行完，陷入死循环。(v) : sl1(A); r1(A); sl2(B); r2(B); sl3(C); r3(C); ul1(B); xl1(B); w1(B); u1(A); u1(B); ul2(C); xl2(C); w2(C); u2(B); u2(C); ul3(A); xl3(A); w3(A); u3(

49、C); u3(A);(vi) :前面3个加锁和读操作是正确的，但xl1(B)和xl2(C)操作被推迟，在B存在共享锁的情况下T1不能再加排它锁，同理在C存在共享锁的情况下T2不能再加排它锁。出现死锁现象。如果要执行 w1(B)，则需在T2事务完成后；但 T2事务完成的前提是 w2(C) 要执行完，这一操作要求之前T3要对C解锁；T3要对C解锁的话则w3(A)要执行完，这一操作要求之前T1要对A解锁，T1要对A解锁的话则w1(B)要执行完，陷入死循环。b)(i) : sl1(A); r1(A); sl2(B); r2(B); sl3(C); r3(C); sl1(B); r1(B); sl2(C

50、); r2(C); sl3(D); r3(D); xl1(C);w1(C); u1(A); u1(B);u1(C); xl2(D); w2(D); u2(B); u2(C); u2(D);xl3(E); w3(E); u3(C); u3(D); u3(E);(ii) :前面6个加锁和读操作是正确的，但xl1(C)和xl2(D)操作被推迟，在 C存在共享锁的情况下T1不能再加排它锁，同理在D存在共享锁的情况下 T2不能再加排它锁。先执行T3事务，w3(E)，T3执行完成后释放它在 C、D、E上的锁；由于还有事务 T2在C上 加了共享锁，所以 xl1(C)操作依然被推迟，于是先执行 T2事务，w2

51、(D)，执行完成后 T2释 放在B、C、D上的锁，这时候T1就可以执行了， w1(C)，执行完成后释放 A、B、C上的锁。(iii) : sl1(A); r1(A); sl2(B); r2(B); sl3(C); r3(C); sl1(B); r1(B); sl2(C); r2(C); sl3(D); r3(D); xl1(C); w1(C); u1(A); u1(B);u1(C); xl2(D); w2(D); u2(B); u2(C); u2(D);xl3(E); w3(E); u3(C); u3(D); u3(E);(iv) :前面6个加锁和读操作是正确的，但xl1(C)和xl2(D)操作被推迟，