笔记「数据库系统概论」

Wings 收录于类别期末速通

2023-02-22 2023-02-22 约 4945 字预计阅读 10 分钟次阅读条评论

1. 绪论

1.1 数据库系统概述

数据Data: 描述事物的符号, 需要一定的语义才能描述事物 (需要定义).
数据库Database (DB): 长期存储在计算机内的, 有组织的, 可共享的大量数据集合
数据库管理系统Database Management System (DBMS): 管理数据库的软件系统
数据库系统Database System (DBS): 计算机系统+数据库+数据库管理系统+数据库管理员+使用数据库的应用 (比如前端)

1.2 数据模型

三要素:

数据结构 (静态)
数据操作 (动态)
数据完整性约束条件

概念模型 (信息模型)

人对数据的抽象概念, 如 E-R.

实体型 (struct Enity {})
实体集 (struct Enity enities[])
实体 (struct Enity enity)
属性 (Enity.name)
- 域: 属性的定义域 (0 <= Enity.age <= 200)
码: 能唯一标识实体的属性集合 ({Enity.id} / {Enity.id, Enity.name})
联系: 特殊的实体型 (具有属性). 两个实体集之间的联系 / 一个实体集内部实体的联系

E-R 图

实体集: 方框
属性: 圆圈
关系: 菱形

咕

逻辑模型和物理模型

逻辑模型是计算机存储, 操作数据时的模型, 如关系模型 (表), 层次模型 (树)

物理模型是硬盘存数据的格式和结构

1.3 数据库系统结构和组成

这里是在说 DBMS.

模式: 模式Schema, 理解成一种数据库的抽象. Class MyDatabase; 实例Instance, 用 OOP 的实例去理解就行. MyDatabase db1, db2
内模式: 数据的存储结构, 比如红黑树. (把结构的定义也抽象一下?)
外模式: 提供的一组 API. 可以根据需求不同有多个外模式. 比如图书馆数据库, 提供给读者和管理员的 APIs 是不同的. (把 APIs 抽象一下?)

真 tm 抽象

三层模式的特点

数据的逻辑独立性: API 不变, 实现 API 的方式可变
数据的物理独立性: API 不变, 数据的存储方式可变

优点: 保证了外模式的稳定性 (说白了就是 API 不变)

2. 关系数据库

2.1 关系

关系的定义太 tm 抽象了, 虽然看懂了, 但是很没有必要去记这玩意.

简单来说就是一个元组的集合, 其中元组的每个分量对应属性.

候选码: 能够唯一确定实体的最小属性集 ({id}, {name})
主码: 人为从某一个候选码中选一个 ({id})
主属性: 候选码的并集, ({id, name}) (有可能候选码有 {A, B}, {A, C}, 那么主属性就是 {A, B, C})
非主属性
基本表
查询表
视图表

关系模式: struct R {}; 关系: struct R r;

哈哈, 又是一层抽象.

(为什么 Schema 会被翻译成模式, 看着 “模式” 就以为是 mode, md)

R(U) = struct R {var a; var b; ...}, U = {a, b, …} (属性的集合)

关系模型的外延: 关系 (行), 关系模型的内涵: 属性 (列)

2.2 关系完整性

实体完整性: 主码的一些规定?
参照完整性: 外码的一些规定? 得有这个码对应的实体
用户定义完整性: 定义域?

2.3 关系操作

集合操作不讲了, 表是元组的集合, 需要并相容才能做 (笛卡尔积和除除外).

笛卡尔积的最后一步是连接, 而不是直接组成又一层有序对; 除不会说, 咕.

除操作一般是查询全部…, 含有 “全部” 字样的是除集 (不能理解, 先记着).

选择 $\sigma$

$$\sigma_{cond(t)}(R) = \{t \in R \mid [cond(t)] = 1 \}$$

其中 $cond(t)$ 是元组满足的条件, 一般是某个属性的值的比较运算

投影 $\Pi$

