TIMEGG

放进时光蛋里。

数据库系统概论笔记

2018.06.12

前言

这学期参选了数据库系统概论这门课程，虽然最后拿到了还行的成绩，但是因为复习仓促跳过了很多知识点。

由于 9 月要参加计算机四级(数据库)的考试，在这里整理一下复习时的笔记，准备一下计算机四级的考试。

选用教材：《数据库系统概论（第五版）》高等教育出版社
ISBN：9787040406641

作为课程，涉及到的数据库知识比较基础，这里做出概要、关键点笔记和一些理解。

2018.10.25 Update - 数据库四级翻车了。原因是把考纲中 数据库 + 操作系统原理 复习成了 数据库 + 软件工程，考试时候完全不知道是什么，凭着大一学的一点点操作系统知识……也没有糊过去。等明年 3 月份再参加吧。

2019.3.3 Update - 计算机四级，就和网上说的一样，非常的水。完全没有必要专门复习数据库，只需要背一背题库就可以通过，甚至在对数据库一知半解的情况下也都可以通过。毕竟计算机四级只有选择题，而且题库一般比较固定。

2019.08.23 Update - 计算机四级证书，事实证明，除了混一混学校的评奖加分，没有任何用处。所以我并不推荐专门准备这个，这些时间可以用来干更多有意义的事情。

绪论

数据库系统概述

数据库的四个基本概念：

  • 数据(data) - 描述事物的符号记录；
  • 数据库(database, DB) - 长期储存、有组织、可共享的大量数据集合；具有 较小冗余度、较高数据独立性、易扩展性、共享性 的特点；
  • 数据库管理系统(database management system, DBMS) - 计算机基础软件之一；提供 数据定义语言(DDL)、数据操纵语言(DML)、数据控制语言(DCL) ；
  • 数据库系统(database system, DBS) - 储存、管理、处理、维护数据的系统；

其中数据库系统包含以下部分：

  • 数据库(DB)
  • 数据库管理系统(DBMS)
  • 数据库应用程序(DBAP)
  • 数据库管理员(DBA)

在不引发混淆的情况下我们称数据库系统为数据库。

数据库发展阶段：人工管理阶段->文件系统阶段->数据库系统阶段。

数据模型

数据抽象阶段：现实->概念模型->逻辑模型->物理模型。

概念模型例：实体-联系模型（E-R模型）：

  • 实体属性：单值属性/多值属性，基属性/派生属性；
  • 联系类型：内部联系/相互联系，一元联系/二元联系/多元联系，普通联系/递归联系；

实体相关的概念对比：

  • 实体：客观存在并可以相互区别的事物；
  • 实体属性：实体具有的某一特征；
  • 实体型：实体 + 属性；
  • 实体集：同一类型实体的集合；

数据模型的构成：数据结构、数据操作、数据的完整性约束；

常见的数据模型：

  • 层次模型 - ex. 树
  • 网状模型 - ex. 图
  • 关系模型 - ex. 表

将概念应用于表中：

  • 关系 - 一个表称作一个关系

  • 元组 - 行

  • 属性 - 列

  • 码 - 请看后详解

  • 域 - 属性选区的范围

  • 分量 - 元组中的一个

数据库系统结构

数据库系统的三个模式：

  • 模式 - 逻辑模式
  • 外模式 - 子模式/用户模式
  • 内模式 - 存储模式

数据库系统的三级模式构成两种映像：

  • 外模式/模式映像 - 逻辑独立性
  • 模式/内模式映像 - 物理独立性

关系数据库

关系的种类：

  • 基本关系：实际表
  • 查询关系：结果表
  • 视图关系：虚拟表

关于码：

  • 候选码：可以唯一确定元组的一组属性就是一个候选码，但其真子集无法唯一确定元组 ，候选码中不止一组属性
  • 主码：候选码中任意一组
  • 超码：可以唯一确定元组的一组属性就是一个超码，超码中不止一组属性
  • 外码：属性中引用的其他实体的主码

候选码是最小超码，主码是候选码的其中一个

