数据库复习总结

（未完）

1 引言

数据字典是指对数据的数据项、数据结构、数据流、数据存储、处理逻辑等进行定义和描述，其目的是对数据流程图中的各个元素做出详细的说明，使用数据字典为简单的建模项目。简而言之，数据字典是描述数据的信息集合，是对系统中使用的所有数据元素的定义的集合

DBMS：数据库管理系统，有一个互相关联的数据的集合和一组用以访问这些数据的程序组成。这个数据集合通常称作数据库。

SQL：结构化查询语言，structured query language

DML：数据操纵语言

DDL：数据定义语言

物理数据独立性：应用程序如果不依赖于物理模式，它们就被称为是具有物理数据独立性，因此即使物理模式改变了它们也无需重写

2 关系模型介绍

关系数据库的结构

关系数据库由表的集合构成，每个表有唯一的名字

关系用来指代表，元组用来指代行，属性指代表中的列

关系实例：包含的一组特定的行

属性的域：对于关系的每个属性，都存在一个允许取值的集合

我们要求对所有关系r而言，r的所有属性的域都是原子的

数据库模式

数据库模式：数据库的逻辑设计

数据库实例：给定时刻数据库中数据的一个快照

关系模式：对应于程序设计中的“类型定义”，由属性序列及各属性对应域组成

码

超码是一个或多个属性的集合，这些属性的组合可以使我们在一个关系中唯一地标识一个元组

如果K是一个超码，那么K的任意超集也是超码

候选码：是超码，它的任意真子集都不能成为超码，它就是最小超码

主码：被数据库设计者选中的、主要用来在一个关系中区分不同元组的候选码

外码：一个关系模式r1在它的属性中包括另一个关系模式r2的主码，那么这个属性在r1上称作参照r2的外码。关系r1也称为外码依赖的参照关系，r2叫做外码的被参照关系。

3 初级SQL

数据定义

基本类型

char, varchar, int, numeric, real, double, float,

基本模式定义

创建department关系模式

create table department
	(dept_name varchar(20) not null,
	building varchar(15),
	budget numeric(12,2), //定点数，12位数字，2位在小数点右边
	primary key (dept_name)); //完整性约束

完整性约束

primary key(a,b,c):属性a,b,c构成关系的主码

Foreign key(a,b,c) references s:关系中任意元组在属性(a,b,c)上的取值必须对应于关系s中某元组在主码属性上的取值

Not null：表明在该属性上不允许空值

SQL禁止破坏完整性约束的任何数据库更新

数据库的修改

//插入
insert into instructor
    values(10211,'Smith','Biology',66000);
insert into instructor
    select ID, name, dept_name, 18000
    from student
    where dept_name = 'Music' and tot_cred>144;
    //在查询结果的基础上插入元组
//删除
delete from student ;
drop table r; //整个关系模式都删掉
delete from r; //删掉关系中的所有元组
delete from r where P; //删除满足条件P的r中的元组
//在已有关系中中增加或去掉属性,新属性上的取值为null
alter table r add A D;
alter table r drop A;
//更新
update instructor
set salary = salary*1.05
where salary < (select avg(salary) from instructor);

只能删除整个元组，而不能只删除某些属性上的值
delete命令只能作用于一个关系
在执行插入前线执行完select语句是非常重要的，例如在student上没有主码约束的话，下面的请求会插入无数元组
```
insert into student 
	selcet * from student
```

case结构

case
	when pred1, then result1
	when pred2, then result2
	…
	else result0
end

update instructor
set salary = case 
			when salary <= 10000 then salary*1.05
			when salary
			else salary*1.03
			end

SQL查询

select xx,xx from table1,table2 where predicate

select * 表示选择所有属性

单关系查询

select distinct dept_name from instructor;
//distinct强行删除重复
select all dept_name from instructor;
//all指明不去重
select ID, salary*1.1 from instructor;
//可以使用+-*/运算表达式
select name from instructor where dept_name='Comp.Sci' and salary > 70000;
//where子句中允许使用and or not，也可以有>< <= >= <>等

多关系查询

select name, instructor.dept_name, building from instructor, department where instructoe.dept_name=department.dept_name

