数据库7DB System

1、1数据库系统与应用并发控制并发控制数据库恢复技术21. 并发控制概述并发控制概述2. 事务模型3. 事务调度与可串行性4. 基于锁的并发控制协议3并发控制技术数据库系统一般可以分为单用户和多用户系统两种。 在任何时刻只允许一个用户使用的数据库系统称为单用户数据库系统。 允许多个用户同时使用的数据库系统称为多用户数据库系统。多数数据库系统都是多用户系统。 例如飞机订票数据库系统、银行数据库系统等4并发控制概述 在一个多用户数据库系统中，数据库中存储的数据项是用户程序存取的基本信息资源。一个存取或改变数据库内容的程序的运行称为一个数据库事务，简称事务。多个事务可同时运行并同时要求存取或修改同一个数

2、据库记录。如果不对并发运行的事务加以适当的控制，则会引起很多问题。5并发控制概述以飞机订座数据库系统为例： 每个航班对应一个数据库记录。每个记录包括对应航班已经预订的座位数和一些其他信息 设X和Y分别是航班A1和A2对应的数据库记录。 事务T1取消航班A1上已经预订的N个座位，并为航班A2增加N个预订座位. 事务T2为航班A1增加M个座位。 6并发控制概述T1READ(X)X:=X-NWRITE(X)READ(Y)Y:=Y+NWRITE(Y)T2READ(X)X:=X+MWRITE(X)数据更新丢失问题7并发控制概述T1READ(X)X:=X-NWRITE(X)READ(Y)Y:=Y+NWRI

3、TE(Y)T2READ(X)X:=X+MWRITE(X)临时值问题8并发控制概述T1READ(X)X:=X-NWRITE(X)READ(Y)Y:=Y+NWRITE(Y)T2READ(X)X:=X+MWRITE(X)错误聚集计算问题 9并发控制概述T1READ(X)X:=X-NWRITE(X)READ(Y)Y:=Y+NWRITE(Y)T3SUM=0READ(A)SUM=SUM+AREAD(X)SUM=SUM+XREAD(Y)SUM=SUM+Y1. 并发控制概述2. 事务模型事务模型3. 事务调度与可串行性4. 基于锁的并发控制协议10并发控制技术一个存取或更改数据库的程序的运行过程称为数据库事务

4、，简称事务。事务是数据库应用程序的基本逻辑单位。 11事务模型任何事务都使用READ和WRITE操作存取数据库 READ(X, Y)的实现算法：1.确定包含数据项X的磁盘块的地址A；2.如果地址为A的数据不在主存缓冲区中，则把A所在磁盘块读入到主存缓冲区；3.从主存缓冲区中找到数据项X，存入程序变量Y。12事务模型任何事务都使用READ和WRITE操作存取数据库 WRITE(Y, X)的实现算法：1.确定包含数据项X的磁盘块的地址A；2.如果地址为A的磁盘块不在主存缓冲区中，则把A磁盘块读入主存缓冲区；3.把程序变量Y的值存入A磁盘块所在主存缓冲区；4.立即或以后把包含A磁盘块的缓冲区写到磁盘

5、存储器。13事务模型事务的原子性 事务中的所有操作要么全部被成功地完成而且这些操作的结果被永久地存储到数据库中，要么这个事务对数据库和其他事务没有任何影响。称这个性质为事务的原子性。 每个事务都必须满足原子性。14事务模型事务的原子性 事务原子性可能遭到破坏的因素有如下两个：1.多个事务并发运行时，不同事务的操作交叉运行。 数据库管理系统必须保证多个事务的交叉运行不影响这些事务的原子性。2.事务在运行中间被强行停止。 数据库管理系统必须保证被强行终止的事务对数据库和其他事务没有任何影响。 保证事务原子性的主要方法是“串行化串行化”方法。15 事务模型事务的状态16事务模型 事务的性质 1.原子

6、性原子性 事务是数据库系统运行的原子程序单元。每个事务的所有操作要么被全部成功地执行，要么一个也不被执行;2.数据库正确保持性数据库正确保持性 一个事务的正确执行必须把数据库从一个正确状态转换为另一个正确状态;3.操作结果永久保持性操作结果永久保持性 如果一个事务使数据库发生了改变，而且该事务已经进入提交状态，则这些改变将不会因以后的失败而丢失;4.独立性独立性 一个事务在进入提交状态之前，它对数据库的更新不可由其他事务读取。这个性质避免了上节讨论的临时值问题，也避免了后边将讨论的嵌套回滚处理问题;5.可串行性可串行性 并发运行的多个事务的运行效果与这些事务按某种次序顺序运行的效果相同.17事