关系模式 R(U, D, dom, F)：

  • R：关系名
  • U：属性名集合
  • D：相应属性名集合的域
  • dom：属性和域的映射
  • F：属性间数据依赖集合

关系的完整性：

  • 实体完整性：主码不能缺省或非法
  • 参照完整性：外码不能非法
  • 用户定义的完整性：用户定义的数据要求

关系操作：

  • 集合运算符：交、并、补、差
  • 专门的关系运算符：选择、投影、连接、除
  • 算术比较符：大于、小于、等于、不等于 etc.
  • 逻辑运算符：与、或、非 etc.

关系操作下有相应的 关系代数 和 关系代数表达式 ，这部分不再写在这里了，不妨去看看书。

SQL 关系数据库标准语言

SQL 三级结构模式：文件(内模式) -> 表(模式) -> 视图(外模式)。

SQL 实现：数据定义，数据查询，数据更新，数据操作。

SQL 结构框架：

instance // 实例
{
	database // 数据库
	{
		schema // 模式
		{
			table // 表
			view // 视图
			index // 索引
		}
	}
}

SQL 数据定义

创建模式与删除模式

create schema schema_name

drop schema schema_name <cascade / restricte>

// e.g.
create schema test_schame authorization auth_name;
drop schema test_schame cascade;

关于 cascade & restricte :

标注 cascade 是级联操作，其操作（例如drop）会对子目录下项目同等操作；

标注 restricte 是限制操作，其操作（例如drop）当子目录下项目非空将报错；

创建表与删除表

create table table_name

drop table teble_name <cascade / restricte>

// e.g.
create table test_table
(
    sno char(10) unique, // 属性名 数据类型 完整性约束
    sname char(10) not null,
    stel char(10),
    dno char(10),

    primary key(sno), // 设置 sno 为主码
    foreign key(dno)
        references test_table2(sno), // 设置 dno 为外码，引用自 test_table2
);

drop table test_table cascade;

创建视图与删除视图

create view view_name

drop view view_name <cascade / restricte>

// e.g.
create view test_view as
select column_name // 涉及到 select 一会再说
from test_table
where condition;

drop view test_view;

创建索引与删除索引

create unique / cluster index index_name

drop index index_name <cascade / restricte>

// e.g.
create unique index test_index on
test_table(sno, sname);

drop index test_index;

SQL 数据查询

select 语法很多，具体内容介绍在众多教程网站上也有很多。这里的笔记就是针对比较常见的 student 表进行的各类操作实例，以此复习各类 select 语法。

// e.g.

// 从 student 表中选取 sno 与 sname
select sno, sname from student;

// 从 student 表中选取所有
select * from student;

// 从 student 表中选取 sage 并减 2015；选取 sname 并小写，输出时重命名为 NAME
select sage-2015, lower(sname) NAME from student;

// 从 student 表中选取 sno 的和，并计 sname 数
select sum(sno), count(sname) from student;

// 从 student 表中选取 sno 并去除重复数据
select distinct sno from student;

// 从 student 表中选取 dno 为 cs 的 sname
select sname from student where dno = 'cs';

// 从 student 表中选取 dno 为 cs 或者 ms 的 sname
select sname from studnet where dno in ('cs','ms');

// 从 student 表中选取 sname 倒数第二位为 l 的 sno
select sno from student where sname like '%l_';

// 从 student 表中选取 sname 最后一位为 _ 的 sno
select sno from student where
	sname like '%\_' escape \;

// 从 student 表中选取 sno = 6 的sname
select sname from student where
	(sno>10 or sno<5) and sno=6;

// 从 student 表中选取 cno 为 3 的 sname 并按照 grade, sno 排序
select sname from student where cno='3'
	order by grade desc/asc, sno desc/asc;

// student 表中不同 sname 数
select count(distinct sname) from studnet;

// 从 student 表中选取 sno 与对应的平均成绩
select sno, avg(grade) from student group by sno;

// 从 student 表中选取挂两科以上的学生
select sno from student where grade<60
	group by sno having count(*)>2;
	select student.*, sc.* from student, sc where
	student.sno = sc.sno;

