数据库

数据库系统概念

数据库知识汇总

Posted by Birdie on May 2, 2022

第一章 引言

数据库管理系统是一个相互关联的数据的集合和一组用以访问这些数据的程序组成。这个数据集合称为数据库。

信息存储结构的定义、信息操作机制的提供、安全性保证

1.2 数据库系统的目标

文件处理系统

  • 数据的冗余和不一致
  • 数据访问困难
  • 数据孤立：数据分散、格式不同
  • 完整性问题：数据库中存储的数据满足一致性约束
  • 原子性问题
  • 并发访问异常：多个用户同时更新数据
  • 安全性问题

1.3 数据视图

数据库系统是一些相互关联的数据以及一组使得用户可以访问和修改这些数据的程序的集合。主要目的是给用户提供数据的抽象视图。

1.3.1 数据抽象

  • 物理层：描述复杂的底层数据结构
  • 逻辑层：描述数据库中存储什么数据以及这些数据间存在什么关系。物理数据独立（应用程序不依赖于物理模式）
  • 视图层：描述整个数据库的某个部分

1.3.2 实例和模式

特定时刻存储在数据库中的信息的集合称作数据库的一个实例。

数据库的总体设计称作数据库模式。

1.3.3 数据模型

数据库结构的基础是数据模型。

  • 关系模型：：用表的集合表示数据和数据间的关系
  • 实体-联系模型
  • 基于对象的数据模型：E-R模型增加了封装、方法（函数）和对象标识等概念后的扩展
  • 半结构化数据模型：允许相同类型的数据项含有不同的数据集的数据定义

1.4 数据库语言

数据定义语言定义数据库模式，数据操纵语言表达数据库的查询和更新。

1.4.1 数据操纵语言

增删改查

过程化DML：要求用户指定需要什么数据以及如何获得这些数据

声明化DML：只要求用户指定需要什么数据

1.4.2 数据定义语言

数据库系统所使用的存储结构和访问方式是通过一系列的DDL语句来说明。

数据值必须满足某些一致性约束

  • 域约束（值域）
  • 参照完整性：一个关系中给定属性集在另一关系的某一属性集中出现
  • 断言
  • 授权

DDL的输出放在数据字典中，数据字典包含了元数据，元数据是关于数据的数据。可以把数据字典看作是一种特殊的表，这种表只能由数据库系统本身来访问和修改。在读取和修改实际数据前，数据库系统要先参考数据字典。

1.5 关系数据库

1.5.1 表

每个表包含了一种特定数据的记录，每种记录类型定义固定数目的字段或属性。表的列对应记录类型的属性。

存储：一个特殊的符号用来分隔记录的不同属性，另一个特殊符号用来分隔记录。

1.5.2 数据操纵语言

SQL的查询是非过程化的，总是仅返回一个表。

1.5.4 来自应用程序的数据库访问

  • 应用程序接口：C语言一起使用的开放数据库连接（ODBC）、Java（JDBC）
  • DML预编译器

1.6 数据库设计

提供概念框架、说明用户数据需求；

选定数据模型、将需求转换成数据库概念模式、描述数据之间的联系；

决定包含哪些属性，如何将这些属性组织到多个表；

功能需求说明；

逻辑设计阶段，物理设计阶段。

1.6.3 实体-联系模型

E-R数据模型使用一组称作实体的基本对象，以及这些对象间的联系。

实体通过属性集合来描述；联系是几个实体之间的关联。

统一建模语言UML

映射基数

1.6.4 规范化

目标：生成一个关系模式集合，使存储信息没有不必要的冗余，能够轻松检索数据。

方法：使用函数依赖。

不良特性：信息重复，缺乏表达某些信息的能力

1.7 数据存储和查询

1.7.1 存储管理器

存储管理器是数据库系统种负责在数据库种存储低级数据与应用程序以及向系统提交的查询之间提供接口的部件。

存储管理器将各种DML语句翻译为底层文件系统命令。

存储管理部件

  • 权限及完整性管理器
  • 事务管理器
  • 文件管理器
  • 缓冲区管理器

数据结构

  • 数据文件
  • 数据字典，存储关于数据库结构的元数据，尤其是数据库模式
  • 索引

1.8 事务管理

原子性、一致性、持久性

事务是数据库应用中完成单一逻辑功能的操作集合

事务管理器：恢复管理器和并发控制管理器

1.13 数据库系统的历史

codd撰写了关系模型和在关系模型中查询数据的非过程化方法，由此关系型数据库诞生了。然后他拿了ACM图灵奖。

第二章 关系模型介绍

2.1 关系数据库的结构

关系数据库由表的集合构成。

表中一行代表了一组值之间的一种联系。

关系指代表，元组指代行，属性指代列。关系是一组特定的行。

域：允许取值的集合，域是原子的

2.2 数据库模式

数据库模式：数据库的逻辑设计 -> 表名（属性）

使用相同的属性是将不同关系的元组联系起来的一种方法

2.3 码

一个元组的属性值必须是能够唯一区分元组的

码是整个关系的一种性质，不是单个元组的性质

超码：一个或多个属性的集合，在一个关系中唯一地标识一个元组

候选码：最小的超码

主码：选中的候选码

外码：一个关系模式在属性中包括另一个关系模式的主码，前者成为外码依赖的参照关系，后者称为被参照关系

2.4 模式图

主码下划线，参照关系到被参照关系用箭头

2.6 关系运算

  • 选出满足一些特定谓词的特殊元组
  • 选出特定的属性
  • 连接运算：来自两个关系的元组对合并成单个元组
    • 自然连接
    • 笛卡尔积运算
  • 集合运算

image-20220103235632512

第三章 SQL

3.1 SQL查询语言概览

组成部分

  • 数据定义语言
  • 数据操纵语言
  • 完整性
  • 视图定义
  • 事务控制
  • 嵌入式SQL和动态SQL
  • 授权

3.2 SQL数据定义

