第六章 关系数据理论

关系模式 STUDENT（Sno, Sdept, Mname, Cno, Grade）中存在的问题

1. 数据冗余度太大，浪费存储空间。如系主任的名字Mname重复出现，其重复的次数与该系所有学生的所有课程成绩出现次数相同
2. 更新异常。数据冗余，更新数据时维护数据完整性代价大。如果更换系主任，系统必须修改所有与该系学生有关的每一个元组。
3. 插入异常，该插入的数据插不进去。如果新成立一个软件工程系，还没有招生，就无法把这个系及其系主任的信息存入数据库。
4. 删除异常，不该删除的数据也删除了。如果某个系得学生全部毕业，我们在删除该系学生信息的同时，把这个系及其系主任的信息也丢掉了。

解决办法：把这个单一模式分成 3 个关系模式： S(Sno, Sdept, Sno->Sdept); SC(Sno, Cno, Grade, (Sno, Cno)->Grade); DEPT(Sdept, Mname, Sdept->Mname); 这 3 个模式不会发生插入异常、删除异常毛病;数据冗余得到控制。

什么是一个好的模式

好的模式不会发生插入异常、删除异常、更新异常、数据冗余应应可能少。 问题的原因：模式中的某些数据依赖引起

什么是数据依赖

完整性约束的一种表现形式

• 限定属性取值范围：例如学生成绩必须在 0-100 之间
• 定义属性值之间的相互关联（主要体现于值的相等于否），即通过属性间值得相等于否来描述
• 是数据库模式设计的关键

数据依赖

• 是通过一个关系中属性间值的相等与否体现出来的数据间的相互关系
• 是现实世界属性间相互联系的抽象
• 是数据内在的性质
• 是语义的体现

数据依赖的主要类型

• 函数依赖(Functional Dependency，简记为 FD)
• 多值依赖(Multivalued Dependency，简记为 MVD)
• 连接依赖

数据依赖对关系模式的影响

• 不合适的数据依赖会造成插入异常、删除异常、更新异常和数据冗余问题。

关系模式

关系模式的形式化定义R(U, D, DOM, F)

• R：关系名，是符号化的元组语义
• U：该关系的属性集合
• D：属性组 U 中属性所来自的域
• DOM：属性向域的映象集合
• F：属性间数据的依赖关系集合

关系模式的简化表示R<U, F>

• 将关系模式简化为一个三元组，影响数据库模式设计的主要是 U 和 F

关系模式 STUDENT<U,F>
U = { Sno,Sdept,Mname,Cno,Grade }
F =｛ Sno→Sdept, Sdept→Mname, (Sno, Cno)→Grade｝
STUDENT（Sno,Sdept,Mname,Cno,Grade, Sno→Sdept, Sdept→Mname,(Sno, Cno)→Grade）

如何解决关系模式中存在的问题

规范化理论—找出关系模式种不合适的数据依赖，消除它们，可以在不同程度上解决插入异常、删除异常、更新异常和数据冗余问题。

函数依赖

函数依赖定义

设 R(U)是一个属性集 U 上的关系模式，X 和 Y 是 U 的子集。若对于 R(U)的任意一个可能的关系 r，r 中不可能存在两个元组在 X 上的属性值相等， 而在 Y 上的属性值不等则称“X 函数确定 Y”或“Y函数依赖于X”，记作X→Y。 X 称为这个函数依赖的决定属性组，也称为决定因素(Determinant)。

例： S(Sno, Sname, Ssex, Sage, Sdept)
F＝ {Sno→Sname，Sno→Ssex，Sno→Sage，Sno→Sdept}

如何确定函数依赖

• 函数依赖是语义范畴的概念。只能根据数据的语义来确定函数依赖。 如Sname →Sno函数依赖只有在“学生不允许有重名”的条件下成立。

• 数据库设计者可以对现实世界作强制的规定。 例如设计者可以强行规定不允许学生有重名，因而使函数依赖Sname →Sno，Sname →Ssex， Sname →Sage，Sname→Sdept成立。

• 函数依赖是指关系模式 R 在任何时刻的关系实例均要满足的约束条件。 不是指某个或某些关系实例 r 满足的约束条件，而是指R的所有关系实例 r 均要满足的约束条件。

平凡函数依赖

• X→Y，Y⊈X，则称 X→Y 是非平凡的函数依赖。
• X→Y，但 Y⊆X ，则称 X→Y 是平凡的函数依赖。

例：在关系SC(Sno, Cno, Grade)中，
非平凡函数依赖： (Sno, Cno) → Grade
平凡函数依赖： (Sno, Cno) → Sno (Sno, Cno) → Cno

对于任一关系模式，平凡函数依赖都是必然成立的，它不反映新的语义，因此若不特别声明， 我们总是讨论非平凡函数依赖。

完全函数依赖与部分函数依赖

在关系模式 R(U)中，如果 X→Y，并且对于 X 的任何一个真子集 X’，都有 X’↛Y, 则称 Y 完全函数依赖于 X，记作 X (F→) Y。若 X→Y，但 Y 不完全函数依 赖于 X，则称 Y 部分函数依赖于 X，记作 X (P→) Y。

[例] 在关系STUDENT（Sno ,Sdept, Mname,Cno,Grade）中，
(Sno, Cno) (F→) Grade 是完全函数依赖
(Sno, Cno) (P→) Sdept 是部分函数依赖，因为Sno → Sdept。

传递函数依赖

在 R（U）中，如果 X→Y，（Y⊈X），Y 不依赖于 X，Y→Z，则称 Z 对 X 传递函数依赖（transitive functional dependency）。记为：X (传递 →) Z。

注意: 如果 Y→X, 即 X←→Y，则 Z 直接依赖于 X。

在关系STUDENT（Sno ,Sdept, Mname,Cno,Grade）中， Sno → Sdept，Sdept → Mname，Sno (传递→) Mname

码

设 K 为关系模式 R<U,F>中的属性或属性组合。若 K → U，则 K 称为 R 的一个候选码(Candidate Key)。

• 如果 U 部分函数依赖于 K，即 K (P→) U,则 K 称为超码（Surpkey）
• 候选码是最小的超码，即 K 的任意一个真子集都不是候选码

[例] S(**Sno**, Sdept, Sage)
Sno→（Sno, Sdept，Sage）， Sno是码
(Sno, Sdept)、 (Sno, Sage)、 (Sno, Sdept, Sage) 是超码
SC(**Sno, Cno**, Grade)中，(Sno, Cno)是码

若关系模式 R 有多个候选码，则选定其中一个作为主码(Primary key)。

[例] S(**Sno, Sname**, Sdept, Sage)， 假设学生无重名
Sno、 Sname是候选码，选择Sno为主码。

主属性与非主属性

• 包含在任何一个候选码中的属性，成为主属性。
• 不包含在任何码中的属性成为非主属性或非码属性。

[例] S(Sno, Sdept, Sage)，Sno是码， Sno是主属性， Sdept, Sage是非主属性。
SC(Sno, Cno, Grade)中，(Sno, Cno)是码，
Sno, Cno是主属性， Grade是非主属性

全码

• 整个属性组是码，称为全码

[例] 关系模式 R（P，W，A） P：演奏者 W：作品 A：听众
语义：一个演奏者可以演奏多个作品，某一作品可被多个演奏者演奏，听众可以欣
赏不同演奏者的不同作品
R（P，W，A）码为(P，W，A)，即全码，All-Key。

外部码

• 关系模式 R<U,F>，U 中属性或属性组 X 并非 R 的码，但 X 是另一个关系模式的码，则称 X 是 R 的外部码（Foreign key）也称外码。

SC（Sno，Cno，Grade）中，Sno不是码，但Sno是关系模式
S（Sno，Sdept，Sage）的码，则Sno是关系模式SC的外部码。

• 主码与外部码一起提供了表示关系间联系的手段

范式

• 范式是符合某一种级别的关系模式的集合。
• 关系数据库中的关系必须满足一定的要求。
• 满足不同程度要求的为不同范式。
• 1NF \supset 2NF \supset 3NF \supset BCNF \supset 4NF \supset 5NF

一个低一级范式的关系模式，通过模式分解（schema decomposition）可以转换为若干个高一级范式的关系模式的集合，这种过程就叫规范化（normalization）。

1NF

• 定义：如果一个关系模式 R 的所有属性都是不可分的基本数据项，则 R∈1NF。
• 第一范式是对关系模式的最起码的要求。不满足第一范式的数据库模式不能称为关系数据模式。

2NF

• 定义:若关系模式 R∈1NF，并且每一个非主属性都完全函数依赖于 R 的码，则 R∈2NF。

一个关系模式 R 不属于 2NF 会产生的问题

1. 插入异常
2. 删除异常
3. 数据冗余度大
4. 修改复杂

2NF 还会存在的问题

• 不能完全消除关系模式种的各种异常情况和数据冗余

3NF

• 定义:关系模式 R<U，F>∈1NF,若 R 中不存在这样的码 X、属性组 Y 及非主属性 Z（Y⊇ Z）,使得 X→Y，Y→Z，Y (-\->) X，成立，则称 R<U，F> ∈ 3NF。

例如:S-D(Sno, Sdept) ∈ 3NF, D-L（Sdept， Sloc）∈ 3NF

3NF 的一些性质

• 若 R∈3NF，则 R 的每一个非主属性既不部分函数依赖于候选码也不传递函数依赖于候选码。
• 采用投影分解法将一个 2NF 的关系分解为多个 3NF 的关系，可以在一定程度上解决原 2NF 关系中存在的插入异常、删除异常、数据冗余度大、修改复杂等问题。
• 将一个 2NF 关系分解为多个 3NF 的关系后，并不能完全消除关系模式中的各种异常情况和数据冗余。

BCNF

• 定义：设关系模式 R<U，F>∈1NF，如果对于 R 的每个函数依赖 X→Y，且 X ⊇ Y 时，X 必含有码，那么 R∈BCNF。
• 即，在关系模式 R<U，F>中，如果每一个决定因素都包含码，则 R∈BCNF。

BCNF 的性质

1. 所有非主属性对每一个码都是完全函数依赖。
2. 所有主属性对每一个不包含它的码也是完全函数依赖。
3. 没有任何属性完全函数依赖于非码的任何一组属性。

如果一个关系数据库中的所有关系模式都属于 BCNF，那么在函数依赖范畴内，它已实现了模式的彻底分解，达到了最高的规范化程度，消除了操作异常诸多问题。

规范化小结

• 一个关系模式只要其分量都是不可分的数据项，它就是规范化的关系模式，但这只是最基本的规范化。
• 规范化程度过低的关系模式不一定能够很好地描述现实世界，可能会存在插入异常、删除异常、修改复杂、数据冗余等问题，解决方式就是对其进行规范化，转换成高级范式。
• 一个低一级范式的关系模式，通过模式分解可以转换为若干个高一级的关系模式集合，这种过程就叫关系模式的规范化。
• 关系数据库的规范化理论是数据库逻辑设计的工具。

关系模式规范化的基本步骤

1. 1NF->2NF，消除非主属性对码的部分函数依赖
2. 2NF->3NF，消除非主属性对码的传递函数依赖
3. 3NF->BCNF，消除主属性对码的部分和传递函数依赖
4. BCNF->4NF，消除非平凡且非函数依赖的多值依赖

规范化的基本思想

• 逐步消除数据依赖中不合适的部分，使模式中的个关系模式，达到某种程度的分离。
• 采用“一事一地”的模式设计原则
• 规范化实质上是概念的单一化

数据依赖的公理系统

• 数据依赖的公理系统是模式分解算法的理论基础。
• 函数依赖的一个有效而完备的公理系统——Armstrong 公理系统，

逻辑蕴含

定义：对于满足一组函数依赖 F 的关系模式 R <U，F>，其任何一个关系 r，若函数依赖 X→Y 都成立（即 r 中任意两元组 t，s，若 t [X]=s [X]，则 t [Y] = s [Y]），则称 F 逻辑蕴含 X→Y。

Armstrong 公理系统

