数据库理论笔记

\(\mathcal{Author:gpf}\)

数据库概述

信息：现实世界事物的存在方式或运动状态的反映。具体地说，是一种已经被加工为特定形式的数据

数据：将现实世界中的各种信息记录下的、可以识别的符号，是信息的载体和具体表现形式

• 数据是信息的符号表示、载体
• 信息是数据的内涵、语义解释
• 数据是符号化的信息，信息是语义化的数据

数据处理：利用计算机进行数据处理的过程，包括数据的采集、整理、编码、输入。由计算机进行加工、传输、计算、检索、输出等操作。目的是计算、推导出有价值的信息作为行动依据

数据库：长期存储在计算机内的、有组织的、可共享的数据集合

数据库管理系统：通用的软件系统，由一组计算机程序构成。对数据库进行有效的管理并提供软件环境，方便用户使用数据库中的信息

数据库系统：一个计算机存储记录的系统。目标是存储信息并支持用户检索和更新所需要的信息。通常由数据库、硬件、软件、用户组成

发展历史

人工管理阶段

50年代中期以前

• 数据不在计算机上保存
• 数据与程序不具有独立性
• 基本没有文件概念
• 一组数据对应一个程序，程序间不共享数据

文件系统阶段

50年代后期-60年代中期

• 数据以文件形式保留在外存上
• 文件多样化
• 由文件系统管理数据，数据的存取基本上以记录为单位
• 程序和数据有一定的独立性，但仍然缺乏独立性
• 数据冗余度大
• 由一定共享性

问题：

• 数据冗余、不一致
• 访问困难
• 数据孤立
• 数据独立性差
• 完整性、原子性、并发访问、安全性问题

数据库系统阶段

60年代后期

• 面向全组织的复杂数据结构（数据结构化是数据库与文件系统的根本区别）
• 数据冗余度小可控，易扩充。集成共享（不再面向应用而是整个系统）
• 具有较高的数据和程序的独立性（物理独立性：数据的存储结构改变时，其逻辑结构不必改变。通过数据的存储结构互为逻辑结构之间的映像实现。逻辑独立性：数据的逻辑结构改变时，应用程序可以不变。通过数据的全局逻辑结构与某类应用所涉及的局部逻辑结构之间的映像实现。）
• 统一的数据控制功能
  • 安全性控制（不合法使用导致泄露、破坏）
  • 完整性控制（正确性、相容性）
  • 并发控制
  • 数据库恢复
• 数据的最小存取单元是数据项

数据库系统的组成

基本问题：集成数据的表示。核心技术：数据模型

主要部分：数据库、用户、软件、硬件

数据库

各种数据。包括目标数据以及描述数据

数据库中的数据是集成的和共享的。集成指特定应用环境中各种应用相关的数据以及数据之间的联系全部地、集中地并按一定结构进行存储。共享指数据被多个用户共享

用户

终端用户

应用程序员：

数据库管理员

系统分析员和数据库设计者

软件

负责数据库存取、维护和管理地软件系统。包括

• 数据库管理系统DBMS
• 支持DBMS运行的操作系统
• 数据库接口的高级语言及其编译系统
• 应用开发工具
• 各种应用系统

硬件

包括内存、外存

数据模型

定义：数据模型用来抽象和表示现实世界中的数据和信息

要求比较真实的模拟现实世界/容易被人理解/便于在计算机上实现

组成要素：

• 数据结构。包括数据本身和数据之间的联系
• 数据操作。是对系统动态特性的描述，包括操作以及操作规则等
• 数据约束条件。完整性规则的集合

概念模型（信息模型）

按用户的观点来对数据和信息建模

实体：客观存在并且可相互区分的事物

属性：实体所具有的某一特性

域：属性的取值范围

实体集：同型实体的集合

实体型：实体名与其属性名集合来刻画同类实体

码：能唯一标识实体的属性集

联系：

ER图

逻辑数据模型

从计算机实现的观点来对数据建模

层次模型：树结构。节点表示实体型，连线表示两实体型间的一对多联系

• 优点：结构简单、易于实现。性能良好。良好的完整性支持
• 缺点：难以描述非层次性的联系。存取只能通过双亲结点来进行。层次命令趋向程序化

网状模型：有向图

• 优点：能更为直接的描述现实世界。性能良好
• 缺点：结构复杂。语言复杂。不利于用户掌握

关系模型：二维表

• 优点：建立在严格的数学概念基础上。简单易理解。概念单一。存取路径透明，独立性和安全性更好。
• 缺点：性能往往不如非关系数据库

要求关系中每个分量是不可分的数据项

面向对象模型：

数据库系统结构

三级模式、两级映像

型是指对某一类数据的结构和属性的说明，值是型的一个具体赋值

模式：全体数据的逻辑结构和特性的描述，三级模式的核心。不涉及数据物理存储细节，与具体的应用程序与编程语言无关

外模式（用户模式）：与某一应用有关的数据的逻辑表示。用户的数据视图

模式：所有用户的公共数据视图。全体数据的全局逻辑结构和特性的描述

内模式（存储模式）：对数据的物理结构和存储方式的描述

外模式/模式映像：定义某个外模式与模式之间的对应关系，数据的逻辑独立性

模式/内模式映像：定义数据逻辑结构与存储结构之间的对应关系，数据的物理独立性

