数据库Database课程笔记-BUAA

第一章概述

数据库技术，是一种数据管理技术

数据库技术的软件实现就是DBMS（数据库管理系统）

数据库系统是在数据库管理系统基础上建立的具有数据处理功能的系统
1
2
3
4
5
6
7
8
9
10
11
12
13
graph RL
A[数据库系统]
B[数据库]
C[数据库管理系统（DBMS）]
D[数据库技术]
E[应用程序]
F[数据管理技术]
C<-.数据处理.->B
C--数据管理-->A
B-->A
E-->A
D--软件实现-->C
D--属于-->F

数据管理技术的发展

数据库与其它数据管理技术相比有什么特点？

数据库技术要解决的基本问题是什么？

数据库技术产生与发展背景

1960s 操作系统、算法与数据结构、软件工程日趋成熟，出现数据库技术（业务数据处理）（科学计算）
层次、网状、关系三类数据库经过发展，关系数据库最终成为主流
今天出现NewSQL、NoSQL（延申到智能化数据处理领域）

数据管理技术的发展过程

人工管理阶段
- 时间：<1950s
  - 背景：只有磁带、卡片等；没有操作系统；主要用于科学计算
  - 特点：
    - 数据不在计算机上存储
    - 程序规定数据的逻辑结构与物理结构，数据与程序不具有独立性（由程序员设计）
    - 应用程序与数据组一一对应
      1
      2
      3
      4
      graph LR
      A[应用程序1]-.-D[文件1]
      B[应用程序2]-.-E[文件2]
      C[应用程序3]-.-F[文件3]
文件系统阶段
- 时间：1950s-1960s
  - 背景：出现磁盘、磁鼓；出现文件系统；计算机不但用于科学计算，还用于管理
  - 特点：
    - 数据以文件形式保留在外存上
    - 数据存取以记录为单位
    - 程序与数据有一定独立性
    - 文件与程序基本上是一一对应关系
      1
      2
      3
      4
      5
      graph LR
      G[存取系统]
      A[应用程序1]-.-G-.-D[文件1]
      B[应用程序2]-.-G-.-E[文件2]
      C[应用程序3]-.-G-.-F[文件3]

* 问题：数据冗余度大、存储空间浪费、易造成数据的不一致性、维护难度大

数据库系统阶段

数据库系统基本问题与关键技术

需求：
- 集成：将特定应用环境中的所有相关的数据，进行统一地、集中地按照一定数据结构进行存储
- 共享：数据可为多个不同的用户所共享
核心技术：
- 数据模型
- 数据独立性
核心软件：数据库管理系统DBMS（Database Manage System）
- 最早的DBMS——IMS，IDS
- 查尔斯·巴赫曼数据库技术之父：在《IDS与DBTG报告》中提出“三级模式、两级映像”

数据库系统数据管理特点

面向全组织的复杂的数据结构
- 在描述数据时，不仅描述数据本身，还要描述数据之间的联系，使整个组织的数据结构化
- 数据库与文件系统的根本区别

数据冗余度小，易扩充

数据库可以随时选择子集，灵活度高

具有较高的数据和程序的独立性

三级模式、两级映像

graph BT
a[应用1]
b[应用2]
c[应用3]
d[应用4]
e[局部逻辑结构（外模式1）]
f[局部逻辑结构（外模式2）]
g[全局逻辑结构（模式）]
h[物理结构（内模式）]
i[数据库]
e-->a
e-->b
f-->c
f-->d
g--外模式/模式映像1-->e
g--外模式/模式映像2-->f
h<--模式/内模式映像-->g
i<-->h
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151


* 统一的数据控制功能

  * 数据的安全性控制（保护非法操作）

  * 数据的完整性控制（数据的正确性）

  * 并发控制

  * 数据库恢复


* 数据的最小存取单位是数据项
  * 既可以存取一个或一组记录，也可以存取数据中某个或一组数据项


### 数据模型

> 数据库技术要解决的基本问题是什么？数据的集成问题

#### 数据模型定义

* 数据模型用来抽像和表示现实世界中的数据和信息

* 目标：现实世界数据和机器世界数据的转换

#### 数据模型的层次

* 将现实世界业务的数据进行认识、抽象，转化为信息世界中的**概念模型**（也称信息模型）
* 将概念模型转化为机器世界数据中的**数据模型**（如层次、网状、关系）

#### 概念模型

* 基于信息世界的概念，表达各种信息
* 有较强的语义表达能力，简单、清晰、便于理解
* 常用E-R法进行表示

#### E-R法（Entity-Relation Approach）

* 目标：描述显示世界，并转换成相应的数据模型

* 基本概念

  * **实体**（Entity）：客观存在并可相互区分的事物 **长方体**

  * **属性**（Attribute）：实体所具有的某一特性 **椭圆形**

  * **码/键**（Key）：唯一标识实体的属性集

  * **域**（Domain）：某个属性的取值范围

  * **实体型**（Entity Type）：表示一类实体，用实体名及其属性名集合来抽象、刻画

  * **联系**（Relation）：实体型之间的联系，是实体之间的相互关联 **菱形**
    * 名称
    * 类型：一对一、一对多、多对多
    * 可以具有属性

* 联系的语义扩充

  > 我从没在这章以外的题目中碰到这几个

  * 存在依赖
    某实体存在依赖于另一实体的存在，称该实体为弱实体，该实体**存在依赖**另一实体
  * 标识依赖
    如果实体不能由它自己的属性来唯一标识，而必须通过与它相联系的另一实体一起来标识 ，那么称该实体**标识依赖**于另一个实体
  * 实体的子类
    子类可以继承父类属性，并定义自己的属性；子类间交集不一定为空

* 注意：

  * 同一个实体机内部各实体之间也可以存在不同类型的联系
  * 三个或多个实体型间可能具有联系（按语义确定类型）
  * 两个实体型之间可具有多种联系

#### 数据模型

* 定义：数据模型是概念的集合，精确描述数据库系统的**静态特性、动态特性和完整性约束**
* 三要素：数据结构、数据操作、完整性约束
* 数据结构（怎么存）
  * 由描述数据对象以及对象之间联系的一组概念组成
  * 描述对象的类型、内容、性质的概念，如关系模型中的域、属性等；描述对象之间联系的概念，如关系模型中的关系
  * 是数据**静态特性**的描述
  * 是刻画数据模型**最重要**的方法，通常按照数据结构的类型来命名数据模型
* 数据操作（怎么改）
  * 是对数据库中各种数据对象（型）的实例（值）允许执行的操作集合，包括操作及操作规则
  * 定义操作的确切含义、操作符号、操作规则及操作语言
  * 是数据**动态特性**的描述
  * 数据库主要有**检索和更新**（插、删、改）两大类操作
* 完整性约束
  * 是**完整性规则**的集合
  * 完整性规则是给定的数据模型中数据及其联系所有的制约和依存规则，用以保证数据的正确、相容；
  * 完整约束条件包括：
    * 符合这种数据模型所必须遵守的基本的通用的完整性约束条件
    * 针对具体数据的特定语义约束条件


#### 数据模型的分类

* 层次模型
  * ”树结构“表示联系
* 网状模型
  * ”图结构“表示联系
* 关系模型
  * ”二维表“表示联系
  * 关系中的每个分量是不可分的数据项

### 数据库系统结构

> 有效解决这些问题的技术是什么？

#### 逻辑结构 vs. 物理结构

* 逻辑结构：数据在程序中定义的结构
* 物理结构：文件在存储介质上的结构

#### 数据独立性

> 解决数据库的共享问题

* 数据独立性由数据和程序共同决定
* 如果数据**物理结构**改变，不需要修改程序，则有**物理独立性**（通过文件系统解决）
* 如果数据**逻辑结构**改变，不需要修改程序，则有**逻辑独立性**（通过SQL解决）
* 如果修改数据，则必须修改程序，则无数据独立性（如果不具有物理独立性或逻辑独立性，则无数据独立性）

#### 三级模式、两级映像

* 用于实现物理独立性及逻辑独立性

* 数据库结构多层次抽象，层次之间建立映射/对应关系

