数据库-复习笔记

April 21, 2021 · 49 min read

Ferdinand Su

Prospective doctoral student @ HIT-ICES, C# developer.

基本概念

数据库：相互之间有关联关系的表的集合
数据库系统包括
- DB
- DBMS
- DBAP
- DBA
- 计算机基础系统
DBMS：数据库管理系统
DBAP：数据库应用
DBA：数据库管理员
DDL：数据定义语言
DML：数据操纵语言
DCL：数据控制语言
SQL：结构化查询语言，包含DDL、DML和DCL

DBMS的功能

语言翻译器
查询优化与实现
数据存取
通信控制
事务管理
故障恢复
安全性控制
完整性控制
数据字典管理
API
性能分析

数据库系统的结构

三个层次

用户层：某一能看到和处理的数据，全局数据的一部分
逻辑层：全局角度理解管理的数据，包含了关联约束
物理层：储存在介质上的数据，包含了路径、储存方式和索引方式

数据的结构

模式：对数据库中数据所进行的一种结构性的描述所观察到数据的结构信息
视图：某一表现形式下展现出的数据
三级视图：
- 外视图：某一用户能看到的
- 概念视图：全局角度理解管理的数据结构描述，包含关联约束
- 内视图：介质上的数据结构描述
两层映像：
- E-I映射：外模式到概念模式，便于用户观察使用
- C-I映射：概念模式到内模式，便于计算机储存和管理
两个独立性
- 逻辑数据独立性：概念模式变化时，可以不改变外部模式
- 物理数据独立性：内部模式变化时，可以不改变概念模式
经典模型
- 表：关系模型
- 树：层次模型
- 图：网状模型

关系代数和SQL

关系

一个关系就是一个表
表的每列的范围称为域，域是一个集合
关系是一组域的笛卡尔积的子集
关系的性质：
- 同质：每一列都来自同一个域
- 不同列可以来自同一个域
- 行间、列间可以互换
- 区分列靠列名，行靠行的关键字
- 理论上，任意两个元组不能完全相同
- 关系的属性不可再分
候选码：一个属性组，可以唯一标识一个元组
主码：候选码之一。主码中的属性值不能为空。
主属性：包含在任何候选码中的属性
外码：R的一个属性组，不是R的候选码，但是与S的候选码相对应

关系完整性

实体完整性：主码中的属性不为空
参照完整性：外码要么空，要么对应了另一个实体的主码
用户自定义完整性：用户针对应用环境定义的完整性约束条件

关系运算

集合运算

交、并、差等，需要两个关系直接有一定的对应性（并兼容性）。
广义笛卡尔积

纯关系运算

选择： $\sigma_{con}(R)=\{t|t \in R \land cont(t)\}$
投影
$\theta$ $θ$ 连接： $R\underset{A\theta B}{\Join}=\sigma_{t[A]\theta s[B]}(R\times S)$ $R A θB ⋈ = σ_{t [A] θ s [B]} (R \times S)$
- 等值连接： $\theta$ 为'='
- 自然连接：A=B的等值连接，简写为 $\Join$
除： $R\div S=\{t|t\in \Pi_{R-S}(R)\land \forall u\in S, tu \in R \}$ ; 笛卡尔积的逆运算
外连接：允许连接后的部分元组因失配而为空
- 左外连接：左侧表中不为空
- 右外连接：右侧表中不为空
- 全外连接：两侧表都可以为空
更名： $\rho_{new-name}(关系)$

SQL

建库、建表和增删改

CREATE DATABSE {DBNAME}
CREATE TABLE {TableName}({Args}):参数包含
- 列名数据类型修饰: 修饰包含：
  - PRIMARY KEY
  - UNIQUE
  - NOT NULL
  - DEFAULT {默认值}
  - CHECK({条件，只能使用当前列的值})
  - REFERENCES {表名}[{列名}] [ON DELETE [CASCADE|SET BULL]]:当被引用的列被删除时，设为空或级联删除。
- CONSTRAINT {约束名称}表约束：
  - UNIQUE {列集合}几列值合在一起是唯一的
  - PRIMARY KEY {列集合}几列联合为主键
  - CHECK {条件}检查多列的值满足条件，只能用某一元组的值
  - FOREIGN KEY {列集合} REFERENCES {表名}({列集合} [ON DELETE [CASCADE|SET BULL]])：引用另一个表的若干列为外键
INSERT INTO {TableName}({Columes}) Values {Values}
DELETE FROM {TableName} WHERE {条件}, 如果没有WHERE语句，则全部删除
UPDATE {TableName} SET {赋值语句} WHERE {条件}
DROP TABLE {TableName}
ALTER TABLE {TableName} {操作}:操作内容包含：
- ADD {列参数|约束参数}
- DROP {完整性约束名}
- MODIFY {列参数}
DROP DATABASE {DBNAME}
USE {DBNAME}和CLOSE {DBNAME}

表查询

