| 【问题1】 假设T1、T2、T3可以并发执行。若A的初值为0,那么存在多少种可能的正确结果? |
| 【问题2】 各个事务内部的结构如表13-4所示,若事务执行不施加任何锁,则有多少种不同的调度方式?写出简要的计算过程。 {{B}}表13-4各个事务内部的结构{{/B}}
【正确答案】
【答案解析】假设Ri、Rj、Rk表示各事务的R操作,Up、Uq、Ur表示各事务的U操作,那么根据组合数学中的乘法原理有:
Ri→Rj→Rk→Up→Uq→Ur 3×2×1×3×2×1=36 Ri→Rj→Up→Rk→Uq→Ur 3×2×2×1×2×1=24 Ri→Rj→Up→Uq→Rk→Ur 3×2×2×1×1×1=12 Ri→Up→Rj→Rk→Uq→Ur 3×1×2×1×2×1=12 Ri→Up→Rj→Uq→Uk→Ur 3×1×2×1×1×1=6 全部加起来得:36+24+12+12+6=90,因此共有90种不同的调度方式。
问答题
【正确答案】
【答案解析】存在。
在A的初值给定为0时,调度R1→R2→R3→U3→U2→U1的执行结果与6个可能的串行调度中的T1→T2→T3或T2→T1→T3的执行结果一致,A的值都为1,也就是说,对于初值0而言,该并发调度策略是“正确”的。 数据库系统对并发事务的调度是随机的,而不同的调度往往会产生不同的结果。如果一个事务运行过程中没有其它事务同时运行。也就是说没有受到其它事务的干扰,那么就可以认为该事务的运行结果是正常的或预想的。因此,将所有事务串行起来的调度策略一定是正确的调度策略,虽然以不同的顺序串行执行事务可能会产生不同的结果,但由于不会将数据库置于不一致的状态,因此都是正确的。 对于多个事务的某种并发调度策略而言,当且仅当该调度的结果与按某一次序串行执行这些事务的结果一样时,就称该策略是可串行化的,并认为该并发调度策略是正确的。 根据排列组合原理,三个事务一共有6种排列: T1→T2→T3 A的值为1 T1→T3→T2 A的值为2 T2→T1→T3 A的值为1 T2→T3→T1 A的值为2 T3→T1→T2 A的值为4 T3→T2→T1 A的值为3 问题2中给出了各个事务的内部结构。假设Ri、Rj、Rk表示各事务的R操作,Up、 Uq、Ur表示各事务的U操作,那么根据组合数学中的乘法原理有: Ri→Rj→Rk→Up→Uq→Ur 3×2×1×3×2×1=36 Ri→Rj→Up→Rk→Uq→Ur 3×2×2×1×2×1=24 Ri→Rj→Up→Uq→Rk→Ur 3×2×2×1×1×1=12 Ri→Up→Rj→Rk→Uq→Ur 3×1×2×1×2×1=12 Ri→Up→Rj→Uq→Rk→Ur 3×1×2×1×1×1=6 全部加起来得:36+24+12+12+6=90,因此共有90种不同的调度方式。这里要注意,对于同一事务而言,R操作必须在U操作之前,如果反了,那就不是原来事务的结构了,也就不是原来的事务了。例如,对次序Ri→Rj→Up→Rk→Uq→Ur而言,Ri可以是 R1、R2、R3三者之一,因此连乘式中Ri对应数字3。当Ri选定之后,假设Ri选定的是 R1,那么对于Rj而言只能从剩下的R2、R3中二选一,所以,连乘式中,Rj对应数字2,假设Rj是R2,那么只剩余R3(Rk只能是R3了)。接下来是Up,Up只能是U1、U2二者之一,因为它若是U3的话,就使得U3排在了剩余的R3之前,破坏了事务T3的结构。又如,次序Ri→Up→Rj→Rk→Uq→Ur中,Ri可以是R1、R2、R3三者之一,因此连乘式中对应数字3,当Ri选定之后,假设Ri是R2,那么接下来的Up只能是U2,因为如果是U1或 U3的话,就会破坏T1或T3的结构。其它类似。 根据前面的阐述可知,如果一个并发调度策略的执行结果跟某个串行执行的结果一致的话,则该并发调度策略就是正确的。在A的初值给定为0时,调度R1→R2→R3→U3→ U2→U1的执行结果与6个可能的串行调度中的T1→T2→T3或T2→T1→T3的执行结果一致,A的值都为1。也就是说,对于初值0而言,该并发调度策略是“正确”的。但这仅仅是凑巧而已,对其它初值未必如此。例如,若A的初值为10,6种串行调度A的值仍有1、 2、4、3四种结果,而调度R1→R2→R3→U3→U2→U1执行之后A的值为11,跟任一个串行调度执行的结果都不一样,因此是不可串行化的,是不正确的。 |