7、务模型1. 并发控制概述2. 事务模型3. 事务调度与可串行性事务调度与可串行性4. 基于锁的并发控制协议18并发控制技术设T0和T1是两个事务。 事务T0从帐号A转50元钱到帐号B。 事务T1把帐号A的存款的10%转到帐号B。19事务调度与可串行性 T0:READ(A);A := A - 50;WRITE(A);READ(B); B := B + 50; WRITE(B) T1:READ(A);tmp := A0.1;A := A-tmp;WRITE(A);READ(B);B := B+tmp;WRITE(B) 设帐号A和帐号B目前的存款分别是1000元和2000元。调度1：20事务调度与可

8、串行性 A和B的最终值分别是855和2145元，A+B在两个事务执行结束时仍然是1000+2000。设帐号A和帐号B目前的存款分别是1000元和2000元。调度2：21事务调度与可串行性这种调度方法的运行结果与第一种调度方法的运行结果不相同，这时A的最终值是850元而B的最终值是2150元，但A+B在两个事务执行结束时仍然是1000+2000。定义1 N个事务的一个调度S是N个事务的所有操作的一个序列，表示这些操作的执行顺序，并且满足对于N个事务中的每个事务T，如果操作i在T中先于操作j执行，则在S中操作i也必须先于操作j执行。前面的调度1和调度2是两个最简单调度，即一个事务的所有操作都执行完

9、后才执行另一个事务的所有操作。称这样的调度为串行调度，表示了事务的串行运行。称其他类型的调度为并行调度。22事务调度与可串行性一个并行调度的例子执行结果与调度1相同。23事务调度与可串行性另一个并行调度的例子 执行结果错误，多了50元。24事务调度与可串行性并不是所有的并并不是所有的并行调度都具有与行调度都具有与串行调度相同的串行调度相同的效果效果调度的可串行性 每个事务独立运行时不会引起任何问题，串行调度一定产生正确的运行结果。但串行调度限制了系统并发性的发挥。 并行调度可能导致不正确的事务运行结果！ 希望并行调度能够和串行调度具有相同的效果，这需要确定具有串行调度效果的系统方法，即可串行性

10、理论。25事务调度与可串行性N个事务的调度S是可串行的如果S等价于一个串行调度。由于串行调度是正确的，所以一个并行调度S等价于一个串行调度意味着S是正确的。26事务调度与可串行性N个事务的调度S是可串行的如果S等价于一个串行调度。由于串行调度是正确的，所以一个并行调度S等价于一个串行调度意味着S是正确的。等价的概念： 调度的冲突等价性 调度的效果等价性 调度的状态等价性 27事务调度与可串行性一个并行调度等价于一个串行调度28事务调度与可串行性调度的冲突冲突等价性 设S是一个调度，S具有两个相继执行的操作Ii和Ij，Ii属于事务Ti，Ij属于事务Tj。 如果Ii和Ij涉及不同的数据项，可以交换

11、Ii和Ij的执行顺序，而不影响调度中任何操作的结果。 如果Ii和Ij涉及同一个数据项Q，则需要慎重考虑Ii和Ij的执行顺序。1.Ii=READ(Q)，Ij=READ(Q)2.Ii=READ(Q)，Ij=WRITE(Q)3.Ii=WRITE(Q)，Ij=READ(Q)4.Ii=WRITE(Q)，Ij=WRITE(Q)29事务调度与可串行性显然，只有当Ii和Ij都是READ操作时，它们的顺序才无关紧要。Ii和Ij冲突，如果它们是不同事务在同一数据项上的操作，并且至少有一个操作是WRITE。30事务调度与可串行性显然，只有当Ii和Ij都是READ操作时，它们的顺序才无关紧要。Ii和Ij冲突，如果它们

12、是不同事务在同一数据项上的操作，并且至少有一个操作是WRITE。31事务调度与可串行性32事务调度与可串行性等价等价33事务调度与可串行性等价等价定义2 如果一个调度S能通过一系列非冲突操作的执行顺序的交换变换成调度S1, 则称S和S1冲突等价。 定义3 称调度S是冲突可串行的，如果它冲突等价于一个串行调度。 34事务调度与可串行性一个非冲突可串行调度的例子：35事务调度与可串行性冲突可串行性的测试方法 S是一个调度，从S构造一个有向图G=(V, E)，称为S的前趋图，其中V是顶点的集合，由S中的事务组成，E是边的集合。(Ti, Tj) E当且仅当下面三个条件之一成立:1.Ti在Tj执行rea

