数据库原理与安全 | 笔记2

第六章关系数据理论

6.1 问题的提出

关系模式是一个五元组：

关系名R是符号化的元组语义
U为一组属性
D为属性组U中的属性所来自的域
DOM为属性到域的映射
F为属性组U上的一组数据依赖（约束关系）

由于D、DOM与模式设计关系不大，因此在本章中把关系模式看作一个三元组：

当且仅当U上的一个关系r满足F时，r称为关系模式R<U,F>的一个关系。

作为二维表，关系要符合一个最基本的条件：每个分量必须是不可分的数据项。满足了这个条件的关系模式就属于第一范式（1NF）。

数据依赖：

一个关系内部属性与属性之间的一种约束关系
通过属性间值的相等与否体现出来的数据间相关联系
是现实世界属性间相互联系的抽象，是数据内在的性质，是语义的体现
设计关系模式时，除给出属性全集外，还需给出数据依赖集合

数据依赖的主要类型：函数依赖（Functional Dependency，FD）、多值依赖（Multi-Valued Dependency，MVD）

例：描述一个学生关系，可以有学号、姓名、系名等属性。

一个学号只对应一个学生，一个学生只在一个系中学习
“学号”值确定后，学生的姓名及所在系的值就被唯一确定

即：，即Sno函数决定Sname和Sdept，记作

【例6.1】建立一个描述学校教务的数据库。

涉及的对象包括：学生的学号（Sno）、所在系（Sdept）、系主任姓名（Mname）、课程号（Cno）、成绩（Grade）

假设学校教务的数据库模式用一个单一的关系模式Student来表示，则该关系模式的属性集合为： $＝$ 现实世界的已知事实（语义）：

一个系有若干学生，但一个学生只属于一个系；
一个系只有一名（正职）负责人；
一个学生可以选修多门课程，每门课程有若干学生选修；
每个学生学习每一门课程有一个成绩。

由此可得到属性组U上的一组函数依赖F：函数依赖关系

关系模式Student<U, F>中存在的问题：

数据冗余：比如，每一个系的系主任姓名重复出现
更新异常：数据冗余，更新数据时，维护数据完整性代价大。比如，某系更换系主任后，必须修改与该系学生有关的每一个元组。
插入异常：如果一个系刚成立，尚无学生，则无法把这个系及其系主任的信息存入数据库。
删除异常：如果某个系的学生全部毕业了，则在删除该系学生信息的同时，这个系及其系主任的信息也丢掉了。

结论：

关系模式不是一个好的模式。
一个“好”的模式应当不会发生插入异常、删除异常和更新异常，数据冗余应尽可能少。

解决方法：用规范化理论改造关系模式来消除其中不合适的函数依赖。把Student单一的模式分成三个关系模式：

S(Sno,Sdept); Sno → Sdept
SC(Sno,Cno,Grade); (Sno,Cno) → Grade
DEPT(Sdept,Mname); Sdept → Mname
消除了过多的不必要的数据依赖，最好的依赖关系：非主属性只依赖候选键（主键）

6.2 规范化

6.2.1 函数依赖

1.函数依赖

定义6.1：

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

通俗理解为：X和Y是两个属性，X唯一确定一个Y。

例如：对r上的任意两个元组，如果： $则$ 若 $则记为$ 。

若Y不函数依赖与X，则记为。

函数依赖和别的数据依赖一样是语义范畴的概念，只能根据语义来确定一个函数依赖。例如“姓名→年龄”这个函数依赖只有在不允许有同名人的条件下成立。

本质上，函数依赖是对属性间取值的一种约束，是一种数据依赖，是问题域业务规则的体现。

2.平凡函数依赖与非平凡函数依赖

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

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

定义6.2：

在 R(U) 中，如果，并且对于 X 的任何一个真子集 , 都有 , 则称 Y 对 X 完全函数依赖，记作。

若，但 Y 不完全函数依赖于 X，则称 Y 对 X 部分函数依赖，记作。

例如在关系SC(Sno, Cno, Grade)中，有：

4.传递函数依赖

定义6.3：

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

如果，则Z直接依赖于X，而不是传递函数依赖。

成立，所以。

6.2.2 码/键(Key)

1. 候选键/超键/主键

定义6.4：

设 K 为中的属性或属性组合。若，则 K 称为 R 的候选码（candidate key）。

如果 U 部分函数依赖于 K，即，则 K 称为超码（surpkey）。候选码是最小的超码，即 K 的任意一个真子集都不是候选码。

若关系模式 R 有多个候选码，则选定其中的一个为主码（primary key）。

2. 主属性/非主属性

主属性与非主属性

包含在任何一个候选码中的属性，称为主属性（prime attribute）
不包含在任何候选码中的属性称为非主属性（nonprime attribute）或非码属性（non-key attribute）

最简单的情况，单个属性是码；最极端的情况，整个属性组是码，称为全码（all-key）。

3. 外码

定义6.5：

定义：关系模式 R 中属性或属性组 X 并非 R 的码，但 X 是另一个关系模式的码，则称 X 是 R 的外部码（foreign key），也称外码。

主码与外码一起提供了表示关系间联系（参照完整性）的手段

4. 函数依赖的公理

定义6.11：

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

5. 函数依赖的公理系统

Armstrong 公理系统（Armstrong's axiom）：

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

A1 自反律（reflexivity rule）：若，则为 F 所蕴涵。
A2 增广律（augmentation rule）：若为 F 所蕴涵，且，则为 F 所蕴涵。（XZ 表示。）
A3 传递律（transitivity rule）：若及为 F 所蕴涵，则为 F 所蕴涵。

注：由自反律所得到的函数依赖均是平凡的函数依赖，自反律的使用并不依赖于 F。

定理：Armstrong 推理规则是正确的。

根据 A1、A2、A3 这三条推理规则可以得到下面三条很有用的推理规则。

合并规则（union rule）：由，有。
伪传递规则（pseudo transitivity rule）：由，有。
分解规则（decomposition rule）：由，有。

6.2.3 范式(Normal Form, NF)

范式是符合某一种级别的关系模式的集合。
关系数据库中的关系是要满足一定要求的，满足不同程度要求的为不同范式。
满足最低要求的叫第一范式，简称 1NF。

范式之间存在联系：

某一关系模式 R 为第 n 范式，可简记为。

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

6.2.4 2NF

定义6.6：

若关系模式，且每一个非主属性都完全函数依赖于任何一个候选码，则。

【例 6.4】S-L-C(Sno, Sdept, Sloc, Cno, Grade)，Sloc 为学生的住处，并且每个系的学生住在同一个地方。S-L-C的码为 (Sno,Cno)，则函数依赖有：

（每个系的学生只住一个地方）

非主属性 Sdept、Sloc 并不完全函数依赖于码，因此。

一个关系模式不属于 2NF，会产生以下问题：

插入异常。如果插入一个新学生，但该生还未选课，即该生无 Cno，由于插入元组时必须给定码值，因此插入失败。
删除异常。如果 S4 只选了一门课 C3，现在他不再选这门课，那么 C3 这个数据项就要删除；而 C3 是主属性，删除了 C3，整个元组就必须一起删除，使得 S4 的其他信息也被删除了。
修改复杂。如果一个学生选了多门课，则 Sdept，Sloc 被存储了多次。如果该生转系，则需要修改所有相关的 Sdept 和 Sloc，造成修改的复杂化。