DDL能够定义

  • 每个关系的模式
  • 每个属性的取值类型
  • 完整性约束
  • 每个关系维护的索引集合
  • 每个关系的安全性和权限信息
  • 每个关系在磁盘上的物理存储结构

3.2.1 基本类型

char varchar int smallint numeric real double float

numeric(p, d) 其中p是总位数，d是小数点右边的位数

char(n) 不满n为后面补空格

3.2.2 基本模式定义

create table r (
	name type (not null),
    ...
    <完整性约束>
    (primary key(name),)
    (foreign key(name) references r)
);

alter table r add name type;
alter table r drop name;

3.3 SQL查询的基本结构

3.3.1 单关系查询

select distinct name from r; -- 强行删去重复
select all name from r; -- 显式表明不删去重复

from 中采用笛卡尔积

3.3.3 自然连接

a natural join b, c
-- 先计算a自然连接b，结构笛卡尔积c
a join b using (type)

3.4 附加的基本运算

3.4.1 更名运算

oldname as newname
-- 相关名称，表别名，相关变量，元组变量

3.4.2 字符串运算

SQL 大小写敏感，MySQL 和 SQL Server 不区分大小写

|| -- 串联
upper(s), lower(s)
trim(s) -- 去掉字符串后面的空格

like：
% -- 匹配任意子串
_ -- 匹配任意一个字符

escape --定义转义字符
like 'ab\%cd%' escape '\' -- 匹配'ab%cd'开头的字符串

3.4.4 排序元组的显示次序

order by --默认升序
order by salary desc, name asc -- 降序和升序

3.4.5 where 子句谓词

between a and b --[a, b]
not between
(a, b) <= (c, d) -- a <= b and c <= d

3.5 集合运算

union -- 并，自动去除重复
union all --保留所有重复
intersect -- 交
except -- 减

3.6 空值

1 < null -- 假（因为unknown）
not (1 < null) -- 真
is unknown
is not unknown
|('a', null),('a', null)| -- 是相同的
null = null -- unknown，不是true

如果元组在所有属性上的取值相等，那么他们就被当作相同元组，即使某些值为空。

3.7 聚集函数

聚集函数是以值的一个集合为输入，返回单个值的函数。

  • 平均值：avg
  • 最小值：min
  • 最大值：max
  • 总和：sum
  • 计数：count

sum和avg的输入必须是数字集，其他运算还可以作用在非数字数据类型的集合上。

distinct 去除重复

3.7.2 分组聚集

在 group by 子句中的所有属性上取值相同的元组将被分在一个组中。

select dept_name, avg(salary)
from instructor
group by dept_name;

需要保证出现在select语句中但没有被聚集的属性只能出现在group by子句中的那些属性。

3.7.3 having 子句

having子句中的谓词在形成分组后才起作用

需要保证出现在having子句中但没有被聚集的属性只能出现在group by子句中。

顺序：

  1. 根据from子句计算出一个关系
  2. where作用在from的结果中
  3. 满足where的元组通过group by形成分组，若没有group by，整个是一个分组
  4. having作用到每个分组上，不满足的分组被抛弃
  5. select在每个分组上应用聚集函数得到单个元组的结果

3.7.4 对空值和布尔值的聚集

除了count(*)外所有的聚集函数都忽略输入集合中的空值。

空集的count运算值为0，其他聚集函数在输入为空集的情况下返回空值。

3.8 嵌套子查询

3.8.1 集合成员资格

in和not in也能用于枚举集合。

3.8.2 集合的比较

> some -- 至少比某一个大
= some -- 等价于in
> all -- 比所有的都大
<> all -- 等价于not in

3.8.3 空关系测试

exists 结构在作为参数的子查询非空时返回true

使用了外层查询相关名称的子查询被称作相关子查询

not exists (B except A) -- 等价于关系A包含关系B

3.8.4 重复元组存在性测试

如果作为参数的子查询结果中没有重复的元组，unique结构将返回true

not unique 测试子查询结果是否存在重复元组

3.8.5 from子句中的子查询

可以使用as子句给子查询的结果关系起个名字，并对属性进行重命名。

select max(tot_salary)
from (...) as dept_total(dept_name, tot_salary)

from 子句嵌套子查询中不能使用来自其他from子句其他关系的相关变量

lateral作为前缀，以便访问from子句中在它前面的表或者子查询中的属性

select ...
from I1, lateral (select ...
                 from I2
                 where I1.xx = I2.xx);

没有lateral子句，子查询不能访问I1

3.8.6 with子句

定义临时关系

with max_budget(value) as (
    select max(budget) from department)
select budget
from department, max_budget
where department.budget = max_budget.value;

3.9 数据库的修改

3.9.1 删除

delete from r where P; -- 如果忽略where,r中全删

delete只能作用于一个关系

3.9.2 插入

insert into r() values ();

3.9.3 更新

update r set a = b;
update r
set a = case
	when pred1 then result1
	when pred2 then result2
	...
	else result0
	end;
-- 为了防止结果为null，使用case判断

第四章 中级SQL

4.1 连接表达式

4.1.1 连接条件

select *
from r1 join r2 on r1.xx = r2.xx;

4.1.2 外连接

  • 左外连接(left outer join)只保留出现在左外连接运算左边的关系中的元组
  • 右外连接(right outer join)只保留出现在右外连接运算右边的关系中的元组
  • 全外连接(full outer join)保留出现在两个关系中的元组
-- 找出所有一门课程也没有选修的学生
select ID
from student natural left outer join takes
where course_id is null;

使用on和where的区别在于，前者会补充空值，而后者不会

4.2 视图

让所有用户看到整个逻辑模型是不合适的。出于安全考虑，需要向用户隐藏特定的数据。

4.2.1 视图定义

create view v() as <query>;

4.2.3 物化视图

如果用于定义视图的实际关系改变，视图也跟着修改。这样的视图称为物化视图。

4.2.4 视图更新

可更新视图

  • from子句中只有一个数据库关系
  • select子句中只包含关系的属性名，不包含任何表达式、聚集或者distinct声明
  • 任何没有出现在select子句中的属性可以取空值，没有not null约束
  • 查询中不含有group by或having子句