// 同表连接
select first.sno, second.con from
	test first, test second where ~;

// 异表 join
select * from table1 left outer join table2 on...
	/right outer join on... /full outer join on...

// 从 student 表中选取大于平均成绩的 sno 与 cno
select sno, cno from sc x where grade >=
	(select ave(grade) from sc y where x.sno=y.sno)

// 从 student 表中选取 con 有 1 的 sname
select sname from student where exists
	(select * from sc where student.sno=sno and cno='1');

// 两层 not exists
select sname from student where not exists
	(select * from course where not exists
		(select * from sc where sno=student.sno
			and cno=course.cno
		) //course that student didnt choose
	);

// 两层 not exists
select distict sno from sc x where not exists
	(select * from sc y where sno=001 and not eixsts
		(select * form sc z where z.sno=x.sno
			and z.cno=y.cno
		) //course that they all chosed
	);

// 不同 select 的结合
select_1 union/union all select_2;
select_1 intersect select_2;
select_1 except select_2;

// 临时表
select sno, cno from sc,
	(select sno, avg(grade) from sc group by sno)
	as avg(avg_sno, avg_grade)
	where sc.sno=avg.avg_sno
	and sc.grade>avg.avg_grade;

SQL 数据更新

// e.g.

// 插入数据
insert into student(sno, sname) values(002, zerotwo);

// 从另一个表选中数据插入
insert into student(sno, sname) 
    select sno, sname from other_tabel;

// 更新数据
update student set sage=22 where sno=002;

// 选择性更新数据
update sc set grade=100 where 'ma'=
	(select dno from student where student.sno=sc.sno);

除此之外还有 delete 等各类操作，都是大同小异。

数据库编程

SQL 编程技术可以有效克服 SQL 语言实现复杂应用方面的不足，提高应用系统和数据库管理系统之间的互操作性。

SQL 编程来访问和管理数据库中数据的方式主要有：

  • 嵌入式 SQL (ESQL)
  • 过程化 SQL (PL/SQL)
  • 存储过程和自定义函数
  • 开放数据库互联 (ODBC) etc.

嵌入式 SQL ：

实例：（更为完善的例子在书上 page.247）

// e.g.

exec sql begin declare section; // 声明主变量
char sno;
char cno;
char sname;
exec sql end declare section;

exec sql include sqlca; // sql通信区
int main(){
	...
	exec sql connect to database_1; // 连接数据库
	exec sql declare v cursor for // 声明游标v，指向select的表
		select...
	exec sql open v;
	for(;;){
		exec sql fetch v into :sno, :cno, :sname; // 推进游标
		if(sqlca.sqlcode != 0) break;
		... // 可以各种操作，也可以内嵌sql语句
	}
	exec sql close v; // 关闭游标
	exec sql commit work; // 提交事务
	exec sql disconnect database_1; // 关闭数据库连接
	return 0;
}

由于学期课程中并没有涉及太多的数据库编程部分，这边就先空下来，后来有空了再补充。

数据库的完整性

三种数据完整性：

实体完整性：(primary key)

// e.g.
sno char(10) primary key; // 列级定义主码
primary key(sno, cno); // 表级定义主码

参照完整性：(foreign key)

// e.g.
foreign key(sno) references student(sno)
    on delete/update cascade;
foreign key(cno) references studnet(cno)
    on delete no action;

用户定义完整性：

// e.g.
sno char(10) not null; // 设置 sno 非空
cno char(10) nuique; // 设置 cno 非重复

check(sex in('mail', 'famail')); // 设置 sex ‘选项’
check(sex='famail' or sname not like'ms.%');

对数据库完整性的操作：

完整性约束

// e.g.
sno char(3) constrant c1 <...>; // 命名约束，把设置给 sno 的完整性约束命名为 c1
alter table student
    add constraint c1 <...>; // 修改约束

断言

// e.g.
create assertion [assertion_name] <sql...>;

触发器

// e.g.
create trigger [trigger_name] <sql...>;

