数据库系统概论备忘

学习数据库时提炼的备忘，比较详细

数据库系统概论

绪论

数据库系统概述

基本概念

• 数据：描述事物的符号记录
• 数据库：长期存储在计算机内、有组织的、可共享的大量数据的集合
• 数据库管理系统：位于用户与操作系统之间的一层数据管理软件
• 数据库系统：由数据库、数据库管理系统、应用程序和数据库管理员组成的存储、管理、处理和维护数据的系统

数据管理系统的发展

人工管理阶段→文件系统阶段→数据库系统阶段

数据库系统的特点

• 数据结构化
• 数据的共享性质、冗余度低且易扩充
• 数据独立性高
• 数据由数据管理系统统一控制管理
  • 数据的安全性保护
  • 数据的完整性保护
  • 并发控制
  • 数据库恢复

数据模型

• 数据模型是对现实世界数据特征的抽象
• 数据模型是数据库系统的核心和基础

两类数据模型

• 概念模型：按用户的观点来对数据和信息建模
• 逻辑模型和物理模型
  • 逻辑模型：按计算机系统的观点对数据建模
  • 物理模型：对数据最底层的抽象

※：数据建模与抽象

• 数据建模是抽象，抽象是理解——区分——命名——表达

概念模型

• 实体：客观存在并可相互区别的事物称为实体 e.g：一个学生

• 属性：实体具有的某一特性 e.g：学生的性别

• 码/键：唯一标识实体的属性集 e.g：学号

• 实体型：用实体名及其属性名集合来抽象和刻画同类实体 e.g：学生（姓名，性别）

• 实体集：同一类型实体的集合 e.g：全体学生

• 联系：

  • 实体内部的联系：组成实体的各属性之间的联系
  • 实体之间的联系：不同实体集之间的联系
    • 一对一：1:1（也可以没有）
    • 一对多：1:m（也可以没有）
    • 多对多：m:n（也可以没有）

• 实体——联系方法（E-R）：用E-R图描述现实世界的概念模型

数据模型的组成要素

• 数据结构
• 数据操作
  • 查询
  • 更新：插入、删除、修改
• 数据的完整性约束条件：用以限定符合数据模型的数据库状态以及状态的变化，以保证数据的正确、有效和相容

常用的数据模型

• 格式化模型

  • 层次模型

  • 网状模型

• 关系模型✅

• 面向对象模型

• 对象关系数据模型

• 半结构化数据模型

• 图数据模型

层次模型

• 最早出现的数据模型，用树形结构来表示实体和实体间的联系
• 构成
  • 有且只有一个根节点没有双亲结点
  • 根以外其他他结点有且只有一个双亲结点
• 优点：结构简单、查询效率高
• 缺点：现实世界中很多联系是非层次性的、对具有多个双亲解点的结点难表示、查询子女结点必须通过双亲结点等

网状模型

• 构成

  • 允许一个以上结点无双亲

  • 一个结点可以由多余一个的双亲

关系模型

• 最重要的数据模型

• 逻辑结构是一张二维表

• 概念

  • 关系：一个关系对应一张表

  • 元组：表中的一行

  • 属性：表中的一列；列头是属性名

  • 码：可以唯一确定一个元组的属性组

  • 域：一组具有相同数据类型的值的集合

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

  • 关系模式：对关系的描述，一般表示为：关系名（属性1，属性2，…，属性n）

    e.g：学生（学号，姓名，性别）

• 关系是规范化的：不允许表中还有表

• 优点：建立在严格的数学概念上、数据结构结构简单、存取路径对用户透明

• 缺点：查询效率不如结构化数据模型

数据库系统的结构

数据库系统模式的概念

• 型：对某一类数据的结构和属性的说明
• 值：型的一个具体赋值
• 模式：数据库中全体数据的逻辑结构和特征的描述（只涉及型）
• 实例：模式的一个具体值称为一个实例

数据库系统的三级模式结构

• 模式：也称逻辑模式，一个数据库只有一个模式。它是数据库中全体数据的逻辑结构和特征的描述，是所有用户的公共数据视图
• 外模式：也称子模式、用户模式，一个数据库可以有多个外模式。它是数据库用户能够看见和使用的局部数据的逻辑结构和特征的描述，是数据库用户的数据视图
  • 保证数据库安全性
• 内模式：也称存储模式，一个数据库只有一个内模式。它是数据物理结构和存储方式的描述，是数据在数据库内部的组织方式

graph TD
A[数据库] --> B[内模式]
B-->|内模式/模式影像|C[模式]
C-->|外模式/模式影像|D[外模式1]
C-->|外模式/模式影像|E[外模式2]
C-->|外模式/模式影像|F[外模式3]
D-->G[应用A]
D-->H[应用B]
E-->I[应用C]
E-->J[应用D]
F-->K[应用E]

数据库的二级映像功能与数据独立性

• 外模式/模式映像：定义了外模式和模式之间的相应关系

  • 保证数据的逻辑独立性

• 内模式/模式映像：定义了数据全局逻辑结构与存储结构之间的对应关系

  • 保证了数据的物理独立性

数据库系统的组成

• 硬件平台及数据库
• 软件
• 人员

关系数据库

关系数据结构及形式化定义

关系

域

• 域：一组具有相同数据类型的值的集合

笛卡尔积

• 笛卡尔积：域上的一种集合运算

  • 给定的一组域 $D_1,D_2,\dots,D_n$，允许其中的某些域是相同的，则 $D_1,D_2,\dots,D_n$ 的笛卡尔积为：
    $D_1×D_2×\dots×D_n=\{(d_1,d_2,\dots,d_n)\mid d_i\in D_i,i=1,2,\dots,n\}$
  • 元组：笛卡尔积中每一个元素 $(d_1,d_2,\dots,d_n)$ 叫作一个 $n$ 元组或简称元组
  • 分量：笛卡尔积元素 $(d_1,d_2,\dots,d_n)$ 中的每一个值 $d_i$ 叫作一个分量

• 基数：若 $D_i(i=1,2,\dots,n)$ 为有限集，其基数为 $m_i(i=1,2，…,\dots,n)$，则 $D_1×D_2×\dots×D_n$ 的基数 $M$ 为：$M=\Pi^{n}_{i=1}m_i$

  • 一般而言，笛卡尔积的某个子集才有实际含义

关系