DISTINCT关键字可以保证结果无重复
ORDER BY {列名} [ASC|DESC]可以完成结果排序(默认升序)
[NOT ] LIKE '{模式}'可以完成模糊查询，模式中:
- %:匹配0或多个字符
- _:匹配任意单字
- :转义
多表联查：可以直接把表名接在FROM后
[NOT ]IN {集合}，其中集合可以来自子查询
<OP> ALL|SOME {集合}: 将前置与集合中的值进行比较
[NOT ]EXISTS {集合}查询是否有集合中的元组存在
聚合函数: COUNT,SUM,AVG,MAX,MIN; 经常搭配GROUP BY {分组条件(列名和HAVING)}使用。聚合函数的参数是列名。
HAVING {分组过滤条件}
UNION|INTERSECT|EXCEPT [ALL} {集合}：并，交，差另一个集合。ALL允许重复元素出现。
IS [NOT ]NULL判断是否为空
[NATURAL] [INNER|{LEFT|RIGHT|FULL}[ OUTER]] JOIN {集合} {ON {连接条件}|USING {列集合}}: NATURAL,ON,USING只能三选一。默认为内连接。
- NATURAL：公共属性上取值相等，且属性只出现一次
- ON: 取值满足指定条件。如果有公共属性，则会出现两次
- USING：使用公共属性的子集完成连接，各属性只出现一次。
子查询的变量只能由外层向内层传递

视图

对应外模式，

CREATE VIEW view_name[(列名)]
AS
{子查询}
[WITH CHECK OPTION]

视图可以像表一样被各种操作使用，也可以被DROP VIEW删除。

视图可以插入删除更新，但是出现以下情况时则不能更新：

目标列包含聚合函数
使用了UNIQUE或DISTINCT
使用了GROUP BY
使用了算术表达式计算出的列
未包含主键

完整性约束

表约束和列约束：见CREATE TABLE
断言CREATE ASSERTION {名称} CHECK {条件}，条件写法与WHERE类似。断言在每次DB更新时都检查，加重DB负担。
触发器：动态约束，

CREATE TRIGGER {名称} 
BEFORE|AFTER 
INSERT|DELETE|UPDATE 
[OF {列名集合}] 
ON {表名} 
[REFERENCING {引用变量声明}] [FOR EACH ROW|STATEMENT]
[WHEN(条件)]
  {操作}|
  {BEGIN ATOMIC
  {一堆操作}
  END}

引用变量声明: OLD|NEW [ROW|TABLE] [AS] {名称}

数据库访问控制

权力分级
- 读
- 更新(INSERT,UPDATE,DELETE)
- 创建(CREATE,DROP,ALTER)
授权指令
```
GRANT {ALL PRIVILEGES|{权限}}
ON 表|视图
TO {public|userid}
[WITH GRANT OPTION]
```
- 权限包括SELECT,INSERT,UPDATE,DELETE
- public表示所有用户
- WITH GRANT OPTION表示被授权者可以传播这些权利
- GRANT换为REVOKE可以收回权力

嵌入式SQL

这是什么🐂🐎？不会吧，不会吧，1202年还有人拿C语言连数据库？

那为什么不用ODBC呢？每行一个exec sql宁看着难不难受啊？

反正不算学分绩，这几个破分，不要也罢。

实锤不考了。

数据库设计

数据建模和数据库设计

数据模型：表达计算机世界的模型
概念模型：概念数据模型，表示信息世界的模型
理解-区分-命名-表达

ER模型

实体-关系模型
实体：客观存在，可互相区分
属性：实体的某一方面特性
关键字/码：实体中能用其值唯一区分每一实例的属性或属性组合
联系：某一实体的实例与其它实体实例之间可能发生的联系；发送联系的实体数目，称为联系的度或元。
角色：实体在联系中的作用

Crow’s Foot法

实体：矩形框
属性：实体框横线的下面
关键字：属性下加下划线
联系：菱形框或直接以名替代
联系基数：0，1，多

设计过程

需求分析
概念数据库设计：ER图
逻辑数据库设计：建立逻辑模型
物理数据库设计：建立物理模型

概念数据库设计-可能冲突

属性冲突
- 属性域冲突
- 属性取值单位冲突
结构冲突
- 同一对象在不同应用中抽象不同
- 同一实体在不同ER图中属性组成不同
- 联系在不同ER图中类型不同
命名冲突
- 同名异义
- 异名同义

错误设计引起的问题

冗余数据
- 非受控：单纯重复
- 受控：外键重复
插入异常：插入新数据时，会因为信息不足而无法插入
删除异常：当某些实体被删掉后，他们共有的某些信息随之丢失

IDEF1x

根据去年试题，本部分是可选的。考虑到复杂性，我决定PartiallyIgnore()

实体：现实和抽象事物的集合
- 独立实体：一个实体的实例都被唯一的标识而不决定于它与其他实体的联系，直角矩形框；主关键字没有外键
- 从属实体：一个实体的实例的唯一标识需要依赖于该实体与其他实体的联系，圆角矩形框；需要从其他实体继承属性作为关键字的一部分，主关键字有外键
联系：实体间的连接关系
- 标定连接联系：子实体的实例都是由它与父实体的联系而确定，父实体的主关键字是子实体主关键字的一部分；实线表示，子实体侧有圆圈
- 非标定连接联系：子实体的实例能够被唯一标识而无需依赖与其实体的联系，父实体的主关键字不是子实体的主关键字；虚线表示，子实体侧有圆圈
- 分类联系：一个实体实例是由一个一般实体实例及多个分类实体实例构成的
  - 完全分类：一圆圈带两横线
  - 不完全分类：一圆圈带一横线
