2024秋数据库理论复习

2024秋数据库系统原理

Posted Jan 3, 2025 Updated Jan 7, 2025

By Zhixin Cai

69 min read

2024秋数据库理论复习

1 概述

发展过程

考试考过

人工管理→文件系统→数据库系统（集成的、共享的）

考试考过

特点：

数据结构化：数据库与文件系统的根本区别，描述数据之间的联系
数据独立性：物理独立性、逻辑独立性。提供 映像（转换） 功能
数据冗余度小
最小存取单位：数据项

集成数据的表示

概念模型（E-R 法）

实体
属性
码（Key）
域（Domain）
实体型：表示一类实体
联系：实体型之间的联系，是实体之间的相互关联。
- 名称
- 类型：一对一，一对多，多对多
- 可以具有属性

E-R 图：

实体（长方形）
属性（椭圆形）
联系（菱形）

数据模型

三要素：

数据结构
由描述数据对象以及对象之间联系的一组概念组成。包括描述对象的类型、内容、性质的概念，和 对象之间联系 的概念（如关系）。是数据 静态特性 的表述。
数据操作
对数据库中各数据对象的实例允许执行的操作集合，包括 操作和操作规则。是数据 动态特性 的表述，主要有 检索和更新 两大类操作。
数据的约束条件
完整性规则：数据和联系的所有制约规则。

数据模型分类：

层次模型（树结构，有向树，节点表示实体型，连线表示一对多联系）
网状模型（图结构，有向图，节点表示实体型，连线表示一对多联系）
关系模型（二维表，要求关系中每个分量是不可分的数据项）

系统结构

数据独立性：应用程序与数据结构之间相互独立。即使数据库逻辑结构变化，程序可以不变。

数据库系统体系结构特征：三级模式、两级映像（模式、外模式、内模式、两级映像）

模式：数据库中数据的逻辑结构和特性的描述，是所有用户的公共数据视图。三级模式的核心，不涉及数据物理存储细节，与具体的应用程序无关

外模式：某个用户或应用的数据视图，与某一应用有关的逻辑表示

内模式：存储模式，数据在数据库系统内部的表示，描述数据的物理结构和存储方式

两级映像：某个模式改变，改变映像即可，可以避免其他模式的修改。

考试考过

逻辑独立性：模式改变，外模式可以不变（外模式与模式分开）
物理独立性：内模式改变，模式可以不变（模式与内模式分开）

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

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$ 是关系的度。

关系可以用二维表表示，每一行是一个元组，每一列是一个域，每个列附加一个名称称为“属性”，属性的名字是唯一的。

性质：

列是 同质的，每一列中的分量来自于同一个域，是同类型数据
不同的列可以来自于同一个域，但每个列的属性名不同
列次序和行次序都可以互换
每个分量必须是 不可再分的数据，满足这一条件的关系称作满足第一范式（1NF）的

考试考过

三个组成部分：关系数据结构、关系操作集合、关系完整性约束

关系模型

基本概念
码（Key，键）
- 候选码：关系中的某一个 属性组 唯一标识一个元组，并具有 最小性（去掉其中某个属性，就不能唯一标识元组），则称这个属性组为候选码
- 主码：如果有多个候选码，选其中一个为主码
主属性：码中的各个属性称为主属性。
关系模式
关系 $R(U, D, dom, F)$
- $U$：属性名的集合
- $D$：域的集合
- $dom$：属性名向域的映射（每个属性对应一个域）
- $F$：属性间相互依赖关系集合
关系模式是稳定的，相当于关系数据库的型；关系是动态的，相当于关系数据库的值。
关系模型的 语义约束
作业题
- 实体完整性：必须有主码，且主码值不可以为空。即主属性不能为空。
- 参照完整性：参照关系的外部码对应的元组值一定可以在目标关系中找到对应的值。
  - 外部码（外键）
    关系 R 的一个非码的属性组 F 是关系 S 的主码，那么 F 是 R 的外部码，R 为参照关系， S 为被参照关系或目标关系。R 和 S 不一定是不同的关系。
    目标关系的主码和参照关系的外部码必须定义在同一个域上。
- 用户定义的完整性
关系数据的操作方式：集合操作。操作的基础：关系运算。关系运算方式：代数方式（关系代数），逻辑方式（关系演算：元组关系演算，域关系演算）。
- 关系代数（传统集合运算）
  除笛卡尔积外，要求运算的两个关系是 同类关系，即度相同，且对应的属性值的域也要相同。
  - 交、并、差
    同集合运算。
  - 广义笛卡尔积
    $R \times S$ 的集合是：前 $n$ 个分量是 $R$ 中的元组，后 $m$ 个分量是 $S$ 中的元组。
  - 选取
    在关系 $R$ 中选取满足给定条件 $F$ 的元组。
    $\sigma_F(R) = { t \mid t \in R, F(t) = ‘真’ }$
  - 投影
    在关系 $R(U)$ 中选取若干列 $A$，删除这些列里重复的行，得到新的关系。
    $\Pi_A(R) = { t[A] \mid t \in R, A \subseteq U }$
  - 连接
    选取连接属性 $X, Y$，在 $R \times S$ 中选取出 $X$ 和 $Y$ 的值进行比较，满足比较条件 $\theta$ 的所有元组。
    $R \underset{X \theta Y}{\bowtie} S = { t \mid t = \langle r, s \rangle \land r \in R \land s \in S \land r[X] \ \theta \ s[Y] }$
  - 自然连接
    在 $R，S$ 中找到相同的属性列 $X,Y$，然后以 $X,Y$ 为连接属性，比较关系 $\theta$ 取 $=$ 做连接，并去除重复的列。
    $R \bowtie S = { (Z, X, W) \mid (Z, X) \in R \land (W, X) \in S \land r[X] = s[X] }$
  - 除法
    考虑 $R(X,Y)$，$S(Z)$，如果属性集 $Y$ 和 $Z$ 相同，那么 $R$ 除以 $S$ 是 $R$ 在 $X$ 上投影的子集，子集和 $S(Z)$ 的笛卡尔积包含于 $R(X,Y)$。
    $R \div S = { t \mid t \in \Pi_X(R) \land s \in S \land \langle t, s \rangle \in R }$