• 关系

  • $D_1×D_2×\dots×D_n$ 的子集叫作在域 $D_1,D_2,\dots,D_n$ 上的关系，表示为 $R(D_1,D_2,\dots,D_n)$
    • $R$：关系名
    • $n$：关系的目或度

• 码/键

  • 候选码：若关系中的某一属性组的值能唯一地标识一个元组，则称该属性组为候选码

    • 简单的情况：候选码只包含一个属性

  • 全码：最极端的情况：关系模式的所有属性组是这个关系模式的候选码，称为全码

  • 在关系模型中，候选键或候选码是某个关系的一组属性所组成的集合，它需要同时满足下列两个条件：

    1. 这个属性集合始终能够确保在关系中能唯一标识元组
    2. 在这个属性集合中找不出真子集能够满足条件 1

  • 满足第一个条件的属性集合称为超键，因此我们也可以把候选键定义为“最小超键”，也就是不含有多余属性的超键

  • 主码：若一个关系有多个候选码，则选定其中一个为主码

    • 通常选择有代表性的、长度较短的候选码作为主码（主键），优先选择数字类型的候选键

  • 主属性：候选码的诸属性称为主属性

  • 外键：一个实体的主键被另外一个实体使用，以表达不同实体元组之间的关系

• 三类关系

  • 基本关系（基本表）：实际存在

  • 查询表：查询结果对应的表

  • 视图表：虚表，不对应实际存储的数据

• 基本关系的性质

  1. 列是同质的
  2. 不同的列可能出自同一个域
  3. 列的顺序无所谓
  4. 任意两个元组的候选码不能相同
  5. 行的顺序无所谓
  6. 分量必须取原子值

关系模式

• 关系：元组的集合

• 关系模式：指出元组集合的结构

• 同一关系模式下，可有很多的关系

• 关系模式是稳定的；而关系是某一时刻的值，是随时间可能变化的

• 关系模式可以形式化地表示为：$R(U,D,DOM,F)$

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

• 关系模式通常可以简记为
  $R(U)$ 或 $R(A_1,A_2,\dots,A_n)$

  • $R$：关系名
  • $A_1,A_2,\dots,A_n$ : 属性名
  • 域名及属性向域的映象常常直接说明为属性的类型、长度

关系数据库

• 关系数据库：所有关系的集合
  • 型：关系数据库模式
  • 值：在某一时刻对应的关系的集合

关系操作

基本的关系操作

• 常用的关系操作

  • 查询操作：选择、投影、连接、除、并、差、交、笛卡尔积
    • 选择、投影、并、差、笛卡尔积是5种基本操作
  • 数据更新：插入、删除、修改

• 关系操作的特点

  • 集合操作方式：操作的对象和结果都是集合，一次一集合的方式

关系数据语言的分类

• 关系代数语言：用对关系的运算来表达查询要求

  • 代表：ISBL

• 关系演算语言：用谓词来表达查询要求

  • 元组关系演算语言：谓词变元的基本对象是元组变量

    • 代表：APLHA,QUEL

  • 域关系演算语言：谓词变元的基本对象是域变量

    • 代表：QBE

• 具有关系代数和关系演算双重特点的语言

  • 代表：SQL

关系的完整性

• 实体完整性和参照完整性称为关系的两个不变性

实体完整性

• 实体完整性规则：若属性 $A$ 是基本关系 $R$ 的主属性，则 $A$ 不能取空值

参照完整性

• 设 $F$ 是基本关系 $R$ 的一个或一组属性，但不是关系 $R$ 的码。如果 $F$ 与基本关系 $S$ 的主码 $K_s$ 相对应，则称 $F$ 是 $R$ 的外码

  • 基本关系 $R$ 称为参照关系
  • 基本关系 $S$ 称为被参照关系或目标关系

• 参照完整性规则：若属性（或属性组）$F$ 是基本关系 $R$ 的外码它与基本关系 $S$ 的主码 $K_s$ 相对应（基本关系 $R$ 和 $S$ 不一定是不同的关系），则对于 $R$ 中每个元组在 $F$ 上的值必须为：

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

用户定义的完整性

• 某一具体应用所涉及的数据必须满足的语义要求

---

关系小结

• 关系模型
  • 关系——结构
  • 关系操作
  • 完整性
    • 实体完整性：主码
    • 参照完整性：外码
    • 自定义完整性：属性与属性组合

关系代数

• 关系代数是一种抽象的查询语言，它用对关系的运算来表达查询
• 基本运算符：并、差、笛卡尔积、投影、选择
• 集合运算符

运算符	含义
∪	并
−	差
∩	交
×	笛卡尔积

• 专门的关系运算符

运算符	含义
σ	选择
π	投影
⋈	链接
÷	除

• 比较运算符

；≥；<；≤；=；≠

• 逻辑运算符

¬；∧；∨

专门的关系运算符

一些表示

（1）$\mathrm{R}, \quad \mathrm{t} \in \mathrm{R}, \quad \mathrm{t}\left[\mathrm{A}_{\mathrm{i}}\right]$
设关系模式为 $R\left(A_{1}, A_{2}, \ldots, A_{n}\right)$，它的一个关系设为 $R$，

$t \in R$ 表示 $t$ 是 $R$ 的一个元组
$t\left[A_{i}\right]$ 则表示元组 $t$ 中相应于属性 $A_{i}$ 的一个分量

（2）$ \mathrm{A}, \mathrm{t}[\mathrm{A}], \mathrm{A}$
若 $A=\left\{A_{i 1}, A_{i 2}, \dots, A_{i k}\right\}$，其中 $A_{i 1}, A_{i 2}, \dots, A_{i k}$ 是 $A_{1}, A_{2}, \dots, A_{n}$ 中的一部分，则 $A$ 称为属性列或属性组。
$t[A]=\left(t\left[A_{i 1}\right], t\left[A_{i 2}\right], \ldots, t\left[A_{i k}\right]\right)$ 表示元组 $t$ 在属性列 $A$ 上诸分量的集合。
$\bar{A}$ 则表示 $\left\{A_{1}, A_{2}, \dots, A_{n}\right\}$ 中去掉 $\left\{A_{i 1},A_{i 2}, \dots, A_{i k}\right\}$ 后剩余的属性组。