• 保证了数据的独立性
• 简化用户接口
• 有利于数据共享
• 有利于数据安全保密

DBA

数据库管理员

决定数据库中的信息内容和结构

决定数据库的存储结构和存取策略

定义数据的安全性要求和完整性约束条件

监控数据库的使用和运行

数据库的改进和重组重构

DBMS

数据库管理系统

主要功能：

• 数据库定义功能，提供DDL描述三种模式
• 数据存取功能，DML
• 数据库运行管理
• 数据组织、存储和管理
• 数据库的建立和维护功能

组成：

• 语言编译处理程序
• 系统运行控制程序
• 系统建立和维护程序
• 数据字典

数据库技术的发展

关系数据模型

组成：

• 数据结构：关系，即二维表
• 完整性约束：实体完整性约束、参照完整性约束、用户定义完整性约束
• 关系操作：包括选择、投影、连接、除、并、交、差，增删改。操作对象及结果都是集合
• 关系数据语言：包括关系代数、关系演算、SQL语言

特点：

• 面向集合的存取方式
• 非过程化

数据结构

域：一组具有相同数据类型的值的集合，如整数、实数

笛卡尔积：给定一组域 \(D_1,D_2,...,D_n\) ，其笛卡尔积为 \(D_1\times D_2\times...\times D_n=\{(d_1,d_2,...,d_n)|d_i\in D_i,i=1,2,...,n\}\) 。若 \(D_i\) 有限，则笛卡尔积的基数为 \(\prod\limits_{i=1}^nm_i(m_i为D_i的基数)\)

元组与分量：笛卡尔积中的每个元素称为一个n元组，元组的每个值叫做分量

关系：笛卡尔积的子集叫做在域 \(D_1,D_2,...,D_n\) 上的关系，用 \(R(D_1,D_2,...,D_n)\) 表示

关系模型中要求关系是有限的

• 列是同质的（每一列中的分量来自于同一域）
• 行、列的顺序无所谓
• 任意两个元组不能完全相同
• 若每一分量是不可再分的数据，则称此关系是满足第一范式（1NF）的

关系模式：关系的描述。形式化表示为 \(R(U,D,dom,F,I)\) ，R为关系名，U为属性名集合，D为属性集U来自的域，dom是由属性到域的映像集合，F是属性间的数据依赖关系，I是完整性约束集合。也可简记为 \(R(A_1,A_2,...,A_n)\)

关系数据库：在给定的应用领域中，所有实体以及实体之间联系的关系的集合构成一个关系数据库

一些描述

候选码：关系模式R(U)的属性集合 \(k\in U\) 是候选码，如果

1. R（U）的任何一个关系实例的任意两个元组在属性集合k上的值都不同。即唯一性，候选码的属性值必须能够唯一地标识关系中的所有元组。
2. k的任何真子集都不满足条件（1）。即最小性，候选码不能包含多余属性。

主码：多个候选码中，选定的码

外部码：关系R的一个或一组属性是另一关系K的主码。R为参照关系，K为被参照关系。注意R和K未必不同，如班长学号参照学号

候选码中的诸属性称为主属性，不包含在任何候选码中的属性称为非主属性。

在最极端的情况下，关系模式的所有属性是这个关系模式的候选码，称为全码。

语义约束：实体完整性、参照完整性、用户定义完整性

• 实体完整性：主码不能取空值
• 参照完整性：关系R2的外部码Fk与关系R1的主码Pk对应，则Fk要么取R1中某个元组的主码的值，要么为空
• 用户定义完整性：用户针对具体应用环境的约束

关系代数

传统集合运算

就是把关系看成元组集合的运算

并：\(R\cup S=\{t|t\in R\lor t\in S\}\)

差：\(R-S=\{t|t\in R\land t\not\in S\}\)

交：\(R\cup S=\{t|t\in R\land t\in S\}\)

广义笛卡尔积：\(R\times S=\{t|t=<r,s>\land r\in R\land s\in S\}\) ，结果的度是R与S的度之和，元组个数是R和S元组个数之积

专门关系运算

选择：在关系中选择满足给定条件的元组，\(\sigma_F(R)=\{t|t\in R,F(t)=真\}\)

投影：从关系中选取若干属性列，然后合并重复行，\(\Pi_A(R)=\{t[A]|t\in R,A\subseteq U\}\)

连接：关系R和S在属性X和Y上的连接，即从两个关系的广义笛卡尔积中选取给定属性X、Y间满足比较条件 \(\theta\) 的元组，\(\underset{X\theta Y}{R⋈S}=\{t|t=<r,s>\land r\in R\land s\in S\land r[X]\theta s[Y]\}\)

自然连接：在相同属性列上做等值连接，并去掉重复的属性列

复合连接：自然连接去掉相同属性列（都去掉）

半连接：在R与S的连接运算结果中只保留R的属性列所得到的元组集合

外连接：自然连接 + 失配的元组（补空行）

象集：关系R(X , Y), X, Y是属性组，x是X上的取值，定义x在R中的象集为Yx = { r[Y] | rR  r[X]= x } 从R中选出在X上取值为x的元组，去掉X上的分量，只留Y上的分量。

除运算：给定关系R(X,Y)和S (Y,Z),其中 X,Y,Z是属性组，R中的Y与S中的Y可以有不同的属性名，但必须出自相同的域集。R与S的除法运算得到一个新的关系P（X），P是R中满足下列条件的元组在X属性列上的投影：元组在X上分量值x的象集Yx包含S在Y上投影的集合。