4.3 事务

事务由查询和更新语句的序列组成。下列SQL语句会结束一个事务：

  • commit work
  • rollback work

事务具有原子性

4.4 完整性约束

完整性约束防止的是对数据的意外破坏。

4.4.1 单个关系上的约束

  • not null
  • unique
  • check(<谓词>)

4.4.2 not null约束

主码隐式not null

4.4.3 unique约束

unique声明指出属性形成了一个候选码，候选码属性可以为null，null不等于其他任何值

4.4.5 参照完整性

on delete cascade
on update cascade,
-- 级联

4.4.6 事务中对完整性约束的违反

initially deferred加入到约束声明，在事务结束的时候检查约束

4.4.7 复杂check条件与断言

create assertion name check ();

只有不破坏断言的数据库修改才被允许。

4.5 SQL的数据类型与模式

4.5.1 SQL中的日期和时间类型

  • date：4位年、月、日
  • time：时分秒，time(p)表示秒的小数点后位数，默认为0；time with timezone可以存储时区信息
  • timestamp：date和time的组合，timestamp(p)表示秒的小数点后位数，默认为6
data '2001-04-25'
time '09:30:00'
timestamp '2001-04-25 10:29:01.45'

-- 将e转换成上述三种类型
case e as t

-- 从date或time值d中，提取出单独的域
extract(field from d)
field in (year, month, day, hour, minute, second, timezone_hour, timezone_minute)

current_date
current_time -- 带时区
localtime -- 不带时区

interval -- 数据类型，允许时间进行加减运算

4.5.2 默认值

default

4.5.3 创建索引

索引是一种数据结构，允许数据库高效地找到关系中在树荫属性上给出定值的元组，而不用扫描所有关系

create index a_index on r(a);

4.5.4 大对象类型

a clob(10KB)
b blob(2GB) -- 二进制大对象

4.5.5 用户定义的类型

独特类型

create type Dollars as numeric(12, 2) final;
create type Pounds as numeric(12, 2) final;
-- 将Pounds类型赋值给Dollars会出错

域

create domain Dollars as numeric(12, 2)
	constraint value_test check(value >= 10);

域上可以声明约束，如not null

域不是强制类型，类型相容即可赋值

4.5.6 create table的扩展

create table r1 like r2;

create table r1 as (
	select * from r2 where ...)
with data;
-- 省略data将不会载入数据

4.6 授权

授权读取数据、插入、更新、删除

4.6.1 权限的授予与回收

grant <select,insert,update,delete>
on r() -- 表或者属性
to <用户/角色列表>

revoke <> on r() from <>

4.6.2 角色

角色有助于根据用户在组织机构中扮演的角色，把一组权限分配给用户。

create role ...;
grant 角色 to ...;

角色可以构成一条链

4.6.5 权限的转移

with grant option;

用户具有权限的充要条件是，当且仅当存在从授权图的根到代表该用户顶点的路径。

4.6.6 权限的回收

revoke select on ... from ... restrict;

默认是级联的，防止级联回收

revoke grant option for ......

set role ...
granted by current_role
-- 不会级联回收

第五章 高级SQL

5.2 函数和过程

5.2.1 声明和调用SQL函数和过程

函数

create function name(var type) returns type or table
begin
	...
	return ...;
end

过程

create procedure name(in var type, out var type...)
begin
	...
end

5.2.2 支持过程和函数的语言构造

变量

declare ... type (default ...);
set @... = ...;

事务

begin atmoic
	...
end

循环

while ... do
	...
end while

repeat
	...
until ...
end repeat

declare n integer default 0;
for r as
	table
do
	set n = ...
end for

条件

if ... then
	...
elseif ...
	...
else
	...
end if

句柄

declare name condition
declare exit handler for name
begin
	...
end

5.3 触发器

5.3.2 SQL中的触发器

create trigger ... after insert on ...
	referencing new row as nrow
	for each row
	when ...
begin
	rollback
end;

第六章 形式化关系查询语言

6.1 关系代数

关系代数基本运算：选择、投影、并、集合差、笛卡尔积和更名。

其他运算：集合交、自然连接和赋值。

6.1.1 基本运算

选择、投影和更名是一元运算，并、集合差和笛卡尔积是二元运算。

6.1.1.1 选择运算
\[\sigma_{谓语}(r)\]

$=,\neq,<,\leq,>,\geq,\and,\or,\neg$

6.1.1.2 投影运算
\[\Pi_{name}(r)\]
6.1.1.7 更名运算
\[\rho_x(E)\]

返回表达式 E 的结果，并且把名字 x 赋给它。

6.1.3 附加的关系代数运算

集合交$r\bigcap s=r-(r-s)$

自然连接$\Join$

赋值$var\larr r$

外连接

image-20220105203749960

聚集运算$\mathcal{G}_{sum(salary)}(r)$，分组的话在$\mathcal{G}$的左下角写

6.2 元组关系演算

\[\lbracet|P(t)\rbrace\\ \lbracet|t\in instructor \and t[salary]>80000\rbrace\]

6.3 域关系演算

\[\left\lbrace<x_{1}, x_{2}, \cdots, x_{n}>\mid P\left(x_{1}, x_{2}, \cdots, x_{n}\right)\right\rbrace\]

第七章 数据库设计和E-R模式

7.1 设计过程概览

7.1.1 设计阶段

  • 完整地刻画未来数据库用户的数据需求。
  • 选择数据模型，并采用所选数据模型的概念将这些需求转换成数据库的概念模式。
    • 概念设计阶段：实体-联系图的构建
    • 检查确保所有数据满足，并且互相不冲突，去除冗余特征
  • 指明企业的功能需求，描述在数据上的各类操作。
  • 逻辑设计阶段，将高层概念模式映射到将使用的数据库系统的实现数据模型上。
  • 将所得到的系统特定的数据库模式使用到后续的物理设计阶段。

