数据库原理

第一章 绪论

可以看到，选择题主要考了一下几个概念：

1. 基于文件系统的管理方法

   数据存储于文件中，由应用程序经过文件系统进行管理。

   缺点：

   1. 每当文件格式发生变化，就要修改应用程序

   2. 文件中存在冗余数据

   3. 文件修改中可能造成数据不一致

   4. 文件修改可能破坏数据正确性

   5. 没有索引，数据访问效率低

   6. 只能对整个文件进行访问控制，数据安全性差【这点确实说得很好】

   7. 没有并发控制，多个应用程序同时读写文件可能发生冲突

2. 数据库系统包括：数据库、数据库管理系统、数据库应用程序、数据库管理员、计算机与网络基本系统

   

3. 数据库管理系统：通过数据库语言让用户操作进而提供数据库定义、数据库操纵和数据库控制功能的系统，同时提供了一系列程序能够实现对数据库的各种存储与维护

4. 用户角度，数据库管理系统包括：数据库定义/操纵/控制/维护

5. 模式相关

   主要是“三级模式两层映像”结构。

   三级模式：

   1. 用户模式 = 外模式 = 局部模式 =？子模式
   2. 概念模式 = 逻辑模式 = 全局模式
   3. 物理模式 = 内模式 = 存储模式

   “模式”默认指概念模式。

   两层映像：

   1. 外模式到概念模式的映像实现了数据的逻辑独立性
   2. 概念模式到内模式的映像实现了数据的物理独立性

   数据库系统的数据独立性是指不会因为系统数据存储结构与数据逻辑结构的变化而影响应用程序。

   抽象程度：数据模型 > 模式 > 视图【关系模型 - 表结构 - 表数据】

6. 数据模型

   重点记各个模型的优缺点。。。

   1. 层次模型
      1. 优点
         1. 数据结构简单清晰
         2. 查询效率高，记录联系指针实现
         3. 性能>关系数据库，<=网状数据库
      2. 缺点
         1. 现实中很多联系是非层次性的
         2. 查询子女必须经过双亲，结构严密，层次命令趋于程序化（这个怎么你了）
   2. 网状模型
      1. 优点
         1. 直观
         2. 性能好，存取效率高
      2. 缺点
         1. 结构复杂
         2. DDL和数据管理语言复杂
         3. 应用程序编写困难，联系通过存取路径实现
   3. 对象-关系数据库
      1. 可有效支持不满足关系第一范式的数据项
      2. 以对象形式封装数据项
      3. 行对象与列对象；聚集对象与结构对象

7. 发展史

   第一代数据库系统是指基于网状模型或层次模型的数据库系统。

   第二代数据库系统是指基于关系模型的数据库系统。

第二章 关系代数

概念

关系

1. 表/关系，列/属性，行/元组

2. 列的取值范围成为域

   

3. 元组定义——域的笛卡尔积元素

   

4. 关系的定义

   

   

5. 关系模式相当于表结构，关系就是在表结构的基础上填数据

6. 关系的特性

   

   

   

7. 码

   

   

   

   

   超码：包含候选码的集合

   

关系模型

完整性约束

实体完整性

主码不能为空

参照完整性

外键属性值要么为空，要么为对方的主码值

用户自定义的完整性

关系代数

总述

关系代数结果是一个新的关系。

集合操作

集合运算（除了笛卡尔积）需满足并相容性。

并

记得去重

差

R-S：出现在R中但不在S中

交

笛卡尔积

关系操作

选择

选择的是元组

这还能非

注意且和或的优先级

投影

选择的是列，记得去重

连接

seta-连接

带条件的

与自身连接

用ρ更名

等值连接

还是得带条件，指明要哪两个属性相等

值得注意的是，最后B和H两列都会保留

自然连接

值得注意的是，会选取所有相同的属性组，把它们合成同一个属性列！

【也只有自然连接会做这个合并操作了，别的都是会保留两个列】

除法

常用于求解“查询全部的/所有的”问题。