实现方法：

1. 求 \(Z=\Pi_X(R)\times\Pi_Y(S)\)
2. 求 \(P=\Pi_X(Z-R)\) 。相当于求出了R中不完全包含关系Y的S属性取值范围的元组
3. \(R\div S=\Pi_X(R)-P\)

笛卡尔积的逆运算，R/Z相当于给定R,Z，求出最大的能使Z*S（笛卡尔积）包含于R的S

元组关系演算

元组演算表达式：\(\{t|\Phi(t)\}\) ，表示所有使谓词 \(\Phi\) 为真的元组集合

t为元组变量，\(\Phi(t)\) 是元组关系演算公式，由原子公式和运算符组成，简称公式

原子公式：

• R(t)，t是关系R中的一个元组
• t[ i ] θ u[ j ]。t[ i ]与u[ j ]分别为t的第i个分量和u的第j个分量，它们之间满足比较关系θ 。
• t[ i ] θ c或c θ t[ i ] 。分量t[ i ]与常量c之间满足比较关系

比如查询学生姓名和所在的系：\(\{t^{(2)}|(\exists u)(STUDENT(u)\land t[1]=u[2]\land t[2]=u[5])\}\)

元组关系演算与关系代数的等价性：

域关系演算的安全性

SQL语言

概述

特点：

• 综合统一
• 高度非过程化
• 面向集合的操作方式
• 以同一种语法结构提供两种使用方式（既是自含式，又是嵌入式）
• 语言简洁

基本表：本身独立存在的表，一个/多个基本表对应一个存储文件

存储文件：由数据块构成的存储空间，其逻辑结构组成了关系数据库的内模式

视图：从一个或几个基本表中导出的表，其本身不独立存储于数据库中

嵌入式SQL：预编译/函数方式实现。

TODO考吗？

查询语句

select[ALL|DISTINCT]<目标表达式>{,<目标表达式>}
from <表名或视图名>{,<表名或视图名>}
[where <条件表达式>]
[group by <分组列>{,<分组列>} [having <条件表达式>]]
[order by <排序列> <排序方式>{,<排序列> <排序方式>}]

分类：单表查询、连接查询、嵌套查询、集合查询

查询条件

查询条件	谓词
比较	>,>=,<,<=,=,!=,<>,!>,!<,not
确定范围	between and,not between and
确定集合	in,not in
字符匹配	like,not like
空值	is NULL,is not NULL
多重条件	and,or
升序/降序	asc,desc

举例：

#查询年龄在[20,23]的数学系和计算机系的学生的姓名、年龄
select name,age from Student where age between 20 and 23 and dept in ('MA','CS');
#查询所有姓刘的学生
select * from Student where name like '刘%';
#查询所有姓刘、名字两个字的学生（名长度是2，下划线跟2个）
select * from Student where name like '刘__';
#查询全体学生的情况，并按所在系的升序和年龄的降序排列
Select * From Student Order By Sdept Asc, Sage Desc

聚集函数

功能	实现
count()	求元组个数
sum()	对数值列求总和
avg()	求数值列的平均值
max()	求最大值
min()	求最小值
group by	按某一或多个属性进行分组

举例

#查询学生总数
select count(*) from Student;
#计算一号课程的平均成绩
select avg(grade) from SC where Cno='1';
#查询选课至少为3门的学生的学号及其选课门数
select Sno,count(Sno) from SC group by Sno having count(sno)>=3;

连接查询

举例

#查询每个学生及其所选课程的情况
Select Student.*, SC.* From Student, SC Where Student.Sno = SC.Sno;

嵌套查询

一个select-from-where称为一个查询块，将一个查询块嵌套在另一个查询块的where子句或having短语的条件中的查询称为嵌套查询。上层为外层查询/父查询，下层为内层查询、子查询

子查询的select语句中不能使用order by语句

相关子查询：子查询的查询条件引用了外部查询的某个属性值。先从外部查询选取一行记录（候选行），然后子查询利用候选行相关列的数据进行查询，结果返回外部查询，外部查询在进行判断，结果放入结果集合

不相关子查询：执行顺序为由内向外求解

举例

#查询其他系中比信息系中某一学生年龄小的学生姓名和年龄。
Select Sname, Sage From Student
Where Sdept <> ‘IS’ And Sage < Any(
    Select Sage From Student Where Sdept = ‘IS’);
#查询选修了全部课程的学生姓名
Select Sname From Student 
	Where Not Exists 
		(Select * from Course 
         	Where Not Exists
         		(Select * from SC 
                 	Where Sno=Student.Sno
                 		And Cno=Course.Cno));

集合查询

举例

#查询选修了1号课程和选修了2号课程的学生的并集
select sno from SC where cno='1' union select sno from SC where cno='2'

更新语句

包括insert、update、delete语句

insert

插入一条或多条记录，没填的列是空或null

insert into <表名>[(<属性列>{,<属性列>})] values(<值>{,<值>})	#插入数据
insert into <表名>[(<属性列>{,<属性列>})] <子查询>		#插入子查询结果

#举例
insert into student values('114514','我超，盒！','IS',18);
insert into SC(sno,cno) values('114514','1919180');
Insert Into Dept_Age (Sdept, Avgage)Select Sdept, AVG(Sage) From Student Group By Sdept;