设 U 为属性集总体，F 是 U 上的一组函数依赖， 于是有关系模式 R <U，F >。对 R <U，F> 来说有以下的推理规则：

• Al. 自反律(Reflexivity)：若 Y ⊆ X ⊆ U，则 X →Y 为 F 所蕴含。
• A2. 增广律(Augmentation)：若 X→Y 为 F 所蕴含，且 Z ⊆ U，则 XZ→YZ 为 F 所蕴含。
• A3. 传递律(Transitivity)：若 X→Y 及 Y→Z 为 F 所蕴含，则 X→Z 为 F 所蕴含。

函数依赖闭包

• 在关系模式 R<U，F>中为 F 所逻辑蕴含的函数依赖的全体叫作 F 的闭包（closure），记为 F+。
• 设 F 为属性集 U 上的一组函数依赖，X ⊆U， XF+ ={ A|X→A 能由 F 根据 Armstrong 公理导出}，XF+称为属性集 X 关于函数依赖集 F 的闭包。

求属性集 X 关于 F 的闭包 XF+

已知关系模式R<U, F>，其中U={A,B,C,D,E}；
F={AB->C,B->D,C->E,EC->B,AC->B}。
求(AB)F+
设X(0)=AB
X(1)=AB U CD=ABCD
X(2)=X(1) U BE=ABCDE
(AB)F+=ABCDE
计算X(1)；
因为X(0) ≠ X(1)，计算X(2)；
这时X(2) ≠ X(1)，但X(2) 已等于全部属性集合U，所以

Armstrong 公理系统的有效性与完备性

• 有效性：由 F 出发根据 Armstrong 公理推导出来的每一个函数依赖一定在 F+中
• 完备性：F+中的每一个函数依赖，必定可以由 F 出发根据 Armstrong 公理推导出来

函数依赖集等价的概念

• 如果 G+=F+，就说函数依赖集 F 覆盖 G（F 是 G 的覆盖，或 G 是 F 的覆盖），或 F 与 G 等价。

两个函数依赖集等价是指它们的闭包等价

最小依赖集

• 如果函数依赖集 F 满足下列条件，则称 F 为一个最小依赖集。

1. F 中任一函数依赖的右部仅含有一个属性。
2. F 中不存在这样的函数依赖 X→A，使得 F 与 F-{X→A}等价。
3. F 中不存在这样的函数依赖 X→A，X 有真子集 Z 使得 F-{X→A}∪{Z→A}与 F 等价。

模式分解

• R<U, F>的一个分解是指：ρ={R1<U1, F1>, …, Rn<Un, Fn>} ，其中 U= U1∪U2∪… ∪Un，并且没有 Ui ⊆ Uj，1 ≤ i，j ≤ n，Fi 是 F 在 Ui 上的投影。

• 把低一级的关系模式分解为若干个高一级的关系模式并不是唯一的

• 在这些分解方法中，只有能够保证分解后的关系模式与原关系模式等价的方法才有意义

• 从不同的角度去观察问题，对“等价”的概念形成了 3 种不同的定义：

  1. 分解具有无损连接性（lossless join）
  2. 分解要保持函数依赖（preserve functional dependency）
  3. 分解既要保持函数依赖，又要具有无损连接性

具有无损连接性的模式分解

• ρ={R1<U1, F1>, …, Rn<Un, Fn>}是 R<U, F>的一个分解，若对 R<U, F>的任何一个关系 r 均有 r = r 在 ρ 中各关系模式上投影的 自然连接成立，则称分解 ρ 具有无损连接性。简称 ρ 为无损分解。

只有具有无损连接性的分解才能够保证不丢失信息。 无损连接性不一定能解决插入异常、删除异常、修改复杂、数据冗余等问题。

保持函数依赖的模式分解

• ρ={R1<U1, F1>, …, Rn<Un, Fn>} 是 R<U, F>的一个分解，若 F 所逻辑蕴含的函数依赖一定也为分解后所有的关系模式中的函数依赖 Fi 所逻辑蕴含，即 F+ = ( F1 ∪ F2 ∪ … ∪ Fn )+，则称关系模式 R 的这个分解是保持函数依赖的（Preserve dependency）

分解的无损连接性和保持函数依赖性

• 如果一个分解具有无损连接性，则它能够保证不丢失信息。
• 如果一个分解保持了函数依赖，则它可以减轻或解决各种异常情况。
• 分解具有无损连接性和分解保持函数依赖是两个互相独立的标准。

1. 若要求分解保持函数依赖，那么模式分解一定能够达到 3NF，但不一定能够达到 BCNF。
2. 若要求分解既具有无损连接性，又保持函数依赖，则模式分解一定能够达到 3NF，但不一定能够达到 BCNF。
3. 若要求分解具有无损连接性，那么模式分解一定能够达到 4NF。

数据库设计

概述

广义地讲，是数据库及其应用系统的设计，即设计整个数据库应用系统； 狭义地讲，是设计数据库本身，即设计数据库的各级模式并建立数据库，这是数据库应用系统设计的一部分。

• 定义：数据库设计是指对于一个给定的应用环境，设计一个优良的数据库逻辑模式和物理结构，并据此建立数据库及其应用系统，使之能够有效地存储和管理数据，满足各种用户的应用需求，包括信息管理要求和数据处理求：
  1. 信息管理要求：在数据库中存储和管理需要的数据对象。
  2. 数据处理要求：对数据对象需要进行的处理，如查询、增删改、统计和分析等。

数据库设计特点

1. 基本规律

   • 三分技术，七分管理，十二分基础数据
   • 管理包括：数据库建设项目管理和企业的业务管理。
   • 基础数据：数据的收集、整理、组织和不断更新

2. 结构设计和行为设计相结合

   • 将数据库结构设计和数据处理设计相结合

   • 传统的软件工程：重行为设计

     忽视对应用中数据语义的分析和抽象，只要有可能就尽量推迟数据结构设计

   • 早期的数据库设计：重结构设计

     致力于数据模型和数据库建模方法研究，忽视了行为设计对结构设计的影响

数据库设计方法

• 大型数据库设计是涉及多学科的综合性技术，又是一项庞大的工程项目。
• 要求多方面的知识和技术，主要包括：
  1. 计算机的基础知识
  2. 软件工程的原理和方法
  3. 程序设计的方法和技巧
  4. 数据库的基本知识
  5. 数据库设计技术
  6. 应用领域的知识

1. 手工设计法
   • 设计质量与设计人员的经验和水平有直接关系
   • 缺乏科学理论和工程方法的支持，工程的质量难以保证
   • 数据库运行一段时间后常常又不同程度地发现各种问题，增加了维护代价。
2. 规范设计法

典型方法——新奥尔良（New Orleans）方法 - 将数据库设计分为若干阶段和步骤 - 采用辅助手段实现每一过程 - 按设计规程用工程化方法设计数据库 基于E-R模型的设计方法 - 概念设计阶段广泛采用 3NF（第三范式）的设计方法 - 逻辑阶段可采用的有效方法 ODL(Object Definition Language)方法 - 面向对象的数据库设计方法 UML(Unified Modeling Language)方法 - 面向对象的建模方法

数据库设计的基本步骤

数据库设计分 6 个阶段

• 独立于任何数据库管理系统
  1. 需求分析 是否做得充分与准确，决定了构建数据库的速度和质量。
  2. 概念结构设计 对用户需求进行综合、归纳与抽象，形成独立于具体 DBMS 的概念模型
• 与选用的数据库管理系统密切相关 3. 逻辑结构设计 将概念结构转换为某个 DBMS 所支持的数据模型，并对其进行优化 4. 物理结构设计 为逻辑数据结构选取一个最适合应用环境的物理结构，包括存储结构和存取方法
• 最终阶段 5. 数据库实施 根据逻辑设计和物理设计的结果构建数据库，编写与调试应用程序，组织数据入库并进行试运行。 6. 数据库运行和维护 经过试运行后即可投入正式运行。 在运行过程中必须不断对数据库设计进行评估、调整与修改。

参与数据库设计的人员

• 系统分析人员和数据库设计人员

  自始至终参与数据库设计

• 数据库管理员和用户代表

  主要参加需求分析与数据库的运行和维护

• 应用开发人员

  包括程序员和操作员 在实施阶段参与进来,分别负责编制程序和准备软硬件环境

数据库设计过程中的各级模式

• 需求分析阶段:综合各个用户的需求
• 概念设计阶段:形成独立于机器特点,独立于各个 DBMS 产品的概念模式(E-R 图)
• 逻辑设计阶段:
  1. 首先将 E-R 图转换成具体的数据库产品支持的数据模型,如关系模型,形成数据库逻辑模式
  2. 然后根据用户处理的要求,安全性的考虑,在基本表的基础上再建立必要的视图(View),形成数据的外模式
• 物理设计阶段:根据数据库管理系统特点和处理的需要,进行物理存储安排,建立索引,形成数据库内模式

需求分析

• 需求分析的重要性:
  • 结果是否准确地反映了用户的实际要求,将直接影响到后面各个阶段的设计,并影响到设计结果是否合理和实用

需求分析的任务

• 充分了解原系统工作概况
• 详细调查要开发的应用系统的组织/部门/企业等
• 明确用户的各种需求

需求分析的方法

数据字典

• 定义:数据字典是关于数据库中数据的描述,称为元数据。

  它不是数据本身，而是数据的数据。

• 数据字典在需求分析阶段建立，在数据库设计过程中不断修改、充实、完善。

• 数据字典是进行详细的数据收集和分析所获得主要结果。

• 数据字典的内容

  • 数据项
  • 数据结构
  • 数据流
  • 数据存储
  • 处理过程

数据项是数据的最小组成单位 若干个数据项可以组成一个数据结构 通过对数据项和数据结构的定义来描述数据流、数据存储的逻辑内容

数据项

• 数据项描述 = {数据项名,数据项含义说明,别名, 数据类型,长度,取值范围,取值含义,与其他数据项的逻辑关系, 数据项之间的联系}

• 关系规范化理论为指导，用数据依赖的概念分析和抽象数据项之间的联系——函数依赖

• “取值范围”、“与其他数据项的逻辑关系”定义了数据的完整性约束条件，是模式设计、完整性检查条件、触发器、存储过程的依据

数据项：学号
    含义说明：  唯一标识每个学生
    别名：      学生编号
    类型：      字符型
    长度：      9
    取值范围：  0000 00 000至9999 99 999
    取值含义:   前4位标识该学生入学年份，5、6位为所在专业系编号，后3位按顺序编号，例如2016 15 008
    与其他数据项的逻辑关系：学号的值确定了其他数据项的值

数据结构

• 数据结构反映了数据之间的组合关系。

  一个数据结构可以由若干个数据项组成，也可以由若干个数据结构组成，或由若干个数据项和数据结构混合组成。

• 数据结构描述= {数据结构名，含义说明，组成: {数据项或数据结构} }

    数据结构：  学生
    含义说明：  学籍管理子系统的主题数据结构，定义了一个学生的有关信息
    组成：      学号，姓名，性别，年龄，所在系，年级

数据流

• 数据流是数据结构在系统内部传输的路径。
• 数据流描述={ 数据流名,说明,数据流来源,数据流去向,组成: {数据结构}, 平均流量,高峰期流量 }
  • 数据流来源：说明该数据流来自哪个处理过程/数据存储
  • 数据流去向：说明该数据流将到哪个处理过程/数据存储去
  • 平均流量：在单位时间（每天、每周、每月等）里的传输次数
  • 高峰期流量：在高峰时期的数据流量

    数据流：    体检结果
    说明：      学生参加体格检查的最终报告
    数据流来源:  体检（处理过程）
    数据流去向:  批准（处理过程
    组成：      { 学号， {血常规}，{尿常规}，{血液生化}，{心电图}，{B超}, … … {其他体检} }
    平均流量：   每天200
    高峰期流量： 每天400

数据存储