R ÷ S = B，B × S的所有元组都在R中。

注意是要每一个元组

除法一般用于带有“全部”“所有”类似字样的题目中

TODO：抓人对个答案

外连接

emmm就是不知道什么时候需要用外连接呢？题目会显式说明吗

第三章 SQL语言

概述

SQL语言

DDL

创建

1. create database canteen;

2. create table

   create table dish(
      dish_id              int not null,
      dish_intro           varchar(128),
      dish_price           numeric(4,1) not null,
      primary key (dish_id)
   );

   

   这个类型估计得背

   

撤销与修改

1. drop table student;

2. alter

   alter table cmt add constraint FK_CMT_ORDER_COM_ORDERS foreign key (order_id)
         references orders (order_id) on delete restrict on update restrict;
         
   alter table cmt 
         drop foreign key FK_CMT_ORDER_COM_ORDERS;

   

DML

查找

基操

1. 基操

   注意逻辑运算符、运算优先级

   select Tname
   from Teacher
   where (Salary < 1500 or Salary > 2000) and D# = '03';

2. distinct

   关系模型的投影和选择结果自动去重，但是DBMS允许重复元组，所以结果不会自动去重。

   关系的无重复元组通过主键和唯一性约束保证，检索结果的无重复元组通过DISTINCT保留字保证。

   select DISTINCT S#
   from SC
   where Score > 80;

3. order by

   通过order by对检索结果降序/升序排序。

   select S#, Sname
   from Student
   Order by S# ASC/DESC;

4. like

   后接类正则表达式

   

   -- 所有姓张学生
   select S#, Sname 
   from Student
   where Sname like "张%"
   
   -- 所有不姓张学生
   select S#, Sname 
   from Student
   where Sname not like "张%"

5. 多表查询

   通过在WHERE中写连接条件来实现。

   

   select Sname
   from Student (as) stu, SC, Course
   where stu.S# = SC.S# and SC.C# = Course.C# and Cname = '数据库'
   order by Score DESC;

子查询

1. IN

   select * from student
   where Sname in ("张三", "王三");

2. 相关子查询

   

   

   select Sname from Student S
   where `S#` in (
   	select `S#` from SC
       where S.S# = SC.S# and `C#` = '001'
   	);

可以这么理解，非相关子查询相当于复杂度On，先计算出子查询的结果，然后再遍历父查询元组看看是否符合条件；相关子查询相当于复杂度On方，需要把父循环变量i代进子循环j中。

3. SOME/ALL谓词

   

   

   select Tname from Teacher
   where Salary <= all (
   	select Salary from Teacher
   	);

   

   

   这个确实得注意，一看就很坑爹

4. exists

   

   意思就是看看子查询结果中有没有元组，有则成立，无则不成立。

   select DISTINCT Sname from Student
   where exists (
   	select * 
       from SC, Course, Teacher
       where SC.C# = Course.C# and Course.T# = Teacher.T#
       	and SC.S# = Student.S#	# 这个值得注意！
       	and Teacher.Tname = "李明"
   );

   关系代数的除法模型可以用exists来实现。做出来一题，之后的就可以类比了。

   

结果计算与聚集函数

select T1.Tname as TR1, T2.Tname as TR2, T1.Salary - T2.Salary as Salary_Diff
from Teacher T1, Teacher T2
where T1.Salary > T2.Salary;

分组查询

group by

# 求每一门课程的平均成绩
select Course.Cname, AVG(Score) as avg_score
from SC, Course
where SC.C# = Course.C#
group by `C#`;

# 求每一个学生的平均成绩
select `S#`, AVG(Score) as avg_score
from SC
group by `S#`;

使用了group by之后，聚合函数的对象就会自动变成分组，而非整个表了。

having

可以看到，我们可以对一个group by分组内通过having来使用聚合函数。

select `S#`, AVG(Score) from SC
where `S#` in ( # 找出两门以上不及格课程的同学
	select `S#` from SC
    where Score < 60
    group by `S#` having Count(*) > 2
)
group by `S#`; # 才对它求average