update

更新某一列的值，根据where确定是哪几行的值

update <表名> set <列名>=<表达式>{,<列名>=<表达式>} [where <条件>]

#举例
update Student set age=22 where sno='114514';	#去掉where就是修改全体学生的年龄

delete

删除一行或多行记录（元组）

delete from <表名> [where<条件>]

#举例
delete from student where sno='114514';

定义语句

对象	创建	删除	修改
表	create table	drop table	alert table
视图	create view	drop view
索引	create index	drop index

表

数据类型有：

数据类型	说明
char(n)	固定长度字符串
varchar(n)	可变长字符串
smallint	小整数
int	整数
numeric(p,d)	定点数
real,double precision	浮点数，双精度浮点数
float(n)	n位浮点数
date	日期（年月日）
time	时间（时分秒）
interval	两个date或time之间的差

完整性约束

完整性约束	说明
NULL/not NULL
UNIQUE	候选码，可以为空
PRIMARY KEY	主码，不为空，只能设定一个或一组属性
FOREIGN KEY	外码
CHECK

create table <表名> (<列名><数据类型>[<列级完整性约束>]{,<列名><数据类型>[<列级完整性约束>]}	{,<表级完整性约束>})
alter table <表名> add(<新列名><数据类型>[<完整性约束>]) drop <完整性约束名> modify(<列名><数据类型>)
drop table student;

#举例
create table student(
	sno char(12) not null,
    sname char(20) not null unique,
    ssex char(2),
    sage int,
    sdept char(15),
    
    primary key(sno),
    foreign key(sdept) references CDEPT(cdept),
    check(sage>=18 and sage <=45)
);
alter table student add(comedate Date) drop primary key;
drop table student;

13

create table S(
	S char(20),
    SN char(20),
    SA int,
    SD char(20),
    primary key(S)
);

create table C(
	C char(20),
    CN char(128),
    PC char(20),
    primary key(C),
    foreign key(PC) references C(C)
);

create table SC(
	S char(20),
    C char(20),
    G int,
    primary key(S,C),
    foreign key(S) references S(S),
    foreign key(C) references C(C),
    check(G<100)
);

insert into S values('s1','李勇',20,'CS');
insert into S values('s2','刘晨',19,'IS');
insert into S values('s3','王敏',18,'MA');
insert into S values('s4','张立',19,'IS');

insert into C(C,CN) values('C2','数学');
insert into C(C,CN) values('C6','数据处理');
insert into C values('C7','Pascal语言','C6');
insert into C values('C4','操作系统','C6');
insert into C values('C5','数据结构','C7');
insert into C values('C1','数据库','C5');
insert into C values('C3','信息系统','C1');

insert into SC values('s1','C1',92);
insert into SC values('s1','C2',85);
insert into SC values('s1','C3',88);
insert into SC values('s2','C2',90);
insert into SC values('s2','C3',80);

SELECT S FROM S WHERE NOT EXISTS(
    SELECT C FROM C WHERE 
    C IN (SELECT C FROM SC WHERE SC.S='s2') 
    AND C NOT IN (SELECT C FROM SC WHERE SC.S=S.S));

create ASSERTION AAA check(100>=all(select G from S));

索引

create [unique][cluster] index <索引名> on <表名> (<列名>[次序]{,<列名>[次序]});
drop index <索引名>

#举例
Create Unique Index Scno On Sc (Sno ASC, Cno DESC);

视图

视图：由一个或几个基本表/视图导出的表，数据库不存储视图的数据而存储其定义，因此也称虚表

• 简化用户操作
• 使用户能以多种角度看待同一数据
• 对重构数据提供了一定程度的逻辑独立性
• 对机密数据提供安全保护

视图消解：执行对视图的查询时，取出对视图的定义，把定义中的子查询和用户的查询结合起来，转换成等价的对基本表的查询

视图更新约束：

• select子句的目标列不能包含聚集函数
• select子句中不能使用distinct关键字
• 不能包括group by语句
• 不能包括经算术表达式计算出来的列
• 对于行列子集视图可以更新（视图是从单个基本表使用选择、投影操作导出的，并且包含了基本表的主码）

create view <视图名> [(<列名>{,<列名>})] as <子查询> with check option;
drop view <视图名>

Create View IS_Student
  As
  Select Sno, Sname, Sage, Sdept From Student
  Where Sdept = ‘IS’
  With Check Option;

数据库的安全性与完整性

数据库安全性

含义：保护数据库以防止不合法的使用所造成的数据泄漏、更改和破坏

• 向授权用户提供可靠的信息服务
• 拒绝非授权的对数据的存取访问请求

数据库的安全性控制：内部安全控制（由计算机系统的软硬件实现）、外部安全控制

外部安全控制包括实体安全控制、人员组织安全控制、过程安全控制

用户标识与鉴别

系统提供的最外层的保护

通常做法位用户名+口令

标识：采用一定的方式标识用户或引用程序的名字或身份

鉴别：用户或程序登录时判断是否位合法的授权用户

存取控制

确保合法用户按指定权限使用DBMS和访问数据，非法用户或不具有相关权限的用户则不能

存取控制机制的两部分：定义用户权限、合法的权限检查

自主存取控制（DAC）

