第4章并发控制与查询优化

《第4章并发控制与查询优化》由会员分享，可在线阅读，更多相关《第4章并发控制与查询优化（34页珍藏版）》请在金锄头文库上搜索。

1、第第4章章 并发控制与查询优化并发控制与查询优化本本 章章 要要 点点 1.深刻理解事务的基本概念。 2.深入理解事务的调度，掌握判断并发调度的是否正确的可串行化准则。 3.了解封锁管理中活锁和死锁的概念以及避免、预防的方法。 4.并发控制是数据库系统实现范畴的一个重要问题。我们要了解并发操作带来的数据不一致现象，在此基础上深入理解保证并行调度可串行性和保证数据一致性的三级封锁协议。 5. 查询优化是数据库系统实现范畴的一个重要问题。在学会用SQL语言对数据库进行查询的基础上，了解数据库系统如何对查询进行优化，有助于在对查询的认识上实现从感性到理性的飞跃。 6. 深入理解查询优化的策略；掌握用

2、关系代数等价变换规则对关系代数查询表达式进行优化的方法 数据库系统一般可分为单用户系统和多用户系统。在任何一个时刻只允许一个用户使用的数据库系统称为单用户系统。允许多个用户同时使用的数据库系统统称为多用户系统。单用户系统一般仅限于微型计算机系统。多数数据库系统都是多用户系统。 数据库是一个共享资源，要供多个用户使用。如果事务程序一个一个地串行执行，一个事务必须等待正在执行的事务结束后才能执行，则会造成系统资源的浪费，对于访问密集型的数据，会严重影响系统响应速度，降低系统的性能。解决的办法就是使多个事务并发执行，但这种并行如果不加以限制，就可能会存取和存储不正确的数据，甚至破坏数据库的一致性和数

3、据库的完整性。并发控制就是一种在多用户的环境下，对数据库的并发操作进行规范的机制。其目的是为了避免对数据的丢失更新、读“脏”数据和不可重复读等，从而保证数据的正确性与一致性。并发控制机制的好坏是衡量一个DBMS性能的重要标志之一。 在关系数据库系统中，用户只需要告诉系统要做什么，而没有指出应该怎么做，因此系统有足够的灵活性作出存取路径等与查询效率直接相关的选择。由于数据库系统掌握了当前数据库的很多信息，所可以对用户的查询作出有效的优化，让用户查询拥有最高的效率。本章主要讨论查询优化的一般策略，关系代数的变换规则。 DBMS的并发控制是以事务为单位进行的。下面先介绍事务的概念。4.1 事 务4.

4、1.1 事务及其性质 事务是构成单一逻辑工作单元的操作集合。或者说：事务是在数据库上的一个或多个操作的序列。它必须以原子的方式执行，也就是说：所有的操作要么都做，要么都不做，是一个不可分割的工作单位。 并不是任意的数据库操作序列都可以定义为事务。事务一般具备下列四个性质。 原子性（Atomicity） 事务的原子性强调了一个事务是一个逻辑工作单元，一个整体，是不可分割的。一个事务所包含的操作要么全部做，要么全部不做，不允许出现失误致使部分执行的情况。 事务的原子性是由DBMS的事务管理子系统来实现的。 一致性（Consistency） 事务执行的结果必须是使数据库从一个一致性状态到另一个一致性

5、状态。通俗的说：就是数据符合我们的所有期望。如果事务执行过程中始终遵循“要么全做，要么全不作”的原则，一般可以保证事务的一致性。 这个性质通常是由编写事务程序的应用程序员完成的。它也可以由系统测试完整性约束自动完成。 事务的原子性和一致性密切相关。 到BCNF范式。在规范化过程中，逐渐消除存储异常，使数据冗余尽量小，便于插入、删除和更新。 隔离性（Isolation） 当两个或更多的事务并发执行时，它们的作用效果必须是相互独立，不能相互影响。也就是说：事务并发执行的效果应该和普通串行执行的效果完全相同。事务之间的隔离性一般是由并发控制子系统来实现的。 持久性（Durability） 事务的持久

