数据库笔记（佛脚版）¶

数据库系统基本概念¶

数据管理技术的发展¶

数据库系统:

对数据集中控制, 统一管理
数据结构化是数据库主要特征之一, 是数据库与文件系统的根本区别

数据库系统数据管理特点:

「记忆」结构化、冗余小、独立、统一控制、数据项

不仅描述数据本身, 还描述数据之间的联系, 使整个组织的数据结构化
数据冗余度小, 易扩充
数据独立性
统一的数据控制: 安完并恢
数据的最小存取单位是数据项

数据模型¶

主要目标: 集成数据的表示

数据模型的两个层次: 现实世界业务 $\rightarrow$ 信息世界信息 (概念模型) $\rightarrow$ 机器世界数据 (数据模型)

概念模型¶

ER 图

数据模型¶

三要素:

数据结构 (静态特性) - 描述对象和对象之间的关系
数据操作 (动态特性) - 增删改查
完整性约束

三类数据模型: 层次模型 (树), 网状模型 (网), 关系模型 (二维表)

根本区别是数据结构不同, 即数据联系的表示方式不同

数据库系统结构¶

主要目标: 统一管理下的数据共享

三级模式, 两级映像

数据独立性: 应用程序与数据结构之间相互独立

物理独立性: 应用程序不关心数据在物理层次上的存储方式;
逻辑独立性: 应用程序不关心数据的逻辑结构的变化.

DBMS 的功能:

「记忆」定义, 存取, 运行, 数据, 维护

数据库定义功能
提供 DDL 语言描述外模式、模式、内模式
模式翻译程序把源模式翻译成目标模式, 存入数据字典中
数据存取功能: 增删改查
数据库运行管理
并发控制、存取控制、完整性约束条件检查和执行, 日志组织和管理, 事务管理和自动恢复
数据组织、存储和管理
数据库的建立和维护功能

DBMS 的组成:

语言编译处理程序
系统运行控制程序
系统建立和维护程序
数据字典

数据字典: 由一系列表组成, 存储着数据库的信息, 包括数据库的三级模式、用户名表、用户权限等.

关系模型¶

基本概念¶

关系: $D_1 \times D_2 \times \cdots \times D_n$ 的子集称为在域 $D_1, D_2, \cdots, D_n$ 上的关系, 记作 $R(D_1, D_2, \cdots, D_n)$

关系的性质:

「记忆」无子一换 (五子棋连成, 换得成功, 编不下去了...)

唯一性: 任意两个元组不能完全相同
无序性: 关系中元组的顺序是无关紧要的
原子性: 关系中每个分量必须是原子值, 不可再分
每一列的分量来自同一域, 列的顺序可以互换

关系数据模型¶

数据结构¶

实体及实体之间的联系用数据结构 “关系” 来表示.

关系模式是对关系的描述, 形式化表示: $R(U, D, dom, F)$

$dom$: 属性向域的映像集合
$F$: 属性间数据依赖关系集合

数据操作¶

集合操作

关系数据操作的基础是关系运算, 关系运算的方式有代数方式和逻辑方式.

完整性约束¶

关系运算: 关系代数¶

集合运算: 同类关系具有相同的度 (列数一致) 并且属性值取自同一域; 同类的关系才能进行并差交

选取 (Selection): 选择关系 $R$ 中满足条件的元组: $\sigma_F(R)$

投影 (Projection): 选取若干属性列并自动删去重复行, 组成新的关系: $\Pi_A(R)$

连接 (Join): 从两个关系的笛卡尔积中选择满足条件 $\theta$ 的元组: $R \underset{X\theta Y}{\Join} S$

自然连接: 选取 $R \times S$ 中相同属性上值相等的元组, 并去掉重复的属性列

除法: $R(X, Y)$ 和 $S(Z)$ , $R \div S$ 先找到 $R$ 和 $S$ 属性相同的列, 候选结果是 $R$ 除开这些列, 然后看候选结果与 $S$ 的笛卡尔积, 如果全部在原 $R$ 内, 则候选结果正式选入.

查询 “全部” 用除法

关系数据语言¶

数据库数据语言¶

数据定义语言 (DDL), 包括模式 DDL, 内模式 DDL, 外模式 DDL
数据操纵语言 (DML, 控制增删改查)
联机交互方式下的 DML 称为自含式语言, 可独立使用, 适用于终端直接查询 $\rightarrow$ SQL
宿主语言方式下的 DML 称为嵌入式语言, 比如在 python 里写数据库查询
数据控制语言 (安完并恢)

特点¶

「记忆」一非集既 (SQL 的特点也可以这么答)

一体化: 融合增删改查功能
非过程化: 不需要知道底层细节
面向集合的存取方式
既可独立使用又可与主语言嵌套使用

SQL¶

概述¶

基本表: 实际存在的, 有文件存储

导出表:

视图 (View): 是虚表, 只在数据字典中存储视图的定义;
快照 (Snapshot): 某一时刻数据库中数据的静态副本

CREATE VIEW male_students AS
SELECT * FROM students WHERE gender='M';        -- 创建视图

CREATE TABLE female_students AS 
SELECT * FROM students WHERE gender='F';        -- 创建快照

CREATE MATERIALIZED VIEW female_students AS ... -- 快照

数据查询¶

(1) 基本结构:

SELECT 目标列 FROM 基本表/视图/快照 WHERE 检索条件

大体流程是根据 WHERE 条件从 FROM 的基本表中选出元组, 随后进行一些 GROUP, ORDER, 目标列投影, ...

(2) 投影:

SELECT 不会去除重复项, SELECT DISTINCT 消去重复行 (和 $\Pi$ 一样了)

(3) 排序:

SELECT * FROM students ORDER BY score;      -- 默认 ASC 升序
SELECT * FROM students ORDER BY score DESC; -- 降序

(4) 连表:

SELECT SN, CID, G FROM S, SC
WHERE S.SID=SC.SID AND SN='李华';

## 检索比小林分数高的同学姓名
SELECT x.name FROM students x, students y  -- 定义别名
WHERE x.score > y.score AND y.name='小林';

