|
|
知识路径： > 数据库技术 > 事务管理 > 数据库的并发控制 > 并发操作、并发调度与并发控制 > 并发调度的可串行性 >
|
|
相关知识点：3个
|
|
|
|
|
冲突（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是冲突可串行化的。
|
|
|