解决的办法是用投影分解把关系模式 S-L-C 分解成两个关系模式：SC(Sno,Cno,Grade) 和 S-L(Sno,Sdept,Sloc)。

SC 的码为 (Sno,Cno)，S-L 的码为 Sno，这样就使得非主属性对码都是完全函数依赖了。

2NF解决的是而非主属性对复合主键(候选键)的部分依赖，即它要求表中的所有非主属性都应该完全依赖于整个主键，而不是主键的一部分。

如果是单一候选键，则一定符合2NF。

例子：

6.2.5 3NF

定义6.7：

设关系模式，若 R 中不存在这样的码 X、属性组 Y 及非主属性 Z（）, 使得成立，，则称。

SC没有传递依赖，因此SC ∈ 3NF

3NF通常解决的是非主属性之间的依赖关系，更准确的是非主属性对候选键的传递依赖。即3NF要求一个关系表中的每个非主属性都不能传递依赖于候选键之外的任何属性。这意味着如果一个非主属性依赖于候选键，那么它不应该再依赖于其他非主属性。

属性组Y可能包括部分主属性、非主属性，或二者的组合：

Y：非主属性（组）—— 最常见，反映非主属性之间的依赖关系
Y：主属性组（但不构成候选键）+ 非主属性（组）—— 不常见
Y：不能是主属性组（但不构成候选键），否则不满2NF —— 非主属性对候选键的部分依赖
Y：不是候选键，因为：，X是候选键

6.2.6 BCNF

定义6.8：

设关系模式，若且时 X 必含有码，则。

即如果每一个决定属性集都包含候选码(即超码)，则R∈BCNF。

满足 BCNF 的关系模式所具有的性质：

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

BCNF在3NF的基础上，进一步解决：

主属性组（但不构成候选键）对候选键的部分或者传递依赖关系
- 主属性（组）之间的依赖关系：对候选键的部分依赖
- 主属性组（但不构成候选键）+非主属性（组）组合对候选键的传递依赖
也就是除了所有属性（组）对候选键的依赖关系之外，没有任何其他的依赖关系

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

3NF的“不彻底”性表现在可能存在主属性[+非主属性]对候选键的传递依赖，很多时候是主属性之间存在依赖关系【表现为主属性对候选键的部分依赖】

主属性的判断：如果关系R中的一个非主属性A能够决定候选键的部分属性Y，则该属性A一定是主属性

6.2.7 多值依赖

定义6.9：

设 R(U) 是属性集 U 上的一个关系模式。X，Y，Z 是 U 的子集，并且 Z=U-X-Y 。关系模式 R(U) 中多值依赖成立，当且仅当对 R(U) 的任一关系 r，给定的一对 (x,z) 值，有一组 Y 的值，这组值仅仅决定于 x 值而与 z 值无关。

Y和Z是相互独立的
R(U)的实例数量 = 相关的一组(x,y,z)的笛卡尔积的数量之和

平凡多值依赖和非平凡的多值依赖：

Z为空，则称X→→Y为平凡的多值依赖。
否则为非平凡的多值依赖，给定一个X，有一组Y与X对应。

【例6.10】关系模式WSC(W,S,C)中，W表示仓库，S 表示保管员，C 表示商品。假设每个仓库有若干个保管员，有若干种商品。每个保管员保管所在仓库的所有商品，每种商品被所有保管员保管。

按照语义，对于W的每一个值Wi，S有一个完整的集合与之对应，而不论C取何值，所以W→→S。同样的，有W→→C。S和C是相互独立的。

多值依赖的性质：

多值依赖具有对称性。即若，则，其中Z=U-X-Y。

多值依赖的对称性可以用完全二分图直观地表示出来。
多值依赖具有传递性。即若，，则。
函数依赖是多值依赖的特殊情况。即若，则。
推理规则：
- 若，，则。
- 若，，则。
- 若，，则 $，$ 。

多值依赖与函数依赖的区别：

多值依赖的有效性与属性集的范围有关

若在 U 上成立，则在上一定成立；反之则不然，即在 W 上成立，在 U 上并不一定成立。

即：缩小范围成立，扩大范围不一定成立

原因：多值依赖的定义中不仅涉及属性组 X 和 Y ，而且涉及 U 中其余属性 Z 。
若函数依赖在 R(U) 上成立，则对于任何均有成立。而多值依赖若在 R(U) 上成立，却不能断言对于任何有成立。

例如，有关系 R(A,B,C,D)，成立，当然也有成立。有 R 的一个关系实例，在此实例上是不成立的，如表所示。

6.2.8 4NF

定义6.10：

关系模式，如果对于 R 的每个非平凡多值依赖，X 都含有码，则称。

4NF 就是限制关系模式的属性之间不允许有非平凡且非函数依赖的多值依赖。4NF 所允许的非平凡多值依赖实际上是函数依赖。

4NF的性质:

不允许有非平凡且非函数依赖的多值依赖
允许的非平凡多值依赖实际是函数依赖（4NF定义）
平凡的多值依赖属于第四范式：因为可以转化为函数依赖

如果一个关系模式是4NF，则必为BCNF（符合定义）。

将多个具有多值依赖的关系拆分成多个单一的平凡多值依赖，从而达到4NF。

6.2.9 规范化小结

第七章数据库设计

7.1 数据库设计概述

7.1.1 数据库设计的特点

特点1：数据库建设的基本规律：

“三分技术，七分管理，十二分基础数据”

管理：数据库建设项目管理、企业（即应用部门）的业务管理
基础数据：数据的收集、整理、组织和不断更新是数据库建设中的重要环节

常用概念：

元数据：是数据资产管理的基础，是关于“数据的数据”。主要是描述数据自身信息，包括来源、结构、编码规范、大小、格式或其它数据特征。相当于数据表格中的表头信息。
主数据：主数据是指满足跨部门业务协同需要的、反映核心业务实体状态属性的企业（组织机构）基础信息。是信息系统互联互通的基石。通过制定主数据标准，在系统建设中规范使用数据标准，进而为业务报表编制、数据统计分析提供基础条件。

特点2：结构（数据）设计和行为（处理）设计相结合

整个设计过程中把数据库结构设计和对数据的处理设计密切结合起来。

结构和行为分离的设计

传统的软件工程：重行为设计，忽视对应用中数据语义的分析和抽象，只要有可能就尽量推迟数据结构设计的决策
早期的数据库设计：重结构设计，致力于数据模型和数据库建模方法研究，忽视了行为设计对结构设计的影响

7.1.2 数据库设计方法

手工试凑法：主要采用手工与经验相结合的方法

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

规范设计法：

基本思想：过程迭代和逐步求精

典型方法：基于 E-R 模型的设计方法、3NF（第三范式）的设计方法、面向对象的数据库设计方法、统一建模语言（UML）方法

7.1.3 数据库设计的基本步骤

数据库设计分 6 个阶段：

需求分析
概念结构设计：ER图
- 整个数据库设计的关键
- 通过对用户需求进行综合、归纳与抽象，形成一个独立于具体数据库管理系统的概念模型
逻辑结构设计：
- 将概念结构转换为某个数据库管理系统所支持的数据模型，并对其进行优化
- “关系模式” 包括全局模式和用户模式(外模式)
物理结构设计：
- 为逻辑数据结构选取一个适合应用环境的物理结构，包括存储结构和存取方法。
- 依赖于具体的DBMS。
数据库实施
数据库运行和维护