JOIN: INNER JOIN RIGHT OUTER JOIN FULL OUTER JOIN

SELECT s.name, c.name FROM students s 
INNER JOIN classes c ON s.class_id=c.id;

## OUTER JOIN 将主表作为结果集
SELECT s.name, c.name FROM students s
RIGHT JOIN classes c ON s.class_id=c.id;    -- 没有学生的班级也会显示

(5) 子查询嵌套:

如果子查询返回一组值, 则要加上 ANY 或 ALL ; 可以用 IN 代替 = ANY

(6) EXISTS:

SELECT name FROM students s WHERE EXISTS 
( SELECT * FROM classes c WHERE c.id=s.class_id AND c.name='一班' );

流程是 EXISTS 的 FROM (这里即 students) 表中的每个元组, 依次判断 EXISTS, 如果为 true, 则加入结果集

## 对每个学生, 不存在这样的课程, 学生没有选择这门课程
SELECT SN FROM S WHERE NOT EXISTS (
    SELECT * FROM C WHERE NOT EXISTS (
        SELECT * FROM SC WHERE SC.SID=S.SID AND SC.CID=C.CID
    )
);

NOT EXISTS 表达蕴涵:

## 至少选修了学生 S2 选修的全部课程的学生学号
## 对每个学生, 不存在这样的课程, S2 选修了而他没有选修
SELECT DISTINCT SID FROM SC SCX WHERE NOT EXISTS (
    SELECT * FROM SC SCY WHERE SCY.SID='S2' AND NOT EXISTS (
        SELECT * FROM SC SCZ WHERE SCZ.SID=SCX.SID AND SCZ.C=SCY.C)
    )
);

(7) 库函数:

COUNT([DISTINCT] 列名) SUM AVG MAX MIN

(8) 分组:

SELECT 目标列 FROM 基本表 WHERE 条件
GROUP BY 列名 [HAVING 分组条件];

(9) 字符串匹配:

SELECT name FROM students WHERE name LIKE '小_';

% 任意序列的 0 个或多个字符; _ 任意单个字符

数据定义¶

模式:

CREATE SCHEMA <模式名> <用户名>;
DROP SCHEMA my_schema <CASCADE|RESTRICT>;  
/* CASCADE: 内部的对象一同删除 */

基本表:

完整性约束:

NULL / NOT NULL / UNIQUE
PRIMARY KEY / FOREIGN KEY / CHECK

CREATE TABLE S(
    SID CHAR(5) NOT NULL UNIQUE,
    SN CHAR(20) NOT NULL,
    SA INT,
    PRIMARY KEY(SID),
    CHECK (SA >= 18 AND SA <= 45)
);

CREATE TABLE SC(
    SID CHAR(5) NOT NULL,
    CID CHAR(5) NOT NULL,
    G NUMBER(4, 2),
    PRIMARY KEY(SID, CID),
    FOREIGN KEY(SID) REFERENCES S(SID),
    FOREIGN KEY(CID) REFERENCES C(CID),
);

DROP TABLE <表名><CASCADE|RESTRICT>;

修改基本表:

ALTER TABLE <表名>
[ADD <新列名> <数据类型>[<完整性约束>]]
[ADD <表级完整性约束>]
[DROP <列名>]
[ALTER / MODIFY <列名> <数据类型>]

## S 表增加入学时间属性
ALTER TABLE S ADD enrollment DATE;
## 修改 SA 的数据类型
ALTER TABLE S MODIFY SA SMALLINT;

视图:

CREATE VIEW cs_student
AS SELECT SID, SN, SA FROM S WHERE SD = 'CS';

DROP VIEW <视图名>[CASCADE]

索引:

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

DROP INDEX <索引名>

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

数据更新¶

INSERT INTO students VALUES (11, 4, '小菜', 'M', 100);

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

DELETE FROM students WHERE id=11;
DELETE FROM SC;  -- 删除所有学生的选课记录

数据控制¶

「记忆」完事权

定义完整性约束条件
支持事务操作
提供安全控制功能: 授权 + 撤销权限

GRANT ALL PRIVILEGES ON DATABASE mydb TO user2;     -- 数据库的权限
GRANT INSERT, UPDATE ON orders TO user3;            -- 表的权限

REVOKE ALL PRIVILEGES ON DATABASE mydb FROM user2;  -- 撤销

数据库保护¶

安全性控制¶

安全性含义¶

数据库的安全性: 是指保护数据库以防止不合法的使用所造成的数据泄漏、更改和破坏. 包括两个方面的含义

向授权用户提供可靠的信息服务
拒绝对数据的非授权存取访问请求, 保证数据的可用性、完整性和一致性

安全性控制¶

「记忆」用存审视加

用户标识与认证 (鉴别)
系统提供的最外层安全保护措施
标识是指系统采用一定的方式标识其用户 / 应用程序的身份
认证是指登录时判断其是否为合法的授权用户
常用的方法是采用用户名和口令
存取控制
确保合法用户按照指定的权限使用 DBMS 和访问数据, 主要包括两个部分:
用户权限定义: 将用户权限记录到数据字典中, 形成安全规则或授权规则
合法权限检查: 用户发出数据库操作请求后, DBMS 根据安全规则进行合法权限检查, 决定是否接受用户的操作请求
用户权限定义和合法权限检查机制一起组成了 DBMS 的安全子系统
审计: 把用户对数据库的所有操作都自动记录下来放入审计日志中
视图机制: 为不同的用户定义不同的视图, 将用户对数据的访问限制在一定的范围内
加密: 将原始数据变换为密文, 防止数据库中数据在存储和传输中失密

存取控制:

自主存取控制: 比较灵活

通过 GRANT 和 REVOKE 实现
SQL 可以授予用户两类权限:
用户级: 与整个数据库有关, 大概有 CREATE SESSION / TABLE / VIEW
关系级: 与关系或视图有关, 大概是 UPDATE / SELECT/ ALL
加上 WITH GRANT OPTION 表示允许被授权的用户转授