• 数据存储是数据结构停留或保存的地方，也是数据流的来源和去向之一。
• 数据存储描述={数据存储名,说明,编号,输入的数据流 ,输出的数据流, 组成: {数据结构}, 数据量, 存取频度, 存取方式}
  • 存取频度：每小时、每天或每周存取次数，每次存取的数据量等信息
  • 存取方法：批处理 / 联机处理；检索 / 更新；顺序检索 / 随机检索
  • 输入的数据流：数据来源
  • 输出的数据流：数据去向

    数据存储：      学生登记表
    说明:           记录学生的基本情况
    输入数据流：    每学期5000
    输出数据流：    每学期5000
    组成：          {学号，姓名，性别，年龄，所在系，年级，{学习成绩}，{体检结果}，{奖惩记录} … … }
    数据量：        每年10000张
    存取方式：      随机存取+按照专业系/班级打印

处理过程

• 具体处理逻辑一般用判定表或判定树来描述。
• 数据字典中只需要描述处理过程的说明性信息。
• 处理过程描述={ 处理过程名, 说明, 输入:{数据流},输出:{数据流}, 处理:{简要说明} }
• 简要说明：说明该处理过程的功能及处理要求
  • 功能：该处理过程用来做什么
  • 处理要求：处理频度要求，如单位时间里处理多少事务，多少数据量、响应时间要求等。
  • 处理要求是物理设计的输入及性能评价的标准

    处理过程：      分配宿舍
    说明：          为所有新生分配学生宿舍
    输入：          学生，宿舍
    输出：          宿舍安排
    处理：          在新生报道后，为所有新生分配学生宿舍
    要求同一间宿舍只能安排同一年级同一性别的学生。
    一个学生只能安排在一个宿舍中，每个学生的居住面积不小于6平方米。
    安排新生宿舍其处理时间应不超过15分钟。

概念模型

• 什么是概念模型 将需求分析得到的用户需求抽象为信息结构即概念模型的过程就是概念结构设计； 概念结构是现实世界的一个真实模型。是各种数据模型的共同基础，它比数据模型更独立于机器、更抽象，从而更加稳定； 概念结构设计是数据库设计的关键。

• 概念模型的用途

  • 概念模型用于信息世界的建模
  • 使现实世界到机器世界的一个中间层次
  • 是数据库设计的有力工具
  • 是数据库设计人员和用户之间进行交流的工具

• 对概念模型的基本要求

  • 较强的语义表达能力
  • 简单、清晰、易于用户理解

信息世界中的基本概念

• 实体（Entity） 客观存在并可相互区别的事物称为实体，可以是具体的人、事、物或抽象的概念。

• 属性（Attribute） 实体所具有的某一特性称为属性。一个实体可以由若干个属性来刻画。

• 码（Key） 唯一标识实体的属性集称为码。

• 实体型（Entity Type） 用实体名及其属性名集合来抽象和刻画同类实体称为实体型

• 实体集（Entity Set） 同一类型实体的集合称为实体集

• 联系（Relationship）

  • 现实世界中事物内部以及事物之间的联系在信息世界中反映为实体（型）内部的联系和实体（型）之间的联系。

  • 实体内部的联系: 是指组成实体的各属性之间的联系

  • 实体之间的联系: 通常是指不同实体集之间的联系

    实体之间的联系有一对一（1:1）、一对多（1:m）和多对多（m:n）等多种类型

• 实体-联系方法（Entity-Relationship Approach）

概念结构设计

实体与属性的划分原则

现实世界的事物能作为属性对待的，尽量作为属性对待

• 划分实体与属性的两条准则：
  1. 作为属性，不能再具有须有描述的性质。属性必须是不可分的数据项，不能包含其他属性。
  2. 属性不能与其他实体具有联系。E-R 图中所表示的联系是实体与实体之间的联系。

    [例1] 职工实体：职工号、姓名、年龄是职工的属性，如何设计职称？
    - 如果不存储和处理与职称相关的工资、福利，根据准则（1）设计为职工的属性。
    - 如果需要存储或处理：与职称相关的工资、津贴、附加福利等，则职称应设计为一个实体。

    [例2] 医院中病人实体，如何设计病房？
    - 一个病人只能住在一个病房，病房号可以作为病人实体的一个属性；
    - 如果病房还要与医生实体发生联系，即一个医生负责若干病房的病人的医疗工作，则根据准则（2） 病房应作为一个实体。

E-R 图的集成

• 合并，解决各分 E-R 图之间的冲突，将分 E-R 图合并，生成初步 E-R 图。
  • 各个局部应用所面向的问题不同，各个子系统的 E-R 图之间必定会存在许多不一致的地方，称之为冲突。
  • 子系统 E-R 图之间的冲突主要有三类： 1. 属性冲突 2. 命名冲突 3. 结构冲突

1. 属性冲突

   • 属性域冲突，即属性值的类型、取值范围或取值集合不同。

     例如零件号，有的部门把它定义为整数，有的部门把它定义为字符型。 年龄，某些部门以出生日期形式表示职工的年龄，有的用整数表示职工的年龄。

   • 属性取值单位冲突。

     例如零件的重量有的以公斤为单位，有的以斤为单位，有的以克为单位。

2. 命名冲突

   • 同名异义，即不同意义的对象在不同的局部应用中具有相同的名字。

   • 异名同义（一义多名），即同一意义的对象在不同的局部应用中具有不同的名字。

     如对科研项目，财务科称为项目，科研处称为课题，生产管理处称为工程。

   • 命名冲突

     可能发生在实体、联系一级上 也可能发生在属性一级上 通过讨论、协商等行政手段加以解决

3. 结构冲突

   • 同一对象在不同应用中具有不同的抽象。

     例如，职工在某一局部应用中被当作实体，而在另一局部应用中被当作属性。 解决方法：把属性变换为实体或把实体变换为属性，使同一对象具有相同的抽象。

   • 同一实体在不同子系统的 E-R 图中的属性个数和属性排列次序不完全相同。

     解决方法：取各子系统的 E-R 图中属性的并集，再适当调整属性的次序。

   • 实体间的联系在不同的 E-R 图中为不同的类型。

     例如，实体 E1 与 E2 在一个 E-R 图中是多对多联系，在另一个 E-R 图中是一对多联系 解决方法是根据应用的语义对实体联系的类型进行综合或调整。

• 修改和重构，消除不必要的冗余，生成基本 E-R 图。

  • 冗余的数据是指：可由基本数据导出的数据

  • 冗余的联系是指：可由其他联系导出的联系

  • 冗余带来的问题：破坏数据库的完整性，数据库维护困难，应当予以消除

  • 消除冗余方法：

    分析方法 规范化理论的方法

• 用规范化理论来消除冗余

  1. 确定分 E-R 图实体之间的数据依赖。
     • 实体之间一对一、一对多、多对多的联系可以用实体码之间的函数依赖来表示。于是有函数依赖集 FL
  2. 求 FL 的最小覆盖 GL ，差集为 D= FL - GL

     • 逐一考察 D 中的函数依赖，确定是否是冗余的联系，若是，就把它去掉

  • 应注意的问题：
    • 冗余的联系一定在 D 中，而 D 中的联系不一定是冗余的；
    • 当实体之间存在多种联系时，要将实体之间的联系在形式上加以区分。

逻辑结构设计

逻辑结构设计的任务

• 把概念结构设计阶段设计好的基本 E-R 图转换为与选用的 DNMS 产品所支持的逻辑结构
• 目前主要使用关系模型，关系模型的逻辑结构是一组关系模式的集合。

E-R 图向关系模式的转换

• 转换内容：将 E-R 图转换为关系模型。将实体型、实体的属性和实体型之间的联系转化为关系模式。

1. 实体型的转换：一个实体型转换为一个关系模式

   • 关系模式的属性：实体的属性
   • 关系模式的码：实体的码

2. 实体型间的 1：1 联系：

   • 可以转换为一个独立的关系模式

     关系模式的属性：与该联系相连的各实体的码以及联系本身的属性 关系模式的候选码：每个实体的码均是该关系模式的候选码

   • 也可以与相连的任意一端对应的关系模式合并

     关系模式的属性：与某一端关系模式合并，则在该关系模式的属性中加入另一端关系模式的码和联系的属性 合并后关系模式的码：不变

3. 实体型间的 1：n 联系：

   • 转换为一个独立的关系模式

     关系模式的属性：与该联系相连的各实体的码+联系本身的属性 关系模式的码：n端的实体的码

   • 与 n 端对应的关系模式合并

     合并后关系模式的属性：在 n 端关系模式中 + 1 端关系的码 + 联系本身的属性 合并后关系模式的码：不变 可以减少系统模式中的关系个数，一般情况下更倾向于采用这种方法

4. 实体间的 m:n 联系：

   • 一个 m:n 联系转换为一个关系模式：

     关系的属性：与该联系相连的各实体的码以及联系本身的属性 关系的码：各实体码的组合

5. 三个或三个以上实体间的一个多元联系

   • 转换为一个关系模式

     关系模式的属性：与该多元联系相连的各实体的码+联系本身的属性 关系模式的码：各实体码的组合

6. 具有相同码的关系模式可合并

   • 目的：减少系统中的关系个数

   • 合并发法：

     将其中一个关系模式的全部属性加入到另一个关系模式中 然后去掉其中的同义属性（可能同名也可能不同名） 适当调整属性的次序

数据模型的优化

• 数据库逻辑设计的结果不是唯一的。

• 得到初步数据据模式后，还应该适当地修改、调整数据库逻辑结构，以进一步提高数据库应用系统的性能，这就是数据模型的优化。

• 关系数据模型的优化通常以规范化理论为指导。

• 优化数据模型的方法：

  1. 确定数据依赖

     按需求分析阶段所得到的语义，分别写出每个关系模式内部各属性之间的数据依赖以及不同关系模式属性之间数据依赖。

  2. 对于各个关系模式之间的数据依赖进行极小化处理，消除冗余的联系。

  3. 按照数据依赖的理论对关系模式进行分析，考察是否存在部分函数依赖、传递函数依赖、多值依赖等，确定各关系模式分别属于第几范式。

  4. 按照需求分析阶段得到的各种应用对数据处理的要求，分析对于这样的应用环境这些模式是否合适，确定是否要对它们进行合并或分解。包括水平分解和垂直分解。

设计用户子模式

• 数据库模式——全局模式 考虑系统全局应用需求，时间效率、空间效率、易维护等。
• 用户子模式——视图机制 考虑局部应用的特殊需求和用户体验。

1. 使用更符合用户习惯的别名

   合并各分 E-R 图曾做了消除命名冲突的工作，以使数据库系统中同一关系和属性具有唯一的名字。这在设计数据库整体结构时是非常必要的。 在设计用户子模式时可以设计子模式时重新定义某些属性名，使其与用户习惯一致，以方便使用。

2. 针对不同级别的用户定义不同的视图，提高系统的安全性

   假设有关系模式:
   产品（产品号，产品名，规格，单价，生产车间，生产负责人，产品成本，产品合格率，质量等级）
   为一般顾客、为产品销售部门和管理部门建立不同的视图。
   

3. 简化用户对系统的使用

   某些局部应用中经常要使用一些很复杂的查询，为了方便用户，可以将这些复杂查询定义为视图。

物理结构设计

• 为一个给定的逻辑数据模型选取一个最适合应用要求的物理结构的过程，就是数据库的物理设计。
• 数据库在物理设备上的存储结构与存取方法称为数据库的物理结构，它依赖于选定的 DBMS。

数据库物理设计的内容和方法

• 关系数据库物理设计的内容

  为关系模式选择存取方法（建立存取路径 为关系、索引、日志、备份等数据库文件选择物理存储结构

• 设计物理数据库结构的准备工作

  • 充分了解应用环境，详细分析要运行的事务，以获得选择物理数据库设计所需参数。
  • 充分了解所用RDBMS的内部特征，特别是系统提供的存取方法和存储结构。

• 物理数据库设计参数

  • 数据库查询事务
    • 查询所涉及的关系
    • 查询条件所涉及的属性
    • 连接条件所涉及的属性
    • 查询的投影属性
  • 数据更新事务
    • 被更新的关系
    • 每个关系上的更新操作条件所设计的属性
    • 修改操作要改变的属性值
  • 每个事务在个关系上运行的频率和性能要求