6、性是指一旦事务成功完成，该事务对数据库所施加的所有更新都是永久的。即使以后系统发生了故障，也应该保留这个事务的执行过程。 事务的持久性是由DBMS的恢复子系统实现的。以上四个性质简称为事务的ACID性质。保证事务的ACID特性是事务处理的重要任务。4.1.2 事务的开始与结束1.开始事务 使用BEGIN TRANSACTION命令显式说明一个事务开始，它说明了对数据库进行操作的一个单元的起始点。在事务完成之前出现任何操作错误和故障，都可以撤销事务，使事务回退到这个起始点。2.结束事务 在SQL中，必须明确地结束一个事务，结束事务通常以下两种方式： 成功结束事务的命令是COMMIT TRANSA

7、CTION，它的作用是提交或确认事务已经完成，所以该命令也称作事务提交。也就是：把当前事务开始以后SQL语句所造成的数据库的任何改变都写到磁盘上，使之永远存放在数据库中。在COMMIT语句执行以前，当前事务中SQL语句对数据库造成的改变都是暂时的，对于其它事务可能可见也可能不可见。 撤消事务的命令是ROLLBACK TRANSACTION，即撤消在该事务中对数据库所做的更新操作，使数据库回退到事务的起始点。 即数据库不发生任何改变。4.1.3 事务的状态 为了更明确地描述事务的执行过程，一般将事务的执行状态分为5种，事务必须处于这5种状态之一。这5种状态是： 活动状态 部分提交状态 失败状态

8、中止状态 提交状态 我们可以在事务中执行如下的操作，以实现事务状态的转换： BEGIN_TRANSACTION：:开始运行事务，使事务进入活动状态。 END_TRANSACTION：说明事务中的所有读写操作都已完成，使事务进入部分提交状态，把事务的所有操作对数据库的影响存入数据库。 COMMIT_ TRANSACTION：标志事务已经成功地完成，事务中的所有操作对数据库的影响已经安全地存入数据库，事务进入提交状态，结束事务的运行。 ABORT_ TRANSACTION：标志事务进入失败状态，系统撤销事务中所有操作对数据库和其它事务的影响，结束事务的运行。 事务进入中止状态后，系统一般有两种选择

9、。一种是重启事务。另一种是杀死事务。 图4.1给出了事务的状态转换图。图4.1 事务的状态转换图4.2 事务调度与并发控制4.2.1 事务的调度 事务调度的一般概念。 调度（Schedule）：事务的执行次序。 串行调度（Serial Schedule）：多个事务依次串行执行，且只有当一个事务的所有操作都执行完后才执行另一个事务的所有操作。 并行调度（Concurrent Schedule）：利用分时的方法处理多个事务。 但是，对于N个事务进行并发调度，情况会变的复杂的多，它的调度方案远大于N！个，而且并发调度的结果有可能是错误的。4.2.2 并发控制 在实际应用当中，数据库是一个重要的共享资

10、源，不同用户可以在不同时间或相同时间使用数据库中的数据，即并发地使用数据库中的数据，就会产生多个事务同时存取同一数据的情况。若对并发操作不加控制，就可能会存取和存储不正确的数据，这样就可能带来一些问题。当多个事务中的多个事务并发执行时，极有可能无法保证事务之间的隔离性，并破坏数据库的一致性、正确性。因此，DBMS的一个重要任务就是要有一种机制去保证事务在并发的存取和修改数据的时候的完整性不被破坏，同时确保这些事务能正确的运行并取得正确的结果。并发控制机制就是一种在多用户环境下对数据库进行并发操作进行规范的机制，它的好坏是衡量DBMS性能的重要标志之一。 并发控制可以给对数据库的操作带来很好好处

11、，最明显的有以下两点： 1.改善系统的资源利用率 2.改善短事务的响应时间数据的不一致性并发控制操作虽然具有较高系统资源利用率和有利于短事务运行的特点，但是在并发执行的过程中如果不对并发执行的事务通过某种机制加以控制，将有可能产生数据的不一致性等问题。 所谓数据的不一致性是指同一数据不同的拷贝的值不一样。采用人工管理或文件系统管理数据时，由于数据被重复存储，当不同的应用使用和修改不同的拷贝时就很容易造成数据的不一致性。 经过大量实例分析，我们发现并发操作的不正确调度可能会带来三种数据不一致性。 丢失修改 读“脏”数据 不可重复读4.2.4 可串行化准则 假如事务都是串行运行的，一个事务的运行过