7.1.2 设计选择

  • 冗余：一个不好的设计可能会重复信息。
  • 不完整：一个不好的设计可能会使得某些方面难于甚至无法建模。

7.2 联系-实体模型

7.2.1 实体集

实体是现实世界中可以区别于其他对象的一个事务或对象。

实体集是相同类型的一个实体集合。

实体可以通过一组属性来表示。

每个实体的每个属性都有一个值。

7.2.2 联系集

联系是指多个实体间的相互关联。

联系集是相同类型联系的集合。

实体集之间的关联称为参与。

实体在联系中扮演的功能称为实体的角色。

联系可以具有描述性属性。

7.2.3 属性

每个属性有一个可取值的集合，称为该属性的域。

属性分类：

  • 简单和复合
  • 单值和多值
  • 派生属性

7.3 约束

7.3.1 映射基数

映射基数表示一个实体通过一个联系集能关联的实体的个数。

7.5 实体-联系图

7.5.1 基本结构

  • 分成两部分的矩形代表实体集
  • 菱形代表联系集
  • 未分割的矩形代表联系集的属性
  • 线段将实体集连接到联系集
  • 虚线将联系集属性连接到联系集
  • 双线显示实体在联系集中的参与度
  • 双菱形代表连接到弱实体集的标志性联系集

image-20220106123655547

7.5.2 映射基数

image-20220106124127390

l..h表示，l是最小的映射基数，h是最大的映射基数。

l=1表示这个实体集在联系集中全部参与

h=*表示没有限制

7.5.4 角色

菱形和矩形之间的连线上标注角色。

7.5.6 弱实体集

没有足够的属性以形成主码的实体集称作弱实体集。有主码的实体集称作强实体集。

弱实体集必须与另一个称作标识或属主实体集的实体集关联才有意义。

弱实体集存在依赖于标识实体集，标识实体集拥有它所标识的弱实体集。

将若实体集与其标识实体集相联的联系称为标识性联系。

标识性联系是从弱实体集到标识实体集多对一的，并且若实体集在联系中是全部参与的。

弱实体集的分辨符是使得我们进行这种区分的属性集合。弱实体集的分辨符也称为该实体集的部分码。

弱实体集的主码由标识实体集的主码加上该弱实体集的分辨符构成。

  • 弱实体集的分辨符以虚下划线表明
  • 关联弱实体集和标识性强实体集的联系集以双菱形标识

image-20220106132256188

7.8 扩展的E-R特性

特化、概化、高层和底层实体集、属性继承和聚集

7.8.1 特化

在实体集内部进行分组的过程称为特化

一个实体集可能属于多个特化实体集，称为重叠特化；

一个实体集必须属于至多一个特化实体集，称为不相交特化。

重叠特化分开使用两个箭头；

不相交特化使用一个箭头。

7.8.2 概化

概化是一个高层实体集与一个或多个底层实体集之间的包含关系。

高层与底层实体集也可以称作超类和子类。

概化是特化的逆过程。

7.8.3 属性继承

高层实体集的属性被底层实体集继承。

层次结构：单继承、多继承（格）

7.8.4 概化上的约束

约束一

  • 条件定义的。属性定义
  • 用户定义的。

约束二

​ 不相交、重叠

约束三

  • 全部概化或特化
  • 部分概化或特化

7.8.5 聚集

聚集是一种抽象，通过这种抽象，联系被视为高层实体。

image-20220106145607498

7.9 数据建模的其他表示法

image-20220106145847635

7.10 数据库设计的的其他方面

  • 数据约束和关系数据库设计
  • 使用需求：查询、性能
  • 授权需求
  • 数据流、工作流

7.10.2 使用需求：查询、性能

  • 吞吐量：每单位时间里能够处理的查询或更新的平均数量
  • 响应时间：单个事务从开始到结束所需的平均时间或最长时间

第八章 关系数据库设计

8.1 好的关系设计的特点

8.1.2 设计选择：更小的模式

无损分解：将表分解后依旧能够区分出属性的归属。

8.2 原子域和第一范式

一个域是原子的，如果该域的元素都是不可分的单元。

第一范式：R的所有属性的域都是原子的。

8.3 使用函数依赖进行分解

r(R)表示，该模式是关系r的，R表示属性集。

K是r(R)的超码

8.3.1 码和函数依赖

image-20220106214306947

如果$\beta\subseteq\alpha$，则形如$\alpha\rarr\beta$的函数依赖是平凡的。

$F^+$表示F集合的闭包。

8.3.2 Boyce-Codd范式

消除所有基于函数依赖能够发现的冗余。

对$F^+$中所有形如$\alpha\rarr\beta$的函数依赖，下面至少有一项成立：

  • $\alpha\rarr\beta$是平凡的
  • $\alpha$是超码

如果$\alpha$和$\beta$不满足，用下面两个模式取代R：

  • $\alpha\cup\beta$
  • $R-(\beta-\alpha)$

8.3.4 第三范式

对$F^+$中所有形如$\alpha\rarr\beta$的函数依赖，下面至少有一项成立：

  • $\alpha\rarr\beta$是平凡的
  • $\alpha$是超码
  • $\beta-\alpha$中的每个属性都包含于R的一个候选码中

8.4 函数依赖理论

8.4.1 函数依赖集的闭包

Armstrong公理

  • 自反律：若$\beta\subseteq\alpha$，则$\alpha\rarr\beta$
  • 增补律：若$\alpha\rarr\beta$，则$\gamma\alpha\rarr\gamma\beta$
  • 传递律

推导出

  • 合并律：若$\alpha\rarr\beta$和$\alpha\rarr\gamma$，则$\alpha\rarr\beta\gamma$
  • 分解律：上面那个反过来
  • 伪传递律：传递加增补

image-20220106220532953

8.4.2 属性集的闭包

image-20220106232050035

8.4.3 正则覆盖

image-20220106232404702

本质上就是是不是可以删掉他还成立。

image-20220107000511222

本质上就是删掉他，然后算闭包，看看是不是能够推出他。

image-20220107000641938