强制存取控制 (MAC): 每个数据库对象 (客体) 被标识以一定的密级, 每个用户 (主体) 被授予某级别的许可证, 对任意对象, 只有具有合法许可证的用户才可以读 / 取

完整性控制¶

完整性含义¶

数据完整性是指数据的正确性和相容性

正确性是指数据应具有合法的类型, 并在有效的取值范围之内
相容性是指表示同一个事实的两个数据应该相同

完整性约束条件¶

施加在数据库数据之上的语义约束条件称为数据库完整性约束条件, 作用的对象可以是: 列、元组、关系

关系模型中的三种完整性约束条件:

实体完整性. 属于关系约束
参照完整性. 属于关系约束
用户自定义完整性. 作用对象是列和元组

完整性约束可分为静态约束和动态约束

静态约束: 数据库在每一确定状态数据对象所应满足的约束条件
动态约束: 数据库从一种状态转变为另一种状态时, 新、旧值之间所应满足的约束条件

完整性约束条件按照完整性检查的时机分为:

立即执行约束
延迟执行约束: 在整个用户事务执行完毕后, 再进行完整性约束的检查, 结果正确方能提交

完整性控制¶

「记忆」定检违

包括三个方面的功能:

定义: 提供定义完整性约束条件的机制
检查: 检查用户发出的操作请求是否违背了完整性约束条件
违约响应: 若违背了完整性约束条件, 则采取一定措施来保证数据的完整性

一条完整性规则可以用一个五元组 (D, O, A, C, P) 来描述

D (Data) 约束所作用的数据对象
O (Operation) 触发完整性检查的数据库操作
A (Assertion) 数据对象必须满足的断言或语义约束
C (Condition) 选择 A 作用的数据对象值的谓词
P (Procedure) 违反完整性规则时触发的过程

SQL 完整性相关支持:

CREATE TABLE 的 NULL / CHECK 等等
CREATE ASSERTION assertion_name CHECK (...)
触发器

CREATE TRIGGER after_star_material
AFTER INSERT ON stars
FOR EACH ROW
BEGIN
    -- 增加资料收藏量
    UPDATE materials
    SET star_count = star_count + 1
    WHERE id = NEW.material_id;
END;

关系数据理论¶

函数依赖¶

完全函数依赖, 记作: $X \overset{F}{\rightarrow} Y$ ; 部分函数依赖, 记作: $X \overset{P}{\rightarrow} Y$ ;

如果 $X \rightarrow Y (Y \not\subseteq X)$, $Y \not\rightarrow X, Y \rightarrow Z(Z \not\subseteq Y)$, 则称 $Z$ 对 $X$ 传递函数依赖 , 记作: $X \overset{T}{\rightarrow} Z$ .

数据依赖公理系统¶

Armstrong 公理系统¶

逻辑蕴涵: 在 $R \langle U, F \rangle$ 中, $X,Y$ 是 $R$ 的属性集合, 如果从 $F$ 中的函数依赖能够推出 $X \rightarrow Y$, 则称 $F$ 逻辑蕴涵 $X \rightarrow Y$

Armstrong 公理系统:

A1 自反律: 若 $Y \subseteq X \subseteq U$ , 则 $X \rightarrow Y$ 为 $F$ 所蕴含
A2 增广律: 若 $X \rightarrow Y$ 为 $F$ 所蕴含, 且 $Z \subseteq U$ , 则 $XZ \rightarrow YZ$ 为 $F$ 所蕴含
A3 传递律: 若 $X \rightarrow Y, Y \rightarrow Z$ 为 $F$ 所蕴含, 则 $X \rightarrow Z$ 为 $F$ 所蕴含

由 Armstrong 公理系统得到的三条推理规则:

合并规则: 由 $X \rightarrow Y, X \rightarrow Z$ 有 $X \rightarrow YZ$
伪传递规则: 由 $X \rightarrow Y, WY \rightarrow Z$ 有 $WX \rightarrow Z$
分解规则: 由 $X \rightarrow Y, Z \subseteq Y$ 有 $X \rightarrow Z$

定理: $$ X \rightarrow A_1A_2...A_k \iff X \rightarrow A_i(i=1,2,...k) $$

有效性和完备性:

有效性: 由 $F$ 出发根据 Armstrong 公理推导出来的每个函数依赖一定在 $F$ 所蕴含的函数依赖的全体之中
完备性: $F$ 所蕴含的函数依赖的全体中的每一个函数依赖, 必定可以由 $F$ 根据 Armstrong 公理导出

闭包 $F^+$¶

$F$ 的闭包 ($F^+$) : 为 $F$ 所逻辑蕴涵的函数依赖全体

属性集 $X$ 关于函数依赖集 $F$ 的闭包: $X_F^+ = \{A\ |\ X \rightarrow A\ 能由\ F\ 根据 \text{Armstrong} 公理导出\}$

$X_F^+$ 的计算:

初始化 $X_F^+ = X$
对于任意 $A \subseteq X_F^+$ , 如果 $F$ 中存在函数依赖 $A \rightarrow B$ , 那么 $X_F^+ \leftarrow X_F^+ \cup B$

最小依赖集 $F_m$¶

若函数依赖集 $F$ 满足:

右边单属性: $F$ 中任一函数依赖 $X \rightarrow A$, $A$ 必是单属性
无多余规则: $F$ 中不存在函数依赖 $X \rightarrow A$ 使得 $F$ 与 $F - \{X \rightarrow A\}$ 等价
左无冗余属性: $F$ 中不存在这样的 $X \rightarrow A$ , 在 $X$ 中有真子集 $Z$ 使得 $F$ 与 $F - \{X \rightarrow A\} \cup \{Z \rightarrow A\}$ 等价

则称 $F$ 为一个极小函数依赖集 / 最小依赖集 / 最小覆盖.

极小化得到 $F_m$:

右边单属性: 检查 $F$ 中的所有 $X \rightarrow Y$, 若 $Y = A_1A_2...A_k$, 则用 $\{X \rightarrow A_j\ |\ j=1,..., k\}$ 代替 $X \rightarrow Y$
左无冗余属性: 若 $X \rightarrow A$ 且 $X = B_1B_2...B_m$ , 则逐个考查 $B_i$, 若 $A \in (X-B_i)_F^+$ , 则以 $X - B_i$ 取代 $X$
从 $F$ 中减去 $X \rightarrow A$ 得到 $G$ , 如果 $A \in X_G^+$ , 则去掉 $X \rightarrow A$

范式¶

低一级范式的关系模式, 通过模式分解可以转换为若干个高级范式的关系模式的集合, 这一过程称为规范化

1 NF:

当一个关系只包含原子值这一约束时, 就满足 1 NF

满足原子值这一约束条件的关系称为规范化关系, 所以关系数据库都是规范化关系

2 NF:

若 $R \in 1 NF$, 且每个非主属性完全依赖于任何一个候选码, 则称 $R \in 2NF$

规范化: 投影分解, 从 1 NF 中消除非主属性对码的部分函数依赖

3 NF:

$R \langle U, F \rangle \in 1 NF$ 中, 若不存在这样的码 $X$, 属性组 $Y$ 及非主属性 $Z$ ($Y \not\subseteq Z$), 使得 $X \rightarrow Y, Y \rightarrow Z$ 成立, $Y \not \rightarrow X$ , 则称 $R \in 3 NF$

规范化: 2 NF; 每个非主属性都不传递依赖于 $R$ 的任何码

3 NF 的不完善: 没有限制主属性对码的部分、传递函数依赖

BCNF:

$R \langle U, F \rangle \in 1NF$, 若 $X \rightarrow Y$ 且 $Y \not\subseteq X$ 时 $X$ 必含有码 (就是 $X$ 为超码), 则 $R \langle U, F \rangle \in BCNF$

模式分解¶

无损连接性¶

「理解」拼好的表和原来一样

判定算法 1:

$\rho = \{R_1\langle U_1, F_1\rangle, R_2\langle U_2, F_2\rangle,..., R_k\langle U_k, F_k\rangle\}$ 是 $R \langle U, F \rangle$ 的一个分解. $U = \{A_1, A_2, ..., A_n\}$, $F = \{FD_1, FD_2, ..., FD_{t}\}$ , $FD_i$ 为 $X_i \rightarrow A_i$ ($F$ 是极小依赖集)

建立 $k$ 行 $n$ 列的表, 每一列对应一个属性 $A_i$, 每一行对应一个关系模式 $R_i$
若属性 $A_j \in U_i$ , 则在 $(i,j)$ 处填上 $a_j$ , 否则填上 $b_{ij}$
对每个 $FD_i$ , 找到 $X_i$ 所对应的列中具有相同值的那些行, 看这些行的 $A_i$ 列元素
若其中有 $a_i$, 则全部改为 $a_i$
否则全部改为 $b_{mi}$ , 其中 $m$ 是最小的行号
重复执行 (2), 直到
表中出现 $a_1, a_2, ... , a_n$ 的一行 $\Rightarrow$ 无损分解
表不再发生变化, 且没有一行为 $a_1, a_2, ... , a_n$ $\Rightarrow$ 有损分解

判定算法 2:

$R \langle U, F \rangle$ 的一个分解 $\rho = \{R_1 \langle U_1, F_1 \rangle, R_2 \langle U_2, F_2 \rangle\}$ 具有无损连接性的充要条件是 $U_1 \cap U_2 \rightarrow U_1 - U_2 \in F^+$ 或 $U_1 \cap U_2 \rightarrow U_2 - U_1 \in F^+$. 即 $R_1, R_2$ 的共同属性至少构成 $R_1, R_2$ 之一的候选码

保持函数依赖性¶

若 $F^+ = (\bigcup_{i=1}^{n}F_i)^+$ , 则称分解 $\rho$ 保持函数依赖.

判定方法: 记 $G = \bigcup_{i=1}^{n}F_i$, 现需判定 $F^+ = G^+$ , 首先看 $F \subseteq G^+$ , 逐一对 $F$ 中的函数依赖 $X \rightarrow Y$, 考察 $Y$ 是否属于 $X_{G^+}^+$

分解算法¶

达到 3 NF 且保持函数依赖¶

合成法:

对 $F$ 进行极小化处理 (仍记为 $F$ )
找出不在 $F$ 中出现的属性, 记为 $U_0$, 把它们构成关系模式 $R_0 \langle U_0, F_0 \rangle$ , 并把它们从 $U$ 中去掉 (仍记为 $U$ )
若有 $X \rightarrow A \in F$ 且 $XA = U$, 则 $\rho = \{R\}$ , 算法终止
按具有相同左部对 $F$ 进行分组, 设有 $k$ 组
每组函数依赖所涉及的全部属性形成属性集 $U_i$
此时 $\rho = \{R_1\langle U_1, F_1\rangle, R_2\langle U_2, F_2\rangle,..., R_k\langle U_k, F_k\rangle\}$ 构成 $R \langle U, F \rangle$ 的一个保持函数依赖的分解

达到 3 NF 且无损连接与保持函数依赖¶

设 $\rho$ 是 $R \langle U, F \rangle$ 的一个保持函数依赖的 3 NF 分解, $X$ 是 $R \langle U, F \rangle$ 的码

若有某个 $U_i$ 满足 $X \subseteq U_i$ , 则 $\rho$ 即为所求
否则令 $\tau = \rho \cup \{R^* \langle X, F_X \rangle\}$ , $\tau$ 即为所求

达到 BCNF 且无损连接¶

令 $\rho = R \langle U, F \rangle$
检查 $\rho$ 中各关系模式是否属于 BCNF, 若是, 则算法终止
设 $\rho$ 中 $R_i \langle U_i, F_i \rangle$ 不属于 BCNF
则存在函数依赖 $X \rightarrow A \in F_i^+ (A \not\in X)$ 且 $X$ 不是 $R_i$ 的码
将 $R_i$ 分解为 $\sigma = \{S_1, S_2\}$ , 其中 $U_{S_1} = XA, U_{S_2} = U_i - \{A\}$

候选码求解¶