12、程完全不受其他事务的影响，只有一个事务结束（提交或者退回）后，另一个事务才能开始运行，那么就可以认为所有事务的运行结果都是正确的，。尽管这些事务假如以不同的顺序运行，可能会对数据库造成不同的影响。以此为判断标准，我们将可串行化的并发调度当作唯一能够保证并发操作正确性的策略。也就是说：假如并发操作调度的结果与按照某种顺序串行执行这些操作的结果相同，就认为并发操作是正确的。 可串行性看作是多个事务并发执行的正确性准则。 根据可串性化的准则，两个事务并发执行的结果只要和任意一种串性化执行的结果相同，就认为是正确的。*4.3 封锁管理 封锁是实现并发控制的一个非常重要的技术。4.3.1 封锁机制 1.

13、封锁的定义及类型 所谓封锁指的是事务T对某个数据对象（如关系、记录等）进行操作以前，先请求系统对其加锁，成功加锁之后该事务就对该数据对象有了控制权，在事务T释放它的锁之前，其他的事务不能更新此数据对象，只有事务T对其解锁之后，其他的事务才能更新它。 要实现灵活、正确的并发控制，需要多种类型的封锁，不同类型的封锁决定了一个事务对某个数据对象加锁以后能进行什么样的操作。数据库管理系统DBMS提供了基本封锁类型有两种：排它锁（Exclusive Lock 简记为X锁）以及共享锁（Share Lock 简记为S锁）。 若事务T对数据对象A加了X锁，则T就可以对A进行读取 以及更新（X锁因此又称为写锁）

14、；在T释放A上的锁X锁以前，任何其他事务都不能再对A加任何类型的锁，从而也不能读取和更新A。这是最严格的一类封锁。当需要对数据对象实施插入、删除或修改操作时，应该使用独占封锁。已经实施独占封锁的表，拒绝来自其他用户的任何封锁。 若事务T对数据对象A加了S锁，则T就可以对A进行读取，但不能进行更新（S锁因此又称为读锁）；在T释放A上的锁S锁以前，其他事务可以再对A加S锁，但不能加X锁，从而可以读取A，但不能更新 以丢失更改问题为例，实施封锁的基本思想是：当一个用户对一个表或记录进行更新时，封锁该表或记录，使其他用户不能在同一时刻更新相同的表或记录，迫使其他用户在更新后的基础上（而不是在更新前的基

15、础上）再实施另外的更新操作。如图4.9。图4.9 丢失更改到BCNF范式。在规范化过程中，逐渐消除存储异常，使数据冗余尽量小，便于插入、删除和更新。 2.封锁粒度 所谓封锁粒度是指封锁对象的大小。封锁的对象可以是逻辑单元，也可以是物理单元。 封锁粒度与系统的并发程度以及并发控制的开销息息相关。封锁粒度越大，系统中能封锁的数据对象就越少，可以同时进行的并发操作也越少，于是系统的并发程度越低；反之，封锁粒度越小，则系统的并发控制越高。换个角度来看，封锁粒度越大，并发控制的开销越少；封锁粒度小了，并发控制的开销就要增加了。因此，要对系统并发度和并发控制开销作一个认真的权衡，才能选择合适的封锁粒度。必

16、要的时候，可以在系统中提供不同粒度的封锁供不同的事务选用。4.3.2 活锁和死锁 在数据库管理系统DBMS利用封锁协议解决并发操作带来的数据不一致性问题，但也有可能引起活锁和死锁问题。 1.活锁 如果事务T1封锁了数据R，事务T2又请求封锁R，于是T2等待。T3也请求封锁R；当T1释放了R上的封锁之后，系统首先批准了T3的请求，T2仍然等待；然后T4又请求封锁R，当T3释放了R上的封锁之后，系统首先批准了T4的请求， ，这样T2有可能永远等待下去。 避免活锁最简单的方法是采用先来先服务的办法。当多个事务请求封锁同一数据对象时，封锁子系统按请求封锁的先后次序对事务排队，数据对象上的锁一旦释放就批