本质就是找到一个最小的F。

image-20220107000720186

本质就是，先合并，然后删，迭代。

8.4.4 无损分解

分解后没有信息损失。

如果$R_1\cap R_2$是$R_1$或$R_2$的超码，那么分解是无损的。

8.4.5 保持依赖

F 在$R_i$上的限定是$F^+$中所有只包含$R_i$中属性的函数依赖的集合。

也就是说，是所有依赖，这些依赖的每一个属性都在$R_i$里面。

$F’$是所有$R_i$上限定的并，如果$F’^+=F^+$的分解为保持依赖的分解。

image-20220107015113663

保持依赖的判断。
如果F上的每一个函数依赖都在其分解后的某一个关系上成立，则这个分解是保持依赖的（这是一个充分条件）。
如果上述判断失败，并不能断言分解不是保持依赖的，还要使用下面的通用方法来做进一步判断。
该方法的表述如下：
算法二：
对F上的每一个α→β使用下面的过程：
result:=α;
while(result发生变化)do
    for each 分解后的Ri
        t=(result∩Ri)+ ∩Ri
        result=result∪t

这里的属性闭包是在函数依赖集F下计算出来的。如果result中包含了β的所有属性，则函数依赖α→β。分解是保持依赖的当且仅当上述过程中F的所有依赖都被保持。

8.5 分解算法

8.5.1 BCNF分解

8.5.1.1 BCNF的判定

方法一

  • 对$\alpha\rarr\beta$，计算$a^+$，验证是否包含R中所有属性
  • 只需检查给定集合F中的函数依赖

方法二

对于分解后$R_i$的每个$\alpha$，确保$\alpha^+$要么不包含$R_i-\alpha$，要么包含$R_i$

8.5.1.2 BCNF分解算法

image-20220107015754669

8.5.2 3NF分解

找出F的一个最小基本集，记为G。
对于G中的每一个FD X→A，将XA作为分解出的某个关系的模式。
如果第2步分解出的关系的模式均不包含R的超键，则增加一个关系，其模式为R的任何一个键。

image-20220107020114959

8.6 使用多值依赖的分解

8.6.1 多值依赖

函数依赖——相等产生依赖

多值依赖——元组产生依赖

多值依赖：$\alpha\rarr\rarr\beta$

多值依赖是说$\alpha$和$\beta$之间的联系独立于$\alpha$和$R-\beta$之间的联系。

image-20220107020711729

image-20220107021157190

image-20220107020726247

8.6.2 第四范式

image-20220107021311393

将BCNF拓展到多值依赖上。

8.6.3 4NF分解

在$D_i$上的限定

image-20220107021528891

image-20220107021428012

第十章 存储和文件结构

全是操统，不看不看

10.8 数据库缓冲区

10.8.2 缓冲区替换策略

LRU 最近最少使用块策略

MRU 最近最长使用块策略

第十一章 索引与散列

11.2 顺序索引

目的：快速随机访问文件中的记录

聚集索引（主索引）：包含记录的文件按照某个搜索码指定的顺序排序

索引顺序文件：在搜索码上由聚集索引的文件

11.2.1 稠密索引和稀疏索引

索引项（索引记录）由一个搜索码值和指向具有该搜索码值的一条或者多条记录的指针构成。

  • 稠密索引：文件中每个搜索码值都有一个索引项。
  • 稀疏索引：只为搜索码的某些值建立索引项。

稠密索引 稠密索引中，文件中每个记录有一个关联的索引项。 在稠密聚集索引中，索引项包括搜索码值以及指向具有该搜索码值的第一条数据记录的指针。 具有相同搜索码值的其余记录顺序地存储在第一条数据记录之后，记录根据相同的搜索码值排序。 在稠密非聚集索引中，索引必须存储指向所有具有相同搜索码值的记录的指针列表。

稀疏索引 在稀疏索引中，只为搜索码的某些值建立索引项。 只有索引是聚集索引时才能使用稀疏索引。

11.2.4 辅助索引

聚集索引：按照每张表的主键构造一棵B+树，同时叶子节点中存放的即为整张表的行记录数据，也将聚集索引的叶子节点称为数据页。

辅助索引：叶子节点并不包含行记录的全部数据。叶子节点除了包含键值以外，每个叶子节点的索引行中还包含了一个书签。该书签用于高速存储引擎哪里可以找到与索引相对应的行数据。

一个索引，其搜索键指定的顺序与文件的顺序不同。

举例说明，如果在一棵高度为3的辅助索引树中查找数据，那需要对这棵辅助索引树遍历3次找到指定主键，如果聚集索引树的高度同样为3，那么还需要对聚集索引树进行3次查找，最终找到一个完整的行数据所在的页，因此一共需要6次逻辑IO访问以得到最终的一个数据页。

辅助索引必须是稠密索引

11.3 $\text{B}^+$树索引

B+树索引采用平衡树结构，树根到树叶的每条路径的长度相同。

树中每个非叶结点有$\lceil\frac{n}{2}\rceil$到$n$个子女。

11.3.1 B+树的结构

p1 k1 p2 k2 p3

p2指向的子树[k1, k2)

最多n-1个搜索码值，n个指针

叶子节点最多n-1个值，最少$\lceil(n-1)/2\rceil$

非叶结点（内部结点）有$\lceil\frac{n}{2}\rceil$到$n$个指针，指针叫扇出

除非整棵树只有一个结点，根节点必须至少包含两个指针

11.3.2 B+树的查询

文件中有N个搜索码值，查询路径长度不超过$\lceil\text{log}_{\lceil n/2\rceil}(N)\rceil$

11.3.3 B+树的更新

11.3.3.1 插入

分裂是1到$\lceil n/2\rceil$，$\lceil n/2\rceil+1$到n

11.6 静态散列

11.6.1 散列函数

  • 分布是均匀的
  • 分布是随机的

11.6.2 桶溢出处理

  • 桶不足
  • 偏斜

闭地址：溢出后就开一个溢出桶，有溢出链