- 非确定联系：多对多联系，必须分解为若干个一对多的联系来表达，引入相交实体
属性
- 属性
- 主键
- 候选键
- 外键

数据依赖

函数依赖

设 $R(U)$ 是属性集合 $U=\{A_1,A_2,\cdots A_n\}$ 上的一个关系模式，X、Y是U的两个子集。若对于 $R(U)$ 中的任何一个关系 $r$ ，其中不可能有两个元组满足在X中的属性组相等而在Y中的属性值不等，则称“X函数决定Y”或“Y函数依赖于X”，记作 $X\rightarrow Y$

对于 $X\rightarrow Y,Y\not\subset Y$ ，称为非平凡的函数依赖
$X\rightarrow Y，Y\rightarrow X$ 记作 $X\leftrightarrow Y$

完全函数依赖

如果对于 $X\rightarrow Y$ 中X的任何真子集X'都有 $X'\not\rightarrow Y$ 则称Y完全函数依赖于X，记作 $X\stackrel{f}{\rightarrow}Y$ ，否则称Y部分函数依赖于X，记作 $X\stackrel{p}{\rightarrow}Y$ ；部分函数依赖导致非受控冗余

传递函数依赖

如果 $X\rightarrow Y,Y\rightarrow Z,Z\not\subset Y,Y\not\subset X,Z\not\subset X,Y\not\rightarrow X$ 则称Z传递函数依赖于X；导致受控冗余

候选键

设 $K$ 为 $R(U)$ 中的属性或属性集合，如果 $K\stackrel{f}{\rightarrow}U$ 则称 $K$ 为 $R(U)$ 上的候选键。

任意候选键可作为主键
包含在任意候选键中的属性称为主属性
如果K是候选键， $S\supset K$ ，则称S为超键

逻辑蕴含

设F是 $R(U)$ 的一个函数依赖集合，X，Y是R的树形子集。如果F中的函数依赖能导出 $X\rightarrow Y$ 则称F逻辑蕴含 $X\rightarrow Y$ ，记作 $F\vDash X\rightarrow Y$

设 $R(U)$ 是属性集合U上的一个关系模式，F为其上的一组函数依赖，记作 $R(U,F)$ ，则：

自反律： $Y\subseteq X\subseteq U$ ，则 $F\vDash X\rightarrow Y$
增广律： $X\rightarrow Y\in F, Z\subseteq U$ 则 $F\vDash XZ\rightarrow YZ$
传递律： $X\rightarrow Y\in F, Y\rightarrow Z$ ，则 $F\vDash X\rightarrow Z$
合并律 $X\rightarrow Y;X\rightarrow Z\Rightarrow X\rightarrow YZ$
伪传递律 $X\rightarrow Y;WY\rightarrow Z\Rightarrow XW\rightarrow Z$
分解率 $X\rightarrow Y;Z\subseteq Y \Rightarrow X\rightarrow Z$
如果 $A_1,A_2\cdots,A_n$ 是属性，则 $X\rightarrow A_1,A_2\cdots,A_n$ 当且仅当对每个 $A_i,X\rightarrow A_i$

闭包

被F逻辑蕴含的所有函数依赖的集合称为F的闭包，记作 $F^+$ ，如果 $F^+=F$ 则称F为一个全函数依赖族。

对 $R(U,F),X\subseteq U$ ，称 $X^+_F=\{A_i|X\rightarrow A_i\}$ 为X关于F的属性闭包。

$X\rightarrow Y \Leftrightarrow Y\subseteq X^+_F$

覆盖

对于两个函数依赖集合F,G，如果 $F^+=G^+$ ，则称F和G等价，也称F覆盖G或G覆盖F

$F^+=G^+\Leftrightarrow F\subseteq G^+\land G\subseteq F^+$
每个函数依赖集F可被其右端至多有一个属性的函数依赖之集G覆盖

如果F满足以下条件，则称F为最小覆盖，或最小依赖集：

F中每个函数依赖右边都是单个属性
$\forall X\rightarrow A\in F, F-\{X\rightarrow A\}\not ={F}$
$\forall X\rightarrow A\in F, Z\subset X, F-\{X\rightarrow A\} \cup \{Z\rightarrow A\}\not ={F}$

多值依赖

对 $R(U),$ 设 $X,Y\subseteq U$ ，若 $\forall r\in R(U)$ ，元组 $t,s\in r,t[X]=s[X]$ 则必有 $u,v\in r$ 使得：

$u[X]=v[X]=t[X]=s[X]$
$u[Y]=t[Y],u[U-X-Y]=s[U-X-Y]$
$v[Y]=t[Y],v[U-X-Y]=t[U-X-Y]$

均成立，则称Y多值依赖于X，记作 $X\rightarrow\rightarrow Y$

多值依赖中，Y有请确定的一组值与X对应，且Y的取值不和U-X-Y中的属性相联系；函数依赖是多值依赖的特例。