关系模式的存取方法选择

索引方法

• 为什么要建立索引 提高存取的效率——查询、插入、删除、更新的效率

• 如何选择索引存取方法 根据应用要求确定： > 对哪些属性列建立索引 > 对哪些索引要设计为唯一索引、组合索引 > 选择合适的索引方法

• 创建索引的方法

CREATE [ UNIQUE ] INDEX 索引名字 ON 表名 [ USING 索引方法 ] ( 列名1，列名2，[, ...] )；

CREATE UNIQUE INDEX studentname ON student USING Hash (sname)；

• RDBMS 提供的索引方法：

  B-tree（B+树），hash（散列）R-tree 、Bitmap 等。 如果不指定，缺省一般是 B-tree。

• 选取索引存取方法的一般规则

  如果一个（或一组）属性经常在查询条件中出现，则考虑在这个（这组）属性上建立索引（或组合索引）； 如果一个属性经常作为最大值和最小值等聚集函数的参数，则考虑在这个属性上建立索引； 如果一个（或一组）属性经常在连接操作的连接条件中出现，则考虑在这个（或这组）属性上建立索引

• B+树索引的特点：

  • 多分平衡树，存取效率高
  • 既能随即查找，又能顺序查找
  • 增删改操作，保持平衡

• 选取 Hash 存取方法的规则 如果一个关系的属性主要出现在等值连接条件中或主要出现在等值比较选择条件中，而且满足下列两个条件之一：

  该关系的大小可预知，而且不变； 该关系的大小动态改变，但所选用的数据库管理系统提供了动态 Hash 存取方法。

• 索引带来的额外开销

  • 维护索引的开销
  • 查找索引的开销
  • 存储索引的开销

聚簇方法的选择

• 定义：为了提高某个属性（或属性组）的查询速度，把这个（或这些）属性上具有相同值的元组集中存放在连续的物理块中称为聚簇。
• 该属性（或属性组）称为聚簇码（cluster key）

1. 创建一个聚簇 CREATE CLUSTER <聚簇名> (<聚簇码>) SIZE (<大小>);
2. 在聚簇上建立索引 CREATE INDEX <索引名> ON CLUSTER <聚簇名>; [例] CREATE CLUSTER emp_dept_cluster (deptno number(6) ) SIZE 1024; CREATE INDEX emp_dept_cluster_index ON CLUSTER emp_dept_cluster;

• 聚簇的作用

  • 大大提高按聚簇属性进行查询的效率 [例] 假设要查询计算机系的所有学生。 > 学生数据表随机存放，计算机系的 500 名学生分散存储在 500 个不同的物理块上，则至少要执行 500 次 I/O 操作。 > 如果按照专业系名聚簇存放，将同一系的学生元组聚簇在一起存放，则可以显著地减少了访问磁盘的次数。计算机系的 500 名学生聚簇存储在 50 个不同的物理块上，只要执行 50 次 I/O 操作。

• 聚簇的适用范围

  • 既适用于单个关系独立聚簇，也适用于多个关系组合聚簇 [例] 假设用户经常要按姓名查询学生成绩单。

    SELECT sname, cno, grade from student, sc where student.sno=sc.sno 这一查询涉及学生关系和选修关系的连接操作，按学号连接这两个关系。

    • 按照学号把学生表和选修表聚簇在一起。
    • 相当于把多个关系按“预连接”的形式存放。
    • 大大提高连接操作的效率。

  • 当 SQL 语句中包含有与聚簇码有关的 ORDER BY,GROUP BY, UNION, DISTINCT 等子句或短语时，使用聚簇特别有利，可以省去或减少对结果集的排序操作

• 聚簇的局限性

  • 在一个基本表上最多只能建立一个聚簇索引

  • 聚簇只能提高某些特定应用的性能

  • 建立和维护聚簇的开销相当大

    对已有关系建立聚簇，将导致关系中元组的物理存储位置移动，并使此关系上原有的索引无效，必须重建。 当一个元组的聚簇码改变时，该元组的存储位置也要相应改变。

• 聚簇索引的使用条件

  1. 很少对基表进行增删操作
  2. 很少对其中的变长列进行修改操作

确定数据库的存储结构

• 影响数据存放位置和存储结构的因素

  • 硬件环境

  • 应用需求

    • 存取时间

    • 存储空间利用率

    • 维护代价

      这三个方面常常是相互矛盾的

• 基本原则

  • 根据应用情况将
    • 易变部分与稳定部分分开存放
    • 经常存取部分与存取频率较低部分分开存放
    • 日志文件与数据库对象（表、索引等）分开存放

在海量数据和多用户环境下，把数据分布存放在不同的磁盘或磁盘阵列上，可以改进系统性能。

[例]
  可以将比较大的表分别放在两个磁盘上，以加快存取速度，这在多用户环境下特别有效。
  可以将日志文件与数据库对象（表、索引等）放在不同的磁盘以改进系统的性能。

数据库管理系统一般都提供了一些存储分配参数 - 同时使用数据库的用户数 - 同时打开的数据库对象数 - 内存分配参数 - 缓冲区分配参数（使用的缓冲区长度、个数） - 存储分配参数 - 物理块的大小 - 物理块装填因子 - 数据库的大小 - 锁的数目等

系统都为这些变量赋予了合理的缺省值。 在进行物理设计时需要根据应用环境确定这些参数值，以使系统性能最优。 在物理设计时对系统配置变量的调整只是初步的，要根据系统实际运行情况做进一步的调整，以切实改进系统性能。

评价物理结构

评价方法

• 定量估算各种方案
  • 存储空间
  • 存取时间
  • 维护代价
• 对估算结果进行权衡、比较，选择出一个较优的合理的物理结构
• 返回用户 征求意见 修改设计

数据库物理设计的步骤

1. 确定数据库的物理结构

   RDBMS 中主要指存取方法和存储结构;

2. 对物理结构进行评价，重点是时间和空间效率

   IF 评价结果满足原设计要求 THEN 进入到物理实施阶段 ELSE ( 重新设计 OR 修改物理结构 OR 返回逻辑设计阶段 修改数据模型)

数据库的实施和维护

数据的载入和应用程序的调试

1. 定义数据库结构

   • 用 DBMS 提供的 DDL 来创建数据库结构

     RDBMS 产生目标模式，生成数据字典

2. 数据装载

   • 组织数据入库是数据库实施阶段最主要的工作

   • 数据装载——ETL

     • 数据抽取
     • 数据转换
     • 数据载入

   • 使用 ETL 工具辅助完成

     ETL 工作是相当费力、费时的

3. 编制和调试应用程序

   • 数据库应用程序的涉及应该与数据设计并行进行
   • 在数据库实施阶段，编制与调试数据库的应用程序。
   • 调试应用程序时由于数据入库尚未完成，可先使用模拟数据。

数据库的试运行

应用程序调试完成，并且已有一小部分数据入库后，就可以开始对数据库系统进行联合调试。

• 主要工作包括：

  • 功能测试：实际运行应用程序，执行对数据库的各种操作，测试应用程序的各种功能。
  • 性能测试：测量系统性能指标，分析是否符合设计目标。

• 数据库性能指标的测量

  • 数据库物理设计阶段，评价数据库结构，估算时间、空间指标时，作了许多简化和假设，必然是近似结果。

  • 数据库试运行则是要实际测量系统的各种性能指标。

    如果结果不符合设计目标，则需要返回物理设计阶段，调整物理结构，修改参数；有时甚至需要返回逻辑设计阶段，调整逻辑结构。

1. 数据的分期入库

   • 重新设计物理结构甚至逻辑结构，会导致数据重新入库

   • 由于数据入库工作量实在太大，所以可以采用分期输入数据的方法

     先输入小批量数据供先期联合调试使用 待试运行基本合格后再输入大批量数据 逐步增加数据量，逐步完成运行评价

2. 数据库的转储和恢复

   • 在数据库试运行阶段，系统还不稳定，硬、软件故障随时都可能发生
   • 系统的操作人员对新系统还不熟悉，误操作也不可避免
   • 因此必须做好数据库的转储和恢复工作，尽量减少对数据库的破坏

数据库的运行和维护

在数据库运行阶段，对数据库经常性的维护工作主要是由数据库管理员完成的，包括：

1. 数据库的转储和恢复

   • 数据库管理员要针对不同的应用要求制定不同的转储计划，定期对数据库和日志文件进行备份。
   • 一旦发生介质故障，即利用数据库备份及日志文件备份，尽快将数据库恢复到某种一致性状态。

2. 数据库的安全性、完整性控制

   • 初始定义
     • 数据库管理员根据用户的实际需要授予不同的操作权限
     • 根据应用环境定义不同的完整性约束条件
   • 修改定义
     • 当应用环境发生变化，对安全性的要求也会发生变化，数据库管理员需要根据实际情况修改原有的安全性控制
     • 由于应用环境发生变化，数据库的完整性约束条件也会变化，也需要数据库管理员不断修正，以满足用户要求

3. 数据库性能的监督、分析和改进

   • 在数据库运行过程中，数据库管理员必须监督系统运行，对监测数据进行分析，找出改进系统性能的方法。
     • 利用监测工具获取系统运行过程中一系列性能参数的值
     • 通过分析这些数据，判断当前系统是否处于最佳运行状态
     • 如果不是，则需要通过调整某些参数来改进数据库性能

4. 数据库的重组织和重构造

   1. 数据库的重组织

      原因：数据库运行一段时间后，由于记录的不断增、删、改，会使数据库的物理存储变坏，从而降低数据库存储空间的利用率和数据的存取效率，使数据库的性能下降。

      • 主要工作：

        • 按原设计要求： - 重新安排存储位置 - 回收垃圾 - 减少指针链

          数据库的重组织不会改变原设计的数据逻辑结构和物理结构 数据库管理系统一般都提供了供重组织数据库使用的实用程序，帮助数据库管理员重新组织数据库。

   2. 数据库的重构造

      原因：数据库应用环境发生变化，会导致实体及实体间的联系也发生相应的变化，使原有的数据库设计不能很好地满足新的需求 增加新的应用或新的实体 取消某些已有应用 改变某些已有应用

   • 数据库重构造的主要工作 根据新环境调整数据库的模式和内模式

     • 增加或删除某些数据项
     • 改变数据项的类型
     • 增加或删除某个表
     • 改变数据库的容量
     • 增加或删除某些索引

   • 重构造数据库的程度是有限的

     • 应用需求变化太大，软硬件发展太快

       无法通过重构数据库来满足新的需求，或重构数据库的代价太大，则表明现有数据库应用系统的生命周期已经结束，应该重新设计新的数据库应用系统了。

第九章 关系查询处理和查询优化

• 查询处理的四个阶段：

  1. 查询分析
  2. 查询检查
  3. 查询优化
  4. 查询执行

查询分析

• 查询分析的任务：对查询语句进行扫描、词法分析和语法分析
  • 词法分析：从查询语句中识别出正确的语言符号
  • 语法分析：进行语法检查

SELECT Sname
FROM Student
WHERE Sno ="20100017"

词法分析：

• 保留字：SELECT， FROM， WHERE
• 变量：Sname, Student, Sno
• 常量：“20100017”
• 运算符： =

可以发现：拼写错误，命名错误，非法符号等。

语法分析：

• 按照 SQL 语言的句法解释查询语句
• 例如 SELECT Sname From Student WHEN Sno=“20100017”就是语法错误的

查询检查

• 有效性检查：检查语句中的数据库对象，如关系名、属性名是否存在和有效

• 根据数据字典中有关的模式定义信息进行检查

• 视图转换

• 如果查询是对视图的操作，则要用视图消解法把对视图的操作转换成对基本表的操作

• 安全性检查：

• 根据数据字典中的用户权限对用户的存取权限进行检查

• 完整性检查：

• 根据数据字典中存储的完整性约束定义，对句子进行检查