出现在多个表格中的属性名，如这里的dept_name，关系名用作前缀来区分

自然连接 natural join

自然连接运算作用于两个关系，并产生一个关系作为结果，它只考虑那些在两个关系模式中都出现的属性上取值相同的元组对

select name, course_id from instructor natural join teaches

join…using

指定需要取值相同的列，进行连接

select name, title from (instructor natural join teaches) join course using (course_id)

附加的基本运算

更名运算 as

select T.name, S.course_id
from instructor as T, teaches as S
where T.ID = S.ID;

字符串运算

字符串相等运算大小写敏感

通配符

百分号%：匹配任意子串
下划线_：匹配任意一个字符

使用like：匹配模式，反斜杠\转义

like '%Comp%' //匹配任何包含Comp子串的字符串
like '___' //匹配只包含三个字符的字符串
like 'ab\%cd%' //匹配以ab%cd开头的字符串

select dept_name from department where building like '%Watsons%'

排序元组的显示次序 order by

asc表示升序（默认），desc表示降序

select * from instructor order by salary desc, name asc

where子句谓词

between, not between

select name
from instructor 
where salary between 9000 and 10000

(a,b,c,…)表示n维元组

select name, course_id
from instructor, teaches
where (instructor.ID, dept_name) = (teaches.ID,'Biology');

集合运算

union，intersect, except对应集合论中$\bigcup, \bigcap, -$的操作

使用这三个操作默认去重，保留重复要使用all

空值 Null values

用is null判断空值

涉及空值的任何比较运算的结果视为unknown

unknown or true = true

unknown and flase = flase

unknown and/or 的其它情况和not unknown均为unknown

聚集函数

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

注意sum和avg的输入必须是数字集，其它的可以不是

基本聚集

select avg(salary) as avg_salary from instructor where dept_name = 'Comp.Sci'

默认有all，保留重复元素（如计算平均值时很重要）

若要去掉重复元素，使用distinct

select count(distinct ID)
from teaches
where semester = 'Spring' and year = 2010;

SQL不允许在用count(*)的时候使用distinct

select count(*)
from course;

group by分组聚集

**Select 后面跟的选择属性集合需要是group by后面跟的属性集合的子集，否则属性需要出现在聚集函数内部**

select dept_name,avg(salary) as avg_salary
from instructor
group by dept_name; //找出每个系的平均工资

Having子句

分组限定条件，having子句中的谓词在形成分组之后才起作用，针对group by子句构成的分组

select dept_name, avg(salary) as avg_salary
from instructor
group by dept_name
having avg(salary) > 42000;

与select子句情况类似，任何出现在having子句中，但**没有被聚集的属性必须出现在group by子句中**，否则查询就是错误的

对空值和布尔值的聚集

除了count(*)以外，聚合函数忽略输入集合中的空值

由于空值被忽略，有可能造册灰姑娘参加函数运算的输入值集合为空集。规定空集的count运算值为0，其他聚合运算在输入为空集的情况下返回一个空值

布尔值有两个聚合函数：Some,every——可以用来处理布尔值的集合

嵌套子查询

select-from-where表达式嵌套在另一个查询的where子句中

集合成员资格 in/not in

in/not in 测试元组是否集合中的成员

select distinct course_id 
from section 
where semester='Fall' and year = 2009 and course_id in 
	(select course_id 
     from section 
     where semester = 'Spring' and year = 2010)

集合的比较

comparison	>	<	>=	<=	<>
some	略
all

in等价于 =some

not in等价于 <>all

select name 
from instructor
where salary > some (select salary
                     from instructor
                     where dept_name = 'Biology');

空关系测试 exist/not exist

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

Exist r 等价于r不为空值

Not exist r 等价于r为空值

//找到所有参加了生物系的所有课程的学生
select distinct S.ID, S.name
from student as S
where not exists 
	((select course_id 
	 from course
	 where dept_name = 'Biology')
	 except
	 (select T.course_id 
	 from takes as T
	 where S.ID = T.ID));

注意$X \subseteq Y \iff X-Y=\varnothing$

