内容概要：数据库基本知识、关系数据库、SQL语言、数据库安全性、数据库完整性、关系数据理论、数据库设计、数据库编程、关系查询的处理和优化、恢复技术、并发控制

绪论

目标：主要基本概念的理解和记忆，要注意区分归纳

基本概念⭐

• 数据：是描述事物的符号记录。数据的含义称为数据的语义，数据与其语义是不可分的。

• 数据库：是长期存储在计算机内、有组织的、可共享的大量数据的集合。

• 数据库管理系统：是位于用户与操作系统之间的一层数据管理软件。它具有数据的定义、组织、存储、管理、操纵功能，数据库的建立、运行、管理、维护功能。

• 数据库系统：是由数据库、数据库管理系统（及其开发工具）、应用程序、数据库管理员组成的存储、管理、处理和维护数据的系统。

• 数据库系统结构图(五层)

  

• 计算机层次结构(五层)

  

数据库管理技术

• 数据库管理技术的三个阶段：人工管理、文件系统、数据库系统

• 各阶段特点

  	人工管理阶段	文件系统阶段	数据库系统阶段
  数据的管理者	用户（程序员）	文件系统	数据库管理系统
  数据面向的对象	某一应用程序	某一应用程序	现实世界
  数据的共享程度	无共享，冗余度极大	共享性差，冗余度大	共享性高
  数据的独立性	不独立，完全依赖于程序	独立性差	高度的物理独立性和一定的逻辑独立性
  数据的结构化	无结构	记录内有结构、整体无结构	整体结构化
  数据控制能力	应用程序自己控制	应用程序自己控制	由数据库管理系统统一管理和控制

数据库系统的特点⭐

• 数据结构化：实现整体数据的结构化
• 高共享、低冗余：数据共享可减少数据冗余，节约空间；易于扩充
• 数据独立性高：包括物理独立性和逻辑独立性
• 由DBUS统一管理和控制：数据的安全性保护、完整性检查、并发控制、数据库恢复

数据模型⭐

数据模型是对现实世界数据特征的抽象

现实世界→概念模型→逻辑模型→物理模型

根据模型应用的不同，模型划分成两类：

• 概念模型：也称信息模型，从用户的观点来对数据和信息建模，主要用于数据库设计；

• 逻辑模型和物理模型

  • 逻辑模型主要包括：层次模型、网状模型、关系模型、面向对象模型和对象关系模型等；
  • 物理模型是对数据最低层的抽象，描述数据在系统内部的表示方式和存取方法，在磁盘或磁带上的存储方式和存取方法，是面向计算机系统的。

概念模型⭐

概念模型的表示方法：E—R方法(实体—联系)

• 实体：客观存在并可相互区别的事物。可是具体的人、事、物或抽象概念

• 属性：实体所具有的某一特性。一个实体可以有若干个属性刻画。

  • 用椭圆形表示，并用无向边将其与相应的实体连接起来
  

• 码：唯一标识实体的属性集

• 域：属性的取值范围。称为属性的域

• 实体型：同类实体称为实体型。

  • 用矩形表示，矩形框内写实体名。
  

• 实体集：同型实体的集合称为实体集

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

  • 联系本身：用菱形表示，菱形框内写明联系名， 并用无向边分别与有关实体型连接起来，同时在无向边旁标上联系的类型（1:1、1:n或m:n）

    

    

  • 联系的属性：联系本身也是一种实体型，也可以有属性。如果一个联系具有属性，则这些属性也要 用无向边与该联系连接起来

实体集间联系

• 一对一联系 (一个班级只有一个正班长)
• 一对多联系（一个班级中有若干名学生）
• 多对多联系（一门课可被若干学生选修，一名学生也可选修多门课）

数据模型

包括逻辑模型和物理模型

组成要素

• 数据结构：描述数据库组成对象以及对象之间的联系
• 数据操作：对数据库中各种对象（型）的实例（值）允许执行的操作及有关的操作规则
• 完整性约束： 一组完整性规则的集合

常用的数据模型

• 层次模型（树）
• 网状模型（图）
• 关系模型（表）
• 面向对象数据模型
• 对象关系数据模型
• 半结构化数据模型

层次模型

满足下面两个条件的基本层次联系的集合为层次模型。

• 有且只有一个结点没有双亲结点，这个结点称为根结点
• 根以外的其它结点有且只有一个双亲结点

表示方法

• 实体型：用记录类型描述。 每个结点表示一个记录类型。
• 属性：用字段描述。每个记录类型可包含若干个字段。
• 联系：用结点之间的连线表示记录（类）型之间的一对多的联系

对于多对多联系，将其分解成一对多联系

方法：冗余结点法、虚拟结点法

层次模型的数据操纵

• CRUD

层次模型的完整性约束

• 无相应的双亲结点值就不能插入子女结点值
• 如果删除双亲结点值，则相应的子女结点值也被同时删除
• 更新操作时，应更新所有相应记录，以保证数据的一致性

层次模型的优缺点

• 优点
  • 层次数据模型简单，对具有一对多的层次关系的部门描述自然、直观，容易理解
  • 性能优于关系模型，不低于网状模型
  • 层次数据模型提供了良好的完整性支持
• 缺点
  • 多对多联系表示不自然
  • 对插入和删除操作的限制多
  • 查询子女结点必须通过双亲结点
  • 层次命令趋于程序化

网状模型

满足下面两个条件的基本层次联系的集合为网状模型。

• 允许一个以上的结点无双亲；
• 一个结点可以有多于一个的双亲

表示方法（与层次数据模型相同）

• 对于多对多联系，将其分解成一对多联系

网状模型的数据操纵

• CRUD

网状数据模型的完整性约束

• 允许插入尚未确定双亲结点值的子女结点值
• 允许只删除双亲结点值

网状模型的优缺点

• 优点
  • 能够更为直接地描述现实世界，如一个结点可以有多个双亲
  • 具有良好的性能，存取效率较高
• 缺点
  • 结构比较复杂，而且随着应用环境的扩大，数据库的结构就变得越来越复杂，不利于最终用户掌握
  • DDL、DML语言复杂，用户不容易使用

关系模型⭐

关系模型的基本概念

• 关系（Relation ）：一个关系对应通常所说的一张表。

• 元组（Tuple ）：表中的一行即为一个元组。

• 属性（Attribute ）：表中的一列即为一个属性，给每一个属性起一个名称即属性名。

• 码（Key ）：表中的某个属性组，它可以唯一确定一个元组。

• 域（Domain ）：属性的取值范围。

• 分量：元组中的一个属性值。

• 关系模式：对关系的描述

  • 关系名（属性 1，属性 2，…，属性 n ）

    例：学生（学号，姓名，年龄，性别，系，年级）

关系模式由五部分组成，即它是一个五元组：

• R（U,D,DOM,F）
  • R：关系名
  • U：组成该关系的属性名集合
  • D：属性组U中属性所来自的域
  • DOM：属性向域的映象集合
  • F：属性间数据的依赖关系集合

关系模型的数据操纵

• 查询、插入、删除、更新
• 数据操作是集合操作，操作对象和操作结果都是关系，即若干元组的集合
• 存取路径对用户隐蔽，用户只要指出 “干什么”，不必详细说明“怎么干“

完整性约束

• 实体完整性、参照完整性、用户定义的完整性

关系数据模型的存储结构

• 表以文件形式存储
• 有的DBMS一个表对应一个操作系统文件
• 有的DBMS自己设计文件结构

关系模型的优缺点

• 优点

  • 建立在严格的数学概念的基础上
  • 概念单一，数据结构简单、清晰，用户易懂易用
    • 实体和各类联系都用关系来表示。
    • 对数据的检索结果也是关系。
  • 关系模型的存取路径对用户透明
    • 具有更高的数据独立性，更好的安全保密性
    • 简化了程序员的工作和数据库开发建立的工作

• 缺点

  • 存取路径对用户透明导致查询效率往往不如非关系数据模型

  • 为提高性能，必须对用户的查询请求进行优化增加了开发数据库管理系统的难度

数据库的系统结构

DB系统内部的模式结构⭐

从数据库管理系统角度看

数据库系统模式的概念

• “型” 和“值” 的概念
  • 型 （Type ） 对某一类数据的结构和属性的说明
  • 值 （Value ） 是型的一个具体赋值

例如：学生记录

记录型：

（学号，姓名，性别，系别，年龄，籍贯）

该记录型的一个记录值

（900201，李明，男，计算机，22，江苏）

• 模式（Schema ）
  • 数据库逻辑结构和特征的描述
  • 是型的描述
  • 反映的是数据的结构及其联系
  • 模式是相对稳定的
• 模式的一个实例（Instance ）
  • 模式的一个具体值
  • 反映数据库某一时刻的状态
  • 同一个模式可以有很多实例
  • 实例随数据库中的数据的更新而变动

数据库系统的三级模式与两级映象

• 外模式

  外模式也称子模式（Subschema）或用户模式，它是数据库用户（包括应用程序员和最终用户）最终能够看见的和使用的局部数据的逻辑结构和特征的描述，是数据库用户的数据视图，是与某一应用有关的数据的逻辑表示。

  外模式面向具体的应用程序，它定义在模式之上，但独立于存储模式和存储设备。设计外模式时应充分考虑到应用的扩充性。外模式通常是模式的子集。一个数据库可以有多个外模式。外模式是保证数据库安全性的一个有力措施。

• 模式

  模式也称逻辑模式，是数据库中全体数据的逻辑结构和特征的描述，是所有用户的公共数据视图。它是数据库系统模式结构的中间层，既不涉及数据的物理存储细节和硬件环境，也与具体的应用程序、所使用的应用开发工具以及高级程序设计语言无关。模式是数据库的中心与关键，它独立于数据库的其他层次。设计数据库模式结构时应首先确定数据库的模式。

  模式实际上是数据库数据在逻辑级上的视图。一个数据库只有一个模式。数据库模式以某一种数据模型为基础，统一综合地考虑了所有用户的需求，并将这些需求有机地结合成一个逻辑整体。模式定义包括数据的逻辑结构定义、数据之间的联系定义以及安全性、完整性要求的定义。

• 内模式

  内模式也称存储模式（Storage Schema），一个数据库只有一个内模式，它是数据物理结构和存储方式的描述，是数据在数据库内部的表示方式。内模式依赖于它的全局逻辑结构，但独立于数据库的用户视图即外模式，也独立于具体的存储设备。

  例如，记录的存储方式是顺序存储、按照B树结构存储还是按HASH方法存储；索引按照什么方式组织；数据是否压缩存储，是否加密；数据的存储记录结构有何规定等。

数据库系统的三级模式是对数据的三个抽象级别，它把数据的具体组织留给DBMS管理，使用户能逻辑抽象地处理数据，而不必关心数据在计算机中的表示和存储。

为了能够在内部实现这三个抽象层次的联系和转换，数据库系统在这三级模式之间提供了二级映像：外模式/模式映像和模式/内模式映像。正是这两层映像保证了数据库系统中的数据能够具有较高的逻辑独立性（外模式／模式映象）和物理独立性（模式／内模式映象）。