需求分析和概念设计独立于任何数据库管理系统，逻辑设计和物理设计与选用的数据库管理系统密切相关。

设计一个完善的数据库应用系统，往往是上述 6 个阶段的不断反复。

这个设计步骤既是数据库设计的过程，也包括了数据库应用系统的设计过程。

在设计过程中把数据库的设计和对数据库中数据处理的设计紧密结合起来，将这两个方面的需求分析、抽象、设计、实现在各个阶段同时进行，相互参照，相互补充，以完善两方面的设计。

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

需求分析阶段：综合各个用户的应用需求
概念结构设计阶段：形成独立于机器特点、独立于各个关系数据库管理系统产品的概念模式，这里指 E-R 图
逻辑结构设计阶段：将 E-R 图转换成具体的数据库产品支持的数据模型，如关系模型，形成数据库逻辑模式；然后根据用户处理的要求、安全性的考虑，在基本表的基础上再建立必要的视图，形成数据的外模式
物理结构设计阶段：根据关系数据库管理系统的特点和处理的需要进行物理存储安排，建立索引，形成数据库内模式

7.2 需求分析

需求分析简单地说就是分析用户的要求。

需求分析是设计数据库的起点，需求分析结果是否准确反映用户的实际要求，将直接影响到后面各阶段的设计，并影响到设计结果是否合理和实用。

需求分为两大类：

功能需求：重点关注
非功能需求 / 技术需求：后期关注

7.2.1 需求分析的任务

需求分析的任务：详细调查现实世界要处理的对象（组织、部门、企业等），充分了解原系统（手工系统或计算机系统）的工作概况，明确用户的各种需求，然后在此基础上确定新系统的功能。新系统必须充分考虑今后可能的扩充和改变。

调查的重点是“数据”和“处理”，通过调查、收集与分析，获得用户对数据库的如下要求：

信息要求。指用户需要从数据库中获得信息的内容与性质。由信息要求可以导出数据要求，即在数据库中需要存储哪些数据。
处理要求。指用户要完成的数据处理功能，对处理性能的要求。
安全性与完整性要求。

确定用户最终需求的难点

用户缺少计算机知识，不能准确地表达自己的需求，所提出的需求往往不断地变化
设计人员缺少用户的专业知识，不易理解用户的真正需求，甚至误解用户的需求

解决方法：设计人员必须不断深入地与用户进行交流，才能逐步确定用户的实际需求

7.2.2 需求分析的方法

需求分析的目标：调查清楚用户的实际要求并进行初步分析，与用户达成共识，分析与表达这些需求。

调查用户需求的具体步骤：

调查组织机构情况。
调查各部门的业务活动情况。
在熟悉业务活动的基础上，协助用户明确对新系统的各种要求，包括信息要求、处理要求、完全性与完整性要求。
确定新系统的边界。

常用的调查方法：

跟班作业。通过亲身参加业务工作来了解业务活动的情况。
开调查会。通过与用户座谈来了解业务活动情况及用户需求。
请专人介绍。
询问。对某些调查中的问题可以找专人询问。
设计调查表请用户填写。如果调查表设计得合理，则很有效。
查阅记录。查阅与原系统有关的数据记录。

分析方法：

结构化分析方法（Structured Analysis，SA）：从最上层的系统组织机构入手，采用自顶向下、逐层分解的方式分析系统。分析系统中的事物（业务数据对象）与事件（业务处理过程）。
面向对象的分析方法（O-O Analysis，OOA）：对系统中的对象数据与行为同时进行建模，建模UML模型。

对用户需求进行分析与表达后，需求分析报告必须提交给用户，征得用户的认可。下图描述了需求分析的过程。

结构化分析-数据建模：识别系统中的实体与相互关系，建立ERD

结构化分析-过程建模：识别系统中的各种事件，分析每个事件的输入、处理过程与输出，进行IPO分析（Input-Process-Output），过程建模DFD。

数据流图DFD：DFD重点描述系统事件（业务流程）的以下方面：①输入 ②处理过程 ③输出 ④数据存储（参与业务流程的数据实体）

7.2.3 数据字典

数据字典是进行详细的数据收集和数据分析所获得的主要成果。
数据字典是关于数据库中数据的描述，即元数据，而不是数据本身。
数据字典是在需求分析阶段建立，在数据库设计过程中不断修改、充实、完善的。

数据字典包括：数据项、数据结构、数据流、数据存储和处理过程。

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

1. 数据项

数据项是不可再分的数据单位。

对数据项的描述通常包括以下内容：

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

“取值范围”、“与其他数据项的逻辑关系”定义了数据的完整性约束条件，是设计数据检验功能的依据。
可以用关系规范化理论为指导，用数据依赖的概念分析和表示数据项之间的联系。

2. 数据结构

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

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

对数据结构的描述通常包括以下内容：

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

3. 数据流

数据流是数据结构在系统内传输的路径。

对数据流的描述通常包括以下内容：

数据流描述={数据流名，说明，数据流来源，数据流去向，组成：{数据结构}，平均流量，高峰期流量}

数据流来源：说明该数据流来自哪个过程
数据流去向：说明该数据流将到哪个过程去
平均流量：在单位时间（每天、每周、每月等）里的传输次数
高峰期流量：在高峰时期的数据流量

4. 数据存储

数据存储是数据结构停留或保存的地方，也是数据流的来源和去向之一。

对数据存储的描述通常包括以下内容：

数据存储描述={数据存储名，说明，编号，输入的数据流，输出的数据流，组成：{数据结构}，数据量，存取频度，存取方式}

存取频度：每小时、每天或每周存取次数及每次存取的数据量等信息
存取方式：批处理/ 联机处理；检索/ 更新；顺序检索/随机检索
输入的数据流：数据来源
输出的数据流：数据去向

5. 处理过程

处理过程的具体处理逻辑一般用判定表或判定树来描述。数据字典中只需要描述处理过程的说明性信息。

处理过程说明性信息的描述通常包括以下内容：

处理过程描述={处理过程名，说明，输入：{数据流}，输出：{数据流}，处理：{简要说明}}

简要说明：说明该处理过程的功能及处理要求。

功能：该处理过程用来做什么
处理要求：处理频度要求，如单位时间里处理多少事务，多少数据量、响应时间要求等
这些处理要求是后面物理设计的输入及性能评价的标准

把需求收集和分析作为数据库设计的第一阶段是十分重要的。第一阶段收集的基础数据（用数据字典来表达）是下一步进行概念设计的基础。强调两点：

（1）设计人员应充分考虑到可能的扩充和改变，使设计易于更改、系统易于扩充

（2）必须强调用户的参与

7.3 概念结构设计

7.3.1 概念模型

将需求分析得到的用户需求抽象为信息结构（即概念模型）的过程就是概念结构设计。

概念模型的主要特点：

能真实、充分地反映现实世界，包括事物和事物之间的联系，是现实世界的一个真实模型
易于理解，可以用它和不熟悉计算机的用户交换意见。
易于更改，当应用环境和应用要求改变时容易对概念模型修改和扩充。
易于向关系、网状、层次等各种数据模型转换。

7.3.2 E-R模型

描述概念模型的工具：E-R 模型

E-R模型的基本观点：世界是由一组称作实体的基本对象和这些对象之间的联系构成的