* ```mermaid
  graph BT
  a[应用1]
  b[应用2]
  c[应用3]
  d[应用4]
  e[局部逻辑结构（外模式1）]
  f[局部逻辑结构（外模式2）]
  g[全局逻辑结构（模式）]
  h[物理结构（内模式）]
  i[数据库]
  e-->a
  e-->b
  f-->c
  f-->d
  g--外模式/模式映像1-->e
  g--外模式/模式映像2-->f
  h<--模式/内模式映像-->g
  i<-->h

数据库由OS管理，其它部分由DBMS管理；OS和DBMS统一由DBA管理
模式
- 是数据库中全体数据的逻辑结构和特性的描述
- 是所有用户的公共数据视图
- 也称为逻辑模式、概念模式
- 用DDL（Data Description Language）进行定义
- 三级模式的核心
外模式
- 与某一特定应用有关的数据的逻辑表示
- 是个别用户的数据视图
- 也称为子模式、用户模式
- 通常是模式的子集
内模式
- 对数据的物理结构和存储方式的描述
- 通常用内模式DDL定义
- 我们程序员不用管🐶
外模式/模式映像
- 解决数据的逻辑独立性
模式/内模式映像
- 解决数据的物理独立性
优点
- 保证数据的独立性
- 简化用户接口，方便用户使用
- 有利于数据共享
- 有利于数据的安全保密

DBMS主要功能

DBMS是数据库系统的核心软件，在操作系统的支持下工作

数据库定义功能
- 提供DDL语言描述外模式、模式、内模式
- 模式翻译程序将源模式翻译成目标模式
数据存取功能
- 提供DML语言（Data manipulation language）对数据库进行检索、插入、修改、删除
数据库运行管理
- 并发控制、存取控制、完整性约束条件检查和执行，日志组织和管理，事务管理和自动恢复
数据组织、存储和管理
数据库的建立和维护功能

第二章关系数据库

E.F.Codd于70年代初提出关系数据模型与关系数据理论，因此获得1981年的ACM图灵奖

~~没想到四十多年后的今天我还在学这个（吐槽）~~🥹

引言

关系理论建立在集合代数理论基础上，有着坚实的数学基础

早期系统

System R：IBM
INGRES：Berkeley

目前主流系统

Oracle、MySQL、PostgreSQL、DB2，SQL-Server等
国内：武汉达梦、人大金仓、华为OpenGauss

GaussDB vs. OpenGauss

GaussDB：华为云数据库统称，包括多个版本，如 GaussDB(for MySQL)、GaussDB(for PostgreSQL) 等

OpenGauss：基于 PostgreSQL 的扩展和优化的开源数据库系统

关系数据模型是如何定义的？

关系模型的优点和缺点是什么？

关系模型的基本概念

关系的数学定义

域（Domain）
一组具有相同数据类型值的集合
元组和分量
给定一组域$D1,D2…$，$D1\times D2…$得到的笛卡尔积的每个元素$(d_1,d_2,…)$称为n元组（n-tuple），或简称元组，元组的每一个值$d_k$叫做分量，分量不可分
笛卡尔积可以表示为二维表
关系也被称为二维表

$D_1$ $D2$ … $D_n$

$d_1$ $d_2$ … $d_n$

… … … …
关系
笛卡尔积叫做在域$D_1, D_2…D_n$上的关系，用$R(D_1,D_2,…D_n)$表示
n=1，单元关系
n=2，二元关系
二维表的每列称为属性(Attribute)

$D_1$	$D2$	…	$D_n$
$d_1$	$d_2$	…	$d_n$
…	…	…	…

关系的性质

列是同质的（Homogenenux），即每一列中的分量来自同一域
不同列可以出自同一域，每列必须有不同的属性名
行、列次序可以互换
任意两个元组不能完全相同
每一分量必须是不可再分的数据，满足这一条件的关系称为满足**第一范式（1NF）**的
eg. 若某分量为二元组（a1, a2），则不满足第一范式

关系模型的数据结构

关系模型的数据结构就是“关系”

关系
- 实体及实体之间的联系均用单一的数据结构——关系来约束
基本概念
- 关系、域、n目关系、元组、属性
- 码（Key，键）
  - 候选码（Candidate key）：关系中的某一属性组，若它的值唯一地标识了一个元组，并具有最小性，则为候选码
  - 主码（Primary key，首码，码）：若一个关系有多个候选码，则选择其中一个为主码
  - 最小性：在保持唯一性的前提下，候选码不包含任何冗余属性。也就是说，如果从候选码中去掉任何一个属性，剩下的属性集将无法继续唯一标识数据记录。
- 主属性和非主属性
  - 候选码中的属性称为主属性，否则为非主属性
关系模式
- 作用：描述数据库的逻辑结构
- 形式化表示：$R(U, D, dom, F)$
  $R$：表示关系的名称，通常代表一个数据库表的名字
  $U$（Universe of attributes）：表示属性集合，包含该关系中的所有属性，每个属性对应数据库表中的一列
  $D$（Domains of attributes）：表示每个属性的定义域（Domain），即每个属性可以取的合法值的类型集合，更精简
  $dom$（Domain function）：表示一个映射函数，用于将每个属性映射到其对应的定义域，更精细
  $F$（Functional dependencies）：表示在该关系模式上定义的函数依赖集。函数依赖用于表示一个属性集如何函数性地决定另一个属性集
- 简记：$R(A_1,A_2…)$
- 关系是关系模式在某一时刻的状态或内容
  关系模式是静态的，关系是动态的
- 型：关系模式的集合构成关系数据库模式—关系数据库的型
- 值：关系的集合则构成具体的关系数据库—关系数据库的值。

关系模型的数据操作

特点：集合操作
- 操作的对象和结果都是集合

基础：关系运算

关系运算分为代数方式和逻辑方式

graph RL
A[关系代数（代数方式）]
B[关系演算（逻辑方式）]
C[元组关系演算]
D[域关系演算]
E[关系运算]
A--->E
B--->E
C--->B
D--->B
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117

  * 关系代数

    * 常规集合运算：并、差、交、广义笛卡儿积（乘）
    * 特有的关系运算：选择、投影、连接、自然连接、 求商

  * 关系演算

    * 元组演算：$\{t\mid\Phi(t)\}$
    * 域关系演算：$\{(x_1,x_2...\mid\Phi(x_1,x_2...)\}$


#### 关系模型的语义约束（完整性约束）

> 关系模型必须支持实体完整性和参照完整性，可以支持用户定义完整性

* 实体完整性（Entity Integrity）
  * 主码不可为空或部分为空
  * 空值：不知道或不存在的值
* 参照完整性（Referential integrity）
  * 若关系R的某个或某组关系F和关系S的主码相对应，则称F为关系R的**外部码（Foreign Key）**，并称R为**参照关系（Referencing Relation）**，S为被**参照关系（Referenced Relation）**或**目标关系（Target Relation）**；R和S不一定是不同的关系
  * 相对应的含义：R的外码和S的主码定义在一个域上
  * 参照完整性：若R的外码F和S的主码P相对应，则R中每一个元组的F值或者等于S中某元组的P值，或者为空值

* 用户定义完整性
  * 用户针对具体的应用环境定义的完整性约束

### 关系代数

> 从数学角度，基本关系代数运算有：并、差、乘、选择、投影
>
> 从数据库角度，核心的关系代数运算为：选择、投影、连接（或自然连接）

#### 传统集合运算

* 并（Union）
* 差（Defference）
* 交（Intersection）
* 广义笛卡儿积（Extended cartesian product）
  * $R\times S = \{t\mid t=<r,s>\and\ r\in R \and s\in S\}$

#### 专门的关系运算

* 选取或限制（Selection or Restriction）
  * $\sigma_F(R)=\{t\mid t\in R,F(t)=\text{True}\}$
  * e.g. $\sigma_{age=12}(S)$
* 投影（Projection)
  * $\Pi_A(R)=\{t[A]\mid t\in R, A\in U\}$
  * e.g. $\Pi_{Name,Age}(S)$
  * 需要删去重复行
* 连接（Join）
  * $\underset{X\theta Y}{R\bowtie S} =\{t\mid t=<r,s>\and r\in R \and s\in S \and r[X] \ \theta \ s[Y]\}$
* 自然连接（Natural Join）
  * $R\bowtie S=\{(Z,X,W)\mid (Z,X)\in R \and (X,W)\in S \and r[X] = s[X]\}$
  * 需要删去重复行
  * 连接与自然连接
    * 自然连接的结果要在上述R与S的等值连接结果基础上再进行投影运算，去掉重复的属性列
* 除法（Divide）
  * $R\div S = (t\mid t \in \Pi_x(R)\and s \in S\and <t,s> \in R)$
  * 翻译：R中所有与S做笛卡尔积得到的关系包含在R中的关系
  * ~~除法需要用乘法来定义，真是讽刺~~

#### 优先级

* 单目运算优先级最高，投影>选取
* 专门关系运算中的多目运算和笛卡尔积优先级其次
* 传统集合运算中的多目运算除笛卡尔积外优先级最低

### 元组关系演算与域关系演算

> 把谓词演算应用到关系运算中就是关系演算
>
> * 以元组为变量，简称元组演算
> * 以域为变量，简称域演算

#### 元组关系演算

* 基本结构：元组演算表达式
* 形式定义：$\{t\mid\Phi(t)\}$
* 递归定义
  1. 原子命题函数是公式，称为原子公式，原子公式有三类
     * $R(t)$
     * $t[i]\ \theta\  u[j]$
     * $t[i]\ \theta\ c或c\ \theta\ t[i]$
  2. 如果$\Phi_1$，$\Phi_2$是公式，则$\Phi_1\and\Phi_2,\Phi_1\or\Phi_2,\neg\Phi$也是公式
  3. 如果$\Phi$是公式，则$\exist t(\Phi), \forall t(\Phi)$也是公式

* 在元组演算公式中，各种运算符的优先次序为：
  * 算术比较运算符最高
  * 量词次之，且$\exist$的优先级高于$\forall$
  * 逻辑运算符最低，且$\neg$优先级高于$\and$，$\and$高于$\or$
  * 如果有括号，则括号中的运算优先级最高

#### 域关系演算

> 其实就是不用数组的元组关系演算🤣

* 形式定义：$\{(x_1,x_2...\mid\Phi(x_1,x_2...)\}$
* 与元组关系演算有相同的运算符、相同的公式递归定义

### 三类关系运算的安全约束及等价性

#### 关系运算的安全约束

* **安全运算**：关系运算中不产生无限关系和无穷验证的运算
* **安全表达式**：**安全运算**的运算表达式
* **安全约束**：对**安全运算**采取的限制
* 关系代数是安全运算，关系演算则不一定是，所以对关系演算要进行安全约束
  * 对$\Phi$定义一个优先的符号集$DOM(\Phi)$，使对$\Phi$的运算结果及中间结果所产生的关系及其 元组的各个分量都必须属于$DOM(\Phi)$

#### 三类关系运算的等价性

* 经过安全约束后的三类关系运算的表达能力是等价的，可以相互转换

* ```mermaid
  graph LR
  A[关系代数表达式]<-->B[安全元组演算表达式]<-->C[安全域演算表达式]<-->A