并交差

空值处理

内连接与外连接

select *
from Teacher left outer join Course natural
order by `T#` ASC;

更新

这几个都是：

1. where省略更新所有

2. 不符合用户定义的完整性约束就不执行

   

insert

insert into Student
values ('1111', '哈哈', '男', 20, '03', '919324')

insert into St
	select `S#`, Sname, AVG(Score)
	from SC, Student
	where SC.S# = Student.S#
	group by Student.`S#`

delete

delete from SC where `S#` = '34556578';

delete from Student where `D#` in
	(select `D#` from Dept where Dname = "自动控制");

update

update Teacher set Salary = Salary * 1.05;

update Teacher
set Salary = Salary * 1.1
where `D#` in
	(select `D#` from Dept where Dname = '计算机');

drop

alter

视图

基本表和视图的概念可以了解一下

定义

create view CompStud as( 	
    select * from Student
    where `D#` in (select `D#` from dept where Dname = '计算机')
);

create view Teach as(
	select T.Tname, C,Cname, Credit
    from Teacher T, Course C
    where T.T# = C.C#
);

create view StudStat(`S#`, Sname, AvgS, MinS, MaxS, CNT) as (
	select `S#`, Sname, AVG(Score), MIN(Score), MAX(Score), Count(*)
    from Student S, SC where S.S# = SC.S#
    group by S.S#
);

更新

删除

第四章 数据库的安全性和完整性

完整性

概述

本课程中的完整性指的是语义完整性。

用户定义完整性约束规则保障完整性

完整性约束

按约束对象分类

1. 域完整性约束

   

2. 关系完整性约束

   

按约束来源分类

1. 结构约束

   

2. 内容约束

   

按约束状态分类

1. 静态约束

   

2. 动态约束

   

sql中的约束

触发器是动态约束这个说法真新奇

静态约束

列约束

create table Student(`S#` char(8) not null unique, Sname char(10),
			Ssex char(2) constraint ctssex check(Ssex = '男' or Ssex = '女'),
            Sage integer check(Sage >= 1 and Sage<150),
            `D#` char(2) references Dept(`D#`) on delete cascade,
            Sclass char(6)
);

表约束

可以看到，它是在表定义中处于跟属性定义同级的低位。

撤销/追加

动态约束（触发器）

定义

具体的触发器代码写在when里的statement处

事件

安全性

自主安全性

概述

方法

存储矩阵

视图

第二点值得注意，可能意思就是用户A只能读P#为它自己ID的存储，可见存储矩阵。

sql

授权

收权

强制安全性

反正意思就是说：

1. 行列权限冲突，就算是高权限
2. 可以读权限小于等于它的，写权限大于等于它的

emmm，也就是说数据的机密性不能降级，只能升级？

存储过程

为啥这东西归在这里。。。

66666666666666，这两个例子值得注意

第五章 数据库设计和ER模型

TODO，这章还没怎么看

数据库设计

ER模型

E-R模型：Entity-Relationship Model

草，原来ER是这个意思

实体-联系模型

实例

属性

码

蛤，不都是主码主键吗。。。。。。

联系

一元联系

我不造啊

二元联系

约束

基数

参与基数

ER图

Chen画法

尼玛，这个总不至于要背吧呃呃，应该大概看懂了差不多得了

还是这个比较阳间

还要尤其注意这张图，还他妈的不一样。。。

它那边还有个案例分析，我懒得看了，反正也是忘了。。。

Crow’s Foot

尼玛，这个阳间多了，上面那个是不是因为是中国人才介绍的，乌鱼子

1就是竖线，0就是圈圈，多就是开叉

也挺好理解，那边有个圈圈代表0

ER图->关系模式

属性的转换

oh！原来是这样，确实这样减少了冗余

联系的转换

确实也避免了大量空值，不过如果双方均部分参与，新关系是不是还得再多一列什么序号作为关键字？还是一个为空直接啥了，不大懂啊

弱实体