多值依赖互补律 $X\rightarrow\rightarrow Y$ 则 $X\rightarrow\rightarrow U-X-Y$
多值依赖增广律 $X\rightarrow\rightarrow Y\land V\subseteq W$ 则 $WX\rightarrow\rightarrow VY$
多值依赖传递律 $X\rightarrow\rightarrow Y\land Y\rightarrow\rightarrow Z$ 则 $X\rightarrow\rightarrow Z-Y$
若 $X\rightarrow Y$ 则 $X\rightarrow\rightarrow Y$
若 $X\rightarrow\rightarrow Y, Z\subseteq Y$ 且对于某个于Y不相交的W有 $W\rightarrow Z$ 则 $X\rightarrow Z$
多值依赖合并律 $X\rightarrow\rightarrow Y\land X\rightarrow\rightarrow Z\Rightarrow X\rightarrow\rightarrow YZ$
多值依赖伪传递律 $X\rightarrow\rightarrow Y\land WY \rightarrow\rightarrow Z\Rightarrow X\rightarrow\rightarrow Z-WY$
混合伪传递律 $X\rightarrow\rightarrow Y\land XY\rightarrow Z\Rightarrow X\rightarrow Z-Y$
多值依赖分解律 $X\rightarrow\rightarrow Y,X\rightarrow\rightarrow Z\Rightarrow \\X\rightarrow\rightarrow Y-Z\\X\rightarrow\rightarrow Z-Y\\X\rightarrow\rightarrow Y\cap Z$

连接依赖

设 $\rho$ 是R的一个分解，若 $\forall r\in R,r_{n目}=\pi_{R_1}(r)\Join\pi_{R_2}(r)\Join\cdots\Join\pi_{R_n}(r)$ ，则称R满足n目连接依赖，记作 $JD[R_1,\cdots,R_n]$ 或n-JD

保证无损连接性
多值依赖是其特例

关系模式设计范式

若R(U)中关系的每个分量不在可分，则称R(U)属于第一范式，记作 $R(U)\in 1NF$ (不存在复合属性)
若 $R(U)\in 1NF$ 且U中每一非主属性完全函数依赖于候选键，则称R(U)属于第二范式，记作 $R(U)\in 2NF$ (不存在部分函数依赖)
若 $R(U,F)\in 2NF$ 且R中不存在这样的情况：存在候选键X，属性组Y和非主属性A， $A\notin X,A\notin Y,Y\not\subset X,Y\not\rightarrow X$ 使得 $X\rightarrow Y,Y\rightarrow A$ 成立，则称R(U)属于第三范式，记作 $R(U,F)\in 3NF$ (不存在传递函数依赖)
若 $R(U,F)\in 1NF$ 且 $\forall X\rightarrow Y\in F$ ,对于 $Y\not\subset X$ 时，X必含有候选键，则称R(U)属于Boyce-Codd范式，记作 $R(U,F)\in BCNF$ ; $BCNF\subset 3NF$ (所有函数依赖左项均包含候选键)
若 $R(U,F)\in 1NF$ ，D是其上的一组依赖(函数依赖或多值依赖)， $\forall X\rightarrow\rightarrow Y\in D$ ,若 $Y\not ={\empty},Y\not\subset X,XY\not ={ U}$ ,必有X为超键，则称R(U)属于第四范式，记作 $R(U)\in 4NF$ ; $4NF\subset BCNF$ (所有依赖左项均包含候选键)
若 $R(U,F)\in 3NF$ ，R上的任何互补多值依赖必有一个为函数依赖，则称R(U)属于弱第四范式，记作 $R(U)\in W4NF$ 。
当且仅当关系模式R的每个连接依赖均按其候选键进行连接运算时，称R是第五范式的，记作 $R\in 5NF$ , 5NF又称PJNF

模式分解

关系模式R的分解是指用R的一组子集 $\rho =\{R_1,,\cdots R_k\}$ 来代替之。

关键在：

无损连接性： $R,\rho$ 的数据内容是否等价
保持依赖性： $R,\rho$ 的数据依赖是否等价

关系分解的性质

设R是关系模式， $\rho$ 是一个分解，r是R的一个关系， $r_i=\pi_{R_i}(r)$ ,投影连接 $m_\rho(r)=\Join_{i=1}^k\pi_{R_i}(r)$ 则

$r\subseteq m_\rho(r)$
$s=m_\rho (r)\Rarr \pi_{R_i}(s)=r_i$
$m_\rho(m_\rho(r))=m_\rho(r)$

无损连接分解

如果 $\forall r\in R, r=m_\rho(r)$ 则称 $\rho$ 为无损连接分解

无损连接分解检验算法

对于关系模式 $R=A_1A_2\cdot A_n$ ，依赖函数集合F和分解 $\rho=\{R_1,\cdots,R_k\}$

构造k行n列的 $R_\rho$ 表，第j列对应 $A_j$ ，i行对应 $R_i$ ，如果 $A_j\in R_i$ ，则i行j列填写 $a_j$ ，否则为 $b_{ij}$
根据F中的元素 $X\rarr Y$ ，寻找X属性取值相同的行，用其值重置Y属性组
修改后，如果有一行为全a，则 $\rho$ 为无损连接分解；否则不是。

+分解为两个关系模式的检验算法

$\rho=\{R_1,R_2\}$ 是R的无损连接分解的充要条件是 $R_1\cap R_2\rightarrow R_1-R_2$ 或 $R_1\cap R_2\rightarrow R_2-R_1$ 属于 $F^+$

%保持依赖分解

如在 $\pi_{R_i}(F)$ 中的所有依赖之并集(i=1, $\cdot$ ,k),逻辑蕴涵F的每个依赖，则称分解 $\rho$ 保持依赖集F。

