06-2 数据库系统的恢复和并发控制技术

6 数据库保护 数据库恢复 并发控制 数据库安全性 数据库完整性

1、事务的表示方法： 事务的表示方法： (X)表示事务 的读X操作； 表示事务T Ri(X)表示事务Ti的读X操作； (X)表示事务 的写X操作。 表示事务T Wi(X)表示事务Ti的写X操作。 事务T1(Read(B) A=B+1;write(A)), T1(Read(B); 例：事务T1(Read(B);A=B+1;write(A)), 事务T2(Read(A) B=A+1; T2(Read(A); 事务T2(Read(A);B=A+1;write(B)) 可以表示成： 可以表示成： T1:R1(B)W1(A) T2:R2(A)W2(B)2

例: 事务 T1:R1(X)R1(Y)W1(Y) 的执行顺序可表示为

R1(X) W1(Y) R1(Y) 符号→表示先于( , 符号 表示先于(<),即R1(X)先于 表示先于 先于 W1(Y)执行， R1(Y)先于 1(Y)执行，而 执行， 先于W 执行， 执行 先于 执行 R1(X)和R1(Y)的先后次序无关紧要。 的先后次序无关紧要。 和 的先后次序无关紧要3

2、冲突操作 如果两个操作来自不同的事务， 定义：如果两个操作来自不同的事务，它 们对同一数据单位进行操作， 们对同一数据单位进行操作，并且其中 至少有一个是写操作， 至少有一个是写操作，则称这两个操作 是相互冲突的或冲突操作。 是相互冲突的或冲突操作。 事务T 例：事务T0:W0(X)W0(Y)W0(Z) 事务T 事务T1:R1(X)R1(Z)W1(X) 则在这两个事务中有冲突操作： 则在这两个事务中有冲突操作： (X)与 (X)与 (Z)与 R1(X)与W0(X) W1(X)与W0(X) R1(Z)与W0(Z) 对于冲突操作不能同时执行， 对于冲突操作不能同时执行，哪个先执 哪个后执行由调度决定。 行，哪个后执行由调度决定。4

3、调度 、是一事务集， 设τ={T1,T2, …T n}是一事务集， τ 是一事务集 的一个调度S是一拟序集 是一拟序集( 的一个调度 是一拟序集(∑ ,<s)其中: 1) ∑说明 执行的操作正是 ， 说明S执行的操作正是 其中 说明 执行的操作正是T1, T2, …T n 的操作。 的操作。 , 2) <s 说明调度 遵守每个事务的操作的 说明调度S遵守每个事务的操作的 内部执行次序 3) 每对冲突操作的执行次序由 决定。 每对冲突操作的执行次序由S决定 决定。5

例如：考虑下列两个事务T0, T1W0(X) T0= W0(Y) W0(Z) T1= R1(Z) R1(X) W1(X)

T0, T1的拟序集表示为： 的拟序集表示为： , T0=({W0(X),W0(Y),W0(Z)},{}) T1 =({R1(X),R1(Z),W1(X)},{R1(X)< W1(X), R1(Z) <W1(X)})6

两个事务T 的调度可以表示为： 两个事务 0,T1的调度可以表示为：W0(X) S1= W0(Y) W0(Z) R1(Z) R1(X) W1(X)

S1=({W0(X),W0(Y) ,W0(Z) ,R1(X),R1(Z) ,W1(X) }, , {W0(X)< R1(X), W0(Z)< R1(Z), R1(X)< R1(Z) , , , R1(X)< W1(X), R1(Z) <W1(X)}) ,7

两个事务T 的调度可以表示为： 两个事务 0,T1的调度可以表示为：

W0(X) S2= W0(Y) W0(Z)

R1(X) W1(X) R1(Z)

S2=( {W0(X),W0(Y) ,W0(Z) , R1(X), R1(Z) , ( W1(X) },{W0(X)< R1(X)

, W0(Z)< R1(Z), , R1(Z)< R1(X) ,R1(X)< W1(X), R1(Z) <W1(X)}) )8

两个事务T 的调度可以表示为： 两个事务 0,T1的调度可以表示为：W0(X) S3= W0(Y) W0(Z) R1(Z) R1(X) W1(X)

S3=( {W0(X),W0(Y) ,W0(Z) , ( R1(X),R1(Z) ,W1(X) },{W0(X)< R1(X), , W0(Z)< R1(Z), R1(X)< W1(X), R1(Z) <W1(X)}) )9

例：给出事务T0,T1,T2,T3,T4的一个调度 给出事务W0(X) T0= W0(Y) W0(Z) R1(X) T1= R1(Z) W1(X) T4= W2(Y)10

W3(Y) T3= R3(Z) W3(Z)

R4(X) R4(Y) R4(Z)

T2= R2(X)

一个调度S1R1(X) W0(X) W0(Y) R1(Z) R2(X) W2(Y) W3(Y) R3(Z) W3(Z) R4(Z) R4(Y) W1(X) R4(X)

W0(Z)

请写出S1的拟序集11

4、串行调度如果在一个调度中， 如果在一个调度中，各个事务不交叉执 而顺序地串行执行， 行，而顺序地串行执行，这个调度被称 为串行调度。 为串行调度。

定义：如果调度S中的任意两个事务Ti和Tj,如 Ti和 定义：如果调度S中的任意两个事务Ti Tj,

果Ti的所有操作都先于Tj的所有操作，或者相反， Ti的所有操作都先于Tj的所有操作，或者相反， 的所有操作都先于Tj的所有操作 则称S 串行调度。 则称S为串行调度。

注意： 注意：在串行调度中每一个事务都是在下一个事务 开始执行之前提交。因此， 开始执行之前提交。因此，串行调度没有并发 性，故每一个串行调度都是一个正确的执行。 故每一个串行调度都是一个正确的执行。 12

5、并发调度如果在一个调度中， 如果在一个调度中，各个事务交叉地执 这个调度称为并发调度。 行，这个调度称为并发调度。

6、可串行化的调度如果一个事务集的并发调度与某一串行 调度是等价的， 调度是等价的，则称该并发调度是可串 行化的 。

定义：多个事务的并发执行是正确的，当且 定义：多个事务的并发执行是正确的，仅当其结果与按某一次序串行地执行它们 时的结果相同， 时的结果相同，称这种调度策略为可串行 化的调度。14

7、串行化定理 定理： 定理：一个调度S是可串行化的，当且仅 当它的串行图是无环的。 无环的。 无环的 串行图： 串行图： 设S是若干事务{T1,T2,…,Tn}的一个调度， S的串行图SG(S)是一个有向图，其构成 规则如下： 1)图中的结点表示事务 2)如果Oi和Oj是冲突操作，且Oi先于Oj 执行，则在图中有一条边Ti→Tj。15