（3）$\overset{\frown} {t_r t_s}$
$R$ 为 $n$ 目关系，$S$ 为 $m$ 目关系。
$t_r \in R, t_s \in S, \overset{\frown}{t_rt_s}$ 称为元组的连接。
$\overset{\frown} {t_r t_s}$ 是一个 $n+m$ 列的元组, 前 $n$ 个分量为 $R$ 中的一个 $n$ 元组，后 $m$ 个分量为 $S$ 中的一个 $m$ 元组。

（4） 象集 $Z_x$
给定一个关系 $R(X, Z)$，$X$ 和 $Z$ 为属性组。 当 $t[X]=x$ 时， $x$ 在 $R$ 中的象集为:

$Z_{\mathrm{x}}=\left\{t[Z] \mid t \in R, \quad t[X]=x\right\}$

它表示 $R$ 中属性组 $X$ 上值为 $x$ 的诸元组在 $Z$ 上分量的集合

选择

• 选择又称为限制
• 选择运算符的含义
  • 在关系R中选择满足给定条件的诸元组

$\sigma_{\mathrm{F}(t)}(R)=\left\{t \mid t \in R \wedge F(t)=True\right\}$

• F： 选择条件, 是一个逻辑表达式, 取值为 "真"或 “假”

  • 基本形式为： $X_{1} \theta Y_{1}$

  • $\theta$ 表示比较运算符

投影

• 从关系R中选择出若干属性列组成新的关系 $\Pi_{A}(R)=\left\{t[A] \mid t \in R \right\}$

  • $A$：$R$ 中的属性列

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

连接

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

$R \bowtie_{X \theta Y} S=\sigma_{X \theta Y}(R \times S)$

• 两类常用的连接运算
  • 等值连接：$R \bowtie_{X = Y} S=\sigma_{X = Y}(R \times S)$
  • 自然连接：特殊的等值连接——去掉了重复的属性列 $R \bowtie S$
    • 悬浮元组：两个关系 $R$ 和 $S$ 在做自然连接时被舍弃的元组
• 外连接：如果把悬浮元组也保存在结果关系中，而在其他属性上填 Null，就叫做外连接
  • 左外连接：只保留左边关系 $R$ 中的悬浮元组
  • 右外连接：只保留右边关系 $S$ 中的悬浮元组

除

• 给定关系 $R(X,Y)$ 和 $S(Y,Z)$，其中 $X,Y,Z$ 为属性组。$R$ 中的 $Y$ 与 $S$ 中的 $Y$ 可以有不同的属性名，但必须出自相同的域集。$R$ 与 $S$ 的除运算得到一个新的关系 $P(X)$，$P$ 是 $R$ 中满足下列条件的元组在 $X$ 属性列上的投影：
  • 元组在 $X$ 上分量值 $x$ 的象集 $Y_x$ 包含 $S$ 在 $Y$ 上投影的集合
  • 记作：$R÷S=\left\{t_r[X]|t_r\in R∧\Pi_Y(S)⊆Y_x\right\}$，其中 $Y_x$ 是 $x$ 在 $R$ 中的象集。
• 除法运算经常用于求解“查询…至少/全部的/所有的…”问题

关系数据库标准语言 SQL

SQL 概述

SQL 的特点

• 综合统一：集 DDL，DML，DCL 功能于一体等
• 高度非过程化：SQL只要提出“做什么”，无须了解存取路径
• 面向集合的操作方式
• 以同一种语法结构提供多种使用方式：是独立的语言，也是嵌入式语言
• 语言简洁，易学易用：核心功能只用了9个动词

SQL 的基本概念

• 模式——基本表

  • 本身独立存在的表
  • SQL中一个关系就对应一个基本表
  • 一个（或多个）基本表对应一个存储文件
  • 一个表可以带若干索引

• 内模式——存储文件

• 外模式——视图

  • 从一个或几个基本表导出的表
  • 数据库中只存放视图的定义而不存放视图对应的数据
  • 视图是一个虚表
  • 用户可以在视图上再定义视图

数据定义

操作对象	创建	删除	修改
模式	CREATE SCHEMA	DROP SCHEMA
表	CREATE TABLE	DROP TABLE	ALTER TABLE
视图	CREATE VIEW	DROP VIEW
索引	CREATE INDEX	DROP INDEX	ALTER INDEX

模式的定义与删除

定义模式

• e.g:

CREATE SCHEMA <模式名> AUTHORIZATION <用户名>[<表定义子句>|<视图定义子句>|<授权定义子句>]

• 定义模式实际上定义了一个命名空间

删除模式

• e.g:

DROP SCHEMA <模式名> <CASCADE|RESTRICT>

• CASCADE：删除模式的同时把该模式中所有的数据库对象全部删除
• RESTRICT：如果该模式中定义了下属的数据库对象（如表、视图等），则拒绝该删除语句的执行
  • 仅当该模式中没有任何下属的对象时才能执行

基本表的定义、删除与修改

定义数据表

• 基本格式：

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

数据类型

• SQL 中域的概念由数据类型实现

• 定义表的属性时需要指明其数据类型及长度

• CHAR，VARCHAR

  • 通常以 byte 计数
  • CHAR 类型数据插入数据库后，会自动补齐空格；VARCHAR 不会

• NCHAR，NVARCHAR

  • 以字符计数
  • 通常是 UTF-8 字符集，1 汉字=3字节

• 日期与时间

  • 统一格式：方便检索、查询
  • 不同的数据库，提供的函数不同
  • 时区问题

• 字符串常量的界定标识

  • 标准 sql 使用单引号’标识字符串常量
  • 很多数据库实现，双引号”也可以标识字符串，但不同数据库有特别的含义
  • 字符串中间的2个连续单引号转义为一个单引号
  • 双引号”通常用来标识关键字，对象名、字段名
  • Oracle中双引号标识的对象名/字段名区分大小写！

• 字符串拼接

  • Oracle：||
  • MySQL：空格

模式与表

• 每一个基本表都属于某一个模式
• 一个模式包含多个基本表

修改基本表

• <表名>是要修改的基本表

  • ADD 子句用于增加新列、新的列级完整性约束条件和新的表级完整性约束条件

  • DROP COLUMN 子句用于删除表中的列

    • 如果指定了 CASCADE 短语，则自动删除引用了该列的其他对
    • 如果指定了 RESTRICT 短语，则如果该列被其他对象引用，关系数据库管理系统将拒绝删除该列

  • DROP CONSTRAINT 子句用于删除指定的完整性约束条件

  • ALTER COLUMN 子句用于修改原有的列定义，包括修改列名和数据类型