「理解」候选码主要是看 $X_F^+$ 是否等于 $U$ , L 类和 N 类非常关键

关键点: 原始点和孤立点统称为关键点 (就是 L 类和 N 类)

单属性依赖集¶

求 $F$ 的最小依赖集 $F_m$
构造函数依赖图 $G$, 从 $G$ 中找出关键属性集 $X$
查看 $G$ 中有无独立回路, 若无则输出 $X$ 即为 $R$ 的唯一候选码; 否则进入 (4)
从各独立回路中取一节点对应的属性与 $X$ 组成一个候选码, 重复直到取完所有的组合

多属性依赖集候选码¶

数据库设计¶

设计概述¶

需求分析
调研应用环境, 收集基础数据
概念结构设计
形成概念模型, 可用 E-R 图表示
逻辑结构设计
将概念结构转换为某个 DBMS 所支持的数据模型, 并进行优化
再将得到的逻辑结构转换成 DBMS 能处理的模式、子模式 (就是建立表和视图)
物理结构设计
在物理设备上的存储结构和存取方法
分为: (1) 确定数据库的内模式; (2) 对物理结构进行时间与空间效率的评价
数据库实施
是建立数据库的过程
用 DBMS 的 DDL 描述三级模式, 并调试产生目标模式
开发应用程序, 组织数据入库并试运行
数据库的运行和维护
数据库正式运行后, 由 DBA 对数据库进行维护

需求分析¶

调查重点是数据和处理, 包括:

信息要求: 系统中所涉及的数据及数据之间的联系
处理要求: 用户要完成什么处理功能, 对性能的要求
安全性与完整性要求

分为两个阶段:

调查用户的实际需求, 与用户达成共识
分析、表达用户的需求
数据流图表达数据和处理之间的关系
数据字典描述系统中的各类数据 (例如: 设计报告里面的表格)

概念结构设计¶

实体模型的调整原则:

属性不能有别的属性
属性不能与实体有联系
实体和属性保持 1:1 或 n:1 的联系

集成局部 E-R 图要: 1. 解决各分 E-R 图之间的冲突, 合并成初步 E-R 图 2. 消除冗余, 生成基本 E-R 图

冲突:

属性冲突: 属性的类型、取值集合不同 $\rightarrow$ 协商解决
命名冲突: 属性名、实体名、联系名的同名异义, 异名同义 $\rightarrow$ 统一命名
结构冲突:
同一对象在一个图里面是实体, 在另一个里面是属性 $\rightarrow$ 把属性变为实体 / 把实体变为属性
- 同一实体在不同分 E-R 图中属性个数、次序不同 $\rightarrow$ 取并集
- 实体间的联系在不同分 E-R 图中呈现不同类型 $\rightarrow$ 根据语义综合或调整

消除冗余:

初步 E-R 图中可能出现冗余数据和冗余联系, 两种方法消除冗余:

分析法
规范化方法: 把每对 n:1 、1:1 、n:m 的联系表示为实体码之间的函数依赖 $X \rightarrow Y$ , 计算最小覆盖集 $F_m$ , 然后判断 $F - F_m$ 中的联系是否冗余

逻辑结构设计¶

把概念结构转换为选用的 DBMS 所支持的数据模型 (主要是关系模型)

E-R 图 $\rightarrow$ 关系模型
实体可以形成表; 联系也要形成表; 具有相同码的关系可以合并
关系模式规范化
关系模型优化
水平分解
垂直分解: 形成若干子关系模式, 必须保证无损连接性和保持函数依赖
用户子模式

物理结构设计¶

确定数据在物理设备上的存储结构与存取方法

存取方法:

索引
索引记录 / 索引项包括: 索引域 (就是属性) + 指针 (属性值对应的记录的具体块号)
聚集
把某个属性/组值相同的记录集中存放在连续的物理块, 能够提高该属性的查询速度; 一个关系只能参加一个聚集
原则:
- 经常进行连接操作的关系可建立聚集; 单个关系的某组属性经常进行相等比较; 关系的某个属性组值重复率高
- 建立与维护聚集系统开销很大, 对于更新操作远远多于连接操作的关系不应使用聚集方法
Hash
通过 Hash 函数把记录关键字转换成地址

存储管理和索引¶

物理存储系统¶

数据库存储在磁盘上, 由 DBMS 管理内存与外存数据的交换, 最小化磁盘存取次数.

物理存储管理器 (或者叫磁盘管理器) 是 DBMS 的最底层, 负责数据在磁盘和主存之间的移动

数据的存储结构¶

文件组织结构¶

数据库的表被映射为文件, 文件在逻辑上是记录的序列
一个块可以包含多个记录; 每条记录存在于单个块中, 记录由块号和在块中的位置唯一标识

文件所占磁盘块的分配:

连续分配
链接分配
按簇分配: 连续和链接的结合, 簇是连续的几个块, 簇之间指针连接
索引分配: 索引块中存放指向块的指针

页 / 块的结构:

页是存储分配和数据传输的单位
最常用分槽页 (slot) 结构: Header + Tuples

记录的结构:

Header (例如元组的加锁信息) + 实际数据

文件中记录的组织方式¶

「理解」记录在逻辑上是有顺序的, 但是在物理上未必. 记录如何在文件所拥有的磁盘块上放置

堆 (Heap): 记录可以存放在文件空间中的任何位置
链表方式
页目录方式: DBMS 维护特殊页保存文件中的数据页的位置, 并记录每个页中空槽数
顺序 (Sequential): 记录按搜索码顺序排列
搜索码: 用于在文件中查找记录的属性
索引 (Indexing):
索引表: 记录的关键字 $\leftrightarrow$ 记录的存储地址, 关键字要有序
散列 (Hashing): 在搜索码上的 hash 函数, 计算出记录在文件中实际的块
聚集 (Clustering): 把相似属性值的记录存储于连续的块中, 以最小化 I/O 次数
聚集码: 是一些属性, 定义了哪些记录会被存储到一起
多表聚集: 加快连接查询, 但会使单个表的访问变慢

缓冲区管理¶

缓冲区: 主存中可以存储磁盘块副本的区域