R3(X) R1(X) W1(X) W1(Y) T2 R3(X) R1(X) W1(X) W1(Y) T2

W3(X) T3 T1 W3(Z) T3 T1

R2(X)

W2(Y)

R2(X)

W2(Y)

8、等价的串行调度：如果 、等价的串行调度：如果SG(S)是无环 是无环等价于SG(S)的任一拓扑排序。 的任一拓扑排序。 的，则S等价于 等价于 的任一拓扑排序

T3 T2 T1

拓扑排序为： T2,T1,T3

T2 T1 T3

拓扑排序为：T1,T3,T2 或为：T1,T2,T317

R1(X) W0(X) W0(Y) R1(Z) R2(X) W2(Y) W3(Y) W3(Z) 调度S的串行

图 调度 的串行图 R4(Z) 拓扑排序为： 拓扑排序为： R4(Y) W1(X) R4(X)

W0(Z)

R3(Z)

T1 T0 T2

T3 T4

T0,T2,T1,T3,T4 , , , , 或为： 或为： T0,T2,T3,T1,T4 , , , ,18

可串行化调度T1 T2 Read(A) Read(B) Read(C) Write(C) Read(D) Write(C) T3 Read(C) Write(D) Write(B)19

T3

T1

T2

1)某一事务在对数据进行读、写之前，先 )某一事务在对数据进行读、写之前， 要申请并获得对该数据的封锁。 要申请并获得对该数据的封锁。 2)在释放一个封锁之后，事务不再申请 )在释放一个封锁之后， 和获得任何其它封锁。 和获得任何其它封锁。 说明：规则 避免了两个冲突操作同时存 说明：规则1避免了两个冲突操作同时存 取同一数据。 规则2把每个事务分为两个 取同一数据。 规则 把每个事务分为两个 阶段：上升段和下降段。 阶段：上升段和下降段。上升 下降

每一事务只有得到全 部锁以后才放锁。 部锁以后才放锁。20

例：对事务T1和T2用两段锁协议加锁的过程 T1:R1(X)W1(Y) T2:W2(X)W2(Y)

Slock X Xlock Y Unlock X Unlock Y

Xlock X Xlock Y Unlock X Unlock Y21

本文来源：https://www.bwwdw.com/article/wbue.html