不同用户对不同数据对象有不同权限，用户可将其拥有的权限转授给其他用户

只有用户有权限，并且用户可以转授权限

用户权限的组成要素：数据对象+操作类型。数据对象如模式、基本表、视图、索引，操作类型如建立、修改、检索、插入、删除等

角色：一组权限的集合，可授予用户或其他角色

用户组：一组具有相同特性用户的集合

grant <用户级权限>|<角色> {,<用户级权限>|<角色>} 
to <用户名>|<角色>|<public> {,<用户名>|<角色>}	#public表示全体用户
[with grant option];	#表示可以转授给其他人

revoke <用户级权限>|<角色> {,<用户级权限>|<角色>} 
from <用户名>|<角色>|<public> {,<用户名>|<角色>}	#public表示全体用户

#关系级权限
grant all|<权限>{,<权限>}
on <表名>|<视图名>{,<表名>|<视图名>}
to {<用户>{,<用户>}|public}
[with grant option]

revoke all|<权限>{,<权限>}	#若该用户已经将权限授予其他用户，则将一并收回
on <表名>|<视图名>{,<表名>|<视图名>}
from {<用户>{,<用户>}|public}

强制存取控制（MAC）

每个数据对象有一定密级，用户被授予某一级别的许可。合法许可才能访问

数据和用户都有标签

主体：系统中的活动实体，包括管理的实际用户、用户的进程。敏感度标记成为许可证级别

客体：系统中的被动实体，受主体操纵，包括文件、基本表、索引、视图等等。敏感度标记称为密级

主体许可证级别大于等于客体密级才能读，等于才能写？

审计和数据加密

审计功能：把用户对数据库的所有操作都自动记录下来放入审计日志中

数据加密：是防止数据库中数据在存储和传输中失密的有效手段

统计数据库安全性

含义：统计数据库只为用户提供统计数据，不允许用户访问微数据（个例）

对统计结果的大小加以控制

禁止在相同元组集合上重复执行一系列统计查询

在统计查询结果中加入噪声，为推导微数据制造困难

数据库完整性

数据库的完整性是指数据的正确性（合法的类型、取值范围）和相容性（同一事实的两个数据应该相同）。

完整性约束条件

施加在数据库数据之上的语义约束条件称为数据库完整性约束条件

约束对象：关系、元组、关系

静态约束

静态约束：数据库每一确定状态时，数据对象所应满足的约束

• 固有约束：指数据模型固有的约束，如关系的属性应当是原子的
• 隐含约束：指隐含于数据模式的约束，一般用DDL语句说明，并存于数据字典中。如实体完整性约束。
• 显式约束：指固有约束，隐含约束之外，依赖于数据的语义和应用，需要显式定义的完整性约束。

按对象划分：

• 静态列级约束：数据类型、格式、取值范围等

• 静态元组约束：元组中各列之间的关系

• 静态关系约束：实体完整性约束、参照完整性约束、函数依赖、统计约束

动态约束

动态约束：数据库从一种状态转变为另一种状态时，新、旧值之间所应满足的约束条件

• 动态列级约束：修改列定义或列值时应满足的约束条件

• 动态元组约束：修改元组值时元组中各个字段间需要满足的约束

• 动态关系约束：加在关系变化前后状态上的限制条件

数据库的完整性控制机制

三个功能：定义、检查、违约响应

立即执行约束：每条执行完后立即检查，若违背则拒绝操作

延迟执行约束：整个用户事务执行完毕后再检查，正确方允许提交

一条完整性规则可用一个五元组DOACP来描述

• D（data）：约束所作用的数据对象（如工资表的sal属性）

• O（Operation）：触发完整性检查的数据库操作（插入或修改职工元组时）

• A（Assertion）：数据对象必须满足的断言或语义约束（sal>10000）

• C（Condition）选择A作用的数据对象值的谓词。（职称='教授'）

• P（procedure）：违反完整性规则时触发的过程（拒绝执行该操作）

实现显式完整性约束：

#断言
assert 余额约束 on 储蓄表: 余额>=0;
#触发器
Create Trigger Update_Sal
        Before Insert Or Update Of Sal, Pos On Teacher
        For Each Row
        When (:new.pos = ‘Professor’)
        Begin
               If :new.sal <1000 Then
                   :new.sal = 1000;
               End If
        End;

关系数据理论

数据依赖：通过关系中属性间值的相等与否体现出来的数据间的相互关系

函数依赖：数据依赖的一种，当x确定后，y也唯一确定，则称x函数决定(y)，(y)函数依赖于x

函数依赖

设R(U)是属性集U上的关系模式，X , Y 是U的子集。若对于R(U)的任意一个可能的关系r，r中不可能存在两个元组在X上的属性值相等，而在Y上的属性值不等，则称X函数决定Y，或Y函数依赖于X，记作 \(X\rightarrow Y\)。

平凡函数依赖：\(X\rightarrow Y\) ，但 \(Y\subseteq X\) ，则称为平凡函数依赖，否则非平凡

完全函数依赖：若 \(X\rightarrow Y\) ，且对于任意 \(X\subset X'\) ，\(X'\not\rightarrow Y\) ，则称Y对X完全函数依赖，记作 \(X\overset{f}\rightarrow Y\) ，否则为为不完全函数依赖 \(X\overset{p}\rightarrow Y\)

完全函数依赖类似于候选码