关于检查约束、断言与触发器的区别：

  • 检查约束：检查是一个SQL，它确保在记录上执行操作之前满足条件；

  • 断言：断言是一条SQL，它确保条件满足或停止对数据库对象执行的操作；

  • 触发器：触发器是在数据库中更新，插入或删除之前或之后执行的一段SQL；

数据库安全性

常通过下面几种方式控制数据库安全性：

用户识别：即最常见的‘登陆’控制。

存取控制：自主存取控制(DAC)、强制存取控制(MAC)。

// e.g. DAC

grant select on table table_1 to user_1; // 授予权限
grant all priviliges on table student, course
    to user_2, user_3; // 授予全部权限
grant select on table table_1 to public; // 授予角色权限
grant update(sno) on table table_1 to user_1;
    with grant option; // 授予可再授权权限

revoke select on table table_1 from user_1
    cascade/restrict; // 收回可再授权权限需要cascade

// e.g. MAC
// 包含 主体：许可证级别；客体：密级，并满足：
* 仅当主体的许可证级别大于或等于客体的密级时，该主体才能读相应的客体；
* 仅当主体的许可证级别小于或等于客体的密级时，该主体才能写相应的客体；

视图：前面已大致介绍；

审计：用户级审计 & 系统级审计；

加密：常见；

关系数据理论

关系数据理论涉及了不少逻辑相关，学习的时候觉得很奇妙，尤其是其中的公理系统和以之推出来的最小依赖集求法；我的笔记中只记下了便于复习的提纲，所以较细致的部分还需要参考书上内容。

关系模式 R(U, D, DOM, F)

  • R：关系名
  • U：组成该关系的属性名集合
  • D：属性组U中属性所来自的域
  • DOM：属性向域的映象集合
  • F：属性间数据的依赖关系集合

依赖关系 （重要）

  • 函数依赖（FD）： 关系 x, y; 若 x1 != x2 能推出 y1 != y2，则称 y 函数依赖于 x。
    • 平凡依赖 / 非平凡依赖；
    • 完全函数依赖（F）/ 部分函数依赖（P）；
    • 传递函数依赖 / 直接依赖；
  • 多值依赖（MVD）： R(U)上关系r，给定的一对（x，z）值，有一组Y的值，这组值仅仅决定于x值而与z值无关，记x->->y;
    • 平凡依赖 / 非平凡依赖；

码（复习）

  • 候选码：可以唯一确定元组的一组属性就是一个候选码，但其真子集无法唯一确定元组 ，候选码中不止一组属性
  • 主码：候选码中任意一组
  • 超码：可以唯一确定元组的一组属性就是一个超码，超码中不止一组属性
  • 外码：属性中引用的其他实体的主码

候选码是最小超码，主码是候选码的其中一个

范式（重要）

  • 1NF：所有属性不可分解；
  • 2NF：非主属性完全函数依赖于主码
  • 3NF：非主属性既不部分依赖于码也不传递依赖于码（仅要求最外层是非主属性）；
  • BCNF：每一个决定属性因素都包含码：
    • 所有非主属性对每一个码都是完全函数依赖；
    • 所有的主属性对每一个不包含它的码，也是完全函数依赖；
    • 没有任何属性完全函数依赖于非码的任何一组属性；
  • 4NF：每个非平凡多值依赖 X→→Y（Y不属于X），X都含有码：
    • 不允许有非平凡且非函数依赖的多值依赖
    • 允许的非平凡多值依赖是函数依赖

范式推导：

  • 1NF -> 2NF：消除非主属性对码的部分函数依赖
  • 2NF -> 3NF：消除非主属性对码的传递函数依赖
  • 3NF -> BCNf：消除主属性对码的部分和传递函数依赖，此时已经实现了函数依赖范围内的彻底分解
  • BCDF -> 4NF：消除非平凡且非函数依赖的多值依赖

