SQL ConcurrencyControl（并发控制）

Example：

• Schedule A

• Schedule B

• Schedule C

• Schedule D

• Schedule E

从数据约束一致性来看，模式A、B、C是可串行化的，D的结果显然不满足条件，但是更改一下D的运算，E就能通过数据约束一致性检查，所以从逻辑上讲模式D和E都是错误的，所以总结来说，判断一个调度是否正确，应该是检查调度中的read和write的执行顺序会不会导致数据约束不一致的可能。

Want schedules that are “good” , regardless of initial state and transaction semantics（与初始状态和事务语义无关）

Only look at order of read and writes

serial schedule（可串行化调度）

• Sd=r1(A)w1(A)r2(A)w2(A) r2(B)w2(B)r1(B)w1(B)

冲突操作形成了一个调度的环，说明是一个不可串行化的调度

• Sc=r1(A)w1(A)r2(A)w2(A)r1(B)w1(B)r2(B)w2(B)

调度C则无环，则说明是可以通过改变顺序，使它成为一个可串行化调度

Concepts

• Transaction: sequence of ri(x), wi(x) actions（事务：读写操作的动作顺序）
• Conflicting actions: r1(A) w2(A) 、w1(A) w2(A)、 r1(A) w2(A)（冲突操作：不同事务、至少包含一个写操作、同一个数据）
• Schedule: represents chronological order in which actions are executed（调度：展示动作执行的时间顺序）
• Serial schedule: no interleaving of actions or transactions（可串行化调度：事务的动作之间没有交叉）

Definition

• S1, S2 are conflict equivalent schedules if S1 can be transformed into S2 by a series of swaps on non-conflicting actions（S1、S2是冲突等价的，如果S1能够通过一系列非冲突操作转换成S2。冲突等价说明两个调度的结果是一样的）
• A schedule is conflict serializable if it is conflict equivalent to some serial schedule.（如果夜歌调度能够冲突等价另一个可串行化调度，那么说明这个调度是冲突可串行化的）

Precedence graph P(S) (S is schedule)

• Nodes: transactions in S
• Arcs: Ti -> Tj whenever

1. pi(A), qj(A) are actions in S
2. pi(A) < qj(A)
3. at least one of pi, qj is a write

Exercise:

What is P(S) for S = w3(A) w2(C) r1(A) w1(B) r1(C) w2(A) r4(A) w4(D) Is S serializable?

What is P(S) for S = w1(A) r2(A) r3(A) w4(A) ?

Lemma引理

• S1, S2 conflict equivalent => P(S1)=P(S2)
• Proof:

Assume P(S1) = P(S2) 存在Ti: Ti -> Tj in S1 and not in S2 =>S1 = …pi(A)... qj(A)… =>S2 = …qj(A)…pi(A)...（pi和qi顺序先后不同，或者不存在冲突操作） 存在矛盾S1, S2 not conflict equivalent

• Note: P(S1)=P(S2)

\neq >

S1, S2 conflict equivalent

Counter example: S1=w1(A) r2(A) w2(B) r1(B) S2=r2(A) w1(A) r1(B) w2(B)

Theorem定理

P(S1) acyclic

<= >

S1 conflict serializable

A locking protocol（锁协议）

Two new actions:

• lock (exclusive): li (A) （排它锁）
• unlock: ui (A) （解锁）

排它锁就是在同一时刻只允许一个事务拥有一个数据的排它锁

Three rules：

• well-formed transactions（良好的事务：对一个数据项，有加锁最后会解锁）
• legal（合法的：在对同一个数据项加锁和解锁中间没有其他事务对该数据进行操作）
• 两端锁协议（2PL）

遵守这三条规则，就一定是冲突可串行化的，，但是可能出现死锁的情况

deadlocked

Assume deadlocked transactions are rolled back（假设死锁会进行回滚）

• They have no effect（没有任何影响）
• They do not appear in schedule（不会出现在调度中）

Shared locks（共享锁/读锁）

共享锁允许不同事务对同一个数据项加多把锁 共享锁与共享锁之间的兼容的 共享锁与排它锁之间是互斥的

• well-fromed transcations
• legal

S = ....l-Si(A) … … ui(A) … 在加S锁和解锁之间，不能有其他事务对该数据项进行加X锁（两者是不兼容的）

S = ... l-Xi(A) … … ui(A) …（） 在加X锁和解锁之间，不能有其他事务对该数据项进行加S、X锁（X锁和X锁、S锁都是不兼容的）

• 2PL transactions

封锁协议

一级封锁协议：

在事务T修改数据之前必须要加X锁，知道事务结束后才释放

• 防止丢失更新的数据
• 不能保证防止可重复读、不能防止读到脏数据

二级封锁协议：

在一级封锁协议上加上，在事务T读取数据之前加上S锁，读完数据之后立即释放S锁

• 防止数据更新丢失
• 防止读脏数据
• 但是不能防止可重复读

三级封锁协议：

在一级封锁协议上加上，在事务T读取数据之前加上S锁，直到事务结束释放锁

• 防止数据更新丢失
• 防止读脏数据
• 防止可重复读