DB系统外部的体系结构

从数据库最终用户角度看

• 单用户结构
• 主从式结构
• 分布式结构
• 客户/服务器结构
• 浏览器/应用服务器/数据库服务器结构

关系数据库

目标:基本概念理解，关系代数查询语言会写

关系代数⭐

关系代数：是一种抽象的查询语言，用对关系的运算来表达查询。

关系代数运算的三个要素：

• 运算对象：关系
• 运算结果：关系
• 运算符：四类
  • 集合运算符
  • 专门的关系运算符
  • 算术比较符
  • 逻辑运算符

选择

• 选择又称为限制（Restriction）

• 选择运算符的含义

  • 在关系R中选择满足给定条件的诸元组

    $\sigma_{F}(R)=${${t|t\in{R}\wedge{F(t)=}}$‘真’}

  • F：选择条件，是一个逻辑表达式，基本形式为： X1θY1

θ：比较运算符（＞，≥，＜，≤，＝或<>）

X1，Y1等：属性名、常量、简单函数；属性名也可以用它的 序号来代替

• 选择运算是从行的角度进行的运算

  

投影

• 选择运算符的含义

  • 从R中选择出若干属性列组成新的关系

    $\prod_{A}(R)=${$t[A]|t\in{R}$}

    A：R中的属性列

• 投影操作主要是从列的角度进行运算

  

连接

• 连接也称为θ连接

• 连接运算的含义

  • 从两个关系的笛卡尔积中选取属性间满足一定条件的元组

  • $R\mathop{\bowtie}\limits_{A\theta{B}}S=${$\widehat{t_rt_s}|t_r\in{R}\wedge{t_s}\in{S}\wedge{t_r[A]\theta{t_s[B]}}$}

    A和B：分别为R和S上度数相等且可比的属性组

    θ：比较运算符

• 连接运算从R和S的广义笛卡尔积R×S中选取（R关系）在A属性组上的值与（S关系）在B属性组上值满足比较关系的元组。

• 两类常用连接运算

  • 等值连接（equijoin）
    • 从关系R与S的广义笛卡尔积中选取A、B属性值相等的那些元组，
    • θ为“＝”的连接运算称为等值连接
  • 自然连接（Natural join）
    • 自然连接是一种特殊的等值连接
    • 两个关系中进行比较的分量必须是相同的属性组在结果中把重复的属性列去掉

• 一般的连接操作是从行的角度进行运算

  

  自然连接还需要取消重复列，所 以是同时从行和列的角度进行运算

• 悬浮元组（Dangling tuple）

  两个关系R和S在做自然连接时，关系R中某些元组有可能在S中不存在公共属性上值相等的元组，从而造成R中这些元组在操作时被舍弃了，这些被舍弃的元组称为悬浮元组。

• 外连接（Outer Join）

  如果把悬浮元组也保存在结果关系中，而在其他属性上填空值(Null)，就叫做外连接

  • 左外连接(LEFT OUTER JOIN或LEFT JOIN) ：只保留左边关系R中的悬浮元组
  • 右外连接(RIGHT OUTER JOIN或RIGHT JOIN) ：只保留右边关系S中的悬浮元组

除

给定关系R (X，Y) 和S (Y，Z)，其中X，Y，Z为属性组。R中的Y与S中的Y可以有不同的属性名，但必须出自相同的域集。R与S的除运算得到一个新的关系P(X)，P是R中满足下列条件的元组在X属性列上的投影：元组在X上分 量值x的像集Yx包含S在Y上投影的集合。

$R\div{S}=${$t_r[X]|t_r\in{R}\wedge{\prod_Y(S)\subseteq{Y_x}}$}

$Y_x$：x在R中的像集，x = tr[X ]

完整性约束⭐

实体完整性和参照完整性是关系模型必须满足的完整性约束条件，被称作是关系的两个不变性，应该由关系系统自动支持。

实体完整性

若属性A是基本关系R的主属性，则属性A不能取空值或重复

参照完整性

限制一个关系引用与之联系关系中不存在的元组数据

用户定义的完整性

若R表中F外键对应S表中Ks主键，则R表中外键要么取空值要么等于S表中主键值

若属性（或属性组）F是基本关系R的外码 它与基本关系S的主码Ks相对应，则对 于R中每个元组在F上的值必须为：

• 或者取空值（F的每个属性值均为空值）
• 或者等于S中某个元组的主码值。

含外键的R叫参照关系，S叫被参照关系

• 候选码：属性或属性集，唯一标识元组
• 主码：候选码中的一个作为主码
• 主属性：包含在候选码中的属性为主属性
• 外码：一个关系中的属性不是该关系的码，但是是其他关系的码，则是该关系的外码
• 全码：所有属性集是这个关系的候选码

用户定义的完整性包括NOT NULL约束、UNIQUE约束、值域约束等

SQL语言⭐

目标：给定环境和语义，会写SQL查询语言

数据定义

模式

创建模式

create schema <模式名> authorization <用户名> [<表定义子句>|<视图定义子句>|< 授权定义子句>]

定义模式实际上是定义一个命名空间，在这个空间上可以进一步定义该模式包含的数据库对象，如基本表、视图 和索引等。

删除模式

drop schema <模式名> <CASCADE|RESTRICT>

CASCADE (级联)，表示在删除模式的同时把该模式中所有的数据库对象全部删除。

RESTRICT(限制)，表示若模式中已经定义下属的数据库对象 (表、视图)时，则拒绝该删除语句的执行。

表

创建表

1
2
3
4

CREATE TABLE <表名>
	(<列名> <数据类型>[<列级完整性约束条件>],
	 <列名> <数据类型>[<列级完整性约束条件>], 
	 [<表级完整性约束条件>]);

列级完整性约束条件：涉及相应属性列的完整性约束条件

表级完整性约束条件：涉及一个或多个属性列的完整性约束条件

常用完整性约束：

• 主码约束：primary key
• 唯一性约束：unique
• 非空值约束：not null
• 参照完整性约束

修改表

1
2
3
4
5

ALTER TABLE <表名>
	[ADD <新列名> <数据类型> [完整性约束]]
	[DROP [COLUMN] <列名>]
    [DROP CONSTRAINT] <完整性约束>
    [ALTER COLUMN <列名> <数据类型>];

• <表名 >：要修改的基本表
• ADD子句：增加新列和新的完整性约束条件
• DROP子句：删除指定的列
• DROP CONSTRAINT子句：删除完整性约束
• ALTER COLUMN子句：用于修改列名和数据类型

删除表

drop table <表名>

基本表删除：数据、表上的索引都删除

表上的视图往往仍然保留，但无法引用

删除基本表时，系统会从数据字典中删去有关该基本表及其索引的描述

索引

建立索引是加快查询速度的有效手段

建立索引

1
2
3
4
5
6

CREATE [UNIQUE] [CLUSTER] INDEX <索引名>
ON <表名>
(
    <列名>[<次序>],
    [<列名>[<次序>]]
);	

• 用<表名>指定要建索引的基本表名字
• 索引可以建立在该表的一列或多列上，各列名之间用逗号分隔
• 用<次序>指定索引值的排列次序，升序：ASC，降序： DESC。缺省值：ASC
• UNIQUE表明此索引的每一个索引值只对应唯一的数据记录
• CLUSTER表示要建立的索引是聚簇索引

对于已含重复值的属性列不能建UNIQUE索引

对某个列建立UNIQUE索引后，插入新记录时 DBMS会自动检查新记录在该列上是否取了重复 值。这相当于增加了一个UNIQUE约束

删除索引

drop index <索引名>;

删除索引时，系统会从数据字典中删去有关该索引的描述。

数据查询

单表查询⭐

语句格式

1
2
3
4
5

SELECT [ALL|DISTINCT] <目标列表达式>[，<目标列表达式>] …
FROM <表名或视图名>[， <表名或视图名> ] …
[ WHERE <条件表达式> ]
[ GROUP BY <列名1> [ HAVING <条件表达式>]]
[ ORDER BY <列名2> [ ASC|DESC ] ]；

• SELECT子句：指定要显示的属性列
• FROM子句：指定查询对象(基本表或视图)
• WHERE子句：指定查询条件
• GROUP BY子句：对查询结果按指定列的值分组，该属性列值相等的元组为一个组。通常会在每组中作用集函数。
• HAVING短语：筛选出只有满足指定条件的组
• ORDER BY子句：对查询结果表按指定列值的升序或降序排序

WHERE子句常用的查询条件

通配符

• % (百分号) 代表任意长度（长度可以为0）的字符串

例：a%b表示以a开头，以b结尾的任意长度的字符串。如acb，addgb，ab 等都满足该匹配串

• _ (下横线) 代表任意单个字符

例：a_b表示以a开头，以b结尾的长度为3的任意字符串。如acb，afb等都满足该匹配串

ESCAPE 短语

当用户要查询的字符串本身就含有 % 或 _ 时，要使用ESCAPE ‘<换码字符>’ 短语对通配符进行转义。

涉及空值的查询

使用谓词 IS NULL 或 IS NOT NULL

多重条件查询

• 用逻辑运算符AND和 OR来联结多个查询条件
  • AND的优先级高于OR
  • 可以用括号改变优先级
• 可用来实现多种其他谓词
  • [NOT] IN
  • [NOT] BETWEEN … AND …

对查询结果排序

• 使用ORDER BY子句
  • 可以按一个或多个属性列排序
  • 升序：ASC；降序：DESC；缺省值为升序
• 当排序列含空值时
  • ASC：排序列为空值的元组最后显示
  • DESC：排序列为空值的元组最先显示

使用集函数

• 计数

1

COUNT （[DISTINCT|ALL] * ） COUNT （[DISTINCT|ALL] <列名 > ）

• 计算总和

1

SUM （[DISTINCT|ALL] <列名 > ） 

• 计算平均值

1

AVG （[DISTINCT|ALL] <列名 > ）

• 求最大值

1

MAX （[DISTINCT|ALL] <列名 > ） 

• 求最小值

1

MIN （[DISTINCT|ALL] <列名 > ）

DISTINCT短语：在计算时要取消指定列中的重复值

ALL短语：不取消重复值 =

ALL为缺省值

对查询结果分组

使用GROUP BY子句分组

• 未对查询结果分组，集函数将作用于整个查询结果
• 对查询结果分组后，集函数将分别作用于每个组
• GROUP BY子句的作用对象是查询的中间结果表
• 分组方法：按指定的一列或多列值分组，值相等的为一组
• 使用GROUP BY子句后，SELECT子句的列名列表中只能出现分组属性和集函数

使用HAVING短语筛选最终输出结果

• 只有满足HAVING短语指定条件的组才输出
• HAVING短语与WHERE子句的区别：作用对象不同
  • WHERE子句作用于基表或视图，从中选择满足条件的元组。
  • HAVING短语作用于组，从中选择满足条件的组。

连接查询⭐

同时涉及多个表的查询称为连接查询

在where子句中用来连接两个表的条件称为 连接条件 或 连接谓词

