2022年数据库系统实现技术 .pdf

《2022年数据库系统实现技术 .pdf》由会员分享，可在线阅读，更多相关《2022年数据库系统实现技术 .pdf（6页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、数据库系统实现技术1.1 数据库管理系统概述数据库管理系统（Data Base Mangement System DBMS）是在操作系统支持下的一个复杂的和功能强大的系统软件，它对数据库进行统一管理和控制。1.11 数据库管理系统的基本功能数据定义功能：允许用户使用专门的数据定义语言来对数据库的结构进行描述，包括外模式，模式，内模式的定义，数据库完整性的定义，安全保密的定义，索引的定义，视图的定义等。这些定义存储在数据字典中，是DBMS 运行的基本依据。数据操作功能：支持用户使用表达能力强且易学易用的数据操作语言或查询语言来表达对数据库中数据所要进行的检索，插入，更新，删除操作，高效的执行用户

2、所表达的对数据库中数据的操作请求。数据存储和管理功能：支持对大量的，各种类型的数据进行组织，存储和管理工作，包括用户数据，索引，数据字典等的存储管理。事务管理功能：提供对事物概念的支持和事务管理能力。支持对数据的并发存取，即多个不同事务同时对数据进行存取，避免同时的访问可能造成的不良后果，并保证数据库具有从多种类型的故障中恢复的能力。其他功能：包括与网络中其他软件系统的通信功能，一个DBMS 与另一个DBMS 或文件系统的数据转换功能，异构数据库之间的互访和互操作功能，对新的高级应用提供支持的能力等。1.12 数据库管理系统的主要部分和各部分的功能数据库系统包括以下三部分：（1）存储管理器：高

3、效的利用辅助存储器来存放数据，并使得数据能够被快速存取。具体负责外存储器中的数据存储管理和访问，索引的建立和管理，内存中的缓冲区管理等。（2）查询处理器：高效的执行像SQL 这样非常高级的语言表达的数据查询和修改。具体负责 DDL 编译，数据安全性定义和安全性控制，数据完整型定义和完整性控制，查询编译，查询优化，查询执行等。（3）事务管理器：对并发执行的事务进行有效地管理，使之具有 ACID 特性。具体负责事务管理，并发控制，日志管理和故障恢复等。数据库系统的层次结构是：应用层，语言翻译处理层,数据存取层，数据存储层。1.2 存储管理1.21 物理存储介质简介物理存储器层次从上到下依次为：高速

4、缓冲存储器（数据库系统中不需要考虑），主存储器，第二级存储器（磁盘存储器）和第三级存储器（磁带存储器，自动光盘机）。在这个层次结构中，一种存储介质的层次越高，它的成本越贵，但是速度就越快。最快的存储介质称为基本存储。第二级存储器称为辅助存储器或联机存储器。层次结构中最底层的介质称为三级存储器，或脱机存储器。1.22 数据存储组织一个数据库被映射为多个不同的文件，在任意一个文件中只储存一个固定长度的记录（定长记录，更容易实现）；或者是使一个文件能容纳多种长度的记录（变长记录，更大的灵活性）。名师资料总结-精品资料欢迎下载-名师精心整理-第 1 页，共 6 页 -每个磁盘块的开始处有一个块头，包含

5、了：块中记录的数目块中空闲空间的末尾处一个由包含记录位置和大小的条目组成的数组实际记录从块尾处开始写入，所有空闲空间存在于块头数组的最后一个条目和第一条记录之间。123 缓冲区管理数据库系统中提高访问效率的一个重要手段是减少磁盘和内存之间传输的块的数目。减少磁盘访问次数的一种方法是在内存中保留尽可能多的磁盘块，尽可能使得要访问的磁盘块已经在内存中。内存中的这种区域，我们称为缓冲区。负责缓冲区空间分配的子系统称为缓冲区管理器。当数据库系统中的程序需要磁盘上的块时，它向缓冲区管理器发出请求。如果一个块已经在缓冲区中，缓冲区管理器将这个块在主存储器中的地址传给请求者。如果这个块不在缓冲区中，缓冲区管

