知识卡片

普通读书笔记卡 · 5654.d.1.f.3.d · 生成模型:未记录

冲突图无环判定调度可串行化

理解等级:中级

数据库调度可把事务作为顶点,把跨事务冲突操作的先后关系作为有向边:不同事务访问同一对象且至少一次为写时,按实际先后建立依赖。若冲突图无环,就存在保持全部冲突次序的串行事务顺序。

这是冲突可串行化的判定,不只是最终写入值碰巧相同;图有环表示不满足该判据,也不能把此图当成锁等待图,直接据其环宣称已经死锁。本章只给判定用途,没有实现并发调度/回滚机制。

补充核验:MIT 6.033事务课程,冲突与冲突图部分(2026-11-06读取),明确同对象至少一写的冲突及无环等价条件。

这张卡片看不懂?

已有反馈 · 0 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    • · 查看原书依据

      冲突性可序列化的调度时序。冲突性可序列化的调度时序产生的结果与序列化调度时序产生的结果一致。为了确定一个调度时序是否为冲突性可序列化的,可以采用一个优先级图来定义各事务之间的关系。如果图不包含圈,则该调度时序就是冲突可序列化的。

    参考来源

    - 位置:《算法精解:C语言描述》第11章《第11章 图》(spine1321;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1288.html;u185-ch11-005)。 - 结论依据:185可序列化冲突完整应用段实读,MIT原始讲义相关定义和图判定补充准确建边条件;无真实交易、SQL或锁操作。 - 原始内容:冲突性可序列化的调度时序。冲突性可序列化的调度时序产生的结果与序列化调度时序产生的结果一致。为了确定一个调度时序是否为冲突性可序列化的,可以采用一个优先级图来定义各事务之间的关系。如果图不包含圈,则该调度时序就是冲突可序列化的。