其中 $\pi_{R_i}(F)$ 是F在 $R_i$ 上的投影，即F中的任一投影 $X\rarr Y$ ，如果X, Y均包含于 $R_i$ , 则 $X\rarr Y\in\pi_{R_i}(F)$ 。

保持依赖性检验算法

👴要🐇了

令 $G=\cup_{i=1}^k \pi_R(F)$ ，只需检查G是否覆盖F

对F中的每一个每一个元素 $X\rightarrow Y$ 计算 $Z=X^+_G$ ,如果X不包含于 $R_i$ 则无需计算了

Z=X
oldZ=EmptySet()
While Not Z = old
  For i = 1 To k
   oldZ=Z
   Z=Z.Union(
     Z
       .Intersect(R[i])
       .Closure()
       .Intersect(R[i])
     )
   Next i
End While

判断G是否蕴含 $X\rarr Y$ :Z是否包含Y

分解算法

无损分解为BCNF

分析函数依赖集合，将左侧不含候选键的函数依赖组成一个关系，将包含候选键的组成一个关系。

算法：

令 $\rho=\{R\}$
对于每个模式 $s\in \rho$ ,如果 $s\notin BCNF$ 则s上必有 $X\rarr A$ 成立且X不是s的超键， $A\notin X$ ；用 $s_1=\{A,X\},s_2=s-\{A\}$ 来替换s
重复2，直到 $\rho$ 中的关系均为BCNF

保持依赖分解为3NF

将每一个函数依赖单独组成一个关系。

算法：

将R中不出现在F中的属性去掉，并单独组成一个模式
$\forall X\rarr A \in F$ ，用XA构成一个新模式；然后将这些前项相同的模式合并。
取 $\rho$ 为新模式的集合，即为所求

%无损并保持依赖分解为3NF/4NF

+设 $\sigma$ 是一个保持依赖分解出的3NF，X是R的候选键，那么 $\tau=\sigma \cup\{X\}$ 是R的一个分解，且满足3NF，并具有无损连接性和保持依赖性。

4NF算法：

令 $\rho=\{R\}$
对每个模式 $s\in\rho$ 如果 $s\notin 4NF$ ，则s上必有一依赖 $X\rarr\rarr Y$ 成立且X不是s的超键， $Y-X\not ={\empty},XY\not ={s}$ 则令 $Z=Y-X$ 显然 $X\rarr\rarr Z$ ,此时用 $s_1=\{Y,X\},s_2=\{Y-X\}$ 替换s
重复2，直到所有关系模式均为4NF

关系模式设计折衷

小模式避免了冗余、插入异常、删除异常，但是减慢了查询速度
一般只需关系模式符合BCNF即可

数据库实现原理

数据库的物理储存

高效储存
快速检索

记录区分与属性值区分

定长记录-变长记录靠分隔符区分始末
非跨块储存-跨块储存(指针链接)
表占用的磁盘块分配方法
- 连续分配
- 连接分配
- 按簇分配：簇内连续，簇间指针；簇也称片段或盘区
- 索引分配：索引块中存放实际数据块的指针

文件组织方法

无序记录：更新效率高，检索效率低
- 删除数据时，可以直接删除，也可以添加删除标记
- 插入新数据到末尾，或者已删除的记录处
- 定期进行数据库重组，移去被删除的记录
有序记录文件：使用特定码进行排序，检索效率高，但是更新效率低
- 更新时移动其他记录
- 可以使用临时的无序文件保存新增记录
- 周期数据库重组，合并溢出文件到主文件
散列文件：检索效率和更新效率都有提高
- 把记录按某属性或属性组的值,依据一个散列函数来计算其应存放的位置
- 散列字段=散列码
- 链接法处理溢出
聚簇文件：将具有相同或相似属性值的记录存放于连续的磁盘簇块中
- 若干个相互关联的表可储存在一个文件中

索引方法

索引：定义在储存表基础上，无需检查所有记录，快速定位所需的辅助储存结构，由一系列磁盘上的索引项组成，包含：
- 索引字段：表中某些列的值串接而成
- 行指针：指向包含索引字段的纪录在磁盘上的位置
储存索引项的文件称为索引文件，储存表称为主文件
不改变存储表的物理存储结构；- 目的提高存储表的访问速度
分为：
- 排序索引文件
- 散列索引文件
索引字段不一定具有唯一性和最小性
稠密索引：主文件的每个项都对应一个索引项
稀疏索引：只对应主文件中的部分记录；要求主文件有序
非候选键的稠密索引三种实现
- 主文件有序
- 索引文件有重复
- 引入了一层指针记录
主索引：每一个储存块有一个索引项，其总数与储存表所占储存块数目相同，储存表的每一储存块第一条记录称为锚记录，又称块锚
主索引
- 主索引的索引字段即块锚的索引字段值，指针指向对应储存块
- 主索引是一个稀疏索引
- 主索引是通常建立在基于主码的排序字段上
- 唯一一个
- 被用于重新组织主文件数据
辅助索引
- 定义在主文件任一或多个非排序字段上
- 稠密索引，检索效率有时相当高
- 通常针对每一个不同值有一个索引项
- 可以有多个
- 不能改变主文件数据
聚簇索引：索引中邻近的记录在主文件中也是邻近的；反之则为非聚簇索引
倒排索引
多级索引
多属性索引
网格索引：利用多个属性，交叉联合定位检索
散列索引