缓冲区管理器: 负责缓存空间分配, 内外存交换; 提供封锁系统 (共享锁和排他锁)

索引¶

索引文件由索引记录 (或称索引项) 构成, 索引记录包含:

索引域 (搜索码): 存储数据文件中一个或一组域 (属性)
指针: 指向索引域值为 $K$ 的记录所在磁盘块的地址

索引将表中的部分属性进行排序, 使得 DBMS 的执行引擎利用这些属性快速进行表的访问.

分类¶

顺序索引 vs. 哈希索引

顺序索引 (排序索引): 索引项是排序的. 又分为稠密索引和稀疏索引
哈希索引: 索引项使用索引域上的 hash 函数确定位置

聚集索引 vs. 非聚集索引

聚集索引 (主索引): 索引域值的排列顺序与记录在文件中的排列顺序一致
非聚集索引 (辅助索引)

稠密索引:

文件中的每个搜索码值都有一个索引项
非聚集索引都是稠密索引

稀疏索引:

部分搜索码值有索引项
当文件记录以索引域排好序时可以采用此种方法; 查找索引域为 $k$ 的记录地址时, 先找索引表中小于 $k$ 的最大索引域值, 然后根据其定位的地址顺序在文件中找

多级索引:

对索引文件建立稀疏索引

B 树和 B+ 树¶

B 树:

每个节点的关键字和指针个数都有范围限制
根节点有 $\left [ 2,n \right ]$ 个子节点
中间节点有 $\left [ \frac{n}{2}, n\right ]$ 个子节点
叶节点有 $\left [ \frac{n-1}{2}, n-1 \right ]$ 个记录指针. 结构是: $key$ + 指向实际记录的指针
所有叶节点都在同一层

B+ 树:

树中所有 $key$ 都在叶节点.
节点结构:
每个节点最多包含 $n-1$ 个搜索码 (即关键字值) $K_1, K_2, ... K_{n-1}$ 以及 $n$ 个指针 $P_1, P_2, ... P_n$

Hash 索引¶

Hash(索引域) 得到该域对应的索引项位置

查询¶

关系查询处理的四个阶段:

「记忆」分检优执

查询分析: 对 SQL 语句进行词法分析、语法分析, 并检查语法错误
查询检查: 语义分析, 安全性检查, 完整性检查; 将 SQL 转化为关系代数表达式
查询优化: 代数优化和物理优化
查询执行: 生成查询计划的代码并执行

查询的实现¶

选择¶

全表扫描法
索引扫描法

排序¶

假设要对表排序, 如果能完全放进内存, 可以使用快排; 如果放不下, 则采用外排序-归并

连接¶

SELECT * FROM S, SC WHERE S.SNO=SC.SNO;

(1) 嵌套循环法

对外层循环 (S) 的每个元组, 检查内层循环 (SC) 的每个元组, 是否满足连接条件, 满足条件则连接并加入结果集.

如果连接使用的缓冲区有 $k$ 块, 分 $k-1$ 块给外表 $r$, 1 块给内表 $s$, 则存取块数为 $b_r + \frac{b_r}{k-1} \times b_s$ ($b$ 为表的磁盘块数目)

$b_r$ 是外表的 I/O 次数
假设现在外表的 $k-1$ 块已经在缓冲区了, 内表加载 $b_s$ 次就能完成这些外表元组的连接; 缓冲外表一共加载 $\frac{b_r}{k-1}$ 次

应选择较小表作为外表

(2) 索引连接法

在内层 SC 表上已经建立了 SNO 的索引, 则对 S 的每个元组, 由 S.SNO 值来查找相应的 SC 元组.

如果两个表都有索引, 则以元组较少的作为外表, 代价最小.

(3) 排序-合并法

首先对 S 和 SC 表按连接属性 SNO 排序; 取 S 表中第一个 SNO, 依次扫描 SC 表中具有相同 SNO 的元组, 并进行连接; 然后再移动 S 的指针...

访问块数: $b_r + b_s$

只能用于等值连接或自然连接

(4) hash join 法

hash 函数 $h$ 将连接属性映射到 $\{0,1,...,n\}$ 上, 将外表 $r$ 的元组划分到了 $r_0, r_1, ..., r_n$ 这些桶中; 同理也将内表 $s$ 的元组分到 $s_0, s_1, ..., s_n$ 这些桶中. 此时只需要将 $s_i$ 和 $r_i$ (即有同样的 hash 值) 中的元组相比较.

其他运算¶

去重: 排序 / 哈希, 然后只保留一个数据

表达式的执行¶

物化:

按次序每次只执行一个运算, 运算结果被物化到一个临时关系中, 这些临时关系一般需要写到磁盘
适用性广泛, 但临时表的读写代价大

流水线:

同时执行多个运算, 将结果传递给下一个运算
不用在磁盘存储临时表, 但对排序等运算不适用

查询优化¶

查询优化的结果是生成查询计划

代数优化¶

等价变换规则:

$\Join$ 和 $\times$ 的交换律
$\Join$ 和 $\times$ 的结合律
投影的串接定律: $\Pi_{A_1, A_2, ..., A_n}(\Pi_{B_1, B_2, ..., B_m}(E)) \equiv \Pi_{A_1, A_2, ..., A_n}(E)$, 其中 $\{A_1, A_2, ..., A_n\} \subseteq \{B_1, B_2, ..., B_m\}$
选择的串接定律: $\sigma_{F_1}(\sigma_{F_2}(E)) \equiv \sigma_{F_1 \wedge F_2}(E)$
选择与投影的交换律: $\sigma_F(\Pi_{A_1, A_2, ..., A_n}(E)) \equiv \Pi_{A_1, A_2, ..., A_n}(\sigma_F(E))$
选择与笛卡尔积交换律:
如果 $F$ 只有 $E_1$ 的属性, 则 $\sigma_F(E_1 \times E_2) \equiv \sigma_F(E_1) \times E_2$
$F = F_1 \wedge F_2$, 且 $F_1$ 只有 $E_1$ 的属性, $F_2$ 只有 $E_2$ 的属性, 则 $\sigma_F(E_1 \times E_2) \equiv \sigma_{F_1}(E_1) \times \sigma_{F_2}(E_2)$
选择与并的分配律: $\sigma_F(E_1 \cup E_2) \equiv \sigma_F(E_1) \cup \sigma_F(E_2)$
选择与差的分配律: $\sigma_F(E_1 - E_2) \equiv \sigma_F(E_1) - \sigma_F(E_2)$
选择对自然连接的分配律: $\sigma_F(E_1 \Join E_2) \equiv \sigma_{F}(E_1) \Join \sigma_{F}(E_2)$
投影与笛卡尔积的分配律: $\Pi_{A_1, ..., A_n, B_1, ..., B_m}(E_1 \times E_2) \equiv \Pi_{A_1, ..., A_n}(E_1) \times \Pi_{B_1, ..., B_m}(E_2)$
投影与并的分配律: $\Pi_{A_1, A_2, ..., A_n}(E_1 \cup E_2) \equiv \Pi_{A_1, A_2, ..., A_n}(E_1) \cup \Pi_{A_1, A_2, ..., A_n}(E_2)$