[<表名1>.]<列名1> <比较运算符> [<表名2>.]<列名2>

比较运算符：=、>、<、>=、<=、!=

广义笛卡尔积

不带连接谓词的连接

很少使用

等值连接（含自然连接）

• 连接运算符为=的连接操作

  [<表名1>.]<列名1> = [<表名2>.]<列名2>

• 任何子句中引用表1和表2中同名属性时，都必须加 表名前缀。引用唯一属性名时可以加也可以省略表 名前缀。

• 自然连接是等值连接的一种特殊情况，把目标列中 重复的属性列去掉。

非等值连接查询

连接运算符不是=的连接操作

[<表名1>.]<列名1><比较运算符>[<表名2>.]<列名2>

比较运算符： > 、 < 、>= 、<= 、!=

[<表名1>.]<列名1> BETWEEN [<表名2>.]<列名2> AND [<表名2>.]<列名3>

自身连接查询

• 一个表与其自己进行连接

• 需要给表起别名以示区别

• 所有属性必须使用别名前缀

外连接查询

外连接与普通连接的区别

• 普通连接操作只输出满足连接条件的元组
• 外连接操作以指定表为连接主体，将主体表中不满足连接条件的元组一并输出

复合条件连接查询

WHERE子句中含多个连接条件

嵌套查询

嵌套查询概述

• 一个SELECT-FROM-WHERE语句称为一个查询块

• 将一个查询块嵌套在另一个查询块的 WHERE子句或HAVING短语的条件中的查询称为嵌套查询

• 子查询被限制：不能使用ORDER BY子句

不相关子查询

• 子查询的查询条件不依赖于父查询

​ 不相关子查询是由里向外逐层处理。即每个子查询在上一级查询处理之前求解，子查询的结果用于建立其父查询的查找条件。

相关子查询

• 子查询的查询条件依赖于父查询

​ 相关子查询首先取外层查询中表的第一个元组，根据它与内层查询相关的属性值处理内层查询，若WHERE 子句返回值为真，则取此元组放入结果表；

​ 然后再取外层表的下一个元组；

​ 重复这一过程，直至外层表全部检查完为止。

子查询的谓词

• 带有IN谓词的子查询
• 带有比较运算符的子查询
• 带有ANY或ALL谓词的子查询
• 带有EXISTS谓词的子查询

用集函数实现子查询通常比直接用ANY或 ALL查询效率要高，因为前者通常能够减少比较次数

带有EXISTS谓词的子查询

• EXISTS谓词
  • 存在量词
  • 带有EXISTS谓词的子查询不返回任何数据，只产生逻辑真值“true”或逻辑假值“false”。
    • 若内层查询结果非空，则返回真值
    • 若内层查询结果为空，则返回假值
  • 由EXISTS引出的子查询，其目标列表达式通常都用 * 因为带EXISTS的子查询只返回真值或假值，给出列名无实际意义
• NOT EXISTS谓词

不同形式的查询间的替换

​ 一些带EXISTS或NOT EXISTS谓词的子查询不能被其他 形式的子查询等价替换

​ 所有带IN谓词、比较运算符、ANY和ALL谓词的子查询 都能用带EXISTS谓词的子查询等价替换。

集合查询

集合操作种类

• 并操作(UNION)
• 交操作(INTERSECT)
• 差操作(EXCEPT)

SELECT语句的一般格式

1
2
3
4
5
6

SELECT [ALL|DISTINCT] <目标列表达式> [别名] [ ，<目标列表达式> [别名]] …
FROM <表名或视图名> [别名] [ ，<表名或视图名> [别名]] …
[WHERE <条件表达式>]
[GROUP BY <列名1>[，<列名1’>] ...
[HAVING <条件表达式>]]
[ORDER BY <列名2> [ASC|DESC] [，<列名2’> [ASC|DESC] ] … ]；

数据更新⭐

插入数据

两种插入数据方式

• 插入单个元组
• 插入子查询结果

插入单个元组：

1
2
3

