数据库系统实现技术

1、数据库管理系统概述
（1）DBMS的基本功能：a. 数据库定义功能（DDL）：外模式、模式、内模式、完整性、安全保
密、索引、视图定义，定义存储在数据字典（系统目录），是DBMS运行的基本依据。
b. 数据操纵功能(DML):检索、插入、更新和删除操作。
c.数据存储和管理：
d.事务管理：并发和故障恢复。
e. 通信功能和数据转换功能等
（2）DBMS的程序模块：数据定义模块、数据操纵模块、数据库运行管理模块、数据库组织、存储
和管理模块、数据库建立、维护和其他方面模块。
（3）DBMS的层次结构：最上层是应用层位于DBMS核心之外。
(2)第二层是语言翻译处理层它处理的对象是数据库语言 SQL,
(3)第三层是数据存取层：该层处理的对象是单个元组。
(4)第四层是数据存储层。该层处理的对象是数据页和系统缓冲区。
(5)操作系统是DBMS的基础。提供的存取原语和基本的存取方法通常作为与DBMS存储层的接口。它
处理的对象是数据文件的物理块。

2、数据库管理系统的主要成分：
三个主要成分：存储管理器（负责外存和内存缓冲区管理）、查询处理器（DDL编译、安全定义和
查询、完整定义和控制、查询编译优化和执行）、事务管理器（ACID特性，事务管理、并发控制、日志管理和故障恢复）
存储管理器重要模块：存储管理、缓冲区管理、索引/文件/记录管理器
查询处理器重要模块：DDL编译器、查询编译器、执行引擎
事务管理器重要模块：事务管理、日志和恢复、并发控制。
缓冲区和锁表是DBMS管理的重要内存结构。
（1）存储管理器：负责管理的数据包括：目标数据、元数据、索引和日志等。
a.物理存储介质层次：高速缓冲存储器、主存储器、第二级存储器、第三级存储器，依次访问速度
降低，价格也降低。
其中高速缓冲存储器、主存储器为基本存储（易失性存储），第二级存储器(例如磁盘)称为辅助存
储器或联机存储器，第三级存储器（如磁带、光盘机）也叫脱机存储器。第二级和第三级存储器为
外存。
磁盘块为磁盘空间分配的基本单位，也是磁盘与主存传输数据的逻辑单元。
b. 数据组织: 一个数据库映为多个不同文件, 为了将不同大小记录组织在同一个磁盘块中，常采
用分槽的页结构，即块开始有块头（包括块中记录个数、块中空闲空间尾指针、记录的位置和大小
的数组）、中间为空闲区、尾部为分配的记录。
C. 缓冲区管理：缓冲区替换策略（最近最少使用LRU，先进先出FIFO、时钟算法、系统控制法等.
d.数据字典：存储关于数据库的描述信息。必须存储的目录信息包括：关系基本信息、用户信息、
索引信息和统计信息。
e. 索引结构：支持对所要求的数据进行快速定位的附加数据结构称为索引。
一个文件可以有多个索引，一个索引包括一个属性和多个属性（查找码或搜索码），以及对应记录
的位置。
顺序索引：查找码按顺序存储如B+树索引，在顺序索引中，如果对应的记录也按查找码排列，则称
为聚集索引（主索引）。
对单个关系中元组的查询可分为点查询和范围查询：
点查询：查询特定属性上指定值的元组，一般为查询结果为单个记录 比如 select * from 
student from s#=’001’
范围查询：查询给定属性值在指定范围的所有元组，一般查询结果为多个记录 select * from 
student from s# between ‘001’ and ‘009’
顺序索引支持点查询和范围查询，散列索引支持点查询，不支持范围查询（注意）
(2) 查询处理: 查询处理器最主要的模块查询编译器和查询执行引擎.
a.查询处理过程：分析查询语句语法（生成语法分析树，翻译为关系表达式，形成初始查询计划）、选择逻辑查询计划（生成逻辑查询计划树或扩展的关系代数表达式）、选择物理查询计划
（生成物理查询计划树）、查询执行。
逻辑查询选择：初始查个询计划转化为一个预期执行执行时间较小的等价计划过程。
b.选择逻辑查询计划和选择物理查询计划的步骤通称为查询优化。
物理查询计划选择常采用基于代价的查询计划选择方法（根据选定的逻辑查询计划派生多个不同物
理查询计划，并选择代价最小或接近最小的物理查询计划）。
关系代数表达式等价：选择运算对并、交、差具有分配律：
σP(E1 ∪ E2)=σP（E1）∪ σP（E2） σP(E1 ∩ E2)=σP（E1）∩ σP（E2）
σP(E1 - E2)=σP（E1）- σP（E2）
投影对并运算分配律：∏L（E1 ∪ E2）=∏L(E1) ∪ ∏L(E2)
c.查询执行:查询执行的最基本动作是关系运算的执行。选择运算的两种实现方式：全表扫描（依
次访问表中的每一块），索引扫描。
（3）事务管理
a.事务的概念:数据库的一些操作的集合通常是一个独立单元，这种具有独立性的逻辑单元即是事
务
b.事务的特性:
1)原子性(Atomicity )。事务的所有操作在数据库中是不可分割的，或全部反映出来或全部不反
映。
2)一致性( Consistency)。事务执行的结果必须是使数据库从一个一致性状态转变到另一个一致
性状态。即数据库中只包含成功事务提交的结果。
3)隔离性(Isolation)。事务的执行不能被其他事务所干扰，一个事务内部的操作及使用的数据对
其他并发事务是隔离的，互不影响。
4)持久性(Durability)。事务一旦提交并执行后，它对数据库中数据的改变是永久的。
事务特性：原子性（Atomicity）、一致性（Consistency）、隔离性（Isolation）、持久性（durability）。
原子性、持久性：事务管理器中故障恢复机制责任。一致性：应用程序员的责任。隔离性：事务管
理器中并发控制部件责任。
（4）事务的并发控制
a.事务的并发执行
并发执行时可能会破坏数据库的一致性，主要问题包括以下三方面：
1)丢失更新。 2)对未提交更新的依赖。（读脏数据） 3)不一致的分析。（不可重复读）
b.并发事务的调度
如果多个事务在某个调度下的执行结果与这些事务在某个串行调度下的执行结果相同，则称这个调
度为可串行化的调度。若用等价的概念来表示就是指某个调度等价于一个串行调度。
可串行化是多个事务并发执行的正确性准则。
事务的可恢复调度：对于每对事务Ti和Tj，如果Tj读取了Ti所写的数据，则Ti先于Tj提交。
级联回滚：一个事务导致依赖它的一系列事务回滚的现象。
无级联回滚（调度）：由于级联回滚导致大量工作撤销，所以对调度加以限制，避免级联回滚发
生，这样的调度为无级联调度。
可串行化且无级联（可恢复）调度保证数据库一致性，是我们所需要的。
（5）.封锁
在事务的并发执行过程中为保证数据库的一致性，常采用封锁的方法来限制其他事务对该事务数据
项的访问。对数据项加锁的方式主要有两种。
1)共享锁。如果事务T获得了数据项Q上的共享型锁(记为S)，则Ti可读Q但不能写e。
2)排他锁。如果事务Ti获得了数据项Q上的排他型锁(记为X)，则T既可读Q又可写Q。
注意：加了共享锁的数据项可以再加共享锁，不能加排他锁。
加了排他锁的数据项不能再加共享锁和排他锁。
简言之：共享锁与共享锁相容，与排他锁不相容
排他锁与任何锁不相容。
两阶段封锁协议保证可串行性，它要求每个事务分两个阶段提出加锁和解锁申请。可保证可串行
化。
1)增长阶段。事务可以获得锁，但不能释放锁。
2)缩减阶段。事务可以释放锁，但不能获得新锁。
两阶段封锁增强协议：严格两阶段封锁协议和强两阶段封锁协议
严格两阶段封锁协议：在遵循两阶段封锁协议下，要求事务的排他锁在事务提交后才能释放。
强两阶段封锁协议：在遵循两阶段封锁协议下，要求事务的所有锁在事务提交前不能释放。
两阶段封锁协议不能保证死锁发生。
（6）故障恢复
a.故障的类型
1)事务故障可分为逻辑错误和系统错误，它们都可能造成事务执行失败。事务没有达到预期的终
点。
2)系统故障：硬件故障或者是数据库软件或操作系统的错误，致使系统停止运行。主存储器内容丢
失，而外存储器完好无损。
3)磁盘故障。数据传送操作过程中由于磁头损坏或故障而造成的数据内容丢失。
b.基于日志的恢复
日志包括事务开始日志记录、更新日志记录、事务提交日志记录和事务终止日志记录。
登记日志记录原则：先写日志原则
发生事务故障后，事务故障恢复的步骤如下：
(1)反向扫描日志，查找该事务的更新记录C
(2)对事务的更新操作执行逆操作，将日志记录中的“改前值”写人数据库。
(3)反复进行直到恢复到该事务的开始日志，则事务故障恢复结束。
对于系统的故障恢复步骤如下：
(1)正向扫描日志文件，将在故障发生前提交的事务的标识记入REDO队列；将故障发生时尚未完成
的事务的标识记人UNDO队列。
(2)对UNDO队列中的事务进行反向扫描，执行逆操作。
(3)对REDO队列中的事务进行正向扫描，重新执行日志记录登记操作。
介质故障恢复：系统备份后，装入后备副本和日志副本，由系统恢复。