删除基本表

• DROP TABLE <表名>［RESTRICT | CASCADE］;
  • RESTRICT：删除表是有限制的。
    • 欲删除的基本表不能被其他表的约束所引用
    • 如果存在依赖该表的对象，则此表不能被删除
  • CASCADE：删除该表没有限制。
• 在删除基本表的同时，相关的依赖对象一起删除

索引的建立与删除

• 建立索引的目的：加快查询速度
  • 建立者：建表者
  • 维护者、使用者：关系数据库管理系统

建立索引

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

• <表名>：要建索引的基本表的名字

• 索引：可以建立在该表的一列或多列上，各列名之间用逗号分隔

• <次序>：指定索引值的排列次序，升序：ASC，降序：DESC。缺省值：ASC

• UNIQUE：此索引的每一个索引值只对应唯一的数据记录

• CLUSTER：表示要建立的索引是聚簇索引（SQL Server语法）

修改索引

ALTER INDEX <旧索引名> RENAME TO <新索引名>

删除索引

DROP INDEX <索引名>

数据字典

• 数据字典：是关系数据库管理系统内部的一组系统表，它记录了数据库中所有定义信息
  • 关系数据库管理系统在执行 SQL 的数据定义语句时，实际上就是在更新数据字典表中的相应信息

数据查询

单表查询

• 定义：查询仅涉及一个表
  1. 选择表中的若干列
     • 选择表中若干列 SELECT Sno FROM Student
     • 查询全部列 SELECT * FROM Student
     • 查询经过计算的值 SELECT 2014-Sage FROM Student
  2. 选择表中的若干元组
     • 消除取值重复的行 SELECT DISTINCT Sno FROM SC
       • 不消除 SELECT ALL Sno FROM SC或 SELECT Sno FROM SC
     • 查询满足条件的元组 WHERE
       • =，!=，<，> 等
       • [NOT] BETWEEN AND，[NOT] IN
       • [NOT] LIKE '<匹配串>' [ESCAPE'<换码字符>']：%代表任意长度字符，_表示任意单个字符
       • IS [NOT] NULL
       • AND，OR
  3. ORDER BY 子句
     • ASC（缺省）升序；DESC 降序
  4. 聚集函数：不能作为条件表达式
     • 统计元组个数 COUNT(*)
     • 统计一列中值的个数 COUNT([DISTINCT|ALL]<列名>)
     • 计算一列值的总和（此列必须为数值型）SUM([DISTINCT|ALL]<列名>)
     • 计算一列值的平均值（此列必须为数值型）AVG([DISTINCT|ALL]<列名>)
     • 求一列中的最大值和最小值 MAX([DISTINCT|ALL]<列名>) MIN([DISTINCT|ALL]<列名>)
  5. GROUP BY子句：将查询结果按某一列或多列的值分组，值相等的为一组
     • GROUP BY，HAVING

连接查询

• 定义：查询涉及两个以上的表
  1. 等值于非等值连接查询
     • 等值连接 =
     • 自然连接 NATURAL JOIN ：去掉目标列的重复属性
     • 其他符号为非等值连接，使用较少
  2. 自身连接：一个表与其自己进行连接，需要给表起别名以示区别
  3. 外连接
     • LEFT OUTER JOIN
  4. 多表连接
• JOIN
  • INNER JOIN
  • OUTER JOIN
  • NATURAL JOIN
  • CROSS JOIN：如果没有 WHERE 条件，返回所有表连接的笛卡尔积

嵌套查询

• 一个 SELECT-FROM-WHERE 语句称为一个查询块
• 嵌套查询：将一个查询块嵌套在另一个查询块的 WHERE 子句或 HAVING 短语的条件中的查询
• 上层的查询块称为外层查询或父查询
• 下层查询块称为内层查询或子查询，不能使用 ORDER BY
  • 依赖父查询，称为相关子查询；否则为不相关子查询
  • IN；比较运算符；ANY、ALL；EXISTS

	=	<>或!=	<	<=	>	>=
ANY	IN	–	<MAX	<=MAX	>MIN	>=MIN
ALL	–	NOT IN	<MIN	<=MIN	>MAX	>=MAX

• 所有带 IN 谓词、比较运算符、ANY 和 ALL 谓词的子查询都能用带 EXISTS 谓词的子查询等价替换
  • SQL语言中没有全称量词 ∀，可以把带有全称量词的谓词转换为等价的带有存在量词的谓词：$（∀x）P≡ ¬（∃x（¬P））$
  • EXISTS 的通俗理解：将外查询表的每一行，代入内查询作为检验，如果内查询返回的结果取非空值，则 EXISTS 子句返回TRUE，这一行可作为外查询的结果行

集合查询

• 并 UNION
  • UNION：合并查询结果时，去掉重复元组
  • UNION ALL：合并查询结果时，保留重复元组
• 交 INTERSECT
• 差 EXCEPT

基于派生表的查询

• 子查询不仅可以出现在 WHERE 子句中，还可以出现在 FROM子句中，这时子查询生成的临时派生表成为主查询的查询对象

SELECT 语句的一般格式

SELECT [ ALL | DISTINCT ]<目标列表达式>[,<目标列表达式>]…
FROM <表名或视图名>[ ,<表名或视图名>]…|( SELECT 语句)
[ AS ]<别名>
[ WHERE <条件表达式>]
[ GROUP BY<列名1>[ HAVING <条件表达式>]]
[ ORDER BY<列名2>[ ASC | DESC ]];

SELECT的一些特别用法

• CASE WHEN：条件返回

SELECT sname, (CASE sdeptwhen 'CS' THEN '计算机' WHEN 'IS' THEN '信息' ELSE '其他' END) AS DEPT FROM student;

• TOP, LIMIT or ROWNUM ：返回查询结果集的前 N 条记录

• WITH … AS：定义一个临时作用域，便于随后的查询引用，类似临时表/视图

WITH qry AS ( SELECT * FROM student NATURAL JOIN scNATURAL JOIN course) 
SELECT sno, sname, cname, grade FROM qry;

• OracleCONNECT BY 层次遍历
  • 如果表中包含树状层级结构数据，那么就可以使用层次查询

正序：

SELECT cno, cpno, level, cnamefrom D9_COURSE 
START WITH cno=1 CONNECT BY cno= prior cpno
ORDER BY level