- 元组关系演算
  基本结构是 元组演算表达式。
  元组关系表达式的形式定义：${ t \mid \Phi(t) }$，表示了所有使 $\Phi$ 为真的元组的集合，即表示了一个关系。
- 域关系演算
  公式中的变量对应的是元组各个分量的域变量。
  域演算表达式的形式定义：${ (X_1, X_2, \dots, X_k) \mid \Phi(X_1, X_2, \dots, X_k) }$，表示所有使 $\Phi$ 为真的那些 $(X_1, X_2, \dots, X_k)$ 组成的元组集合，即表达了一个关系。
关系运算的 安全约束
安全运算：不产生无限关系和无穷验证的运算
关系代数是安全运算，关系演算不一定是。对关系演算要进行安全约束。
安全表达式：安全运算的运算表达式
安全约束：对关系运算采取的限制。方法是对 $\Phi$ 定义一个有限的符号集 $DOM(\Phi)$，使 $\Phi$ 的运算结果及中间结果所产生的关系及其元组的各个分量都必须属于 $DOM(\Phi)$。即 $DOM(\Phi)$ 包括 $\Phi$ 中的所有常量和所有元组的所有分量值。
安全约束后，三种关系运算是等价的，可以互相转换。

关系数据语言

数据库数据语言分类：

数据定义语言DDL（Data definition language）：模式DDL，外模式DDL，内模式DDL
数据操纵语言DML（Data manipulation language）：四种基本操作（检索、插入、修改、删除），分为联机交互方式（自含式语言，可独立使用）和宿主语言方式（嵌入高级语言程序中）。
数据控制语言DCL（Data control language）：完成数据库的安全性控制、完整性控制、并发控制等。

关系数据语言的核心是查询，又称为 查询语言。关系运算是设计关系数据语言的基础，关系运算的分类决定了关系语言的分类。

3 SQL

基本表：实际存在的表

导出表：从基本表导出的表，有视图和快照

视图：虚表，只在数据库的数据字典中存储视图的定义。视图定义出来就可以当正常的基本表用。

数据查询

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

SELECT：目标列
FROM：基本表或视图，即要操作的关系名，可以有多个
WHERE：检索条件

查询块的结果仍是一个表，先在表的水平方向上按 WHERE 选取元组，然后在垂直方向上按 SELECT 指定的列进行投影。

投影：要加 DISTINCT，不加的话就是单纯的选取

SELECT DISTINCT C#
FROM SC;

选取：WHERE 引出查询条件，布尔运算符（AND，OR，NOT）