INSERT 
INTO <表名> [(<属性列1>[，<属性列2 >…)]
VALUES (<常量1> [，<常量2>] … );

• INTO子句
  • 指定要插入数据的表名及属性列
  • 属性列的顺序可与表定义中的顺序不一致
  • 没有指定属性列：表示要插入的是一条完整的元组， 且属性列属性与表定义中的顺序一致
  • 指定部分属性列：插入的元组在其余属性列上取空 值
• VALUES子句
  • 提供的值必须与INTO子句匹配
    • 值的个数
    • 值的类型

插入子查询结果：

1
2
3

 INSERT 
 INTO <表名> [(<属性列1> [，<属性列2>… )]
 子查询;

INTO子句(与插入单条元组类似)

• 指定要插入数据的表名及属性列
  • 属性列的顺序可与表定义中的顺序不一致
  • 没有指定属性列：表示要插入的是一条完整的元组
  • 指定部分属性列：插入的元组在其余属性列上取空值
• 子查询
  • SELECT子句目标列必须与INTO子句匹配
    • 值的个数
    • 值的类型

修改数据

1
2
3

UPDATE <表名>
SET <列名>=<表达式>[，<列名>=<表达式>]…
[WHERE <条件>]；

功能：修改指定表中满足WHERE子句条件的元组

• 修改某一个元组的值
• 修改多个元组的值
• 带子查询的修改语句

删除数据

1
2
3

DELETE
FROM <表名>
[WHERE <条件>]；

功能： 删除指定表中满足WHERE子句条件的元组

WHERE子句

• 指定要删除的元组
• 缺省表示要修改表中的所有元组

三种删除方式

• 删除某一个元组的值
• 删除多个元组的值
• 带子查询的删除语句

视图⭐

视图的特点

• 虚表，是从一个或几个基本表（或视图） 导出的表
• 只存放视图的定义，不会出现数据冗余
• 基表中的数据发生变化，从视图中查询 出的数据也随之改变

基于视图的操作

• 查询
• 删除
• 受限更新
• 定义基于该视图的新视图

创建视图

1
2
3

 CREATE VIEW <视图名> [(<列名>[,<列名>]…)]
 AS <子查询>
 [WITH CHECK OPTION]；

DBMS执行CREATE VIEW语句时只是把视图的定义存入数据字典，并不执行其中的SELECT语句。

在对视图查询时，按视图的定义从基本表中将数据查出。

组成视图的属性列名全部省略或全部指定

• 全部省略: 由子查询中SELECT目标列中的诸字段组成
• 全部指定:
  • 某个目标列是聚集函数或列表达式
  • 目标列为 *
  • 多表连接时选出了几个同名列作为视图的字段
  • 需要在视图中为某个列启用新的更合适的名字

WITH CHECK OPTION

透过视图进行增删改操作时，不得破坏视图定义中的谓词条件 （即子查询中的条件表达式）

删除视图

1

DROP VIEW <视图名>； 

该语句从数据字典中删除指定的视图定义

由该视图导出的其他视图定义仍在数据字典中，但已不能使用，必须显式删除

删除基表时，由该基表导出的所有视图定义都必须显式删除

查询视图

视图消解法（View Resolution）

• 进行有效性检查，检查查询的表、视图等是否存在。如果存在，则从数据字典中取出视图的定义
• 把视图定义中的子查询与用户的查询结合起来， 转换成等价的对基本表的查询
• 执行修正后的查询

视图消解法的局限

• 有些情况下，视图消解法不能生成正确查询。 采用视图消解法的DBMS会限制这类查询。

更新视图

用户角度：更新视图与更新基本表相同

DBMS实现视图更新的方法：视图消解法（View Resolution）

指定WITH CHECK OPTION子句后

• DBMS在更新视图时会进行检查，防止用户通过视图对不属于视图范围内的基本表数据进行更新

一些视图是不可更新的，因为对这些视图的更 新不能唯一地有意义地转换成对相应基本表的 更新(对两类方法均如此)

视图的作用

• 视图能够简化用户的操作
• 视图使用户能以多种角度看待同一数据
• 视图对重构数据库提供了一定程度的逻辑独立性
• 视图能够对机密数据提供安全保护

数据库安全性

目标：了解数据库安全性的基本概念

数据库的安全性是指保护数据库，防止因用户非法使用数据库造成数据泄露、更改或破坏。

数据库安全性控制的常用方法

• 用户标识和鉴定
• 存取控制
• 视图
• 审计
• 加密

自主存取控制⭐

自主存取控制（Discretionary Access Control ，简称DAC）

同一用户对于不同的数据对象有不同的存取权限

不同的用户对同一对象也有不同的权限

用户还可将其拥有的存取权限转授给其他用户

通过 SQL 的GRANT 语句和REVOKE 语句实现

用户权限组成

• 数据对象
• 操作类型

定义用户存取权限：定义用户可以在哪些数据 库对象上进行哪些类型的操作

定义存取权限称为授权

授权

1
2
3
4

GRANT <权限>[,<权限>]...
[ON <对象类型> <对象名>]
TO <用户>[,<用户>]...
[WITH GRANT OPTION];

GRANT功能：将对 指定操作对象 的 指定操作权限 授予 指定的用户。

指定了WITH GRANT OPTION子句: 获得某种权限的用户还可以把这种权限 再授予别的用户。

没有指定WITH GRANT OPTION子句: 获得某种权限的用户只能使用该权限， 不能传播该权限

对数据库模式的授权由DBA在创建用户时实现：

1
2

CREATE USER <username>
[WITH][DBA|RESOURCE|CONNECT]

语句说明：

• 系统的超级用户才有权创建一个新的数据库用户；
• 新创建的数据库用户有三种权限：CONNECT、 RESOURCE 和DBA；
• CREATE USER 语句中若没有指定创建的新用户的权限， 默认该用户具有CONNECT权限；

回收

1
2
3

REVOKE <权限>[,<权限>]...
[ON <对象类型> <对象名>]
FROM <用户>[,<用户>]...;

功能：从指定用户那里收回对指定对象的指定权限

数据库角色

数据库角色是被命名的一组与数据库操作相关的权限， 角色是权限的集合，通过角色来管理数据库权限可以 简化授权的过程。

角色的创建

1

 CREATE ROLE <角色名>

给角色授权

1
2
3

GRANT <权限>[,<权限>]…
ON<对象类型>对象名
TO <角色>[,<角色>]…

将一个角色授予其他的角色或用户

1
2
3

GRANT <角色1>[,<角色2>]…
TO <角色3>[,<用户1>]…
[WITH ADMIN OPTION

角色权限的收回

1
2
3

REVOKE<权限>[,<权限>]…
ON <对象类型><对象名>
FROM <角色>[,<角色>]…

强制存取控制方法

每一个数据对象被标以一定的密级

每一个用户也被授予某一个级别的许可证

对于任意一个对象，只有具有合法许可证 的用户才可以存取

强制存取控制（Mandatory Access Control， 简称 MAC）是指系统为保证更高程度的安全性，按照TDI/TCSEC标准中安全策略的要求，所采取的强制存取检查手段。

MAC不是用户能直接感知或进行控制的。

MAC适用于对数据有严格而固定密级分类的部门

主体与客体

• 在MAC中，DBMS所管理的全部实体被分为 主体和客体两大类

• 主体是系统中的活动实体

  • DBMS所管理的实际用户
  • 代表用户的各进程

• 客体是系统中的被动实体，是受主体操纵的

  • 文件
  • 基表
  • 索引
  • 视图

• 敏感度标记

  • 对于主体和客体，DBMS为它们每个实例 （值）指派一个敏感度标记（Label）
  • 敏感度标记分成若干级别
    • 绝密（Top Secret）
    • 机密（Secret）
    • 可信（Confidential）
    • 公开（Public）

• 主体的敏感度标记称为许可证级别 （Clearance Level）

• 客体的敏感度标记称为密级（Classification Level）

• MAC机制就是通过对比主体的Label和客体的Label，最终确定主体是否能够存取客体

小结

随着计算机网络的发展，数据的共享日益加强， 数据的安全保密越来越重要

DBMS是管理数据的核心，因而其自身必须具 有一整套完整而有效的安全性机制。

《可信计算机系统评测标准》TCSEC/TDI是目 前各国所引用或制定的一系列安全标准中最重要的一个。

CSEC/TDI从安全策略、责任、保证和文档四个 方面描述了安全性级别的指标

实现数据库系统安全性的技术和方法有多种，最重要的是存取控制技术和审计技术。

审计日志（Audit Log） ：将用户对数据库的所有操作记录在上面

• 目前许多大型DBMS 达到了C2级，其安全版本 达到了B1
• C2级的DBMS必须具有自主存取控制功能和初步的审计功能
• B1级的DBMS必须具有强制存取控制和增强的审计功能
• 自主存取控制功能一般是通过SQL 的GRANT语 句和REVOKE语句来实现的

数据库完整性

目标：三类完整性约束的定义、SQL创建、触发器创建和使用

什么是数据库的完整性：

• 数据的正确性和相容性

• 防止不合语义的数据进入数据库。

实体完整性

关系模型的实体完整性在CREATE TABLE中用PRIMARY KEY 定义。

单属性的码：

• 定义为列级约束条件

• 定义为表级约束条件

多属性的码：

• 定义为表级约束条件

实体完整性检查和违约处理

对定义主码的表，当用户要插入一条记录或对主码 列进行更新操作时，要进行实体完整性规则自动检查。

• 检查主码值是否唯一，若不唯一则拒绝插入或修改；
• 检查主码的各个属性是否为空，只要有一个为空就拒绝插入或修改。

参照完整性

关系模型的参照完整性在CREATE TABLE中用FOREIGN KEY 短语定义哪些列为外码，用REFERENCES短语指明外码参照哪些表的主码。

参照完整性检查和违约处理

用户定义的完整性

在创建表的属性的同时，应根据具体的应用要求，定义属性 上的约束条件，即属性值限制，包括：

• 列值非空（NOT NULL短语）
• 列值唯一 （UNIQUE短语）
• 检查列值是否满足一个布尔表达式（CHECK短语）

在创建表时，用CHECK短语定义元组上的约束条件，即元组级的限制；元组级的限制可以设置不同属性之间的取值的相互约束条件。

参照完整性检查和违约处理

当插入元组或修改属性值时，DBMS就检查属性上的约束条件是否被满足，若不满足操作被拒绝执行。

当往表中插入元组或修改属性值时，若不满足元组上的约束条件就拒绝操作

触发器⭐

触发器（Trigger）是用户定义在关系表上的一 类由事件驱动的特殊过程

• 触发器保存在数据库服务器中
• 任何用户对表的增、删、改操作均由服务器自动激 活相应的触发器
• 触发器可以实施更为复杂的检查和操作，具有更精 细和更强大的数据控制能力

定义触发器

1
2
3
4
5

 CREATE TRIGGER <触发器名> 
 {BEFORE | AFTER} <触发事件> ON <表名>
 REFERENCING NEW|OLD ROW AS<变量>
 FOR EACH {ROW | STATEMENT}
 [WHEN <触发条件>]<触发动作体>

触发器又叫做事件-条件-动作（event-condition-action）规则。

当特定的系统事件发生时，对规则的条件进行检查，如果条件成立则执 行规则中的动作，否则不执行该动作。规则中的动作体可以很复杂，通 常是一段SQL存储过程。

激活触发器

触发器的执行是由触发事件激活的，同一个表上的多个触发器激活时遵循以下次序：

• 执行该表上的BEFORE触发器；
• 激活触发器的SQL语句；
• 执行该表上的AFTER触发器。
• 对于同一表上的多个触发器则遵循“先创造先执行” 原则

删除触发器

1

DROP TRIGGER 〈触发器名〉on 表名〉；

小结

数据库的完整性是为了保证数据库中存储的数 据是正确的，所谓正确的是指符合现实世界语义的

DBMS完整性实现的机制

• 完整性约束定义机制
• 完整性检查机制
• 违背完整性约束条件时DBMS应采取的动作

完整性机制的实施会极大地影响系统性能

关系数据理论⭐

目标：基本概念掌握，会对给定的关系模式进行规范化等计算操作

数据依赖的基本概念

关系模式的简化表示

R(U,F)

U： 组成该关系的属性名集合

F： 属性间数据的依赖关系集合

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

数据依赖：关系内部属性和属性间的一种约束关系

不够规范的关系模式可能存在的问题：

• 数据冗余太大
• 更新异常（Update Anomalies）
• 插入异常（Insertion Anomalies）
• 删除异常（Deletion Anomalies）

规范化

规范化理论用来改造关系模式，通过分解关系模式来消除其中不合适的数据依赖，以解决插入异常、删除异常、 更新异常和数据冗余问题。

函数依赖⭐

函数依赖（Functional Dependency，简记为FD）

设R(U)是一个属性集U上的关系模式，X和Y 是U的子集。

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

Y=f(X)

例如：规定不允许同名人出现，函数依赖“姓名→年龄”成立。所插入的元组必须满足规定的函数依赖，若发现有同名人存在， 则拒绝装入该元组。

平凡与非平凡函数依赖

在关系模式R(U)中，对于U的子集X和Y

如果X→Y，但Y$\nsubseteq$X，则称X→Y是非平凡的函数依赖

若X→Y，但Y $\subseteq$ X, 则称X→Y是平凡的函数依赖

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

非平凡函数依赖： (Sno, Cno) → Grade

平凡函数依赖：(Sno, Cno) → Sno

​ (Sno, Cno) → Cno

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

完全与部分函数依赖

在关系模式R(U)中，如果X→Y，并且对于X的任何一个真子集X’，都有

​ X’$\nrightarrow$Y, 则称Y完全函数依赖于X，记作$X \stackrel{F}{\rightarrow} Y$。

若X→Y，但Y不完全函数依赖于X，则称Y部分函数依赖于X，记作$X \stackrel{P}{\rightarrow} Y$。

例: 在关系SC(Sno, Cno, Grade)中，

由于：Sno →Grade，Cno → Grade， 因此：(Sno, Cno)$\stackrel{F}{\rightarrow}$Grade

Student(Sno, Sname, Ssex, Sage) (Sno, Sname)$\stackrel{P}{\rightarrow}$Sage

传递函数依赖

在关系模式R(U)中，如果X→Y，Y→Z， 且Y$\nsubseteq$X，Y$\nrightarrow$X，则称Z传递函数依赖于X。

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

例: 在关系Std(Sno, Sdept, Mname)中，有：

Sno → Sdept，Sdept → Mname

Mname传递函数依赖于Sno

码

码是可以确定一个元组的所有信息的属性名或属性组

候选码⭐

设K为关系模式R<U,F>中的属性或属性组合。 若$K\stackrel{F}{\rightarrow}U$，则K称为R的一个侯选码（Candidate Key）。若关系模式R有多个候选码，则选定其中的一个做为主码（Primary key）。

• 主属性与非主属性 :包含在码中的属性称为码属性
• ALL KEY： 由R的所有属性构成码，称为全码

候选码的定义：如果关系中的某一属性组的值能唯一地标识一个元组，则称该属性组为候选码；

主码的定义：如果一个关系有多个候选码，则选定其中一个为主码；

主属性定义：候选码的诸属性称为主属性；

非主属性定义：不包含在任何候选码中的属性称为非主属性；

实体完整性规则：如果属性（一个或者一组属性）A是基本关系R的主属性，则A不能取空值。

外部码

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

主码又和外部码一起提供了表示关系间联系的手段。

范式

范式是符合某一种级别的关系模式的集合。

关系数据库中的关系必须满足一定的要求。

满足不同程度要求的为不同范式。

范式的种类：

• 第一范式(1NF)
• 第二范式(2NF)
• 第三范式(3NF)
• BC范式(BCNF)
• 第四范式(4NF)
• 第五范式(5NF)

各种范式之间存在联系：

$1NF\supset2NF\supset3NF\supset{BCNF}\supset4NF\supset5NF$

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

1NF⭐

1NF的定义：如果一个关系模式R的所有属性都是不可分的基本数据项，则R∈1NF

第一范式是对关系模式的最起码的要求。不满足第一范式的数据库模式不能称为关系数据库

但是满足第一范式的关系模式并不一定是一个好的关系模式

2NF⭐

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

采用投影分解法将一个1NF的关系分解为多个2NF的关系，可以在一定程度上减轻原1NF关系中存在的插入异常、删除异常、数据冗余度 大、修改复杂等问题

将一个1NF关系分解为多个2NF的关系，并不能完全消除关系模式中的各种异常情况和数据冗余

3NF⭐

3NF的定义：关系模式R中若不存在这样的码X、属性组Y及非主属性Z（Z$\nsubseteq$ Y）, 使得 X→Y，Y → X，Y→Z成立，则称R ∈ 3NF

若R∈3NF，则R的每一个非主属性既不部分函数依赖于候选码也不传递函数依赖于候选码

如果R∈3NF，则R也是2NF

采用投影分解法将一个2NF的关系分解为多个3NF的关系， 可以在一定程度上解决原2NF关系中存在的插入异常、删除异常、数据冗余度大、修改复杂等问题

将一个2NF关系分解为多个3NF的关系后，并不能完全消除关系模式中的各种异常情况和数据冗余

BCNF⭐

设关系模式R∈1NF，如果对于R的每个函数依赖X→Y，若Y不属于X，则X必含有候选码，那么R∈BCNF

若R∈BCNF，则

• 每一个决定属性集（因素）都包含（候选）码
• R中的所有属性（主，非主属性）都完全函数依赖于码
• R∈3NF
• 若R∈3NF 则 R不一定∈BCNF

3NF与BCNF的关系

• 如果关系模式R∈BCNF， 必定有R∈3NF
• 如果R∈3NF，且R只有一个候选码， 则R必属于BCNF

BCNF的关系模式所具有的性质

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

多值依赖与4NF

多值依赖

多值依赖（Multivalued Dependency，简记为MVD）

设R(U)是一个属性集U上的一个关系模式， X、 Y和Z 是U的子集，并且Z＝U－X－Y，多值依赖 X→→Y成立 当且仅当对R的任一关系r，r在（X，Z）上的每个值对 应一组Y的值，这组值仅仅决定于X值而与Z值无关

例 Teach（C, T, B） C为课程，T为教师，B为参考书

对于C的每一个值，T有一组值与之对应，而不论B取何值

多值依赖的性质

• 多值依赖具有对称性

  若X→→Y，则X→→Z，其中Z＝U－X－Y

• 多值依赖具有传递性

  若X→→Y，Y→→Z， 则X→→Z -Y

• 函数依赖是多值依赖的特殊情况

• 若X→→Y，X→→Z，则X→→Y$\cup$Z

• 若X→→Y，X→→Z，则X→→Y∩Z

• 若X→→Y，X→→Z，则X→→Y-Z， X→→Z-Y

4NF

关系模式R<U,F>∈1NF，如果对于R的每个非平凡多值依赖X→→Y（Y $\nsubseteq$ X）， X都含有候选码，则R∈4NF

规范化小结

• 关系数据库的规范化理论是数据库逻辑设计的工具
• 一个低一级范式的关系模式，通过模式分解可以转换为若干个高一级范式的关系模式集合，这种过程就叫关系模式的规范化

规范化的基本思想

• 消除不合适的数据依赖
• 规范化实质上是概念的单一化
• 不能说规范化程度越高的关系模式就越好
• 上面的规范化步骤可以在其中任何一步终止

数据依赖的公理系统

逻辑蕴含

对于满足一组函数依赖F的关系模式R<U,F> ，其任何一个关系r， 若函数依赖X→Y都成立, 则称F逻辑蕴含X →Y

函数依赖闭包

在关系模式R<U,F>中为F所逻辑蕴含的函数依赖的全体叫作 F的闭包， 记为F$^+$

Armstrong公理系统

从已知的一些函数依赖，可以推导出另外一些函数依赖，这就需要一套推理规则，这些规则常被称作“Armstrong 公理”

三条推理规则

对关系模式R<U,F>来说有以下三条推理规则

• A1.自反律：Y$\subseteq$X$\subseteq$U，则X→Y为F所蕴含
• A2.增广律：若X→Y为F所蕴含， 且Z$\subseteq$U，则XZ→YZ为F所蕴含
• A3.传递律：若X→Y及Y→Z为F所蕴含，则X→Z为F所蕴含

根据以上三条推理规则可以得到以下三条推理规则

• 合并规则：由X→Y，X→Z，有X→YZ (A2， A3）
• 伪传递规则：由X→Y，WY→Z，有XW→Z (A2， A3）
• 分解规则：由X→Y及Z$\subseteq$Y，有X→Z (A1， A3）

根据合并规则和分解规则，可得引理

• 引理6.l X→A$_1$A$_2$…A$_k$成立的充分必要条件是X→A$_i$成立（i=1，2，…，k）

属性集的闭包

设F为属性集U上的一组函数依赖，X$\subseteq$U， X$_F{^+}$ ={ A|X→A能由F 根据Armstrong公理导出}， X$_F{^+}$称为属性集X关于函数依赖集F的闭包

• 引理6.2 设F为属性集U上的一组函数依赖，X，Y$\subseteq$U， X→Y 能由F 根据Armstrong公理导出的充分必要条件是Y$\subseteq$X$_F{^+}$
• 用途：将判定X→Y是否能由F 根据Armstrong公理导出的问题， 就转化为求出X$_F{^+}$ ，判定Y是否 为X$_F{^+}$的子集的问题

属性集闭包计算方法⭐⭐⭐⭐⭐

原文链接：https://blog.csdn.net/Wonz5130/article/details/80464466

例：关系模式R（U，F），其中U={A，B，C，D，E，I}，F={A→D，AB→E，BI→E，CD→I，E→C}，计算（AE)$^+$

解：

第一步：令X={AE}，X$^{(0)}$=AE。

第二步：求X$^{(1)}$。逐一扫描F集合中各个函数依赖，在F中找出左边是AE子集的函数依赖，其结果是：A→D，E→C。这时，F中这两个函数依赖要打上标记(我通常是打上√，表示已经用过，后面不能用了)。于是X$^{(1)}$=AE∪DC=ACDE；

第三步：判断X$^{(1)}$是否等于$^{(0)}$以及$^{(1)}$是否等于 U。

在这里，X$^{(1)}$≠ X$^{(0)}$，且X$^{(1)}$≠ U，所以在F中继续找出左边是ACDE子集的函数依赖，其结果是：CD→I。同样打上标记。于是X$^{(2)}$=ACDE∪I=ACDEI。(这里有一个注意点，∪右边的元素只写左边没有的)

继续判断，虽然X$^{(2)}$≠ X$^{(1)}$，但在F中未用过的函数依赖的左边属性已没有X$^{(2)}$的子集，所以不必再计算下去，即(AE)$^+$=ACDEI。

这里总结一下解题套路：

第一步：X$^{(0)}$=X。

第二步：求X$^{(1)}$。就是在F中找，左边是X$^{(0)}$的元素子集的函数依赖，打上标记√。

第三步：判断X$^{(1)}$是否等于 X$^{(0)}$以及 X$^{(1)}$是否等于 U。

这里有四种情况：

第一种：X$^{(i)}$= X$^{(i-1)}$，说明已经找到闭包。

第二种：X$^{(i)}$≠ X$^{(i-1)}$但是X$^{(i)}$= U，说明已经找到闭包。

第三种：都不相等，但是在F中未用过的函数依赖的左边属性已没有X$^{(i)}$的子集，所以不必再计算下去，已经找到闭包。

第四种：都不相等，在F中未用过的函数依赖的左边属性还有X$^{(i)}$的子集，重复执行。

最小函数依赖集计算⭐⭐⭐⭐⭐

原文链接：https://blog.csdn.net/Wonz5130/article/details/80465245

如果函数依赖集F满足下列条件，则称F为一个极小函数依赖集。亦称为最小依赖集或最小覆盖。

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

例：U=(A,B,C,D,E,G) F={BG→C，BD→E，DG→C，ADG→BC，AG→B，B→D}，求F最小依赖集。

解：

第一步：右边单一化(拆分)

F1={BG→C，BD→E，DG→C，ADG→B，ADG→C，AG→B，B→D}

第二步：对拆分后的各个依赖，在去掉它的F1中求闭包；如果包含右边属性，则表示这个函数依赖要去掉。(去本求包)

BG→C：求(BG)$^+$=BCDEG，包含右边属性C，所以去掉。

BD→E：(BD)$^+$=BD，不包含右边E，所以不用去掉。

DG→C：(DG)$^+$=DG，也不用去掉。

ADG→B：(ADG)$^+$=U，包含B，所以去掉。

ADG→C：(ADG)$^+$包含C，去掉。(在这里，求闭包的时候，不能再用前面去掉的函数依赖了，所以如果从后往前判断，可能不用去掉ADG->B，所以最小依赖集不唯一，写出一个即可。)

AG→B：(AG)$^+$=AG，不用去掉。

B→D：(B)$^+$=B，不用去掉。

所以F2={BD→E,DG→C,AG→B,B→D}

第三步：对左边属性单一化，判断冗余，代替。（左部最小化）

BD→E：B→E，求(B)$^+$=BDE，包含D，所以D冗余。

​ D→E，求(D)$^+$=D，所以B不冗余。

​ 所以用B->E代替BD->E。

DG->C：D→C，(D)$^+$=D，所以G不冗余。

​ G→C，(G)$^+$=G，所以D不冗余。

AG→B：A→B，(A)$^+$=A，所以G不冗余。

​ G→B，(G)$^+$=G，所以A不冗余。

所以F$_m$={B→E,DG→C,AG→B,B→D}

注：最小依赖集不唯一，从前往后判断与从后往前判断，结果可能不同

候选码计算方法⭐⭐⭐⭐⭐

原文链接：https://blog.csdn.net/Wonz5130/article/details/80464679

对于给定的关系R（A1，A2，…, An）和函数依赖集F，可将其属性分为四类：

L类：仅出现在F的函数依赖左部的属性；

R类：仅出现在F的函数依赖右部的属性；

N类：在F的函数依赖左右两边均未出现的属性；

LR类：在F的函数依赖左右两边均出现的属性。

这里还有几个定理，非常有用(我一般用定理1/2/3和推论1)。

定理1：对于给定的关系模式R及其函数依赖集F，若X（X属于R）是L类属性，则X必为R的任一候选关键字的成员。

推论1：对于给定的关系模式R及其函数依赖集F，若X（X属于R）是L类属性，且X$^+$包含了R的全部属性，则X必为R的唯一候选关键字。

定理2：对于给定的关系模式R及其函数依赖集F，若X（X属于R）是R类属性，则X不在任何候选关键字中。

定理3：对于给定的关系模式R及其函数依赖集F，若X（X属于R）是N类属性，则X必为R的任一候选关键字的成员。

推论2：对于给定的关系模式R及其函数依赖集F，若X（X属于R）是N类和L类组成的属性集，且X+包含了R的全部属性，则X必为R的唯一候选关键字。

例：关系模式R（U，F），其中U={A，B，C}，F={AB→C，C→A}，试求此关系的候选键。

解：

第一步：用“LRN法”求出L、R、N、LR各有哪些元素。一般都是先写N、LR，再写L、R。防止冲突。

L：B

R：none

N：none

LR：A，C

第二步：

先求B的闭包(B)+ 。发现就是{B}。所以B不符合，于是要和LR里的元素组合。

再求(AB)$^+$=ABC=U，所以AB是候选键。

再求(BC)$^+$=ABC=U，所有BC也是候选键。

于是：候选键为AB,BC。

这里总结一下解题套路：

第一步：用“LRN法”求出L、R、N、LR各有哪些元素。

第二步：根据三个定理、两个推论，一般都是先求L中元素的闭包。如果是U，则符合推论1，候选码唯一。如果不是U，这时就要并上LR中的元素，继续求闭包，一般都是两两组合。然后如果其中有一组闭包是U，其他一组不是U，那就不用再三个组合了，因为这样会产生冗余，除非三个一组里面不包含前面求到的闭包是U的两个元素。

3NF分解、BCNF分解

数据库设计

目标：数据库设计的整体流程，E-R画法，给定E-R图转成关系模式

数据库设计的基本步骤⭐

1. 需求分析：准确了解与分析用户需求
2. 概念结构设计：通过对用户需求进行综合、归纳与抽象，形成一个独立于具体DBMS的概念模型
3. 逻辑结构设计：将概念结构转换为某个DBMS所支持的数据模型，对其进行优化
4. 物理结构设计：为逻辑数据模型选取一个最适合应用环境的物理结构（包括存储结构和存取方法）
5. 数据库实施：运用DBMS提供的数据语言、工具及宿主语言，根据逻辑设计和物理设计的结果：建立数据库、编制与调试应用程序、组织数据入库、并进行试运行
6. 数据库运行和维护：数据库应用系统经过试运行后即可投入正式运行。在数据库系统运行过程中必须不断地对其进行评价、调整与修改

需求分析

需求分析的方法过程⭐

• 调查组织机构总体情况
• 熟悉业务活动
• 明确用户需求
• 确定系统边界

数据字典⭐

数据字典的内容

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

数据项是数据的最小组成单位

若干个数据项可以组成一个数据结构

数据字典通过对数据项和数据结构的定义来描述数据流、数据存储的逻辑内容

数据项

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

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

• 取值范围、与其他数据项的逻辑关系定义了数据的完整性约束条件

数据结构

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

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

数据结构描述＝｛数据结构名，含义说明，组成:｛数据项或数据结构}｝

数据流

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

数据流描述＝｛数据流名，说明，数据流来源，数据流去向，组成:｛数据结构｝，平均流量，高峰期流量｝

• 平均流量是指在单位时间（每天、每周、每月等） 里的传输次数
• 高峰期流量则是指在高峰时期的数据流量

数据存储

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

数据存储描述＝｛数据存储名，说明，编号，流入的数据流 ，流出的数据流 ，组成:｛数据结构｝，数据量，存取方式｝

• 数据量：每次存取多少数据，每天（或每小时、每周等） 存取几次等信息
• 存取方法：批处理 / 联机处理；检索 / 更新；顺序检索 / 随即检索

处理过程

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

处理过程描述＝｛处理过程名，说明，输入:｛数据流｝，输出:｛数据流｝，处理:｛简要说明}}

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

概念结构设计⭐

要会画E-R图

E-R图画法⭐

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

• 实体型：用矩形表示，矩形框内写明实体名
• 属性：用椭圆形表示，并用无向边将其与相应的实体型连接起来
• 联系：用菱形表示，菱形框内写明联系名，并用无向边分别与有关实体型连接起来，同时在无向边旁标上联系的类型（1∶1，1∶n或m∶n）
  • 联系可以具有属性
  • 联系的度：参与联系的实体型的数目
    • 2个实体型之间的联系度为2，也称为二元联系；
    • 3个实体型之间的联系度为3，称为三元联系；
    • N个实体型之间的联系度为N，也称为N元联系

实体和属性的区别

实体与属性是相对而言的。同一事物，在一种应用环境中作为“属性”，在另一种应用环境中就必须作为“实体” 。

属性不能再具有需要描述的性质。即属性必须是不可分的数据项，不能再由另一些属性组成。

属性不能与其他实体具有联系。联系只发生在实体之间。

E-R图的集成

集成方式

• 一次集成
  • 一次集成多个分E-R图
  • 通常用于局部E-R图比较简单时
• 逐步累积式
  • 首先集成两个局部E-R图（通常是比较关键的两个局部E-R图）
  • 以后每次将一个新的局部E-R图集成进来

冲突⭐

属性冲突

两类属性冲突

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

  例1， 由于学号是数字，因此某些部门（即局 部应用）将学号定义为整数形式，而由于学号 不用参与运算，因此另一些部门（即局部应用） 将学号定义为字符型形式。

  例2， 某些部门（即局部应用）以出生日期形 式表示学生的年龄，而另一些部门（即局部应用）用整数形式表示学生的年龄。

• 属性取值单位冲突

  例：学生的身高，有的以米为单位，有的以厘 米为单位，有的以尺为单位

属性冲突的解决方法：讨论、协商解决

命名冲突

两类命名冲突

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

  例，局部应用A中将教室称为房间 局部应用B中将学生宿舍称为房间

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

  例，有的部门把教科书称为课本 有的部门则把教科书称为教材

属性冲突的解决方法：讨论、协商解决

结构冲突

三类结构冲突

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

  例，“课程”在某一局部应用中被当作实体 在另一局部应用中则被当作属性

  解决方法：通常是把属性变换为实体或把实体变换为属性，使同一对象具有相同的抽象。变换时要遵循两个准则

• 同一实体在不同局部视图中所包含的属性不完全相同，或者属性的排列次序不完全相同。

  解决方法：使该实体的属性取各分E-R图中属性的并集，再适当设计属性的次序

• 实体之间的联系在不同局部视图中呈现不同的类型

  例1， 实体E1与E2在局部应用A中是多对多联系， 而在局部应用B中是一对多联系

  例2， 在局部应用X中E1与E2发生联系，而在局部应用Y中E1、E2、E3三者之间有联系。

  解决方法：根据应用语义对实体联系的类型进行综合或调整。

小结

什么是概念结构设计

概念结构设计的步骤

• 抽象数据并设计局部视图
• 集成局部视图，得到全局概念结构
• 验证整体概念结构

设计局部视图

• 选择局部应用
• 逐一设计分E-R图
  • 标定局部应用中的实体、属性、码，实体间的联系
  • 用E-R图描述出来

集成局部视图

• 合并分E-R图，生成初步E-R图

  • 消除冲突
    • 属性冲突
    • 命名冲突
    • 结构冲突

• 修改与重构

  • 消除不必要的冗余，设计生成基本E-R图
    • 分析方法
    • 规范化理论

逻辑结构设计⭐

要会把E-R图转换为关系模式

转换规则⭐⭐⭐⭐⭐

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

• 关系的属性：实体型的属性
• 关系的码：实体型的码

例，学生实体可以转换为如下关系模式： 学生（学号，姓名，出生日期，所在系， 年级，平均成绩）

2.一个m:n联系转换为一个关系模式。

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

例，“选修”联系是一个m:n联系，可以将它转换为如下关系模式，其中学号与课程号为关系的组合码： 选修（学号，课程号，成绩）

3.一个1:n联系可以转换为一个独立的关系模式，也可以与n端对应的关系模式合并。

• 转换为一个独立的关系模式
  • 关系的属性：与该联系相连的各实体的码以及联系本身的属性
  • 关系的码：n端实体的码
• 与n端对应的关系模式合并
  • 合并后关系的属性：在n端关系中加入1端关系的码和联系本身的属性
  • 合并后关系的码：不变

例，“班级组成”联系为1:n联系。 将其转换为关系模式的两种方法： 1)使其成为一个独立的关系模式： 组成（学号，班级号） 2)将其学生关系模式合并： 学生（学号，姓名，出生日期，所在系， 年级，$\color{red}{班级号}$，平均成绩）