逆序：

SELECT cno, cpno, level, cnamefrom D9_COURSE
START WITH cno=6 CONNECT by prior cno= cpno
ORDER BY level

数据更新

插入数据

• 两种插入数据方式
  • 插入元组
  • 插入子查询结果：可以一次插入多个元组

插入元组

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

插入子查询结果

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

复制表结构/数据

• MySQL

  • 复制表结构

    CREATE TABLE SC_2 LIKE SC

  • 复制表结构和数据

    CREATE TABLE SC_2 SELECT * FROM SC

  • 复制数据

    INSERT INTO SC_2 SELECT * FROM SC

修改数据

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

删除数据

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

空值的处理

• 空值的产生：插入元组的部分属性为空；外连接；空值的关系运算
• 空值的判断：IS NULL；IS NOT NULL
• 空值的约束条件
  • 有 NOT NULL 约束条件的不能取空值
  • 加了 UNIQUE 限制的属性不能取空值
  • 码属性不能取空值
• 空值与另一个值（包括另一个空值）的算术运算的结果为空值
• 空值与另一个值（包括另一个空值）的比较运算的结果为 UNKNOWN
• 空值与另一个值（包括另一个空值）的逻辑运算时，同时考虑其可能为 True 和 False

视图

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

定义视图

建立视图

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

• WITH CHECK OPTION 表示对视图进行 UPDATE，INSERT，DELETE 操作时要保证更新的行仍然满足视图定义中子查询的条件表达式
• 行列子集视图：一个视图是从单个基本表导出的，并且只是去掉了基本表的某些行和某些列，但保留了主码

删除视图

DROP VIEW <视图名>[CASCADE]

• 如果该视图上还导出了其他视图，使用 CASCADE 级联删除语句，把该视图和由它导出的所有视图一起删除
• 删除基表时，由该基表导出的所有视图定义都必须显式地使用 DROP VIEW 语句删除

查询视图

• 用户角度：查询视图与查询基本表相同

• 关系数据库管理系统实现视图查询的方法：视图消解法

  1. 进行有效性检查

  2. 转换成等价的对基本表的查询

  3. 执行修正后的查询

更新视图

• 对视图的更新同样也是通过视图消解法实现

数据库完整性

• 数据库的完整性
  • 正确性：符合现实语义
  • 相容性：同一对象在不同表中符合逻辑
• 完整性不等于安全性：前者防止不正确的数据，后者防止非法操作

实体完整性

实体完整性定义

• CREATE TABLE 中用 PRIMARY KEY 定义
• 单属性构成的码有两种说明方法
  • 定义为列级约束条件
  • 定义为表级约束条件
• 对多个属性构成的码只有一种说明方法
  • 定义为表级约束条件

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

• 插入或对主码列进行更新操作时，关系数据库管理系统自动进行检查。包括：
  • 检查主码值是否唯一，如果不唯一则拒绝插入或修改
    • 全表扫描
  • 检查主码的各个属性是否为空，只要有一个为空就拒绝插入或修改

参照完整性

参照完整性定义

• 在 CREATE TABLE 中用 FOREIGN KEY 短语定义哪些列为外码
• 用 REFERENCES 短语指明这些外码参照哪些表的主码

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

• 处理策略
  • 拒绝执行
  • 级联操作
  • 设置为空值

用户定义的完整性

属性上的约束条件

• CREATE TABLE 时定义属性上的约束条件

  • 列值非空 NOT NULL

  • 列值唯一 UNIQUE

  • 检查列值是否满足一个条件表达式 CHECK

  • 如果不满足则操作被拒绝执行

元组上的约束条件

• CREATE TABLE 时用 CHECK 定义元组上的约束条件
  • 如果不满足则操作被拒绝执行

完整性约束命名子句

1. 完整性约束命名子句

CONSTRAINT <完整性约束条件名><完整性约束条件>

• <完整性约束条件>包括 NOT NULL、UNIQUE、PRIMARY KEY 短语、FOREIGN KEY 短语、CHECK 短语等

2. 修改表中的完整性限制

• eg：

  ALTER TABLE Student DROP CONSTRAINT C4

断言

• 断言：任何对断言中所涉及的关系的操作都会触发关系数据库管理系统对断言的检查，任何使断言不为真值的操作都会被拒绝执行

创建断言

CREATE ASSERTION <断言名> <CHECK 子句>

删除断言

DROP ASSERTION <断言名>

触发器

定义触发器

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

• 当特定的系统事件发生时，对规则的条件进行检查，如果条件成立则执行规则中的动作，否则不执行该动作

• 表的拥有者才可以在表上创建触发器

• 触发器名

  • 触发器名可以包含模式名，也可以不包含模式名
  • 同一模式下，触发器名必须是唯一的
  • 触发器名和表名必须在同一模式下

• 表名

  • 触发器只能定义在基本表上，不能定义在视图上
  • 当基本表的数据发生变化时，将激活定义在该表上相应触发事件的触发器

• 触发事件可以是 INSERT、DELETE 或 UPDATE 也可以是这几个事件的组合

  • 还可以 UPDATE OF<触发列，...>，即进一步指明修改哪些列时激活触发器

  • AFTER/BEFORE 是触发的时机

    • AFTER 表示在触发事件的操作执行之后激活触发器
    • BEFORE 表示在触发事件的操作执行之前激活触发器

• 触发器类型

  • 行级触发器 FOR EACH ROW
  • 语句级触发器 FOR EACH STATEMENT

• 触发条件

  • 触发器被激活时，只有当触发条件为真时触发动作体才执行;否则触发动作体不执行。
  • 如果省略 WHEN 触发条件，则触发动作体在触发器激活后立即执行

激活触发器

• 触发器的执行，是由触发事件激活的，并由数据库服务器自动执行
  • 顺序：BEFORE 触发器，激活触发器的 SQL 语句，AFTER 触发器

删除触发器

DROP TRIGGER <触发器名> ON <表名>

关系数据理论

问题的提出

• 针对具体问题，如何构造一个适合于它的数据模式——关系数据库的规范化理论

• 关系模式由五部分组成，是一个五元组：R(U, D, DOM, F)

  • 由于D、DOM与模式设计关系不大，因此在本章中把关系模式看作一个三元组：R<U,F>
  • 当且仅当 U上的一个关系 r 满足 F 时，r 称为关系模式 R<U,F> 的一个关系
  • 作为二维表，关系要符合一个最基本的条件：每个分量必须是不可分开的数据项
    • 满足了这个条件的关系模式就属于第一范式（1NF）