%B+树

每个节点有： $[P_1K_1P_2\cdots P_{n-1}K_{n-1}P_n]$

其中 $P$ 为指针， $K$ 为索引字段值

叶节点都在最下层
除了段指针(指向下一个数据块)外，叶节点中的的指针都指向记录
索引项
平衡树，各分支高度相同：插入删除时，伴随结点的分裂与合并
叶节点覆盖了全部索引
每个索引块的指针利用率应该在50%-100%之间

插入-分裂

寻找保存键值记录的叶子，如果未满直接插入
如果满了，则申请新节点
同时调整应插入但未插入节点中的键值记录，使其均衡存放于两个叶节点中(分裂)
调整指针
分裂是可能向上层递归的

删除-合并

查找叶子节点中的记录，删除之
调整其左侧或右侧结点及本结点中的键值记录，使其均衡存放于两个叶节点中，或是直接合并为一个节点
合并可能是向上层递归的

B树

索引值只出现一次，可能在叶节点，也可能在非叶节点
指向主文件的指针可能在叶节点，也可能在非叶节点
所有节点才能覆盖全部索引

散列索引

M个桶，分别具有相同容量
散列函数 $h(k)$ 可以将键值k映射到 $\{0,1,\cdots,M-1\}$ 中
然后将k对应的记录插入h(k)的桶
静态散列：M数目不变，可能会产生过多溢出桶
动态散列： $h(k)$ 与M有关，从而M可以根据元素数目动态增加

可扩展散列索引

使用指向块的指针数组表示桶
指针数组可扩增，长度总是2的幂，指针指向的块可能被共享
散列函数h为每个键计算出一个K位二进制序列，K足够大；而桶的数目总是使用从序列第一位或最后一位算起的若干位

线性散列索引

总是使储存块平均记录，保持与总容量的固定比例；超过比例时，桶数+1并分裂
储存块并不总是可以分裂，故允许有溢出块。但是平均溢出块数小于1
用于做桶数组项序号的二进制位数是 $\lceil log_2 n\rceil$ ，其中n为桶数；他们总是从散列函数的低位开始取
低位相同而高位不同的桶分裂

查询实现

一次单一元组的一元操作：选择，投影
整个关系的一元操作：排序，去重，分组
整个关系的二元操作：集合运算，积，连接

连接操作的实现方法

降低IO次数
充分利用内存

表空间扫描

P1：暴力，适用于任何情况，复杂度 $B_R\times(1+B_S)$
P2：全主存实现，要求内存能装下两个关系，复杂度 $B_S+B_R$
P3：半主存实现：内存能装下一个关系，复杂度 $B_S+B_R$
P4：大关系实现：任何情况，复杂度 $B_R\times\frac{B_S}{M-2}+B_S$

迭代器算法

迭代取出一个集合中的每一个元素，而封装其读取细节。

Open()
GetNext()
Close()

两趟扫描算法

一趟扫描完成操作只适用于内存足够大的情况
第一趟划分子集，使之具有某种特性(有序、散列值)
第二趟处理全局性内容的操作，形成结果关系
两趟扫描适合于大量数据

两段多路归并排序TPMMS

第一段：划分元数据为若干子集合，内存所有块用于处理一个子集合，依次处理
第二段：对已排序的元数据归并
复杂度： $3B(R)$ ,不考虑写回或 $4B(R)$ ，考虑写回
条件：大数据集合块数 $\lt B_{memory}^2$
不满足条件，可以用更多段归并

基于排序的两趟扫描

去重操作：归并排序去重
分组聚集：归并排序分组
并、交、差：归并排序，根据输入源确定是否输出
连接：基于连接所用的属性排序，归并连接输出

基于散列的两趟扫描

第一趟：构建散列子表，用散列函数 $h_p$ 将原始关系划分为M-1个子表，并储存
第二趟：处理每个字表，用另一个散列函数 $h_r$ 将子集读入内存并建立内存结构，进行不同操作

去重操作
分组操作
并、交、差
连接：以连接属性作为关键字，设计散列函数

查询优化

逻辑优化策略

尽早完成投影
串接选择和投影
合并笛卡尔积与选择为一个连接
连接运算前预处理
找出表达式的公共子式

关系代数操作等价性

(L1,L2)连接与连接，积与积满足交换律和结合律
(L3)投影串接律：两个投影共同作用的结果是其属性交集的结果
(L4)选择串接律：两个选择共同作用的结果是结果的交集
(L5)选择和投影交换律：如果选择条件F只涉及投影的各属性，那么投影和选择操作可交换
(L6)选择和积的交换律：可以将只涉及到部分属性的选择操作换到积内部
(L7)投影和积的交换律：可以将只涉及到部分属性的投影操作换到积内部
(L8,L9)选择和并、差的交换律
(L10)投影和并的交换律

优化算法

使用L4串接选择表达式
对每个选择，根据L4-9将其尽可能移动到树底
对每个投影，根据L3，5，7，10将其尽可能移动到树底
使用L4和L5将串接的选择和投影合并
对修改后的语法树，将其内结点按以下方式分组：
1. 每个二元运算结点(积、并、差、连接等)和其所有一元运算直接祖先结点放在一组；
2. 对于其后代结点，若后代结点是一串一元运算且以树叶为终点，则将这些一元运算结点放在该组中；
3. 若该二元运算结点是笛卡儿积，且其后代结点不能和它组合成连接，则不能将后代结点归入该组。
产生一个程序：它以每组结点为一步，后代组先执行。