4.一个1:1联系可以转换为一个独立的关系模式， 也可以与任意一端对应的关系模式合并

• 转换为一个独立的关系模式
  • 关系的属性：与该联系相连的各实体的码以及联系本身的属性
  • 关系的候选码：每个实体的码均是该关系的候选码
• 与某一端对应的关系模式合并
  • 合并后关系的属性：加入对应关系的码和联系本身的属性
  • 合并后关系的码：不变

5.三个或三个以上实体间的一个$\color{red}{多元联系}$转换为一个关系模式

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

例，“讲授”联系是一个三元联系，可以将它 转换为如下关系模式，其中课程号、职工号和 书号为关系的组合码： 讲授（课程号，职工号，书号）

6.同一实体集的实体间的联系，即$\color{red}{自联系}$，也可按上述1:1、1:n和m:n三种情况分别处理。

例，如果教师实体集内部存在领导与被领导的 1:n自联系，我们可以将该联系与教师实体合 并，这时主码职工号将多次出现，但作用不同， 可用不同的属性名加以区分： 教师：｛职工号，姓名，性别，职称，$\color{red}{系主任号}$｝

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

数据模型的优化

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

优化数据模型的方法

• 确定数据依赖
• 对于各个关系模式之间的数据依赖进行极小化处理，消除冗余的联系
• 按照数据依赖的理论对关系模式逐一进行分析，考查是否存在部分函数依赖、传递函数依赖、多值依赖等，确定各关系模式分别属于第几范式
• 按照需求分析阶段得到的各种应用对数据处理的要求，分析对于这样的应用环境这些模式是否合适，确定是否要对它们进行合并或分解。
• 按照需求分析阶段得到的各种应用对数据处理的要求，对关系模式进行必要的分解或合并，以提高数据操作的效率和存储空间的利用率

