- 刚踏足职场,牢固技术功底对我们未来走得多远尤为重要。然而当今工作环境迫使我们 “沉迷” 追逐新概念、新技术,比如机器学习、大数据技术等,难免内心难免会浮躁不安,有时候走得太快反而淡忘了软工知识体系正是当初上学时期指导我们认识软件世界的重要角色。正如设计模式给我们启示,认知不应依赖于具象,而是抽象概念指导认识,学习应是如此,不随波逐流,巩固根基知识更容易让自我渐入一个熵减过程。
- 软件设计师(中级)所考查的内容正是软件工程体系知识树的缩影,很庆幸能借此机会温故知新,同时复习过程以笔记形式记录在案,即知识输入到输出全过程,以构建起属于自己的计算机科学知识体系。
- 最后声明一点,知识复盘固然重要,但考试终究要刷题练习。希望笔记内容能帮到有同样备考需要的朋友,若笔记有错误之处,还请您不吝赐教、指正。
备考调研
报名信息
- 考试名称:计算机技术与软件专业技术资格 (水平) 考试
- 考纲范围:百度百科 - 考试要求
- 报名时间:第二季度(2-4 月);第四季度(7-9 月)
- 考试时间:第二季度(5 月);第四季度(11 月)
- 单科满分:
75分
;合格分数:45分
考试形式:
客观题
和主观题
,均为笔试
客观题讲究做题技巧,优先考虑排除法;主观题讲究标准解答,复习以真题为主。
考试科目:中级软考的科目名称
专业类别 专业类别 计算机软件 软件设计师 ✓
软件评测师
软件过程能力评估师计算机应用技术 多媒体应用设计师
嵌入式系统设计师
计算机辅助设计师
电子商务设计师信息系统 系统集成项目管理工程师
信息系统监理师
数据库系统工程师 ✓
信息系统管理工程师
信息安全工程师信息服务 计算机硬件工程师
信息技术支持工程师
参考资料
更新进度
- [ ] 计算机系统导论【※】
- [ ] 计算机系统基础
- [ ] 计算机体系结构
- [ ] 程序设计语言基础
- [ ] 程序设计语言
- [ ] 语言处理程序:汇编、编译、解释
[ ] 数据结构
- [ ] 线性结构
- [ ] 数组 / 矩阵 / 广义表
- [ ] 树
- [ ] 图
- [ ] 查找
- [ ] 静态查找表
- [ ] 动态查找表
- [ ] 哈希查找表
[ ] 排序:内部排序
基本类型 细分 插入排序 直接插入排序、折半插入排序、希尔排序 交换排序 冒泡排序、快速排序 选择排序 选择排序、堆排序 归并排序 -- 基数排序 --
[ ] 算法设计与分析
- [ ] 基本概念
- [ ] 算法分析
- [ ] 分治法
- [ ] 贪心法
- [ ] 回溯法
- [ ] 动态规划法
- [ ] 分支界限法
- [x] 操作系统【※】:进程管理、存储管理、磁盘管理
- [ ] 软件工程基础
- [ ] 概述
- [ ] 软件过程模型
- [ ] 需求分析
- [ ] 系统设计【※】
- [ ] 系统测试【※】
- [ ] 运行维护
- [ ] 软件项目管理【※】
- [ ] 软件质量
- [ ] 软件度量
[x] 面向对象技术【※】
[x] UML:类图、用例图、活动图、时序图、状态图
[x] 设计模式:六大设计原则、二十三种模式
[x] 数据库技术【※】:数据模型(E-R 模型、数据模型、关系模型)、关系代数、SQL、规范化、事务管理、并发控制
- [ ] 网络技术【※】
- [ ] 网络概述
- [ ] 网络互连硬件
- [ ] 网络协议标准
- [x] 标准化和软件知识产权【※】:标准化、软件知识产权(软件著作权、商业秘密权、专利权)
正文内容
计算机系统导论
中央处理单元
CPU 简化模型
CPU 简化模型
CPU 组成结构
CPU 基本组成结构
运算单元
- 算术逻辑单元 ALU:对数据的算术运算和逻辑运算。
累加寄存器 AC:为 ALU 提供一个工作区。
注意累加寄存器是通用寄存器之一。
数据缓冲寄存器 DR:CPU 与内存、外部设备之间的数据传送中转站。
- 状态条件寄存器 PSW:保存由算术指令和逻辑指令运行或测试的结果建立的各种条件码内容。
控制单元
- 指令寄存器 IR:当前执行的指令。
- 程序计数器 PC:下一条要执行的指令的地址。
- 地址寄存器 AR:保存当前 CPU 所访问的内存单元的地址。
- 指令译码器 ID:包含操作码与地址码两部分。
总线系统
- 一条总线系统同一时刻仅允许一个设备发送,但允许多个设备接口。
- 总线分类
- 数据总线:CPU 与 RAM 之间来回传送需要处理或存储的数据。
- 地址总线:指定在 RAM 之中存储的数据的地址。
- 控制总线:将微处理器控制单元的信号传送到周边设备。
- 总线的性能指标:带宽 = 位宽 / 工作频率
- 带宽:单位时间传送的数据总量,单位 B/s
- 位宽:数据总线的位数,单位 B
- 工作频率:单位时间振幅的频率,f = 1/t,单位 GHzz、MHz
- [例] 总线带宽为 32 bit,时钟频率为 200 MHz,若总线上每 5 个时钟周期传送一个 32 bit 字,则该总线的带宽为(B/s)?
- 总线带宽对齐: 32 bit / 8 bit = 4B
- 每个时钟周期: t = 1 / f = 1 / 200
- 该总线的带宽:4 / (5* 1/200) = 160 MB/s
数据库技术
基本概念
数据库管理系统(DBMS)的功能:
数据库定义语言(Data Definition Language, DDL)
- 外模式、概念模式和内模式的定义
- 数据库完整性定义
安全保密定义(口令、级别和存取权限)
这些定义存储在数据字典中。
数据库操纵语言(Data Manipulation Language, DML):对数据的基本操作(增删改查)
数据库管理系统的分类:
- 关系数据库系统:借助集合代数等概念及方法处理数据库中的数据。
- 面向对象的数据库系统
- 面向对象数据模型能完整描述现实世界的数据结构,能表达数据间的嵌套、递归联系
- 具有面向对象技术的封装、继承特性
- 对象关系数据库系统:在传统的关系数据库模型基础上,提供元组、数组、集合等更为丰富的数据类型以及其操作方法。
数据库系统的体系结构
- 客户端 / 服务器模式(C/S模式)
- 并行式:数据库系统是多个物理上连在一起的处理器(CPU)
- 分布式:数据库系统是多个地理分开的处理器(CPU)
数据库三级模式结构
- 外模式:又称用户模式,对应
用户级
,是某个或某几个用户所看到的数据库的数据视图,可利用 DML 对数据记录进行操作。 - 概念模式:又称逻辑模式,对应
概念级
,是数据库中全部数据的逻辑结构和特征的总体描述,并以数据库管理系统提供的 DDL 来描述定义。 内模式:又称存储模式,对应
物理级
,是数据库中全体数据的内部表示或底层描述。例如:记录的存储方式为顺序存储、B/B+ 树结构存储亦或是 Hash 存储;索引的组织方式;数据是否压缩等。
两级映像:保证数据库的数据具有较高的
逻辑独立性
和物理独立性
。- 外模式 / 模式映射:外部级与概念级之间。
模式 / 内模式映像:概念级与内部级之间。
为保证程序正确运作,物理结构 / 逻辑结构改变,需要修改对应模式之间映像。
特性 解释 物理独立性 数据库的内模式发生改变时,数据逻辑结构不变 逻辑独立性 用户应用程序与数据的逻辑结构是相互独立的
- 外模式:又称用户模式,对应
数据库系统体系结构示意图:
关系数据库的三级模式结构
数据模型
模型三要素
- 数据结构: 所研究的对象类型的集合。
- 数据操作:对数据库中各种对象的实例(值)允许执行的操作集合,包括操作及操作规则。
- 数据的约束条件:完整性规则的集合。
实体-联系模型(E-R 模型)
- 实体
联系
一对一(1:1):实体集 $E_1$ 与实体集 $E_2$ 集最多只有一个实体相联系。
任意选择一方,加入对方主键
一对多(1:n):实体集 $E_1$ 中一个实体与实体集 $E_2$ 中多个实体相联系。
多方加入对方主键
多对多(m:n):实体集 $E_1$ 中多个实体与实体集 $E_2$ 中多个实体相联系。
联系集中加入双方主键
属性
简单属性、复合属性
简单属性是原子的、不可再分
单值属性、多值属性
姓名 — 单值属性;男/女 — 多值属性
NULL 值:表示无意义或者不知道。
- 派生属性:可从其他属性得到。例如,
工作年限
可以从参加工作时间
计算而得。
E-R 图中主要构件
E-R 图中主要构件
扩充的 E-R 模型
弱实体:一个实体的存在必须以另一个实体为前提。
例如:某职工的家属,某家属是属于某职工的。
特殊化:实体集具有相同的属性,但实体集可按照某些特征区分为几个子实体。
例如:学生实体集可区分为:博士生、研究生、本科生、大专生等。
数据模型
层次模型:树型结构表示数据间的联系。在层次模型中,每一结点表示一个记录类型(实体),记录之间的联系用结点之间的连线表示,并且除根节点以外其他结点有且仅有一个双亲结点。
层次模型
网状模型:层次模型的特例,即去掉层次结构的限制,允许两个结点之间有多种联系(复合联系)。
关系模型:使用表格结构表达实体以及实体集之间的联系。
- S(Sno, Sname, SD, Sage, Sex):学生S(学号, 姓名, 系, 年龄, 性别)
- T(Tno, Tname, Age, Sex):教师T(工号, 姓名, 年龄, 性别)
- C(Cno, Cname, Pcon):课程C(课程号, 课程名称, 先修课程号)
SC(Sno, Cno, Grade):选课SC(学号, 课程号, 成绩)
关系模型
面向对象模型:存储对象是以对象为单位,每个对象包含对象的属性和方法,具有类和继承等特性。
关系代数
基本概念
属性和域
属性和域
:描述一个事物常常取若干特征来表示,特征又可称为属性(Attribute)。每个属性取值范围对应一个值的集合,称之为该属性的域(Domain)。第一范式:通常要求所有域都应该是原子数据。
笛卡尔积与关系
定义 1:设 $D_1, D_2, …, D_n$ 为任意集合,定义其笛卡尔积为:
每一种元素 $(d_1, d_2, …, d_i, …, d_n)$ 称为一个 n 元组(包含 n 个属性的元组),元组的每一个值 $d_i$ 称为元组的一个
分量
。笛卡尔积可用二维表表示,每行表示一个元组,每列表示一种属性,每列的值来源于一个域。
若 $D_i (i = 1, 2, …, n)$ 为有限集,其基数为 $m_i (i = 1, 2, …, n)$,则 $D_1 \times D_2 \times… \times D_n$ 的基数为:
[例] 若 $D_1 = { 0, 1 }, D_2 = { a, b }, D_1 = { c, d }$,求 $D_1 \times D_2 \times D_3$
[解] 笛卡尔积中每一个元素应该是一个三元组:
笛卡尔积二维表示
定义 2:$D_1 \times D_2 \times… \times D_n$ 的子集称为在域 $D_1, D_2, …, D_n$ 上的关系,记作 $R(D_1, D_2, …, D_n)$,称关系 R 为 n 元关系。
- 笛卡尔积是所有可能的组合,参与运算的某属性的取值范围(域)$D_1, D_2, …, D_n$ 并不会取全部的可能值(组合需要有意义)。
[例] 姓名的域往往抽取有限个 {张三,李四},学号的域也是抽取有限个 {00001, 00002, 00003}。但笛卡尔积给出他们所有的可能组合,现实情况是一个有且仅有一个学号。
1
2
3
4{
(张三,100101), (张三,100102), (张三,100103),
(李四,100101), (李四,100102), (李四,100103)
}
关系的相关名词
- 目或度:R 表示关系的名字,n 是关系的目或度。
- 候选码:关系中某一属性或者属性组的值能唯一地标识一个元组。
- 主码:关系中有多个候选码,选择其一为主码。
- 主属性:包含在候选码中的属性;不包含在任何候选码的属性称为非主属性。
- 外码:关系模式 R 中的属性或者属性组非该关系的码,但为其他关系的码,那么该属性集对关系模式 R 而言既外码。
- 全码:关系模型中所有属性组都为这个关系模式的候选码。
完整性约束
完整性约束
:保证当授权用户对数据库修改时不会破坏数据的一致性
。- 实体完整性:关系 R 的主属性不能取 NULL 值。
- 参照完整性:关系模型中实体间的联系是用关系描述的,故存在关系间的
引用
。 - 用户定义完整性
关系运算
关系运算
:关系操作的操作对象与结果都是集合
。关系运算 运算符 含义 集合运算 $\cup \\ - \\ \cap \\ \times$ 并
差
交
笛卡尔积比较运算 $> \\ \geq \\ < \\ \leq \\ = \\ \neq$ 大于
大于等于
小于
小于等于
等于
不等于逻辑运算 $\neg \\ \wedge \\ \vee$ 非
与
或专门的运算 $\sigma \\ \pi \\ \bowtie \\ \div$ 选择
投影
连接
除
基本的关系代数运算
并(Union)
- 关系 R 与 S 具有相同的关系模式(R与S的元数相同、结构相同)。
关系 R 与 S 的并属于 R 或属于 S 的元组构成的集合,记作:
差(Difference)
- 关系 R 与 S 具有相同的关系模式。
关系 R 与 S 的差由属于 R 但不属于 S 的元组构成的集合,记作:
广义笛卡儿积(Cartesian)
广义笛卡儿积(Extended Cartesian Product)
元数分别为 n 和 m 目的关系 R 与 S 的广义笛卡儿积为一个 n+m 列的元组集合。记作:
<$t^n$, $t^m$> 为元组 $t^n$ 与 $t^m$ 拼接成的一个元组。
投影(Projection)
投影:从关系的
垂直方向
进行运算,在关系 R 中选择若干属性列 A 组成新的关系,记作:
选择(Selection)
选择:从关系的
水平方向
进行运算,是从关系 R 中选择满足给定条件的诸元组,记作:- F 中运算对象是属性名(或列序号)、常数、运算符(算术比较符和逻辑运算符)。
- [例1] $\sigma_{1 \geq 6}(R)$ 表示选取 R 关系中第一个属性大于等于第六个属性的元组;
- [例2] $\sigma_{1 \geq 6}(R)$ 表示选取 R 关系中第一个属性大于等于 6 的元组。
扩展的关系代数运算
交(Intersection)
- 关系 R 与 S 具有相同的关系模式。
关系 R 与 S 的交是由属于 R 同时又属于 S 的元组构成的集合,记作:
等价于 $R \cap S = R-(R-S)$
连接(Join)
- 无条件连接:笛卡儿积
有条件连接:$\theta$ 连接 / 等值连接 / 自然连接
$\theta$ 连接:从笛卡儿积中选取属性间满足一定条件的元组,记作:
$X \theta Y$ 为连接条件,$\theta$ 为比较运算符。X、Y 分别是关系 R、S 上度数相等且可比的属性组。
- $t^n[X]$ 表示 R 中 $t^n$ 元组对应于属性 X 的一分量。
- $t^m[Y]$ 表示 S 中 $t^m$ 元组对应于属性 Y 的一分量。
等值连接:当 $\theta$ 为
=
时称作等值连接,记作:自然连接
- 特殊的
等值连接
,他要求两个关系中进行比较的分量必须是相同属性组,并且在结果集中将重复属性列去掉
。 一般连接
是从关系的水平方向
运算;自然连接不仅从关系的水平方向
和垂直方向
运算。因此自然会去掉重复属性。没有重复属性,自然连接自然转化为笛卡儿积。
自然连接可由基本关系运算笛卡儿积和选取运算表示:
[例] 设有关系 R 与 S,求自然连接 $R \bowtie S$。
自然连接
- 特殊的
除(Division)
- 同时从关系的水平方向和垂直方向进行运算。
- 给定关系 R(X, Y) 和 S(Y, Z),X、Y、Z 为属性组。
$R \div S$ 应当满足元组在 X 上的分量值 $x$ 的象集 $Y_x$ 包含在关系 S 在属性 Y 上投影的集合,记作:
$Y_x$ 为 $x$ 在 R 中的象集,$x = t^n[X]$,且 $R \div S$ 的结果集的属性组为 X。
[例] 设有关系 R 与 S,求 $R \div S$。
- 由定义可得,X 为属性 AB,Y 为属性 CD。
- 关系 S 在 Y 上的投影为 $\pi_{CD}(S) = {(c, d), (e, f)}$。
- 关系 R 的属性组 X 可取 3 个值 {(a, b), (b, d), (c, k)},则它们的象集分别为:
- $CD_{(a, b)} = { (c, d), (e, f), (h, k) }$
- $CD_{(b, d)} = { (e, f), (d, l) }$
- $CD_{(c, k)} = { (c, d), (e, f) }$
上述象集包含 $\pi_{CD}(S)$ 有 (a, b) 和 (c, k),为此 $R \div S = { (a, b), (c, k) }$。
$R \div S$
外连接(Outer Jion)
- 外连接(Outer Jion):自然连接时某些属性值不同则会导致这些元组被舍弃,而外连接正是用于处理由于连接运算而信息缺失的问题。
- 左外连接:取出左侧关系中所有与右侧关系中任一元组都不匹配的元组,用空值 NULL 填充所有来自右侧关系的属性,以构成新的元组。
- 右外连接:取出右侧关系中所有与左侧关系中任一元组都不匹配的元组,用空值 NULL 填充所有来自右侧关系的属性,以构成新的元组。
- 全外连接:
- 完成左外连接和右外连接操作。
- 填充左侧关系中所有与右侧关系中任一元组都不匹配的元组,并填充右侧关系中所有与左侧关系中任一元组都不匹配的元组,产生新元组加入自然连接的结果中。
[例] 设有关系 R 与 S,求 R 与 S 的左外连接、右外连接以及全外连接。
关系 R 与 S 的外连接
SQL 语言
SQL 基本结构
- 数据定义语言 (DDL):Create、Alter 和 Drop
- 数据操作语言 (DML):Insert、Update 和 Delete
- 数据查询语言 (DQL):Where,Order By,Group By 和 Having
- 数据控制语言 (DCL):Grant、Revoke
SQL 数据定义
创建表
创建表:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17CREATE TABLE mytable (
-- int 类型,不为空,自增
id INT NOT NULL AUTO_INCREMENT,
-- int 类型,不为空
fid INT NOT NULL,
-- decimal 类型,不可为空,默认值为 1.0
-- 前一个代表整数的位数,后一个代表小数的位数
col1 DECIMAL(10,6) NOT NULL DEFAULT 1.0,
-- 变长字符串类型,最长为 45 个字符,可以为空
col2 VARCHAR(45) NULL,
-- 日期类型,可为空
col3 DATE NULL,
-- 设置主键为 id
PRIMARY KEY (id)
-- 设置外键为 fid
FOREIGN KEY (fid) REFERENCES mytable1(fid)
);
修改表
添加列:
1
2ALTER TABLE mytable
ADD col VARCHAR(20);删除列:
1
2ALTER TABLE mytable
DROP COLUMN col;删除表:
1
DROP TABLE mytable;
建立索引
创建表时创建索引:
1
2
3
4
5
6
7
8CREATE TABLE 表名 (
字段名1 数据类型 [完整性约束条件…],
字段名2 数据类型 [完整性约束条件…],
-- UNIQUE:每一个索引值只对应唯一的数据记录
-- CLUSTER:建立聚簇索引
[UNIQUE | CLUSTER] INDEX | KEY
[索引名] (字段名[(长度)] [ASC | DESC])
);CREATE 在已存在的表上创建索引:
1
2CREATE [UNIQUE | CLUSTER] INDEX 索引名
ON 表名 (字段名[(长度)] [ASC | DESC]) ;ALTER TABLE 在已存在的表上创建索引:
1
2ALTER TABLE 表名 ADD [UNIQUE | CLUSTER] INDEX
索引名 (字段名[(长度)] [ASC | DESC]) ;
删除索引
删除索引:
1
DROP INDEX 索引名 ON 表名字;
创建视图
创建视图:创建视图必须遵循以下规定
- 子查询可以是任意复杂的 SELECT 语句,但通常不允许含有
ORDER BY
子句和DISTINCT
短语。 WITH CHECK OPTION
表示对UPDATE
、INSERT
、DELETE
操作时保证更新、插入或删除的行满足视图定义中的谓语条件,即子查询中的条件表达式。组成视图的属性列名要么全部省略 / 全部制定。
若全部省略属性列名,则由隐含该视图的 SELECT 子查询目标列的主属性组成。
1
2
3CREATE VIEW 视图名 (属性列名)
AS SELECT 查询子句
[WITH CHECK OPTION];
- 子查询可以是任意复杂的 SELECT 语句,但通常不允许含有
删除视图
删除视图:
1
DROP VIEW 视图名
SQL 数据查询
基本结构
SELECT 基本结构
1
2
3
4
5SELECT [ALL|DISTINCT] <目标列表达式>
FROM <表名或视图名>
[WHERE <条件表达式>]
[GROUP BY <列名> [HAVING <条件表达式>]]
[ORDER BY <列名> [ASC|DESC]]SELECT
子句对应关系代数中的投影运算
。- 输出结果可以是列名、表达式、聚合函数(COUNT、AVG、SUM、MAX、MIN)
- DISTINCT 确保查询结果集中不存在重复元组,它作用于所有列,也就是说所有列的值都相同才算相同。
FROM
子句对应关系代数中的笛卡儿积
。WHERE
子句对应关系代数中的选择谓语
, WHERE 子句的表达式中可使用的运算符如下表所示。操作符 说明 = 等于 < 小于 > 大于 <> 不等于 $\leq$ 小于等于 $\geq$ 大于等于 BETWEEN 在两个值之间 IS NULL / IS NOT NULL 为 NULL / 不为 NULL - 应该注意到
NULL
、0
与空字符串
是不同的概念。 AND
和OR
用于连接多个过滤条件。优先处理 AND,当一个过滤表达式涉及到多个 AND 和 OR 时,可以使用()
来决定优先级,使得优先级关系更清晰。IN
操作符用于匹配一组值,其后也可以接一个 SELECT 子句,从而匹配子查询得到的一组值。NOT
操作符用于否定一个条件。
- 应该注意到
连接查询
内连接:又称
等值连接
,使用普通查询并在WHERE
中将两个表中要连接的列用等值方法连接起来。1
2
3SELECT A.value, B.value
FROM tablea AS A, tableb AS B
WHERE A.key = B.key;自连接:自连接可以看成内连接的一种,只是连接的表是
自身
而已。例如:一张员工表包含员工姓名和员工所属部门,找出与 Jim 处在同部门的所有员工姓名。
1
2
3
4
5
6
7
8
9
10
11
12
13-- 子查询版本
SELECT name
FROM employee
WHERE department = (
SELECT department
FROM employee
WHERE name = "Jim"
);
-- WHERE版本
SELECT e1.name
FROM employee AS e1, employee AS e2
WHERE e1.department = e2.department AND e2.name = "Jim";自然连接:自然连接是把同名列通过等值测试连接起来的,同名列可以有多个。
内连接和自然连接的区别:内连接
提供连接
的列,而自然连接自动连接
所有同名列。外连接:外连不但返回符合连接和查询条件的数据行,且保留了没有关联的那些行。分为左外连接,右外连接以及全外连接。例如,左外连接就是保留左表没有关联的行。
子查询
非相关子查询
概念:非相关子查询是独立于外部查询的子查询,子查询执行完毕后将值传递给外部查询。子查询中只查询一次并返回一个字段的数据。
可以将子查询的结果作为 WHRER 语句的过滤条件:
1
2
3
4
5SELECT *
FROM mytable1
WHERE col1 IN (
SELECT col2 FROM mytable2
);下面的语句可以检索出客户的订单数量,子查询语句会对第一个查询检索出的每个客户执行一次:
1
2
3
4
5
6SELECT cust_name, (
SELECT COUNT(*)
FROM Orders
WHERE Orders.cust_id = Customers.cust_id) AS orders_num
FROM Customers
ORDER BY cust_name;
关联子查询
- 概念:关联子查询会引用外部查询中的一列或多列。这种子查询之所以被称为关联子查询,是因为子查询的确与外部查询有关。当问题的答案需要依赖于外部查询中包含的每一行中的值时,通常就需要使用关联子查询 $^{[3]}$。
相关子查询的执行依赖于外部查询的数据,外部查询执行一行,子查询就执行一次。并且是外部先查询一次,然后再执行一次内部查询。
即内部查询依赖于外部查询。
例如,查询部门工资前三高的所有员工 (Leetcode):
1
2
3
4
5
6
7
8
9
10
11Select d.Name as Department, e.Name as Employee, e.Salary
From Employee as e, Department as d
Where 1=1 AND e.DepartmentId = d.Id
Group By e.DepartmentId, e.id
Having (
Select Count(distinct es.Salary)
From Employee as es
Where 1=1
AND e.DepartmentID = es.DepartmentID
AND es.Salary > e.Salary
) < 3
聚合函数
各个 DBMS 的聚合函数都是不相同的,因此聚合函数一般不具备可移植性。SQL 提供的预定义聚合函数:
函 数 说 明 AVG( [DISTINCT\|ALL]<列名> )列名> 返回某列的平均值 COUNT( [DISTINCT\|ALL]<列名> )
COUNT([DISTINCT\|ALL]*)列名>返回某列的行数
统计元组个数MAX( [DISTINCT\|ALL]<列名> )列名> 返回某列的最大值 MIN( [DISTINCT\|ALL]<列名> )列名> 返回某列的最小值 SUM( [DISTINCT\|ALL]<列名> )列名> 返回某列值之和 以上聚合函数会忽略 NULL 行,考虑哪些运算不能包含 NULL 即可。
使用 ANY 和 ALL 谓语必须同时使用比较运算符,其含义及等价转换关系如下表所示:
谓 语 语 义 等价转换关系 >ANY 大于子查询结果中某个值 >MIN >ALL 大于子查询结果中所有值 >MAX <ANY 小于子查询结果中某个值 <MAX <ALL 小于子查询结果中所有值 <MIN <>ANY 不等于子查询结果中某个值 -- <>ALL 不等于子查询结果中任何值 NOT IN =ANY 等于子查询结果中某个值 IN =ALL 等于子查询结果中任何值 --
分组
- 把具有相同的数据值的行放在同一组中。
- 指定的分组字段除了能按该字段进行分组,也会按该字段自动进行排序。
可以对同一分组数据使用汇总函数进行处理,例如求分组数据的计数等。
1
2
3SELECT col, COUNT(*) AS num
FROM mytable
GROUP BY col;
GROUP BY 自动按分组字段进行排序,当然可通过 ORDER BY 按要求的汇总字段排序。
1
2
3
4SELECT col, COUNT(*) AS num
FROM mytable
GROUP BY col
ORDER BY num;
WHERE 过滤行,HAVING 过滤分组,行过滤应当先于分组过滤。
1
2
3
4
5SELECT col, COUNT(*) AS num
FROM mytable
WHERE col > 2
GROUP BY col
HAVING num >= 2;
- 分组规定:
- GROUP BY 子句需出现在 WHERE 子句之后,ORDER BY 子句之前;
- 除了汇总字段外,GROUP BY 子句中必须给出 SELECT 语句的字段名称;
- NULL 的行会单独分组;
- 大多数 SQL 实现不支持 GROUP BY 列具有可变长度的数据类型。
排序
- 升序:ASC (默认)
- 降序:DESC
可以按多个列进行排序,并且为每个列指定不同的排序方式:
1
2
3SELECT *
FROM mytable
ORDER BY col1 DESC, col2 ASC;
通配符
- 通配符也是用在过滤语句中,但它只能用于
文本字段
。%
匹配>=0
个任意字符;_
匹配==1
个任意字符;[]
可以匹配集合内的字符,例如 [ab] 将匹配字符 a 或者 b。用脱字符 ^ 可以对其进行否定,也就是不匹配集合内的字符;- 模式是大小写敏感的。
使用
LIKE
来进行通配符匹配:提示:不要滥用通配符,通配符位于开头处匹配会非常慢。
1
2
3
4
5
6SELECT *
FROM mytable
WHERE col LIKE '[^AB]%'; -- 挑选不以 A 和 B 开头的任意文本
-- WHERE col LIKE '%AB%'; 挑选包含 AB 的任意文本
-- WHERE col LIKE '%A\%B%'; 挑选包含 A%B 的任意文本(转义符的使用)
SQL 数据更新
插入
1
2
3
4
5
6INSERT INTO 表名 (字段名)
VALUES(常量)
-- 省略字段名,则 VALUES 需要补全所有属性作为输入
INSERT INTO 表名
VALUES(常量1, 常量2, ..., 常量 k)删除
1
2DELETE FROM 表名
[WHERE 条件表达式]修改
1
2
3UPDATE 表名
SET 列名 = 值表达式
[WHERE 条件表达式]
SQL 访问控制
常见的操作权限
对象 对象类型 操作权限 属性列 TABLE SELECT、INSERT、UPDATE、DELETE
ALL PRIVILEGES(包含四种权限)视图 TABLE SELECT、INSERT、UPDATE、DELETE
ALL PRIVILEGES(包含四种权限)基本表 TABLE SELECT、INSERT、UPDATE、DELETE、ALTER、INDEX
ALL PRIVILEGES(包含四种权限)数据库 DATABASE CREATETAB 建表权限 授权
PUBLIC
:设置该参数可将权限赋给全体用户WITH GRANT OPTION
:指定该语句则表示获得权限的用户还可将权限赋予给其他用户1
2
3
4
5
6GRANT <操作权限> [ON <对象类型> <对象名>]
TO <用户>
[WITH GRANT OPTION];
-- [例] 对表 S、P、J 的所有操作权限赋给所有用户
-- GRANT ALL PRIVILEGES ON TABLE S,P,J TO PUBLIC;
收回权限
1
2
3
4
5REVOKE <操作权限> [ON <对象类型> <对象名>]
FROM <用户>
-- [例] 将 User1 用户对表 S 的属性 Sno 的修改权限收回
-- REVOKE UPDATE(Sno) ON TABLE S FROM User1;
SQL 存储过程
游标:一条 SQL 语句可以产生或处理多条记录,而主语言是面向记录的,一组主变量一次只能存放一条记录。引入游标概念,通过游标指针来决定获取哪条记录。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20# 定义游标
# 实操当中变量名前缀需要添加 @,比如 DECLARE @Cur CURSOR FOR
DECLARE <游标名> CURSOR FOR
<SELECT 语句>
# 打开游标
# 实操当中变量名前缀需要添加 @,比如 OPEN @Cur
OPEN <游标名>
# 推进游标
# 实操当中变量名前缀需要添加 @,比如 FETCH NEXT FROM @Cur INTO @id, @name
FETCH NEXT FROM <游标名>
INTO <变量名>
# 关闭游标
# 实操当中变量名前缀需要添加 @,比如 CLOSE @Cur
CLOSE <游标名>
# 释放游标
DEALLOCATE <游标名>
创建存储过程
1
2
3
4
5
6
7
8
9CREATE PROCEDURE <存储过程名称> (
# IN:表示输入参数(默认值)
# OUT:表示输出参数
# IN OUT:即作为输入参数,也作为输出参数
IN | OUT | IN OUT @<参数名称> <参数类型>
) as
BEGIN
<SQL 语句>
END [存储过程名称]
SQL 触发器
特殊的储存过程,它的执行不是由程序调用,也不需要手工出发,而是由事件触发的。
触发器功能虽强大,但得谨慎使用。在数据库操作中,我们可以通过关系、触发器、存储过程、应用程序等来实现数据操作,同时规则、约束、缺省值也是保证数据完整性的重要保障。若我们过分依赖于触发器,势必影响数据库结构,同时增加了维护难度。
创建触发器
1
2
3
4
5
6
7
8
9CREATE TRIGGER <触发器名称> <BEFORE | AFTER>
<INSERT | DELETE | UPDATE [OF 列名清单]>
ON <表名>
[REFERENCING <临时视图表>]
[FOR EACH ROW | FOR EACH STATEMENT]
[WHEN <触发条件>]
BEGIN
<触发条件>
END [触发器名称]Referencing:指定临时视图的别名,触发器运行过程中,系统会生成存放更新值(旧值)以及更新后的值(新值)的临时视图。当触发器运行结束后,视图即不存在。
1)行级触发器视图名为 OLD ROW 和 NEW ROW。
2)语句级触发器默认视图名为 OLD-TABLE 和 NEW-TABLE。When:指定触发器的触发条件,触发条件须包含临时试图的名称。
[例] 银行处理透支时,不是将余额设置为负值,而是将账户余额设置为零,并建立一笔贷款(金额为透支金额,贷款号等于该透支账户的账户号),利用触发器实现这一过程。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17CREATE TRIGGER overdraft_trigger AFTER UPDATE ON account
REFERENCING NEW ROW as nrow
FOR EACH ROW
WHEN nrow.balance < 0
BEGIN ATOMIC
INSERT INTO borrower VALUES (
SELECT d.customer_name, d.account_number
FROM depositor as d
WHERE nrow.account_number = d.account_number
)
INSERT INTO loan VALUES (
nrow.account_number, # 贷款号
nrow.balance # 透支额
)
UPDATE account SET balance = 0
WHERE account.account_number = nrow.account_number
END
规范化
函数依赖
- 记 $A \to B$ 表示 A 函数决定 B,也可以说 B 函数依赖于 A。
- 若 ${A_1,A_2,… ,A_n}$ 是关系的一个或多个属性的集合,该集合函数决定了关系的其它所有属性并且是
最小的
,那么该集合就称为键码
。 - 对于 $A \to B$,如果能找到 A 的真子集 $A’$,使得 $A’ \to B$,那么 $A \to B$ 就是
部分函数依赖
,否则就是完全函数依赖
。 - 对于 $A \to B$,$B \to C$,则 $A \to C$ 是一个
传递函数依赖
。
异常
如表所示,展示了学生课程关系的函数依赖为 {Sno, Cname} -> {Sname, Sdept, Mname, Grade},键码为 {Sno, Cname}。也就是说,确定学生和课程后就能确定其它信息。
Sno Sname Sdept Mname Cname Grade 1 学生-1 学院-1 院长-1 课程-1 90 2 学生-2 学院-2 院长-2 课程-2 80 2 学生-2 学院-2 院长-2 课程-1 100 3 学生-3 学院-2 院长-2 课程-2 95 不符合范式的关系,会产生很多异常,主要有以下四种异常:
冗余数据
:例如学生-2
出现了两次。修改异常
:更改表中某个实体的单独属性时,需对多行进行更新。例如 sdept=’’学院-2’ 的院长,则需要需改多行记录。删除异常
:删除表中某一实体则会导致其他实体消失。例如删除了课程-1
需要删除第一行和第三行,那么 学生-1 的信息就会丢失。插入异常
:表中某个实体随着另一个实体而存在。例如想要插入一个学生的信息,如果这个学生还没选课,那么就无法插入。
范式
范式化设计
- 第一范式(1NF):
- 属性不可分,即数据库表的每一列都是不可分割的基本数据项,同一列中不能有多个值,即实体中的某个属性不能有多个值或者不能有重复的属性。
- 单一属性列由基本的数据类型所构成。
第二范式(2NF):
- 表中只具有一个主键。
每个非主属性完全函数依赖于键码,而不能存在非主属性部分依赖于键码。
比如,复合主键中常包括两种实体,如上述例子中的学生实体与课程实体,它们各自的属性依赖于各实体的主键。
如上表所示,学生课程关系中 {Sno, Cname} 为键码,有如下函数依赖:
- Sno -> Sname, Sdept
- Sdept -> Mname
- Sno, Cname -> Grade
- 函数依赖状况分析:
- Grade 完全函数依赖于键码,它没有任何冗余数据,每个学生的每门课都有特定的成绩。
- Sname, Sdept 和 Mname 都部分依赖于键码,当一个学生选修了多门课时,这些数据就会出现多次,造成大量冗余数据。
第三范式(3NF):
非主属性即不部分依赖,也不传递函数依赖于键码。
简而言之,第三范式就是属性不依赖于其它非主属性。
上表关系中存在以下传递函数依赖:Sno $\to$ Sdept $\to$ Mname。
Boyce Codd 范式(BCNF):
主属性之间不存在传递依赖关系。
简而言之,BCNF 范式规范主键之间不能存在相互决定的关系。
3NF 按定义排除了任何非主属性对键码的传递依赖与部分依赖。但该实体未必满足 BCNF 范式。
第四范式(4NF):
- 满足 Boyce Codd 范式基础上,并且没有多值依赖关系。
- 假设上表中 Sdept 包含多个 Mname(一个学院多名院长任职),存在多值依赖性,将导致不必要的数据重复。
反范式设计
- 反范式化:鉴于性能和读取效率考量,适当违反数据库范式设计要求,允许少量数据冗余。
优劣比较
优劣 范式化 反范式化 优势 1) 可尽量减少数据冗余 1) 减少表关联查询
2) 更好进行索引优化劣势 1) 多表关联查询
2) 难以进行索引优化1) 存在数据冗余及数据维护异常
事务管理
- 事务:指满足
ACID
特性的一组操作,可以通过 Commit 提交一个事务,也可以使用 Rollback 进行回滚。 ACID
- 原子性(Atomicity)
- 事务被视为不可分割的最小单元,事务的所有操作要么全部提交成功,要么全部失败回滚。
- 回滚可以用回滚日志来实现,回滚日志记录着事务所执行的修改操作,在回滚时反向执行这些修改操作即可。
- 一致性(Consistency):数据库在事务执行前后都保持一致性状态。在一致性状态下,所有事务对一个数据的读取结果都是相同的。
- 隔离性(Isolation):一个事务所做的修改在最终提交以前,对其它事务是不可见的。
持久性(Durability):一旦事务提交,则其所做的修改将会永远保存到数据库中。即使系统发生崩溃,事务执行的结果也不能丢失。
使用重做日志来保证持久性。
- 原子性(Atomicity)
ACID 特性概念简单,但不好理解,主要是因为这几个特性不是一种平级关系:
- 只有满足一致性,事务的执行结果才是正确的。
- 在无并发情况下,事务串行执行,隔离性一定能够满足。此时只要能满足原子性,就一定能满足一致性。
- 在并发情况下,多个事务并行执行,事务不仅要满足原子性,还需要满足隔离性,才能满足一致性。
事务满足持久化是为了能应对数据库崩溃的情况。
ACID逻辑关系
- 只有满足一致性,事务的执行结果才是正确的。
并发控制
事务并发环境下保证事务一致性的方法
- 在并发环境下,事务的隔离性很难保证,因此会出现很多并发一致性问题。
- 产生并发不一致性问题的主要原因是破坏了事务的隔离性。
- 解决方法是通过
并发控制
来保证隔离性。- 并发控制可以通过
封锁
来实现,但是封锁操作需要用户自己控制,相当复杂。 - 数据库管理系统提供了事务的
隔离级别
,让用户以一种更轻松的方式处理并发一致性问题。
- 并发控制可以通过
并发一致性问题
丢失数据:T1 和 T2 两个事务都对一个数据进行修改,T1 先修改,T2 随后修改,T2 的修改覆盖了 T1 的修改。
简记为
同时修改
。读脏数据:T1 对一个数据做了修改,T2 读取这一个数据。若 T1 执行 ROLLBACK 操作,则 T2 读取的结果和第一次的结果不一样。
简记为
读取修改失败的记录
。最简单的场景是修改完成后,紧接着查询检验结果。不可重复读:T2 读取一个数据,T1 对该数据做了修改。如果 T2 再次读取这个数据,此时读取的结果和第一次读取的结果不同。
简记为
读时修改
,重复读取的结果不一样。幻影读:T1 读取某个范围的数据,T2 在这个范围内插入新数据或者删除数据,T1 再次读取这个范围的数据,此时读取结果和第一次读取的结果不一样,事务并没有独立开来。
简记为
事务没有独立性,受其他事务插入或者删除影响
。并发一致性问题
封锁
封锁粒度
- 以 MySQL 为例,它提供了两种封锁粒度:
行级锁
以及表级锁
。 - 应尽量只锁定需要修改的那部分数据,而不是所有的资源。锁定的数据量越少,发生锁争用的可能就越小,系统的并发程度就越高。
但是加锁需要消耗资源,锁的各种操作(包括获取锁、释放锁、以及检查锁状态)都会增加系统开销。因此封锁粒度越小,系统开销就越大。
为此,我们在选择封锁粒度时,需在
锁开销
和并发程度
之间做一个权衡
。
封锁类型
读写锁
- 排它锁(Exclusive):写锁,简写为 X 锁
共享锁(Shared):读锁,简写为 S 锁
有以下两个规定:
- 一个事务对数据对象 A 加了 X 锁,就可以对 A 进行读取和更新。加锁期间其它事务不能对 A 加任何锁。
- 一个事务对数据对象 A 加了 S 锁,可以对 A 进行读取操作,但是不能进行更新操作。加锁期间其它事务能对 A 加 S 锁,但是不能加 X 锁。
读写锁之间的兼容关系如表所示:✕ 相互不兼容,✓ 相互兼容
锁类型 排它锁 X 共享锁 S 排它锁 X ✕ ✕ 共享锁 S ✕ ✓
意向锁(Intention Locks)
- 支持多粒度封锁,使得行锁和表锁能够共存。
- 在存在行级锁和表级锁的情况下,事务 T 想要对表 A 加 X 锁,就需要先检测是否有其它事务对表 A 或者表 A 中的任意一行加了锁,那么就需要对表 A 的每一行都检测一次,这是非常耗时的。
- 意向锁在原来的 X / S 锁之上引入了 IX / IS 锁(两者都属于表级锁),用来表示一个事务稍后会对表中的某个数据行上加 X 锁或 S 锁。整理可得以下两个规定:
- 一个事务在获得某个数据行对象的 S 锁前,必须先获得表的 IS 锁或者更强的锁。
- 一个事务在获得某个数据行对象的 X 锁之前,必须先获得表的 IX 锁。
读写锁与意向锁的兼容关系如表所示:✕ 相互不兼容,✓ 相互兼容
- 任意 IS / IX 锁之间都是兼容的,因为它们只是表示想要
对表加锁
,而不是真正加锁。 S 锁只与 S 锁和 IS 锁兼容,也就是说事务 T 想要对数据行加 S 锁,其它事务可以已经获得对表或者表中的行的 S 锁。
锁类型 排它锁 X 共享锁 S 意向排它锁 IX 意向共享锁 IS 排它锁 X ✕ ✕ ✕ ✕ 共享锁 S ✕ ✓ ✕ ✓ 意向排它锁 IX ✕ ✕ ✓ ✓ 意向共享锁 IS ✕ ✓ ✓ ✓
- 任意 IS / IX 锁之间都是兼容的,因为它们只是表示想要
封锁协议
三级封锁协议
一级封锁协议
:事务 T 要修改数据 A 时必须加 X 锁,直到 T 结束才释放锁。可解决 “丢失修改” 问题,因不能同时有两个事务对同一个数据修改,那么事务的修改就不会被覆盖。
二级封锁协议
:在一级封锁基础上,要求读取数据 A 时必须加 S 锁,读取完马上释放 S 锁。可解决 “丢失修改” 和 “读脏数据” 问题,因一个事务在对数据 A 进行修改,根据 1 级封锁协议,会加 X 锁,那么就不能再加 S 锁了,也就是不会读入数据。
三级封锁协议
:在二级封锁基础上,要求读取数据 A 时必须加 S 锁,直到事务结束了才能释放 S 锁。可解决 “丢失修改” 和 “读脏数据” 问题,还进一步防止了 “不可重复读” 的问题,因为读 A 时,其它事务不能对 A 加 X 锁,从而避免了在读的期间数据发生改变。
三级封锁协议示例
两段锁协议
- 两段锁协议是指每个事务的执行可以分为两个阶段:生长阶段(加锁阶段)和衰退阶段(解锁阶段)。
- 两段封锁实现方式:
- 事务开始后就处于加锁阶段,一直到执行 ROLLBACK 和 COMMIT 之前都是加锁阶段。
- ROLLBACK 和 COMMIT 使事务进入解锁阶段,即在 ROLLBACK 和 COMMIT 模块中 DBMS 释放所有封锁。
可串行化调度:通过并发控制,使得并发执行的事务结果与某个串行执行的事务结果相同。
事务遵循两段锁协议是保证可串行化调度的
充分条件
。例如以下操作满足两段锁协议,它是可串行化调度。1
lock-x(A)...lock-s(B)...lock-s(C)...unlock(A)...unlock(C)...unlock(B)
但不是
必要条件
,例如以下操作不满足两段锁协议,但是它还是可串行化调度。1
lock-x(A)...unlock(A)...lock-s(B)...unlock(B)...lock-s(C)...unlock(C)
隔离级别
事务指定一个隔离级别,该隔离级别定义了一个事务必须与其他事务进行资源或数据更改相隔离的程度。隔离级别是从
允许并发一致性问题发生
的角度进行描述的。例如,脏读、不可重复读或幻影读。如表所示,是关于隔离级别与并发副作用的层级关系。图例说明:✕ 是可避免的情况,✓ 是允许发生的情况
隔离级别 \ 并发一致性问题 脏读 不可重复读 幻影读 未提交读 ✓ ✓ ✓ 提交读 ✕ ✓ ✓ 可重复读 ✕ ✕ ✓ 串行化读 ✕ ✕ ✕ 实现方式:MySQL 的 InnoDB 存储引擎实现隔离级别的具体方式有:多版本并发控制(MVCC)与 Next-Key Locks。
隔离级别:
- 未提交读(Read uncommitted):事务中的修改,即使没有提交,对其它事务也是可见的。
提交读(Read committed):一个事务只能读取已经提交的修改事务。换句话说,一个事务所做的修改在提交之前对其它事务是不可见的。
Oracle 数据库默认的事务隔离级别。
可重复读(Repeatable Read):保证一个当前事务读取不会受到另一个事务修改数据(即使已提交或者回滚)的影响,也称为快照读。
MySQL 数据库默认的事务隔离级别。
可串行化(Serialzable):强制事务串行执行。需要加锁实现,而其它隔离级别通常不需要加锁。
多版本并发控制
- 多版本并发控制(Multi-Version Concurrency Control, MVCC):MySQL 的 InnoDB 存储引擎实现隔离级别的一种具体方式,用于实现
提交读
和可重复读
这两种隔离级别。 未提交读
隔离级别总是读取最新的数据行,无需使用 MVCC。可串行化
隔离级别需要对所有读取的行都加锁,单纯使用 MVCC 无法实现。
版本号
- 该版本号是指事务的版本号。
- 系统版本号:是一个递增数字,每开始一个新事务,系统版本号就会自动递增。
- 事务版本号:事务开始时的系统版本号。
隐藏列
该版本号指数据行快照的版本号。
MVCC 在每行记录后面都保存着两个隐藏的列,用来存储两个版本号:
- 创建版本号:指示创建一个数据行快照时的系统版本号;
- 删除版本号:如果该快照的删除版本号大于当前事务版本号表示该快照有效,否则表示该快照已经被删除了。
UndoLog
MVCC 使用到的快照存储在 Undo Log 中,该日志通过回滚指针把一个数据行(Record)的所有快照连接起来。
存储在 Undo日志中的快照
实现过程
- 以下实现过程是针对
可重复读
隔离级别的:- 当开始一个事务时,该事务的版本号肯定大于当前所有数据行快照的创建版本号,理解这一点很关键。
- 数据行快照的创建版本号是创建数据行快照时的系统版本号,系统版本号随着创建事务而递增,因此新创建一个事务时,这个事务的系统版本号比之前的系统版本号都大,也就是比所有数据行快照的创建版本号都大。
SELECT
多个事务必须读取到同一个数据行的快照,并且这个快照是距离现在最近的一个有效快照。
但也有例外,若一个事务正在修改该数据行,那么它可以读取事务本身所做的修改,而不用和其它事务的读取结果一致。
把没有对一个数据行做修改的事务称为 T,T 所要读取的数据行快照的创建版本号必须小于等于 T 的版本号,因为如果大于 T 的版本号,那么表示该数据行快照是其它事务的最新修改,因此不能去读取它。
- 除此之外,T 所要读取的数据行快照的删除版本号必须是未定义或者大于 T 的版本号,因为如果小于等于 T 的版本号,那么表示该数据行快照是已经被删除的,不应该去读取它。
- INSERT:将当前系统版本号作为数据行快照的创建版本号。
- DELETE:将当前系统版本号作为数据行快照的删除版本号。
UPDATE:将当前系统版本号作为更新前的数据行快照的删除版本号,并将当前系统版本号作为更新后的数据行快照的创建版本号。
可以理解为先执行 DELETE 后执行 INSERT。
快照读与当前读
快照读:使用 MVCC 读取的是快照中的数据,这样可以减少加锁所带来的开销。
1
SELECT * FROM table;
当前读:读取的是最新的数据,需要加锁。以下第一个语句需要加 S 锁,其它都需要加 X 锁。
1
2
3
4
5SELECT * FROM table WHERE ? LOCK IN SHARE MODE;
SELECT * FROM table WHERE ? FOR UPDATE;
INSERT ...;
UPDATE ...;
DELETE ...;
Next-Key Locks
MVCC 不能解决
幻影读
问题,Next-Key Locks 就是为了解决这个问题而存在的。场景复现:可重复读保证了一个事务不会修改已经由另一个事务读取但未提交 (或回滚) 的数据,例如统计某班男生的人数。但此时插入一名男生,而同样的查询操作会导致不一致的查询结果。
- 在可重复读(REPEATABLE READ)隔离级别下,使用
MVCC + Next-Key Locks
可以解决幻读问题。 - Next-Key Locks 是 MySQL 的 InnoDB 存储引擎的一种
锁实现
。
Record Locks
- 锁定一个记录上的索引,而不是记录本身。
- 如果表没有设置索引,InnoDB 会自动在主键上创建隐藏的聚簇索引,因此 Record Locks 依然可以使用。
Gap Locks
锁定索引之间的间隙,但是不包含索引本身。例如当一个事务执行以下语句,其它事务就不能在 t.c 中插入 15。
1
SELECT c FROM t WHERE c BETWEEN 10 and 20 FOR UPDATE;
Next-Key Locks
它是 Record Locks 和 Gap Locks 的结合,不仅锁定一个记录上的索引,也锁定索引之间的间隙。例如一个索引包含以下值:10, 11, 13, and 20,那么就需要锁定以下区间:
1
2
3
4
5(-∞, 10]
(10, 11]
(11, 13]
(13, 20]
(20, +∞)
操作系统
进程管理
进程状态
进程的五态模型
进程的五态模型
创建进程
分两个阶段:第一阶段为一个新进程创建必要的管理信息;第二阶段让该进程进入就绪状态。终止进程
分两个阶段:第一阶段等待操作系统进行善后处理;第二阶段释放主存。
具有挂起状态的进程状态及其转换
细分进程状态及其转换
- 活跃就绪:进程在
主存
并且可被调度的状态。 - 静止就绪:就绪进程被对换到
辅存
时的状态,它是不能被直接调度的状态,只有当主存中没有活跃就绪态进程,或具有更高优先级的挂起态进程时,系统才会把挂起就绪态进程调回主存并转换为活跃就绪。 - 活跃阻塞:进程在
主存
,一旦等待的事件产生便进入活跃就绪状态。 - 静止阻塞:阻塞进程对换到
辅存
时的状态,一旦等待的事件产生便进入静止就绪状态。
- 活跃就绪:进程在
进程通信
- 进程的同步与互斥
- 同步:多个进程可并发执行,每个进程以各自独立的、不可预知的速度向前推进,但需在某些确定点上协调合作进程间的工作。
- 互斥:系统中多个进程因争用
临界资源
而互斥执行。
- 信号量机制
- 临界资源:进程间需要互斥方式对其进行共享的资源。
- 临界区:每个进程中访问临界资源的那段代码称为
临界区
。 - 信号量:特殊变量
PV 操作
PV 操作
P 操作:S:=S-1,若 $S \geq 0$ 则执行 P 操作的进程继续执行;若 $S < 0$ 则置该进程为阻塞状态(无资源可用),并将其插入阻塞队列。
$S \geq 0$,S 表示该资源的可用数;$S < 0$,$|S|$ 表示阻塞队列中等待该资源的进程数。
1
2
3
4
5Procedure P(Var S:Semaphore);
Begin
S:=S-1; // S>=0 表示缓冲区为空,可送入产品
If S<0 Then Wait(S) // 执行 P 操作的进程插入等待队列
End;V 操作:S:=S+1,若 $S > 0$ 则执行 V 操作的进程继续执行;若 $S \leq 0$ 则唤醒一个阻塞状态的进程,并将其插入就绪队列,然后执行 V 操作的进程继续。
$S > 0$,S 表示正在等待该资源的进程数;$S \leq 0$,$|S|$表示该资源的可用数。
1
2
3
4
5Procedure V(Var S:Semaphore);
Begin
S:=S+1; // S>0 缓冲区有产品
If S<=0 Then Resume(S) // 从阻塞队列中唤醒进程
End;
利用 PV 操作实现进程的互斥:令信号量 mutex 初值为 1,当进入临界区时执行 P 操作,退出临界区时执行 V 操作。
1
2
3P(mutex)
临界区
V(mutex)
死锁
必要条件
互斥
:资源是独占的且排他使用,进程互斥使用资源。每个资源要么已分配给一个进程,要么就是可用的。占有和等待
:已经得到的资源的某进程可再请求资源。不可抢占
:已经分配给进程的资源不可强性被抢占,只能是占有进程显式地释放。环路等待
:有两个及以上的进程组成一条环路,该环路中的每个进程都在等待下一个进程所占有的资源。以上给出了导致死锁的四个必要条件,只要系统发生死锁则以上四个条件至少有一个成立。反过来思考,我们可通过破坏四个条件中的任何一个来预防死锁的发生。
处理方法
鸵鸟策略
:把头埋在沙子里,假装根本没发生问题。- 因解决死锁问题的代价很高,因此鸵鸟策略这种不采取任务措施的方案会获得更高的性能。
- 大多数操作系统,包括 Unix,Linux 和 Windows,处理死锁问题的办法仅仅是忽略它。
死锁检测
:不试图阻止死锁,而是当检测到死锁发生时,采取措施进行恢复。每种类型一个资源的死锁检测
下图为资源分配图,其中
方框表示资源
,圆圈表示进程
。资源指向进程表示该资源已经分配给该进程,进程指向资源表示进程请求获取该资源。图 (a) 可以抽取出环,如图 (b),它满足了环路等待条件,因此会发生死锁。每种类型一个资源的死锁检测
每种类型一个资源的死锁检测算法是通过
检测有向图是否存在环
来实现。从一个节点出发进行深度优先搜索
,对访问过的节点进行标记,如果访问了已经标记的节点,就表示有向图存在环,也就是检测到死锁的发生。
每种类型多个资源的死锁检测
如图所示,有三个进程四个资源,每个数据代表的含义如下:
- E 向量:资源总量
- A 向量:资源剩余量
- C 矩阵:每个进程所拥有的资源数量,每一行都代表一个进程拥有资源的数量
R 矩阵:每个进程请求的资源数量
每种类型多个资源的死锁检测
进程 P1 和 P2 所请求的资源都得不到满足,只有进程 P3 可以,让 P3 执行,之后释放 P3 拥有的资源,此时 A = (2 2 2 0)。P2 可以执行,执行后释放 P2 拥有的资源,A = (4 2 2 1) 。P1 也可以执行。所有进程都可以顺利执行,没有死锁。
- 算法总结如下:每个进程最开始时都不被标记,执行过程有可能被标记。当算法结束时,任何没有被标记的进程都是死锁进程。
Step.01
:寻找一个没有标记的进程 Pi,它所请求的资源小于等于 A。Step.02
:若找到了这样一个进程,那么将 C 矩阵的第 i 行向量加到 A 中,标记该进程并转回 1。Step.03
:若没找到这样一个进程,算法终止。
死锁恢复
- 利用抢占恢复
- 利用回滚恢复
- 通过杀死进程恢复
死锁预防
:在程序运行前预防发生死锁。破坏互斥条件
:例如假脱机打印机技术允许若干个进程同时输出,唯一真正请求物理打印机的进程是打印机守护进程。破坏占有和等待条件
:一种实现方式是规定所有进程在开始执行前请求所需要的全部资源。破坏不可抢占条件
:允许对资源实行抢夺。- 方法一:一个进程不能获得所需全部资源时便处于等待状态,等待期间他占有的资源将被隐式的释放重新加入到系统的资源列表中,可被其他的进程使用,而等待的进程只有重新获得自己原有的资源以及新申请的资源才可以重新启动执行。
- 方法二:若一进程请求当前被另一进程占有的一个资源,则操作系统可抢占另一个进程,要求它释放资源。仅在任意两个进程的优先级都不相同的条件下,该方法才能预防死锁。
破坏环路等待
:给资源统一编号,进程只能按编号顺序来请求资源。
死锁避免
:在程序运行时避免发生死锁。安全状态
- 图 (a) 的第二列 Has 表示已拥有的资源数,第三列 Max 表示总共需要的资源数,Free 表示还有可以使用的资源数。
从图 (a) 开始出发,先让 B 拥有所需的所有资源 (图 b),运行结束后释放 B,此时 Free 变为 5 (图 c);接着以同样的方式运行 C 和 A,使得所有进程都能成功运行,因此可以称图 a 所示的状态时安全的。
证明 (a) 的状态是安全的
定义:如果没有死锁发生,并且即使所有进程突然请求对资源的最大需求,也仍然存在某种
调度次序
能够使得每一个进程运行完毕
,则称该状态是安全的。安全状态的检测与死锁的检测类似,因为安全状态必须要求不能发生死锁。下面的银行家算法与死锁检测算法非常类似,可以结合着做参考对比。
单个资源的银行家算法
- 一个小城镇的银行家,他向一群客户分别承诺了一定的贷款额度,算法要做的是判断对请求的满足是否会进入不安全状态,如果是,就拒绝请求;否则予以分配。
图 (c) 为不安全状态,因此算法会拒绝之前的请求,从而避免进入图 (c) 中的状态。
单个资源的银行家算法
多个资源的银行家算法
如图所示,有五个进程,四个资源。
多个资源的银行家算法
左边的图表示已经分配的资源,右边的图表示还需要分配的资源。
下方向量 E、P 以及 A 分别表示:总资源、已分配资源以及可用资源。
注意这三个为向量,而不是具体数值,例如 A = ( 1 0 2 0 ),表示 4 个资源分别还剩下 1/0/2/0。
检查一个状态是否安全的算法如下:
- Step.01:查找右边的矩阵是否存在一行小于等于向量 A。如果不存在这样的行,那么系统将会发生死锁,状态是不安全的。
- Step.02:假若找到这样一行,将该进程标记为终止,并将其已分配资源加到 A 中。
- Step.03:重复以上两步,直到所有进程都标记为终止,则状态时安全的。若一个状态不是安全的,需要拒绝进入这个状态。
线程
- 线程是进程中的一个实体,是被系统
独立分配
和独立调度
的基本单位。 一个进程中可以有多个线程,它们共享进程资源。
QQ 和 QQ 浏览器是两个进程,浏览器进程里面有很多线程。例如 HTTP 请求线程、事件响应线程、渲染线程等,线程的并发执行使得在浏览器中点击一个新链接从而发起 HTTP 请求时,浏览器还可以响应用户的其它事件。
进程与线程的区别:
拥有资源
:进程是资源分配
的基本单位,但是线程不拥有资源,线程可以访问隶属进程的资源。调度
:线程是独立调度
的基本单位,在同一进程中,线程的切换不会引起进程切换。但是从一个进程中的线程切换到另一个进程中的线程时,会引起进程切换。系统开销
:由于创建或撤销进程时,系统都要为之分配或回收资源,如内存空间、I/O 设备等,所付出的开销远大于创建或撤销线程时的开销。类似地,在进行进程切换时,涉及当前执行进程 CPU 环境的保存及新调度进程 CPU 环境的设置,而线程切换时只需保存和设置少量寄存器内容,开销很小。通信方面
:线程间可以通过直接读写同一进程中的数据进行通信,但是进程通信需要借助IPC
(进程间通信,Inter-Process Communication)。
存储管理
基本概念
存储器的层次结构
存储器的层次结构
虚拟地址:源程序的地址空间称为符号地址空间,其从 0 号单元开始编址,并顺序分配所有的符号名所对应的地址单元。它不是主存的真实地址,又称为
相对地址
。源程序经过
汇编
或者编译
后,再经过链接编辑程序加工形成程序的装配模块,即转换为相对地址编址模块。地址空间:程序中由相对地址组成的空间称为逻辑地址空间,相对地址空间通过再定位机构转换到绝对地址空间(物理地址的集合)。
- 地址重定位:
- 静态重定位:在程序装入主存时,已完成逻辑地址到物理地址的变化,在程序的执行期间将不会再发生变化。
- 优点:无须硬件地址变换机构的支持,它只要求程序本身是可重定位的(修改地址部分具有某种标识)。
- 缺点: 必须给作业分配一个连续的存储区域。
- 动态重定位:在程序运行期间完成逻辑到物理地址的变化。
- 优点:程序在执行期间可换入和缓存主存;不必给程序分配连续的主存空间,把主存中碎片集中起来。
- 静态重定位:在程序装入主存时,已完成逻辑地址到物理地址的变化,在程序的执行期间将不会再发生变化。
管理方案
分页存储管理
- 分页原理
- 将一个进程的地址空间划分成若干个大小相等的区域,称为页。
- 相应地,将主存空间划分成与页相同大小的若干个物理块,称为块。
- 为进程分配主存时,将进程中若干页分别装入多个不相邻的块中。
地址结构
- 分页地址由两部分组成,前一部分分为页号 P,后一部分为偏移量 W,即页内地址。
地址长度为 32 位,0 ~ 11 位为页内地址(每页大小为 $2^{12}B=4KB$),12 ~ 31 位为页号($2^{20}B=1MB$)
分页地址结构
页表
- 进程的多个页面离散地分配到主存的多个物理块时,系统应保证在主存中找到进程要访问的页面所对应的物理块。
- 为此,系统为每个进程建立了一张页面映射表(页表)。
- 页表的作用是实现从页号到物理块号(页帧号)的地址的映射。
如图所示,逻辑页号为 4,查找页表得到该页的物理块号为 15,与页内地址 256 拼接得到物理地址。
页式存储管理的地址映射
分页存储优劣
- 优:空间利率高,且产生碎片少
- 劣:增加系统开销,可能产生 抖动现象。
分段存储管理
- 分段原理
- 作业的地址空间被划分为若干个段,每段式一组完整的逻辑信号,例如有主程序段、子程序段、数据段以及堆栈段。
- 每个段都拥有自己的名字,从 0 开始编制的一段连续的地址空间,各段长度是可以不等的。
地址结构:逻辑地址由段号和段内地址两部分组成,允许一个作业最多 64KB 个段,每个段最大长度为 64KB。
分段地址结构
段表
- 为每个段分配一个连续的分区,而进程中的各个段可里离散地分配到主存的不同分区中。
- 系统为每个进程建立一张段映射表(段表),每个段在表中占有一个表项,其中记录了该段在主存中的起始地址(基址)和段的长度。
- 程序在执行时,通过查段表来找到每个段所对应的主存区。
- 段表实现了从逻辑段到物理主存区的映射。
段式存储的内存空间划分
段式存储的内存空间划分
如图所示,分段式存储管理实现从逻辑地址到物理地址的变换功能。
段式存储管理的地址变换机构
分段存储优劣
- 优:多道程序共享内存
- 劣:内存利用率低,较多内存碎片
段页式存储管理
- 分页过程由操作系统完成,用户不必关心分页过程,其缺点式不易实现共享;段是信息的逻辑单位,易于实现分段式共享即允许若干进程共享一个或多个段。对两种存储管理方式 “各取所长”,既具有分页系统又能提高主存利用率的存储管理方式
段页式存储管理
。 - 段页式原理
- 将整个主存划分成大小相等的存储块,将用户程序按程序的逻辑关系分为若干个段,并为每个段赋予一个段名,再将每个段划分成若干页,存储块为单位离散分配。
地址结构:由段号、段内页号和页内地址组成。
段页式管理的地址结构
段页式系统
- 系统必须同时配置段表和页表。
- 对段中的页进行离散地分配,段表中的内容不在式段的主存始址和段长,而是页表始址和页表长度。
- 段表寄存器用于存放段表起始地址和段表长度 TL。
段页式系统中逻辑地址到物理地址的变换过程,如下图所示。
- 根据段号 S 查段表,得到页表的起始地址。
- 根据页号 P 查页表,得到物理块号 b。
将物理块号 b 拼页内地址 W 得到物理地址。
段页式存储管理的地址变换结构
虚拟存储管理
- 页面置换算法(页面淘汰算法)
- 请求分页是在纯分页系统基础上增加了请求调页功能、页面置换功能所形成的
页面虚拟存储系统
。 - 在进程运行过程中,若发生缺页但主存又无空闲块时,为保证进程能正常运行,须从主存中调出一页程序或者数据送到
磁盘对换区
。 - 究竟将哪个页面调出,需根据一定的页面置换算法来决定。
- 请求分页是在纯分页系统基础上增加了请求调页功能、页面置换功能所形成的
先进选出置换算法(FIFO):总是淘汰最先进入主存的页面,即选择在主存中驻留时间最近的页面予以淘汰。
当分配物理块数量增多时,有缺页次数增加、缺页率提高的异常现象,称之为
抖动
。最近最少未使用置换算法(Least recently used, LRU)
- 选择最近最少未使用的页面予以淘汰。
- 系统在每个页面设置一个访问字段,用于记录这个页面自上次被访问以来所经历的时间 T,选择 T 最大的页面予以淘汰,但实现时需硬件支持(寄存器或栈)。
[实例] 在一虚拟存储系统中,进程的内存空间为 3 页,开始内存为空,有以下访问页序列:5 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 5 0 1,分别计算 FIFO 置换算法和 LRU 置换算法的缺页次数。
FIFO 置换算法和 LRU 置换算法的缺页次数对比
磁盘管理
磁盘结构与参数
磁盘结构与参数
磁盘的性能参数
- 磁盘存取数据时间
- 磁盘容量
存取时间 = 寻道时间 + 等待时间
- 等待时间:平均定位时间 + 转动延迟,即等待读写的扇区转到磁头下方所用的时间。
- 寻道时间:磁头移动到磁道所需时间。
容量
- 非格式化 = 面数 * 磁道数/面 * 内圆周长 * 最大位密度
格式化 = 面数 * 磁道数/面 * 扇区数/道 * 字节数/扇区
格式化 = 面数 * 磁道数/面 * 单磁道字节数
知识产权
基本概念
知识产权可分为
工业产权
和著作权
两类。工业产权:专利、实用新型、工业品外观设计、商标、厂商名称、服务标记、产地标记(或原产地名称)
商业秘密、微生物技术、遗传基因技术也属于工业产权保护对象。
著作权:作者对其创作的作品享有
人身权
和财权
。- 人身权:发表权、署名权、修改权、保护作品完整权
- 财产权:作品使用权、获报酬权
智力成果不限于其一,它们可
同时
成为工业产权和著作权保护的客体。比如,计算机软件和实用艺术品受著作权保护同时,权利人还可通过申请发明专利和外观设计专利获得专利权。
知识产权的特点
- 无形性:
- 无形财产权,客体是智力创作性成果(或知识产品)。
- 没有形体的精神财富,可脱离其所有者而存在的无形信息,可同时为多个主体使用。
- 双重性:
- 某些知识产权具有财产权和人身权。比如著作权。
- 商业秘密只有财产权属性;专利权、商标权主要体现为财产权。
- 确认性:智力创作性成果的财产权需要依法审查确认,以得到法律保护。
- 独占性:
- 智力成果可同时被多个主体所使用,为此法律授予知识产权一种专用权。
- 未经权利人许可,任何单位或个人不得使用,否则构成侵权并承担相应法律责任。
- 地域性:各国主管机关依照本国法律授予的知识产权,只能在其
本国领域内
受法律保护。 时间性:知识产权具有法定的保护期限,期限届满则权利自行终止,成为社会公众可自由使用的知识。至于期限长短依照各国的法律确定,以下为我国知识产权保护期限的情况:
- 发明专利:20 年(自专利申请日起计算)
- 实用新型专利权和外观设计专利权:10 年(自专利申请日起计算)
商标权:自核准注册之日起 10 年,可根据所有人需要无限地延长权利期限。
在期限届满 6 个月内申请续展注册,每次续展注册有效期为 10 年,续展注册次数不限。
商业秘密:受法律保护期限是不确定的,秘密一旦被公众所知悉即可成为自由似乎用的知识。
- 无形性:
计算机软件著作权
著作权的主体与客体
- 软件著作权的主体
- 公民:公民自行独立开发、订立委托合同他人开发(约定著作权归自己享有)、转让取得、继承取得
- 法人
- 法人组织并提供创作物质条件所实施的开发(法人承担社会责任)
- 接口委托、转让等有效合同关系取得著作权的主体资格
- 法人变更而依法成为著作权的主体
- 其他组织
- 软件著作权的客体:计算机程序及其有关文档
著作权的权利
- 著作人身权(精神权利)
- 发表权
- 开发者身份权(署名权)
- 著作财产权(经济权利):使用权、复制权、修改权、发行权、翻译权、注释权、信息网络传播权、出租权、使用许可权和获得报酬权、转让权。
- 合法持有人的权利
- 把软件装入计算机等存储信息的装置内。
- 必要的复制。
- 制作备份复制品,复制品不得通过任何方式提供他人使用。
- 不得向第三方提供修改后的软件。
著作权的保护期
- 自软件开发完成之日起产生,保护期为 50 年。
- 保护期满,除开发者身份权以外,其他权利终止。软件进入共有领域。
计算机软件商业秘密
- 商业秘密定义
- 不为公众所知悉的;
- 能为权利人带来经济利益;
- 具有实用性并经权利人采取保密措施的技术信息和经营信息。
商业秘密构成条件
- 未公开性
- 实用性:能给权利人带来经济效益
保密性
缺少上述任一条件时,商业秘密丧失保护。
商业秘密权:无形财产权
专利权
对于专利不适用的对象,不授予专利权
- 违法国家法律、社会公德、妨害公共利益的发明创造。
科学发现:客观世界存在但未揭示的规律、性质和现象等的认识。
科学发明与科学发现表述的概念是不一样的。
智力活动的规则和方法:人们进行推理、分析、判断、运算、处理、记忆等思维活动的规则和方法。
- 病的诊断和治疗方法
- 动物和植物品种,但动植物品种的生产方法可依照专利法规定授予专利权。
- 用原子核变换方法获得的物质。
授予专利权的条件
- 新颖性
- 创造性
- 实用性:发明或实用新型能够制造或使用,且能够产生积极的效果。
专利的申请
- 专利申请权
- 专利申请人:公民、法人、组织
- 职务发明创造的单位
- 非职务发明创造的专利申请人为完成发明创造的发明人或设计人
- 共同发明创造的专利申请人是共同发明人或设计人或其所属单位
- 委托发明创造的专利申请人为合同约定的人
- 受让人
- 专利申请原则
- 一份申请一项发明
- 最先申请原则
- 专利申请日(关键日)
- 专利申请受理代办处收到完整专利申请文件的日期。
- 申请文件为邮寄的,以寄出的邮戳日为申请日。
专利申请审批
- 初步审查:经初步审查认为符合本法要求的,自申请日起满18个月,即行公布(公布申请)。
自申请日起三年内,专利局可根据申请人随时提出请求,对其申请进行实质审查。
实质审查:对申请专利的新颖性、创造性、实用性等依法审查的法定程序。
实用新型和外观设计专利申请只进行初步审查,不进行实质审查。