并发控制

三种不一致性

丢失修改：后一次修改会覆盖前一次修改，从而丢失了累计修改结果
不能重复读：两次读取到的不是同一个数据
脏读：读取的数据已经失效

事务

事务是DBMS控制数据操作的一种手段，将一系列操作组合在一起进行操作控制，从而保证系统的一致性

宏观性：一个存取，或一次执行
微观性：对于数据库的一系列基本操作的一个整体性执行
并发执行：多个事务宏观上看是并发执行的，微观上的基本操作则可以是交叉执行的
事务的特性：ACID
- A原子性：DBMS保证事务的操作是不可分的
- C一致性：DBMS保证事物的操作状态是正确的，符合一致性
- I隔离性：DBMS保证并发执行的多个事务之间互不影响
- D持久性：DBMS保证已提交的事务影响是持久的，被撤销的事务影响是可恢复的
事务调度：一个事务的基本步(读写、锁等)的一种执行顺序称为一个调度
并发调度的正确性：当且仅当并发调度下得到的新数据库结果和分别串行得到的一致，才说调度是正确的
可串行性：如果无论数据库初态如何，一个调度对数据库状态的影响都和某个串行调度相同

事务调度表达模型

$r_T(A)$ ：事务T读取A
$w_T(A)$ ：事务T写A

操作冲突

冲突的两个操作不能交换顺序，否则可以
同一事务的任何两个操作都是冲突的
不同事物对同一元素的两个写操作是冲突的
不同事物对同一元素的一读一写操作是冲突的
冲突可串行性：如果一个调度可以通过交换相邻两个无冲突操作，从而转换为一个串行调度，则称他为可串行的
满足冲突可串行性，一定满足可串行性；反之不然。
正确性 $\supseteq$ 可串行性 $\supseteq$ 冲突可串行性

冲突可串行性判别算法

构造有向图
节点是每一个事务 $T_i$
如果 $T_i$ 的某个操作要在 $T_j$ 前执行，则绘制一条 $T_i\rightarrow T_j$ 的边
检查有向图是否有环

基于锁的并发控制

读写前要获得锁
每个元素的锁是唯一的
完成后释放
$L_i(A)$ ： $T_i$ 对A加锁
$U_i(A)$ ： $T_i$ 对A解锁

锁的类型

排他锁：只有一个事务可以读写，其他事务均不能读写
共享锁：所有事务可读，但均不可以写
更新锁：初始读，以后可以升级为写
增量锁：增量更新被和其它类型的更新区分开

协议级别LP

有写要求的数据对象加排他锁，不再访问后即可解锁；只能防止修改丢失
有写要求后立即加排他锁，事务提交时解锁；不能防止重复读
有写要求后立即加排他锁，事务提交时解锁；需要读的对象加共享锁，不再访问后即可解锁；防止丢失更改、脏读和重复读。
有写要求后立即加排他锁，事务提交时解锁；需要读的对象加共享锁，事务提交后即可解锁；可以防止所有不一致(包括幻读)

SQL隔离性级别

读未提交-0LP
读已提交-1LP
可重复读-2LP
可串行化-3LP

封锁粒度

封锁数据对象的大小。

单位：

属性值
元组/某索引项
元组集合
整个关系/整个索引
整个DB

从前往后：并发度小，封锁开销小

两段封锁协议2PL

读写数据之前要获得锁，各事务中所有封锁请求先于任意解锁请求
分为加锁段和解锁段两阶段。
可以保证冲突可串行性
可能产生死锁

基于时间戳的并发控制

时间戳：唯一性递增性的标记，可表征一系列事务执行的先后顺序
借助时间戳，强制(执行时判断冲突)使一组并发事务交叉执行，等价于一个特定顺序的串行执行
- 如果没有冲突，则予以执行
- 如果有冲突，则撤销并重启该事务；此时事务获得了更大的时间戳，后执行
对于每个元素x，系统保留其上的最大时间戳
- RT(x)：读过该元素的事务的最大时间戳
- WT(x)：写过该元素的事务的最大时间戳
- C(x)：最近写该元素的事务是否已经提交

调度规则：

读取时，与WT(x)比较：
- TS大，则允许，并更新RT；
- 否则拒绝并重启
写入时，与RT(x)和WT(x)比较:
- TS大，则允许，并更新WT；
- 否则拒绝并重启

托马斯写规则

过时的写操作可以直接被忽略，从而无需撤销过时的事务

读取调度：
- 如果 $TS\lt WT$ 则回滚T
- 如果 $TS\ge WT$ $TS \geq W T$ ，读取可以实现
  - C为真，立即执行并更新RT
  - 否则，等待C为真或写事务结束
写入调度
- 如果 $TS\ge RT\land TS\ge WT$ 则立即写入，然后更新WT，复位(置0)C
- 如果 $TS\ge RT\land TS\lt WT$ $TS \geq RT \land TS < W T$ ，那么写入可实现，但是x已经有了新值
  - C为真，则进行托马斯写(忽略并继续)
  - 否则，等待C为真或写事务结束