SELECT S#, C#, G
FROM SC
WHERE (C# = 'C1' OR C# = 'C2') AND G >= 70;

SELECT S#, C#, G
FROM SC
WHERE G BETWEEN 70 AND 85;

排序：在查询块后接 ORDER BY 子句，ORDER BY {列} {ASC|DESC}，ASC为升序，DESC为降序，缺省为升序

SELECT *
FROM S
ORDER BY SD, SA DESC;

连表检索：在 FROM 中指明要连接的表名，在 WHERE 中指明 连接条件 和选取条件。相当于先对 FROM 中的所有表 做笛卡尔积 得到一张大表，然后再用 WHERE 筛选。

SELECT SN, C#, G
FROM S, SC
WHERE S.S# = SC.S# AND SN = '张华';

表自身连接可以通过定义别名来表示。

SELECT X.SN, X.SA
FROM S X, S Y
WHERE X.SA > Y.SA AND Y.SN = '李勇';

外连接：在连接条件的一边加 (*)，相当于这个表加了一个空行，使得另一个表中不满足连接条件的元组也可以进行连接，使得其可以输出。

SELECT S.S#, SN, SA, SD, C#, G
FROM S, SC
WHERE S.S# = SC.S#;

外部查询：WHERE 子句中可以包括另一个查询块，称为子查询。

子查询返回单值，可以直接用比较运算符连接

SELECT SN
FROM S
WHERE S.SA = 
    (SELECT SA FROM S
     WHERE SN = '李勇');

子查询返回一组值。必须在比较运算符后插入 ANY, ALL 等操作符
```
SELECT SN
FROM S
WHERE S# = ANY
    (SELECT S# FROM SC
     WHERE C# = 'C2');
```
- 可以用 IN, NOT IN 表示检索，分别可以代替 =ANY, !=ALL
```
SELECT SN
FROM S
WHERE S# IN
    (SELECT S# FROM SC
     WHERE C# = 'C2');
```
- EXISTS, NOT EXISTS 表示子查询结果非空/空时为真
```
SELECT SN
FROM S
WHERE EXISTS
    (SELECT * FROM SC
     WHERE S# = S.S# AND C# = 'C2');
```
  这个例子表示，对于 S 的每一行，把 S# 代入看子查询结果是否非空。
- NOT EXISTS 表达全称量词
  检索选修所有课程的学生姓名：检索学生姓名，不存在他不选修的课程
```
SELECT SN
FROM S
WHERE NOT EXISTS 
    (SELECT * FROM C
     WHERE NOT EXISTS 
         (SELECT * FROM SC
          WHERE S# = S.S# AND C# = C.C#));
```
  翻译一下：选取学生，这个学生满足的条件是不存在一个课程，使得这个学生没有选修这个课程。
- NOT EXISTS 表达蕴含
  检索至少选修了 S2 选修的所有课程的学生学号：检索学生学号，不存在 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#));
```
  翻译一下：选取学生，这个学生满足，不存在一个课，使得 S2 选修了，且这个学生没有选修

并、差、交：UNION, MINUS, INTERSECT。操作对象是同类关系。

库函数：COUNT, SUM, AVG, MAX, MIN，COUNT(column) 表示求某一列中非空值的个数，COUNT(*) 表示求行的总数。只能在 SELECT 子句和 HAVING 子句中出现。

分组检索：GROUP BY {列名} \n [HAVING {条件}] 按照属性列的值分组（相等的为一组），对每一组进行 SELECT。HAVING 是去掉不符合条件的分组，SELECT 是去掉不符合条件的行。

SELECT S#, SUM(G)
FROM SC
WHERE G >= 60
GROUP BY S#
HAVING COUNT(*) >= 4
ORDER BY SUM(G) DESC;

部分匹配：LIKE/NOT LIKE {字符串常量}，字符串常量中可以包含 %（表示任意 0 个或多个字符）和 _（表示任意单个字符）。

派生表：FROM 子句中的子查询，生成的表叫做临时派生表，需要指定别名。

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;

数据定义

考试考

定义基本表

  
  Create Table <表名>
  (
    <列名><数据类型>[<列级完整性约束>]
    [{, <列名><数据类型>[<列级完整性约束>]}]
    [{, [<表级完整性约束>]}]
  );

完整性约束
- NULL/NOT NULL
- UNIQUE
- PRIMARY KEY
- FOREIGN KEY
- CHECK
数据类型
- char(n)
- varchar(n)
- int
- smallint
- real, double
- numeric(n, m) n 位数字，小数点后 m 位
- date
- time
- interval

例子

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

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

修改基本表

语法：

  
Alter Table <表名>
[Add <新列名><数据类型>[<完整性约束>]]
[Drop <完整性约束名>]
[Modify <列名><数据类型>]

示例：
- 示例1：S 表增加“入学时间”属性
  1 Alter Table S Add Scome Date;
- 示例2：将 SA 的数据类型改为字符串长整数
  1 Alter Table S Modify SA Smallint;

删除基本表
- 语法：
  1 Drop Table <表名>;
- 示例：
  1 Drop Table S;

定义索引

语法：

  
Create [Unique][Cluster] Index <索引名>
On <表名> (<列名>[次序][, <列名>[次序] …]);

示例：

  
Create Unique Index Scno
On SC(S# ASC, C# DESC);

删除索引

语法：
1 Drop Index <索引名>;
示例：
1 Drop Index Stusno;

定义视图

语法：

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

示例：建立计算机系的学生视图

  
Create View CS_Student
As
SELECT S#, SN, SA FROM S
WHERE SD = 'CS';

删除视图

语法：
1 Drop View <视图名>;
示例：
1 Drop View CS_Student;

视图消解：DBMS 执行对视图的查询时，把视图定义中的查询和用户的查询结合起来，转换成一个等价的对基本表的查询，直接对基本表进行查询。

插入单个元组

语法：

  
Insert Into <表名> [(<属性列>[, <属性列>])]
Values(<值>[, <值>]);

示例：

  
Insert Into S Values ('S10', '陈冬', 'IS', 18);

插入子查询结果

语法：

  
Insert Into <表名> [(<属性列>[, <属性列>])]
<子查询>;

示例：

  
Insert Into Dept_Age (Sdept, AvgAge)
Select SD, AVG(SA) From S
Group By SD;

修改数据

语法：

  
Update <表名>
Set <列名> = <表达式> [, <列名> = <表达式>]
[Where <条件>];

示例：

  
  Update S
  Set SA = 22
  Where S# = 'S1';

删除数据

语法：

  
Delete From <表名> [Where <条件>];

示例

：

示例1：删除学号为 S19 的学生的记录
1 Delete From S Where S# = 'S19';
示例2：删除所有学生的选课记录
1 Delete From SC;

示例3：删除计算机系所有学生的选课记录

  
Delete From SC
Where 'CS' = (Select SD From S
              Where S.S# = SC.S#);

空值 NULL 的运算：三值逻辑，True, False, Unkown

4 数据库保护

安全性防范非法用户和非法操作，完整性防范不合语义的数据。

数据库安全性控制

考试考过（安全性定义、安全性控制方法）

数据库的安全性：保护数据库以防止 不合法的使用所造成的数据泄露、更改和破坏。

用户标识和认证：系统提供的 最外层 安全保护措施。

标识：用一定的方式标识用户或应用程序的名字或身份
认证：系统在用户登录时判断其是否为合法的授权用户

存取控制 确保合法用户按照指定权限使用 DBMS 和访问数据，而非法用户或不具有相关权限的用户则不能。

用户权限定义：将用户权限记录到数据字典中，形成安全规则或授权规则
合法权限检查：用户发出请求后，DBMS 根据字典中的安全规则进行合法权限检查，决定是否接受用户的请求
这两个机制一起组成了 DBMS 的安全子系统

考试考过（自主存取控制、强制存取控制）

存取控制方法：

自主存取控制（DAC）：用户对不同的对象有不同的权限，不同的用户对同一个对象也有不同的权限，用户还可以把权限转授给其他用户。
用户权限有 数据对象和操作要素 两个组成部分，对用户存取权限的定义称为授权，授权中应指明 用户名，数据对象名，允许的操作类型。
角色是一组权限的集合，将角色授予用户就可以实现权限分配。
SQL 中的两类用户权限：
- 用户级权限：为每个用户授予的特定权限，是对用户 使用整个数据库 权限的限定
- 关系级权限：数为用户授予的 与关系或视图有关的 权限，是对用户使用 关系或视图 权限的限定
SQL：授权 Grant，取消权限 Revoke
强制存取控制（MAC）：每个数据对象赋予一个密级，每个用户授予一个许可证，对于每个对象，只有拥有合法许可证的用户才可以存取
DBMS 管理的实体分为 主体和客体 两类。
- 主体：系统中的 活动实体，包括实际用户和用户的各个进程
- 客体：系统中的 被动实体，包括文件、基本表、索引、视图等
对于每个实体，指定一个 敏感度标记（Label），主体的敏感度标记称为 许可证级别，客体称为密级。
对比主体和客体的 Label 来确定主体是否能够存取客体。主体许可证级别 大于等于 客体密级，可以读取，等于时才可写。

安全性控制其他方法：

视图机制：为不同用户定义不同的视图
审计：记录用户对数据库的所有操作放入审计日志中
数据加密：防止数据库中的数据在存储和传输中失密。使得不知道解密算法的人无法获知数据内容

可信计算机系统评测标准 TCSEC，可信计算机系统评估标准关于数据库系统的解释 TDI：从 安全策略、责任、保证、文档 四个方面描述了安全级别划分的指标。

数据完整性控制

数据完整性：数据的正确性和相容性，关系到数据库系统能否真实的反应现实世界

正确性：数据有合法的类型，并在有效取值范围内

相容性：同一对象在不同关系中的数据符合逻辑

完整性约束条件：施加在数据库数据上的语义约束条件，作用对象可以是列（列的类型、范围等）、元组（元组各字段间约束）、关系（若干元组、关系间的约束）

实体完整性（关系约束，一个关系元组的约束，PRIMARY KEY）
参照完整性（关系约束，关系之间的约束，FOREIGN KEY）
用户自定义完整性（列/元组约束，UNIQUE/NOT NULL/CHECK）

两种完整性约束：一种反应固定的时候的状态，一种反应变化时候的状态

静态约束：每一个 确定状态 数据对象满足的约束条件，反应数据库 状态合理性。
动态约束：从一种状态转变为另一种状态时，新旧值之间 满足的约束条件，反应数据库 状态变迁

完整性控制应包括三个方面上的功能：

定义功能：可以定义完整性约束，提供定义的机制
检查功能：检查用户操作是否违背完整性约束
违约响应：违背完整性约束后的措施

完整性约束条件按照检查时间的分类：

立即执行约束：一条语句 执行完后立即进行完整性约束的检查
延迟执行约束：整个用户事务 执行完后进行检查

完整性规则的表示：五元组$(D,O,A,C,P)$

Data：数据对象
Operation：触发检查的操作
Assertion：数据对象需要满足的约束
Condition：A 作用的数据对象值的谓词（筛选数据，使得 A 只对某一类数据生效）
Procedure：违背规则时触发的过程

SQL 对数据完整性的支持：建表、断言（涉及多个表或统计操作的约束）、触发器（Trigger，由事件驱动的特殊过程）

5 关系数据理论

数据依赖：一个关系内部属性值之间相互依赖又相互制约 的关系。

函数依赖

概念

函数依赖 $X \rightarrow Y$：$R(U)$ 是属性集 $U$ 上的关系模式，$X,Y$ 是 $U$ 的子集，如果对于 $X$ 的每个确定值，$Y$ 都有唯一的值与之对应，则称 $X$ 函数确定 $Y$ 或 $Y$ 函数依赖于 $X$。

若 $Y \subseteq X$，则称 $X \rightarrow Y$ 是 平凡的函数依赖；若 $Y \nsubseteq X$，则称 $X \rightarrow Y$ 是非平凡的函数依赖。

函数依赖是 语义范畴 的概念，不能形式化证明，且不随时间而变化。

在 $R(U)$ 中，如果 $X \rightarrow Y$，且对于任意 $X$ 的真子集 $X’$，都有 $X’ \nrightarrow Y$，则称 $Y$ 对 $X$ 完全函数依赖，记作 $X \xrightarrow{f} Y$；否则称为 $Y$ 对 $X$ 部分函数依赖，记作 $X \xrightarrow{p} Y$。

在 $R(U)$ 中，如果 $X \rightarrow Y$，$Y \rightarrow Z$，且 $Y \nrightarrow X$，则称 $Z$ 对 $X$ 传递函数依赖，记作 $X \xrightarrow{t} Z$。设 $K$ 为 $R<U, F>$ 中的属性或属性组合，若 $K \xrightarrow{f} U$，则称 $K$ 为 $R$ 的 候选码。若候选码多于一个，则选定其中的一个作为主码。

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

外部码：属性组是另一个关系模式的码，且不是自己所属关系的码，就是外码。

函数依赖公理系统

逻辑蕴含：如果从关系 $R(U, F)$ 里 $F$ 中的函数依赖能够推出 $X \rightarrow Y$，则称 $F$ 逻辑蕴含 $X \rightarrow Y$。

闭包：$F$ 逻辑蕴含的函数依赖的全体，记作 $F^+$。
Armstrong 公理系统
对于 $R<U, F>$，有如下规则：
- 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$ 所蕴含。
推论：
- 合并规则：由 $X \rightarrow Y$，$X \rightarrow Z$，有 $X \rightarrow YZ$。
- 伪传递规则：由 $X \rightarrow Y$，$WY \rightarrow Z$，有 $WX \rightarrow Z$。
- 分解规则：由 $X \rightarrow YZ$ 且 $Z \subseteq Y$，有 $X \rightarrow Z$。
- 若 $X \rightarrow A_1A_2 \dots A_k$ 成立 $\Leftrightarrow X \rightarrow A_i$ 成立（$i = 1, 2, \dots, k$）。
有效性：由 F 经过公理系统推导出来的函数依赖一定在 F 的逻辑蕴含中
完备性：F 的逻辑蕴含中的函数依赖一定可以由 F 经过公理系统推导出
属性集 $X$ 的闭包：$X_F^+ = { A \mid X \rightarrow A \text{ 能由 } F \text{ 根据 Armstrong 公理导出} }$
注意闭包中的元素是属性，闭包是属性的集合。
求法：初始 $X_F^+ = {X}$，然后一直枚举 $X_F^+$ 的所有子集 $A$，看 $F$ 中有没有 $A \rightarrow B$，有的话就把 $B$ 加进 $X_F^+$ 里，直到 $X_F^+$ 不再变化。

函数依赖集

函数依赖集等价：$F^+=G^+$，则 $F$ 和 $G$ 等价

考试会考。

最小依赖集：

函数依赖右部一定是单属性
没有多余的函数依赖
每个函数依赖左部属性集中没有多余的属性

最小化函数依赖集 $F$：

逐个检查 $F$ 中各函数依赖 $FD_i : X \rightarrow Y$，若 $Y = A_1A_2 \dots A_k, k \geq 2$，则用 ${ X \rightarrow A_i \mid i = 1, 2, \dots, k }$ 代替 $X \rightarrow Y$。（右部单属性）
逐个检查 $F$ 中各函数依赖 $X \rightarrow A$，设 $X = B_1 \dots B_m$，逐个考查 $B_i$，若 $A \in (X - B_i)^+_F$，则以 $(X - B_i)$ 取代 $X$。直到 $F$ 不再改变。（左部没有多余）
逐个检查 $F$ 中各函数依赖 $X \rightarrow A$，令 $G = F - { X \rightarrow A }$，若 $A \in (X)^+_G$，则从 $F$ 中去掉该函数依赖，直到 $F$ 不再改变。（没有多余函数依赖）

范式

考试会考，记住这几个定义。

第一范式 1NF：二维表中的每一个元素都是一个精确值，而不是值集，也就是不能表中有表。这个约束叫做 原子值。满足这个约束条件的关系称为 规范化关系，简称范式。

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

2NF

$R \in 1NF$ 且 每个非主属性完全依赖于码
规范化

3NF

$R \in 2NF$ 且 每个非主属性不传递依赖于 $R$ 的任何码
规范化

BCNF：若关系模式 $R<U, F> \in 1NF$，如果对于 $R$ 的每个函数依赖 $X \rightarrow Y$，且 $Y \nsubseteq X$ 时，$X$ 必含有码，则 $R<U, F> \in BCNF$。

多值依赖

~~估计不考~~

$Y$ 多值依赖于 $X$，$X \twoheadrightarrow Y$：$Z=U-X-Y$，只要在 $R(U)$ 中确定了 $X$ 的值，就可以唯一确定一组 $Y$ 的值，且这组 $Y$ 的值不依赖于 $Z$ 的值。

这是一个整体性的性质，因此不能简单的拆分子集来推出一些结论，如：若 $X \twoheadrightarrow Y$ 在 $R(U)$ 上成立，$Y’ \subseteq Y$，则不一定有 $X \twoheadrightarrow Y’$ 成立。

性质：

多值依赖有对称性：
- 若 $X \twoheadrightarrow Y$，则 $X \twoheadrightarrow Z$，其中 $Z = U - X - Y$。
若 $X \rightarrow Y$，则 $X \twoheadrightarrow Y$。即函数依赖可以看作多值依赖的特殊情况。
若 $X \twoheadrightarrow Y$，而 $Z = \varnothing$，则称 $X \twoheadrightarrow Y$ 为 平凡的多值依赖，否则，若 $X \twoheadrightarrow Y$，而 $Z \neq \varnothing$，则称 $X \twoheadrightarrow Y$ 为 非平凡的多值依赖。
多值依赖的推论：
- 若 $X \twoheadrightarrow Y$，则 $X \twoheadrightarrow YZ$。
- 若 $X \twoheadrightarrow Y$，则 $X \twoheadrightarrow Y \cap Z$。
- 若 $X \twoheadrightarrow Y$，则 $X \twoheadrightarrow Z, \quad X \twoheadrightarrow Z - Y$。

4NF

若关系模式 $R<U, F> \in 1NF$，如果对于 $R$ 的每个非平凡的多值依赖 $X \twoheadrightarrow Y$ （$Y \nsubseteq X$），$X$ 都含有码，则称 $R \in 4NF$。即非平凡多值依赖都是左边有码的函数依赖。

规范化

基本思想是让一个关系只描述一个实体或实体间的一种联系。实质是概念的单一化。

模式分解

定义和性质

函数依赖集投影

$F_i = { X \rightarrow Y \mid X \rightarrow Y \in F^+ \land XY \subseteq U_i }$，称 $F_i$ 为 $F$ 在 $U_i$ 上的投影。

一个属性集合里的全部函数依赖

关系模式分解

关系模式 $R<U, F>$ 的一个分解 $\rho$ 是指 $\rho = { R_1<U_1, F_1>, R_2<U_2, F_2>, \dots, R_n<U_n, F_n> }$，其中 $U = \bigcup_{i=1}^n U_i$，并且没有 $U_i \subseteq U_j$，$1 \leq i, j \leq n$，$F_i$ 是 $F$ 在 $U_i$ 上的投影。

分解的无损连接性

设 $\rho = { R_1<U_1, F_1>, R_2<U_2, F_2>, \dots, R_k<U_k, F_k> }$ 是 $R<U, F>$ 的一个分解，$r$ 是 $R<U, F>$ 的一个关系，定义 $m_\rho(r) = \underset{i=1}{\overset{k}{\bowtie}} \Pi_{R_i}(r)$，其中 $\Pi_{R_i}(r) = { t[U_i] \mid t \in r }$ ，即 $m_\rho(r)$ 是 $r$ 在 $\rho$ 中各关系模式投影上的连接。

若对于 $R<U, F>$ 的任何一个关系 $r$，都有 $r = m_\rho(r)$，则称分解 $\rho$ 具有 无损连接性，简称 $\rho$ 为 无损分解。

即拆开来再连接回去，还能得到原来的样子，不会丢失关系的信息。

无损分解的判定

~~好像不考~~

分解的保持函数依赖性

若 $F^+ = (\bigcup_{i=1}^n F_i)^+$，则称 $R<U, F>$ 的分解 $\rho = { R_1<U_1, F_1>, \dots, R_n<U_n, F_n> }$ 保持函数依赖。

即分解之后不丢失函数依赖的信息。

模式分解可以达到的范式等级

要求保持函数依赖，可以到 3NF，不一定能到 BCNF
要求无损连接性，可以到 4NF 或更高
要求保持函数依赖和无损链接，可以到 3NF，不一定能到 BCNF

关系模式分解算法

这个必考。

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

极小化 $F$
不在 $F$ 中的属性单独作为一个关系模式
如果有一个函数依赖和剩余属性集合相等，那么不拆分这个关系
对 $F$ 按相同左部的原则分组，去掉子集后得到所有 $U_i$（其中互不为子集）

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

先按上面的算法求保持函数依赖的 3NF 分解
原关系 $R<U,F>$ 的码为 $X$，看有没有 $U_i$ 包含了 $X$，如果没有的话，加一个关系 $R^*<X, F_X>$。

达到 BCNF 且保持无损连接：

一直分里面的关系模式，如果里面有关系模式不属于 BCNF，那么里面一定有一个函数依赖逻辑蕴含与 $F$，使得 $X\rightarrow A$ 且 $X$ 不是关系模式的码，那么就分出关系 $XA$ 和 $U_i-{A}$。

求候选码

$L,U$ 类属性一定是候选码成员，$R$ 类属性一定不是候选码成员。如果 $L,N$ 类属性组成的集合 $X$ 满足 $X_F^+ = U$，则 $X$ 为 唯一候选码。

图论判定方法：

每个属性是一个节点，单属性 函数依赖构成边。

在图中可以找出 $L,U$ 类属性集 $X$（入度为 $0$ 的点以及孤立点）。如果没有独立回路（不能由其它节点到达的回路），那 $X$ 是唯一候选码，否则每条独立回路各取一个节点和 $X$ 组成一个候选码。

6 数据库设计

数据库设计：设计优化的数据库逻辑结构和物理结构

特点：要把数据设计和处理设计结合起来

手工试凑法（直接设计）

规范设计

需求分析
收集基础数据及处理，即用户要完成什么 处理功能，以及 数据之间的联系。
数据流图 表达数据和处理之间的关系，数据字典 描述系统中各类数据。
数据库概念结构设计
E-R 法：
- 用 E-R 图描述现实世界（概念模型）
- 将 E-R 图转换成相应的数据模型
设计概念结构的四类方法：自顶向下，自底向上，逐步扩张，混合策略
自底向上的设计方法：
- 设计局部 E-R 图
  过程：选择局部应用，建立实体模型，确定实体间联系类型，用 E-R 图表示实体及联系。
  对数据字典进行抽象，得到实体和属性。属性必须是不可分的数据项，也不能和其它实体有联系，实体和他的属性要保持 1:1或n:1 的联系，否则需要把这个属性上升到实体。
- 综合局部，形成总 E-R 图
  合并形成初步 E-R 图，修改和重构生成基本 E-R 图。
  消除冲突：属性冲突、命名冲突、结构冲突
  消除冗余：冗余数据（可以从基本数据导出的数据）、冗余联系（可以从其他联系导出的联系）
  规范化方法消除冗余联系：
  - 把实体用符号表示，把联系表示为函数依赖表达式 $X \rightarrow Y$
  - 极小化函数依赖集，然后判断不在最小覆盖集里的关系，确定是否是冗余联系
数据库逻辑结构设计
形成初始关系数据库模式，关系模式规范化，关系模式优化，子模式定义
E-R 图转换为关系模型：
- 一个实体转换为一个关系模式，一个联系转换为一个关系模式，多元联系也转换为一个关系模式
- 弱实体类型的转换：用一个新的关系存储弱实体类型的属性，并为这个关系添加外码（标识关系的主码）。新关系的主码为标识关系的主码和弱实体类型的码的组合。
- 超类、子类的转换：为超类和子类分别各自创建关系，超类关系里包含所有子类共有的属性以及主码，并包含一个属性作为 子类判定符，每个子类关系里包含超类的主码以及这个子类特有的属性。
规范化：分析函数依赖，确定范式等级
优化：确定是否进行模式合并或分解
- 水平分解：把关系的元组分为几个子集（按行分组），每个子集作为一个子关系。
- 垂直分解：把关系的属性分解为若干子集（按列分组），形成若干子关系模式。经常一起使用的属性分解出来作为一个子关系模式。
设计子模式：设计用户外模式（视图）
数据库物理结构设计
数据库物理结构：数据在物理设备上的存储结构与存取方法
- 存储结构：存放位置、系统配置
- 存取方法：索引方法、聚集方法、hash 方法
  - 索引方法：加速数据访问。索引项包括两个域 索引域（Key）、地址，常用 B+ 树索引。索引域选择：经常在查询条件（WHERE）中出现，经常作为最大值和最小值库函数的参数，经常作为连接属性。（快速查找、以及利用 B+ 树从左往右有序的特点）
  - 聚集方法：把关系中某个属性组 值相同的记录 集中存放在连续的物理块。一个关系只能参加一个聚集。适合经常连接的关系、某组属性经常进行相等比较或值重复率高。更新操作远多于连接的话不适合使用。
  - hash 方法：把关键字转换为地址。条件：关系的大小可以预知且不变；或 DBMS 提供动态 hash 存取方法。
数据库实施
数据库运行和维护

7 存储管理和索引

数据放入内存才能被处理，DBMS 处理内存和外存（磁盘）数据的交换。

DBMS 存储管理的目标：最小化磁盘存取次数

磁盘块（页面）：存储分配和检索的逻辑单元，数据以块为单位在磁盘和主存之间传输

物理存储管理器，也称磁盘管理器，是 DBMS 的最底层，隔离上层模块和底层软硬件平台

数据库：由若干文件组成，这些文件采用专有的格式，操作系统不能获取文件内容的任何信息

存储管理器维护数据库文件，把文件组织为块/页的集合，并跟踪页的数据读取与写入、跟踪可用的空间

表被映射为底层存储中的文件，文件被组织为记录的序列，记录被映射到磁盘块上。文件由若干磁盘块组成，一个块可以包含几个记录。

数据块结构：分槽结构

记录

记录：字节序列，由 DBMS 将其解释为属性类型和值

记录的组织方式

堆：可以在文件里任何位置（链表、页目录）
顺序：按 Key 排列（可以高效按某个 Key 搜索）
索引：有序索引表-主文件
散列：hash 函数和桶
聚集：有相同属性值的记录存在同一个块上

缓冲区管理

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

缓冲区组织和管理：一个 页面数组，每个元素称为帧，存放一个块。页表跟踪页的访问情况。

共享锁、排他锁

替换策略：最近最少使用

索引

索引项：索引域（搜索码）、指针

分类：

排序索引、哈希索引
聚集索引（索引域的顺序和记录的排列顺序一样）、非聚集索引（辅助索引，排列顺序和本来的顺序不一样）
稠密索引（每个索引域值都有一个索引项）、稀疏索引（部分索引域才有对应项）
多级索引

B+ 树：B 树的改进，节点从左到右按关键字递增链接

hash 索引

8 查询处理与查询优化

关系查询的四个阶段：查询分析（词法分析、语法检查）、查询检查（语义检查、权限检查、SQL 语句转关系代数表达式）、查询优化、查询执行

查询操作的实现

选择：全表扫描，索引扫描
排序：快速排序（内存中的关系），外排序-归并
连接：嵌套循环（双重循环遍历表），索引链接（一个表按照连接属性建立索引，相互取连接属性比较），排序-合并（两个表按照连接属性排序，然后双指针），hash join（把连接属性 hash）

表达式的执行：

物化方法：每次执行一个运算，结果 物化到一个临时关系 中
流水线方法：同时执行多个运算，把结果传给下个运算，不存储临时关系

查询优化

转成语法树，进行代数优化，进行物理优化

代数优化：优化关系代数表达式，改变操作次序和组合（优化查询树）
选择运算尽早执行，投影运算尽早执行，投影运算和选择运算同时执行，结合笛卡尔积和选择运算，找公共子表达式
物理优化：存取路径和底层操作算法的选择
基于启发式规则的操作算法选择：
- 选择操作：小关系全表扫描，大关系索引扫描
- 连接操作
  - 已经按连接属性排好序：排序-合并
  - 连接属性上有索引：索引链接
  - 其中一个表较小：hash-join
  - 嵌套循环
基于代价估算的优化：计算执行代价，选择最小的执行计划

9 事务处理技术

事务：用户定义的数据库操作序列

考试考过：事务特性、两个解决办法

ACID 特性：

原子性：里面的操作要么都做，要么都不做（恢复机制）
一致性：事务执行结果是数据库从一致性状态变到另一个一致性状态（原子性）
隔离性：一个事务的执行不能被其他事务干扰（并发控制）
持久性：事务对数据库的影响是永久的（恢复机制）

事务的特性可能被破坏：多个事务并发时操作交叉进行；事务运行时被强行停止

解决办法：数据库并发控制机制、数据库恢复机制

事务的开始和结束可以由用户显式控制。

数据库恢复技术

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

意义：保证事务原子性；系统故障后可以恢复

故障：

事物内部故障（可预期的/不可预期的）
系统故障（系统停止运行，使事务都异常终止）
介质故障（外存故障，破坏数据库，影响存取这部分数据的事务）
计算机病毒（对数据进行非法修改）

故障的影响：

数据库本身被破坏
数据不正确

数据库恢复的原理：冗余，利用存储在别处的冗余数据来重建或恢复

数据转储：定期将整个数据库复制到磁带或另一个磁盘保存起来，称为 后备副本

两种状态：

静态转储
动态转储：不影响数据库可用性，需要把转储期间事务对数据库的修改记录，建立 日志文件。后备副本加上日志文件 可以恢复数据库。

两种方式：

海量转储：每次转储全部
增量转储：更新

日志：记录事务对数据库更新操作，可以以记录为单位或以数据块为单位

作用：

事务故障和系统故障恢复
动态转储必须建立
静态转储恢复转储完到故障点间事务

写入规则：按照事务执行时间顺序，先写日志，再写数据库

故障恢复策略

事务故障：UNDO 撤销事务，强行回滚
反向扫描日志，执行事务的逆操作，直到事务开始
系统故障：UNDO + REDO 撤销未完成的，重做已完成的（已提交的事务可能还没写入数据库）
介质故障：装入最新后备副本，装入转储后的日志，重做事务

检查点技术：检查点之前的事务可以不重做。

检查点记录：记录正在执行的事务和最新的事务地址

重新开始文件：记录检查点记录的地址

恢复子系统维护：把缓存中日志写入磁盘，写入检查点记录，写入数据记录，把检查点记录地址写入重新开始文件

利用检查点恢复：定位最近检查点，检查点建立时的事务 UNDO，检查点后新开始的事务 UNDO，提交的事务 REDO。

并发控制

并发导致的数据不一致性：

丢失更新
脏数据读出
不能重复读

并发控制：调度并发事务，避免并发事务相互干扰造成数据不一致性

方法：封锁机制，加锁

排它锁 X 锁：只允许有锁的事务读取和修改
共享锁 S 锁：可以读取，且有 S 锁时其他事务只可以加 S 锁

封锁协议：何时加锁，何时放锁

一级封锁协议：写的时候加 X 锁，事务结束后释放。防止丢失修改
二级封锁协议：读之前加 S 锁，读完释放。防止读脏数据
三级封锁协议：读之前加 S 锁，事务结束后释放 S 锁，防止不可重复读

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

多粒度封锁：同时支持多种封锁粒度，选择时考虑封锁开销和并发度。可以构建一颗树，更高的节点粒度大，锁一个节点，这个节点（显式）的后代都被上锁（隐式）。

意向锁：加锁时对上级节点加意向锁，这样之后再加锁就可以不检查下级节点。

活锁：永远等待。先来先服务

死锁：永远无法结束。

预防死锁
一次封锁法：事务一次性把所有使用的数据加锁，降低了系统并发度
顺序封锁法：对数据对象规定一个封锁顺序，实现难度大
死锁检测和解除
超时法
等待图法：看有没有环
解除：撤销一个代价小的事务

事务调度：多个事务的操作序列，但是对于每个事务来说，操作顺序不能变（事务间可以穿插）

事务执行正确性：结果和串行执行相同。可串行化调度（正确调度）

冲突可串行化调度：可以交换两个事务中不冲突操作的次序得到串行调度

两段锁协议：保证可串行性。获得封锁，释放封锁，且释放后不再获得锁。可能发生死锁。

10 数据库技术新发展

数据仓库：支持管理决策过程的、面向主题的、集成的、随时间增长的持久数据集合

分布式数据库系统

分布式：数据分布在网络的各个节点上，被一种机制联系在一起，构成有机整体

数据分布、场地自洽（局部应用）、自洽场地之间的协作性（全局应用）

分片方式：水平、垂直、导出（按其他关系水平分）、混合

分片保证：完整性、不相交性、可重构性

分布透明性（分布独立性）：

分片透明性：用户不用考虑分片
位置透明：用户不用知道位置
局部数据模型：用户不用知道具体的数据模型

DDBMS：全局控制集中（集中在一个节点上）、全局控制分散（集中在每个节点上）、全局控制部分分散

分布事务处理：全局事务被划分为在许多节点上的子事务。原子性：这些子事务要么一起提交，要么一起回滚。

协调局部事务管理器：两端提交协议，协调者做决定，参与者执行决定

协调者：做决定提交/撤销
参与者：管理子事务执行和读写

云计算

云数据库服务 RDS：把传统数据库部署在云上，一主多从，高可用性

云原生数据库：针对云的环境设计数据库架构，计算和存储分离

原生分布式数据库：

期末复习, 数据库

数据库期末复习

This post is licensed under CC BY 4.0 by the author.

1 概述

发展过程

集成数据的表示

概念模型（E-R 法）

数据模型

系统结构

2 关系数据库

概念与性质

关系模型

关系数据语言

3 SQL

数据查询

数据定义

4 数据库保护

数据库安全性控制

数据完整性控制

5 关系数据理论

函数依赖

概念

函数依赖公理系统

函数依赖集

范式

多值依赖

规范化

模式分解

定义和性质

关系模式分解算法

求候选码

6 数据库设计

7 存储管理和索引

记录

缓冲区管理

索引

8 查询处理与查询优化

查询操作的实现

查询优化

9 事务处理技术

数据库恢复技术

并发控制

10 数据库技术新发展

分布式数据库系统

云计算

Trending Tags