1. 实体之间的联系

（1）两个实体型之间的联系

一对一联系（1:1）如果对于实体集 A 中的每一个实体，实体集 B 中至多有一个（也可以没有）实体与之联系，反之亦然，则称实体集 A 与实体集 B 具有一对一联系，记为 1:1。例如，学校里一个班级只有一个正班长，而一个班长只在一个班中任职，则班级与班长之间具有一对一联系。
一对多联系（1:n）如果对于实体集 A 中的每一个实体，实体集 B 中有 n 个实体（n ⩾0 ）与之联系，反之，对于实体集 B 中的每一个实体，实体集 A 中至多只有一个实体与之联系，则称实体集 A 与实体集 B 有一对多联系，记为 1:n。
多对多联系（m:n）如果对于实体集 A 中的每一个实体，实体集 B 中有 n 个实体（n ⩾0 ）与之联系，反之，对于实体集 B 中的每一个实体，实体集 A 中也有 m 个实体（n ⩾0 ）与之联系，则称实体集 A 与实体集 B 具有多对多联系，记为 m:n。

（2）两个以上的实体型之间的联系

一般地，两个以上的实体型之间也存在着一对一、一对多、多对多联系。

例如，对于课程、教师与参考书 3 个实体型，如果一门课程可以有若干个教师讲授，使用若干本参考书，而每一个教师只讲授一门课程，每一本参考书只供一门课程使用，则课程与教师、参考书之间的联系是一对多的，如图(a)所示。

例如，有三个实体型：供应商、项目、零件，一个供应商可以供给多个项目多种零件，而每个项目可以使用多个供应商供应的零件，每种零件可由不同供应商供给，由此看出供应商、项目、零件三者之间是多对多的联系，如图(b)所示。

（3）单个实体型内的联系

同一个实体集内的各实体之间也可以存在一对一、一对多、多对多联系。

例如，职工实体型内部具有领导与被领导的联系，即某一职工（干部）“领导”若干名职工，而一个职工仅被另外一个职工直接领导，因此这是一对多的联系。

2. E-R 图

E-R 图提供了表示实体型、属性和联系的方法。

Chen ERD：

实体型：用矩形表示，矩形框内写明实体名。
属性：用椭圆形表示，并用无向边将其与相应的实体型连接起来。
联系：用菱形表示，菱形框内写明联系名，并用无向边分别与有关实体型连接起来，同时在无向边旁标上联系的类型（1:1、1:n 或 m:n）。
如果一个联系具有属性，则这些属性也要用无向边与该联系连接起来。

Crow’s foot notation：

鱼尾纹符号：

One 一
Many 多
Zero or many 零或多		最小零，最大多（可选）
One or many 一个或多个		最少一个，最多多个（强制）
One and only one 独一无二		最小一个，最多一个（强制）
Zero or one 零或一		最小零，最大一个（可选）

Many to One:

Many to Many:

One to One:

举例：

*7.3.3 扩展的E-R模型

*7.3.4 UML

7.3.5 概念结构设计

1. 实体与属性的划分原则

实体应包含一系列不同的描述信息
- 如果一个数据元素有描述性信息，该数据元素应被识别为实体
- 如果一个数据元素只有一个标识名，则其应被识别为属性
实体应当表达单一、简单的概念，不应该把不相关的属性放到一个实体
属性选择
- 作为属性，不能再具有需要描述的性质。属性必须是不可分的数据项，不能包含其他属性。
- 属性不能与其他实体具有联系，即E-R图中表示的联系是实体之间的联系。
- 实体属性应当忠实于实际的业务需求，属性应该与实体密切相关，根据业务需求确定一个实体应该有哪些属性

2. E-R图的集成

E-R图的集成：在开发一个大型信息系统时，最经常采用的策略是自顶向下地进行需求分析，然后再自底向上地设计概念结构。即首先设计各子系统的分E-R图，然后将它们集成起来，得到全局E-R图。

E-R图的集成一般需要两步：

合并：解决各分E-R图之间的冲突，将分E-R图合并起来生成初步E-R图。分析——统一——合并
修改和重构：消除不必要的冗余，生成基本E-R图

（1）合并E-R图，生成初步E-R图

各个局部应用所面向的问题不同，各个子系统的E-R图之间必定会存在许多不一致的地方，称之为冲突。子系统E-R图之间的冲突主要有三类类：

属性冲突
- 属性域冲突：即属性值的类型、取值范围或取值集合不同。例如零件号，有的部门把它定义为整数，有的部门把它定义为字符型，不同部门对零件号的编码也不同。又如年龄，某些部门以出生日期形式表示职工的年龄，而另一些部门用整数表示职工的年龄。
- 属性取值单位冲突：例如，零件的重量有的以公斤为单位，有的以斤为单位，有的以克为单位。
命名冲突
- 同名异义：即不同意义的对象在不同的局部应用中具有相同的名字。
- 异名同义：即同一意义的对象在不同的局部应用中具有不同的名字。
结构冲突
- 同一对象在不同应用中具有不同的抽象：例如，职工在某一局部应用中被当作实体，而在另一局部应用中则被当作属性。解决方法通常是把属性变换为实体或把实体变换为属性，使同一对象具有相同的抽象
- 同一实体在不同子系统的E-R图中所包含的属性个数和属性排列次序不完全相同（常见）：原因是不同的局部应用关心的是该实体的不同侧面。解决方法是使该实体的属性取各子系统的E-R图中属性的并集，再适当调整属性的次序。
- 实体间的联系在不同的E-R图中为不同的类型：如实体E1与E2在一个E-R图中是多对多联系，在另一个E-R图中是一对多联系。解决方法是根据应用的语义对实体联系的类型进行综合或调整。

（2）消除不必要的冗余，设计基本的E-R图

冗余的数据：可由基本数据导出的数据
冗余的联系：可由其他联系导出的联系
并不是所有的冗余数据与冗余联系都必须加以消除，有时为了提高效率，不得不以冗余信息作为代价。

7.4 逻辑结构设计

7.4.1 E-R图向关系模型的转换

7.4.2 数据模型的优化

7.4.3 设计用户子模式

7.5 物理结构设计

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

7.5.2 关系模式存取方法选择

7.5.3 确定数据库的存储结构

7.5.4 评价物理结构

7.6 数据库的实施和维护

第八章数据库编程

8.2 过程化SQL

8.2.1 过程化SQL的块结构

过程化SQL在数据库服务器上执行，效率高（预编译）

可以扩展标准SQL的功能

业务逻辑在数据库上实现，便于根据需求修改，无需改动应用程序

基本结构是块：块之间可以互相嵌套，每个块完成一个逻辑操作

定义：DECLARE 变量、常量、游标、异常等

定义的变量、常量等只能在该基本块中使用。当基本块执行结束时，定义就不再存在。

SQL Functions定义与调用：

# 定义：
create function dept_count (dept_name varchar(20))
    			returns integer
    begin
        declare d_count integer;
        select count (* ) into d_count
        from instructor
        where instructor.dept_name = dept_name
    return d_count;
end
# 调用：
select dept_name, budget
    from department
    where dept_count (dept_name ) > 12

SQL Procedures 定义与调用：

# 定义：
create procedure dept_count_proc (in dept_name varchar(20), out d_count integer)
    begin
        select count(*) into d_count
        from instructor
        where instructor.dept_name = dept_count_proc.dept_name
    end
