哈尔滨工业大学2010年考博专业课试题《数据库原理》

1、哈尔滨工业大学2010年春博士入学考试数据库原理试卷一、名词解释（15分，每小题3分） （1）无损联接（P122）称这个分解是满足函数依赖集的无损连接（2）函数的逻辑蕴含（3）多值依赖（4）函数依赖集F的闭包F+设R是一个具有属性集合U的关系模式，F是给定的函数依赖集合，由F推导出的所有函数依赖的集合，称为F的闭包，记作F+。（5）简要分析关系规范化的利弊关系模式规范化：把一个给定关系模式转化为某种范式的过程称为关系模式的规范化过程，简称规范化。关系模式规范化的主要方法是关系模式的分解，即把一个低一级范式的关系模式分解为若干个高一级范式的子关系模式，使这些子模式具有指定的某种范式。关系规范化的

2、目的是解决关系模式中存在的数据冗余、插入和删除异常、更新不一致等问题。规范化的程度越高，数据的冗余和更新异常相对减少，但由于联接运算费时，查询时所花的时间也就越多。因此，规范化的程度不是越高越好，而取决于关系运算的实际需求。在实际工作中，应根据具体情况权衡利弊，适可而止。一般来说，静态关系模式（数据加载之后，用户在这个关系上仅运行查询操作，不再进行更新、插入和删除等操作）只需具有第一范式形式，动态关系模式（用户经常在这个关系上进行更新、插入和删除等操作）至少具有第三范式形式。二、已知关系模式R的属性集合U=A，B，C，D，E，函数依赖集合F=AC，BC，CD，DEC，CEA，分解=R1(A，D

3、)，R2(A，B)，R3(B，E)，R4(C，D，E)，R5(A，E)，请验试是否具有无损联接性（15分）解：的无损联接性判断表结果如下表示RiABCDEADa1b12b31a4b15ABa1a2b31a4b25BEa1a2a3a4a5CDEa1b42a3a4a5AEa1b52a3a4a5由于表中不存在值为a1，a2，a3，a4，a5的行，所以分解具有无损联接性。三、什么是故障点、检查点、转储点？请按某次完整的故障恢复过程，描述这三者在故障恢复过程中的使用（10分）1. 数据库故障的种类及其恢复策略数据库系统可能发生的故障主要分为四类：事务故障、系统故障、介质故障和计算机病毒。（1）事务故障事

4、务故障是指事务在运行过程中由于种种原因未能运行到正常结束点前而被终止，通常分为：可预期的事务故障：应用程序可以发现并让事务回滚，撤销已做的修改操作，恢复数据库到正确状态。非预期的事务故障：这些事务故障不能由事务程序处理，如并发事务发生死锁而被撤销等。事务故障的恢复方法：恢复到事务未执行时的状态。反向阅读日志文件，找出该事务的所有更新操作，对每一项更新操作做它的逆操作，即强行回滚（ROLLBACK）该事务，这类恢复操作称为事务撤销（UNDO）。（2）系统故障系统故障是指造成数据库系统停止运行的任何事件，如操作系统、DBMS、硬件故障或突然断电等，使得系统需要重新启动，通常称为软故障（Soft C

5、rash）。系统故障影响正在运行的所有事务，但不破坏数据库。发生系统故障时主存内容，尤其是数据库缓冲区（在内存）中的内容都被丢失，所有运行事务都非正常终止。发生系统故障时，一些尚未完成的事务的结果可能己送入物理数据库，从而造成数据库可能处于不正确的状态。为保证数据一致性，需要清除这些事务对数据库的所有修改。恢复子系统必须在系统重新启动时让所有非正常终止的事务回滚，强行撤销（UNDO）所有未完成事务。另一方面，发生系统故障时，有些己完成的事务可能有一部分甚至全部留在缓冲区，尚未写回到磁盘上的物理数据库中，系统故障使得这些事务对数据库的修改部分或全部丢失，这也会使数据库处于不一致状态，因此应将这些

6、事务己提交的结果重新写入数据库。所以系统重新启动后，恢复子系统除需要撤销所有未完成事务外，还需要重做（REDO）所有己提交的事务，以将数据库真正恢复到一致状态。系统故障的恢复方法：对未完成的事务进行回滚，强行撤销（UNDO）所有未完成的事务；对已完成的事务提交，结果仍在缓冲区的事务重新提交。（3）介质故障介质故障称为硬故障（Hard Crash），是指外存故障，如磁盘损坏、磁头碰撞，瞬时强磁场干扰等。这类故障将破坏数据库或部分数据库，并影响正在存取这部分数据的所有事务。这类故障比前两类故障发生的可能性小得多，但破坏性最大。发生介质故障后，磁盘上的物理数据和日志文件被破坏，恢复策略是重装数据库，