小结

任务

• 将概念结构转化为具体的数据模型

逻辑结构设计的步骤

• 将概念结构转化为一般的关系、网状、层次模型
• 将转化来的关系、网状、层次模型向特定DBMS支 持下的数据模型转换
• 对数据模型进行优化
• 设计用户子模式

数据库的物理设计

数据库在物理设备上的存储结构与存取方法称为数据库的物理结构，它依赖于给定的计算机系统。

为一个给定的逻辑数据模型选取一个最适合应用环境的物理结构的过程，就是数据库的物理设计。

存取方法

DBMS常用存取方法

• 索引方法，目前主要是B+树索引方法，其他还有hash、Rtree、Bitmap等

• 聚簇（Cluster）方法

什么是聚簇

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

例： CREATE CLUSTER INDEX Stusname ON Student(Sname)；

在Student表的Sname（姓名）列上建立一个聚簇索引，而且Student表中的记录将按照Sname值的升序存放

• 在一个基本表上最多只能建立一个聚簇索引
• 聚簇索引的用途：对于某些类型的查询，可以提高查询效率
• 聚簇索引的适用范围
  • 很少对基表进行增删操作
  • 很少对其中的变长列进行修改操作

Hash

当一个关系满足下列两个条件时，可以选择HASH存取方法

• 该关系的属性主要出现在等值连接条件中或主要出现在相等比较选择条件中
• 该关系的大小可预知，而且不变； 或该关系的大小动态改变，但所选用的DBMS提供了动态HASH存取方法。

数据库维护

在数据库运行阶段，对数据库经常性的维护工作主要是由DBA（Database Administrator）完成的，包括：

• 数据库的转储和恢复
• 数据库的安全性、完整性控制
• 数据库性能的监督、分析和改进
• 数据库的重组织和重构造

数据库编程

目标：基本概念的理解

嵌入式SQL⭐

将SQL嵌入到高级语言，通过预编译将sql语言转换为高级语言或者一些库函数进行调用

嵌入式SQL的处理过程⭐

为了区分SQL语句与主语言语句，需要前缀：EXEC SQL

嵌入式SQL语句与主（高级）语言之间的通信⭐

• 主变量（宿主变量，host variable）：就是在嵌入式SQL语句中引用主语言说明的程序变量
• SQL通信区 （SQLCA）：向主语言传递SQL语句的执行状态信息；主语言能够据此控制程序流程
• 建立和关闭数据库：合法用户连接，按需分配，用完释放资源
• 游标：数据缓冲区，将查询的结果存放在缓冲区中
  • 解决集合性操作语言与过程性操作语言的不匹配
  • 将SQL语句查询数据库的结果交主语言进一步处理

ODBC

ODBC（Open Database Connectivity） 建立了一组规范，并提供一组访问数据库的标准API

• 规范应用开发
• 规范DBMS应用接口

PL/SQL

PL/SQL是编写数据库存储过程的一种过程语言，叫做过程化SQL语言（Procedural Language/SQL）。

它结合SQL的数据操作能力和过程化语言的流程控制（判断、循坏）能力，是SQL的过程化扩展。

PL/SQL程序的基本结构是块，所有的PL/SQL程序都是由块组成的，这些块之间可以相互嵌套，每个块完成一个逻辑操作。