17、准申请队列中第一个事务获得锁。如图6.10（a）所示。 （a）活锁 （b）死锁图4.10 活锁和死锁示意图 避免活锁最简单的方法是采用先来先服务的办法。当多个事务请求封锁同一数据对象时，封锁子系统按请求封锁的先后次序对事务排队，数据对象上的锁一旦释放就批准申请队列中第一个事务获得锁。 2.死锁 指多个事务循环等待其他事务释放锁而陷入停滞状态，不借助于外力干预则无法解开的状态。换句话说，如果事务T1封锁了R1，T2封锁了R2，然后T1又请求封锁R2，因T2已封锁了R2，于是T1等待释放R2上的锁；接着T2又申请封锁R1，因T1已封锁了R1，T2也只能等待T1释放R1上的锁。这样就出现了T1在等待

18、T2，而T2又在等待T1的局面，T1和T2两个事务永远不能结束，形成死锁。如图4.10（b）所示。 目前，在数据库中解决死锁问题主要有两种方法：一种是采取一定措施来预防死锁的发生；另一种是允许发生死锁，但同时采用一定手段定期诊断系统中有无死锁，若有则解除之。 预防死锁通常有两种方法，一种叫一次封锁法。它要求每个事务必须一次将所有要用到的数据加锁，否则就不能继续执行。另一种叫顺序封锁法。它是预先对数据对象规定一个封锁顺序，所有事务都按这个顺序实行封锁。数据库系统中诊断死锁的方法与操作系统类似，一般使用超时法或事务等待图法。 超时法 等待图法4.3.3 两段锁协议 可串行性准则是并发事务正确性的准

19、则。这个准则规定，一个给定的并发调度，当且仅当它是可串行化的，才是正确的调度。两段锁协议是保证并发调度可串行性的封锁协议。 两段锁（Two Phase Locking，简称2PL）协议：把所有事务分成两个阶段对数据项加锁和解锁。 申请加锁阶段：事务可以申请加锁，但是不能解除任何已取得的封锁。 释放封锁阶段：事务可以释放封锁，但是不能申请新的封锁。 我们通常称遵守两段封锁协议的事务为“两段式事务”。可以证明，若并发执行的所有事务均遵守两段锁协议，则对这些事务的任何并发调度策略都是可串行化的。因此，所有的两段式事务，其并行执行的结果一定式正确的。 需要说明的是，事务遵守两段锁协议是可串行化调度的充

20、分条件，但不是必要条件。也就是说，若并发事务都遵守两段锁协议，则对这些事务的任何并发调度都是可串行化的；反之，若对并发事务的一个调度是可串行化的，却不一定保证所有事务都符合两段锁协议。4.3.4 三级封锁协议 前面介绍过三种数据不一致性：丢失修改、读“脏”数据以及不可重复读。三级封锁协议是保证数据一致性的封锁协议，它是通过选择不同的加锁类型和释放时间而不同程度地解决了这些问题。 1级封锁协议 2级封锁协议 3级封锁协议4.4 查询优化的一般策略 对于一个较复杂的查询要求，通常都可以用几种不同的表达式来表达，它们的结果应该是相同的，单质型的过程可能有很大差别。 我们希望在系统开销尽量销的情况下对

21、查询进行尽可能的优化，一般采用以下策略： 选择运算尽早进行。一般来说，将选择运算提前进行将最有效的优化查询所占用的时间和空间。应特别强调的是，当关系的元组数量很大，而内存有限时，每次只能连接部分元组，这样就需要把磁盘上的数据多次重复地读入内存，甚至还需要把中间结果暂时写入磁盘。而磁盘的读写要比CPU 的处理慢得的，因此减少对磁盘的访问对查询优化至关重要。 投影运算与选择运算进行。对同一个关系进行操作的投影和选择运算应该同时进行，这样可以避免重复的扫描该关系，从而节省了查询时间。 将笛卡儿积与随后的选择运算合并为连接运算。因为连接运算（尤其是自然连接）要比笛卡儿积运算所花的时间少很多。 投影运算

22、与其他运算同时进行。这样就不必为了删除关系的某些属性值而把关系再扫描一遍了。 寻找公共子表达式并将结果加以存储。如果有一个频繁出现的子表达式，其结果关系并不大，从磁盘读入这个结果关系所花的时间要比计算该子表达式所花的时间少，那么先计算该公共子表达式并将结果存储在磁盘上就能对查询起到优化作用。当查询的对象是视图时，定义视图的表达式就可看作式公共子表达式。 对文件进行预处理。对适当的属性预先进行排序或者建立索引将有助于快速有效地找到适当的元组。只要预处理所花费的时间仍然合算，那么这种优化策略还是有用的。4.5 关系代数的等价变换 第3章中介绍过关系代数语言，后面我们将要介绍的SQL查询语言。不管哪

