冲突可串行化的判定：前趋图有向无环

并发调度是否”正确”，标准是它的执行结果是否等价于某个串行调度（一次 只跑一个事务）——但要判定这一点，不需要真的把所有可能的串行顺序 都拿来比对，而是先定义”冲突操作”（不同事务对同一数据的操作，其中 至少一个是写操作，这是唯一会因执行顺序不同而导致结果不同的操作 组合），再看这些冲突操作在实际调度里的先后顺序能不能通过”交换相邻 的非冲突操作”逐步整理成某个串行顺序（冲突等价）。这个判定过程被 进一步转化成一个图论问题：把每个事务当作前趋图里的一个节点，只要 事务A的某个操作与事务B的某个操作冲突、且A的操作先执行，就画一条 从A到B的边——一个调度是冲突可串行化的，当且仅当它的前趋图是有向 无环图。如果图里出现环，说明存在这样的矛盾：至少有一对冲突操作是 A先于B，又至少有一对冲突操作是B先于A，这种互相”抢跑”的关系无论 怎么交换非冲突操作的顺序都理不顺，因此不可能等价于任何一个串行 调度。这个判定方法虽然理论清晰，但实践中不可用：它要求整个调度的 所有操作都执行完才能画出完整的前趋图，而现实中事务是陆续到达、 执行、提交的，数据库不可能等一批事务全部结束后再决定它们的执行 顺序——这也是为什么实际系统要靠[[两阶段锁协议保证可串行化的机制]] 这类”边执行边约束”的协议，而不是靠事后判定。

结构图：

flowchart TD
    A[调度中的所有操作] --> B[识别冲突操作对<br/>同一数据+至少一个写操作]
    B --> C[构造前趋图<br/>Ti先于Tj的冲突操作→画一条Ti到Tj的边]
    C --> D{前趋图是否有向无环}
    D -->|是| E[冲突可串行化<br/>拓扑排序得到等价串行顺序]
    D -->|否, 存在环| F[非冲突可串行化<br/>执行结果不正确]