查询树的启发式优化:

选择运算尽早执行 (最重要)
投影运算尽早执行
把投影运算和选择运算同时进行
把投影同其前或其后的双目运算结合起来
把某些选择同在它前面要执行的笛卡尔积结合起来成为一个连接运算
找出公共子表达式, 把公共子表达式的结果写入中间文件, 重复使用

查询树优化算法:

把形如 $\sigma_{F_1 \wedge F_2}(E)$ 变换为 $\sigma_{F_1}(\sigma_{F_2}(E))$
把选择运算尽量移到叶端
把投影运算尽量移到叶端
把选择和投影的串接合并成单个选择、单个投影或一个选择后跟一个投影的形式, 使尽可能多的选择和投影同时执行
如果笛卡尔积后还需按连接条件进行选择操作, 可将两者组合成连接操作
对每个叶节点加必要的投影操作, 以去掉对查询无用的属性

物理优化¶

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

(1) 基于规则的启发式优化方法

选择操作:
对于小关系, 使用全表顺序扫描
对于大关系, 可以采用索引扫描法
连接操作:
如果两个表都已经按照连接属性排序——排序-合并法
如果一个表在连接属性上有索引——索引连接法
如果连接属性上未排序且未建索引, 且其中一个表较小——hash join 法
最后可选用嵌套循环法, 并选择较小的表为外循环表

(2) 基于代价估算的优化方法: 利用数据库的统计信息计算各种操作算法的执行代价, 选出具有最小代价的执行计划

事务¶

事务的概念¶

事务 (Transaction) 是用户定义的数据库操作序列, 这些操作要么都做, 要么都不做, 是一个不可分割的工作单位.

「记忆」ACID

原子性 (Atomicity): 事务中包括的所有操作要么都做, 要么都不做
一致性 (Consistency): 事务执行的结果必须是使数据库从一个一致性状态, 变到另一个一致性的状态
隔离性 (Isolation): 一个事务的执行不能被其它事务干扰
持久性 (Durability): 一个事务一旦提交之后, 它对数据库的影响必须是永久的; 其它操作或故障不应该对其执行结果有任何影响

事务的 ACID 特性有可能遭到破坏, 主要有两种情况:

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

措施: 利用数据库并发控制机制以及数据库恢复机制保证事务的特性不被破坏, 从而保证数据库数据的正确、有效.

原子性由恢复机制实现
一致性是由事务的原子性保证的
隔离性通过并发控制机制实现
持久性通过恢复机制实现

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

SQL:

事务开始: BEGIN TRANSACTION
事务结束: COMMIT 提交事务, 正常结束; ROLLBACK 撤消全部更新, 回滚到事务开始时状态, 非正常结束

提交后事务的所有修改必须被保留

数据库恢复技术¶

数据库恢复是通过数据库管理系统的恢复子系统完成的.

数据库恢复子系统的意义:

保证事务的原子性: 事务非正常终止时进行回滚
当系统发生故障以后, 数据库能够恢复到正确状态

数据库恢复的基本原理为冗余.

故障的种类¶

事务故障:

可预期的: 事务根据内部的测试条件, 确定是否回滚
不可预期的: 不能由应用程序处理的事务故障. 如死锁, 运算溢出, 违反完整性规则等

系统故障:

造成系统停止运行的任何事情, 系统要重新启动. 如硬件错误, 操作系统故障, 停电等
这类故障打断所有正在运行的事务, 使事务都异常中止, 但不会破坏数据库 (因为在磁盘上存着的)

介质故障:

指外存故障. 如磁盘损坏
破坏数据库, 并影响正在存取这部分数据的所有事务

计算机病毒:

人为对数据进行非法修改

恢复¶

(1) 数据转储

DBA 定期地将整个数据库复制到磁带或另一个磁盘的过程, 备用的数据被称为后备副本或后援副本.

两种转储状态:

静态转储: 系统中无事务运行时进行转储, 并且转储过程中不允许对数据库进行任何存取、修改
优点: 保证副本的数据一致性
缺点: 降低了数据库的可用性 (因为被转储占用了)
动态转储: 转储期间允许对数据库进行存取或修改
优点: 不影响数据库的可用性
缺点: 不能保证副本上的数据正确、有效. 还必须把转储期间各事务对数据库的修改记录下来, 建立日志文件. 后援副本加上日志文件就能把数据库恢复到某一时刻的正确状态

两种转储方式:

海量转储: 每次转储全部数据库
增量转储: 每次只转储上一次转储后更新过的数据

(2) 日志文件

日志是用来记录事务对数据库更新操作的文件. 有两种格式: 以记录为单位或以数据块为单位.

以记录为单位: 记录哪一条记录怎么变了; 以数据块为单位: 直接记录修改前后整页是怎样的

日志文件的作用:

事务故障和系统故障恢复必须使用日志文件
动态转储方式, 必须同时建立后备副本和日志文件

日志文件的写入规则:

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

恢复策略¶

事务故障的恢复: UNDO

