a）给出上面12个动作的一个串行调度的例子和一个非串行调度的例子。 b）这12个动作共有多少串行调度？ c）这12个动作共有多少可串行化调度？
d）这两个串行顺序对数据库的影响是相同的，即（T1,T2）和（T2,T1）等价。通过给出任意数据库初态时这两个事务的结果，说明这一事实。 a）串行调度的例子 T1 READ(A,t) t:=t+2 READ(B,t) t:=t*3 非串行调度的例子 T1 READ(A,t) t:=t+2 READ(B,t) t:=t*3 T2 READ(B,s) s:=s*2 WRITE(B,s) READ(A,s) s:=s+3 WRITE(A,s) T2 READ(B,s) s:=s*2 READ(A,s) s:=s+3 A 10 12 B 15 45 90 WRITE(A,t) WRITE(B,t) WRITE(B,s) WRITE(A,s) 15 WRITE(A,t) WRITE(B,t) 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 each transaction may interleave in any way, and the last three of each may interleave 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 second reads) must follow the third step of each transaction (their first writes), either to avoid reading A or B before it is written, or because actions of the same transaction cannot be reordered. The number of serializable orders of this type is (6 choose 3)*(6 choose 3) = 20*20 = 400. The total number of serial orders is thus 402. d） 假设初始A=10，B=15，则（T1,T2）的结果如a）中所示。下面是（T2,T1）的结果。 T1 READ(B,s) s:=s*2 READ(A,s) s:=s+3 T2 READ(A,t) t:=t+2 READ(B,t) t:=t*3 A 10 13 B 15 30 90 WRITE(B,s) WRITE(A,s) WRITE(A,t) 15 WRITE(B,t) 对比可知，最后结果一致，均是A=15，B=90 习题7.2.5 对以下的每一个调度：
a) w3(A) ;r1(A) ; w1(B) ;r2(B) ; w2(C) ;r3(C) ;
b) r1(A) ; r2(A) ;w1(B) ; w2(B) ;r1(B) ; r2(B) ; w2(C) ; w1(D) ; c) r1(A) ; r2(A) ;r1(B) ; r2(B) ;r3(A) ; r4(B) ; w1(A) ; w2(B) ; d) r1(A) ; r2(A) ;r3(B) ;w1(A) ;r2(C) ; r2(B) ; w2(B) ; w1(C) ; e) r1(A) ; w1(B) ; r2(B) ;w2(C) ; r3(C) ; w3(A) ; 回答如下问题：
ⅰ. 调度的优先图是什么？
ⅱ. 调度是冲突可串行化的吗？如果是，等价的串行调度有哪些？ ⅲ. 是否有等价的调度（不管事务对数据做什么），但又不是冲突等价的？ a）
优先图是 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的赋值将出错。如果T3不优先于T1，那么B的赋值将出错。 b）
优先图是 T1 -----> T2 该图有环，所以调度不是冲突可串行化的。
假设A, B，C和 D 的初值都为10，T1将B置为A+B，D置为20，T2 也将B置为A+B，
C置为20。调度（T1, T2）和（T2, T1）是等价的。 c）
优先图（precedence graph）是 T3 -----> T1 -----> T2 <----- T4 该图是有环的，所以调度不是冲突可串行化的。
没有等价且不为冲突等价的调度。假设A和B的初值都为10，T1将A设为A+B，T2将B设为B+A，T3是打印A，T4是打印B。如果T4不优先于T2，则T4打印出来B的值是错误的。如果T3不优先于T1，则T3打印出来A的值是错误的。 d）
优先图（precedence graph）是 T3 -----> T2 -----> T1
该图是无环的，所以调度是冲突可串行化的。等价的串行调度只有（T3, 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 -----> T3 该图无环，所以调度是冲突可串行化的。等价的串行调度只有（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，那么B的赋值将出错。 习题7.3.1 下面是两个事务，其中给出了封锁请求和事务的语义。回忆一下习题7.2.1中，这些事务具有特殊的性质，即它们被调度的方式可以是非冲突可串行化的，但由于其语义又是可串行化的。
下面的问题中，只考虑读写动作的调度，而不要考虑封锁、解锁或赋值步骤。 a） 给出被锁禁止的调度的一个例子。
r1(A); r2(B); w2(B); r2(A); w1(A); r1(B); w1(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),之后T1将释放B上的锁，这时候r1(B)将被允许继续。调度顺序为:r1(A) ; r2(A) ;w1(B) ; r1(B) ;w2(B) ; r2(B) ; w2(C) ; w1(D) ;
c) 请求r2(A)将被推迟，因为T1对数据库元素A加锁了，等到w1(A),之后T1将释放A上的锁，这时候r2(A)将被允许继续。同样请求r3(A)也将被推迟，因为T1对数据库元素A加锁
了，T1解锁之后有T2对A加锁，等到r2(A),之后T2将释放A上的锁，这时候r3(A)将被允许继续。另外r4(B)也被推迟，要在w2(B)之后才将被允许继续。
调度顺序为：r1(A) ; r1(B) ;w1(A) ; r2(A) ; r2(B) ;r3(A) ; w2(B) ; r4(B) ;
d) 请求r2(A)将被推迟，因为T1对数据库元素A加锁了，等到w1(A),之后T1将释放A上的锁，这时候r2(A)将被允许继续。调度顺序为: r1(A); r3(B); w1(A); r2(A); r2(C); r2(B); w2(B); w1(C).
e) 没有操作被推迟，调度顺序为r1(A) ; w1(B) ; r2(B) ;w2(C) ; r3(C) ; w3(A) ; 习题7.4.1 对下面事务T1、T2和T3 的每一个调度： a）r1(A);r2(B);r3(C);w1(B);w2(C);w3(A);
b）r1(A);r2(B);r3(C); r1(B);r2(C);r3(D);w1(C);w2(D);w3(E); 做以下各件事情：
a)
(i): 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);
(ii): 前面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)要执行完，陷入死循环。
(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不能再加排它锁，同理在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(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); 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(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)操作被推迟，在C存在共享锁的情况下T1不能再加排它锁，同理在D存在共享锁的情况下T2不能再加排它锁。
先执行T3事务，w3(E)，T3执行完成后释放它在C、D、E上的锁；由于还有事务T2在C上加了共享锁，所以xl1(C)操作依然被推迟，于是先执行T2事务，w2(D)，执行完成后T2释放在B、C、D上的锁，这时候T1就可以执行了，w1(C)，执行完成后释放A、B、C上的锁。 (v): sl1(A); r1(A); sl2(B); r2(B); sl3(C); r3(C); sl1(B); r1(B); sl2(C); r2(C); sl3(D); r3(D); ul1(C); xl1(C); w1(C); u1(A); u1(B);u1(C); ul2(D); xl2(D); w2(D); u2(B); u2(C); u2(D); ul3(E); xl3(E); w3(E); u3(C); u3(D); u3(E);
(vi): 前面6个加锁和读操作是正确的，但xl1(C)和xl2(D)操作被推迟，在C存在共享锁的情况下T1不能再加排它锁，同理在D存在共享锁的情况下T2不能再加排它锁。
先执行T3事务，w3(E)，T3执行完成后释放它在C、D、E上的锁；由于还有事务T2在C上加了共享锁，所以xl1(C)操作依然被推迟，于是先执行T2事务，w2(D)，执行完成后T2释放在B、C、D上的锁，这时候T1就可以执行了，w1(C)，执行完成后释放A、B、C上的锁。 习题7.4.2
sl1(A); r1A(); sl2(B); r2(B); il1(B); inc1(B); il2(A); inc2(A); xl1(C); w1(C); u1(A); u1(B); u1(C); xl2(D); w2(D); u2(B); u2(A); u2(D);
前面2个加锁和读操作是正确的，但il1(B)操作被推迟，在B存在共享锁的情况下T1不能再加增量锁。事务T1后面的操作被推迟，再看T2事务，操作il2(A)也是不允许的，因为T1事务在A上加了共享锁，所以T1、T2事务都不能正常执行，陷入死锁状态。