事务并发调度问题
昨天看模拟题,有一道关于数据库并发的题目,不是很明白,所以今天特地到网上查了一下,在这里做一个记录:
题目是数据库系统工程师考试06年5月下午卷的第5题,具体的题目是这样的:
******************************************************************************
【说明】
现有一个事务集{T1,T2,T3,T4},其中这四个事务在运行过程中需要读写X、Y和Z。设Ti对X的读操作记作TiR(X),Ti对X的写操作记作TiW(X)。
事务对XYZ的访问情况如下:
T1:T1R(x)
T2:T2R(Y),T2W(X)
T3:T3W(Y),T3W(X),T3W(Z)
T4:T4R(Z),T4W(X)
【问题1】试述事务并发高(调)度的正确性准则及其内容(4分)
【问题2】请判断如下高(调)度是否正确。(4分)
T3W(Y),T1R(X),T2R(Y),T3W(X),T2W(X),T3W(Z),T4R(Z),T4W(X)
按这种调度产生的事务依赖关系图如下:
【问题3】给出与【问题2】中调度等价的一串行调度序列。(3分)
(注:严重质疑题目里的“高度”应该是错别字,改成“调度”才可以理解)
******************************************************************************
首先关于【问题1】,我的理解是这样的:事务的并发调度的正确性,取决于这个并发调度是不是可以等价得转换为串行调度。只有当一个并行调度可以与某一次的串行调度转化时,这个并发调度才是正确的。
然后对于【问题2】,可能对题目本身比较难以理解。其实对于并行调度的正确性判断不需要考虑读写一致性和锁定/解锁的问题,虽然事务T1/T2/T3/T4中的每一个子项都是原子性的,在启动前锁定,完成后解锁,但是如果不是按照整个事务的串行化执行,其最后的结果是会发生错误的。所以我们只能从事务对于X/Y/Z的依赖性的角度来进行分析,例如:
数据项X:T1R(X),T3W(X),T2W(X),T4W(X)
相对于X的事物依赖图为:T1--->T3,T1--->T2,T1--->T4,T3--->T2,T3--->T4,T2--->T4
数据项Y:T3W(Y),T2R(Y)
相对于Y的事物依赖图为:T3--->T2
数据项Z:T3W(Z),T4R(Z)
相对于Z的事物依赖图为T3--->T4
综合X,Y,Z的事物依赖图得到题目已知的事物调度依赖图。
在事物调度依赖图中,沿箭头方向不产生回路(要包含所有事务)的一条路径就是与该并发调度等价的串行调度,假设在事务依赖图中有回路产生,则该并发调度是不可串行化的。而本题按照T1--->T3--->T2--->T4的顺序是满足条件的,所以题中的并行调度顺序是正确的。
如果是不可串行化的调度,则可能是发生了死锁。例如...,T2R(Y),T3W(X),...T2W(X),T3W(Y),...
如果出现这种情况,则改换成串行模式时,对于Y,T3在等待T2结束后对Y解锁,而对于X,T2在等待T3结束后对X解锁,这样就造成了互相等待的死锁情况而无法进行下去。
需要特别注意的是:在事物依赖有向图中,选取的路径是不可以包括回路(多方死锁),或者双向路径的。
对于【问题三】,只要搞明白上面的原理,就很简单了,答案就是 T1--->T3--->T2--->T4