7、然后重做已完成的事务。介质故障的恢复方法：首先，装入最新的数据库后备副本，使数据库恢复到最近一次转储时的一致性状态；对于动态转储的副本，还须同时装入转储开始时的日志文件副本，利用恢复系统故障的方法（重做REDO+撤销UNDO）将数据库恢复到一致性状态。其次，装入相应的日志文件副本，重做已完成的事务。最后，从故障开始点反向读日志文件，使数据库恢复到故障前那一刻的状态。（4）计算机病毒计算机病毒是一种人为的故障或破坏，是一些恶作剧者研制的一种计算机程序。恢复方法与介质故障的恢复方法相同。2. 数据库恢复技术数据库恢复的基本单位是事务。数据库恢复的基本策略是数据冗余和事务恢复，其中数据冗余是指数据备

8、用副本和日志文件，事务恢复是利用事务作为操作单位进行恢复。数据库恢复的基本思想：数据库系统通过记录日志和数据转储来建立冗余数据。日志记录了数据库的所有更新操作信息，所有故障的恢复都需要它。数据转储制作数据库的后备副本，这些副本与日志配合使用，用来实现介质故障恢复。数据库镜像在不同的存储介质上维护数据库的同步副本，也是建立冗余数据的一种方法。使用数据库镜像可以简化介质故障的恢复，但需要附加的存储设备。数据恢复可分两个方面：一是事务或系统故障的恢复；另一个是存储介质故障的恢复。对于事务和系统故障涉及的存储器主要是主存储器和高速缓冲存储器， 这两个存储器属临时存储器。当事务或系统发生故障时，临时存储

9、器上的数据要么被破坏，要么全部丢失。介质故障涉及的存储器主要是硬盘、软盘、磁带等 永久存储器。不管哪种故障恢复都必须借助日志文件，日志文件必须存放于理论上永远不会损坏的存储器上，称为永恒存储器。数据库恢复的基本方法有：定期备份数据库、建立日志文件、针对不同故障类型分别恢复。（1）基于日志的恢复技术日志是数据库管理系统用来记录事务对数据库相关历史操作的文件，是日志记录的序列，记录了每个事务的开始标记、结束标记和所有更新操作。不同的数据库系统采用不同的日志文件，这些日志文件主要包括以记录为单位的日志文件和以数据块为单位的日志文件两种。n 以记录为单位的日志文件登录的内容： 各事务的开始标记，用表示

10、。 各事务的结束标记，用表示事务已经提交。 各事务的所有更新操作。用表示T事务在数据对象X上执行的操作，其中V1、V2表示更新前后数据对象的值。n 以数据块为单位的日志文件登记的内容包括： 事务标识 被更新的数据块。日志文件的作用除进行事务故障的恢复和系统故障的恢复外，还用于存储介质故障的恢复。事务故障和系统故障都不破坏存储在磁盘上的数据库，可以使用日志进行数据库恢复。日志除可以用来进行事务故障恢复和系统故障恢复外，还可协助后备副本进行介质故障恢复。当数据库被破坏后，可重新装入后备副本把数据库恢复到转储结束时的正确状态，然后利用日志文件，把已完成的事务进行重做，对故障发生时候未完成的事务进行撤

11、销处理。因此，利用日志文件恢复数据库的方法如下图所示。图 利用日志文件恢复数据库说明：其中TaTb为静态转储阶段，从Ta时刻开始转储，到Tb时刻转储完毕。若Tf时刻发生故障，则重装后备副本，只能恢复到转储结束时刻，其后的事务必须重做。Ta为转储点，Tb为检查点，Tf为故障点，（2）基于检查点的恢复技术利用日志技术进行数据库恢复时，恢复子系统必须搜索日志，确定哪些事务需要重做（REDO），哪些事务需要撤销（UNDO）。一般需要检查所有日志记录，这样就带来两个问题：一是搜索整个日志将耗费大量的时间，二是很多需要重做（REDO）处理的事务实际上已经将它们的更新操作结果写到了数据库中了，然而恢复子系统