传递函数依赖：\(X\rightarrow Y,Y\rightarrow Z,Y\not\subseteq X,Z\not\subseteq Y,Y\not\rightarrow X\) ，称Z对X传递函数依赖

多值依赖：\(Z=U-X-Y\) ，任意一个关系r，(x,z)都能决定y，但仅决定于x，则多值依赖 \(X\rightarrow\rightarrow Y\) 成立

TODO：不懂

函数依赖是多值依赖的特例

超码：设K为R<U,F>的属性或属性组，\(K\rightarrow U\) ，则称K为R的超码

码属于超码

主属性：包含在任何一个候选码中的属性

非主属性：不包含在任何一个候选码中的属性

全码：关系模式的码由整个属性组构成

范式

范式定义：对关系的不同数据依赖程度的要求

规范化：一个低级范式的关系模式，通过模式分解可以转换为若干个高级范式的关系模式的集合

1NF

关系中每一分量必须是原子的，不可再分（不能用序列、集合作为属性值）

2NF

\(R\in1NF\) ，且每个非主属性完全依赖于码，则称 \(R\in2NF\)

要求没有部分函数依赖。没有非主属性也是2NF

3NF

关系模式R<U,F>中，若不存在这样的码X，属性组Y，以及非主属性Z（\(Z\not\subseteq Y\)），使得下式成立 \(X\rightarrow Y,Y\rightarrow Z,Y\not\rightarrow X\) ，则称 \(R\in3NF\)

要求没有传递函数依赖

不规定 \(Y\not\subseteq X\) 是为了同样去除部分函数依赖

BCNF

若关系模式\(R<U,F>\in1NF\) ，若 \(X\rightarrow Y,Y\not\subseteq X\) 时，X必含有码，则 \(R<U,F>\in BCNF\)

• 所有非主属性都完全函数依赖于每个候选码
• 所有主属性都完全函数依赖于每个不包含它的候选码
• 没有任何属性完全函数依赖于非码的任何一组属性

数据依赖的公理系统

对于满足一组函数依赖F的关系模式R<U,F>，其任何一个关系r，若函数依赖 \(X\rightarrow Y\) 都成立，则F逻辑蕴含\(X\rightarrow Y\)

Armstrong公理：

• 自反：\(Y\subseteq X\subseteq U\)，则 \(X\rightarrow Y\) 为F所蕴含
• 增广律：\(X\rightarrow Y,Z\subseteq U\)，则 \(XZ\rightarrow YZ\) （指并集）
• 传递律：\(X\rightarrow Y,Y\rightarrow Z\)，则 \(X\rightarrow Y\)

闭包：\(X_F^+=\{A|X\rightarrow A能由F根据Armstrong公理导出\}\)

数据依赖集的等价：F于G等价，当且仅当 \(F^+=G^+\)

最小依赖集F：

• F中任一函数依赖右端仅含一个属性
• F中不存在这样的函数依赖 \(X\rightarrow A\) ，使得F与 \(F-\{X\rightarrow A\}\) 等价
• F中不存在这样的函数依赖 \(X\rightarrow A\) ，在X中有真子集Z，使得F与 \(F-\{X\rightarrow A\}\cup\{Z\rightarrow A\}\) 等价（不存在部分函数依赖）

模式分解：

函数依赖集合 \(F_i=\{X\rightarrow Y|X\rightarrow Y\in F^+\land XY\subseteq U_i\}\) 称为F在 \(U_i\) 上的投影

就是把F中不在U上的函数依赖关系去掉了

关系模式R<U,F>的一个分解是指 \(\rho=\{R_1<U_1,F_1>,R_2<U_2,F_2>,...,R_n<U_n,F_n>\}\) ，其中 \(U=\cup_{i=1}^nU_i\) ，且没有 \(U_i\subseteq U_j,1\leq i,j\leq n\) ，\(F_i\) 是F在 \(U_i\) 上的投影

无损连接、3NF、函数依赖不变

设 \(\rho\) 是 \(R(U,F)\) 的一个分解，r是R的一个关系，定义 \(m_\rho(r)=\overset{k}{\underset{i=1}{R⋈S}}\prod_{R_i}(r)\) ，即r在 \(\rho\) 中各关系模式投影上的连接。若任意一个r，都有 \(r=m_\rho(r)\) ，则称无损连接分解

担任连接的字段为候选码，则为无损连接

判断是否为无损分解：

1. 建表，表头的一行为各个属性，左边一列是分解后的属性组，(i,j)若属性j在属性组i里填aj，否则填bij。
2. 遍历每个依赖X->Y，查看X和Y列，对于X列取值相同的那些行，若对应的Y列有a，则都改成a，否则改成最小的bij
3. 若有一行都是a，则是无损分解

TODO：3NF、BCNF、无损连接、函数依赖的分解

例：

设有关系R（U, F）U={A, B, C, D, E, F, G}F={E→D, C→B, CE→AF, B→A, C→AB}

求：R的候选码判断R所属的范式如果R不属于第三范式，将R规范化到第三范式，并保持函数依赖和无损连接的分解

1. 将属性按L（只出现在函数依赖的左边）R LR N（都不出现）分类，求出可能的候选码，然后求最小依赖集。结果为CEG
   
2. 最小依赖集：1将函数依赖的右部分解为单属性2去掉多余的函数依赖3检查是否存在部分函数依赖
3. 按相同左部分组。若无候选码则再加入包含候选码的一个分解