强行回滚, 撤消已做的修改
具体步骤: 反向扫描日志文件, 查找该事务的更新操作; 对该事务的更新操作 (插入、删除、修改) 执行逆操作; 如此处理下去，直到读到该事务的开始标志

系统故障的恢复: UNDO + REDO

系统故障造成数据库不一致状态的原因有两个:
未完成的事务对数据库的更新可能已经写入数据库 (磁盘) $\Rightarrow$ UNDO
已提交事务对数据库的更新可能还留在缓冲区未写入数据库 $\Rightarrow$ REDO
具体步骤: 正向扫描日志文件, 找出故障发生前已经提交的事务, 将其事务加入重做队列 (REDO). 同时找出故障发生时尚未完成的事务, 将其事务标识记入撤销队列 (UNDO). 随后进行 UNDO 和 REDO

介质故障的恢复:

装入数据库后备副本. 对于动态转储的副本, 还需要装入转储开始时刻的日志文件副本.
装入转储以后的日志文件副本, 重做已经完成的事务

检查点¶

在检查点之前提交的事务, 在数据库恢复时不必重做

在日志文件中增加检查点 (checkpoint) 记录
包括: 建立检查点时刻所有正在执行的事务清单; 这些事务最近一个日志记录的地址
系统增加重新开始文件, 用来记录检查点在日志文件中的地址

写检查点前, 将所有缓存写入磁盘; 恢复时只对检查点之后的事务进行 UNDO 和 REDO (正向扫描)

数据库镜像¶

由 DBMS 自动保证镜像数据库与主数据库的一致性

并发控制¶

并发¶

多个事务同时存取同一数据时, 如果不加控制可能读到或写入不正确的数据, 破坏数据库的一致性.

丢失更新: 事务 1 的更新被事务 2 覆盖掉了
脏数据的读出: 读到了还没提交, 将来可能撤销的数据
不能重复读: 事务两次读同一记录结果不同

并发控制的方法: 封锁¶

并发控制的目标: 合理调度并发事务, 保证数据的一致性.

主要方法是封锁 (locking):

排它锁 (X 锁, exclusive lock)
共享锁 (S 锁, share lock)

封锁协议¶

一级封锁协议:

事务 T 在修改数据 R 之前必须对其加 X 锁, 直到事务结束才释放 (结束包括正常的 COMMIT 和非正常的 ROLLBACK)
可以防止丢失更新

二级封锁协议:

一级封锁协议 + 事务 T 在读取数据 R 之前必须先对其加 S 锁, 读完后即可释放 S 锁
可以进一步防止读脏数据

三级封锁协议:

一级封锁协议 + 事务 T 在读取 R 之前必须对其加 S 锁, 直到事务结束才释放
再进一步保证了可重复读

活锁¶

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

死锁¶

(1) 预防死锁

一次封锁法: 每个事务将其所有要使用的数据全部加锁
顺序封锁法: 预先对数据对象规定一个封锁顺序; 实现难度大

(2) 死锁的检测和解除

超时法: 事务的等待时间超过了规定的期限, 就认为发生了死锁
等待图法: 出现回路则表示有死锁

(3) 死锁恢复

选择一个处理死锁代价最小的事务, 将其 UNDO, 即释放其持有的锁; 之后再恢复

事务的串行化调度¶

可串行化调度: 多个事务的并发执行是正确的, 当且仅当其结果与按某一次序串行执行时的结果相同.

可串行化调度判定的充分条件:

「理解」原来的并发操作可以变换到按事务顺序执行的操作

一个调度 $S_c$ 在保证冲突操作次序不变的情况下, 交换两个事务不冲突操作的次序, 得到另一个串行调度 $S_c'$, 则调度 $S_c$ 为冲突可串行化调度
冲突操作: 不同事务对同一数据的读-写和写-写操作. E.g: 事务 $T_i$ 读 $x$, $T_j$ 写 $x$, 则记为 $R_i(x)$ 和 $W_j(x)$
冲突可串行化调度一定是可串行化调度

两段锁协议可保证并发事务的可串行性 (充分条件):

在对任何数据进行读、写操作之前, 事务首先要获得对该数据的封锁 $\Rightarrow$ 扩展阶段
在释放一个封锁之后, 事务不再获得任何其它封锁 $\Rightarrow$ 收缩阶段

数据库笔记（佛脚版）¶

数据库系统基本概念¶

数据管理技术的发展¶

数据模型¶

概念模型¶

数据模型¶

数据库系统结构¶

关系模型¶

基本概念¶

关系数据模型¶

数据结构¶

数据操作¶

完整性约束¶

关系运算: 关系代数¶

关系数据语言¶

数据库数据语言¶

特点¶

SQL¶

概述¶

数据查询¶

数据定义¶

数据更新¶

数据控制¶

数据库保护¶

安全性控制¶

安全性含义¶

安全性控制¶

完整性控制¶

完整性含义¶

完整性约束条件¶

完整性控制¶

关系数据理论¶

函数依赖¶

数据依赖公理系统¶

Armstrong 公理系统¶

闭包 \(F^+\)¶

最小依赖集 \(F_m\)¶

范式¶

模式分解¶

无损连接性¶

保持函数依赖性¶

分解算法¶

达到 3 NF 且保持函数依赖¶

达到 3 NF 且无损连接与保持函数依赖¶

达到 BCNF 且无损连接¶

候选码求解¶

单属性依赖集¶

多属性依赖集候选码¶

数据库设计¶

设计概述¶

需求分析¶

概念结构设计¶

逻辑结构设计¶

物理结构设计¶

存储管理和索引¶

物理存储系统¶

数据的存储结构¶

文件组织结构¶

文件中记录的组织方式¶

缓冲区管理¶

索引¶

分类¶

B 树和 B+ 树¶

Hash 索引¶

查询¶

查询的实现¶

选择¶

排序¶

连接¶

其他运算¶

表达式的执行¶

查询优化¶

代数优化¶

物理优化¶

事务¶

事务的概念¶

数据库恢复技术¶

故障的种类¶

恢复¶

恢复策略¶