12、又重新执行这个操作，也会浪费大量时间。数据转储：定期对数据库进行复制或转储（Dump）。注意几个概念：静态转储、动态转储、海量转储和增量转储。转储是指DBA定期将整个数据库复制到永久存储器的过程，这些备用的数据文本称为后备副本或后援副本。一旦系统发生介质故障，数据库就遭到破坏，可以将后备副本重新装入，但重装后备副本只能将数据库恢复到转储时的状态，要想恢复到故障发生时的状态，还必须重新运行自转储以后的所有更新事务。转储按照转储时的状态分为静态转储和动态转储。静态转储：是指在系统中无运行事务时进行的转储操作，转储操作开始时，数据库处于一致性状态，转储期间不允许对数据库的任何存取和修改，得到的是一个

13、数据一致性的副本。动态转储：是指转储期间允许对数据库进行存取或修改操作，即转储和用户事务可以并发执行。它不用等待正在运行的用户事务结束，必须把转储期间各事务对数据库的修改记下来，建立日志文件。这样，后备副本加上日志文件就能把数据库恢复到某一时刻的正确状态。采用动态转储必须借助日志文件，把转储期间的存取活动登记下来作为后援副本，方能保证恢复到转储结束时刻的正确状态。转储又可分为海量转储和增量转储。海量转储每次转储全部数据库；增量转储指每次只转储上次转储后更新过的数据。从恢复角度看，使用海量转储得到的后备副本进行恢复一般说来更简单些。但如果数据库很大，事务处理又十分频繁，则增量转储方式更实用更有效

14、。完整数据库备份：完整数据库备份就是备份整个数据库。它备份数据库文件、这些文件的地址以及事务日志的某些部分（从备份开始时所记录的日志顺序号到备份结束时的日志顺序号）。差异数据库备份：差异数据库备份是指将从最近一次完全数据库备份以后发生改变的数据进行备份。如果在完整备份后将某个文件添加至数据库，则下一个差异备份将会包括该新文件。这样可以方便地备份数据库，而无须了解各个文件。事务日志备份：事务日志备份就是自从上一个事务以来已经发生了变化的部分。事务日志备份比完整数据库备份节省时间和空间，而且利用事务日志备份进行恢复时，可以指定恢复到某一个事务。文件组备份：文件组备份就是对数据库中的部分文件或文件组

15、进行备份。文件组是一种将数据库存放在多个文件上的方法。检查点（Check Point）：也称为安全点或恢复点，是一个数据库事件，它把修改数据从高速缓存中的脏缓存块中的数据写入磁盘的数据文件中，并更新控制文件和数据文件。检查点会创建一个已知的正常点，在数据库管理系统意外关闭或崩溃后进行恢复的过程中，数据库引擎可以从该点开始应用日志中所包含的更改。也就是说，数据库的检查点相当于一个触发器，当满足一定的条件时就会触发这个事件，这时高速缓存中的脏缓存块中的数据就会被写入到数据文件之中，合理设置检查点直接关系到数据的安全与数据库系统的性能。检查点是数据库和事务日志之间的同步点，在检测点上DBMS：（1）

16、拒绝接受新的事务请求；（2）停止正在处理的还未完成的一切事务；把缓冲区写入磁盘；（3）等待OS确认所有对数据库和日志的写请求都已完成（此时数据库和日志是同步的），接着，向日志写入一条检测点记录。当用户更新或者插入数据的时候，系统首先会将数据保存到数据缓存中，而不是直接存储到硬盘上。当用户更新或者插入数据的时候，数据库系统首先会将数据保存到数据的缓存区域，而不是直接存储到硬盘上的数据文件中。而等到满足一定条件的时候，系统就会将数据缓存区中的数据保存到硬盘的数据文件中，促使将数据缓存中的信息保存到数据文件中。即“检查点”将当前内存中已修改的页（称为“脏页”）和事务日志信息从内存写入磁盘，并记录有关

17、事务日志的信息。当数据库系统执行了一个检查点之后，系统会将所有的已经提交事务对数据库所做的全部写入到硬盘的数据文件中。也就是说，此时硬盘上的数据文件已经反映了数据库的一个完整的状态，用户先前对数据库所做的更改已经全部保存到了数据文件之中。此时如果发生了什么变故，但是数据库系统崩溃。由于数据库所的变化都已经保存到了数据文件之中，为此在进行数据恢复时只需要将数据库恢复到上一个检查点执行时刻即可，而不需要进行复杂的恢复操作。所以说，如果将这个检查点设置的比较短一点，即两个检查点发生的时间比较短，那么就可以减少数据库恢复所需要的时间。但是也并不是说检查点设置的越短越好，因为数据库的任何更改都及时保存到

