数据库系统原理

Introduction

文件系统的缺点:

数据冗余，导致可能出现数据不一致
数据访问困难
没有数据隔离性
Integrity problem 完整性问题：存储数据的值满足特定的一致性约束
原子性操作
多用户并发
安全性问题

DB: database A collection of interrelated data

DBMS: DataBase Management System

Applications: Set of programs to access the data

Three-level Architecture

view: 某一类用户所关注的逻辑信息，比如，老师只关心学生的选课和成绩

logic: 所有不同类用户所关注的逻辑信息的集合, 只有一个

physical: 逻辑信息存储的物理结构

三级模式, 两级映象 $\rightarrow$ 数据独立性

Functions of DBMS

Data Definition and storage management;
Data Manipulation, Data Access;
Data Security and integrity;
Transaction management, Data recovery and concurrency;
Data dictionary （存储用户、结构、索引等信息）

Relation Model

Relational Data Structure

Order of turples is irrelevant;
Order of attributes is irrelevant;
For all relations, the domains of all attributes be atomic;
Attributes names must be different;
Serveral attributes can have the same domain;

不同的属性可以有相同的取值域, 但是含义不同比如：user_id 和 book_id 均从整数域中取值, 但是表示含义不同
Turples are not duplicate.

Super Key: $R(U)$ is a relation schema, $K \subseteq R(U)$, values for key are sufficient to identify an unique tuple of each possible relation $r(R)$ by possible $r$

在关系模式中
唯一标识元组
属性集

Candidate Key: minimal superkey

Uniqueness  唯一性
Irreducibility  最小性

Primary Key: one of cadidate keys (结合实际)

Forign Key: For $R_{1}, R_{2}$, $R_1$ includes the Primary Key X of $R_2$, X is called a Foreign Key referencing $R_2$

Integrity Constraint of Primary Key: 实体完整性约束, 主键不为空

Referential Integrity Constraint: 参照完整性约束, 外键只能为空或者来自于所参照的主键的取值

Relational Algebra Operation

basic

Select 选择: $\sigma_{p}(r)$

$p$ 是选择谓词, 选择 $r$ 中满足 $p(t)$ 的数据 $t$

Project 投影: $\Pi_{A_1, A_2, \cdots, A_k}(r)$

取出关系 $r$ 中名为 $A_1, \cdots, A_k$ 的属性，并对结果去重

Union 并: $r \cup s$

$r$ 和 $s$ 具有相同数量的属性，属性的取值域相融

Set Difference 差: $r - s$

$r - s = { t | t \in r \ and \ t \notin s }$

Cartesian-Product 笛卡尔乘积: $r \times s$

$r \times s = { tq | t \in r \ and \ q \in s }$

Rename 更名: $\rho_{x}(E)$

$\rho_{X}(E)$，将 $E$ 改名为 $X$ > $\rho_{X(A_1, \cdots, A_n)}(E)$，将 $E$ 改名为 $X$, 表中列的名字改为 $A_1, A_2, \cdots, A_n$

additional

Set-Intersection 交: $r \cap s$

$r \cap s = { t | t \in r \ and \ t \in s } = r - (r - s)$

Join 连接:

Division 除法: $R\div S$ 在表 $R$ 中满足 $S$ 中条件的数据但是不包含 $S$ 中的字段, 具体看这篇文章

Assignment 赋值: 把结果赋给中间变量, 数据无变化

Outer join 外连接: 分为 left join 和 right join, 表中属性可能有空值

Null 空值: 要查询为空的属性需要明确地表示出来

Modification