开地址：一个桶满了就插到其他桶

  • 线性探查法（按轮转顺序，放下一个）

11.7 动态散列

[(25条消息) 数据库] 图解动态散列的插入操作_(ง •̀_•́)ง-CSDN博客_动态散列

取高位

11.9 位图索引

位图是一个二进制数组，长度为表的行数。

对于一个属性，有多少类就有多少个位图，每个位图中，如果一行在在该类上，那么位图的这一位是1，否则是0。

image-20220108161139665

11.10 SQL中的索引定义

create index index_name on r(属性)
create unique index index_name on r(属性) -- 候选码

第十二章 查询处理

查询处理是指从数据库中提取数据时设计的一系列活动。

12.1 概述

基本步骤：

  1. 语法分析与翻译
  2. 优化
  3. 执行

计划原语：加了“如何执行”注释的关系代数运算

查询执行计划：用于执行一个查询的原语

查询执行引擎：接受一个查询执行计划，执行该计划并把结果返回给查询

12.2 查询代价的度量

传输一个块的数据平均消耗$t_r$秒，磁盘块平均访问时间$t_s$秒。

12.3 选择运算

12.3.1 使用文件扫描和索引的选择

索引结构称为存取路径。

使用索引的搜索算法称为索引扫描。

  • A1（线性搜索）
  • A2（主索引，码属性等值比较）
  • A3（主索引，非码属性等值比较）
  • A4（辅助索引，等值比较）
  • A5（主索引，比较）
  • A6（辅助索引，比较）
  • A7（利用一个索引的合取选择）
  • A8（使用组合索引的合取选择）
  • A9（通过标识符的交实现合取选择）
  • A10（通过标识符的并实现合取选择）

image-20220109131843532

12.4 排序

12.4.1 外部排序归并算法

对不能全部放在内存中的关系的排序称为外排序。

  1. 建立多个排好序的归并段。
  2. 对归并段进行归并。

12.4.2 外部排序归并的代价分析

$b_r$代表包含关系r中记录的磁盘块数，M表示内存缓冲区中可以用于排序的块数

磁盘块传输总数：$b_r(2\lceil\text{log}_{M-1}(b_r/M)\rceil+1)$

磁盘搜索总数：$2\left\lceil b_{r} / M\right\rceil+\left\lceil b_{r} / b_{b}\right\rceil\left(2\left\lceil\log {\left\lfloor M / b{b}\rfloor-1\right.}\left(b_{r} / M\right)\right\rceil-1\right)$

12.5 连接运算

连接r和s

12.5.1 嵌套循环连接

image-20220109141822582

磁盘块传输总数：$n_r*b_s+b_r$

磁盘搜索总数：$n_r+b_r$

12.5.2 块嵌套循环连接

image-20220109141851408

磁盘块传输总数：$b_r*b_s+b_r$

磁盘搜索总数：$2b_r$

12.5.3 索引嵌套循环连接

时间代价：$b_r(t_r+t_s)+n_r*c$

12.5.4 归并连接

磁盘块传输总数：$b_r+b_s$

磁盘搜索总数：$\lceil b_r/b_b\rceil+\lceil b_s/b_b\rceil$

12.5.5 散列连接

$n_k$个划分

不进行递归划分：

  • 磁盘块传输总数：$3(b_r+b_s)+4n_k$

    磁盘搜索总数：$2\lceil b_r/b_b\rceil+\lceil b_s/b_b\rceil+2n_k$

  • 磁盘块传输总数：$2\left(b_{r}+b_{s}\right)\left\lceil\log {M-1}\left(b{s}\right)-1\right\rceil+b_{r}+b_{s}$

    磁盘搜索总数：$2\left(\left\lceil b_{r} / b_{b}\right\rceil+\left\lceil b_{s} / b_{b}\right\rceil\right)\left\lceil\log {M-1}\left(b{s}\right)-1\right\rceil$

第十三章 查询优化

查询优化就是从所有策略中找出最有效的查询执行计划的一种处理过程。

第十四章 事务

构成单一逻辑工作单元的操作集合称作事务。

14.1 事务概念

事务是访问并可能更新各种数据项的一个程序执行单元。

事务用形如 begin transaction 和 end transaction 语句来界定。

  • 原子性：事务是不可分割的。
  • 隔离性：事务不被来及并发执行的数据库语句干扰。
  • 持久性：崩溃后事务的操作也必须是持久的。
  • 一致性：数据库的一致性。

ACID 特性。

14.4 事务原子性和持久性

中止：事务并非总能成功地执行完成。

已回滚：中止事务造成的变更被撤销。

方法：维护一个日志。

已提交：成功完成执行的任务。

撤销已提交事务所造成影响的唯一方法是执行一个补偿事务。

事务必须处于以下状态之一：

  • 活动的
  • 部分提交的：最后一条语句执行后
  • 失败的
  • 中止的：事务回滚并且数据库已恢复到事务开始执行前的状态后
  • 提交的

处理可见的外部写：在非易失性存储设备中临时写下与外部写相关的所有数据，然后再事务进入提交状态后再执行真正的写操作。

14.5 事务隔离性

并发的理由：

  • 提高吞吐量和资源利用率
  • 减少等待时间

执行的顺序称为调度。

在并发执行中，通过保证所执行的任何调度的效果都与没有并发执行的调度效果一样，确保数据库的一致性，这种调度称为可串行化。

14.6 可串行化

当 I 和 J 是不同事务在相同的数据项上的操作，并且其中至少有一个是 write 指令，I 和 J 是冲突的。

如果调度 S 可以通过一系列非冲突指令交换转换称为 S‘，称 S 和 S’ 是冲突等价的。

若一个调度 S 与一个串行调度冲突等价，则成调度 S 是冲突可串行化的。

优先图，边$T_i\rarr T_j$

  • 在$T_j$ read 之前$T_i$ write
  • 在$T_j$ write 之前$T_i$ read
  • 在$T_j$ write 之前$T_i$ write

优先图无环是冲突可串行化的。