# 调用：
declare d_count integer;
call dept_count_proc( ‘Physics’, d_count);

执行部分：

BEGIN
	# SQL语句、过程化SQL的流程控制语句
EXCEPTION
	# 异常处理部分
END；

8.2.2 变量和常量的定义

变量定义
- 变量名数据类型 [[NOT NULL] :=初值表达式]
- 变量名数据类型 [[NOT NULL] 初值表达式]
常量定义
- 常量名数据类型 CONSTANT:=常量表达式
- 常量必须要给一个值，并且该值在存在期间或常量的作用域内不能改变。如果试图修改它，过程化SQL将返回一个异常。
赋值语句
- 变量名 :=表达式

8.2.3 流程控制

过程化SQL功能：

条件控制语句

IF-THEN，IF-THEN-ELSE和嵌套的IF语句

IF  condition  THEN
    Sequence_of_statements1;     /*条件为真时语句序列才被执行*/
ELSE
    Sequence_of_statements2;     /*条件为假或NULL时才被执行*/  
END IF

循环控制语句

LOOP，WHILE-LOOP和FOR-LOOP

LOOP
    Sequence_of_statements；    /*使用EXIT、BREAK或LEAVE等循环结束语句结束*/
END LOOP;

WHERE condition LOOP
    Sequence_of_statements；    /*条件为真时执行循环体内的语句序列*/
END LOOP;

FOR count IN [REVERSE] bound1...bound2  LOOP
     Sequence_of_statements；
END LOOP;

错误处理

如果过程化SQL在执行时出现异常，则应该让程序在产生异常的语句处停下来，根据异常的类型去执行异常处理语句。 SQL标准对数据库服务器提供什么样的异常处理做出了建议，要求过程化SQL管理器提供完善的异常处理机制。

8.3 存储过程和函数

8.3.1 存储过程

过程化 SQL 块类型

命名块：编译后保存在数据库中，可以被反复调用，运行速度较快，过程和函数是命名块
匿名块：每次执行都要编译，不能在其他过程化 SQL 块中调用

存储过程：由过程化 SQL 语句书写的过程，经编译和优化后存储在数据库服务器中，使用时只需调用

优点：

运行效率高
降低客户机和服务器之间的通信量
方便实施企业规则

存储过程的用户接口

创建存储过程

1	`CREATE OR REPLACE PROCEDURE 过程名([参数1,参数2,...]) AS<过程 SQL 块>`

执行存储过程

1	`CALL/PERFORM PROCEDURE 过程名([参数1,参数2,...])`

修改存储过程

1	`ALTER PROCEDURE 过程1 RENAME TO 过程2`

删除存储过程
1
DROP PROCEDURE 过程名

8.3.2 函数

函数：和存储过程一样，都是持久性存储模块，但是函数必须指定返回的类型

创建函数

1	`CREATE OR REPLACE FUNCTION 函数名([参数1,参数2,...]) RETURNS <类型> AS<过程 SQL 块>`

执行存储过程

1	`CALL/PERFORM FUNCTION 函数名([参数1,参数2,...])`

修改函数名

1	`ALTER FUNCTION 函数名1 RENAME TO 函数名2`

重新编译
1
ALTER FUNCTION 函数名 COMLIPE

8.6 JDBC编程

JDBC(Java Database Connectivity) API 提供了一套访问任何RDBMS的标准接口。包含组件：

JDBC Driver：驱动程序
Connection：数据库连接
Statement：增删改查SQL语句
ResultSet：执行查询返回的结果集

8.6.1 JDBC编程的基本步骤

加载目标数据库的驱动程序（jar包）
打开一个数据库连接Connection
创建一个“Statement”对象
构造SQL数据操作（DML）语句
使用 Statement 对象发送构造的SQL语句
DB Server执行SQL语句，返回ResultSet结果集，Client执行后续的应用逻辑
执行相关的异常处理
关闭Statement, Connection等对象释放资源

public static void JDBCexample(String dbid, String userid, String passwd)
{
    try ( Connection conn = DriverManager.getConnection(
        "jdbc:oracle:thin:@db.test.com:2000:testdb", userid, passwd);
        Statement stmt = conn.createStatement();
    	)
    {
        … Do Actual Work ….
    }
    catch (SQLException sqle) {
        System.out.println("SQLException : " + sqle);
    }
}

Oracle JDBC驱动连接方式:

Connecting to Oracle service name (建议使用)：

1 2	`jdbc:oracle:thin:[<user>/<password>]@//<host>[:<port>]/<service> Ex：jdbc:oracle:thin:@//myoracle.db.server:1521/orclpdb`

8.6.2 JDBC SQL 执行调用方式

execute()
- 返回true或者false：如果第一个结果是一个ResultSet对象，则返回true；如果是一个更新计数或者没有结果，则返回false。
- 通过反复调用Statement.getResultSet来检索查询返回的ResultSet对象。
- 通用于执行所有的DML（数据操作语言）和DDL（数据定义语言）语句。
executeQuery()
- 返回一个ResultSet对象。
- 用于执行SELECT查询语句。
executeUpdate()
- 返回一个表示受SQL语句影响的行数的整数。
- 用于执行INSERT（插入）、DELETE（删除）或UPDATE（更新）语句。

8.6.3 SQL注入

1. 预编译语句

Prepared Statement（预编译语句）是一种用于执行SQL查询和更新操作的安全编程技术。

PreparedStatement pStmt = conn.prepareStatement(
    "insert into instructor values(?,?,?,?)");
pStmt.setString(1, "88877");
pStmt.setString(2, "Perry");
pStmt.setString(3, "Finance");
pStmt.setInt(4, 125000);
pStmt.executeUpdate();
pStmt.setString(1, "88878");
pStmt.executeUpdate();

当从用户获取输入并将其添加到查询中时，始终使用预编译语句。绝不要通过字符串拼接来创建查询，因为这会增加SQL注入的风险。

2. SQL注入

SQL注入是一种高级的代码注入技术，发生在应用程序与数据库交互层的安全漏洞。

如果在输入的查询字符串之中注入了特别的SQL指令，当设计不良的程序忽略了特殊字符或者某些逻辑检查，那么这些注入进去的恶意SQL指令就会被数据库服务器执行，因此遭到破坏或是入侵。

攻击者通过专门构造传递给数据库的SQL字符串来修改SQL自身的语法和功能，从而实现恶意查询或者数据破坏的意图。

SQL注入产生的技术根源：典型的B/S应用程序三层架构

前台的查询条件传递给中间的WEB服务器
WEB服务器通过构建合适的SQL语句发送给后台的DB服务器执行
如果应用程序对前台的查询字符串不做特殊字符串或者关键字的检查和过滤，可能就会导致SQL注入

漏洞产生原因：开发人员应用SQL API实现数据操作逻辑，通常只关心业务逻辑，缺乏安全编程概念与意识

动态构造SQL字符串（拼接），未做特殊字符串安全过滤
不安全的数据库配置与权限设置：
- 默认数据库系统账号/密码
- 权限过大，非“最小权限”原则，没有根据实际需求设置权限
- 程序中使用DBA角色等

3. SQL注入测试

识别SQL注入：推理测试

WEB 应用：HTTP get/post 请求

经典的单引号判断法 http://xxx/abc.php?id=1’