存储过程

由PL/SQL书写的过程，经过编译后存储在数据库服务器中，使用时直接调用即可。

优点

• 由于存储过程不像解释执行的SQL语句那样在提出操作请 求时才进行语法分析和优化工作，因而运行效率高。
• 存储过程降低了客户机和服务器之间的通信量。
• 方便实施企业规则。

关系查询的处理和优化

目标：理解查询处理的步骤阶段，会用关系代数写出查询表达式，并对其进行优化

查询处理

查询处理的步骤⭐

查询操作

常见的查询操作：选择，投影，连接

选择操作⭐

• 简单的全表扫描方法：对查询的基本表顺序扫描，逐一检查每个元组是否满足条件，把满足条件的元组作为结果输出，小表有效，大表顺序扫描效率低。
• 索引扫描方法：若选择条件中的属性上有索引（B+索引或Hash索引） ，可以用索引扫描方法。 通过索引先找到满足条件的元组主码或元组指针，再通过元组指针直接在查询的基本表中找到元组。

连接操作⭐

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

• 嵌套循环方法（nested loop）：对外层循环（Student）的每一个元组（s）,检索内层循环（SC）中的每一个元组（sc），并检查这两个元组在连接属性 （sno）上是否相等。满足条件则串接后输出，否则直到外层循环表中的元组处理完为止。
• 排序-合并连接法（sort-merge join）：
  • 若连接的表没有排好序，首先对Student表和SC表按连接属性Sno排序；
  • 取Student表中第一个Sno，依次扫描SC表中具有相同Sno的元组；把它 们连接起来；
  • 当扫描到Sno不相同的第一个SC元组时，返回Student表扫描它的下一个 元组，再扫描SC表中具有相同Sno的元组，把它们连接起来；
  • 重复上述步骤直到Student表扫描完。
• 索引连接（index join）方法：
  • 在SC表上建立属性Sno的索引，如果原来没有的话；
  • 对Student中每一个元组，由Sno值通过SC的索引查找相应的SC元组；
  • 把这些SC元组和Student元组连接起来。
  • 循环执行2)3),直到Student表中的元组处理完为止。

查询优化

代数优化⭐

关系代数等价变换规则

关系代数表达式等价：指用相同的关系代替两个表达式中相应的关系所得到的结果是相同的。上面的优化策略大部分都涉及到代数表达式的变换。

常用的等价变换规则

设E1、E2等是关系代数表达式，F是条件表达式

1. 连接、笛卡尔积交换律

   $E1\times{E2}\equiv{E2\times{E1}}$

   $E1\mathop{\bowtie}E2\equiv{E2\mathop{\bowtie}E1}$

   $E1\mathop{\bowtie}\limits_{F}E2\equiv{E2\mathop{\bowtie}\limits_{F}E1}$

2. 连接、笛卡尔积的结合律

   $(E1\times{E2})\times{E3}\equiv{E1\times({E2}\times{E3})}$

   $(E1\mathop{\bowtie}E2)\mathop{\bowtie}E3\equiv{E1\mathop{\bowtie}(E2\mathop{\bowtie}E3)}$

   $(E1\mathop{\bowtie}\limits_{F}E2)\mathop{\bowtie}\limits_{F}E3\equiv{E1\mathop{\bowtie}\limits_{F}(E2\mathop{\bowtie}\limits_{F}E3)}$

3. 投影的串接定律

   

4. 选择的串接定律

   $\sigma_{F1}(\sigma_{F2}(E))\equiv\sigma_{F1\wedge{F2}}(E)$

   选择的串接律说明选择条件可以合并，这样一次就可检查全部条件。

5. 选择与投影的交换律

   • 假设: 选择条件F只涉及属性A1,…,An

     

   • 假设: F中有不属于A1, …,An的属性B1,…,Bm

     

6. 选择与笛卡尔积的交换律

   • 假设：F中涉及的属性都是E1中的属性

     

   • 假设：F=F1∧F2，并且F1只涉及E1中的属性， F2只涉及E2中的属性，则由上面的等价变换规则1，4，6可推出：

     

   • 假设： F=F1∧F2， F1只涉及E1中的属性， F2涉及E1和E2两者的属性，它使部分选择在笛卡尔积前先做

     

7. 选择与并的分配律

   假设：E=E1∪E2，E1，E2有相同的属性名

   

8. 选择与差运算的分配律

   假设：E1与E2有相同的属性名

   

9. 选择对自然连接的分配律

   F 只涉及E1 与E2的公共属性

   

10. 投影与笛卡尔积的分配律

    假设：E1和E2是两个关系表达式， A1，…，An是E1的属性， B1，…，Bm是E2的属性

    

小结

1-2: 连接、笛卡尔积的交换律、结合律

3： 合并或分解投影运算

4： 合并或分解选择运算

5-8： 选择运算与其他运算交换

5，9，10： 投影运算与其他运算交换

查询树的启发式优化⭐

1.选择运算应尽可能先做。 ⭐

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

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

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

5.找出公共子表达式

结合变换准则所得表达式的优化算法⭐

（1）分解选择运算：利用规则4分解选择运算

（2）通过交换选择运算，将其尽可能移到叶端：对每一个选择，利用规则4～8尽可能把它移到树的叶端。

（3）通过交换投影运算，将其尽可能移到叶端：对每一个投影利用规则3，5，9，l0中的一般形式尽可能把它移向树的叶端。

（4）合并串接的选择和投影，以便能同时执行或在一次扫描中完成：利用规则3～5把选择和投影的串接合并成单个选择、单个投影或一个选择后跟一个投影。使多个选择或投影能同时执行，或在一次扫描中全部完成。

（5）对内结点分组：把上述得到的语法树的内节点分组。每一双目运算(×，$\mathop{\bowtie}$ ，∪，-)和它所有的直 接祖先为一组(这些直接祖先是б，π运算)。如果其后代直到叶子全是单目运算，则也将 它们并入该组，但当双目运算是笛卡尔积 (×)，而且其后的选择不能与它结合为等值 连接时除外。把这些单目运算单独分为一组。

（6）生成程序：生成一个程序，每组结点的计算是程序中的 一步。各步的顺序是任意的，只要保证任何一组的计算不会在它的后代组之前计算。

优化查询树的题

物理优化

存取路径和底层操作算法的选择

恢复技术

目标：基本概念的理解掌握

事务⭐

基本定义

什么是事务

• 事务(Transaction)是用户定义的一个数据库操作序列，这些操作要么全做，要么全不做，是一个不可分割的工作单位。
• 事务和程序是两个概念：在关系数据库中，一个事务可以是一条SQL语句， 一组SQL语句或整个程序。一个应用程序通常包含多个事务。
• 事务是恢复和并发控制的基本单位

如何定义事务

1
2
3
4
5

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

• COMMIT
  • 事务正常结束
  • 提交事务的所有操作（读+更新）
  • 事务中所有对数据库的更新永久生效
• ROLLBACK
  • 事务异常终止
  • 事务运行的过程中发生了故障，不能继续执行，回滚事务的所有更新操作
  • 事务滚回到开始时的状态

事务的特性（ACID特性）⭐

• 原子性（Atomicity）/ˌadəˈmisədē/：

  事务是数据库的逻辑工作单位

  事务中包括的诸操作要么都做，要么都不做

• 一致性（Consistency）

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

  一致性状态： 数据库中只包含成功事务提交的结果 不一致状态： 数据库中包含失败事务的结果

• 隔离性（Isolation）/ˌīsəˈlāSH(ə)n/

  对并发执行而言 一个事务的执行不能被其他事务干扰

  一个事务内部的操作及使用的数据对其他并发事务是隔离的

  并发执行的各个事务之间不能互相干扰

• 持续性（Durability ）/ˌd(y)o͝orəˈbilədē/

  持续性也称永久性（Permanence）

  一个事务一旦提交，它对数据库中数据的改变就应该是永久性的。

  接下来的其他操作或故障不应该对其执行结果有任何影响。

故障种类⭐

事务故障

什么是事务故障

• 某个事务在运行至正常终止点前被中止

事务故障的常见原因

• 输入数据有误 、运算溢出、违反了某些完整性限制、某些应用程序出错、并行事务发生死锁

事务故障的恢复

• 发生事务故障时，夭折的事务可能已把对数据库的部分修改写回磁盘

• 事务故障的恢复：撤消事务（UNDO）

• 强行回滚（ROLLBACK）该事务

• 清除该事务对数据库的所有修改，使得这个事务像根本没有启动过一样

系统故障

什么是系统故障

• 整个系统的正常运行突然被破坏
• 所有正在运行的事务都非正常终止
• 内存中数据库缓冲区的信息全部丢失
• 外部存储设备上的数据未受影响

系统故障的常见原因

• 操作系统或DBMS代码错误、操作员操作失误、特定类型的硬件错误（如CPU故障）、突然停电

系统故障的恢复

• 清除尚未完成的事务对数据库的所有修改
  • 系统重新启动时，恢复程序要强行撤消 （UNDO）所有未完成事务
• 将缓冲区中已完成事务提交的结果写入数据库
  • 系统重新启动时，恢复程序需要重做 （REDO）所有已提交的事务

介质故障

什么是介质故障

• 硬件故障使存储在外存中的数据部分丢失或全部丢失
• 介质故障比前两类故障的可能性小得多， 但破坏性大得多

介质故障的常见原因

• 硬件故障（磁盘损坏、磁头碰撞、操作系统的某种潜在错误、瞬时强磁场干扰）

恢复技术

恢复机制涉及的关键问题：

• 如何建立冗余数据

  • 数据转储（backup）

  • 登记日志文件（logging）

• 如何利用这些冗余数据实施数据库恢复

数据转储

什么是数据转储

• 数据转储是指DBA将整个数据库复制到磁带或另一个磁盘上保存起来的过程。
• 这些备用的数据文本称为后备副本或后援副本

数据转储方法

• 静态转储：在系统中无运行事务时进行转储

• 动态转储：转储操作与用户事务并发进行

  需要把动态转储期间各事务对数据库的修改活动登记下来，建立日志文件

  后备副本加上日志文件才能把数据库恢复到某一时刻的正确状态

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

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

日志文件⭐

什么是日志文件

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

日志文件的格式

• 以记录为单位的日志文件
• 以数据块为单位的日志文件

日志文件的用途

• 进行事务、系统故障恢复
• 动态转储必须使用日志
• 转储后备副本配合进行介质故障恢复

登记日志文件的原则

• 登记的次序严格按并发事务执行的时间次序
• 必须先写日志文件，后写数据库

恢复方法

事务故障的恢复

• 事务故障：事务在运行至正常终止点前被中止(日志中有begin 没有commit)
• 由恢复子系统应利用日志文件撤消（UNDO）此事务已对数据库进行的修改
• 事务故障的恢复由系统自动完成，不需要用户干预

事务故障的恢复步骤

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

系统故障的恢复

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

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

恢复方法

• Undo 故障发生时未完成的事务
• Redo 已完成的事务

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

系统故障的恢复步骤

