|
数据库系统必须控制事务的并发执行以保证数据库处于一致性状态。
|
|
|
|
多个事务的并发执行是正确的,当且仅当其结果与某一次序串行地执行它们时的结果相同,称这种调度策略是可串行化的调度(serializability schedule)。
|
|
|
可串行性是并发事务正确性的准则,按这个准则规定,一个给定的并发调度,当且仅当它是可串行化的才认为是正确调度。
|
|
|
|
冲突(conflict):当Ii和Ij是不同事务在相同的数据项上操作的命令,且至少有一个是write命令时,则称Ii与Ij是冲突的。
|
|
|
考虑某调度S中含有分别属于事务Ti、Tj的两条命令Ii、Ij(i≠j)。若Ii、Ij分别访问不同的数据项,则交换Ii、Ij的执行次序不会影响调度执行的结果。若Ii、Ij访问相同的数据项,则Ii、Ij的执行次序可能会影响调度执行的结果。在此只讨论read和write命令在以下四种情况时Ii、Ij是否可交换:
|
|
|
(1)Ii=read(D),Ij=read(D)。在调度S中,Ii与Tj读到的是相同的数据D值,交换Ii、Ij的执行次序不会影响执行的结果。
|
|
|
(2)Ii=read(D),Ij=write(D)。在调度S中,若Ii先于Ij执行,那么Ii没有读到Ij写回的D值,可见Ii、Ij的执行次序是非常重要的。
|
|
|
(3)Ii=write(D),Ij=read(D)。在调度S中,Ii、Ij的执行次序是非常重要的,其原因与(2)类似。
|
|
|
(4)Ii=write(D),Ij=write(D)。由于Ii、Ij都是写操作,Ii、Ij的执行次序对Ii、Tj没有影响,但是,若调度S中的下一条命令是read(D),那么读取的值会受到影响,因为数据库中只保留了后一条write命令写入的值。
|
|
|
等价调度:设Ii与Ij是调度S的两条连续的命令,若Ii与Ij是不同事务的命令且不冲突,则可以交换Ii与Ij的顺序得到一个新的调度S*。我们称S与S*是等价的。
|
|
|
|
|
例如,考虑上图(a)调度S3,由于T1的write(A)与T0的read(B)不冲突,可以将T1的write(A)与T0的read(B)的执行次序交换,得到另一个等价调度S5,如下图所示。
|
|
|
|
|
|
①T0的read(B)与T1的read(A)执行次序交换。
|
|
|
②T0的write(B)与T1的write(A)执行次序交换。
|
|
|
③T0的write(B)与T1的read(A)执行次序交换。
|
|
|
经过上述一系列交换后得到的是一个如下图(a)所示的串行调度S1。这也说明了调度S5等价于一个串行调度,所以是一个正确的调度。请思考为什么调度S4是一个错误的调度。
|
|
|
|
|
冲突等价(conflict equivalent):如果调度S经过一系列非冲突命令交换成S*,则称S与S*是冲突等价的。
|
|
|
冲突可串行化(conflict serializable):若调度S与一个串行调度S*冲突等价,则S是冲突可串行化的。
|
|
|
|
在设计并发控制机制时,必须证明该机制产生的调度是否为可串行化的。为了确定一个调度S是否可串行化可以通过S构造一个有向图,也称优先图(precedence graph)。该图由G=(V,E)组成,其中,V是一个顶点集,由所有事务组成;E是一个边集,由满足下述三个条件的边Ti→Ij组成:
|
|
|
(1)在Ij执行Read(A)之前,Ti执行Write(A)。
|
|
|
(2)在Ij执行Write(A)之前,Ti执行Read(A)。
|
|
|
(3)在Tj执行Write(A)之前,Ti执行Write(A)。
|
|
|
如果优先图中存在边Ti→Tj,则任何等价于S的串行调度S'中,Ti必出现在Tj之前。
|
|
|
例如,调度S1(参见上图(a))优先图如下图(a)所示,图中只有一条边T0→T1,因为T0的所有命令均在T1之前执行;调度S2(参见上图(b))优先图如下图(b)所示,图中只有一条边T1→T0,意味着T1的所有命令均在T0之前执行。
|
|
|
|
|
但对调度S4(参见下图(b)),其优先图如上图(c)所示,由于T0执行Read(A)先于T1执行Write(A),所以优先图中有一条边T0→T1;又因为T1执行Read(B)先于T0执行Write(B),所以优先图中有一条边T1→T0。
|
|
|
|
|
如果调度S的优先图中有环,则调度S是冲突不可串行化的;如果图中无环,则调度S是冲突可串行化的。
|
|
|
可见,要判定冲突是否可串行化,首先需要构造有向图,然后调用环检测算法进行判定。有关环检测算法可参见相关书籍。
|
|
|