关系数据语言概述

数据库数据语言

数据定义（描述）语言（Data definition or description language，DDL）
- 包括模式DDL，外模式DDL，内模式DDL
数据操纵语言（Data Manipulation Language，DML）
- 四种基本操作：检索、插入、修改、删除
- DML有联机交互方式和宿主语言方式
  - 联机交互方式：自含式语言，可独立使用，适用于终端直接查询
  - 宿主语言方式：嵌入式语言，依附于宿主语言，嵌入高级语言的程序中，实现数据库操作
数据控制语言（Data Control Language，DCL）
- 完成数据库的安全性控制、完整性控制、并发控制

关系数据语言特点及优点

特点
- 一体化
  - 将数据的定义、查询、更新、控制等合为一体，只提供一种称之为“查询语言”的语言，便于用户学习使用
- 非过程化
  - 用户只需要决定“干什么”，具体“怎么干”由DBMS决定，使得语言操作简单、易学、易用
- 面向集合的存取方式
  - 操作的对象和结果都是关系
- 既可独立使用又可与主语言嵌套使用
优越性
- 关系模型采用了最简单的数据结构，使得DML大大简化
- 关系数据语言建立在关系运算的数学基础上，可以实现关系的垂直方向和水平方向的任意分割和组装操作，可构造出多样的新关系

关系数据语言分类

关系数据语言的核心是查询，所以又称为查询语言

graph LR
A[关系代数]
B[关系演算]
C[元组关系演算]
D[域关系演算]
E[ISBL]
F[ALPHA；QUEL]
G[QBE]
H[SQL]
I[关系运算]
I-->A
I-->B
A---->E
E--->H
F--->H
B-->C--->F
B-->D--->G

关系模型的优点与缺点

优点
- 建立在严格数学概念基础上，有严格的设计理论
- 概念单一，实体和联系都用关系描述，查询操作结果也是一个关系，保证了数据操作语言的一致性
- 数据结构简单直观、易理解、语言表达简洁
- 存取路径对用户透明，数据独立性更高，安全保密性更好,，简化了程序员和数据库开发建立的工作
缺点

随着各种查询优化的开发，劣势已经基本解决
- 由于存取路径对用户透明，查询效率不如层次、网状数据模型
- 为了提高性能，需要查询优化，增加数据库管理系统的开发难度

第三章关系数据库标准语言SQL

1974，由Chamberlin和Boyee提出，称为SEQUEL（Structured English Query Language），Chamberlin被称为SQL之父

1975-1979，在IBM的System R上实现

1981，IBM在推出SQL/DS关系数据库时，将其命名为SQL（Structured Query Language）

目前，ANSI和ISO先后制定了SQL-86、SQL-89……SQL-2011等多个SQL标准

2024，fysszlr被称为“SQL之耻”🏳️

概述

关系数据库中，可以通过SQL操作的数据对象有哪些？

SQL特点

综合统一
非过程化
面向集合
提供两种使用方式（交互式、嵌入式）
语言简洁、易学易用

基本概念

基本表与导出表
- 基本表：是实际存在的，在存储中可用一个存储文件来表示
- 导出表：是从基本表导出的表，由视图（View）和快照（Snapshot）
  - 相对于快照视图更常用一些
  - 视图是一个虚表，即在实际数据库中不单独存储视图的数据，只在数据库的数据字典中存储视图的定义
  - 视图一经定义就可以和基本表一样进行查询等操作，也可以用来定义新的视图
  - 视图定义示例
    1
    2
    3
    4
    Create View CS_STudent
    As
    SELECT S#,SN,SA FROM S
    WHERE SD = 'CS';
  - 快照是某一个时间点，数据库内信息的静态副本；视图可更新，快照不可更新

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

用户——SQL，外模式——View，模式——Base table，内模式——Stored file
用户可以操作外模式，也可以直接操作模式
外模式可以对应到一个模式，也可以对应到多个模式
一个模式对应一个内模式

graph TB
A[SQL]
B[View V1]
C[View V2]
D[Base table B1]
E[Base table B2]
F[Base table B3]
G[Base table B4]
H[Stored file S1]
I[Stored file S2]
J[Stored file S3]
K[Stored file S4]
A<--->D<-->H
A<-->B-->E<-->I
A<-->C-->F<-->J
C-->G<-->K

SQL语法

SQL如何实现数据定义、查询、更新、控制操作？

SQL数据查询功能

这一部分内容其实不多，理解例子并灵活运用最重要

下文例子默认：