$$\Pi_{\{A\}(R)$$

整张表选择属性组 A, 也就是提取列. 需要去重

连接 $\bowtie$

$$R \bowtie_{A \theta B} S = \sigma_{t[A] \theta s[B]}( R \times S)$$

等值连接: $\theta$ 为 $=$

自然连接, 式子不写下面的条件. 要求 R 和 S 的有相同的属性组. 然后属性组等值连接, 最后只保留一组属性

外连接:

左外连接: 连接符号左边的所有元组都保留着, 不满足连接条件的, 在最后结果的字段里填充 NULL
右外连接: 保留右边
全外连接: 都保留

3. SQL

3.1 三级模式

内模式: 存储文件的逻辑结构 (物理结构不算在内)
模式: 基本表
外模式: 视图

SQL 中的 Schema 是数据对象的集合, 算是存储文件之上的一层抽象? namespace 的概念.

3.2 SQL 语句

记一下可能考的但是没练的.

1
2
3
4
5
6
7
8


create table Table (
  A int,
  B varchar(20),
  C datetime,
  primary key (A, B),
  foreign key (B) references Table2(B),
  check (C between "2020-01-01" and "2021-01-01")
);

1
2


insert into Table (A, B, C)
  values (a, b, c);

1
2


delete from Table
  where ...;

1
2
3


update Table
  set a = a + 1
  where ...;

4. 数据库安全性

这里说的是数据隐私安全

4.1 数据库安全性控制

用户标识与鉴别Identification & Authentication

登录才能使用数据库.

口令 / 基于函数的单向认证

自主存取控制Discretionary Access Control (DAC)

用户具有某些权限, 这些权限可以被定义, 进行操作的时候 DBMS 检查权限. 用户权限定义和合法权检查机制一起组成了DBMS的安全子系统.

用户可以向其他用户转授权限.

数据库管理员 (DBA) 有所有权限
数据库对象创建者拥有这个对象的所有操作权限, 包括传递权限的权限
有传递权限的用户可以将权限传递给其他用户

在权限模型中, 用户可以看作权限的集合.

可定义角色 (role), 也是权限的集合.

1
2
3


create/drop role role_name
grant option/role on object to user_name/role_name [with grant option]
revoke option/role on object from user_name/role_name [cascade/restrict]

all privileges 所有权限, public 所有用户 / 角色

with grant option 同时授予传递权限的权限 cascade “递归” 删除所有被授予出去的权限 restrict 没有授予出去的权限时才能删除

强制存取控制Mandatory Access Control (MAC)

数据 (客体) 和用户 (实体) 都具有一个凭证标签 (Label), 如 TopSecret > Secret > Confidential > Public.

主体 $\ge$ 客体时具有写的权限
主体 $\le$ 客体时具有读的权限

为什么主体标签等级高但是不能写低等级的客体呢? 因为低等级的客体会被低等级的人读, 而高等级的人有可能向其中写入一些更加机密的信息. 所以这里直接不信任高等级的人 (从根源上防止数据泄漏?)

先 DAC 再 MAC

视图机制

不该看的不给你看, 甚至可以配合 DAC 保护视图

审计

每次操作都有记录, 看记录找出凶手

数据加密

不解释

4.2 统计数据库安全性

统计数据库: 只允许查询统计信息, 不允许查询单个记录

用户可以通过数学把戏, 计算单个记录

要防止这个数学把戏, 用魔法打败魔法.

任意一次查询的统计信息必须涉及 N 条单个记录
任意两次查询的统计信息不能涉及 M 个交记录
查询次数不能超过 $1 + \frac{N-2}{M}$

什么? 怎么算的? 不会数学把戏! 我猜也不会考这个.

5. 数据库完整性

定义 - 检查 - 违反处理

实体完整性: 定义码, 列级别或表级别, 多个属性组作为码只能在表级定义, 违反时拒绝操作
参照完整性: 定义外码, 参照另一张表的主码, 可指定违反时的处理, 如拒绝, 或者级联修改/删除
用户定义完整性: 在列上规定 NOT NULL, UNIQUE, CHECK (a IN (1, 2, …)) 这种, 违反时拒绝操作
完整性约束: 可以在表中用 CONSTRAINT 定义约束, 并且可修改
域: 可以用 CREATE DOMAIN + CONSTRAINT 定义域 (数据类型)

触发器: hook

6. 关系数据库理论

变成离散数学了捏

6.1 数据依赖理论

函数依赖

函数依赖: 对一个关系模式 $R(U)$, 若对属性集合存在两个子集 $X, Y \subseteq U$, 将 $X, Y$ 看成函数, 变量就是表中的可能出现的分量值, 有 $X \rightarrow Y$ 是个单射, 即函数, 则称 $X$ 函数决定 $Y$, $Y$ 函数依赖于 $X$, 记 $X \rightarrow Y$. $X$ 称 决定因素Determinant
平凡函数依赖: $Y \subseteq Y, X \rightarrow Y$ 非常废话, 所以是平凡.
非平凡函数依赖: 字面意思
$X \rightarrow Y, Y \rightarrow X$ 记为 $X \leftrightarrow Y$
不存在依赖关系在箭头上划个斜杠
函数依赖有具体讨论的领域, 如 R(U) 还是某个具体的关系实例 r;
$X \rightarrow Y$, 当 $X$ 极小时, 称为完全依赖, 否则部分依赖. 箭头上加 F (Full) 或 P (Partial)
传递函数依赖: 相当于复合函数, $X \rightarrow Y, Y \rightarrow Z \Rightarrow X \rightarrow Z$, $X \rightarrow Z$ 箭头上加 T (Transition)

Armstrong 公理系统

自反律: $Y \subseteq X \Rightarrow X \rightarrow Y$
增广律: $X \rightarrow Y \Rightarrow (X \cup Z) \rightarrow (Y \cup Z)$, (也记做 $XZ \rightarrow YZ$)
传递律: $X \rightarrow Y, Y \rightarrow Z \Rightarrow X \rightarrow Z$

闭包: 函数依赖集合 $F$ 蕴含的所有函数依赖 (可用 Armstrong 推出) 称为闭包, 记为 $F^+$. 求 $F^+$ 是 NP hard 问题, 只能通过所有 Armstrong 三个公理论去枚举推
属性集闭包: $R(U, F), X \subseteq U, X_F^+ = \{A_i \mid (X \rightarrow A_i) \in F^+ \}$, 人话就是 $X$ 能决定的所有属性组的集合
覆盖: $F, G$, $F^+ = G^+$, 则 $F, G$ 等价 (或相互覆盖). 判定求 $\forall X, Y, Y \in X_F^+ \Leftrightarrow Y \in X_G^+$

计算属性闭包: 增广求, 直到极大

函数依赖的最小覆盖:

分离右边属性: $A \rightarrow BC \Rightarrow A \rightarrow B, A \rightarrow C$
去除左部冗余: 左边依次看是否冗余 $ABC \rightarrow D$, 看依次去掉某个属性 (如第一次去掉 A), 求剩余属性在 $F$ 上的闭包 $(BC)_F^+$, 看有没有 $D$, 有的话 $A$ 冗余, $BC \rightarrow D$, 继续去掉某一个, 直到不能去.
去除多余依赖: 考察每一个依赖 $X \rightarrow Y \in F$, 求 $X_{F-\{X \rightarrow Y\}}^+$, 若 $Y \in X_{F-\{X \rightarrow Y\}}^+$, 则多余, 去除.

非常合理, Armstrong 的逆过程.

求候选码:

先求最小函数依赖 $F$, 将属性分为 4 类:

L: 只出现在左边
R: 只出现在右边
N: 没有出现
LR: 既出现在左边又出现在右边

将 L 和 N 放在一起, 记为 $X$, 将 R 和 LR 放在一起, 记为 $Y$.

考察 $Y$ 的所有子集, 分别放入 $X$, 求 $X_F^+$, 若为 $U$, 则 $X$ 是候选码.

候选码不唯一.

6.2 关系范式理论

1NF

属性原子

2NF

非主属性完全依赖于候选码 (能够唯一确定实体的属性集)

1NF 的前提下, 不存在非主属性对于候选码的部分函数依赖

3NF

2NF 的前提下, 不存在非主属性对于候选码的传递函数依赖

BCNF

3NF 的前提下, 所有的函数依赖的决定因素都是超码 (含有码的属性组)

4NF

多值依赖

$(X, Y, Z)$ 是 $U$ 的一个划分, $y = X(x)$ 的取值有多个, $z = X(x)$ 的取值也有多个, 把 $(X, Y, Z)$ 在一起 ($U$), 则 $Y$ 与 $Z$ 会根据 $X$ 有一定关系 (表现为同一个 x 下, 两个取值集合的笛卡尔积)

$X \rightarrow\rightarrow Y, X \rightarrow\rightarrow Z$.

在 BCNF 的前提下, 每个非平凡多值依赖的决定因素都是超键 (含有码的属性组)

6.3 模式分解理论

无损分解

分解的表做自然链接, 结果与原表一致. 但是这玩意得用实例来判断()

用关系模式的判断方法如下.

设一个关系模式 $R(U, F)$ ($F$ 是最小函数依赖集) 分解为 $\rho = \{R_i(U_i)\}$. 列表, 行为 $U_i$, 列为 $A \in U$.

若 $A_j \in U_i$ 则在 $T_{ij}$ 上填 ai, 否则填 bij.
遍历每个 $X \rightarrow Y$, 找到属性(组) X 上相同的行, 改变这些行的属性 Y 上的值为相同的值 (这些值里的字典序列最小值)
直到出现某一行为 ai, 则无损, 否则不是无损

大致行为像是考察每个函数依赖, 看看最后能不能决定所有的属性 (某一行都是 ai, 猜想继续做到不变的话应该是每一行都是 ai, 懒得研究了), 如果可以, 则任意的实例这样分解, 然后自然链接, 都不会出现多出来的数据 (因为所有都被决定了), 否则会出现不存在的数据

若只分解成两个 $\rho = \{R_1,R_2\}$, 则可以判断 $R_1 \cap R_2 \rightarrow R_1 - R_2$ 或者 $R_1 \cap R_2 \rightarrow R_2 - R_1$ 成立, 如果是, 则无损分解.

不会证明, 爬

多值依赖:

$(X, Y, Z)$ 是 $U$ 的一个划分, $X \rightarrow\rightarrow Y, X \rightarrow\rightarrow Z$ 的充要条件是 $R$ 的分解 $\{R_1(XY), R_2(XZ)\}$ 具有无损链接性.

不会证明, 爬

保持依赖分解

分解后的 $Fi$ 的并集 $G$, 如果 $F, G$ 覆盖, 则保持依赖. 非常平凡. 判断用判断覆盖那套.

分解成 3NF

求最小函数依赖
将决定因素相同的函数依赖涉及到的属性 (组) 放在一起组成一个关系模式
求候选码若候选码不在任何分解出的关系模式中, 则候选码组成一个关系模式

无损且保持依赖

无损分解成 BCNF

求最小函数依赖
对分解出的每个关系模式, 找到一个破坏 BCNF 的函数依赖, 即 $X \rightarrow Y$, $X$ 不是这个关系模式的超码, 将其分解成 $R_1(XY), R_2(U-XY)$.
重复考察直到满足 BCNF

非常暴力的算法, 只能保证无损, 不保证保持依赖

7. 数据库设计

需求分析
概念设计: 根据需求画 E-R 图
逻辑设计: 根据 E-R 图设计关系模型, 优化模型, 设计用户子模式 (外模式, 视图)
物理设计: 磁盘结构, hash, 聚簇, B+ tree
实施
运维

8. 嵌入式 SQL

(宿) 主语言: C 等使用嵌入式 SQL 的语言

预编译, 将 SQL 代码编译成主语言的函数以供调用, 可以在 SQL 代码里写主语言的东西, SQL 语句前面加 EXEC SQL 表示这是一条 SQL 语句, 否则都是主语言语句.

通信:

SQLCA: SQL Communication Area, 一条 SQL 语句执行后, 成功与否的变量 SQLCODE 放在这个地方, 主语言根据 SQLCODE 进行逻辑控制
主变量: 主语言的变量, 传递给 SQL 语句, 也可以传指针接收某些值
游标 (cursor): 一个缓冲取. SQL 语句的结果可能有多个值, 比如 select 会有多条结果, 存在缓冲区里, 主语言用这个指针从缓冲区中读取

10. 数据库恢复技术

事务Transaction

原子性
一致性: 和业务功能一致, 由原子性和隔离性保证?
隔离性: 事务不能相互影响
持续性: 事务一旦提交, 对系统的影响是永久的

11. 并发控制

锁

排他锁 (X): 事务 T 对数据对象 A 加 X 锁后, 只有 T 能读写 A, 其他事务不能读写, 也不能对 A 加任何锁.
共享锁 (S): 事务 T 对数据对象 A 加 S 锁后, 所有事务都可以读, 可以加 S 锁, 不能加 X 锁.

读数据前要加 S 锁, 写数据前要加 X 锁.

封锁协议:

一级封锁协议: 写前加 X 锁, 事务结束释放锁, 防丢失修改
二级封锁协议: 一级 + 读前加 S 锁, 读完释放锁, 防脏读 (X 没释放加不了 S)
三级封锁协议: 一级 + 读前加 S 锁, 事务结束释放锁, 防不可重复读 (保证通一个事务中的多次读一致)

活锁: 调度问题导致某个事务得不到锁 - 采用合理调度如 FCFS
死锁:
- 一次封锁: 封锁所有可能用到的数据, 但是并发性差
- 顺序封锁: 每个事务都按一定顺序加锁, 但是维护成本高
- 诊断与解除:
  - 诊断:
    - 超时法: 设置一个时间阈值, 事务还没有结束则认为死锁
    - 等待图法: 把事务的等待建图论模型, 存在环则认为死锁
  - 解除: 选择一个 (处理代价最小的) 事务, Rollback 并释放他获取的所有锁

并发调度的可串行性

可串行化: 两个事务可串行执行

调度: 并发事务中语句的执行顺序

冲突: 两个操作交换顺序会改变结果

冲突可串行化: 冲突操作次序不变, 交换其他操作, 整个调度可串行 (啥啊, 不懂)

冲突可串行化 $\Rightarrow$ 可串行化

优先图: 从调度序列中找冲突操作对应的事务执行顺序, 事务连边, 无环则冲突可串行, 任意拓扑序就是一个合法的串行

两段锁协议: 两个阶段, 第一个阶段只申请锁, 第二个阶段只释放锁

目录