6、理器首先在缓冲区中为这个块分配空间，如果需要的话，会把其它块移出主存储器，为这个新块腾出空间。被移出的块如果被修改过，则需要将它写回磁盘。然后缓冲区管理器把新块从磁盘读入缓冲区，并将这个块在主存储器中的地址告诉请求者。1.24 数据字典在数据库系统中，除了存储关系外，还需要维护关于数据库的描述信息，这里信息称为数据词典，或系统目录。系统必须存储的目录信息主要包括：关系的基本信息：关系的名字，每个关系中各个属性的名字，属性的域的长度，在数据库上定义的视图的名字和这些视图的定义，完整性约束，关系所使用的存储方法。用户信息：授权用户的名字，用于认证用户的密码或其他信息，用户的授权索引的描述：索引的名

7、字，被索引的关系的名字，构造的索引的类型统计信息：关系中每个元祖的字节数，每个关系中元祖的总数等。1.25 索引结构支持对于所需要的数据进行快速定位的附加的数据结构称为索引。一个文件上可以建立多个索引，每个索引都是基于文件中的一个属性或属性组来建立的，这个属性或属性组称作查找码(搜索码)。当查找条件是基于这样的属性提出时，系统可以利用索引快速的在文件中查找记录索引有两种类型：顺序索引：顺序索引按顺序存储搜索码的值，并将搜索码与包含该搜索码的记录关联起来。最常用的顺序索引是B+树索引。若包含记录的文件中记录之间的物理顺序按照某属性或属性组的值排列，则基于该属性或属性组所建立的顺序索引称为聚集索引

8、。可减少磁盘块I/O 次数。散列索引：散列索引将索引码值平均分布到散列桶中，每个值所属的散列桶是由一个函数决定的，该函数称为散列函数。顺序索引能有效的支持点查询和范围查询；散列索引能有效的支持点查询，但不支持范围查询。1.3 查询处理查询处理包括：将查询语句翻译为能在文件系统的物理层上使用的表达式，为优化查询进行各种转换，实际的查询执行。查询处理器的主要模块有：查询编译器和查询执行引擎。名师资料总结-精品资料欢迎下载-名师精心整理-第 2 页，共 6 页 -1.31 查询处理概述首先 语法分析器 检查用户查询的语法，构造该查询语句的语法分析树 表示，然后将其翻译成关系代数表达式。如果查询是用视

9、图形式表示的，翻译阶段还要用定义该视图的关系代数表达式来替换所有对该视图的引用。然后系统进行查询重写,将语法分析树转化为初始查询计划，这种查询计划通常表示为逻辑查询计划或扩展的关系代数表达式。然后初始查询计划被转换为一个预期所需执行时间较少的等价的计划。这个过程称为逻辑查询的计划选择。选择逻辑查询计划和选择物理查询计划的步骤通称为查询优化。可以简单的用磁盘块I/O 次数来度量磁盘上存取数据的代价。1.32 查询的执行查询的执行最基本的动作是关系代数运算的执行。而每一个基本的关系代数运算都有多种不同的实现算法。不同的实现算法适用于不同的情况。如：查询条件的类型不同，可利用的存取路径不同等；不同的

10、实现算法其执行代价也不同。扫描运算包括了全表扫描和索引扫描。1.33 查询优化查询优化包括逻辑查询计划选择和物理查询计划选择两个重要步骤：（1）逻辑查询计划选择不仅要考虑初始的由语法分析树转换成的关系代数表达式，还需要考虑其他可选的等价表达式。表达式转换的等价规则是将一个关系代数表达式转换为与之等价的另一个关系代数表达式的规则。查询优化器利用等价规则将一个表达式转换成逻辑上等价的但执行效率更高的另一个表达式。表达式转换时使用的启发式规则：A尽可能深的将选择推入表达式树中B 尽可能深的将投影推进树中，可以加入新的投影C 重复消除有时可以消去，或移到树中更方便的位置D某些选择可以与其下面得笛卡儿积

11、相结合，以便把运算对转换成连接（2）物理查询计划选择在将逻辑查询计划转换成物理查询计划时，需要给出查询如何被执行的具体细节，即不仅指名要执行的操作，而且指明这些操作执行的顺序，执行每步所用的算法，获得所存储数据的方式，数据从一个操作传递到另一个操作的方式等。系统通常采用基于代价的查询计划选择算法1.4 事务管理1.41 事物的概念和特性事务是构成单一逻辑工作单元的操作集合。不论有无故障，数据库系统必须保证事务的正确执行，即该事务的整个操作集合完全被执行，或属于该事务的操作一个也不执行。为了保证事务的正确执行，维护数据库的完整性，要求数据库系统维护一下事务特性：（1）原子性（Atomcity）:

12、事务的所有操作在数据库中要么全部正确反映出来，要么全部不反映。故障恢复机制的责任（2）一致性（Consistency）：事务的隔离执行（即没有并发执行的其他事务）保持数据库的一致性。应用程序员的责任（3）隔离性（Isolation）:尽管多个事务可以并发执行，但系统必须保证，对任一对名师资料总结-精品资料欢迎下载-名师精心整理-第 3 页，共 6 页 -事务 Ti 和 Tj 在 Ti 看来，Tj 或者在 Ti 开始前已经停止执行，或者在Ti 完成之后开始执行。这样，每个事务都感觉不到系统中有其他事务在并发的执行。并发控制保证.（4）持久性(Durability):一个事务成功完成后，它对数据库

13、的改变必须是永久的，即使系统可能出现故障。故障恢复机制的责任这些特性被称为ACID 特性。1.42 故障恢复（1）故障类型和系统对策系统可能发生的主要故障类型：A事务故障：逻辑错误：事务由于某些内部条件而无法继续正常执行，这样的内部条件如非法输入，找不到数据，溢出，或超出资源限制。系统错误：系统进入一种不良状态（例如死锁），结果事务无法继续正常执行，但该事务可以在以后的某个时间重新执行。事务故障意味着事务没有到达预期的终点，破坏了一致性，需要进行撤销或回滚。（UNDO）B系统故障：硬件故障，或者是数据库软件或操作系统的漏洞，导致系统停止运行，主存储器内容丢失，而外存储器仍完好无损。在系统重新启

14、动时恢复子系统必须重做(REDO)所有已提交的事务，以保证事务的持久性和数据库的一致性。C磁盘故障：由于数据传送操作过程中的磁头损坏或磁盘的局部故障造成磁盘块上的内容丢失。发生磁盘故障时，可以利用其他在磁盘上的数据拷贝，或三级介质上的备份来进行恢复。（2）基于日志的恢复保证在故障发生后仍保持数据库一致性以及事务的原子性的算法称为恢复算法，包括:a.在正常事务处理时采取措施，将数据库内容中的更新活动，保证有足够的信息可用于故障恢复。b.故障发生后采取措施，在数据库内容恢复到某个保证数据库一致性，事务原子性及持久性的状态。日志是 日志记录 的序列，它记录了数据库中的所有更新活动。日志记录主要有以下

15、几种，用于记录数据库的写操作和事务处理过程中的重要事件事务开始日志记录：表示事务的开始更新日志记录：表示事务对数据项的修改操作事务提交日志记录：表示事务的提交事务终止日志记录：表示事务的终止利用更新日志记录中的改前值可以进行UNDO,撤销已做的修改操作，将数据项恢复到修改以前的旧值；利用更新日志记录中的改后值进行REDO，重做已完成的操作，将数据项置为修改后的新值。登记记录的原则：登记的顺序严格按照事务的并发执行中各操作发生的实际顺序；必须先把日志记录写到外存的日志文件中，再把相应的数据库修改写到外存的数据库中。这称作先写日记的原则。事务故障恢复的步骤是：反向扫描日志文件，查找该事务的更新操作

16、。对该事务的每一个更新操作执行UNDO,即将日志记录中”改前值”写入数据库。名师资料总结-精品资料欢迎下载-名师精心整理-第 4 页，共 6 页 -如此处理下去，直到读到该事务的开始日志系统故障恢复的步骤是：正向扫描日志文件，找出在故障发生前已提交的事务，将其事务标识记入REDO 队列；找出在故障发生时尚未完成的事务，将其事务标识记入UNDO队列。对 UNDO 队列中的事务进行UNDO 处理，即反向扫描日志文件，对每一个需要UNDO 的事务的更新操作执行逆操作。对 REDO 队列中的事务进行REDO 处理，即正向扫描日志文件，对每一个需要REDO 的事务的更新重新执行日志记录登记的操作。1.4

