数据库系统概论复习笔记

前言

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

由于 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
  • 基于代价估计的优化

结尾

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

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

如果未来有用到数据库的内容,那么再复习并更新这篇文章。