数据库设计

设计方法：手工试凑、规范化设计、自动数据库设计工具

手工试凑缺点：

• 数据间关系复杂，要求多样，很难仅凭经验设计
• 需求变，数据结构很难随之发生变化
• 与DBMS结合紧密，移植困难
• 缺乏文档资料，难以评审
• 难以由多人合作进行设计

规范化设计方法：将设计过程划分为若干阶段，每个阶段只解决整个设计中的部分问题

共六个阶段：需求分析、概念结构设计、逻辑结构设计、物理结构设计、数据库实施、数据库运行与维护

需求分析：用数据流图表达关系、数据字典描述数据

概念结构设计：E-R法。最常用的是自底向上方法

规范化设计的特点：

• 分步进行
• 反复性
• 试探性

数据字典：系统中各类数据描述的集合。包括数据项、数据结构、数据流、数据存储、处理过程

关系的存取方法：索引方法、聚集方法、HASH方法

存储管理和索引

磁盘访问时间=寻道时间+旋转时间+传输时间

数据库存储结构：数据库-文件-块/页。文件在逻辑上被组织为记录的序列

文件的磁盘块分配：

• 连续分配
• 链接分配
• 按簇分配
• 索引分配

页/块最常用的是分槽页结构，有header和data

文件中记录的组织方式为堆（随便放在文件中的任意位置）、顺序、索引、散列、聚集（相同或相似的记录存储于连续的磁盘块中）

缓冲区被组织为一个固定大小的页面数组，每个元素称为帧，存放在磁盘上的一个页/块

缓冲区允许有共享锁、排他锁，对页进行封锁。替换策略如LRU（最近最少使用）

索引：排序/哈希，聚集/非聚集。稠密/稀疏

多级索引如二叉树、B树（所有叶节点在同一层，关键字散布在各层）、B+树（关键字按递增顺序从左到右安排在叶节点上）

查询优化

查询处理的基本步骤：语法分析与翻译、优化、执行查询语句

查询优化的步骤：转为内部表示如语法树、优化语法树、选择底层的操作算法、生成查询执行计划

连接操作

• 嵌套循环
• 排序-合并
• 索引连接
• Hash join

查询代价=IO代价+CPU代价+通信开销

关系代数的等价变换规则：

• 连接、笛卡尔积各自都具有交换律、结合律
• 投影的串接定律 \(\Pi_A(\Pi_B(E))=\Pi_A(E)\)
• 选择的串接定律 \(\sigma_{F_1}(\sigma_{F_2}(E))=\sigma_{F_1\land F_2}(E)\)
  
• ……TODO

查询优化的一般准则：

• 选择运算尽可能先做。（为了减小中间结果）
• 执行连接操作前对文件适当预处理，如排序、在连接属性上建立索引等等
• 投影运算和选择运算同时做。（避免重复扫描关系）
• 投影运算与前面或后面的双目运算结合起来。（减少扫描关系的遍数）
• 查询树：使用连接操作代替笛卡尔积
• 查询树：没用的属性利用投影操作去掉

TODO考吗？

数据恢复

事务：用户定义的一个数据库操作序列构成，操作要么全做，要么不做

事务的特性：

• 原子性：事务定义
• 一致性：执行结果应当使数据库从一个一致性状态转变为另一个一致性状态
• 隔离性：一个事务的隔离不能被其他事务干扰
• 持久性：提交之后，对数据库的影响是永久的

数据库恢复子系统的目的：保证事务的原子性、发生故障后能恢复到正确的状态

故障的种类：

• 事务内部的故障。分为可预期如？，不可预期如死锁、违反完整性规则
• 系统故障。如蓝屏、停电。需要清除所有未完成的事务对数据库的修改，同时重做所有已完成的事务
• 介质故障。如磁盘损坏
• 计算机病毒

数据库恢复的技术

数据库恢复的原理：冗余。

建立冗余的常用方法有数据转储、登录日志文件

数据冗余+操作冗余

数据转储

从转储状态上分为两种

• 静态转储（转储期间数据不会变化，不允许对数据库的任何存取、更新）
• 动态转储

从转储方式上分为两种

• 海量转储：每次转储全部数据库
• 增量转储：每次只转储上次转储后更新过的数据

登录日志文件

日志文件是用来记录事务对数据库的更新操作的文件

以记录为单位的日志文件记录事务的开始标记、结束标记、更新操作

以数据块为单位的日志文件记录事务标识、更新前后的数据块

登记日志文件的原则：

• 登记次序严格按并发事务执行的时间顺序
• 先写日志文件后写数据库

恢复策略

事务故障的恢复

1. 反向扫描文件日志找到该事务的更新操作
2. 将更新前的值写入数据库
3. 直到读到该事务的开始标志

系统故障

1. 正向扫描日志文件，找出故障前已经提交的事务，计入重做REDO队列，未完成的计入撤销UNDO队列
2. 撤销队列进行UNDO操作，反向扫描日志文件，写入更新前的值
3. 重做队列进行REDO处理，正向扫描日志文件执行

介质故障

1. 装入最新的数据库后备副本
2. 装入转储以后的日志文件副本

其他技术

推迟更新技术：每个事务到达提交点前不能更新数据库。更新操作的日志写入前不能到达提交点