S(S#, SN, SA, SD);

C(C#, CN, PC#);

SC(S#, C#, G);

基本结构：SELECT-FROM-WHERE组成的查询块

SELECT 目标列
FROM 基本表（或视图）
WHERE 检索条件;
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

* 查询块的结构仍然是一个表，查询块可以进行关系代数中投影、选取、连接等操作的组合

* SELECT对垂直方向进行操作，WHERE对水平方向进行操作

* 技巧

  * **投影操作**：如果没有WHERE，即为单纯的投影操作

    * 采用**DISTINCT**可以消去SELECT结果中的重复行

      ```sql
      # 检索全体学生选的课号
      SELECT DISTINCT C#
      FROM SC;


* **选取检索**：WHERE可以包含多种符号

  * 比较运算符：=、< >(!=)、>、>=、<、<=

  * 布尔运算符：AND、OR、NOT 

  * ( )

  * 使用**BETWEEN AND**可以区间查询

    1
2
3
SELECT S#
FROM SC
WHERE G BETWEEN 70 AND 85;


* **排序检索**：使用**ORDER BY**进行排序检索

  * 格式：ORDER BY 列名 ASC（或DESC）

  * ASC：升序，DESC：降序；默认升序

  * 支持多列排序

  * ```sql
    # 检索全体学生信息，并按系号升序，同一个系按年龄降序排
    SELECT *
    FROM S
    ORDER BY SD, SA DESC;
    1
2
3
4
5
6
7
8
9
10

* **连表检索**：将多个相互关联的表按照一定条件连接起来，可以实现连表检索

  * 此时WHERE需要包含连接条件和选取条件

    ```sql
    # 检索学生张华所学课程的成绩
    SELECT SN, C#, G
    FROM S, SC
    WHERE S.S#=SC.S# AND SN='张华';


  * 可以定义**别名**实现表自身的连接

    1
2
3
4
# 检索所有比李勇年龄大的学生姓名、年龄
SELECT X.SN, X.SA
FROM S X, S Y
WHERE X.SA>Y.SA AND Y.SN='李勇';


  * **外连接**
    在连接谓词某一边加\+或\*，则逻辑上为*所在边的表增加了一个空行；它可以与另一个表中所有不满足连接条件的元组进行连接，使这些元组能够输出

    1
2
3
4
# 检索所有学生的全部信息。
SELECT S.S#, SN,SA,SD, C#, G
FROM S, SC
WHERE S.S#=SC.S#(*);


* **嵌套检索**：WHERE的子句中可以包含另一个查询块，称为**子查询**或**嵌套查询**，包含子查询的语句称为**外部查询**

  * 普通子查询：与外部查询无关，可单独执行获得一组值

  * 相关子查询：把外查询的列值作为检索条件的条件值

  * 如果子查询返回单值，可以直接用比较运算符 =,<>,>,>=,<,<=等连接子查询

    1
2
3
4
5
6
# 检索与李勇同岁的学生姓名
SELECT SN
FROM S
WHERE S.SA=
	(SELECT SA FROM S
	WHERE SN='李勇');


  * 如果子查询返回一组值，则必须在比较运算符和子查询之间插入**ANY**、**ALL**、**IN**（在集合中）、**NOT IN** （不在集合中等）、**EXIST**（子查询不为空）、**NOT EXIST**（子查询不为空）等操作符啦

    1
2
3
4
5
6
7
# 检索选修C2课程的成绩最高的学生学号
SELECT S#
FROM SC
WHERE C#=‘C2’ AND
	G>=ALL
	(SELECT G FROM SC
	WHERE C#=‘C2’);


    特别的，可以用两个NOT EXIST表示任意或蕴含

    1
2
3
4
5
6
7
8
# 检索至少选修了学生S2选修的全部课程的学生学号
SELECT DISTINCT S#
FROM SC SCX
WHERE NOT EXISTS
    (SELECT * FROM SC SCY
    WHERE SCY.S# = 'S2' AND NOT EXISTS
        (SELECT * FROM SC SCZ
        WHERE S# = SCX.S# AND C# = SCY.C#));


* **并、差、交检索**：**UNION**（并）、**MINUS**（差）、**INTERSECT**（交）

  * 并、差、交检索的操作对象必须是相容的，是同类关系，即必须有相同数量的属性列，且相应属性列的域也必须相同

    1
2
3
4
5
# 检索无人选修的课程号和名称
SELECT C#，CN FROM C WHERE C# IN
    (SELECT C# FROM C
    MINUS
    SELECT DISTINCT C# FROM SC); # 我觉得这里的DISTINCT不必要


* **库函数检索**：库函数只能在SELECT和HAVING子句中出现

  | 库（集）函数 | 作用             |
  | ------------ | ---------------- |
  | COUNT()      | 按列值计个数     |
  | COUNT(\*)    | 对行记数         |
  | SUM()        | 对数值列求总和   |
  | AVG()        | 求数值列的平均值 |
  | MAX()        | 在列中找出最大值 |
  | MIN()        | 在列中找出最小值 |

* **分组检索**：按属性列（列组）将关系的元组分组，每组在这些分组属性列（列组）上具有相同值，对每一组执行SELECT操作

  * **HAVING**子句针对“分组”进行，必须和**GROUP BY** 连用，用于去掉不符合条件的若干分组

    1
2
GROUP BY 列名
[HAVING 条件表达式]


  * 出现的顺序：WHERE — GROUP BY — HAVING

    1
2
3
4
5
6
7
# 求选修四门以上课程的学生学号和总成绩（不统计不及格的课程）。最后按降序列出总成绩排序名单。
SELECT S#, SUM（G）
FROM SC
WHERE G>=60
GROUP BY S#
HAVING COUNT(*) >=4
ORDER BY SUM(G) DESC;


* **算术表达式检索**：SELECT子句中，可包括由属性列、常数、库函数、算 术运算符+-*/ 等组成的算术表达式；检索结果数据项名可用表达式表示或用“别名”来表示

  1
2
3
4
5
6
# 有职工表EMP( EMP#，EMPN，JOB，SALARY，BONUS，DEPT )，要求检索所有PROGRAMMER的奖金大于工资25%的职工姓名和一年的总收入，并按奖金与工资之比的降序排列。
SELECT EMPN,BONUS/SALARY BS, 12*(SALARY+BONUS) TOTAL
FROM EMP
WHERE JOB='PROGRAMMER'
AND BONUS>0.25*SALARY
ORDER BY BONUS/SALARY DESC;


* **部分匹配查询**：<列名> **LIKE**/**NOT LIKE** <字符串常量>

  * %：代表任意序列的0个或多个字符
  * _：代表任意单个字符

  1
2
3
4
# 检索所有姓刘的学生的学号、姓名
SELECT S#, SN
FROM S
WHERE SN LIKE '刘%';


* **派生表查询**：当子查询出现在FROM子句中，则子查询生成的表称为临时派生表，该表也可作为主查询的操作对象

  1
2
3
4
5
6
# 检索每个学生超出自己平均成绩的课程号。
SELECT S#, C#
FROM SC, (SELECT S#, AVG(G)
        FROM SC
        GROUP BY S# ) AS AVG_SC(AVG_S#,AVG_G)
WHERE SC.S# = AVG_SC.AVG_S# AND SC.G >= AVG_SC.AVG_G)

SQL数据定义功能

定义、删除、修改基本表
定义、删除视图
定义、删除索引
操作对象创建删除修改

基本表 Create Table Drop Table Alter Table

视图 Create View Drop View \

索引 Create Index Drop Index \

操作对象	创建	删除	修改
基本表	Create Table	Drop Table	Alter Table
视图	Create View	Drop View	\
索引	Create Index	Drop Index	\

SQL视图操作

定义视图

Create View <视图名>
[(<列名>[,<列名>] …)]
As <子查询>
[With Check Option]

删除视图
1
Drop View <视图名>
视图消解（View Resolution）
- DBMS执行视图查询操作时，将对视图的操作转化为对原始数据字典的查询，这一过程叫做视图消解
视图优点
- 能够简化用户操作
- 使用户能够以多种角度看待同一数据
- 提供了一定程度的逻辑独立性
- 能够对数据提供安全保护

SQL数据更新

插入数据——Insert语句
修改数据——Update语句
删除数据——Delete语句

SQL数据控制

定义完整性约束条件
支持事务操作
提供安全控制功能
- 授权
- 收回权限

空值处理

空值：“不知道”、”不存在“、”无意义“的值，统一用NULL表示
属性定义中使用NOT NULL和UNIQUE约束的域以及主属性都不可以取空值
空值算数运算结果为NULL，布尔运算结果为UNKNOWN
空值判断：使用IS NULL或IS NOT NULL
1
2
3
SELECT *
FROM S
WHERE SD IS NULL;
在WHERE和HAVING子句中，只有使结果为TRUE的元组才会输出

嵌入式SQL

SQL有哪些使用方式？

嵌入式SQL的意义
- 把SQL语句嵌入到高级语言中
- 把SQL的最佳特性与程序设计语言中的最佳特性（如过程处理能力）结合起来，使SQL功能更强，灵活性更强
嵌入式SQL与高级语言区别
- 在SQL语句前加前缀（如EXEC SQL），区分SQL语句与主语言语句
- 需要通过游标遍历SQL产生的集合，对齐颗粒度
- 通过主变量（主语言程序变量）交换数据
嵌入式SQL的处理
- 对嵌入式SQL，DBMS需要进行预编译进行处理
  - DBMS需要将SQL语句翻译成高级语言源码，然后按主语言的通常方式进行编译、连接
  - 优点：执行效率高
  - 缺点：可移植性差
    - ODBC（Open Database Connectivity）
      由微软设计，便于数据库实现共同API，便于移植
    - JDBC（Java Database Connectivity）
      由Oracle设计，是Java的数据库访问标准
- 动态SQL允许程序在运行过程中“临时”组装SQL语句

第四章数据库保护

数据完整性控制是为了防止数据库中存在不符合语义的数据，防止错误信息的输入和输出

数据安全性控制是保护数据库防止恶意的破坏和非法存取

安全性措施的防范对象是非法用户和非法操作，完整性措施的防范对象是不合语义的数据

数据库安全性控制

数据库中的数据会有哪些安全威胁，如何进行安全保护？

数据库安全性控制含义

数据库的安全性：保护数据库以防止不合法的使用所造成的数据泄漏、更改和破坏
- 向授权用户提供可靠的信息服务
- 拒绝对数据的非授权存取访问请求，保证数据的可用性、完整性和一致性，进而保护数据库所有者和使用者的合法权益
作用
- 保护数据库防止恶意的破坏和非法存取
计算机系统安全模型
1
2
graph LR
A[用户/应用程序]---B[DBMS]---C[OS&Network]---D[DB]
- 用户/应用程序：用户标识和认证
- DBMS：存取控制、审计
- OS&Network：操作系统与网络安全
- DB：数据加密

数据库安全性控制方法

用户标识与认证
- 数据库提供的最外层安全保护方法
- 标识是指系统采用一定的方式标识其用户或应用程序的名字或身份
- 认证是指系统在用户或应用程序登录时判断其是否为合法的授权用户
- 常用实现方式：用户名和口令

存取控制

确保合法用户按照指定权限使用DBMS和访问数据
包含用户权限定义和合法权限检查两部分，这两部分组成DBMS的安全子系统

自主存取控制（discretionary access control，DAC)

根据预先定义的用户权限进行存取控制，用户权限是指用户对数据对象允许执行的操作类型，由数据对象和操作类型两个要素组成；用户间可以授予权限

示例

	数据对象	操作类型
模式	模式	建立、修改、检索
模式	内模式	建立、修改、检索
模式	外模式	建立、修改、检索
数据	表	检索、插入、删除、修改
数据	属性列	检索、插入、删除、修改

一般使用基于角色的存取控制（RBAC）
- 用户级权限，用户对整个数据库权限的限定，与数据库中具体关系无关
- 关系级权限，用户使用关系和视图权限的限定
- 授予权限：Grant
- 取消权限：Revoke

强制存取方法（mandatory access control， MAC)
- MAC机制对比主体和客体的Label，最终确定主体是否能够存取客体
  - 仅当主体的许可证级别大于或等于客体的密级时，该主体才能读取相应的客体
  - 仅当主体的许可证级别等于客体的密级时，该主体才能写相应的客体

其它方法
- 视图
  为不同用户定义不同视图，将用户访问限制在一定范围内
- 审计
  将用户对数据库的所有操作自动记录下来放入审计日志中
- 数据加密
  防止数据库中数据在存储和传输中失密

可信计算机系统评测标准

目前大部分数据库系统处于C等级防护

标准
- TCSEC（Trusted Computer System Evaluation Criteria)，1985，美国国防部制定，可信计算机标准
- TDI（Trusted Database Interpretation），1991，美国国家计算机安全中心制定，数据库标准

数据库完整性控制

如何保证数据库中数据的正确、有效和一致性？

数据完整性含义

数据完整性：指数据的正确性和相容性
- 正确性：数据应具有合法的类型，并在有效的取值范围之内
- 相容性：指同一对象在不同关系中的数据是符合逻辑的
作用
- 防止数据库中存在不符合语义的数据，防止错误信息的输入和输出

完整性约束条件

定义：施加在数据库数据之上的语义约束条件
作用对象可以是列、元组、关系
包含实体完整性、参照完整性、用户自定义完整性
静态约束
- 数据库在每一确定状态必须满足的约束，是反映数据库状态合理性的约束
- 包含静态列级约束、静态元组约束、静态关系约束
动态约束
- 数据库在数据转变时必须满足的约束，是反映数据库状态变迁的约束
- 包含动态列级约束、动态元组约束、动态关系约束

完整性控制

功能
- 定义功能
  提供定义完整性约束条件的机制
- 检查功能
  检查用户发出的操作请求是否违背了完整性约束条件
- 违约响应
  若违背了完整性约束条件，则采取一定措施来保证数据的完整性
完整性检查时机
- 立即执行约束：在一条语句执行完后立即进行完整性约束的检查
- 延迟执行约束：在整个用户事务执行完毕后，再进行完整性约束的检查
完整性规则形式定义：(D, O, A, C, P)
- D ( Data ) 约束所作用的数据对象
- O ( Operation ) 触发完整性检查的数据库操作
- A ( Assertion ) 数据对象必须满足的断言或语义约束
- C ( Condition ) 选择A作用的数据对象值的谓词
- P ( Procedure ) 违反完整性规则时触发的过程

第五章关系数据理论

什么样的关系是好关系？没有插入异常、删除异常、数据冗余
1
2
3
4
5
6
7
8
9
10
11
graph RL
A[关系的规范化]
B[关系数据理论]
C[规范化方法：模式分解]
D[关系模式规范标准：范式]
E[数据依赖：函数依赖/多值依赖]
E-->D-->C
E-.->B
D-.->B
C-.->B
B--指导-->A
todo：

多值依赖和4NF部分有未完成事宜

无损分解判定算法有未完成事宜

候选码求解算法有未完成事宜

函数依赖

定义

X–>Y：有属性X和Y，若对于X的每个具体值，Y有唯一的值与之对应，则称“X函数确定Y”或“Y函数依赖于X”
平凡的函数依赖：X–>Y，且$Y\subseteq X$
非平凡的函数依赖：X–>Y，且$Y\nsubseteq X$
决定因素：X–>Y，则X为决定因素
类型：1:1、1:m、n:m

三种函数依赖

完全函数依赖：若X–>Y，且X的任意真子集都无法确定Y，则Y对X完全函数依赖，记作$X\overset{f}\rightarrow Y$
部分函数依赖：若X–>Y，且存在X真子集确定Y，则Y对X部分函数依赖，记作$X\overset{p}\rightarrow Y$
传递函数依赖：若X–>Y，Y–>Z，且Y无法确定X，则Z对X传递函数依赖，记作$X\overset{t}\rightarrow Z$

函数依赖公理系统

有属性集合X和Y，若从F的函数依赖能推出$X\rightarrow Y$，则称F逻辑蕴含$X\rightarrow Y$
$F$的闭包记作$F^+$
Armstrong公理系统
- 自反律：若$Y\subseteq X$，则$X\rightarrow Y$
- 增广率：若$X\rightarrow Y$，则$XZ\rightarrow YZ$
- 传递率：若$X\rightarrow Y,\ Y\rightarrow Z$，则$X\rightarrow Z$
Armstrong公理推论
- 合并规则：若$X\rightarrow Y,\ X\rightarrow Z$，则$X\rightarrow YZ$
- 伪传递规则：若$X\rightarrow Y,\ WY\rightarrow Z$，则$WX\rightarrow YZ$
- 分解规则：若$X\rightarrow Y,\ Z\subseteq Y$，则$X\rightarrow Z$
- 由合并规则和分解规则可推出如下定理
  - $X\rightarrow A_1, A_2…A_k$成立，与$X\rightarrow A_i(i=1,2,…,k)$等价，X能推出A的任意子集
属性集的闭包
- 定义：属性集X关于函数依赖集F的闭包
- 定理：若$X\rightarrow Y$能从Armstrong公理系统推出，则$Y\subseteq X_F^+$
Armstrong公理系统的有效性与完备性
- 有效性
  - 指由F出发根据Armstrong公理推导出来的每个函数依赖一定在F所蕴含的函数依赖的全体之中
  - 有效性由Armstrong公理系统的正确性证明
- 完备性
  - F所蕴含的函数依赖的全体中的每一个函数依赖，必定可以由F根据Armstrong公理导出
  - 证明：使用两个特殊元组t，s辅助证明
函数依赖集等价与覆盖
- 若$F^+=G^+$，则称F+与G+等价
- 若$F^+=G^+$，则$F\subseteq G^+$、$G\subseteq F^+$，称F覆盖G，同时G覆盖F
函数依赖集的最小依赖集
- 要求
  - 右部为单属性
  - 没有多余的函数依赖（Functional Dependency，FD）
  - 每个FD左部没有多余属性
- 极小化方法
  1. 用右部单属性推导式替代右部集合推导式
  2. 检查所有FD，删去所有多余项
  3. 检查所有FD，删去所有多余左部属性
  4. 重复以上步骤若干次

规范化

发展过程：

1971-1972：CODD系统提出1NF，2NF，3NF的概念

1974：CODD 和BOYCE提出BCNF

1976：FAGIN 提出4NF，后来又提出了“投影-连接范式” PJNF，也称 5NF

范式间关系：
$1NF\subset2NF\subset3NF\subset BCNF\subset4NF\subset5NF$

范式概念（1NF）

如果某个关系满足某个指定的约束集，则称它属于某种范式（Normal Form）
1NF
- 最低要求
- 定义：一个关系只包含原子值
- 满足1NF的称为规范化关系，简称范式
规范化：一个低一级范式的关系模式，通过模式分解转换为若干个高级范式的关系模式的集合的过程

与函数依赖相关的范式（2NF, 3NF, BCNF）

2NF
- 定义：$R\in 1NF$，且每个非主属性完全依赖于码（主属性可以部分依赖于码）
- 既要依赖于主键，又不能仅仅依赖码的一部分
- 规范化：用画图法从1NF中消除非主属性对码的部分函数依赖
- 插入异常依然存在；删除异常会导致连锁信息被删除；数据冗余得到一定改善
3NF
- 定义：$R\in2NF$，且每个非主属性不传递依赖于R的任何码
- 所有的异常都消失了（表面上）
BCNF
- 当某些特定情况发生时，3NF可能依然存在各种异常
- 定义
  - $R\in 1NF$，对所有X–>Y，且$Y\nsubseteq X$时，都有X含有码
- 性质
  - 所有属性都完全函数依赖于（不包含该属性的）候选码
  - 没有任何属性完全函数依赖于非码的任何一组属性

多值依赖与第四范式

函数依赖反应了现实世界实体间的相互约束

现实世界实体间还有其它约束：

多值依赖

连接依赖

分层依赖

相互依赖

多值依赖

定义
- 若对于X，Y，Z（其中Z=U-X-Y），Y的值决定于X的值，且与Z值无关，则称多值依赖X–>–>Y成立
- 也即：当X确定了，Y和Z都可以有被X决定的多个值，但它们之间是相互独立的

4NF

模式分解的理论

模式分解的定义

若$F_i={X\rightarrow Y\mid X\rightarrow Y\in F^+\ \and\ XY\subseteq U_i}$，则称Fi为F在Ui上的投影
关系模式R<U, F>的一个分解${R_1<U_1,F_1>,R_2<U_2, F_2>,…,R_n<U_n,F_n>}$，其中$U=\Sigma U_i$

分解的无损连接性

定义
- 对于关系模式R<U, F>的分解，r为R中任何一个关系，若将分解中所有属于r的部分连接，仍能得到r，则称该分解为无损分解，具有无损连接性
判定算法
- 仅分解为两部分时的判断算法：R1， R2的共同属性至少构成 R1、R2 二者之一的侯选码，则为无损连接

分解的保持函数依赖性

定义
- 若$F+=(\Sigma F_i)+$，则称分解保持函数依赖
判定算法
- 计算$(\Sigma F_i)+$，验证F的每一条依赖是否在$(\Sigma F_i)+$中

模式分解的原则

具有无损连接性
保持函数依赖

模式分解的算法

达到3NF且保持函数依赖的分解算法
达到3NF且同时保持无损连接与函数依赖的分解算法
达到BCNF无损连接分解算法

候选码的求解和算法

快速求解候选码的充分条件

左边为单属性的函数依赖集候选码成员的图论判定方法

多属性依赖集候选码求解法

第六章数据库设计

数据库设计方法概述

数据库设计的任务是什么？

数据库设计中的难点是什么，采用怎样的设计方法解决？

数据库设计

定义
- 对于一个给定的应用环境，设计优化的数据库逻辑结构和物理结构，建立数据库，使之能够有效地存储数据，为开发满足用户需求的应用系统奠定基础
特点
- 要把数据设计和处理设计密切结合起来
- 与硬件、软件和管理紧密相关

手工试凑法

根据应用的数据要求与处理要求，直接设计数据库的结构
缺点
- 数据间关系复杂，使用要求各式各样，很难仅凭经验进行设计
- 用户需求一旦改变，难以改变数据结构设计
- 数据库设计和DBMS绑定，难以移植
- 难以多人合作；难以交流分享设计

规范设计法

运用软件工程的思想和方法，把整个设计过程划分为若干阶段，把复杂的大问题分为若干相对简单的小问题，每个阶段只解决整个设计中的部分问题
迭代和逐步求精的过程
步骤
- 需求分析
- 概念结构设计
- 逻辑结构设计
- 物理结构设计
- 数据库实施
- 数据库运行和维护

数据库设计的需求分析

怎样进行数据库设计的需求分析？

需求分析的目标

处理要求：指用户要完成什么处理功能，对处理的响应时间和处理方式的要求
信息要求：指系统中所涉及的数据及数据之间的联系，具体收集数据的名称、类型、长度等，确定数据之间联系的类型
安全性和完整性的要求

需求分析的方法

调查用户实际要求，与用户达成共识
分析、表达用户的需求
- 用数据流图表达数据和处理之间的关系
- 用数据字典描述系统中各类数据

数据库概念结构设计

如何利用E-R法进行应用系统的概念模型设计？

局部E-R图设计
综合分E-R图形成总E-R图
- 解决冲突，将各分E-R图合并起来生成初步E-R图
  - 冲突主要包括属性冲突、命名冲突、结构冲突
  - 属性冲突：属性的类型、取值范围或取值集合不同，或属性取值单位冲突——讨论协商解决
  - 命名冲突：包括属性名、实体名、联系名之间的同名异义，异名同义——建立命名表，统一命名
  - 结构冲突：
    - 同一对象在不同应用中有不同抽象；如在一应用中为实体，在另一应用中为属性——把属性变为实体或实体变为属性
    - 同一实体在不同分E-R图中属性个数、次序不同——属性求并，再适当调整次序
    - 实体之间的联系在不同分E-R图中呈现不同类型———根据语义加以综合或调整
- 消除不必要的冗余，生成基本E-R图
  - 初步E-R图可能存在冗余的联系和冗余的关系
  - 分析法
  - 规范化方法
    1. 将各种关系依赖转化为码之间的函数依赖
    2. 进行极小化处理
    3. 考察每一个在极小集中消失的函数依赖，确定是否为冗余

数据库逻辑结构设计

数据库的逻辑结构设计的主要内容是什么？

E-R图向关系模型的转换
- 将实体型、联系和多元联系，每个转换为一个关系模式
- 具有相同码的关系可以合并
- 对于实体型：实体的属性就是关系的属性，实体的码就是关系的码
- 对于联系：联系相连的属性的码以及联系的属性为关系的属性，候选码根据各实体的码组合决定
- 对于弱实体类型：创建一个新的关系，新关系主码为被依赖关系的主码和弱实体类型的码，属性为弱实体类型所有的属性
- 对于超类/子类联系：为超类和子类分别创建关系，超类关系包含所有子类均有的属性，以及一个子类判定码；子类关系包含超类的码和子类的属性
关系模型的规范化和优化
- 规范化
  - 按照数据依赖的理论，确定关系模型的范式等级
- 优化
  - 按系统的处理要求，确定是否进行模式合并或分解
  - 可以对关系模式进行必要的分解
    - 水平分解：将关系的元组分为若干子集合，每个集合为一个子关系，以提高系统效率
      - 二八原则：将经常使用的数据分解出来作为一个关系，其它数据作为另一个关系
    - 垂直分解：将关系模式的属性分解为若干子集合，形成若干子关系模式
      - 原则：经常在一起使用的属性从R中分解出来的形成一子关系模式
      - 垂直分解必须保证无损连接性
设计用户子模式
- 根据局部应用的需求，结合具体DBMS的特点，设计用户外模式
  - 列更符合用户习惯
  - 对不同级别的用户定义不用的视图，保证系统的安全性
  - 降低复杂查询的难度，简化使用

数据库物理结构设计

数据库的物理结构设计的主要内容是什么？

物理结构包括数据在物理设备上的存储结构与存取方法
存储结构
- 存放位置
  - 经常存取部分和存取频率较低部分分开存放
  - 数据和日志备份放于不同的磁盘上
- 系统配置
  - 配置变量、存储分配参数、进行物理优化
存取方法
- 索引
  - 包含索引记录/索引项
  - 索引记录必须有序
  - 索引并非越多越好
- 聚集
  - 将关系中某个属性（组）相同的记录存放在连续的物理块中，提高该属性的查询速度
  - 一个关系只能参加一个聚集
  - 经常进行连接操作的关系可以建立聚集
  - 建立和维护聚集系统开销很大，对于更新操作多于连接操作的关系不应该使用聚集
- hash
  - 通过hash将关键字转化为地址
  - 使用hash无法加速区间查询方法
  - 一般要求关系的大小可与之，而且不变
  - 如果关系大小动态改变，则需要dbms提供动态hash存取方法

第七章存储管理和索引

总的来说，这章内容在CO和OS讲过一遍了（大概

物理存储系统

DBMS如何在磁盘上以文件形式存储数据？

存储分级

内存：cpu，内存DRAM
外存：固态硬盘SSD，机械硬盘HDD，网盘Network Storage
数据只有放入内存才能被处理
DBMS设定数据库的基本存储在磁盘上，DBMS管理内存和外存的数据交换
DBMS目标：最小化磁盘的主存键传输存储块的数量，即最小化磁盘存取次数

磁盘

架构：盘片-磁道-扇区
时间：寻道时间+旋转时间+传输时间

数据存储结构

DBMS如何在磁盘上以文件形式存储数据？

概述

数据库的表映射到文件
文件被组织为记录的序列，记录被映射到磁盘块上
文件由若干磁盘块构成，块是存储分配和数据传输的单位
一个块可以包含几个记录，每条记录被完全包含在单个块中

文件的磁盘块分配

连续分配：文件在块中连续存放
连接分配：数据块中包含下个数据块的指针
按簇分配：簇是连续的几个磁盘块，簇之间指针连接
索引分配：索引块中存放指向数据块的指针

数据库块/页

每个页由头部header和数据构成
header包含了页中数据的元数据，例如：
- 页大小
- checksum
- dbms版本
分槽（slot）页结构
- Header中记录了已经使用的槽数，以及最后一个被用槽的偏移量，以及一个槽数组
- 槽数据记录的每个元组的偏移量
- 槽数组从开始向尾部增长，记录元组从尾部向开始增长，二者相遇被认为页满
- 便于存储变长记录
记录（tuple）结构
- 记录是字节序列，DBMS负责将其解释为属性类型和值
  - 记录头部：元组的元数据，例如加锁信息
  - 记录数据：属性的实际数据，不能超过一个页
  - 唯一标识符ID

graph LR
A[文件]
B[页]
C[Header]
D[Slot]
E[Tuple]
A-->B-->C
B-->D-->E
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146

### 缓冲区管理	

> DBMS如何管理内存，以及从磁盘读写文件？
>
> 这里的缓冲区，真的不是缓存吗？
>
> 脑袋好痒，感觉又听了一遍计组

* 缓冲区：主存中可以存储磁盘块副本的区域
* 缓冲区管理区：缓存空间分配，内外存交换
* 交换单位：块/页
* 目标：最小化交换的块/页数
* 页表、策略......

### 索引

> DBMS如何提高数据访问效率？有哪些类型的索引，它们是如何构造的？

#### 基本概念

* 构成

  * **索引域（搜索码）**：存储数据文件的属性组
  * **指引**：指向记录在磁盘块的位置

* 索引对部分属性进行了组织或排序，且大小比原记录小得多，利用DBMS快速有效访问

* DBMS负责在执行查询时使用最恰当的索引

* 分类

  * 排序索引 vs. 哈希索引
    * 字如其名~
  * 聚集索引 vs. 非聚集索引
    * 聚集索引：索引排列顺序和记录一致，又被称为**主索引**（Primary Index）
    * 非聚集索引：索引顺序和记录不一致，又被称为**辅助索引**（Secondary Index）
  * 稠密索引 vs. 稀疏索引
    * 稠密索引：对于文件中每个搜索码都有索引项与其对应
    * 稀疏索引：只有部分索引域有索引项，索引大小小，但查询慢；非聚集索引都是稀疏索引

* 多级索引

  > 索引文件可能过大，所以需要多级索引以减小空间大小

  * 二叉树索引：排列方式和二叉堆相同
  * 多枝树索引：同一节点有多个关键字值的情况时使用
  * B树
  * B+树
  * 哈希索引

## 第八章 查询处理与查询优化

> 关系查询处理的四个阶段：
>
> * 查询分析
> * 查询检查
> * 查询优化
> * 查询执行
>
> 查询时间的主要影响因素：IO次数

### 查询处理过程

> 从接收到SQL查询语句到语句执行，需要做哪些处理？

#### 关系查询处理步骤

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

#### 查询代价的度量

* 影响因素：磁盘访问，CPU, 网络通信等
* 从磁盘访问数据的**I/O代价**通常是最重要的代价
* 使用访问磁盘的块数作为估计代价的因素

### 查询操作的实现

> 选取、连接等操作是如何实现的？

#### 选择运算实现算法

* 全表扫描法
  * 按照物理顺序读表的块到内存，检查每个元组，直到所有块都接受检查
* 索引扫描法
  * 先通过索引项找到目标索引项，再通过索引项找到元组

#### 连接运算实现算法

* 嵌套—循环法
  * 两个表，一个为外循环，一个为内循环
  * 需要检查每一种元组组合，代价高
  * 元组较多的为外层关系
* 索引嵌套—循环法
  * 如果内层关系有索引，则可以用其索引加速连接查询过程
  * 如果内外都有索引，则用元组较少的关系作为外层关系
* 排序—合并法
  * 将两个关系在连接属性上排序
  * 用类似two pointers的方法遍历两个关系一遍
  * 只能用于等值连接或自然连接
* 哈希连接法
  * 将两表的连接属性映射到一个集合上，只在集合的同一个元组中遍历查找连接项
  * 只能用于等值连接或自然连接

#### 排序算法

* 快速排序：内存中可以完全容纳关系时使用
* 外排序-归并
  1. 简历多个排好序的归并段（run），仅包含关系的部分记录
  2. 对归并段进行排序

#### 其它算法

* 去重：使重复数据相邻，再删除
  * 排序
  * 哈希
* 投影：在每个元组上投影，再去重
* 并差交
  * 类似排序-合并法
  * 或类似hash法


#### 表达式的执行

* 物化（Materialized）
  * 按次序每次执行一个运算，并将结果保存为一个临时关系，写入磁盘
  * 适用性广泛，但临时表的写和读代价大
* 流水线（Pipeline）
  * 将运算过程整理为一个运算树
  * 同时执行多个运算，将结果传递给下一个运算
  * 不需要在磁盘存储临时关系
  * 对于一些操作不适用，比如排序

### 查询优化

> 查询优化的目标是什么？如何进行优化？

#### 查询优化的必要性

```sql
SELECT SN
FROM S, SC
WHERE S.S# = SC.S# AND C#=’02’;

该sql在好的查询语句和坏的查询语句下表现可能相差10^4倍！！！

查询优化的目标

选择一个高效执行的查询处理策略，使得查询代价最小，即访问磁盘的块数最少

查询优化方法

查询计划：定义了每个操作的算法以及这些操作执行的顺序

查询的代数优化
- 关系代数表达式的优化，即按照一定的规则，改变代数表达式中操作的次序和组合
- 启发式优化规则
  - 选择运算尽早执行（减小中间关系——减少元组数据）
  - 投影运算尽早执行（减小中间关系——减少属性数目）
  - 把投影运算和选择运算同时进行；把投影同其前或其后的双目运算结合起来（减少扫描关系的次数）
  - 把某些选择同在它前面要执行的笛卡尔积结合起来成为一个连接运算（把笛卡尔积与选择转换为连接）
  - 找出公共子表达式，把公共子表达式的结果写入中间文件，重复使用（中间结果复用）
- 关系代数表达式等价变换规则
  - 共十一条
    ~~因为打赌不会考这个所以没有记录（理直气壮）~~
查询的物理优化
- 存取路径和底层操作算法的选择，包括基于规则或基于代价等
- 常用方法
  - 基于规则的启发式优化方法
  - 基于代价估算的优化方法
  - 两者结合的优化方法

查询优化的一般步骤

把查询转换成语法树，如关系代数语法树（查询树）
把查询树利用代数优化转换成优化后的标准形式
利用基于启发式规则的物理优化，选择底层的操作算法与存取路径，生成查询计划；利用基于代价的物理优化，选择代价最小的

第九章事务处理技术

事务是数据库恢复和并发控制的基本单位

事务的概念

在数据库系统运行过程中，有哪些情况可能造成数据丢失、错误或不一致？

什么是事务？事务有哪些特性？事务的实现机制有哪些？

事务的特性

ACID

原子性（Atomicity）：由恢复技术实现
一致性（Consistency）：由原子性保证
隔离性（Isolation）：由并发控制实现
持久性（Durability）：由恢复技术实现

事务的特性遭破坏的情况

多个事务并发运行时，不同事务的操作交叉进行
事务在运行过程中被强行停止

数据库恢复技术

如何将数据库从各种故障中恢复？

概述

将数据库从错误状态回复到已知正确状态
通过数据库管理系统的恢复子系统完成

故障的种类

事务内部的故障
- 人工对数据库进行回滚
- 死锁、运算溢出等
系统故障
- 硬件错误、操作系统故障、掉电等
- 会使事务异常终止，不会破坏数据
介质故障
- 硬盘损坏
- 破坏数据库，影响相关事务
计算机病毒
- 对数据进行非法修改
- 基本不在考虑范围内

恢复的实现技术

核心思想：UNDO未完成的事务，REDO已完成的事务

故障对数据库系统的影响
1. 数据本身被破坏
2. 数据本身没有问题
恢复原理：冗余
关键问题
- 如何建立冗余
- 如何通过冗余实施数据库恢复
数据转储的两种状态
- 静态转储
  - 系统中无事务运行时进行的转储操作，并且转储过程中，不允许对数据库进行任何存取、修改
  - 优点：保证副本的数据一致性
  - 缺点：由于转储必须等待正在运行的事务结束才能开始，而新的事务必须等待转储结束才能执行，降低了数据库的可用性
- 动态转储
  - 转储期间允许对数据库进行存取或修改
  - 优点：不影响数据库的可用性
  - 缺点：不能保证副本上的数据正确、有效，还必须把转储期间各事务对数据库的修改记录下来，建立日志文件
数据转储的两种方式
- 海量转储
  - 每次存储全部数据库
- 增量转储
  - 只存储上次更新的内容
日志文件的建立和使用
- 记录事务对数据库的操作
- 分为以记录为单位和以数据块为单位
- 必须先写日志文件，后写数据库
- 遇到事务故障和系统故障时，撤销事务，根据转储类型恢复数据
UNDO
- 反向扫描日志文件，查找事务的更新操作
- 对更新操作执行逆操作，直到遇到该事务的开始标志为止
检查点
- 纯日志恢复技术的缺点
  - 搜索耗费时间多
  - 不必要重做某些事务
- 检查点技术可以改善效率，使得检查点前的事务不必重做
- 新增重新开始文件，动态维护检查点
- 恢复步骤
  - 将检查点时的事务放入UNDO列表
  - 从检查点开始正向扫描日志，将开始的事务放入UNDO，结束的事务放入REDO
  - UNDOUNDO的，REDOREDO的

并发控制技术

并发控制的基本思想与主要方法是什么？如何保证并发事务调度的正确性？

概述

并发控制优点
- 提高系统吞吐量
- 减少平均相应时间
问题
- 如果控制不当，会对数据一致性带来问题
具体问题种类
- 丢失更新（Lost Update）
- “脏”数据的读出（Dirty Read）
- 不可重复读（Non-Repeatable Read）

并发控制主要方法

采用封锁机制，合理调度并发事务，避免并发事务间的互相干扰造成数据的不一致
封锁的类型
- 排它锁（X锁）：不可读不可写
- 共享锁（S锁）：可读不可写
- t1\t2 X S
  
  X N N
  
  S N Y
一级封锁协议——防止丢失更新
- 事务在修改数据前必须对其加X锁，直到事务结束
- 防止丢失修改，不能保证可重复读和不读“脏”数据
二级封锁协议——防止读脏数据
- 一级封锁协议+事务在读取数据前必须加S锁，直到读取结束
- 防止读“脏”数据，不能保证重复读
三级封锁协议——防止不可重复度
- 一级封锁协议+事务在读取数据前必须加S锁，直到事务结束
- 防止重复读
封锁粒度：封锁对象的大小
- 粒度大，并发性低，封锁机构简单，开销小
- 粒度小，并发性高，封锁机构复杂，开销大
多粒度封锁协议
- 多粒度树中每个结点可以被独立地加锁，覆盖所有子节点
- 显式封锁是当前结点被直接加锁
- 隐式封锁是当前节点的先祖被加锁导致当前结点加锁
- 意向锁
  - 对任意节点加锁时，必须先对其上级节点加意向锁
  - 在后续加锁时，不需要额外检查下级节点的封锁，只需检查对象和它的上级结点
  - 三种意向锁
    - 意向共享锁 IS
    - 意向排它锁 IX
    - 意向共享排它锁 SIX （先加S，再加IX）
  - t1\t2 S X IS IX SIX
    
    S Y N Y N N
    
    X N N N N N
    
    IS Y N Y Y Y
    
    IX N N Y Y N
    
    SIX N N Y N N

t1\t2	X	S
X	N	N
S	N	Y

t1\t2	S	X	IS	IX	SIX
S	Y	N	Y	N	N
X	N	N	N	N	N
IS	Y	N	Y	Y	Y
IX	N	N	Y	Y	N
SIX	N	N	Y	N	N

活锁和死锁

CO还在追我

解决死锁的办法
- 预防死锁
- 死锁检测和解除
预防死锁
- 一次封锁法
- 顺序封锁法
死锁检测
- 超时法
- 等待图法
死锁恢复
- 选择一个处理死锁代价最小的事务，将其撤销

事务可串行化调度

定义
- 多个事务的并发执行是正确的，当且仅当其结果与按某一次序串行执行它们时的结果相同，我们称这种调度策略为可串行化调度
- 一个给定的并发调度，当且仅当它是可串行化的，才认为是正确调度
两段锁协议（Two-phase Locking）
- 事务分为两个阶段，第一个阶段是获得封锁，也称为扩展阶段；第二个阶段是释放封锁，也称为收缩阶段
- 在对任何数据进行读、写操作之前，事务首先要获得对该数据的封锁
- 在释放一个封锁之后，事务不再获得任何其它封锁
执行两段锁协议的事务一定是可串行化调度的，但仍可能发生死锁

其它并发控制方法

事务隔离级别
悲观与乐观并发控制技术
多版本并发控制技术

第十章数据库技术新发展

终于结束啦~~让我们来听听数据库的“新”技术

概述

数据库技术有哪些新的发展方向？

SQL

传统关系型数据库，支持SQL操作、事务ACID特性
几千用户，TB级数据

NoSQL

Not only SQL，非关系型的数据库，水平可扩展、分布式
不使用SQL，不支持事务的ACID操作
HBase、MongoDB等

NewSQL

新的可扩展/高性能数据库
不仅具有NoSQL的海量数据存储管理能力，还保持了传统数据库支持ACID和SQL等特性
华为云数据库GaussDB，VoltDB，OceanBase等

分布式数据库概念与技术

什么是分布式数据库系统，分布式数据库的体系结构以及实现技术是怎样的？

分布式数据库系统基本概念

分布式数据库系统定义
- 分布式数据库是由一组分布在计算机网络的不同结点上的数据组成，每个结点具有独立处理的能力（称为场地自治），可以执行局部应用，同时每个结点也能通过网络通信支持全局应用
  - 局部应用：只操作一个结点上数据库的应用
  - 全局应用：操作两个或两个以上节点上数据库的应用
- 分布性— 数据分布存储在网络的各个节点上
- 逻辑上的整体性—数据被一种机制联系在一起，构成一个有机整体
- 分布式数据库以“数据分布”为前提，强调场地自治性（局部应用）以及自治场地之间的协作性（全局应用），两者缺一不可
  - 场地自治性：每个场地有自己的数据库、一组终端、运行局部DBMS，是独立的DBS，具有高度自治性
  - 自治场地之间的协作性：各结点组成整体，从用户角度看，分布式数据库系统逻辑上如同一个集中式数据库一样，用户可以在任何场地执行全局应用
分布式数据库系统的特点
- 数据独立性
  - 数据的逻辑独立性和物理独立性
  - 数据的分布独立性
    - 数据的逻辑分片、数据物理位置分布的细节、重复副本（冗余数据）一致性问题、局部结点上的数据模型等与用户程序无关
集中与自治相结合的控制结构
适当增加数据冗余
- 提高系统的可靠性、可用性
- 提高系统性能
- 不利于更新，增加了系统维护代价
- 全局的一致性、可串行性和可恢复性

分布式数据库系统体系结构

整体结构

graph TB
A[全局外模式1]
B[全局外模式2]
C[全局概念模式]
D[分片模式]
E[分布模式]
F[局部概念模式1]
G[局部内模式1]
H[局部DB1]
I[局部概念模式2]
J[局部内模式2]
K[局部DB2]
A---C
B---C
C---D---E
E---F
E---I
F---G---H
I---J---K

分布透明性
- 分片透明性
- 位置透明性
- 局部数据模型透明性

分布式数据库系统主要技术

分布式查询处理和优化
分布事务管理

云数据库

什么是云数据库，其架构是怎样的？

云数据库
- 概述
  - 云服务提供商建立计算、存储与网络资源池，基于这些资源池提供基础设施、平台和软件服务
  - 用户可按需按量购买和使用云服务提供的各种服务
- 挑战和机遇
  - 如何更好的将云的底层资源池化、资源解耦优势发挥出来，支撑用户建立高可用、可拓展性、弹性的数据库系统
- 数据库服务DataBase-as-a-Service，DBaaS
  - 云数据库服务
    - 一主多从
  - 云原生数据库技术
    - 计算存储分离
    - 计算节点无状态
    - 存储集群灵巧化
原生分布式数据库
- 由多个同构型的数据库节点组成
- 每个节点都具备分布式处理的能力
- 相互连接组合形成面向用户的单个数据库