数据依赖的公理系统

  • 逻辑蕴含：对于满足一组函数依赖 F 的关系模式 R<U,F>，其任何一个关系 r 若函数依赖 X→Y 都成立,（即 r 中任意两元组 t, s,若 t =s ,则 t[Y]=s[Y]）,则称 F 逻辑蕴含 X→Y;
  • Armstrong公理系统：
    • 自反律： y in x in u => x->y in F
    • 增广律： x->y z in u => xz->yz
    • 传递律： x->y y->z => x->z
  • 推理规则
    • 合并规则： x->y x->z => x->yz
    • 伪传递规则： x->y wy->z => xw->z
    • 分解规则： x->y z in y => x->z
  • 函数的最小依赖集：
    • F 中任一函数依赖的右部仅含有一个属性
    • F 中不存在这样的函数依赖 X→A，使得 F 与 F-{X→A} 相等（即 F 中函数依赖不能由其中的其他函数依赖导出）
    • F 中不存在这样的函数依赖 X→A，X 中存在真子集 Z 使得 F-{X→A}∪{Z→A} 与 F 等价（即 F 中各函数左侧都是最小属性集中的）
  • 求候选码准则：
    • 准则1：如果属性 A 只在 F 中各个函数依赖的左端出现，则 A 必是码中的属性
    • 准则2：如果属性 A 只在 F 中各个函数依赖的右端出现，则 A 必不是码中的属性
    • 准则3：如果 A 不在F的各个函数依赖中出现，则 A 必不是码中的属性
  • 求候选码方法：
    • 根据准则3：把不在 F 中出现的各个函数依赖中出现的属性去掉，因为这些属性一般对模型没什么意义
    • 根据准则1：确定码中必须有的属性集（设为 M ）
    • 根据准则2：去掉码中肯定没有的属性
    • 确定余下的属性集（设为 W ）
    • 从属性 M 开始，令 K=M，如果 KF +=U，K 就是候选码。否则从W选择属性加入到 K 中，直到 KF +=U，K 就是候选码（注意可能有多个候选码）
// e.g. 求函数最小依赖集实例
F = { A → BC ， B → AC ， C → A }，求 Fmin

{
	[step.1]
	F= { A → B ， A → C ， B → A，B  → C，C → A }

	[step.2]
	G=F-{ A → B }
		AG += AC，不包含 B，所以 A → B 保留
	G=F-{ A → C }
		AG += ABC，包含 C，所以 A → C 删除，令 F=G ，
		F={A → B ， B → A，B  → C， C → A}
	G=F-{ B → A }，
		BG += BAC，包含A，所以 B → A 删除，令F=G，F={A → B，BC， C → A}
	G=F-{ B → C }，
		BG +=B，不包含 C，所以 B → C 保留
	G=F-{ C → A }，
		CG += C，不包含 A，所以 C → A 保留

	[step.3]
	F={ A → B ，B → C ，C → A }
}

数据库设计

  1. 需求分析阶段：了解分析用户需求 (数据 and 处理)；
  2. 概念结构设计：综合归纳用户需求形成概念模型，形成概念模式 (E-R)；
  3. 逻辑结构设计：概念模型转化为数据模型并优化，形成逻辑模式，进一步优化为外模式；
  4. 物理结构设计：选定储存结构和存取方法，形成内模式；
  5. 数据库实施：建立数据库、编制程序、数据入库、调试运行；
  6. 数据库运行与维护：及时评价、调整、修改；

数据库恢复

事务：是用户定义的一个 数据库操作序列 ，这些操作要么都做，要么都不做，是一个不可分割的工作单位，恢复和并发控制的基本单位；

事务的性质：

  • 原子性：要么全做要么不做；
  • 一致性：要么写入正确的结果，要么不写入；
  • 隔离性：详看并发控制（关于交叉进行）；
  • 持续性：commit之后修改是持久的；

故障：

  • 事务故障：逻辑故障、完整性约束下的中止事务；
  • 系统故障：停电、死机；
  • 介质故障：储存盘损坏；
  • 病毒：病毒攻击；

备份：

  • 动态备份 / 静态备份；
  • 海量备份 / 增量备份；

恢复策略：

  • 事务故障：反向扫描log，按步骤恢复至故障事务开始的标记；
  • 系统故障：
    • log中有记录 commit：redo，正向扫描；
    • log中无记录 commit：undo，操作同事务故障；
  • 介质故障：恢复数据库并常规使用 log 恢复；