13、d(Q)之前执行write(Q)2.Ti在Tj执行write(Q)之前执行read(Q)3.Ti在Tj执行write(Q)之前执行write(Q)36事务调度与可串行性37事务调度与可串行性38事务调度与可串行性冲突可串行性的测试方法:如果调度S的前趋图有回路，则S不是冲突可串行的。如果调度S的前趋图无回路，则S是冲突可串行的。39事务调度与可串行性1. 并发控制概述2. 事务模型3. 事务调度与可串行性4. 基于基于锁的并发控制协锁的并发控制协议议40并发控制技术一个保证可串行性的方法是在互斥的方式下存取数据项，即当一个事务存取一个数据项时不允许其他事务修改这个数据项。可以通过基于锁的并发控

14、制协议实现。41基于锁的并发控制协议锁的概念 锁是数据项上的并发控制标志。锁可以分为两种类型：1.共享锁 如果事务T得到了数据项Q上的共享锁，则T可以读这个数据项，但不能写这个数据项。共享锁表示为S2.互斥锁 如果事务T得到了数据项Q上的互斥锁，则T既可以读这个数据项，也可以写这个数据项。互斥锁表示为X42基于锁的并发控制协议 银行数据库系统的例子： 设A和B是两个帐号。事务T7从帐号B向帐号A转50元钱，事务T8显示帐号A和B的总金额。 T7: LOCK-X(B); T8: LOCK-S(A); READ(B); READ(A); B := B - 50; UNLOCK(A); WRITE(

15、B); LOCK-S(B); UNLOCK(B); READ(B); LOCK-X(A); UNLOCK(B); READ(A); DISPLAY(A+B)。 A := A + 50; WRITE(A); UNLOCK(A)。43基于锁的并发控制协议银行数据库系统的例子：设A和B的值分别是100和200元。 调度1： 两个事务串行执行，即或方式执行，T8总是显示300元的值。44基于锁的并发控制协议T7: LOCK-X(B); READ(B); B := B - 50; WRITE(B); UNLOCK(B); LOCK-X(A); READ(A); A := A + 50; WRITE(A)

16、; UNLOCK(A)。T8: LOCK-S(A); READ(A); UNLOCK(A); LOCK-S(B); READ(B); UNLOCK(B); DISPLAY(A+B)银行数据库系统的例子： 调度2： 事务T8错误地显示250元 出现这种情况的原因是T8所看到的是一个不一致的数据库状态。45基于锁的并发控制协议两段锁协议 两阶段锁协议要求每个事务分两个阶段进行数据项的加锁和解锁。 阶段1 加锁阶段。在这阶段，事务可以申请获得任何数据项上的任何类型的锁，但是不能释放任何锁。 阶段2 解锁阶段。在这阶段，事务可以释放任何数据项上的任何类型的琐，但是不能再申请任何琐。 每个事务开始运行后

17、即进入加锁阶段，申请获得所需要的所有锁。 当一个事务第一次释放锁时，该事务进入解锁阶段。进入解锁阶段的事务不能再申请任何锁。46基于锁的并发控制协议满足两段锁协议？47基于锁的并发控制协议数据库恢复技术并发控制数据库恢复技术48数据库恢复的必要性数据库恢复的必要性使用日志的数据库恢复技术 缓冲技术检测点49数据库恢复技术破坏事务原子性和引起系统故障的原因： 计算机系统故障 在事务运行过程中发生的软硬件故障。 事务或系统错误 事务中的某些操作或错误参数可能引起事务的失败，如零做除数、数溢出等。用户也可以通过某种方式终止事务的运行。 事务的强行终止 事务经常具有测试某些特殊情况发生的功能。当测试的

18、情况发生时，事务将被强行终止。如果一个事务违背了可串行性条件或几个事务处于死锁状态，相应的事务将被并发控制机制强行终止。 磁盘故障 在事务进行读写操作时，磁盘发生硬件故障。 其他原因 磁盘毁坏、电源故障、机房失火等意外情况。50数据库恢复的必要性数据库恢复的必要性使用使用日志的数据库恢复技术日志的数据库恢复技术 缓冲技术检测点51数据库恢复技术 银行数据库系统的例子： 设事务T从帐号A向帐号B转50元钱，A与B的初值分别是1000和2000元。 假设在事务T的执行期间，在WRITE(B)执行之前WRITE(A)执行之后发生系统故障。 由于主存内容丢失了，所以不知道事务T的状况如何。于是，当系统

