1、冲突可串行化的判定 一.问题的提出 在数据库工程师的考试中，对事务的并发操作多次考到，且占有很高的分值。这部分知识学习不难，但考试得分不高，纠其原因是不太理解。在设计并发控制机制时，必须保证由该机制产生的调度是可串行化的。在此我们只讨论冲突可串行化的判定。二. 冲突可串行化的判定判定方法分为两个步骤：- 步骤 1：产生调度的优先图;- 步骤 2：采用一个合适的算法(如基于深度优先或广度优先的环检测算法，这是图论课程中的内容) 检查优先图中是否有有向环。如果有，则该调度就不是冲突可串行化的，否则就是冲突可串行化的。设 S 是一个调度，由 S 构造一个有向图，称为优先图。该图由两部分 G=(V,E
2、)组成，其中 V 是顶点集，E 是边集。顶点集由所有参与调度的事务组成。边集由满足下列三个条件之一的边 TiTj 组成：-Ti 的 write(Q)在 Tj 的 read(Q)之前执行;-Ti 的 read(Q)在 Tj 的 write(Q)之前执行;-Ti 的 write(Q)在 Tj 的 write(Q)之前执行;如果有向图中存在边 TiTj ，则在任何与 S 等价的串行调度 S中，Ti 都必须出现在 Tj 之前，即如下所示：。注意，在画优先图时，不管有多少对冲突的指令使得存在有向边 TiTj，在优先图中只画一条从 Ti 到 Tj 的边，而不是多条。1 、示例 1:调度 1 如图 1 所示
3、：图 1：并发调度 1它的优先图构造如下：图 2：并发调度 1 的优先图因此调度 1 等价于串行调度。2 、示例 2 调度 2 如图 3 所示：图 3：调度 2 它的优先图构造如下：图 4：调度 2 的优先图因此调度 2 等价于串行调度。3 、示例 3并发调度 3 如图 5 所示：图 5：调度 3它的优先图构造如下：图 6：调度 3 的优先图因为存在有向环，所以调度 3 不是冲突可串行化的。4 、示例 4假设并发调度 4 的优先图如图 7 所示，由于图中不存在有向环，因此它是冲突可串行化的。根据图可以确定在串行调度中 Ti 排在最前， Tm 排在最后。因此调度 4 等价于串行调度：或。图 7：调度 4 的优先图