如果页面返回错误，则存在 Sql 注入。原因是无论字符型还是整型都会因为单引号个数不匹配而报错。如果未报错，不代表不存在 SQL 注入。

4. SQL注入类型

整数注入：

含有漏洞的代码为：

1
2
3

sql = "SELECT * FROM clients WHERE " .
"account = $formacct AND " .
"pin = $formpin";

如果输入：

1 2	`$formacct = 1 or 1=1 # $formpin = 1111`

最后的sql结果为：

1
2
3

SELECT * FROM clients
WHERE account = 1 or 1=1
# AND pin = 1111

字符串注入：

含有漏洞的代码为：

1	`sql = "SELECT * FROM users WHERE username = ' " + user + " ' AND password = ' " + pwd + " ' ";`

对username进行注入：

1	`user = " admin' OR '1'='1 "`

对password进行注入：

1	`pwd = " ' OR '1'='1 "`

SQL注释：
- 单行注释：-- ，MySQL：#
- 多行注释：/* */
执行多条SQL语句：

username的输入为：Admin’ or 1=1;INSERT INTO Users VALUES (‘root’, ‘123456’); --，由于分号，SQL语句变成两句。

Union注入：查询额外的信息

1	`Select * form users where username=‘admin’ union select * from users;`

5. 预防SQL注入

预编译语句
根本的解决方案：检查用户输入，转义特殊字符

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

查询优化分类：

代数优化：指关系代数表达式的优化
物理优化：指存取路径和底层操作算法的选择

9.1 关系数据库系统的查询处理

9.1.1 查询处理步骤

查询处理步骤

查询分析：对查询语句进行扫描、词法分析和语法分析
- 词法分析：从查询语句中识别出正确的语言符号
- 语法分析：进行语法检查
查询检查：检查查询的合法性，例如数据模型完整性检查、安全性检查（DAC/MAC定义的权限）等。
- 检查语句中的数据库对象，如关系名、属性名是否存在和有效
- 用视图消解方法把对视图的操作转换成对基本表的操作
- 用用户权限和完整性约束定义对用户的存取权限进行检查
- 检查通过后把SQL查询语句转换成内部表示，即等价的关系代数表达式
- 关系数据库管理系统一般都用查询树，也称为语法分析树来表示扩展的关系代数表达式。
查询优化：选择高效的查询执行策略。
- 分类：代数优化/逻辑优化、物理优化
- 查询优化的依据：基于规则、基于代价、基于语义
查询执行：按优化器的执行策略运行查询。

9.1.2 实现查询操作的算法示例

1. 选择操作的实现

实现方法：

全表扫描方法
索引扫描方法：通过索引先找到满足条件的元组主码或元组指针，再通过元组指针直接在查询的基本表中找到元组

Index的一般结构：B+树

多路搜索平衡树，高度一般3~4层，搜索性能稳定
非叶子节点仅用作索引，数据全部在叶子节点
叶子节点左小右大排序，用指针连在一起

若选择时有多个条件，可有两种解决算法：Sdept＝‘CS’ AND Sage>20，如果Sdept和Sage上都有索引：

分别用上面两种方法分别找到Sdept＝‘CS’的一组元组指针和Sage>20的另一组元组指针（使用B+树索引找到Sage=20的索引项，以此为入口点在B+树的顺序集上得到Sage>20的所有元组指针），然后求这两组指针的交集
找到Sdept＝‘CS’的一组元组指针，通过这些元组指针到student表中检索，对得到的元组检查另一些选择条件(如Sage>20)是否满足

2. 连接操作的实现

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

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

实现方法：

嵌套循环算法(nested loop join)
- 对外层循环(Student表)的每一个元组(s)，检索内层循环(SC表)中的每一个元组(sc)
- 直到外层循环表中的元组处理完为止。
- 理想的情况是：外表较小，内表的连接字段有唯一索引，或者非唯一索引的区分度较高。通常可以快速返回前面的几条查询记录。
排序-合并算法(sort-merge join 或merge join)
- 先对Student表和SC表按连接属性Sno排序。取Student表中第一个Sno，依次扫描SC表中具有相同Sno的元组。当扫描到Sno不相同的第一个SC元组时，返回Student表扫描它的下一个元组，再扫描SC表中具有相同Sno的元组，把它们连接起来。重复上述步骤直到Student 表扫描完。
- Student表和SC表都只要扫描一遍。
- 如果两个表原来没有排序，执行时间要加上对两个表的排序时间。
- 可适用于等值、非等值，但是不能用于!=运算
索引连接(index join)
- 在SC表上已经建立属性Sno的索引。对Student中每一个元组，由Sno值通过SC的索引查找相应的SC元组。循环执行，直到Student表中的元组处理完为止。
Hash Join算法
- 把连接属性作为hash码，用同一个hash函数把Student表和SC表中的元组散列到hash表中。
- 划分阶段：对包含较少元组的表(如Student表)进行一遍处理，把它的元组按hash函数分散到hash表的桶(bucket)中。
- 试探阶段：对另一个表(SC表)进行一遍处理，利用相同的hash函数将相匹配的元组连接起来。
- Hash Join是做大数据集连接时的常用方式。
- 算法前提：适用于较小的表完全可以放于内存中的情况。
- Hash Join只能应用于等值连接。

9.2 关系数据库系统的查询优化

9.2.1查询优化概述

查询优化的优点：

用户不必考虑如何最好地表达查询以获得较好的效率
系统可以比用户程序的“优化”做得更好

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

执行代价：

集中式数据库 磁盘存取块数(I/O代价)（主要）、处理机时间(CPU代价)、查询的内存开销
分布式数据库总代价 = I/O 代价 + CPU 代价 + 内存代价 + 通信代价

9.2.2一个实例

9.3 代数优化

9.3.1 关系代数表达式等价变换规则

代数优化策略：通过对关系代数表达式的等价变换来提高查询效率

关系代数表达式等价：指用相同的关系代替两个表达式中相应的关系所得到的结果是相同的

常用的等价变换规则：

连接、笛卡尔积交换律
连接、笛卡尔积的结合律
投影的串接定律
选择的串接定律：选择条件可以合并，一次就可检查全部条件
选择与投影操作的交换律
选择与笛卡尔积的交换律：使部分选择在笛卡尔积前先做
选择与并、差、自然连接的分配律
投影与并、笛卡尔积的分配律（投影与差没有分配律）

9.3.2 查询树的启发式优化

典型的启发式规则有：

（1）选择运算应尽可能先做：在优化策略中这是最重要、最基本的一条。

（2）把投影运算和选择运算同时进行

（3）把投影同其前或后的双目运算结合起来

（4）把某些选择同在它前面要执行的笛卡尔积结合起来成为一个连接运算

（5）找出公共表达式

下面给出[例9.3]中 SQL语句的代数优化示例：

SELECT Student.Sname
FROM Student, SC
WHERE Student.Sno=SC.Sno
	AND SC.Cno=’2’

利用规则4、6把选择σSC.Cno=‘2’移到叶端，查询树便转换成下图优化的查询树。这就是9.2.2节中Q3的查询树表示。

9.4 物理优化

代数优化改变查询语句操作的次序和组合，不涉及底层的存取路径

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

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

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

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

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

对于选择条件是“主码＝值”的查询查询结果最多是一个元组，可以选择主码索引
对于选择条件是“非主属性＝值”的查询，并且选择列上有索引要估算查询结果的元组数目如果比例较小(<10%)可以使用索引扫描方法，否则还是使用全表顺序扫描
对于选择条件是属性上的非等值查询或者范围查询，并且选择列上有索引 同2方法
对于用AND连接的合取选择条件