• 数据依赖：是一个关系内部属性与属性之间的一种约束关系

  • 通过属性间值的相等与否体现出来的数据间相互联系
  • 函数依赖 FD ；多值依赖 MVD

规范化

函数依赖

• 对 $r$ 上的任意 2 个元组 $t_1$, $t_2$, 如果 $t_1[X] = t_2 [X] \Rightarrow t_1[Y ] = t_2 [Y ]$ ，则 $X→Y$

  • $X$ 称为该函数依赖的决定因素

  • $X\rightarrow Y$ 表示 1:n 关系

  • 若 $X→Y$，并且 $Y→X$ , 则记为 $X←→Y$

    • 表达 1:1 关系

  • 若 $Y$ 不函数依赖于 $X$, 则记为 $X \nrightarrow Y$

    • 表达 m:n 关系

• 函数依赖是语义范畴的概念，只能根据数据的语义（也就是应用需求）来确定一个函数依赖

• $X→Y$，但 $Y⊈X$ 则称 $X→Y$ 是非平凡的函数依赖;如果 $Y\subseteq X$，则为平凡的函数依赖

  • 对于任一关系模式，平凡函数依赖都是必然成立的，它不反映新的语义；所以一般讨论非平凡的函数依赖

• 完全函数依赖：在 $R(U)$ 中，如果 $X→Y$，并且对于 $X$ 的任何一个真子集 $X’$, 都有 $X’ \nrightarrow Y$, 则称 $Y$ 对 $X$ 完全函数依赖，记作 $X→^{F}Y$

  • 若 $X→Y$，但 $Y$ 不完全函数依赖于 $X$ ，则称 $Y$ 对 $X$ 部分函数依赖，记作 $X→^P Y$

• 传递依赖：如果 $X→Y(Y⊈X)$，$Y↛X$，$Y→Z(Z⊈Y)$, 则称 $Z$ 对 $X$ 传递函数依赖 $X\rightarrow^{\text{传递}}Z$

  • 但是 $Y\rightarrow X$ 时，$Z$ 直接依赖于 $X$

码

• 候选码：设 $K$ 为 $R<U,F>$ 中的属性或属性组合。若 $K→ ^{F}U$，则 $K$ 称为 $R$ 的一个候选码

  • 如果 $K\rightarrow^{P} U$，$K$ 称为超码
  • 候选码是最小的超码
  • 主码是候选码中选出一个

• 主属性与非主属性

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

• 全码：整个属性组是码

• 外码：关系模式 $R$ 中属性或属性组 $X$ 并非 $R$ 的码，但 $X$ 是另一个关系模式的码，则称 $X$ 是 $R$ 的外码

范式

• 范式：符合某一种级别的关系模式的集合

  • 关系数据库中的关系必须满足不同范式，记为 $R \in nNF$
  • $1NF\supset2NF\supset3NF\supset BCNF \supset4NF \supset 5NF$

• 规范化：低一级范式的关系模式，通过模式分解转换为若干个高一级范式的关系模式的集合的过程

2NF

• 2NF：若关系模式 $R \in 1NF$，并且每一个非主属性都完全函数依赖于任何一个候选码，则 $R \in 2NF$
• 解决了非主属性对复合主键的部分依赖，对于单一候选键，一定符合 2NF

3NF

• 设关系模式 $R\in 1NF$，若 $R$ 中不存在这样的码 $X$、属性组 $Y$ 及非主属性 $Z(Z \supseteq Y)$, 使得 $X\rightarrow Y$，Y\rightarrowZ 成立，$Y\rightarrow X$ 不成立，则称 $R\in 3NF$

• 解决非主属性之间的依赖关系

BCNF

• 设关系模式 $R \in 1NF$，若 $X→Y$ 且 $Y⊆X$ 时 $X$ 必含有码，则 $R \in BCNF$

  • 即：每一个决定属性集都包含候选码

• BCNF 在函数依赖范畴内实现了模式的彻底分解，达到了最高的规范化程度，消除了插入异常和删除异常

多值依赖

• 设 $R(U)$ 是属性集 $U$ 上的一个关系模式。$X,Y,Z$ 是 $U$ 的子集，并且 $Z=U-X-Y$。关系模式 $R(U)$ 中多值依赖 $X→→Y$ 成立，当且仅当对 $R(U)$ 的任一关系 $r$，给定的一对 $(x,z)$ 值，有一组 $Y$ 的值，这组值仅仅决定于 $x$ 值而与 $z$ 值无关。
  • 若 $X→→Y$，而 $Z$ 为空，则称 $X→→Y$ 为平凡的多值依赖。
  • 否则称 $X→→Y$ 为非平凡的多值依赖
• 多值依赖的性质
  • 多值依赖具有对称性
  • 多值依赖具有传递性
  • 函数依赖是多值依赖的特殊情况

4NF

• 关系模式 $R<U,F> \in 1NF$，如果对于 $R$ 的每个非平凡多值依赖 $X→→Y(Y⊈X)$，$X$ 都含有码，则 $R<U,F> \in 4NF$
• 4NF​ 就是限制关系模式的属性之间不允许有非平凡且非函数依赖的多值依赖

规范化小结

graph TB;
A[1NF]--消除非主属性对码的部分函数依赖-->B[2NF]
B--消除非主属性对码的传递函数依赖-->C[3NF]
C--消除主属性对码的部分和传递函数依赖-->D[BCNF]
D--消除非平凡且非函数依赖的多值依赖-->E[4NF]

数据库设计

数据库设计概述

数据库设计的特点

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

• 几个常用述语

  • 元数据：指公司数据资产管理的基础，是关于“数据的数据”
    • 例如数据类型、数据定义、数据关系等
    • 相当于数据表格中的表头信息
  • 主数据：指满足跨部门业务协同需要的、反映核心业务实体状态属性的企业基础信息

数据库设计方法

• 手工试凑法
• 规范设计法
  • 新奥尔良（New Orleans）方法
  • 基于E-R模型的数据库设计方法
  • 3NF（第三范式）的设计方法
  • 面向对象的数据库设计方法
  • 统一建模语言（UML）方法

数据库设计的基本步骤