检查点技术：checkpoints文件记录当时所有事务清单和最近的log的地址，redo文件记录检查点位置，可以提高故障恢复效率；

  • 记录：日志写入->检查点写入->数据写入->重新开始文件写入；
  • 恢复：重新开始文件找到最后检查点->事务清单上的事务进行审计->正向扫描log，无 commit：undo，有 commit：redo；

并发控制

面对的三种问题：丢失修改、不可重复读、读取脏数据；

事务执行：事务串行执行、交叉并发执行(单机)、同时并发执行(多机)；

技术：排他锁(X) read & write & 共享锁(S) read only；

封锁协议：

  • 一级封锁协议：修改前加上X锁，可以防止丢失修改，不能保证可重复读和脏数据；
  • 二级封锁协议：一级封锁基础上，读取前加上S锁（到读取结束），可以防止丢失修改和脏数据，不能保证可重复读；
  • 三级封锁协议：一级封锁基础上，读取前加上S锁（直到事务结束），可以防止三种问题；

活锁 & 死锁：

  • 活锁：一个事务持续等待，没有逻辑上锁死；
  • 死锁：逻辑上锁死；预防或诊断解除（超时法、事务等待图法）；

可串行化调度：多个事务的并发执行是正确的，当且仅当其结果与按某一次序串行地执行这些事务时的结果相同。可串行化调度当然也保持数据库的一致状态；

可串行性：是并发事务正确调度的准则。在RDBMS中，作为并发控制的正确性准则。一个给定的并发调度，当且仅当它是可串行化的，才认为是正确调度；

两段锁协议（可串行化的充分条件，但并不保证避免死锁）：

  • 第一阶段：获得封锁（扩展阶段）；
  • 第二阶段：释放封锁（收缩阶段）；

粒度：封锁对象的大小，区别为逻辑单元和物理单元；

多粒度封锁：同时支持多种封锁粒度；

多粒度封锁协议：

  • 允许对多粒度树中的每个节点独立加锁；
  • 节点加锁意味着所有后裔加锁；
  • 显示封锁 / 隐式封锁（因上一条引起）；

多粒度封锁效率低，因为它需要检查上下所有节点的加锁情况

意向锁（如果对一个结点加意向锁，则说明该结点的下层结点正在被加锁，对任一结点加基本锁，必须先对它的上层结点加意向锁）：

  • 意向共享锁（IS）：后裔拟加S锁；
  • 意向排他锁（IX）：后裔拟加X锁；
  • 共享意向排他锁（SIX）：S+IX的效果（意思是要读整个表并且可能更新一些数据）；

申请封锁自上而下，释放封锁自下而上。

关系查询处理和查询优化

查询分析：查询语句的语义分析；

查询检查：安全性检查 & 完整性检查；

查询优化：

  • 代数优化：关系代数表达式的优化；此处内容较多，详看书本 page.281
  • 物理优化：
    • 基于规则的启发式优化
      • 选择操作
        1. 小关系：全表扫描
        2. 主码相关：主码索引
        3. 非主属性：比例较小索引，较大全表
        4. 非等值或者范围：同上
        5. OR：一般全表
      • 连接操作
        1. 已按照连接属性排序：排序-合并方法
        2. 连接属性上有索引：索引连接法
        3. 其中一个表比较小：HASH join方法
    • 基于代价估算的优化
      • 代价估计：
        1. 全表B块，全表扫描cost=B
        2. 全表B块，选择条件码值对应，平均搜索cost=B/2
  • 基于代价估计的优化

结尾

对照书上看了一看，发现学的是真的粗糙，像数据库编程、数据库安全都很粗略地看了过去，学习过程中也没有实际做出什么东西来，这份笔记涉及的部分也差了很多，只是为了通过期末考试。

因为学期的课程讲到关系查询就结束了，所以之后的内容如管理系统、大数据部分，在课程和复习中只大致浏览过。

教程文档
发表评论