如果有涉及这些属性的组合索引优先采用组合索引扫描方法
如果某些属性上有一般的索引，可以用索引扫描方法通过分别查找满足每个条件的指针，求指针的交集通过索引查找满足部分条件的元组，然后在扫描这些元组时判断是否满足剩余条件
其他情况：使用全表顺序扫描

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

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

如果2个表都已经按照连接属性排序：选用排序-合并算法
如果一个表在连接属性上有索引：选用索引连接算法
如果上面2个规则都不适用，其中一个表较小：选用Hash join算法
可以选用嵌套循环方法，并选择其中较小的表，确切地讲是占用的块数(b)较少的表，作为外表(外循环的表)

9.4.2 基于代价的优化

1. 统计信息

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

优化器需要的统计信息：

对每个基本表该表的元组总数(N) 元组长度(l) 占用的块数(B) 占用的溢出块数(BO)
对基表的每个列该列不同值的个数(m) 列最大值最小值列上是否已经建立了索引哪种索引(B+树索引、Hash索引、聚集索引) 可以计算选择率(f) 如果不同值的分布是均匀的，f＝1/m 如果不同值的分布不均匀，则要计算每个值的选择率，f＝具有该值的元组数/N
对索引索引的层数(L) 不同索引值的个数索引的选择基数S(有S个元组具有某个索引值) 索引的叶结点数(Y)

2. 代价估算示例

全表扫描算法的代价估算公式
- 如果基本表大小为B块，全表扫描算法的代价 cost＝B
- 如果选择条件是“码＝值”，那么平均搜索代价 cost＝B/2
索引扫描算法的代价估算公式
- 如果选择条件是“码＝值” 则采用该表的主索引若为B+树，层数为L，需要存取B+树中从根结点到叶结点L块，再加上基本表中该元组所在的那一块，所以cost=L+1
- 如果选择条件涉及非码属性若为B+树索引，选择条件是相等比较，S是索引的选择基数(有S个元组满足条件) 满足条件的元组可能会保存在不同的块上，所以(最坏的情况)cost=L+S
- 如果比较条件是＞，＞＝，＜，＜＝操作假设有一半的元组满足条件就要存取一半的叶结点通过索引访问一半的表存储块 cost=L+Y/2+B/2 如果可以获得更准确的选择基数，可以进一步修正Y/2与B/2
嵌套循环连接算法的代价估算公式
- 嵌套循环连接算法的代价 cost＝Br+BrBs/(K-1)
- 如果需要把连接结果写回磁盘 cost＝Br+Br Bs/(K-1)+(FrsNrNs)/Mrs 其中Frs为连接选择性(join selectivity)，表示连接结果元组数的比例 Mrs是存放连接结果的块因子，表示每块中可以存放的结果元组数目
排序-合并连接算法的代价估算公式
- 如果连接表已经按照连接属性排好序，则 cost＝Br+Bs+(FrsNrNs)/Mrs
- 如果必须对文件排序还需要在代价函数中加上排序的代价

第十章数据库恢复技术

10.1 事务的基本概念

事务：用户定义的一个数据库操作序列，这些操作要么全做，要么全不做，是一个不可分割的工作单位。
是恢复和并发控制的基本单位

事务定义

BEGIN TRANSACTION                
    SQL 语句1 
    SQL 语句2 
COMMIT / ROLLBACK

事务结束
- COMMIT：事务正常结束，提交事务的所有操作
- ROLLBACK：事务异常终止，事务滚回到开始时的状态
事务的ACID特性：
- 原子性：事务是数据库的逻辑工作单位
- 一致性：事务执行的结果必须是使数据库从一个一致性状态变到另一个一致性状态
- 隔离性：一个事务的执行不能被其他事务干扰
- 持续性：一个事务一旦提交，它对数据库中数据的改变就应该是永久性的

10.2 数据库恢复概述

故障是不可避免的

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

10.3 故障的种类

事务内部的故障
- 故障是非预期的：包括运算溢出、并发事务死锁、违反完整性而终止
- 事务故障意味着没有达到预期的终点，数据库可能处于不正确状态
- 事务故障的恢复：事务撤消（UNDO）
系统故障
- 称为软故障，是指造成系统停止运转的任何事件，使得系统要重新启动
- 例如：硬件错误、操作系统故障、数据库管理系统代码错误、系统断电
- 故障时，一些尚未完成的事务的结果可能已送入物理数据库，造成数据库可能处于不正确状态。恢复策略：系统重新启动时，恢复程序让所有非正常终止的事务回滚，强行撤消（UNDO）所有未完成事务
- 故障时，有些已完成的事务可能有一部分甚至全部留在缓冲区，尚未写回到磁盘上的物理数据库中，系统故障使得这些事务对数据库的修改部分或全部丢失。恢复策略：系统重新启动时，恢复程序需要重做（REDO）所有已提交的事务。
介质故障
- 为硬故障，指外存故障
- 例如磁盘损坏等
- 介质故障比前两类故障的可能性小得多，但破坏性大得多
计算机病毒

10.4 恢复的实现技术

恢复操作的基本原理：冗余
如何建立冗余数据
- 数据转储：转储是指数据库管理员定期地将整个数据库文件复制到磁带、磁盘或其他存储介质上保存起来的过程，备用的数据文本称为后备副本。
  - 静态转储：在系统中无运行事务时进行的转储操作
  - 动态转储：转储操作与用户事务并发进行
  - 海量转储：每次转储全部数据库
  - 增量转储：只转储上次转储后更新过的数据
- 登记日志文件
  - 事务故障恢复和系统故障恢复必须用日志文件
  - 在动态转储方式中必须建立日志文件，后备副本和日志文件结合起来才能有效地恢复数据库
  - 登记的次序严格按并发事务执行的时间次序
  - 必须先写日志文件，后写数据库

10.5 恢复策略

事务故障：事务在运行至正常终止点前被终止
- 恢复方法：利用日志文件撤消(UNDO)此事务已对数据库进行的修改
- 反向扫描文件日志(即从最后向前扫描日志文件)，查找该事务的更新操作。对该事务的更新操作执行逆操作。即将日志记录中“更新前的值” 写入数据库。
系统故障
- 撤销(UNDO)未完成的事务：反向扫描日志文件，对每个撤销事务更新操作执行逆操作
- 重做(REDO)已完成事务：正向扫描日志文件，对每个重做事务重新执行登记的操作
- 系统故障的恢复由系统在重新启动时自动完成，不需要用户干预
介质故障
- 重装数据库
- 重做已完成的事务

10.6 具有检查点的恢复技术

问题的提出：

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

具有检查点（checkpoint）的恢复技术：

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

检查点记录的内容：

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

重新开始文件的内容：

记录各个检查点记录在日志文件中的地址
类似索引记录

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

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

第十一章并发控制

多事务执行方式
- 事务串行执行：每个时刻只有一个事务运行，其他事务必须等到这个事务结束以后方能运行
- 交叉并发方式：事务的并行执行是这些并行事务的并行操作轮流交叉运行
- 同时并发方式：多处理机系统中，每个处理机可以运行一个事务，多个处理机可以同时运行多个事务，实现多个事务真正的并行运行
数据库管理系统必须提供并发控制机制