19、恢复正常以后，可能选择如下的两个方法之一进行数据库恢复：1.重新运行事务T。如此做法将使A的值变为900美元，而不是950，数据库进入错误状态。2.不再运行事务T。这样，A和B的值分别是950和2000美元。数据库同样进入错误状态。52使用日志的数据库恢复技术银行数据库系统的例子： 显然上述两种简单的数据库恢复方法都不能保证数据库的正确性。 问题的根源在于：没有等到事务真正提交就已经修改了数据库。 正确的数据库恢复技术应该保证每个事务的原子性，即要么一个事务的所有操作结果都存入数据库，要么所有操作对数据库都无影响，决不允许部分操作的结果记入了数据库，而另一部分操作的结果却丢失了。53使用日志的

20、数据库恢复技术为了保证事务的原子性，在执行一个数据库更新操作时，可以首先把描述更新操作的信息写入日志日志，而不修改数据库本身。当事务提交时，再使用日志日志中存储的更新操作信息实现数据库的更新。54使用日志的数据库恢复技术数据库系统日志 记录有关事务的数据库操作信息的存储结构是数据库系统日志，简称日志。 使用如下的表示法表示各种类型的日志记录：1.：事务T已经开始。2.：事务T在数据项X上执行写操作。X在执行写操作之前的值为V1，执行写操作之后的值为V2。3.：事务T已经提交。55使用日志的数据库恢复技术无论什么时候，当一个事务执行完一个写操作WRITE(Q)，就应该在数据库被修改之前建立起描述

21、这个写操作的日志记录。需要时，既可以用日志记录中存储的Q的新值更新数据库中的Q，也可以根据日志记录中存储的Q的原始值把数据库中已经由WRITE(Q)操作改变的Q值恢复到WRITE(Q)执行之前的值。使用日志的数据库恢复技术1.推迟更新技术2.即时更新技术56使用日志的数据库恢复技术推迟更新技术 为了保证事务的原子性，在每个事务运行期间，推迟更新技术在日志中记录这个事务对数据库的所有更新操作，把所有数据库更新操作推迟到该事务提交时执行。 推迟更新技术必须遵循下述推迟更新协议：1.每个事务在到达提交点之前不能更新数据库。2.在一个事务的所有更新操作所对应的日志记录写入永恒存储器之前，该事务不能到达

22、提交点。57使用日志的数据库恢复技术推迟更新技术 当一个事务到达提交点时，称该事务进入部分提交状态。 推迟更新协议保证当一个事务部分提交时，这个事务的所有更新操作的信息都已记录在日志中。 当一个事务部分提交时，推迟更新技术可以使用日志中有关该事务的数据库更新操作的信息更新数据库。如果在一个事务部分提交之前异常结束或系统发生故障，日志中有关这个事务的信息将被删除。 58使用日志的数据库恢复技术事务T： 从帐号A向帐号B转50元钱。 A与B的初值分别是1000和2000元。59使用日志的数据库恢复技术 使用推迟更新技术执行事务T1.T开始执行时，在日志中写一个新记录。2.在日志中写入一个新记录，其

23、中，V1是X的原始值，V2是WRITE(X)要写入X的值。3.在日志中写一个新记录。4.然后，对于日志中每个型为的记录，把数据库中数据项X的值更新为V2。5.在进行数据库更新过程中，系统可能发生故障。必须保证在数据库更新过程开始之前，所有的日志记录都已经被写到永恒存储器上。这一步工作完成之后，数据库真正的被事务T更新，T进入提交状态。6.显然，推迟更新技术只要求新的数据项值。于是，前面介绍的日志结构中的原始值域可以省略。60使用日志的数据库恢复技术 考虑银行数据库系统： 事务T0从帐号A向帐号B转储50元钱：T0: read(A); A := A - 50; write(A); read(B)

24、; B := B + 50; write(B). 事务T1从帐号C支出100元钱： T1: read(C); C := C - 100; write(C).61使用日志的数据库恢复技术考虑银行数据库系统： 设A、B和C的初值分别是1000、2000、和700元，并且T0和T1按串行调度执行。日志中包含的有关T0和T1的信息如下：62使用日志的数据库恢复技术考虑银行数据库系统： 按照推迟更新协议，T0和T1的执行结果写入数据库和日志的一种顺序：63使用日志的数据库恢复技术使用日志，数据库恢复机制可以处理任何导致非永久存储器的信息丢失问题。 数据库恢复机制需要下边的操作：redo(T): FOR