串行化顺序可以通过拓扑排序得到。

如果某个调度视图等价于一个串行调度，则称该调度是视图可串行化的。

image-20220111144032082

14.7 事务隔离性和原子性

14.7.1 可恢复调度

可恢复调度满足：对于每对$T_i$和$T_j$，如果$T_j$读取了之前由$T_i$所写的数据项，则$T_i$先于$T_j$提交。

14.7.2 无级联调度

无级联调度满足：对于每对$T_i$和$T_j$，如果$T_j$读取了之前由$T_i$所写的数据项，则$T_i$先于$T_j$提交。

14.8 事务隔离级别

  • 可串行化
  • 可重复读：只允许读取已提交数据，并且在一个事务两次读取一个数据项期间，其他事务不得更新该数据。
  • 已提交读：只允许读取已提交数据，但不要求可重复读。
  • 未提交读：允许读取未提交数据。

以上所有隔离性级别都不允许脏写。默认隔离性级别是已提交读。

14.9 隔离性级别的实现

14.9.1 锁

两阶段封锁要求一个事务由两个阶段，一个阶段只获得锁但不释放锁，第二个阶段只释放锁但是不获得锁。

共享锁用于事务读的数据项，而排他锁用于事务写的数据项。许多事务可以同时持有一个数据项上的共享锁，但是只有当其他事务在一个数据项上不持有任何锁时，一个事务才允许持有该数据项上的排他锁。

14.9.2 时间戳

数据项的读时间戳记录读该数据项的事务的最大的时间戳。

数据项的写时间戳记录写入该数据项当前值的事务的时间戳。

第十五章 并发控制

15.1 基于锁的协议

15.1.1 锁

共享锁可读不能写。

排他锁可读也可写。

共享锁与共享锁是相容的，而与排他锁不相容。

15.1.2 锁的授予

防止饿死：当事务$T_i$申请对 Q 加 M 型锁时：

  1. 不存在在数据项 Q 上持有与 M 型锁冲突的锁的其他事务
  2. 不存在等待对数据项 Q 加锁且先于$T_i$申请加锁的事务

15.1.3 两阶段封锁协议

  1. 增长阶段：事务可以获得锁但不释放锁。
  2. 缩减阶段：事务可以释放锁但是不获得锁。

在调度中该事务获得其最后加锁的位置称为事务的封锁点。

强两阶段封锁协议：事务在提交前不能释放任何锁。

锁转换：锁升级只能发生在增长阶段，降级只能发生在缩减阶段。

15.1.4 封锁的实现

锁管理器实现从事务接受消息并反馈信息。维护锁表。

image-20220111142552067

15.1.5 基于图的协议

数据库图：有向无环图

树形协议：只是用排他锁

  1. $T_i$首次加锁可以对任何数据项进行。
  2. 此后，$T_i$对数据项 Q 加锁的前提是$T_i$当前持有 Q 的父项上的锁。
  3. 对数据项解锁可以随时进行。
  4. 数据项被$T_i$加锁并解锁后，$T_i$不能再对该数据项加锁。

满足树形协议的调度是冲突可串行化的。

15.2 死锁处理

  • 使用死锁预防协议保证系统永不进入死锁状态。
  • 允许系统进入死锁状态，用死锁检测和死锁恢复机制进行恢复。

都会引起事务回滚。

如果系统进入死锁状态的概率相对较高，通常使用死锁预防机制。

15.2.1 死锁预防

  • 每个事务在开始之前封锁它的所有数据项

    • 缺点
      • 事务开始前不知道哪些数据项需要封锁
      • 效率低
    • 变种：对所有数据项加一个次序，要求事务只能按次序规定的顺序封锁数据项（两阶段锁关联的全序）

  • 抢占与事务回滚

    • wait-die：当事务 i 申请的数据项被 j 持有，仅当 i 的时间戳小于 j 的时间戳，允许 i 等待；否则 i 回滚。
    • wound-wait：（和wait-die相反）当事务 i 申请的数据项被 j 持有，仅当 i 的时间戳大于 j 的时间戳，允许 i 等待；否则 i 回滚。
    • 两者都会产生不必要的回滚

  • 基于锁超时：申请锁的事务至多等待一段给定的时间，超时后回滚并重启。

    • 无法确定等待时间阈值：等待时间太长导致不必要的延迟；等待时间太短造成资源浪费

15.2.2 死锁检测与恢复

15.2.2.1 死锁检测

当且仅当等待图包含环时，系统中存在死锁。

15.2.2.2 从死锁中恢复
  1. 选择牺牲者
    • 事务已经计算的时间，还需计算的时间
    • 事务已经用了多少数据项
    • 为完成事务还需使用多少数据项
    • 回滚时将涉及多少事务
  2. 回滚
    • 部分回滚
    • 彻底回滚
  3. 饿死
    • 在选择牺牲者的因素中包含回滚次数

15.3 多粒度

系统定义多级粒度，形成一个粒度层次图（一棵树）。

如果事务给一个点显式增加锁，那么其隐式地为该节点子树上的点增加锁。

意向锁：如果一个结点加上了意向锁，意味着要在树的较低层进行显示加锁。

共享型意向锁 IS ；排他型意向锁 IX；共享排他型意向锁 SIX

多粒度封锁协议：

  1. 事务$T_i$必须遵从所类型相容函数。
  2. 事务$T_i$必须首先解锁树的根节点，并且可以加任意类型的锁。
  3. 仅当$T_i$当前对 Q 的父节点具有 IX 或 IS 锁时，$T_i$对 Q 可以加 S 或 IS 锁。
  4. 仅当$T_i$当前对 Q 的父节点具有 IX 或 SIX 锁时，$T_i$对 Q 可以加 X、SIX 或 IX 锁。
  5. 仅当$T_i$未曾对任何结点解锁时，$T_i$可以加锁。
  6. 仅当$T_i$不持有 Q 的子节点的锁时，$T_i$可以对 Q 解锁。

15.8 插入操作、删除操作与谓词读

15.8.1 删除