18、数据文件中，如果检查点设置得太短必然会使数据库系统的性能会大打折扣。基于检查点的恢复技术在日志文件中增加一类新的记录检查点记录（检查点建立时所有正在执行的事务清单），增加一个重新开始文件（存储个检查点记录的地址），并让恢复子系统在登录日志文件期间动态维护日志。数据库恢复机制定期执行如下操作，保存数据库状态，建立检查点：n 将目前主存中的所有日志记录强行输出到外存储器；n 将所有缓冲区中被修改的数据块强行写入磁盘；n 把日志记录写入磁盘。在建立检查点时，不允许事务执行任何更新操作，如写缓冲块或写日志记录。建立检查点之后，所有在检查点之前发生的更新操作都已经输出到数据库中，尚未完成的事务都登记在检

19、查点记录中。这样，发生系统故障时，只需从最近的检查点记录开始扫描日志文件。对于事务故障，基于检查点的恢复过程和不使用检查点的恢复过程是相同。但对于系统故障，使用检查点技术可缩小日志的扫描范围，减少不必要的重做（REDO），提高系统故障恢复效率。当需要进行数据库恢复时，只需搜索日志文件，确定在最近创建的检查点之后开始执行或处于活动状态的事务，然后对这些事务执行重做（REDO）或撤销（UNDO）操作。数据库发生故障时有两种处理方法：如数据库已破坏，则由DBA装入最近备份的数据库然后利用“日志文件”执行REDO（重做）操作；如数据库未被损坏，但某些数据不可靠，则系统会自动执行撤销（UNDO）操作恢复

20、数据。事务故障的恢复事务恢复是指事务未运行至正常终止点前被撤消，此时应对该事务做撤消处理。事务故障的恢复由系统自动完成。发生事务故障时：（1）执行一个中止（ABORT）并撤销（UNDO）它对数据库的任何改变，即进行下面所述的“向后恢复”数据库；（2）清除它对其它事务的影响，即中止（ABORT）那些读了它的“脏数据”的事务。这又可能进一步引起事务的中止（ABORT），称为串联撤消过程；（3）撤销（UNDO）所有被撤消的事务对数据库所作的任何改变。系统故障的恢复系统故障的恢复由系统重新启动时自动完成，其恢复步骤如下：（1）正向扫描日志文件，找出故障发生前已经提交的事务，将其事务标识记入重（REDO

21、）队列，同时找出故障发生时尚未完成的事务，将其事务标识记入撤消（UNDO）队列；（2）对撤消队列中的各个事务进行撤消（UNDO）处理；（3）对重做队列中的各事务进行重做（REDO）处理。介质故障的恢复介质故障恢复的原理是利用存储在别处的冗余数据来重建数据库。所以介质故障的恢复涉及两个问题：一是如何建立冗余数据；二是如何利用冗余数据恢复数据库。最常用的技术是转储和登记日志文件。转储是DBA定期将整个数据库复制到磁带或另一个磁盘上保存起来。当数据库遭到破坏时，可以利用这些数据来恢复数据库，但只能恢复到转储时的状态，在这以后所运行的事务必须重新运行才能恢复到故障时的状态。日志文件的作用除进行事务故障

22、的恢复和系统故障的恢复外，还用于介质故障的恢复。在动态转储中，后援副本必须和日志文件结合起来才能有效地恢复数据库。在静态转储中，若数据库被破坏，必须先利用后备副本文件装入到上一次转储结束前的正确状态，然后再利用日志文件把已经完成的事务重新处理，使数据库恢复到故障前的某一时刻的正确状态。介质故障的恢复方法是重装后备数据库，然后重做已完成的事务，具体步骤如下：（1）装入最近的数据库后备副本，即故障前最后一次转储的数据库副本，使数据库恢复到最后转储时的一致性状态。（2）打开永恒存储器中的日志文件，正向扫描日志文件，找出故障发生时已经提交的事务的标识，将其记入重做队列，然后对重做队列中的所有事务进行重