23、种语言最终都可以转换成关系代数表达式，因此关系代数一直是本书研究的在重点，在本章也不例外。关系代数表达式的优化是查询优化的重要基础，所谓关系代数表达式的优化，就是按照一定的等价变换规则将其转换为查询效果更高的表达式，为此我们必须先了解等价的概念。 用相同的关系代替两个关系代数表达式中相应的关系，如果所得到的结果关系完全一样，则称两个关系代数表达式E1和E2等价，记作：E1 E2 。变换规则 常用的关系代数等价变换规则如下： 1.连接或笛卡儿积的交换律 E1 E2 E2 E1 2.连接或笛卡儿积的结合律 设E1 、E2和 E3是关系代数表达式，F1和F2是连接的条件，其中F1只涉及到E1和E2的

24、属性，F2只涉及到E2和E3的属性，则有：（E1 E2） E3 E1 （ E2 E3） 3.投影的串接律 设E为关系代数表达式，A，B为属性集，且A是B的子集，则有： A（B（E） A（E） 4.选择的交换/ 串接律 设E为关系代数表达式，F1和F2为选择的条件，则有： 4a. 选择的交换律 F1（ F2 （E） F2（ F1 （E） 4b. 选择的串接律 F1（ F2 （E） F2F1（E） 5.选择与投影的交换/串接律 5a. 选择与投影的交换律 设选择条件F只涉及属性A1，A2， ，An，则有 A1，A2， ，An （ F（E） F（A1，A2， ，An（E） 5b. 选择与投影的串接律

25、 设选择条件F中有不属于A1，A2， ，An的属性，B1，B2， ，Bm，则有：A1，A2， ，An （ F（E） F（A1，A2， ，An，B1，B2， ，Bm（E） 6.选择对笛卡儿积的分配律 如果选择条件F只涉及E1的属性，则有：F（E1 E2） F（E1） E2如果选择条件F = F1F2，且F1只涉及E1的属性，F2只涉及E2的属性，则有：F（E1 E2） F1（E1） F2（E2） 7.投影对笛卡儿积的分配律 设E1 和 E2是关系代数表达式，Ai（i = 1，2， ，n）是E1的属性，Bj（j= 1，2， ，m）是E2的属性，则有：A1，A2， ，An，B1，B2， ，Bm（E1

26、 E2） A1，A2， ，An（E1）B1，B2， ，Bm（E2）8.选择对并的分配律设E1 和 E2具有相同的属性。则有：F（E1 E2） F（E1 ） F（E2）9.投影对并的分配律设E1 和 E2具有相同的属性。则有：A1，A2， ，An （E1 E2） A1，A2， ，An （E1） A1，A2， ，An（E2）10.选择对差的分配律设E1 和 E2具有相同的属性。则有：F（E1 E2） F（E1 ） F（E2）小 结 本章的内容属于数据库范畴内较为深入、理论性较强的知识。要求理解事务、并发操作可能引起的问题以及解决的途径。 为了提高数据库的使用效率，必须允许多个用户并发地对数据库进行

27、查询、更新等操作，如果不对这种并发操作加以合理控制，容易造成并发操作结果出错、数据出现不一致性。并发操纵调度正确性的唯一准则是可串行化准则。为了保证数据库中数据的一致性，保证并发事务的可串行化调度，采用了封锁管理机制。采用不同的封锁协议，就能不同程度地解决并发操作调度可能出现的种种问题。本章介绍了保证并行调度可串行性的两段封锁协议和能够保证数据一致性的三级封锁协议。 查询优化属于数据库范围内较为深入，理论性较强的知识。关系数据库语言的级别较高，它不需要用户选择数据的存取路径，只需要用户提出“做什么”，不需要指出“怎么做”，这就给数据库管理系统提供了很大的自由度。系统可以并且必须选取存取策略，这就是查询优化对于系统而言既具有可能性，又具有必要性。所谓查询优化，就是以提高查询效率为目标，查询占用的时间及空间越少，查询效率越高，根据普遍的、行之有效的优化策略，按照关系代数变换规则对查询表达式进行变换，最后得到一个优化代价合理、查询效率较高的查询计划。