25、日志中每个型为的记录 DO 把数据库中数据项X的值改为值V; ENDFOR. redo操作必须是幂等的，即执行多次和执行一次的效果相同。64使用日志的数据库恢复技术下文中“系统故障发生后”是指“系统发生故障并被修复以后”。当系统故障发生后，数据库恢复机制将考察日志，确定需要重做的事务T。 事务T需要重做当且仅当日志包含记录和。 于是，如果系统在事务T成功完成之后发生故障，日志中有关T的信息将被用来将数据库恢复到正确状态。65使用日志的数据库恢复技术事务T0和T1定义如前，而且按调度运行。66使用日志的数据库恢复技术假定系统在事务运行结束之前出现故障。 设故障恰好发生在T0的write(B)操作

26、的信息被写入日志之后。 在这种情况下，数据库恢复机构不必采取任何恢复行动，因为日志中没有提交记录。A和B的值仍然保持为1000和2000元。 67使用日志的数据库恢复技术假定系统在事务运行结束之前出现故障。 设故障恰好发生在write(C)执行之后。 这种情况下，数据库恢复机构需要执行redo(T0)操作，因为记录在日志中。当redo(T0)操作被执行之后，帐号A和B的值分别是950和2050元。帐号C的值仍然是700元。 68使用日志的数据库恢复技术 假定系统在事务运行结束之前出现故障。 设故障恰好发生在执行之后。 这种情况下，由于日志中包含两个提交记录和，数据库恢复机制必须执行redo(T

27、0)和redo(T1)。 这些操作执行完以后，帐号A、B和C的值分别是950、2050和600。 69使用日志的数据库恢复技术再考虑另一种情况： 正在恢复时又发生了第二次系统故障。 由于已经执行了一些redo操作，数据库发生了部分更新，但有可能并没将所有的数据库更新都记入数据库。 当系统的第二次故障到来时，恢复工作与上面的例子相同，对于日志中的每个提交记录，执行redo(Ti)。70使用日志的数据库恢复技术使用推迟更新技术的数据库恢复过程定义如下：1.从后向前扫描日志记录，建立两个事务表：一个表称为提交事务表，包含全部具有日志记录的事务T，即已提交的事务；另一个表称为未提交事务表，包括全部具有

28、日志记录, 但不具有日志记录的事务T，即尚未提交的事务；2.对于提交事务表中的每个事务T，执行REDO(T)；3.对于未提交事务表中的每个事务T，删除所有T的日志记录，放弃T，待以后重新启动执行。71使用日志的数据库恢复技术即时更新技术 即时更新技术允许事务直接更新数据库。处于活动状态的事务直接在数据库上实施的更新称为非提交更新。任何即时更新技术都必须遵循如下的即时更新协议：1.所有型日志记录安全地存储到永恒存储器之前，事务T不能不能更新数据库。2.所有型日志记录安全地存储到永恒存储器之前，不允许不允许事务T提交。 72使用日志的数据库恢复技术即时更新协议保证在系统故障发生时，每个运行事务的更

29、新操作的描述信息都安全地记录在日志中。一旦系统故障导致事务T失败，即时更新技术将根据型日志记录，把数据项X的值恢复为它的原始值V1。73使用日志的数据库恢复技术即时更新协议1.T开始执行时，记录被写到日志。2.在T运行期间，当T发出一个write(X)操作时，记录首先被写入日志，然后直接在数据库上执行write(X)。3.当T部分提交时，记录被写到日志。为了满足即时更新协议的要求，在WRITE(X)操作直接应用到数据库之前，有关这个操作的日志记录必须安全地写入永恒存储器。 74使用日志的数据库恢复技术仍以事务T0和T1为例说明即时更新技术。 设事务T0和T1按调度顺序执行。日志中有关这两个事务

30、的记录如下： 75使用日志的数据库恢复技术当T0和T1运行时，数据库和日志按照即时更新协议变化过程：76使用日志的数据库恢复技术 即时更新技术需要如下两个操作：(1) undo(T): FOR 日志中每个型为的记录 DO 把数据库中数据项X的值改为V1;ENDFOR(2) redo(T): FOR 日志中每个型为的记录 DO 把数据库中数据项X的值改为V2;ENDFOR undo和redo操作必须是幂等的，即执行多次和执行一次的效果相同。77使用日志的数据库恢复技术系统发生故障后，即时更新技术将调用如下的过程进行数据库的恢复处理：1.从后向前扫描日志记录，建立两个事务表：一个表称为提交事务表，包