23、做。这样便可把数据库恢复到故障前的某一时刻的一致性状态。不过按照这种方法进行恢复存在着严重的弊端：一方面需要搜索整个日志文件，耗费大量的时间；另一方面需要重做大量已经成功地将其更新操作结果写入数据库的事务，浪费极大。数据库镜像为了避免磁盘介质故障影响数据库的可用性，许多数据库管理系统提供了数据库镜像功能，用于数据库的恢复。即根据DBA的要求，DBMS自动把整个数据库或其中关键数据复制到另一个磁盘上，每当主数据库更新时，DBMS自动把更新后的数据复制到镜像磁盘上。一旦发生介质故障，系统自动切换到镜像磁盘上，避免了因介质故障而关闭系统。用户应用不用中断，也无须重装数据库后备副本，更不用重做转储后已

24、经做过的操作。另一方面，在没有出现故障的时候，数据库镜像还可以用于并发操作，即某一数据对象被加X锁时，其它用户要访问该数据对象不用等待，可从数据库镜像上读取。四、简述一级、二级、三级封锁协议，并分析每一级封锁协议解决了哪些数据不一致性问题，还存在哪些数据不一致问题（10分）（P277 范明数据库原理教程，P166 尹为民数据库技术及应用）事务的并发执行可能带来的数据不一致性：（1）丢失修改；（2）不可重复读；（3）读“脏”数据并发控制：用正确的方式调度并发操作，使一个用户事务的执行不受其它事务的干扰，从而避免造成数据的不一致性。避免数据不一致性的方法和技术主要是并发控制，如封锁（Locking

25、）技术、基于时间戳的并发控制技术等。封锁是事务T在对某个数据对象进行操作之前，先向系统发出加锁请求，加锁后事务T就对该数据对象有了一定的控制权，在事务T释放它的锁之前，其他事务不能更新该数据对象。基本的锁有两种：共享锁（S锁）和排他锁（X锁）。排他锁（X锁）：又称写锁，若事务T获得了数据对象Q上的排他锁，则事务T既可以读又可以写（修改）数据对象Q，但在事务T释放Q上的X锁之前，其他事务既不能获得Q上的S锁，也不能获得Q上的X锁。共享锁（S锁）：又称读锁，若事务T获得了数据对象Q上的共享锁，则事务T可以读但不能写Q，并且在事务T释放Q上的S锁之前，其他事务只能获得Q上的S锁，而不能获得Q上的X锁

26、。在事务T在数据对象Q上的排他锁保证了在事务T释放数据对象Q上的锁之前，其他事务既不能读取，也不能修改数据对象Q，即排他锁保护数据对象不被同时读或写；事务T在数据对象Q上的共享锁（S锁）保证了其他事务可以读数据对象Q，但在事务T释放Q上的S锁之前不能对数据对象Q做任何修改，即共享锁保护数据对象不被写，但可以同时读。三级封锁协议：在运用封锁技术对数据对象进行加锁时，对封锁方式约定的一些规则称为封锁协议。对封锁方式约定不同的规则，就形成了各种不同的封锁协议（Locking Protocol），其总共分为以下三级：（1）一级封锁协议：事务T在修改数据项Q之前必须对其加排他锁（X锁），直至该事务结束才

27、释放。事务结束包括正常结束（COMMIT）和非正常结束（ROLLBACK）。作用：一级封锁协议可以防止丢失修改，保证事务T是可恢复的。但由于在一级锁协议中，如果仅仅是读数据而不对其进行修改，是不需要加锁的，所以它不能保证可重复读和不读“脏”数据。（2）二级封锁协议：事务T在要读取数据项Q之前必须对其加S锁，读完后即可释放加在数据项Q上的S锁。此种封锁方式与一级封锁协议（事务T对要修改数据项Q必须先对其加X锁，直到事务结束才释放数据项Q上的X锁）共同构成了二级封锁协议。作用：二级锁协议可防止丢失修改及读“脏”数据；但在二级封锁协议中，由于读完数据后立即释放S锁，所以不能保证可重复读。（3）三级封锁协议：事务T在读取数据项Q之前必须先对其加S锁，在要修改数据项Q之前必须先对其加X锁，直到事务结束后才释放加在数据项Q上的所有锁。此种封锁方式与一级封锁协议联合构成了三级封锁协议。作用：在三级锁协议中，无论是读数据还是写数据都要等到事务结束才释放