具有检查点的恢复技术：记录检查点时刻所有正在执行的事务清单、以上事务最近一个日志记录的地址

数据库镜像

根据DBA要求，自动把整个数据库或其中的关键数据复制到另一个磁盘上。更新时，DBMS保证一致性

增强了可靠性（故障后可以通过镜像继续服务）、提供一定并行性

并发控制

优点：

• 提高系统吞吐量，改善系统资源利用率
• 减少平均响应时间

问题：

• 丢失修改（T1的提交修改被T2覆盖）
• 不可重复读（T1读之后，T2改，T1再读时不一样了）
• 读到脏数据（T1写，但T2出错，一并撤销，T1再访问就读到脏数据）

条件：多个事务同时访问一个数据集合、至少一个事务对数据集合进行了更新

锁

采用的技术：封锁

锁的类型：

• 排他锁（X锁），写时加，其他事务的任何请求都不成功
• 共享锁（S锁），读时加，其他事务可读不可写

相容矩阵

一级封锁协议：修改数据之前必须加X锁。可防止丢失修改

二级封锁协议：一级锁协议+读取前必须加S锁。可防止读脏数据

三级封锁协议：1+读取前必须加S锁，直到事务结束才释放。可防不可重复读

死锁活锁

预防死锁：

• 一次封锁法：每个事务必须一次将所有要使用的数据全部加锁，降低了系统并发度
• 顺序封锁：预先规定一个封锁顺序，数据库动态变化很难实现

死锁检测与恢复：

检测：超时法、等待图法（节点是事务，a指b代表a等待b，存在回路说明死锁）

恢复：选一个代价最小的事务，撤销

事务的调度：串行调度、并行调度。多个事务的并发执行是正确的，当且仅当其结果与按某一次串行的执行顺序结果相同。称调度策略为可串行化调度。一个并发调度可串行化才正确

各种锁

两段锁协议：

• 在对任何数据进行读写操作之前，事务首先要获得对该数据的封锁。
• 在释放一个封锁之后，事务不再获得任何其他封锁

若所有事务都遵循两段锁协议，则可串行化

封锁粒度：封锁对象（逻辑单元如元组，物理单元如物理页）的大小。颗粒度小则并发程度高、封锁机构复杂、开销大

多粒度树：根节点是整个数据库，表示最大的粒度，叶节点表示最小的粒度

多粒度封锁协议：多粒度树中的每个结点被独立地加锁，结点中的所有子节点也被加上同样类型的锁

意向锁：如果对一个结点加意向锁，则说明下层结点正在被加锁；对任一结点加锁时，需要先对上层结点加意向锁

有意向共享锁IS、意向排他锁IX、意向共享排他锁SIX

分布式数据库

分布式数据库由分布在计算机网络的不同计算机上的一组数据组成，网络中每个节点具有场地自治性（可以执行局部应用，即只对本节点数据进行存取的应用），每个节点也通过网络通讯支持全局应用

特点：分布性（独立存储、独立处理）、逻辑整体性

分布式数据库系统的特点：

• 数据独立性
• 集中与自治相结合的控制机构
• 适当增加数据冗余
• 全局的一致性、可串行性、可恢复性

目标：

• 适应部门分布的组织结构、降低费用
• 提高系统的可靠性和可用性
• 充分利用数据库资源，提高现有集中式数据库的利用率
• 逐步扩展处理能力和系统规模

设计

分布透明性包括

• 分片透明性。用户只对全局关系进行操作而不必考虑关系的分片
• 位置透明性。用户或应用程序不必了解片段的存储位置
• 局部数据模型透明性。不必了解局部场地上使用哪种数据模型

存储方式有

• 重复存储。几个节点有完全相同的副本
• 分片存储。完全性、不相交性、可重构性
  • 水平分片。按行分
  • 垂直分片。按列分
  • 导出分片。按其他关系的属性条件分片
  • 混合分片。连续应用几种分片方法
• 组合存储。重复存储和分片存储相结合

命名和局部自治性：每个数据项必须有唯一的名字。方法：名字服务器/节点+名字

管理系统

D-DBMS的四个组成部分：

• LDBMS，局部场地上的DBMS
• GDBMS，全局数据库管理系统
• 全局数据字典，存放全局概念模式、分片模式等定义、映像定义等等
• 通信管理

D-DBMS的分类：

全局控制集中、全局控制分散、全局控制部分分散

同构型、异构型（各节点的局部DBMS不同）

查询处理

分类有局部查询、远程查询、全局查询。前两个只涉及单点数据

处理过程：查询变换、数据定位

集中式数据库：IO+CPU代价 分布式数据库：IO+CPU代价+通信代价

传送时间T=总传输延迟+总数据量/传输速度

TODO半连接的传输

事务处理

不仅要保证事务在每个节点上的原子性，还要保证全局事务的原子性

事务管理器：管理在局部节点的事务或全局事务的一部分

事务协调器：协调该节点发起的事务的执行

sthelse

数据模型三要素：数据结构、数据操作、数据完整性约束

存取控制包括：自主（DAC），强制（MAC）。其机制包括用户权限定义、合法权限检查

DAC的用户权限的组成要素：数据对象+数据操作

完整性控制的功能包括：定义、检查、违约响应

data要用like，比如 select * from test1 where a like '2025%' ，或者 select * from test1 where a like '_____01___';