- 如果 $TS\lt RT$ 则立即回滚并重启
提交调度：找到所有该事务写入的元素，置位它们的C
终止调度：如果有事务等待T写入，则他们要重新尝试读/写

基于有效性确认的并发控制

事务在启动时刻被赋予唯一的时间戳，来记录启动顺序
为每一活跃事务保存读写数据的集合 $RS(T)，WS(T)$
有效性确认：通过对多个事务的读写集合分析，判断是否有冲突
无效事务回滚重启
事务的三个阶段
- 读：事务从数据库中读取读集元素合中的所有元素，并在局部空间中计算出要写入的值
- 有效性确认：调度器比较读写集合，来确认有效性
- 写：事务向数据库中写入写集合中元素的值
调度器维护三个集合：
- Start：已经开始，但未完成有效性确认
- Val：已经确认有效性但尚未写入
- Fin：已经完成第三阶段的事务

有效性确认规则

冲突1：T不应进行有效性确认
- U在Fin或Val，已经经过确认
- $Fin(U)>Start(T)$ ,U在T开始前未完成
- $RS(T)\cap WS(U)\not ={\emptyset}$
冲突2：T不应进行有效性确认
- U在Val，已经经过确认
- $Fin(U)>Val(T)$ ,U在T开始确认前未完成
- $WS(T)\cap WS(U)\not ={\emptyset}$
没有冲突，则对T进行确认。

故障恢复

故障分类

事务故障

某个程序自身运行错误引起的故障
影响该事务本身
适用事务故障恢复:Undo/Redo

系统故障

由于断电、非正常关机引起的故障
影响正在运行的事务与数据库缓冲区(其中也包括已经允许的事务)
可以通过系统运行日志来恢复(Undo/Redo事务)
运行日志中定期设置和更新检查点(检查点之前的事务都已经写入)

介质故障

由于介质损坏引起
影响是全面的
可以用副本替换被损坏的数据库，完成恢复
副本恢复后，还需依据运行日志进行恢复
日志中设置转储点，在此时进行备份

日志

缓冲区处理策略

Force：内存中的数据最晚在commit时写入数据
No Steal：不允许事务在Commit前把内存中的数据写入磁盘
No Force：内存中的数据可以一直保留，在Commit后的一段时间再写入磁盘
Steal：允许事务在Commit前把数据写入磁盘

缓冲区策略与回复策略的关系

检查点

静止型
- 设置时，停止接收新事务，并等待现有事务完成和写入日志
- 日志刷新到磁盘，写入<CKPT>
非静止型
- 设置时不必关闭系统，允许新事务进入
- 写入<START CKPT(T1,...,Tk)>, 记录活动事务
- 活动事务都完成时，写入<END CKPT>

Undo型日志

对于任意事务T，按以下顺序向磁盘输出T的日志信息：

<T,X,v>(v为旧值)
OUTPUT(X)
<COMMIT T>或<ABORT T>被加入日志

恢复时，对于未完成的事务，将v写回磁盘

Redo型日志

对于任意事务T，按一下顺序向磁盘输出T的日志信息：

<T,X,v>(v为新值)
<COMMIT T>
OUTPUT(X)

恢复时，从日志起始位置正序处理，重做已提交事务的所有更改

Undo/Redo结合型日志

对于任意事务T，按一下顺序向磁盘输出T的日志信息：

<T,X,u,v>(u为旧值，v为新值)
<COMMIT T>
OUTPUT(X)

2、3可以换位。

恢复时，自前向后重复已提交的事务；自后向前撤销未完成的事务

基本概念​

DBMS的功能​

数据库系统的结构​

三个层次​

数据的结构​

关系代数和SQL​

关系​

关系完整性​

关系运算​

集合运算​

纯关系运算​

SQL​

建库、建表和增删改​

表查询​

视图​

完整性约束​

数据库访问控制​

嵌入式SQL​

数据库设计​

数据建模和数据库设计​

ER模型​

Crow’s Foot法​

设计过程​

概念数据库设计-可能冲突​

错误设计引起的问题​

IDEF1x​

数据依赖​

函数依赖​

完全函数依赖​

传递函数依赖​

候选键​

逻辑蕴含​

闭包​

覆盖​

多值依赖​

连接依赖​

关系模式设计范式​

模式分解​

关系分解的性质​

无损连接分解​

无损连接分解检验算法​

+分解为两个关系模式的检验算法​

%保持依赖分解​

保持依赖性检验算法​

分解算法​

无损分解为BCNF​

保持依赖分解为3NF​

%无损并保持依赖分解为3NF/4NF​

关系模式设计折衷​

数据库实现原理​

数据库的物理储存​

记录区分与属性值区分​

文件组织方法​

索引方法​

%B+树​

插入-分裂​

删除-合并​

B树​

散列索引​

可扩展散列索引​

线性散列索引​

查询实现​

连接操作的实现方法​

表空间扫描​

迭代器算法​

两趟扫描算法​

两段多路归并排序TPMMS​

基于排序的两趟扫描​

基于散列的两趟扫描​

查询优化​

逻辑优化策略​

关系代数操作等价性​

优化算法​

并发控制​

三种不一致性​

事务​

事务调度表达模型​

操作冲突​

冲突可串行性判别算法​

基于锁的并发控制​