Delete 删除: $r \leftarrow r - E$ ($r$ 是数据库, $E$ 是将要被删除的数据

Insertion 插入: $r \leftarrow r \cup E$

Update 更新: $r \leftarrow \Pi_{F_1, F_2, \cdots, F_k}(r)$ ($F_1, F_2, \cdots, F_k$ 是对应列的新值)

SQL

标准 SQL 语句，没啥好记的，和实际的各种 SQL 方言有些不同但大体上差不多

E-R

右边第二个图的写法中, l 为 1 表示全参与, 0 表示部分参与; h 表示对应关系, 要反过来看, 比如下面这个例子, 表示 instructor 和 student 是一对多的关系

Specialization

disjoint: 高层实体集之间没有重叠 e.g. 老师演绎出教授和副教授两个实体集

overlapping: 高层实体集之间有重叠 e.g. 人演绎出银行职员和银行客户

total: 高层实体集一定全部属于底层实体集

partial: 部分属于

Aggregation

多个实体集和一个实体集产生关系

Reduction to Relation Schemas

简单属性: 直接放入表中

复合属性: 只要最终的叶子节点的属性放入表中

多值属性: 另外生成一张表, 并且要包含原来实体集的主键和多值属性一起作为新表的主键

导出属性: 理论上不要, 实际可以进行判断要不要

弱实体集: 主键是自己的主键和依赖的强实体集的主键

一对多/一对一关系: 把一的主键放到多的表中当作外键, 关系有属性的话也一并放入

多对多关系: 另外生成一张表, 主键为关联的两个实体的主键复合的主键

Relational Database Design

Functional Dependencies

$\alpha \rightarrow \beta$, 无论何时当且仅当对于任意 $r$ 中数据都满足上述条件, 并且还有以下性质:

$$t_1[\alpha] = t_2[\alpha] \Rightarrow t_1[\beta] = t_2[\beta]$$

Trivial dependency:

$\alpha \rightarrow \beta \cap \beta \subseteq \alpha$

Transitive dependency:

第三个条件是为了防止变成直接依赖

Partial dependency:

Logically imply:

没太看懂, 感觉说了个废话

Closure:

Armstrong’s Axioms:

additional rules:

Closure of Attribute Sets:

Equivalent FD Sets:

Canonical Cover /Minimal Cover:

求最小覆盖集步骤:

将所有函数右部全部化为单一属性

去掉所有函数依赖左边的冗余属性

去掉所有冗余的函数依赖关系

这里有个去本求包看着有点用: 数据库必考题目~最小依赖集（最小覆盖、极小函数依赖集）_求最小函数依赖集例题-CSDN 博客

Extraneous Attributes:

Normal Forms

1NF: 表中属性都是原子的, 即: 不能表中有表. 只有满足 1NF 才是关系型数据库.

2NF: $R$ 中每一个非主属性都完全函数依赖于 $R$ 的码 (也就是超键, 详细定义可以看一文搞懂候选码、主码、全码、外码、主属性、主键、主关键字、非主属性清晰总结-阿里云开发者社区 (aliyun.com)

没有部分依赖

3NF: 没有非主属性对码的部分函数依赖, 也没有非主属性对码的传递函数依赖

平凡依赖

左边是超键

右边是键属性

BCNF:

平凡依赖

左边是超键

候选键求法: 数据库——求候选键的方法-CSDN 博客

Decomposition

Lossless-join decomposition:

Dependency preservation:

3NF 的无损连接和依赖保持的分解【数据库系统原理北京邮电大学 2022 邓芳】【精准空降到 57:53】 :

求最小覆盖 (记得求完最小覆盖后左边表达式相同的函数依赖要合并)
每个函数关系一个关系模式, 每个关系模式不能有覆盖
检查如果候选键没有包含在之前得到的关系模式中, 则需要把候选键单独拿出当作一个关系模式

BCNF 的无损连接的分解: 【数据库系统原理北京邮电大学 2022 邓芳】【精准空降到 1:10:36】

数据库 BC 范式（BCNF）判断和分解-CSDN 博客

数据库系统从入门到精通十三：3NF 与 BCNF 分解 - 知乎 (zhihu.com)

期末复习

中间还有几章没记, 没啥不太好理解的内容 ~~(绝对不是因为懒)~~, 就放在期末复习的时候一块记录

是否为 confilct serializable: 对操作绘制前驱图, 读写、写读和写写互斥, 对前驱图进行拓补排序. 无环则为 conflict serializable, 拓补排序结果即为冲突和串行化序列; 否则为不可 conflict serializable.

recoverable & cascadeless: 数据库理论笔记18可恢复性调度-非瀑布性调度-调度独立等级 - duskcloudxu - 博客园 (cnblogs.com)

2PL: 两阶段锁协议, 分为加锁和释放锁两个阶段, 不能有重叠, 也就是一旦释放了某个锁后则不能再执行获取锁的操作

strict 2PL: 严格两阶段锁协议, 获取所有锁一直到事务提交时再释放

ignore: 最近检查点之前 commit/abort 的事务

redo: 最近检查点到 crash 中间 commit/abort 的事务

undo: 一直到 crash 都未完成的事务

增加 log 规则: 从后往前扫描, 挨个添加与 undo 事务相反的日志, 日志为一条赋值语句, 直到扫描到该事务的 start 时将该事务移出 undo list, 并写入一条 abort 日志

timestamp protocol:

基于时间戳的并发控制协议 - 知乎 (zhihu.com)

个人理解: 符合时间戳协议就是所有事务可串行化, 并且串行化的结果要符合时间戳的先后顺序

【sql】sql 中 true，false 和 null 之间 and、or 运算的理解。_true false null-CSDN 博客

Introduction#

Three-level Architecture#

Functions of DBMS#

Relation Model#

Relational Data Structure#

Relational Algebra Operation#

basic#

additional#

Modification#

SQL#

E-R#

Specialization#

Aggregation#

Reduction to Relation Schemas#

Relational Database Design#

Functional Dependencies#

Normal Forms#

Decomposition#

期末复习#