• 例如 where Sno = 20100017 就是错误的，因为 Sno 是字符类型 Char(8)

查询优化

• 查询优化分类
  • 代数优化/逻辑优化：指针对关系代数表达式的优化
  • 物理优化：指存取路径和底层操作算法的选择
• 查询优化的选择依据
  • 基于规则
  • 基于代价
  • 基于语义

查询执行

• 依据优化器得到的执行策略去生成查询执行计划 自顶向下
• 代码生成器生成执行查询计划的代码 自底向上

关系算子的实现

关系代数是关系数据库的抽象语言，理解如何实现关系代数操作有助于我们理解查询优化的过程。

选择操作的实现

实现方法：

1. 全表扫描方法
   • 对查询的基本表顺序扫描，逐一检查每个元组是否满足选择条件，把满足条件的元组作为结果输出
   • 适合小表，不适合大表
2. 索引扫描方法
   • 适合于选择条件中的属性上有索引（例如 B+树索引或 Hash 索引）
   • 通过索引先找到满足条件的元组主码或元组指针，再通过元组指针直接在查询的基本表中找到元组

SELECT * from Student WHERE <条件表达式> 考虑<条件表达式>的几种情况： C1：无条件； C2：Sno=‘201215121’; C3：Sage>20; C4：Sdept=‘CS’ AND Sage>20;

1. 全表扫描算法

   • 假设可以使用的内存为 M 块，全表扫描算法思想：

   1. 按照物理次序读 Student 的 M 块到内存
   2. 检查内存的每个元组 t，如果满足选择条件，则输出 t
   3. 如果 student 还有其他块未被处理重复 1 和 2

2. 索引扫描算法 SELECT * from Student WHERE Sno='201215121'

   • 假设 Sno 上有索引
   • 算法： - 使用索引得到 Sno 为’201215121’元组的指针 - 通过元组指针在 Student 表中检索到该学生 SELECT * from Student WHERE Sage>20
   • 假设 Sage 上有索引
   • 算法： - 使用 B+树索引找到 Sage=20 的索引项，以此为入口点在 B+树的顺序集上得到 Sage>20 的所有元组指针 - 通过这些元组指针到 Student 表中检索到所有年龄大于 20 的学生 SELECT * from Student WHERE Sdept='CS' AND Sage>20
   • 假设 Sdept 和 Sage 上都有索引
   • 算法 1：
     • 分别用 Index Scan 找到 Sdept=‘CS’的一组元组指针和 Sage>20 的另一组元组指针
     • 求这两组指针的交际
     • 到 Student 表中检索
     • 得到计算机系年龄大于 20 的学生
   • 算法 2：
     • 找到 Sdept=‘CS’的一组元组指针，通过这些元组指针到 Student 表中检索
     • 并对得到的元组检查另一些选择条件（如 Sage>20）是否满足
     • 把满足条件的元组作为结果输出

选择算子的处理要考虑到<条件表达式>具体情况，采用不同的策略。

• C1：无条件；采用全表扫描
• C2：Sno=‘201215121’；结果集小的情况下，利用索引
• C3：Sage>20；结果集太大的情况下，直接全表扫描
• C4：Sdept=‘CS’ AND Sgae>20；多个条件的情况下比较复杂，会分别考虑每个条件再合并结果，也可能逐一顺序考虑这些条件，甚至条件太复杂时候直接扫描表格。

连接操作的实现

• 连接操作是查询处理中最耗时的操作之一

例: SELECT * FROM Student, SC WHERE Student.Sno=SC.Sno;

1. 嵌套循环算法(nested loop join)

   • 对外层循环(Student 表)的每一个元组 s，检索内层循环(SC 表)中的每一个元组(sc)
   • 检查这两个元组在连接属性(Sno)上是否相等
   • 如果满足连接条件，则串接后作为结果输出，直到外层循环表中的元组处理完为止。

2. 排序合并算法(merge join)

   • 如果连接的表没有排好序，先对 Student 表和 SC 表按连接属性 Sno 排序

   • 取 Student 表中第一个 Sno，依次扫描 SC 表中具有相同 Sno 的元组

   • 当扫描到 Sno 不相同的第一个 SC 元组时，返回 Student 表扫描它的下一个元组，再扫描 SC 表中具有相同 Sno 的元组，把它们连接起来

   • 重复上述步骤直到 Student 表扫描完

     Student 表和 SC 表都只要扫描一遍 如果两个表原来无序，执行时间要加上对两个表的排序时间 对于大表，先排序后使用排序-合并连接算法执行连接，总时间一般仍会减少。

3. 索引连接算法(index join)

   1. 在 SC 表上已经建立 Sno 的索引。
   2. 对 Student 表中每一个元组，由 Sno 值通过 SC 的索引查找相应的 SC 元组
   3. 把这些 SC 元组和 Student 元组连接起来
   4. 循环执行 2、3，直到 Student 表中的元组处理完为止。

4. Hash Join 算法

   • 把连接属性作为 Hash 码，用同一个 hash 函数把 Student 表和 SC 表中的元组散列到 hash 表中。

   • 划分阶段

     1. 对包含较少元组的表（如 Student 表）进行一遍处理
     2. 把它的元组按 hash 函数分散到 hash 表的桶中

   • 试探阶段

     1. 对另一个表（sc 表）进行一遍处理

     2. 把 SC 表中的元组也按同一个 hash 函数（hash 码是连接属性）进行散列

     3. 把 SC 元组与桶中来自 Student 表并与之相匹配的元组连接起来

        hash join 算法前提：假设两个表中较小的表在第一个阶段后可以完全放入内存的 hash 桶中

查询优化的作用

• 是关系数据库管理系统实现的关键技术，也是关系系统的优点所在
• 减轻了用户对于系统底层选择存取路径的负担
• 用户可以关注查询的正确表达上，而无需考虑查询的执行效率如何
• 系统优化后的程序通常可以比用户程序做得更好
  1. 优化器可以从数据字典中获取许多统计信息，而用户程序则难以获得这些信息。
  2. 如果数据库的物理统计信息改变了，系统可以自动对查询重新优化以选择相适应的执行计划。在非关系系统中必须重写程序，这在实际中往往是不可行的。
  3. 优化器可以考虑数百种不同的执行计划，程序员一般只能考虑有限的几种可能性。
  4. 优化器中包括了很多复杂的优化技术，这些优化技术往往只有最好的程序员才能掌握。系统的自动优化相当于使得所有人都拥有这些优化技术。

关系数据库管理系统通过某种代价模型计算出各种查询执行策略的执行代价，然后选取代价最小的执行方案。

• 集中式数据库

  • 执行开销主要包括

    • 磁盘存取块数（I/O 代价）

    • 处理及时间（CPU 代价）

    • 内存空间的开销

      其中 I/O 代价是最主要的

• 分布式数据库

  • 总代价=I/O 代价+CPU 代价+内存代价+通信代价

查询优化的总目标

• 选择有效的策略
• 求得给定关系表达式的值
• 使得查询代价最小（实际上是较小）

先做选择再做连接操作，这样参与连接的元组就可以大大减少，这是代数优化 利用索引连接代价也较小，这是物理优化

代数优化

理想：

1. 找出查询 Q 的全部等价表达式（结果相同）E（Q）
2. 对 E(Q)中的每一个表达式计算其执行代价：f(q),q∈E(Q),q 是 Q 的一个等价表达式
3. 找出执行代价最小的表达式

问题：成本太高

现实：

1. 从查询 Q 出发，按照事先确定的规则对 Q 进行变换，获得 Q1，Q1 与 Q 必须等价
2. 确保 Q1 的执行代价比 Q 的执行代价低
3. 直到找不到执行代价更小的等价表达式，结束

问题：不一定是最优的

关系代数表达式的等价变换规则 - 等价的含义：指用相同的关系代替两个表达式中相应的关系所得到的结果是相同的 - 两个关系表达式 E1 和 E2 是等价的，可记为 E1≡E2

典型的启发式规则

1. 选择运算应尽可能先做 在优化策略中这是最重要、最基本的一条。
2. 把投影运算和选择运算同时进行 如有若干投影和选择运算，并且它们都对同一个关系操作，则可以在扫描此关系的同时完成所有的这些运算以避免重复扫描关系。
3. 把投影同其前或其后的双目运算结合起来，没有必要为了去掉某些字段而扫描一遍关系。
4. 把某些选择同在它前面要执行的笛卡尔积结合起来成为一个连接运算，连接特别是等值连接运算要比同样关系上的笛卡尔积省很多时间。
5. 找出公共子表达式
   • 如果这种重复出现的子表达式的结果不是很大的关系
   • 并且从外存中读入这个关系比计算该子表达式的时间少得多
   • 则先计算以此公共子表达式并把结果写入中间文件是合算的
   • 当查询的视图时，定义视图的表达式就是公共子表达式的情况

物理优化

物理优化就是要选择高效合理的操作算法或存取路径，求得更好的查询计划

物理优化方法

• 基于规则的启发式优化
  • 启发式规则是指那些在大多数情况下都使用，但不是在每种情况下都是适用的规则。
• 基于代价估算的优化
  • 优化器估算不同执行策略的代价，并选出具有最小代价的执行计划。
• 两者结合的优化方法
  • 常常先使用启发式规则，选取若干较优的候选方案，减少代价估算的工作量
  • 然后分别计算这些候选方案的执行代价，较快地选出最终地优化方案

基于启发式规则地存取路径选择优化

1. 选择操作地启发式规则

   • 对于小关系，使用全表顺序扫描，即使选择列上有索引

   • 对于大关系，启发式规则有：

     1. 对于选择条件是“主码=值”的查询

        • 查询结果最多是一个元组，可以选择主码索引
        • 一般的关系数据库管理系统会自动建立主码索引

     2. 对于选择条件是“非主属性=值”的查询，并且选择列上有索引

        • 要估算查询结果的元组数目
        • 如果比例较小（<10%）可以使用索引扫描办法
        • 否则还是使用全表顺序扫描

     3. 对于选择条件是属性上的非等值查询或者范围查询，并且选择列上有索引

        • 要估算查询结果的元组数目
        • 如果比较小（<10%）可以使用索引扫描办法
        • 否则还是使用全表扫描

     4. 对于用 AND 连接的合取选择条件

        • 如果有涉及这些属性的组合索引，优先采用组合索引扫描办法

        • 如果某些属性上有一般的索引，可以用索引扫描办法

          通过分别查找满足每个条件的指针，求指针的交集 通过索引查找满足部分条件的元组，然后再扫描这些元组时判断是否满足剩余条件

        • 其他情况：使用全表顺序扫描

     5. 对于用 OR 连接的析取选择条件，一般使用全表顺序扫描

2. 连接操作的启发式规则

   1. 如果 2 个表都已经按照连接属性排序
      • 选用排序-合并算法
   2. 如果一个表在连接属性上有索引
      • 选用索引连接算法
   3. 如果上面 2 个规则都不适用，其中一个表较小
      • 选用 hash join 算法
   4. 可以选用嵌套循环的方法，并选择其中较小的表，确切地讲是占用的块数(b)较少的表，作为外表(外循环的表)。 理由：
      • 设连接表 R 与 S 分别占用的块数为 Br 和 Bs
      • 连接操作使用的内存缓冲区块数为 K
      • 分配 K-1 块给外表
      • 如果 R 为外表，则嵌套循环存取的块数为 Br+BrBs/(K-1)
      • 显然应该选块数小的表作为外表

基于代价的优化

启发式规则优化是定性的选择，适合解释执行的系统

• 解释执行的系统，优化开销包含在查询总开销之中

编译执行的系统中查询优化和查询执行是分开的

• 可以采用精细复杂一些的基于代价的优化方法