来自外层查询的一个相关名称（S）可以用在where子句的子查询中。使用了来自外层查询相关名称的子查询被称作相关子查询

重复元组存在性测试 unique

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

//找出所有在2009年最多开设一次的课程
select T.course_id
from courses as T
where unique(select R.course_id
             from section as R 
             where T.course_id = R.course_id and
                R.year = 2009);

from子句中的子查询

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

select dept_name, avg_salary
from (select dept_name, avg(salary) as avg_salary
        from instructor
        group by dept_name)
        as dept_avg(dept_name,avg_salary)
where avg_salary > 42000;

子查询的结果关系被命名为dept_avg，属性名是dept_name 和 avg_salary

with子句

提供定义临时关系的方法，这个定义只对包含with子句的查询有效

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

标量子查询

子查询只返回包含单个属性的单个元组

sql允许标量子查询出现在返回单个值的表达能够出现的任何地方

//查询每个系的导师数量
select dept_name,
    (select count(*)
     from instructor
     where department.dept_name = instructor.dept_name)
     as num_instructors
from department;

4 中级SQL

连接表达式

连接条件 on

与自然连接的区别：自然连接相同的字段出现一次，而这里出现两次；若想只显示一次，则需要select指定字段

on条件可以表示任何SQL谓词，可以表示比自然连接更丰富的连接条件

select * from student join takes on student.ID = takes.ID

外连接

外连接在结果中创建包含空值元组的方式，保留了在连接中丢失的元组

左外连接left outer join，只保留出现在左外连接运算之前（左边）的关系的元组

右外连接right outer join，只保留出现在右外连接运算之前（右边）的关系的元组

全外连接full outer join，保留出现在两个关系中的元组

前面不保留未匹配元组的连接运算被称作内连接运算

//找出一门课也没有选的学生
select ID from student natural left outer join takes
where course_id is null

在左外连接中，左侧关系中不匹配右侧关系任何元组的元组被添上空值并加到结果中。上面的左外连接使得结果中没有选课的学生的元组也得以保留，相对应的属于takes字段的部分为null。

on子句可以和外连接一起使用。on和where在外连接中的表现是不同的。on条件是外连接声明的一部分，但where子句却不是。

外连接，三种，都要掌握，左外右外全外

视图的概念，如何create视图，基本sql语句

视图的更新要注意什么（什么时候可以更新，什么不能）

授权，authorization，sql语句要会写

权限的传递（如何进行传递）

6 形式化关系查询语言

注意关系代数的基本操作，要会写

基本的关系代数式子

能写出基本的查询

外连接的关系代数写法

看一下元组关系演算（很基本的查询会写就可）

7 数据库设计和E-R模型

ER图，数据库的设计阶段，design process（名词都是要记住的）

什么是弱实体集，和强实体集有什么区别

ER图画法规范，用教材上的规范

根据实际的需求画出ER图

知道一些规则，怎么转化成实际的关系模式

关系模式还原成ER图

联系转化成关系，如何转化，主码如何进行选择（多方）

8 关系数据库设计

理论性比较强

主要就是分解，为什么要进行分解

进行分解的时候哪些依据可以使用？

函数依赖（概念

使用函数依赖进行基本推导Armstrong公理

平凡依赖

BC范式的概念（基本要求

属性的闭包，怎么求，概念是

怎么证明超码，候选码

正则覆盖

多值依赖：了解概念就可

四种范式，注意冗余度，高低

11 索引和散列

索引

唯一索引的概念

如何使用sql进行定义

主索引，辅助索引，以及应用的场合

B+ 树的构造

基本的搜索代价（公式）

12 查询处理

选择操作的代价分析（多种情况

sorting的归并排序（只要求掌握二路的）

二路做一个外部的归并排序

连接操作，嵌套循环nested loop和block nested loop

掌握基本的操作

对它们的代价进行分析

13 查询优化

掌握等价转化的基本规则

掌握选择操作有关的

14 事务

事务是访问并可能更新各种数据项的一个程序执行单元，用形如begin transaction和end transaction语句来界定。

事务的ACID特性