• 数据库设计分6个阶段
  1. 需求分析
  2. 概念结构设计：概念模型，E-R 图（概念模式）
  3. 逻辑结构设计：关系，非关系（外模式）
  4. 物理结构设计：存储结构（内模式）
  5. 数据库实施
  6. 数据库运行和维护

需求分析

需求分析的任务

需求分析的方法

• 结构化分析方法

数据字典

• 数据字典：描述数据流、数据存储的逻辑内容
  • 数据项：最小组成单位
  • 数据结构：反映了数据之间的组合关系
  • 数据流：数据结构在系统内传输的路径
  • 数据存储：数据结构停留或保存的地方
  • 处理过程：描述处理过程的说明性信息

概念结构设计

概念模型

• 将需求分析得到的用户需求抽象为概念模型
  • 易于理解
  • 真实反映世界

E-R 模型

• E-R模型的基本观点：世界是由一组称作实体的基本对象和这些对象之间的联系构成的
  • 刻画：实体、属性、联系、关键字/码

实体之间的联系

• 两个实体型之间的联系

  • 一对一联系（1∶1）
  • 一对多联系（1∶n）
  • 多对多联系（m∶n）

• 联系的度：参与联系的实体型的数目

E-R图

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

  • 实体型：用矩形表示，矩形框内写明实体名。
  • 属性：用椭圆形表示，并用无向边将其与相应的实体型连接起来
  • 联系：用菱形表示，菱形框内写明联系名，并用无向边分别与有关实体型连接起来，同时在无向边旁标上联系的类型（1∶1，1∶n或m∶n）

• Chen ERD

• Crow’s Foot Notation

概念结构设计

实体与属性的划分原则

• 实体应包含描述信息
  • 如果一个数据元素有描述型信息，该数据元素应被识别为实体
  • 如果一个数据元素只有一个标识名，则其应被识别为属性
    • 两条准则：
      1. 属性必须是不可分的数据项，不能包含其他属性
      2. 属性不能与其他实体具有联系

实体属性

• 简单与复合属性.
• 单值与多值属性
• 多值属性通常被识别为实体
• 派生属性
• 可以从其他属性计算而来
• 属性依附
• 把属性附加在其最直接描述的实体上

E-R图的集成

• E-R图的集成一般需要分两步
  1. 合并。解决各分E-R图之间的冲突，将分E-R图合并起来生成初步E-R图
     • 冲突主要有三类：
       1. 属性冲突：属性域冲突、属性取值单位冲突
       2. 命名冲突：同名异义、异名同义
       3. 结构冲突：
          • 同一对象在不同应用中具有不同的抽象
          • 同一实体在不同子系统的E-R图中所包含的属性个数和属性排列次序不完全相同
          • 实体间的联系在不同的E-R图中为不同的类型
  2. 修改和重构。消除不必要的冗余，生成基本E-R图
     • 冗余的数据：指可由基本数据导出的数据
     • 冗余的联系：指可由其他联系导出的联系
     • 以数据字典和数据流图为依据，分析消除

逻辑结构设计

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

转换原则

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

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

  • 将每个分量属性作为复合属性所在实体的属性
  • 或者，将复合属性本身作为所在实体的属性

• 关系的码：实体的码

• 多值属性的转换：将多值属性与所在实体的关键字一起组成一个新的关系

2. 实体型间的联系有以下不同情况

• 1:1 联系
  • 转换为一个独立的关系模式
  • 或，与某一端实体对应的关系模式合并
• 1:n 联系
  • 转换为一个独立的关系模式
  • 或，与 n 端对应的关系模式合并
• m:n 联系
  • 转换为一个关系模式
• 三个或三个以上实体间的一个多元联系转换为一个关系模式
• 具有相同码的关系模式可合并

数据模型的优化

• 对关系模式进行必要分解
  • 水平分解：把关系的元组分成若干子集合，定义每个子集合为一个子关系，以提高系统的效率
  • 垂直分解：将一个属性比较多，一行数据比较大的表，将不同的属性拆分到不同的表中以降低单表大小，达到提升性能的方法

设置用户子模式

• 使用更符合用户习惯的别名
• 针对不同级别的用户定义不同的视图，以保证系统的安全性
• 简化用户对系统的使用：复杂查询定义为视图

物理结构设计

关系模式存取方法选择

B+ 树索引存取方法

• 选择索引方法从一般规则
  • 一个（一组）属性经常在查询条件中出现
  • 一个属性经常作为最大值和最小值等聚集函的参数
  • 一个（一组）属性经常在连接操作的连接条件中出现

Hash 索引存取方法

• 选择 hash 存取方法的规则如下：如果一个关系的属性主要出现在等值连接条件中或主要出现在等值比较选择条件中，而且满足下列两个条件之一，则该关系可以选择 hash 存取
  1. 一个关系的大小可预知，而且不变
  2. 关系的大小动态改变，但 DBMS 提供了动态 hash 存取方法

聚簇存取方法

• 聚簇：为了提高某个属性（组）的查询速度，将这个（些）属性（称为聚簇码）上具有相同值的元组集中存放在连续的物理块中，称为聚簇
• 建立聚簇索引后，基表中数据也需要按照指定的聚簇属性值的升序或降序存放。即，聚簇索引的索引项顺序与表中元组的物理顺序一致
• 聚簇索引的使用条件
  • 很少对基表进行增删操作
  • 很少对其中的变长列进行修改操作

数据库编程

过程化 SQL

过程化 SQL 的块结构

• 过程化 SQL 块的基本结构

  • 定义部分 DECLARE

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

  • 执行部分

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

变量和常量的定义

• 变量定义
• 变量名 数据类型 [[NOT NULL]:= 初值表达式]
• 变量名 数据类型 [[NOT NULL] 初值表达式]
• 常量定义
  • 常量名 数据类型 CONSTANT:= 常量表达式
  • 常量必须给一个值，并且该值在存在期间或常量的作用域内不能改变
• 赋值语句
  • 变量名称:= 表达式

流程控制

• 过程化 SQL 功能
  1. 条件控制语句
     • IF-THEN , IF-THEN-ELSE
  2. 循环控制语句
     • LOOP , WHILE-LOOP , FOR-LOOP
  3. 错误处理

存储过程和函数

存储过程

• 过程化 SQL 块类型

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

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

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