1. 统计信息

   • 基于代价的优化方法要计算查询的各种不同执行方案的执行代价，它和数据库的状态密切相关

   • 优化器需要的统计信息

     1. 对每个基本表

        • 该表的元组总数(N)
        • 元组长度(I)
        • 占用的块数(B)
        • 占用的溢出块数(BO)

     2. 对基表的每个列

        • 该列不同值得个数(m)

        • 列最大值、最小值

        • 列上是否已经建立了索引

        • 哪种索引(B+树索引、Hash 索引、聚集索引)

        • 可以计算选择率(f)

          如果不同值的分布是均匀的，f=1/m 如果不同值的分布不均匀，则要计算每个值的选择率，f=具有该值的元祖数/N

     3. 对索引

        • 索引的层数(L)
        • 不同索引值的个数
        • 索引的选择基数 S(有 S 个元组具有某个索引值
        • 索引的叶节点数(Y)

2. 代价估算实例

   1. 全表扫描算法的代价估算公式

      • 如果基本表大小为 B 块，则全表扫描算法的代价 cost=B
      • 如果选择条件是“码=值”，那么平均搜索代价 cost=B/2 （以块的 IO 数量作为度量单位）

   2. 索引扫描算法的代价估算公式

      • 如果选择条件是“码=值”
        • 则采用该表的主索引
        • 若为 B+数，层数为 L，需要存取 B+树中从根节点到节点 L 块，再加上基本表中该元组所在的那一块，所以 cost=L+1
      • 如果选择条件涉及非码属性
        • 若为 B+树索引，选择条件是相等比较，S 是索引的选择基数(有 S 个元组买组条件)
        • 满足条件的元素可能会保存在不同的块上，所以(最坏的情况)cost=L+S
      • 如果比较条件是>,>=,<,<=操作
        • 假设有一半的元组满足条件
        • 就要存取一半的叶节点
        • 通过索引访问一半的表存储块
        • cost=L+Y/2+B/2
        • 如果可以获得更准确的选择基数，可以进一步修正 Y/2 和 B/2

   3. 嵌套循环连接算法的代价估算公式

      • 嵌套循环连接算法的代价 cost = Br+BrBs/(K-1)

      • 如果需要把连接结果写回磁盘 cost = Br+BrBs/(K-1)+(Frs x Nr x Ns)/Mrs

        其中 Frs 为连接选择性(join selectivity)，表示连接结果元组数的比例 Mrs 是存放连接结果的快因子，表示每块中可以存放的结果元组数目

   4. 排序-合并连接算法的代价估算公式

      • 如果连接表已经按照连接属性排好序，则 cost = Br+Bs+(Frs x Nr x Ns)/Mrs

      • 如果必须对文件排序

        还需要在代价函数中加上排序的代价 对于包含 B 个块的文件排序的代价大约是(2xB)+(2xBxlog(2)B)

比较复杂的查询，尤其是涉及连接和嵌套的查询 不要把优化的任务全部放在关系数据库管理系统上 应该找出关系数据库管理系统的优化规律，以写出适合关系数据库管理系统自动优化的 SQL 语句 对于关系数据库管理系统不能优化的查询需要重写查询语句，进行手工调整以优化性能

数据库恢复技术

事务

• 事务(Transaction)是用户定义的一个数据库操作序列，这些操作要么全做，要么全不做，是一个不可分割的工作单位。

• 事务和程序是两个概念

  • 在关系数据库中，一个事务可以是一条 SQL 语句，一组 SQL 语句或整个程序
  • 一个程序通常包含多个事务

• 事务是恢复和并发控制的基本单位

显式定义方式

BEGIN TRANSACTION
  SQL 1
  SQL 2
  ....
COMMIT

BEGIN TRANSACTION
  SQL 1
  SQL 2
  ....
ROLLBACK

隐式方式 当用户没有显示地定义事务时，数据库管理系统按缺省规定自动划分事务

事物的特性(ADID 特性)

• 原子性（Atomicity）

  • 事务是数据库的逻辑工作单位，事务中的诸操作要么都做，要么都不做

• 一致性（Consistency） 事务执行的结果必须是使数据库从一个一致性状态变到另一个一致性状态

  • 一致性状态
    • 数据库中只包含成功事务提交的结果
  • 不一致状态
    • 数据库系统运行中发生故障，有些事务尚未完成就被迫中断；
    • 这些未完成事务对数据库所做的修改有一部分已写入物理数据库，这时数据库就处于一种不正确的状态

• 隔离性（Isolation） 一个事务的执行不能被其他事务干扰

  • 一个事务内部的操作及使用的数据对其他并发事务是隔离的
  • 并发执行的各个事务之间不能相互干扰

• 持续性（Durability）

  • 一个事务一旦提交，它对数据库中数据的改变应该是永久性的
  • 接下来的其他操作或故障不应该对其执行结果有任何影响

• 破坏事务 ACID 特性的因素

  1. 多个事务并行运行时，不同事物的操作交叉执行
     • 数据库管理系统必须保证多个事务的交叉运行不影响这些食物的隔离性
  2. 事务在运行过程中被强行停止
     • 数据库管理系统必须保证被强行终止的事务对数据库和其他事务没有任何影响

数据库恢复概述

故障是不可避免的

• 计算机硬件故障
• 软件地错误
• 操作员的失误
• 恶意的破坏

故障的影响

• 运行事务非正常中断，影响数据库中数据的正确性
• 破坏数据库，全部或部分丢失数据

数据库的恢复

• 数据库管理系统必须具有把数据库从错误状态恢复到某一已知的正确状态(亦称为一致状态或完整状态)的功能，这就是数据库的恢复管理系统对故障的对策

故障种类

1. 事务内部的故障

   • 有的是可以通过事务程序本身发现的
   • 有的是非预期的，不能由事务程序处理的。
     • 运算溢出
     • 并发事务发生死锁而被选中撤销该事务
     • 违反了某些完整性限制而被终止
   • 意味着事务没有达到预期的终点(COMMIT 或者显示的 ROLLBACK)，数据库可能处于不正确状态
   • 恢复方法：事务撤消(UNDO)
     • 强行回滚该事务
     • 撤销该事务已经做出的任何对数据库的修改，使得该事务像根本没有启动一样

2. 系统故障 称为软故障，是指造成系统停止运转的任何时间，使得系统要重新启动。

   • 特定类型的硬件错误(如 CPU 故障)

   • 操作系统故障

   • 数据库管理系统代码错误

   • 系统断电

   • 故障影响：

     • 整个系统的正常运行突然被破坏
     • 所有正在运行的事务都非正常终止
     • 内存中数据库缓冲区的信息全部丢失
     • 不破坏数据库 发生系统故障时，一些尚未完成的事务的结果可能已送入物理数据库，造成数据库可能处于不正确状态。

   • 恢复策略：系统重新启动时，恢复程序让所有非正常终止的事务回滚，强行撤销(UNDO)所有未完成事务。 发生系统故障时，有些已完成的事务可能有一部分甚至全部留在缓冲区，尚未写回到磁盘上的物理数据库中，系统故障使得这些事务对数据库的修改部分或全部丢失

   • 恢复策略：重新启动时撤销所有未完成的事务，重做所有已提交的事务。

3. 介质故障 称为硬故障，值外存故障

   • 硬盘损坏
   • 磁头碰撞
   • 瞬时强磁场干扰 介质故障破坏数据库或部分数据库，并影响正在存取这部分数据的所有事务 介质故障比前两类故障的可能性小得多，但破坏性大得多

4. 计算机病毒

   • 一种人为的故障或破坏，是一些恶作剧者研制的一种计算机程序
   • 可以繁殖和传播，造成对计算机系统包括数据库的危害

故障小结

各类故障，对数据库的影响有两种可能性

1. 数据库本身被破坏
2. 数据库没有被破坏，但是数据可能不正确，这是由于事务的运行被非正常终止造成的。

恢复操作的基本原理：冗余

• 利用存储在系统别处的冗余数据来重建数据库中已被破坏或不正确的那部分数据

恢复的实现技术：复杂

• 一个大型数据库产品，恢复子系统的代码要占全部代码的 10%以上

恢复的实现技术

数据转储

• 转储是指数据库管理员定期地将整个数据库复制到磁带、磁盘或其他存储介质上保存起来的过程
• 备用的数据文本称为后备副本(backup)或后援副本
• 数据库遭到破坏后可以将后备副本重新装入
• 重装后备副本只能将数据库恢复到转储时的状态
• 要想恢复到故障发生时的状态，必须重新运行自转储以后的所有更新事务

转储方法

1. 静态转储
   • 在系统中无运行事务时进行的转储操作
   • 转储开始时数据库处于一致性状态
   • 转储期间不允许对数据库的任何存取、修改活动
   • 得到的一定是一个数据一致性的副本
   • 优点：简单
   • 缺点：降低了数据库的可用性
     • 转储必须等待正运行的用户事务结束
     • 新的事务必须等转储结束
2. 动态转储
   • 转储操作与用户事务并发进行
   • 转储期间允许对数据库进行存取或修改
   • 优点
     • 不用等待正在运行的用户事务结束
     • 不会影响新事务的运行
   • 缺点
     • 不能保证副本中的数据正确有效

利用动态转储得到的副本进行故障恢复

• 需要把动态转储期间各事务对数据库的修改活动记录下来，监理日志文件
• 后备副本加上日志文件就能把数据库恢复到某一时刻的正确状态

海量转储与增量转储

• 海量转储：每次转储全部数据库

• 增量转储：只转储上次转储后更新过的数据

• 两者比较

  • 从恢复角度看，使用海量转储得到的后备副本进行恢复往往更方便
  • 如果数据库大，事务处理又十分频繁，则增量转储方式更实用更有效

登记日志文件

• 日志文件是用来记录事务对数据库的更新操作的文件

日志文件的格式

• 以记录为单位的日志文件
  • 各个事务的开始标记(BEGIN TRANSACTION)
  • 各个事务的结束标记(COMMIT 或 ROLLBACK)
  • 各个事务的所有更新操作 以上均作为日志文件中的一个日志记录 (log record)
    • 事务标识（标明是哪个事务）
    • 操作类型（插入、删除或修改）
    • 操作对象（记录 ID、Block NO.）
    • 更新前数据的旧值（对插入操作而言，此项为空值）
    • 更新后数据的新值（对删除操作而言, 此项为空值） 例如 T1 U AA 18 20 T1 事务更新操作 将 AA 对象的值从 18 改为 20 T1 I TU 1 T1 事务插入操作 插入值为 1 的 TU 对象 T1 D TV 20 T1 对象删除事务 删除值为 20 的 TV 对象
• 以数据块为单位的日志文件
  • 事务标识
  • 被更新的数据块

日志文件的作用

• 进行事务故障恢复
• 进行系统故障恢复
• 协助后备副本进行介质故障恢复

具体作用

• 事务故障恢复和系统故障恢复必须用日志文件。
• 在动态转储方式中必须建立日志文件，后备副本和日志文件结合起来才能有效地恢复数据库。
• 在静态转储方式中，也可以建立日志文件。
  • 故障恢复时重新装入后援副本把数据库恢复到转储时刻的正确状态
  • 利用日志文件，重做已完成事务，撤销未完成的事务
  • 不必重新运行那些已完成的事务程序就可把数据库恢复到故障前某一时刻的正确状态

为保证数据库是可恢复的，登记日志文件时必须遵循两条原则

1. 登记的次序严格按并发事务执行的时间次序
2. 必须先写日志文件，后写数据库
   • 写日志文件操作：把表示这个修改的日志记录写到日志文件中
   • 写数据库操作：把对数据的修改写到数据库中 先写日志文件的原因：
   • 写数据库和写日志文件是两个不同的操作
   • 在这两个操作之间可能发生故障
   • 如果先写了数据库修改，而在日志文件中没有登记下这个修改，则以后就无法恢复这个修改了
   • 如果先写日志，但没有修改数据库，按日志文件恢复时只不过是多执行一次不必要的 UNDO 操作，并不会影响数据库的正确性

恢复策略

事务故障的恢复

事务故障：事务在运行至正常终止点前被终止

恢复方法

• 由恢复子系统利用日志文件撤消（UNDO）此事务已对数据库进行的修改

事务故障的恢复由系统自动完成，对用户是透明的，不需要用户干预

恢复步骤：

1. 反向扫描文件日志（即从最后向前扫描日志文件），查找该事务的更新操作。
2. 对该事务的更新操作执行逆操作。即将日志记录中“更新前的值” 写入数据库。
   • 插入操作， “更新前的值”为空，则相当于做删除操作
   • 删除操作，“更新后的值”为空，则相当于做插入操作
   • 若是修改操作，则相当于用修改前值代替修改后值
3. 继续反向扫描日志文件，查找该事务的其他更新操作，并做同样处理。
4. 如此处理下去，直至读到此事务的开始标记，事务故障恢复就完成了。

系统故障的恢复

系统故障造成数据库不一致状态的原因

• 未完成事务对数据库的更新可能已写入数据库
• 已提交事务对数据库的更新可能还留在缓冲区没来得及写入数据库

恢复方法

1. Undo 故障发生时未完成的事务
2. Redo 已完成的事务

系统故障的恢复由系统在重新启动时自动完成，不需要用户干预

系统故障的恢复步骤

1. 正向扫描日志文件（即从头扫描日志文件）

   • 重做(REDO) 队列: 在故障发生前已经提交的事务

     这些事务既有 BEGIN TRANSACTION 记录，也有 COMMIT 记录

   • 撤销 (UNDO)队列:故障发生时尚未完成的事务

     这些事务只有 BEGIN TRANSACTION 记录，无相应的 COMMIT 记录

2. 对撤销(UNDO)队列事务进行撤销(UNDO)处理

   • 反向扫描日志文件，对每个撤销事务的更新操作执行逆操作
   • 即将日志记录中“更新前的值”写入数据库

3. 对重做(REDO)队列事务进行重做(REDO)处理

   • 正向扫描日志文件，对每个重做事务重新执行登记的操作
   • 即将日志记录中“更新后的值”写入数据库

介质故障的恢复

1. 重装数据库
2. 重做已完成的事务

恢复步骤

1. 装入最新的后备数据库副本(离故障发生时刻最近的转储副本) ，使数据库恢复到最近一次转储时的一致性状态。
   • 对于静态转储的数据库副本，装入后数据库即处于一致性状态
   • 对于动态转储的数据库副本，还须同时装入转储时刻的日志文件副本，利用恢复系统故障的方法（即 REDO+UNDO），才能将数据库恢复到一致性状态。
2. 装入有关的日志文件副本(转储结束时刻的日志文件副本) ，重做已完成的事务。
   • 首先扫描日志文件，找出故障发生时已提交的事务的标识，将其记入重做队列。
   • 然后正向扫描日志文件，对重做队列中的所有事务进行重做处理。即将日志记录中“更新后的值”写入数据库。

介质故障的恢复需要数据库管理人员的接入

• 数据库管理员的工作
  • 重装最近转储的数据库副本和有关的各日志文件副本
  • 执行系统提供的恢复命令

具体的恢复操作仍由数据库管理系统完成

具有检查点的恢复技术

问题：

• 搜索整个日志将耗费大量的时间
• 重做处理：重新执行，浪费了大量时间

检查点恢复技术

• 在日志文件中增加检查点记录
• 增加重新开始文件
• 恢复子系统在登陆日志文件期间动态地维护日志

检查点技术

检查点记录的内容

• 建立检查点时刻所有正在执行的事务清单
• 这些事务最近一个日志记录的地址

重现开始文件的内容

• 记录各个检查点记录在日志文件中的地址

动态维护日志文件的方法： 周期性地执行如下操作：建立检查点，保存数据库状态。 具体步骤：

1. 将当前日志缓冲区中的所有日志记录写入磁盘的日志文件上
2. 在日志文件中写入一个检查点记录
3. 将当前数据缓冲区的所有数据记录写入磁盘的数据库中
4. 把检查点记录在日志文件中的地址写入一个重新开始文件

恢复子系统可以定期或不定期地建立检查点,保存数据库状态

• 定期
  • 按照预定的一个时间间隔，如每隔一小时建立一个检查点
• 不定期
  • 按照某种规则，如日志文件已写满一半建立一个检查点

使用检查点的恢复策略

使用检查点方法可以改善恢复效率

• 当事务 T 在一个检查点之前提交
  • 数据库所做的修改已写入数据库
  • 写入时间是在这个检查点建立之前或在这个检查点建立之时
  • 在进行恢复处理时，没有必要对事务 T 执行重做操作
• 当事务 T 在检查点时还没有完成
  • T 对数据库所做的修改已写入数据库
  • 在进行恢复处理时，如果需要重做 T，重做的起始点是检查点。

利用检查点的恢复步骤

1. 从重新开始文件中找到最后一个检查点记录在日志文件中的地址，由该地址在日志文件中找到最后一个检查点记录
2. 由该检查点记录得到检查点建立时刻所有正在执行的事务清单 ACTIVE-LIST
   • 建立两个事务队列
     • UNDO-LIST
     • REDO-LIST
   • 把 ACTIVE-LIST 暂时放入 UNDO-LIST 队列，REDO 队列暂为空。
3. 从检查点开始正向扫描日志文件，直到日志文件结束
   • 如有新开始的事务 Ti，把 Ti 暂时放入 UNDO-LIST 队列
   • 如有提交的事务 Tj，把 Tj 从 UNDO-LIST 队列移到 REDO-LIST 队列;直到日志文件结束
4. 对 UNDO-LIST 中的每个事务执行 UNDO 操作，对 REDO-LIST 中的每个事务执行 REDO 操作

数据库镜像

介质故障是对系统影响最为严重的一种故障，严重影响数据库的可用性

• 介质故障恢复比较费时
• 为预防介质故障，数据库管理员必须周期性地转储数据库

提高数据库可用性的解决方案

数据库镜像（Mirror）

• 数据库管理系统自动把整个数据库或其中的关键数据复制到另一个磁盘上
• 数据库管理系统自动保证镜像数据与主数据的一致性 每当主数据库更新时，数据库管理系统自动把更新后的数据复制过去

数据库镜像用途

• 出现介质故障时
  • 可由镜像磁盘继续提供使用
  • 同时数据库管理系统自动利用镜像磁盘数据进行数据库的恢复
  • 不需要关闭系统和重装数据库副本
• 没有出现故障时
  • 可用于并发操作
  • 一个用户对数据加排他锁修改数据，其他用户可以读镜像数据库上的数据，而不必等待该用户释放锁

频繁地复制数据自然会降低系统运行效率 在实际应用中用户往往只选择对关键数据和日志文件镜像。而不是对整个数据库进行镜像

并发控制

多用户数据库系统 允许多个用户同时使用的数据库系统

• 飞机定票数据库系统
• 银行数据库系统 特点：在同一时刻并发运行的事务数可达数百上千个

多事务执行方式

1. 事务串行执行
   • 每个时刻只有一个事务运行，其他事务必须等到这个事务结束以后方能运行
   • 不能充分利用系统资源，发挥数据库共享资源的特点
2. 交叉并发方式
   • 在单处理机系统中，事务的并行执行是这些并行事务的并行操作轮流交叉运行
   • 单处理机系统中的并行事务并没有真正地并行运行，但能够减少处理机的空闲时间，提高系统的效率
3. 同时并发方式
   • 多处理机系统中，每个处理机可以运行一个事务，多个处理机可以同时运行多个事务，实现多个事务真正的并行运行
   • 最理想的并发方式，但受制于硬件环境
   • 更复杂的并发方式机制

并发控制概述

• 事务是并发控制的基本单位
• 并发控制机制的任务
  • 对并发操作进行正确调度
  • 保证事务的隔离性
  • 保证数据库的一致性

并发操作带来的数据不一致性

1. 丢失修改（Lost Update）

   • 两个事务 T1 和 T2 读入同一数据并修改，T2 的提交结果破坏了 T1 提交的结果，导致 T1 的修改被丢失。

     	T1	T2
     ①	R(A)=16
     ②		R(A)=16
     ③	A←A-1
     	W(A)=15
     ④		A←A-3
     		W(A)=13

2. 不可重复读（Non-repeatable Read）

   • 不可重复读是指事务 T1 读取数据后，事务 T2 执行更新操作，使 T1 无法再现前一次读取结果。

   1. 情况 1

      • T1 读取某一数据
      • T2对其做了修改
      • 当 T1 再次读该数据时，得到与前一次不同的值

   2. 情况 2

      • 事务 T1 按一定条件从数据库中读取了某些数据记录
      • 事务T2删除了其中部分记录
      • 当 T1 再次按相同条件读取数据时，发现某些记录神秘地消失了。

   3. 情况 3

      • 事务 T1 按一定条件从数据库中读取某些数据记录

      • 事务 T2 插入了一些记录

      • 当 T1 再次按相同条件读取数据时，发现多了一些记录

        后两种不可重复读有时也称为幻影现象（Phantom Row）

3. 读“脏”数据（Dirty Read）

   • 事务 T1 修改某一数据，并将其写回磁盘
   • 事务 T2 读取同一数据后，T1 由于某种原因被撤销
   • 这时 T1 已修改过的数据恢复原值，T2 读到的数据就与数据库中的数据不一致
   • T2 读到的数据就为“脏”数据，即不正确的数据

数据不一致性：由于并发操作破坏了事务的隔离性 并发控制就是要用正确的方式调度并发操作，使一个用户事务的执行不受其他事务的干扰，从而避免造成数据的不一致性 对数据库的应用有时允许某些不一致性，可以降低对一致性的要求以减少系统开销

并发控制的主要技术

• 封锁(Locking)
• 时间戳(Timestamp)
• 乐观控制法
• 多版本并发控制(MVCC)

并发操作带来的数据不一致性

1. 丢失修改 （修改-修改冲突）
2. 不可重复读 （读-更新冲突）
   • 修改
   • 删除
   • 插入
3. 读“脏”数据（修改-读冲突）

封锁

定义：封锁就是事务 T 在对某个数据对象（例如表、记录等）操作之前，先向系统发出请求，对其加锁

加锁后事务 T 就对该数据对象有了一定的控制，在事务 T 释放它的锁之前，其它的事务不能更新此数据对象。

基本封锁类型

• 排它锁（Exclusive Locks，简记为 X 锁/写锁）
  • 若事务 T 对数据对象 A 加上 X 锁，则只允许 T 读取和修改 A，其它任何事务都不能再对 A 加任何类型的锁，直到 T 释放 A 上的锁
  • 保证其他事务在 T 释放 A 上的锁之前不能再读取和修改 A
• 共享锁（Share Locks，简记为 S 锁/读锁）
  • 若事务 T 对数据对象 A 加上 S 锁，则事务 T 可以读 A 但不能修改 A，其它事务只能再对 A 加 S 锁，而不能加 X 锁，直到 T 释放 A 上的 S 锁
  • 保证其他事务可以读 A，但在 T 释放 A 上的 S 锁之前不能对 A 做任何修改

封锁协议

• 在运用 X 锁和 S 锁对数据对象加锁时，需要约定一些规则，这些规则为封锁协议（Locking Protocol）。
  • 何时申请 X 锁或 S 锁
  • 持锁时间
  • 何时释放

对封锁方式规定不同的规则，就形成了各种不同的封锁协议，在不同的程度上保证并发操作的正确调度。

三级封锁协议

1. 一级封锁协议

   • 事务 T 在修改数据 R 之前必须先对其加 X 锁，直到事务结束才释放。

     • 正常结束（COMMIT）
     • 非正常结束（ROLLBACK）

   • 一级封锁协议可防止丢失修改，并保证事务 T 是可恢复的。

   在一级封锁协议中，如果仅仅是读数据不对其进行修改，是不需要加锁的，所以它不能保证可重复读和不读“脏”数据。

2. 二级封锁协议

   • 一级封锁协议加上事务 T 在读取数据 R 之前必须先对其加 S 锁，读完后即可释放 S 锁。

   • 二级封锁协议可以防止丢失修改和读“脏”数据。

     在二级封锁协议中，由于读完数据后即可释放 S 锁，所以它不能保证可重复读。

3. 三级封锁协议

   • 一级封锁协议加上事务 T 在读取数据 R 之前必须先对其加 S 锁，直到事务结束才释放。
   • 三级封锁协议可防止丢失修改、读脏数据和不可重复读。

三级协议的主要区别

• 什么操作需要申请封锁以及何时释放锁（即持锁时间）

  不同的封锁协议使事务达到的一致性级别不同 封锁协议级别越高，一致性程度越高

活锁和死锁

避免活锁：采用先来先服务的策略

• 当多个事务请求封锁同一数据对象时
• 按请求封锁的先后次序对这些事务排队
• 该数据对象上的锁一旦释放，首先批准申请队列中第一个事务获得锁

死锁的预防

1. 一次封锁法

   • 要求每个事务必须一次将所有要使用的数据全部加锁，否则就不能继续执行

   问题：

   • 过早加锁，降低系统并发度
   • 难于事先精确确定封锁对象
     • 数据库中数据是不断变化的，原来不要求封锁的数据，在执行过程中可能会变成封锁对象，所以很难事先精确地确定每个事务所要封锁的数据对象。
     • 解决方法：将事务在执行过程中可能要封锁的数据对象全部加锁，这就进一步降低了并发度。

2. 顺序封锁法

   • 预先对数据对象规定一个封锁顺序，所有事务都按这个顺序实行封锁。

   问题：

   • 维护成本 数据库系统中封锁的数据对象极多，并且随数据的插入、删除等操作而不断地变化，要维护这样的资源的封锁顺序非常困难，成本很高。
   • 难以实现 事务的封锁请求可以随着事务的执行而动态地决定，很难事先确定每一个事务要封锁哪些对象，因此也就很难按规定的顺序去施加封锁

结论

• 在操作系统中广为采用的预防死锁的策略不太适合数据库的特点
• 数据库管理系统在解决死锁的问题上更普遍在用的是诊断并解除死锁的方法

死锁的诊断和解除

死锁的诊断

1. 超时法 如果一个事务的等待时间超过了规定的时限，就认为发生了死锁

   • 优点：实现简单
   • 缺点：
     • 有可能误判死锁
     • 时限若设置得太长，死锁发生后不能及时发现

2. 等待图法 用事务等待图动态反映所有事务的等待情况

   • 事务等待图是一个有向图G=(T，U)
   • T为结点的集合，每个结点表示正运行的事务
   • U为边的集合，每条边表示事务等待的情况
   • 若T1等待T2，则T1，T2之间划一条有向边，从T1指向T2
   • 并发控制子系统周期性地（比如每隔数秒）生成事务等待图，检测事务。如果发现图中存在回路，则表示系统中出现了死锁。

解除死锁

• 选择一个处理死锁代价最小的事务，将其撤销
• 释放此事务持有的所有的锁，使其它事务能继续运行下去

并发调度的可串行性

• 数据库管理系统对并发事务不同的调度可能会产生不同的结果
• 串行调度是正确的
• 执行结果等价于串行调度的调度也是正确的，称为可串行化调度

可串行化调度

• 多个事务的并发执行是正确的，当且仅当其结果与按某一次序串行地执行这些事务时的结果相同

可串行性

• 是并发事务正确调度的准则
• 一个给定的并发调度，当且仅当它是可串行化的，才认为是正确调度

冲突可串行化调度

一个比可串行化更严格的条件

• 冲突操作：是指不同的事务对同一数据的读写操作和写写操作

  • Ri(x)与Wj(x) /事务Ti读x，Tj写x，其中i≠j/

  • Wi(x)与Wj(x) /事务Ti写x，Tj写x，其中i≠j/

  涉及同一个数据库元素, 并且至少有一个是写操作

• 不冲突操作

  • ri(X); rj(Y) 读
  • ri(X); wj(Y), X不等于Y
  • wi(X); rj(Y), X不等于Y
  • wi(X); wj(Y), X不等于Y

不能交换的动作：

• 同一事务的两个操作
• 不同事务的冲突操作
  • Ri(x)与Wj(x)
  • Wi(x)与Wj(x)

一个调度Sc在保证冲突操作的次序不变的情况下，通过交换两个事务不冲突操作的次序得到另一个调度Sc’，如果Sc’是串行的，称调度Sc是冲突可串行化的调度

若一个调度是冲突可串行化，则一定是可串行化的调度

[例] 
今有3个事务的一个调度
r3(B) r1(A) w3(B) r2(B) r2(A) w2(B) r1(B) w1(A)
判断该调度是否是冲突可串行化的调度。
Sc1 = r3(B) r1(A) w3(B) r2(B) r2(A) w2(B) r1(B) w1(A)
	  r3(B) w3(B) r1(A) r2(B) r2(A) w2(B) r1(B) w1(A)
	  r3(B) w3(B) r2(B) r2(A) w2(B) r1(A) r1(B) w1(A)
Sc2 = r3(B) w3(B) r2(B) r2(A) w2(B) r1(A) r1(B) w1(A)
所以Sc1是冲突可串行化的调度
Sd = r1(A) w1(A) r2(A) w2(A) r2(B) w2(B) r1(B) w1(B)
w1(A)和 r2(A)冲突，w2(B)和r1(B)冲突
不能通过无冲突交换将Sd变换为串行调度
Sd不是冲突可串行化的调度

• 冲突可串行化调度是可串行化调度的充分条件，不是必要条件。还有不满足冲突可串行化条件的可串行化调度。

[例11.4]
有3个事务 T1=W1(Y)W1(X)，T2=W2(Y)W2(X)，T3=W3(X)
调度L1=W1(Y)W1(X)W2(Y)W2(X)W3(X)是一个串行调度。
调度L2=W1(Y)W2(Y)W2(X)W1(X)W3(X)不满足冲突可串行化。
但是调度L2是可串行化的，因为L2执行的结果与调度L1相同，Y的值都等于T2的值，X的值都等于T3的值

两段锁协议

数据库管理系统普遍采用两段锁协议的方法实现并发调度的可串行性，从而保证调度的正确性

两段锁协议指所有事务必须分两个阶段对数据项加锁和解锁

• 在对任何数据进行读、写操作之前，事务首先要获得对该数据的封锁
• 在释放一个封锁之后，事务不再申请和获得任何其他封锁

“两段”锁的含义

事务分为两个阶段

• 第一阶段是获得封锁，也称为扩展阶段
  • 事务可以申请获得任何数据项上的任何类型的锁，但是不能释放任何锁
• 第二阶段是释放封锁，也称为收缩阶段
  • 事务可以释放任何数据项上的任何类型的锁，但是不能再申请任何锁

例
事务Ti遵守两段锁协议，其封锁序列是 ：
Slock A Slock B Xlock C Unlock B Unlock A Unlock C；

事务Tj不遵守两段锁协议，其封锁序列是：
Slock A Unlock A Slock B Xlock C Unlock C Unlock B；

遵守两段锁协议，是一个可串行化调度。

事务遵守两段锁协议是可串行化调度的充分条件，而不是必要条件。

若并发事务都遵守两段锁协议，则对这些事务的任何并发调度策略都是可串行化的。

若并发事务的一个调度是可串行化的，不一定所有事务都符合两段锁协议。

• 对T1和T2的调度没有遵守两段锁协议
• 但是它是可串行化的
• L1=R1(B)W1(A)R2(A)W2(B)

并发事务遵守两段锁协议，对这些事务的任何并发调度策略都是可串行化的；

不遵守两段锁协议，对这些事务的并发调度策略可能是可串行化的，也可能不是可串行化的。

• 两段锁协议与防止死锁的一次封锁法对比
  • 一次封锁法要求每个事物必须一次将所有要使用的数据全部加锁，否则就不能继续执行，因此一次封锁法遵守两段锁协议
  • 但是两段锁协议并不要求事务必须一次将所有要使用的数据全部加锁，因此遵守两段锁协议的事务可能发生死锁

[例] 遵守两段锁协议的事务可能发生死锁

封锁粒度

封锁对象的大小称为封锁粒度(Granularity)

封锁的对象:逻辑单元，物理单元

• 例：关系数据库中的封锁对象
  • 逻辑单元: 属性值、属性值的集合、元组、关系、索引项、整个索引、整个数据库等
  • 物理单元：页（数据页或索引页）、物理记录等

封锁粒度与系统的并发度和并发控制的开销密切相关。

• 封锁的粒度越大，数据库所能够封锁的数据单元就越少，并发度就越小，系统开销也越小；
• 封锁的粒度越小，并发度较高，但系统开销也就越大

例1：事务T1需要修改元组L1 ，事务T2需要修改元组L2 ， L1和L2 位于同一个数据页面A。
若封锁粒度是数据页，事务T1需要对数据页A加锁，T2被迫等待，直到T1释放A。
如果封锁粒度是元组，则T1和T2可以同时对L1和L2加锁，不需要互相等待，提高了系统的并行度。

封锁粒度越小，并发度越高。

例2：事务T3需要读取整个表
若封锁粒度是元组，T3必须对表中的每一个元组加锁，开销极大
若封锁粒度是关系，T3只需要一次加锁
若锁粒度是数据页呢？

封锁粒度越小，封锁开销越大。

多粒度封锁

在一个系统中同时支持多种封锁粒度供不同的事务选择

• 同时考虑封锁开销和并发度两个因素, 适当选择封锁粒度

  • 需要处理大量元组的用户事务：以关系为封锁单元
  • 需要处理多个关系的大量元组的用户事务：以数据库为封锁单位
  • 只处理少量元组的用户事务：以元组为封锁单位

• 多粒度树

  • 以树形结构来表示多级封锁粒度
  • 根结点是整个数据库，表示最大的数据粒度
  • 叶结点表示最小的数据粒度

例1：三级粒度树

根结点为数据库，数据库的子结点为关系，关系的子结点为元组。

例2：四级粒度树

• 多粒度封锁协议

  • 允许多粒度树中的每个结点被独立地加锁
  • 对一个结点加锁意味着这个结点的所有后裔结点也被加以同样类型的锁
  • 在多粒度封锁中一个数据对象可能以两种方式封锁：显式封锁和隐式封锁

• 显式封锁: 直接加到数据对象上的封锁

• 隐式封锁:是该数据对象没有独立加锁，是由于其上级结点加锁而使该数据对象加上了锁

显式封锁和隐式封锁的效果是一样的

系统检查封锁冲突时

• 要检查显式封锁
• 还要检查隐式封锁

对某个数据对象加锁，系统要检查

• 该数据对象
  • 有无显式封锁与之冲突
• 所有上级结点
  • 检查本事务的显式封锁是否与该数据对象上的隐式封锁冲突(由上级结点已加的封锁造成的）
• 所有下级结点
  • 看上面的显式封锁是否与本事务的隐式封锁（将加到下级结点的封锁）冲突

意向锁

引进意向锁的目的：提高对某个数据对象加锁时系统的检查效率

• 如果对一个结点加意向锁，则说明该结点的下层结点正在被加锁
• 对任一结点加基本锁，必须先对它的上层结点加意向锁

常用意向锁

• 意向共享锁(Intent Share Lock，简称IS锁)
  • 如果对一个数据对象加IS锁，表示它的后裔结点拟（意向）加S锁。
  • 
• 意向排它锁(Intent Exclusive Lock，简称IX锁)
  • 如果对一个数据对象加IX锁，表示它的后裔结点拟（意向）加X锁。
  • 
• 共享意向排它锁(Share Intent Exclusive Lock，简称SIX锁)
  • 如果对一个数据对象加SIX锁，表示对它加S锁，再加IX锁，即SIX = S + IX。
  • 

锁的强度

• 锁的强度是指它对其他锁的排斥程度
• 一个事务在申请封锁时以强锁代替弱锁是安全的，反之则不然

具有意向锁的多粒度封锁方法

• 申请封锁时应该按自上而下的次序进行
• 释放封锁时则应该按自下而上的次序进行

作用

• 提高了系统的并发度
• 减少了加锁和解锁的开销
• 在实际的数据库管理系统产品中得到广泛应用