原子性：事务的所有操作在数据库中要么全部正确反应出来，要么完全不反应。
- 保证原子性的思路：对于事务要执行写操作的数据项，数据库系统在磁盘上记录其旧值。记录在日志文件中。
一致性：隔离执行事务时，保持数据库的一致性。
- 例如：A向B转账，一致性要求事务执行前后不改变A+B的和
隔离性：尽管多个事务可能并发执行，每个事务都感觉不到系统中有其他事务在执行。
- 事务的隔离性确保事务并发执行后的系统状态与这些事务以某种次序一个接一个地执行后的状态是等价的。确保隔离性是数据库系统中并发控制系统的责任
持久性：一个事务成功完成后，它对数据库的改变必须是永久的，即使出现系统故障。（确保以下两条中的任何一条来达到持久性）
- 事务做的更新在事务结束前已经写入磁盘
- 有关事务已执行的更新信息已写到磁盘上，并且此类信息必须充分，能让数据库在系统出现故障后重新启动时重新构造更新

存储结构

易失性存储器：信息通常在系统崩溃后不会幸存
非易失性存储器：信息会在系统崩溃后幸存
稳定性存储器：信息永远不会丢失（丢失的可能性微乎其微）

事务修改写入稳定性存储器（持久性），日志记录写入稳定性存储器（原子性）

事务原子性和持久性

中止事务造成的变更被撤销，称事务已回滚，典型方法：维护日志。

撤销已提交事务方法：执行一个补偿事务。

进入中止状态后，系统有两种选择：

重启事务：仅当引起事务中止的是硬件错误而不是事务内部逻辑的软件错误。
杀死事务：通常是事务内部逻辑造成的错误

事务隔离性

提高吞吐量和资源利用率：I/O活动可以和CPU处理并行执行
减少等待时间：不同时长事务共享CPU周期和磁盘存取。减少执行事务时不可预测的延迟。

不是所有的并发执行都能得到正确的结果。

并发调度的原则：要和某一个串行调度等价。这样可以保证数据库的一致性

可串行化

如果某调度和某一个串行调度等价，那么称其串行等价的。

冲突可串行化
视图可串行化

指令冲突

对同一个数据，至少有一个是write指令的时候，这两条指令是冲突的

I=read(Q), J=read(Q)，顺序无关紧要。非冲突
I=read(Q), J=write(Q)，次序重要。冲突
I=write(Q), J=read(Q)，次序重要。冲突
I=write(Q), J=write(Q)，次序重要，影响后面读Q的指令。冲突

如果调度S可以经过一系列非冲突指令交换成S‘，称S和S’冲突等价。（注意是交换两个事务不冲突的指令，单个事务的内部读写顺序仍然相同）

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

优先图

有向边Ti->Tj表示在Ti和Tj至少有一个是写，且Ti在Tj之前执行。

如果优先图有环，则是非冲突可串行化的。

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

视图可串行化

如果一个调度S的视图等价于一个串行调度的视图，那么称它为视图可串行化的。

事务隔离和原子性

可恢复调度

可恢复调度应满足：对每对事务Ti和Tj，若Tj读取了之前由Ti所写的数据项，则Ti先于Tj提交

无级联调度

无级联调度应满足：对于每对事务Ti和Tj，如果Tj读取了先前由Ti所写的数据项，则Ti必须在Tj这一读操作前提交。

每一个无级联调度都是可恢复调度。

缺点：并发性差。

事务隔离性级别

可串行化serializable：通常保证可串行化调度。
可重复读repeatable read：只允许读取已提交数据，而且在一个事务两次读取一个数据项期间，其他事务不得更新该数据。但该事务不要求与其他事务可串行化。
已提交读read commited：只允许读取已提交数据，但不要求可重复读。比如，在事务两次读取一个数据项期间，另一个事务更新了该数据并提交
未提交读read uncommited：允许读取未提交数据。这是SQL允许的最低一致性级别

以上所有隔离性级别都不允许脏写，即如果一个数据项已经被另外一个尚未提交或终止的事务写入，则不允许对该数据项执行写操作

15 并发控制

基本的锁，兼容矩阵（两种锁）

死锁的概念，

死锁的检测方法

16 恢复系统

日志记录

恢复算法

redo，undo