也就是说弱实体虽然有键，但是不够作为主键？什么鬼

这个箭头可以看出，弱实体完全参与联系，且为1:m关系。

具化/泛化

这个的意思就是person是对customer和employee的泛化，customer和employee是对person的具化。

实体联系设计问题

问题

冗余

删除异常

设计准则

物理数据库

第六章 数据库规范

函数依赖

定义

函数依赖

定义

特性

部分/完全/传递依赖

部分/完全

传递

候选码

注意必须得是完全依赖，也就是说要满足极小性。

公理系统

定义

逻辑蕴含

公理、定理

注意看我加的黑字批注。

闭包

从而由此可以定义某个属性/属性组的闭包：

也即存放的是通过这个什么定理，从X开始可以导出的所有属性。

TODO，这个没懂

好像意思就是，如果F的闭包等于自身，那么它就是一个全函数依赖族。可以联想一下什么情况会闭包等于自身呢？感觉差不多就是消除了所有的传递依赖之类的。

函数依赖集

如果两个函数依赖的函数依赖完备集等价，则两个函数依赖等价。

覆盖

这个最小函数依赖注意一下，反正意思就是右边就一个，然后木有冗余依赖和冗余属性。

范式

1NF

2NF

3NF

消除了非主属性对主属性的传递依赖。

也就是说，最后的情况就是非主属性完全且非传递依赖于主属性

BCNF

模式分解

沙比，说得那么曲折，反正意思就是，ρ是一个模式分解，然后如果对ρ里面每个属性进行投影，最后把这些结果连接起来，最后的东西就叫做这个mr，也即投影连接。【就是这个连接不知道是笛卡尔积还是什么玩意】

无损连接分解

判断方法

无损分解BCNF

保持依赖分解

反正意思就是，F中的左部右部都在Ri这个属性的，这些式子能推导出F中其他式子，那么就叫保持依赖。

判断方法

保持依赖分解3NF

又无损又保持依赖

第七章 数据库物理存储

基础概念

存储体系

磁盘结构

容量

圆盘-盘面-磁道-扇区

这个例子值得注意，不论一个文件多小，它都是占一个磁盘块。

一般情况下，一个磁盘块包含多个扇区。

读写时间

RAID

数据库实现

存储查询实现

真感觉有必要写一下cmu15445

与磁盘映射

文件组织方法

无序

有序

你也要GC是吧

散列

聚簇文件

第八章 数据库索引

概述

定义

SQL

分类

总之总结一下，其实大概就是稀疏索引和稠密索引。

然后：

1. 根据主属性排序的主文件+稀疏索引 = 主索引

2. 根据某个属性排序的主文件+稀疏/稠密索引 = 聚簇索引【可以注意下跟主索引的差别】

   

3. 根据非主属性排序的主文件+稠密索引 = 辅助索引

4. 对某个非排序属性进行稠密索引 = 非聚簇索引

稀疏与稠密

还得是折中，加层

主/辅助索引

这个就是我们dblab5干的

注意，它确实就引入了个链表，关注Downtown字段。

不用排序是因为相当于加了一层哈希了。

TODO，说实话那句话真没看懂

聚簇/非聚簇

上面那个是稀疏索引，相当于不是根据主码而是根据别的属性了

与主索引差别：

倒排索引

这个算不算content-based hhh

其他

B+树

TODO

存储约定

建立不同索引

主键稠密

主键稀疏

非键稠密

排序

不排序

B树

插入删除

这些就结合下cmu的跟ppt的算法复习一下吧，考前再说。

散列

是什么

散列索引

动态散列索引

可扩展散列索引

注意，其它不变，每次只需重新散列涉及到的那个桶。此时00和01两个桶还是指向的0010这个快。

这时候i无需增加

线性散列索引

它这个意思应该是mask有log2n位，也即hash函数为k & (2^log2n - 1)

也即把最高位改为0.

第九章 数据库查询算法实现

连接的实现

注意，主存每页容量等于一个磁盘块容量，此处做了简化感觉。

迭代器

用于一元操作