• 存储过程的用户接口

  1. 创建存储过程

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

  2. 执行存储过程

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

  3. 修改存储过程

     ALTER PROCEDURE 过程1 RENAME TO 过程2

  4. 删除存储过程

     DROP PROCEDURE 过程名

函数

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

  1. 创建函数

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

  2. 执行存储过程

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

  3. 修改函数名

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

  4. 重新编译

     ALTER FUNCTION 函数名 COMLIPE

关系查询处理和查询优化

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

查询处理步骤

1. 查询分析：对查询语句进行扫描、词法分析和语法分析
2. 查询检查：检查合法权、视图转换（视图消解法）、安全性检查、完整性初步检查
3. 查询优化：选择一个高效的查询处理策略
   • 代数优化
   • 物理优化
4. 查询执行：依据优化器生成查询计划代码

代数优化

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

• 代数优化策略：通过对关系代数表达式的等价变换来提高查询效率
• 常用的等价变换规则
  1. 连接、笛卡尔积的交换律
  2. 连接、笛卡尔积的结合律
  3. 投影的串接定律
  4. 选择的串接定律
  5. 选择与投影操作的交换律
  6. 选择和笛卡尔积的交换律
  7. 选择和并的分配律
  8. 选择和差的分配律
  9. 选择对自然连接的分配律
  10. 投影和笛卡尔积的分配律
  11. 投影和并的分配律
  12. 投影和差没有分配律

查询树的启发式优化

• 典型的启发式规则
  1. 选择运算尽可能先做
  2. 把投影运算和选择运算同时进行
  3. 把投影同其前或后的双目运算结合起来
  4. 把某些选择同在它前面要执行的笛卡尔积结合起来成为一个连接运算

物理优化

基于规则的启发式优化

• 选择操作的启发式规则

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

  • 对于大关系

    • 对于选择条件是“主码=值”的查询，查询结果最多是一个元组，可以选择主码索引

    • 对于选择条件是“非主属性=值”的查询，并且选择列上有索引。要估算查询结果的元组数目

      • 如果比例较小可以使用索引扫描方法
      • 否则还是使用全表顺序扫描

    • 对于选择条件是属性上的非等值查询或者范围查询，并且选择列上有索引。要估算查询结果的元组数目

      • 如果比例较小可以使用索引扫描方法

• 否则还是使用全表顺序扫描

• 连接操作的启发式规则

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

基于代价估算的优化

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

数据库恢复

事务的基本概念

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

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

• 事务定义

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

• 事务结束

  • COMMIT：事务正常结束，提交事务的所有操作
  • ROLLBACK：事务异常终止，事务滚回到开始时的状态

• 事务的ACID特性：

  • 原子性：事务是数据库的逻辑工作单位

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

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

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

故障的种类

• 事务内部的故障
• 系统故障
• 介质故障
• 计算机病毒

恢复的实现技术

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

• 如何建立冗余数据

  • 数据转储

    • 静态转储：在系统中无运行事务时进行的转储操作
    • 动态转储
    • 海量转储
    • 增量转储

  • 登记日志文件

恢复策略

• 事务故障：撤销——反向扫描文件日志，找到事务操作
• 系统故障：撤销未完成的事务，重做已完成事务

并发控制

• 多事务执行方式
  • 事务串行执行
  • 交叉并发方式
  • 同时并发方式

并发控制概述

• 并发控制基本单位：事务

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

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

• 并发控制的主要技术

  • 封锁
  • 时间戳
  • 乐观控制法
  • 多版本并发控制

封锁

• 封锁：事务在对某个数据对象操作之前，先向系统发出请求，对其加锁

• 基本封锁类型

  • 排它锁（X 锁）：写锁，仅加锁事务可以读取和修改数据对象
  • 共享锁（S 锁）：读锁，其他事务可以读取，但是不能修改数据对象

封锁协议

• 封锁协议：在运用X锁和S锁对数据对象加锁时约定的规则

  • 何时申请 X 锁或 S 锁
  • 持续时间
  • 何时释放

• 三级封锁协议

  1. 一级封锁协议：事务 T 在修改数据 R 之前必须先对其加 X 锁，直到事务结束才释放

     • 防止丢失修改，不能保证可重复读和不读“脏”数据

  2. 二级封锁协议：一级封锁协议+事务 T 在读取数据 R 之前必须先对其加 S 锁，读完后即可释放 S锁

     • 防止丢失修改和不读“脏”数据，不能保证可重复读

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

     • 防止丢失修改、读“脏”数据和不可重复读

活锁和死锁

• 活锁：封锁导致的某个事务永远等待

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

• 死锁：封锁导致的事务永远不能结束

• 避免死锁

  • 预防死锁
    • 一次封锁法：一次将所有要用的数据全部加锁
    • 顺序封锁法：所有事务按某个顺序加锁
  • 诊断死锁
    • 超时法：超过规定时限就认为发生了死锁
    • 等待图法：用事务等待图动态反映所有事务的等待情况
  • 解除死锁
    • 选择一个处理死锁代价最小的事务，将其撤消

并发调度的可串行性

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

  • 可串行性

• 冲突：调度中一对连续的动作，它们满足：如果它们的顺序交换，那么涉及的事务中至少有一个事务的行为会改变

• 冲突可串行化：可串行化调度+交换不冲突操作次序得到的调度仍然是可串行化调度

两段锁协议

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

  • 用于实现并发调度的可串行性，遵守两段锁协议是可串行化调度的充分条件
  • 第一阶段，扩展阶段：获得封锁
  • 第二阶段，收缩阶段：释放封锁

• 一次封锁法遵守两段锁协议，但是遵守两段锁协议的事务可能发生死锁

封锁的粒度

• 封锁粒度：封锁对象的大小

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

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

  • 多粒度树：用树形结构表示封锁粒度，根节点数据粒度最大
  • 多粒度封锁数据对象可能以两种方式封锁
    1. 显式封锁
    2. 隐式封锁：因为上级结点加锁而加锁

• 意向锁：对任一结点加基本锁，必须先对它的上层结点加意向锁

  • 目的：提高对某个数据对象加锁时系统的检查效率
  • 种类
    1. 意向共享锁，IS 锁：它的后裔节点拟意向加 S 锁
    2. 意向排他锁，IX 锁：它的后裔节点拟意向加 X 锁
    3. 共享意向排他锁，SIX 锁：加 SIX 锁=加 S 锁+加 IX 锁