1. 并发控制

1.1 不一致性

• 丢失修改
• 不能重复读
• 脏读

2. 事务

2.1 概念

具有ACID特性的若干数据库
基本操作的组合体被称为事务。

2.2 特性

• 宏观独立完整
• 微观交错执行

2.3 ACID

• 原子性 Atomicity
• 一致性 Consistency
• 隔离性 Isolation
• 持久性 Durability

2.4 调度

一组事务的基本步(读、写、其他控 制操
作如加锁、解锁等)的一种执行顺序称为对这组事务的一个调度。

• 多个事务从宏观上看是并行执行的，但其微观上的基本 操
  作(读、写)则是交叉执行的。

2.5 冲突

调度中一对连续的动作：如果它们的顺序交换，那么涉及的事务中至少有一个事务的行为会改变。

• 有冲突的两个操作是不能交换次序的，没有冲突的两个事务是可交换的
• 同一事务的任何两个操作都是冲突的
• 不同事务对同一元素的两个写操作是冲突的
• 不同事务对同一元素的一读一写操作是冲突的

2.6 可串行性

如果不管数据库初始状态如何，一个调度对数据库状态的影响都和某个串行调度相同，则我们说这个调度是可串行化的(Serializable)或具有可串行性(Serializability)。

2.7 冲突可串行性

一个调度，如果通过交换相邻两个无冲突的操作能够转换到某一个串行的调度，则称此调度为冲突可串行化的调度。

• 冲突可串行性是比可串行性 要严格的概念。

• 满足冲突可串行性，一定满足可串行性；反之不然。

• 判别算法：

1. 构造一个前驱图(有向图)
2. 结点是每一个事务Ti。如果 $T_i$ 的一个操作与Tj的一个操作发生冲突，且Ti在 Tj前
   执行，则绘制一条边，由Ti指向Tj, 表征Ti要在Tj前执行。
3. 测试检查: 如果此有向图没有环，则是冲突可串行化的!

2.8 并发调度的正确性

当且仅当在这个并发调度下所得到的新数据库结果与分别串行地运行这些事务所得的新数据库完全一致，则说调度是正确的。

• 并发调度的正确性 $\supseteq$ 可串行性 $\supseteq$ 冲突可串行性

3. 基于封锁的并发控制方法

3.1 锁

• $L_i(A)$ : 事务 $T_i$ 对数据元素 $A$ 加锁
• $U_i(A)$ : 事务 $T_i$ 对数据元素 $A$ 解锁

1. 排他锁X (exclusive locks)：只有一个事务能读、写，其他任何事务都不能读、写

2. 共享锁S (shared locks)：所有事务都可以读，但任何事务都不能写

3. 更新锁U (Update locks)：初始读，以后可升级为写

4. 增量锁I (Incremental lock)：增量更新(例如A=A+x) 区分增量更新和其他类型的更新

3.2 封锁协议