• 正向扫描日志文件（即从头扫描日志文件）
  • Redo队列: 在故障发生前已经提交的事务
  • Undo队列:故障发生时尚未完成的事务
• 对Undo队列事务进行UNDO处理
  • 反向扫描日志文件，对每个UNDO事务的更新操作执行逆操作
• 对Redo队列事务进行REDO处理
  • 正向扫描日志文件，对每个REDO事务重新执行登记的操作

介质故障的恢复

介质故障的恢复需要DBA介入

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

具体的恢复操作仍由DBMS完成

恢复方法

• 重装数据库，使数据库恢复到一致性状态
• 重做已完成的事务

介质故障的恢复步骤

• 装入最新的后备数据库副本，使数据库恢复到最近一次转储时的一致性状态。
  • 利用静态、动态转储恢复到转储的状态
• 装入有关的日志文件副本，重做已完成的事务
  • 从转储时刻开始，扫描日志，故障发生时已提交的事务，REDO事务

具有检查点的恢复技术

两个问题

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

解决方案

• 在日志文件中增加检查点记录 （checkpoint）

  检查点记录的内容

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

• 增加重新开始文件

  重新开始文件的内容

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

• 恢复子系统在登录日志文件期间动态地维护日志

利用检查点的恢复方法

当事务T在一个检查点之前提交，T对数据库所做的修改已写入数据库。

在进行恢复处理时，没有必要对事务T执行REDO操作

利用检查点的恢复步骤

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

小结⭐

• 如果数据库只包含成功事务提交的结果，就说数据库处于一致性状态。保证数据一致性是对数据库的最基本的要求。
• 事务是数据库的逻辑工作单位
  • DBMS保证系统中一切事务的原子性、一致性、隔离性和持续性
• DBMS必须对事务故障、系统故障和介质故障进行恢复
• 恢复中最经常使用的技术：数据库转储和登记日志文件
• 恢复的基本原理：利用存储在后备副本、日志文件和数据库镜像中的冗余数据来重建数据库
• 常用恢复技术
  • 事务故障的恢复
    • UNDO
  • 系统故障的恢复
    • UNDO + REDO
  • 介质故障的恢复
    • 重装备份并恢复到一致性状态 + REDO
• 提高恢复效率的技术
  • 检查点技术
    • 可以提高系统故障的恢复效率
    • 可以在一定程度上提高利用动态转储备份 进行介质故障恢复的效率
  • 镜像技术
    • 镜像技术可以改善介质故障的恢复效率

并发控制

目标：掌握基本概念和定义，理解并发控制的目的

并发控制概述⭐

多事务执行的三种方式

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

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

• 丢失修改（lost update）

  丢失修改是指事务1与事务2从数据库中读入同一数据并修改，事务2的提交结果破坏了事务1提交的结果， 导致事务1的修改被丢失。(W-W)

• 不可重复读（non-repeatable read）

  不可重复读是指事务1读取数据后，事务2执行更新操作，使事务1无法再现前一次读取结果。(R-W)

• 读“脏”数据（dirty read）

  事务1修改某一数据，并将其写回磁盘，事务2读取同一数据后，事务1由于某种原因被撤消，这时事务1已修改过的数据恢复原值，事务2读到的数据就与数据库中的数据不一致，是不正确的数据，又称为“脏”数据。（W-R）

封锁

什么是封锁

• 封锁就是事务T在对某个数据对象（例如表、记录等）操作之前，先向系统发出请求，对其加锁。加锁后，事务T就对该数据对象有了一定的控制， 在事务T释放它的锁之前，其它的事务不能更新此数据对象。
• 封锁是实现并发控制的一个非常重要的技术

两种封锁类型

• 排它锁（eXclusive lock，简记为X锁）

  排它锁又称为写锁

  若事务T对数据对象A加上X锁，则只允许T读取和修改A，其它任何事务都不能再对A加任何类型的锁，直到T释放A上的锁

• 共享锁（Share lock，简记为S锁）

  共享锁又称为读锁

  若事务T对数据对象A加上S锁，事务T可以读A但不能修改A，其它事务也只能再对A加S锁，而不能加X锁，直到T释放A上的S锁

锁的相容矩阵

Y=Yes，相容的请求

N=No，不相容的请求

什么是封锁协议

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

三级封锁协议

• 一级封锁协议

  事务T在修改数据W之前必须先对其加X锁，直到事务结束才释放。（读不加锁）

  一级封锁协议可防止丢失修改

• 二级封锁协议

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

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

• 三级封锁协议

  一级封锁协议基础上，事务T在读取数据R之前必须先对其加S锁，直到事务结束才释放

  三级封锁协议可防止丢失修改、读脏数据和不可重复读

活锁和死锁⭐

什么是活锁

• 事务T1封锁了数据R，事务T2又请求封锁R，于是T2等待。T3也请求封锁R，当T1释放了R上的封锁后，系统首先批准了T3的请求，T2仍然等待。然后T4又请求封锁R，当T3释放了R上的封锁之后，系统又批准了T4的请求……T2可能永远等待。因为事务T2在不断的重复尝试获取锁R，所以这个就是活锁。

• 活锁有可能自行解开

如何避免活锁

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

什么是死锁

• 事务T1获取了数据R1的排它锁，事务T2获取了数据R2的排它锁。事务T1需要获取数据R2的排它锁来完成事务，但数据R2的排它锁需要事务T2执行完才能释放，而事务T2需要获取数据R1的排它锁来完成事务，但数据R1的排它锁需要事务T1执行完才能释放。此时形成死锁。
• 在两个或多个任务中，如果每个任务锁定了其他任务试图锁定的资源，此时会造成这些任务永久阻塞，从而出现死锁。
• 除非某个外部进程断开死锁，否则死锁中的两个事务都将无限期等待下去。

解决死锁的方法

• 预防死锁

  • 一次封锁法

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

    一次封锁法存在的问题：降低并发度

  • 顺序封锁法

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

    顺序封锁法存在的问题：维护成本高

在操作系统中广为采用的预防死锁的策略并不很适合数据库

DBMS在解决死锁的问题上更普遍采用的是诊断并解除死锁的方法

• 死锁的诊断与解除

  • 超时法

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

  • 等待图法

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

    事务等待图是一个有向图G=(T，U)，T为结点的集合，每个结点表示正运行的事务，U为边的集合，每条边表示事务等待的情况。若T1等待T2，则T1，T2之间划一条有向边，从T1指向T2

    并发控制子系统周期性地（比如每隔1 min）检测事务等待图。如果发现图中存在回路，则表示系统中出现了死锁

  • 解除死锁

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

并发调度的可串行性

可串行性的定义

• 几个事务的并行执行是正确的，当且仅当其结果与按某一次序串行地执行它们时的结果相同。 这种并行调度策略称为可串行化（Serializable） 的调度
• 可串行性是并行事务正确性的唯一准则

什么是冲突操作

• 冲突操作是指读写操作和写写操作

什么是冲突可串行化调度

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

• 一个调度是冲突可串行化的，则一定是可串行化的调度。 （充分条件）

  例：调度Sc1=r1(A)w1(A)r2(A) w2(A)r1(B)w1(B) r2(B)w2(B)

  通过2次交换:

  ​ w2(A)与r1(B)w1(B)交换： r1(A)w1(A)r2(A) r1(B)w1(B) w2(A) r2(B)w2(B)

  ​ r2(A)与r1(B)w1(B)交换: r1(A)w1(A) r1(B)w1(B) r2(A) w2(A) r2(B)w2(B)

  得到Sc2=r1(A)w1(A) r1(B)w1(B) r2(A) w2(A) r2(B)w2(B)

  Sc2等价于一个串行调度T1，T2；所以Sc1是冲突可串行化调度。

两段锁协议

两段锁协议的内容

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

所有遵守两段锁协议的事务，其并行执行的结果一定是正确的

事务遵守两段锁协议是可串行化调度的充分条件，而不是必要条件。可串行化的调度中，不一定所有事务都必须符合两段锁协议。

两段锁协议并不要求事务必须一次将所有要使用的数据全部加锁，因此遵守两段锁协议的事务可能发生死锁

多粒度封锁⭐

什么是封锁粒度

• X锁和S锁都是加在某一个数据对象上的

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

  例：在关系数据库中，封锁对象：

  逻辑单元: 属性值、属性值集合、元组、关系、索引项、整个索引、整个数据库等

  物理单元：页（数据页或索引页）、物理记录等

• 封锁对象可以很大也可以很小

  例： 对整个数据库加锁 对某个属性值加锁

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

什么是多粒度封锁

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

什么是多粒度树

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

显示封锁和隐式封锁

• 在多粒度封锁中一个数据对象可能以两种方式封锁：显式封锁和隐式封锁

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

• 隐式封锁: 由于其上级结点加锁而使该数据对象加上了锁

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

什么是意向锁

• 对任一结点加基本锁，必须先对它的上层所有结点加意向锁
• 如果对一个结点加意向锁，则说明该结点的下层结点正在被加锁
• 意向锁可以提高对某个数据对象加锁时系统的检查效率

例：对任一元组 r 加锁，先对关系R加意向锁

事务T要对关系R加X锁, 系统只要检查根结点数据库和关系R是否已加了不相容的锁，不需要搜索和检查R中的每一个元组是否加了X锁

三种意向锁⭐

• 意向共享锁(Intent Share Lock，简称IS锁)

  例：要对某个元组加S锁，则要首先对关系和数据库加IS锁

• 意向排它锁(Intent Exclusive Lock，简称IX锁)

  例：要对某个元组加X锁，则要首先对关系和数据库加IX锁。

• 共享意向排它锁(Share Intent Exclusive Lock，简称SIX锁)

  例：对某个表加SIX锁，则表示该事务要读整个表（所以要对该表加S锁），同时会更新个别元组（所以要对该表加IX锁）

意向锁的相容矩阵

小结

• 数据共享与数据一致性是一对矛盾
• 数据库的价值在很大程度上取决于它所能提供的数据共享度
• 数据共享在很大程度上取决于系统允许对数据并发操作的程度
• 数据并发程度又取决于数据库中的并发控制机制
• 另一方面，数据的一致性也取决于并发控制的程度。 施加的并发控制愈多，数据的一致性往往愈好
• 数据库的并发控制以事务为单位
• 数据库的并发控制通常使用封锁机制
  • 两类最常用的封锁
• 不同级别的封锁协议提供不同的数据一致性保证，提供不同的数据共享度
  • 三级封锁协议
• 并发控制机制调度并发事务操作是否正确的判别准则是可串行性
  • 并发操作的正确性则通常由两段锁协议来保证。
  • 两段锁协议是可串行化调度的充分条件，但不是必要条件
• 对数据对象施加封锁，带来问题
• 活锁： 先来先服务
• 死锁：
  • 预防方法
    • 一次封锁法
    • 顺序封锁法
  • 死锁的诊断与解除
    • 超时法
    • 等待图法
• 不同的数据库管理系统提供的封锁类型、封锁协议、达到的系统一致性级别不尽相同。但是其依据的基本原理和技术是共同的