11.1 并发控制概述

并发控制基本单位：事务
并发操作带来的数据不一致性

事务1 事务2

丢失修改 Update Update

不可重复读 Read Update/Delete/Insect

读“脏”数据 Rollback Update Read
并发控制的主要技术
- 封锁
- 时间戳
- 乐观控制法
- 多版本并发控制

	事务1	事务2
丢失修改	Update	Update
不可重复读	Read	Update/Delete/Insect
读“脏”数据	Rollback Update	Read

11.2 封锁

封锁：事务在对某个数据对象操作之前，先向系统发出请求，对其加锁
基本封锁类型
- 排它锁（X 锁）：写锁若事务T对数据对象A加上X锁，则只允许T读取和修改A，其它任何事务都不能再对A加任何类型的锁，直到T释放A上的锁
- 共享锁（S 锁）：读锁若事务T对数据对象A加上S锁，则事务T可以读A但不能修改A，其它事务只能再对A加S锁，而不能加X锁，直到T释放A上的S锁；即保证其他事务可以读A，但是不能修改。

11.3 封锁协议

封锁协议：在运用X锁和S锁对数据对象加锁时约定的规则
- 何时申请 X 锁或 S 锁
- 持续时间
- 何时释放
三级封锁协议
1. 一级封锁协议：事务 T 在修改数据 R 之前必须先对其加 X 锁，直到事务结束才释放
  - 防止丢失修改，不能保证可重复读和不读“脏”数据
2. 二级封锁协议：一级封锁协议+事务 T 在读取数据 R 之前必须先对其加 S 锁，读完后即可释放 S锁
  - 防止丢失修改和不读“脏”数据，不能保证可重复读
3. 三级封锁协议：一级封锁协议+事务 T 在读取数据R之前必须先对其加 S 锁，直到事务结束才释放
  - 防止丢失修改、读“脏”数据和不可重复读

11.4 活锁和死锁

活锁：封锁导致的某个事务永远等待
避免活锁：采用先来先服务的策略
死锁：封锁导致的事务永远不能结束
避免死锁
- 预防死锁
  - 一次封锁法：一次将所有要用的数据全部加锁，降低系统并发度
  - 顺序封锁法：所有事务按某个顺序加锁，成本高难实现
- 诊断死锁
  - 超时法：超过规定时限就认为发生了死锁
  - 等待图法：用事务等待图动态反映所有事务的等待情况
- 解除死锁
  - 选择一个处理死锁代价最小的事务，将其撤消

11.5 并发调度的可串行性

可串行化调度：多个事务的并发执行是正确的，当且仅当其结果与按某一次序串行地执行这些事务时的结果相同
- 可串行性
冲突：调度中一对连续的动作，它们满足：如果它们的顺序交换，那么涉及的事务中至少有一个事务的行为会改变
有冲突的两个操作是不能交换次序的，没有冲突的两个事务是可交换的
冲突可串行化：可串行化调度+交换不冲突操作次序得到的调度仍然是可串行化调度

11.6 两段锁协议

两段锁协议：所有事务必须分两个阶段对数据项加锁和解锁
- 用于实现并发调度的可串行性，遵守两段锁协议是可串行化调度的充分条件
- 在对任何数据进行读、写操作之前，事务首先要获得对该数据的封锁。在释放一个封锁之后，事务不再申请和获得任何其他封锁
- 第一阶段，扩展阶段：获得封锁
- 第二阶段，收缩阶段：释放封锁
一次封锁法遵守两段锁协议，但是遵守两段锁协议的事务可能发生死锁

11.7 封锁的粒度

封锁粒度：封锁对象的大小
- 封锁的粒度越大，数据库所能够封锁的数据单元就越少，并发度就越小，系统开销也越小
多粒度封锁：一个系统中同时支持多种封锁粒度供不同的事务选择
- 多粒度树：用树形结构表示封锁粒度，根节点数据粒度最大
- 多粒度封锁数据对象可能以两种方式封锁
  1. 显式封锁
  2. 隐式封锁：因为上级结点加锁而加锁
意向锁：对任一结点加基本锁，必须先对它的上层结点加意向锁
- 目的：提高对某个数据对象加锁时系统的检查效率
- 种类
  1. 意向共享锁，IS 锁：它的后裔节点拟意向加 S 锁
  2. 意向排他锁，IX 锁：它的后裔节点拟意向加 X 锁
  3. 共享意向排他锁，SIX 锁：加 SIX 锁=加 S 锁+加 IX 锁

#大三上 #期末复习 #数据库

数据库原理与安全 | 笔记2

https://harrison-1eo.github.io/2023/12/19/数据库笔记2/

作者

Harrison

发布于

2023年12月19日

更新于

2023年12月31日

许可协议

网络内容安全 | 内容要点总结上一篇

数据库原理与安全 | 笔记1 下一篇

数据库原理与安全 | 笔记2

第六章 关系数据理论

6.1 问题的提出

6.2 规范化

6.2.1 函数依赖

1.函数依赖

2.平凡函数依赖与非平凡函数依赖

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

4.传递函数依赖

6.2.2 码/键(Key)

1. 候选键/超键/主键

2. 主属性/非主属性

3. 外码

4. 函数依赖的公理

5. 函数依赖的公理系统

6.2.3 范式(Normal Form, NF)

6.2.4 2NF

6.2.5 3NF

6.2.6 BCNF

6.2.7 多值依赖

6.2.8 4NF

6.2.9 规范化小结

第七章 数据库设计

7.1 数据库设计概述

7.1.1 数据库设计的特点

7.1.2 数据库设计方法

7.1.3 数据库设计的基本步骤

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

7.2 需求分析

7.2.1 需求分析的任务

7.2.2 需求分析的方法

7.2.3 数据字典

7.3 概念结构设计

7.3.1 概念模型

7.3.2 E-R模型

*7.3.3 扩展的E-R模型

*7.3.4 UML

7.3.5 概念结构设计

7.4 逻辑结构设计

7.4.1 E-R图向关系模型的转换

7.4.2 数据模型的优化

7.4.3 设计用户子模式

7.5 物理结构设计

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

7.5.2 关系模式存取方法选择

7.5.3 确定数据库的存储结构

7.5.4 评价物理结构

7.6 数据库的实施和维护

第八章 数据库编程

8.2 过程化SQL

8.2.1 过程化SQL的块结构

8.2.2 变量和常量的定义

8.2.3 流程控制

8.3 存储过程和函数

8.3.1 存储过程

8.3.2 函数

8.6 JDBC编程

8.6.1 JDBC编程的基本步骤

8.6.2 JDBC SQL 执行调用方式

8.6.3 SQL注入

1. 预编译语句

2. SQL注入

3. SQL注入测试

4. SQL注入类型

5. 预防SQL注入

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

9.1 关系数据库系统的查询处理

9.1.1 查询处理步骤

9.1.2 实现查询操作的算法示例

1. 选择操作的实现

2. 连接操作的实现

9.2 关系数据库系统的查询优化

9.2.1查询优化概述

9.2.2一个实例

9.3 代数优化

9.3.1 关系代数表达式等价变换规则

9.3.2 查询树的启发式优化

9.4 物理优化

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

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

第六章关系数据理论

第七章数据库设计

第八章数据库编程

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

第十章数据库恢复技术

第十一章并发控制