删除前，要加排他锁

15.8.2 插入

插入前，要加排他锁

15.7.3 谓词读和幻想现象

幻想现象：两个事务没有访问共同的元组，但他们相互冲突。

索引封锁协议：

  • 每个关系上至少有一个索引。
  • 只有在关系的索引上找到元组后，事务$T_i$才能方位这些元组。全表扫描看作是一个索引上所有叶节点的扫描。
  • 进行查找的事务$T_i$必须在它要访问的所有索引叶节点上获得共享锁。
  • 在没有更新关系上的所有索引之前，事务$T_i$不能插入、删除或者更新关系中的元组。
  • 元组照常获得锁。
  • 遵循两阶段封锁协议。

另一种方法，对查询中的谓语加共享锁。如果想增删，判断是否满足谓语，满足就存在锁冲突。

第十六章 恢复系统

16.1 故障分类

  • 事务故障
    • 逻辑错误
    • 系统错误
  • 系统崩溃
  • 磁盘故障

16.2.2 数据访问

位于磁盘上的块称为物理块。

磁盘临时位于主存的块称为缓冲块。

内存中临时存放块的区域称为磁盘缓冲区。

  • input(B) 传送物理块 B 至主存
  • output(B) 传送缓冲块 B 至磁盘
  1. read(X) 将数据项 X 的值赋予局部变量$x_i$
    • 若 X 所在块 B 不在主存中，则input(B)
    • 将缓冲块 X 的值赋予$x_i$
  2. write(X) 将局部变量$x_i$的值赋予缓冲块系统项 X
    • 若 X 所在块 B 不在主存中，则input(B)
    • 将$x_i$的值赋予缓冲块 B 中的 X

如果数据库执行output(B)，称为强制输出。

16.3 恢复与原子性

16.3.1 日志记录

日志是日志记录的序列。

更新日志记录描述一次数据库写操作，有如下字段：

  • 事务标识，执行wirte操作的唯一标识
  • 数据项标识，所写数据项的唯一标识。通常是数据项在磁盘上的位置。
  • 旧值
  • 新值

$<T_i,X_j,V_1,V_2>$表明事务$T_i$对数据项$X_j$执行了一个写操作，写之前是$V_1$，写之后是$V_2$。

$<T_i\ start>$事务开始

$<T_i\ commit>$事务提交

$<T_i\ abort>$事务中止

16.3.2 数据库修改

延迟修改：直到提交都还没修改

立即修改：修改在事务活跃时发生

  • undo使用一个日志记录，将日志记录中指明的数据项设置为旧值
  • redo使用一个日志几里路，将日志记录中指明的数据项设置为新值

16.3.5 使用日志来重做和撤销事务

对日志进行一次扫描，没遇到一个redo日志记录就执行redo动作。

优点：确保保持更新的顺序，并且效率更高，只需要整体读一次日志。

  • undo恢复后，在日志中写下redo-only日志记录，该记录不需要包含旧值。

  • 事务的undo操作完成后，写一个$<T_i\ abort>$日志记录。

系统崩溃后：

  • 如果日志包含strat，但不包含commit，也不包含abort，则需要对事务进行撤销
  • 如果日志包含start，以及commit或者abort，则需要重做。
    • 尽管日志中有abort，但是日志中也会有undo操作所写的redo-only日志记录，需要对整个事务进行一个撤销。

16.3.6 检查点

搜索整个日志文件：

  • 搜索时间长
  • 恢复过程长

检查点执行过程：

  1. 将当前位于主存的所有日志记录输出到稳定存储器
  2. 将所有修改的缓冲块输出到磁盘
  3. 将日志记录<checkpoint L>输出到稳定存储器。L是执行检查点时正活跃的事务列表。

找到最后一个检查点，扫描该检查点之后执行的事务集合T

  • 既没有commit也没有abort，执行undo
  • 有commit或者abort，执行redo

16.4 恢复算法

16.4.1 事务回滚

事务$T_i$的回滚如下：

  1. 从后往前扫描日志，对于每一个$<T_i,X_j,V_1,V_2>$
    • 将$V_1$写道$X_j$，并且
    • 往日志中加入制度日志记录$<T_i,X_j,V_1>$
  2. 一旦发现start，停止扫描，写入$<T_i,abort>$

16.4.2 系统崩溃后的恢复

  1. 重做阶段：从最后一个检查点正向扫描日志
    • 回滚的事务列表undo-list设定为<checkpoint L>中的L
    • 一旦遇到正常日志记录或者制度日志记录，就重做该操作
    • 一旦发现start，就加入undo-list
    • 一旦发现abort或者commit，将其从undo-list中删除
  2. 撤销阶段：从尾端反向扫描日志
    • 一旦发现属于undo-list中事务的日志记录，undo
    • 发现undo-list中事务的start，就写入abort，然后去掉
    • 一旦undo-list变成空表，结束

16.5 缓冲区管理

16.5.1 日志记录缓冲

先写日志：

  • 日志记录commit输出到稳定存储器后，再提交事务
  • commit输出到稳定存储器之前，与该事务相关的所有日志记录都已经输出到稳定存储器
  • 主存中数据块输出到数据库前，与数据块中数据有关的日志记录已经输出到稳定存储器

将缓冲的日志写到磁盘称为强制日志。

16.5.2 数据库缓冲

强制策略：事务提交时强制将修改过的所有块输出到磁盘。

非强制策略：即使一个事务修改了某些还没有写回到磁盘的块，也允许提交。

非窃取策略：活跃的事务修改过的块不应该写出到磁盘。

窃取策略：允许系统将修改过的块写到磁盘，即使做这些修改的事务还没有全部提交。

CATALOG
    FEATURED TAGS
    神经网络 机器学习 机器人 webot 通信原理 并行计算 信息安全 自然语言处理 数据库 数字图像处理 软件工程 编译原理 强化学习 数字电路 proteus 计算机组成原理 VIVADO JAVA 论文阅读 组合优化 NIPS AAAI IJCAI 隐私保护