一趟扫描算法

一趟扫描

没看懂

基于索引

两趟扫描

内外排序

两阶段多路归并排序TPMMS

干净一点的图：

可以画个树理解一下

第十章 数据库查询优化技术

概念

优化思路

语义优化

也就是SQL语句层面的优化

语法优化

也就是关系运算层面的优化

6

语法优化（逻辑层优化）

示例背景

语法树

这个就相当于把XLOANS这个视图定义展开为语法树了

优化策略

人话：

1. 早做投影和选择
2. 选择投影尽量挨在一起
3. 没懂。。。
4. 选择+笛卡尔积换成条件连接
5. 预处理，如建立索引
6. 找公共子表达式（如语法图）

我服了，体会一下吧。

关系代数操作次序交换的等价性

定义

定理

意思就是这个l3可以用来：

1. 两遍扫描->一遍扫描
2. 拓展语法树，便于用之后其它定理化简

这个也体现了，反向使用定理L3，然后再用L7这个组合技达到的优化效果

注意，投影和差是没有交换律的。

虽然都确实直观吧，但我感觉我服了。。。

算法

TODO

这个具体看PPT吧，还有它后面的例子，或者听下网课，感觉快死了。

物理查询优化

定义

TODO，为啥非聚簇，用索引就得每个元组扫一遍？？？不是取决于索引表大小吗，我真服了

算法思路

性能评估

评估方案

数据获取

代价估算

投影

选择

好吧，m和n也是这么估算的：

最后那个简单估计，是意思是复杂度主要由第二个条件决定吗？想想确实很直观。

连接

简要结论

第十一章 数据库事务处理技术

反正大概意思就是：

本章就是围绕这两个问题来的。

不一致现象

事务

定义

性质

宏观性

微观性

特性：ACID

调度与可串行性

概念

图中最右错误，是因为这样的话B=B-20这个操作事实上就会被覆盖了。这两个事务不关心读的是不是B origin，只需要+10和-20操作都做了就行。

事务模型

冲突与可串行性

强烈推荐：冲突可串行化、事务优先图。PPT讲的不知道啥玩意

也就是说，如果一个schedule经过一系列对任意两个不冲突操作的调换动作后，可以变成一个完全串行的schedule，那么我们就称其为冲突可串行化。

如果一个 schedule 和某个串行 schedule 冲突等价，则称该 schedule 是冲突可串行化（conflict serializable）的。

真不懂

冲突可串行判别算法

一种就是上面那个图片例子，一直交换直到得到串行调度；

另一种就是下面要介绍的这个画图了。

说实话真没懂这啥玩意冲突可串行

也没搞懂这灰线又tm哪来的。。。

基于封锁的并发控制

概述

不满足

考虑因素

锁的类型

封锁协议

相容性矩阵

加解锁时机

封锁粒度

两段封锁协议

两段封锁协议是一种基于锁的并发控制方法。

满足

注意这个两端锁与前面那个只用锁的差距。两段锁把B加锁也移到前面了，所以可以保证冲突可串行性。

读nm，不读再见

可以看到，图中确实是满足两段锁协议要求的，加锁段里确实没有解锁段。消除死锁的方式应该就是按照一定顺序获取锁。

基于时间戳的并发控制方法

概述

简单的调度规则

规则

示例

真没看懂为什么要撤回T2和T3

冲突是否可串行

另一种调度规则

解决问题

也就是说U没有提交，所以T要更新的反而也丢了，变得更加过时（）

规则

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

第十二章 数据库事务恢复技术

故障类型与影响

恢复基本思路

事务故障

系统故障

介质故障

冗余阵列

日志

是什么

此时应该上层已经确保了事务的调度是冲突可串行化的，所以这里不用考虑会不会脏读问题。

Undo型日志

记录规则

这对应的应该是Steal

恢复步骤

检查点

Redo型日志

记录规则

这对应的应该是No Steal

恢复步骤

检查点

结合型日志

记录规则

恢复步骤

感觉得先undo再redo？