17、3 并发控制（1）事务并发执行可能出现的问题当多个事务并发执行时，即使每个事务各自都正确的执行，数据库的一致性也可能被破坏。三个主要问题是：丢失更新：出现在两个事务同时进行修改操作时，只反映出后一个事务的修改，而丢失了第一个事务的修改操作。对未提交更新的依赖：（读脏数据）如果允许事务Ti 检索，甚至更新已被另一个尚未提交的事务Tj 更新过的数据项，就会引起对未提交更新的依赖问题。不一致的分析（不能重复读）：如读取的总和不一样等。（2）并发事务的调度如果并发执行的控制完全由操作系统负责，许多调度都是可能的，包括使数据库处于不一致状态的调度。保证事务的并发调度执行后数据库总处于一致状态是数据库系统

18、的职责。数据库系统中完成此任务的部件是并发控制部件。（3）可串行化如果多个事务在某个调度下的执行结果与这些事务的某个串行调度下的执行结果相同，则称这个调度为可串行化的调度。可串行化是多个事务并发执行的正确性准则。多个事务在某个调度下的执行是正确的，是能保证数据库一致性的，当且仅当该调度是可串行化的。S 与 S 调度等价的条件：A对于每个数据项Q，若事务 Ti 在调度 S中读取了Q 的初始值，那么在调度S 中 Ti 也必须读取Q 的初始值。B对于每个数据项Q，若事务Ti 在调度 S 中执行的READ(Q),并且读取的值是由 Tj 产生的，则在调度S 中 Ti 读取的值也必须是由Tj 产生的。C对

19、于每个数据项Q，若在调度S 中有事务执行了最后的写操作，则在调度S 中该事务也必须执行最后的.A 和 B 保证了在两个调度中的每个事务都读取相同的值，而进行相同的计算。C和 A，B 一起保证两个调度得到相同的最终系统状态。（4）可恢复性大多数数据库系统要求所有调度都是可恢复的。可恢复调度应该满足：对于每对事务Ti 和 Tj，如果 Tj 读取了由Ti 所写的数据项，则 Ti 先于 Tj 提交。无级联调度应满足：对于每对事务Ti 和 Tj，如果 Tj 读取了由Ti 所写的数据项，则 Ti 必须在 Tj 这一读取前提交。（5）基于封锁的并发控制并发控制最常用的方法是封锁的方法，即当一个事务访问某个数

20、据项时，以一定的方式锁住该数据项，从而限制其他事务对该数据项的访问。给数据项加锁的方式有两种：名师资料总结-精品资料欢迎下载-名师精心整理-第 5 页，共 6 页 -共享锁和排他锁。共享锁：如果事务Ti 获得了数据项Q 上的共享型锁（记为S），则 Ti 可读 Q，但不能写 Q 排他锁：如果事务 Ti 获得了数据项Q 上的排他型锁（记做 X），则 Ti 即可读 Q，又可写 Q 只有 S 和 S锁相容保证可串行性的一个协议时两阶段封锁协议，该协议要求每个事物分为两个阶段提出加锁和解锁申请。（1）增长阶段：事务可以获得锁，但不能释放锁（2）缩减阶段：事务可以释放锁,但不能获得新锁一开始，事务处于增长

21、阶段，事务根据需要获得锁，一旦该事务释放了锁，它就进入了缩减阶段，不能再发出加锁请求。两阶段封锁协议保证可串行性，对于任何事务，在调度中该事务获得最后加锁的时刻称为事务的 封锁点。将多个事务根据他们的封锁点进行排序，这个顺序就是事务的一个可串行化次序。严格两阶段封锁协议除了要求封锁是两阶段之外，还要求事务持有的所有排他锁必须在事务提交后方可释放。这保证未提交事务所写的任何数据在该事物提交之前均以排他锁方式加锁，防止了其他事务读这些数据。这样可以避免级联回滚。强两阶段封锁协议要求在事务提交之前不得释放任何锁。在强两阶段封锁条件下，事务可以按其提交的顺序串行化。两阶段封锁并不保证不发生死锁，发生死锁后系统必须能检测和排除它，即使一个陷入死锁的事务回滚，从而释放其拥有的锁。被终止的事务对数据库所作的任何改变必须撤销，这称作事务的回滚。名师资料总结-精品资料欢迎下载-名师精心整理-第 6 页，共 6 页 -