数据库系统期末复习

雨点打透心脏的1/2处 2022-03-30 09:08 1136阅读 0赞

# 数据库期末复习 #

### 文章目录 ###

*  数据库期末复习
 *   *  2. 关系模式介绍
     *   *  2.1 关系数据库的结构
         *  2.2 数据库模式
         *  2.3 码（key）
         *  2.4 模式图
         *  2.6 关系运算
     *  3.SQL
     *   *  1. 数据类型：
         *  2. 建表结构：
         *  3. 指定主键
         *  4. 指定外码
         *  5. 删除表
         *  6. 删除表中内容
         *  7. 为现有关系添加属性
         *  8. 从现有关系中删去属性
         *  9. 单关系查询
         *  10. 多关系查询
         *  11. 自然连接(natural join)
         *  12. 更名运算
         *  13. 排列元组的显示次序
         *  14. where子句谓语
         *  15. 并运算
         *  16. 交运算
         *  17. 差语句
     *  3. 中级SQL
     *   *  1. 左外连接、右外连接、全外连接
         *  2. 连接条件（on）
         *  3. 视图
         *   *  1. 虚关系
             *  2. 视图的定义
             *  4. 在查询中使用视图
             *  5. 物化视图
             *  6. 视图更新
         *  2. 完整性约束
         *   *  1.not null 约束
             *  2. unique约束
             *  3. check约束
         *  3. 参照完整性
         *  4. 事务中对完整性约束的违反
         *  5.复杂check条件与断言
         *  6. SQL的数据类型与模式
         *   *  1.默认值
             *  2. 大对象类型
         *  7. 权限的授予与收回
     *  4. 数据库设计和E-R模型
     *   *  4.1 实体-联系模型（entity-relationship）
         *  4.2 实体集
         *  4.3 联系集
         *  4.4 属性
         *  4.5 约束
         *   *  4.5.1 映射基数
             *  4.5.2 参与约束
             *  4.5.3 码
         *  4.6 实体-联系图
         *   *  4.6.1 基本结构
             *  4.6.2 映射基数
             *  4.6.3 弱实体集
         *  4.7 转换为关系模式
         *   *  4.7.1 具有简单属性的强实体集的表示
             *  4.7.2 具有复杂属性的强实体集的表示
             *  4.7.3 弱实体集的表示
             *  4.7.4 联系集的表示
     *  5. 关系数据库
     *   *  5.1 原子域和第一范式
         *  5.2 码和函数依赖
         *  5.4 Boyce-Codd 范式（BCNF）
         *  5.5 第三范式(3NF)
         *  5.6 函数依赖理论
         *   *  5.6.1 函数依赖集的闭包
             *  5.6.2 属性集的闭包
             *  5.6.3 无损分解
             *  5.6.4 保持依赖
         *  5.7分解
         *   *  5.7.1 3NF分解
             *  5.7.2 BCNF分解算法
     *  6. 事务管理
     *   *  6.1 事务
         *  6.2 存储结构
         *  6.3 事务原子性和持久性
         *   *  6.3.1 抽象事务模型
         *  6.4 调度
         *   *  6.4.1 可串行化
         *  6.5 事务隔离性和原子性
         *   *  6.5.1 可恢复调度
             *  6.5.2 无级联调度
     *  7. 并发控制
     *   *  7.1 基于锁的协议
         *   *  7.1.1 锁
             *  7.1.2 两段锁协议

## 2. 关系模式介绍 ##

### 2.1 关系数据库的结构 ###

1.  关系数据库由表的集合构成，每个表有唯一的名字。
2.  在关系模型的术语中，**关系用来指代表， 而元组用来指代行。属性指代的是表的列。**
3.  关系实例（relation instance）指代的是一个关系的特定实例，也就是所包含的一组特定的行。
4.  对于表中的每个属性，都有一个允许取值的集合，称为该属性的**域（domain）**。
5.  表中所有属性的值都必须的原子的（即不可再分的）。
6.  每个域中都包含null（表示空的、不存在的）。
7.  关系：两个集合的笛卡尔积的任意子集叫做关系。

### 2.2 数据库模式 ###

1.  数据库模式：数据库的逻辑设计
2.  数据库实例：给定时刻数据库中数据的一个快照
3.  关系的概念对应编程语言中变量的概念，而关系模式对应编程语言中类型定义的概念。
4.   R = ( A 1 , A 2 , … , A n ) R = (A1, A2, …, An ) R=(A1,A2,…,An)\`就是一个关系模式，我们使用大写字母开头 的名字来代表**关系模式**如，**Instructor\_schema = (ID, name, dept\_name, salary)**，用小写字母开头的名字来代表**关系**，如 **instructor (Instructor \_schema)**

### 2.3 码（key） ###

1.  一个元组的属性值必须是能够唯一区分元组的。即一个关系中没有两个元组在所有属性的取值上相同。
2.  超码（superkey）是一个或多个属性的集合，这些属性的集合可以使我们在一个关系中唯一的标识一个元组。
3.  如果K是一个超码，那么K的任意超集也都是超码。
4.  如果K是一个超码，且它的任意真子集都不能称为超码，那么称K是候选码（candidate key）
5.  候选码可能有多个。
6.  **主码（primary key）代表被数据库设计者选中的，主要用来在一个关系中区分不同元组的候选码**。
7.  一个关系模式（如r1）可能在它的属性中包含另一个关系模式（r2）的主码。这个属性在r1上被称为参照r2的外码。
8.  参照完整性约束：要求在参照关系中任意元组在特定属性上的取值必然等于被参照关系中某个元组在特定属性上的取值。

### 2.4 模式图 ###

1.  一个含有主码和外码依赖的数据库模式可以用模式图（schema diagram）表示。

### 2.6 关系运算 ###

1.  最常用的关系运算是从单个关系（如instructor）中选出一些满足特定谓语（如salary>85000）的特殊元组，其结果是一个新关系，它是原始关系的一个子集。
2.  另一个常用的运算是从一个关系中选出特定的属性（列）。其结果是一个只包含那些被选择属性的新关系。
3.  连接运算可以通过一些方式把分别来自两个关系的元组对合并成单个元组。
4.  关系代数提供了一组运算，他们以一个或多个关系作为输入，返回一个关系作为输出。

## 3.SQL ##

### 1. 数据类型： ###

>  *  char(n)：固定长度的字符串，用户指定长度。
>  *  varchar(n)：可变长度的字符串，用户指定最大长度n。等价于全称character varying。
>  *  Int：整数类型。
>  *  smallInt：小整数类型。
>  *  numeric(p, d)：定点数，精度由用户指定。这个数有p位数字（加上一个符号位）。其中d位数字在小数点右边。
>  *  real, double precision：浮点数与双精度浮点数。
>  *  float(n)：精度至少为n位的浮点数。

### 2. 建表结构： ###

create table instructor(
        ID char(5),
        name varchar(20),
        dept_name varchar(20),
        salary numeric(8,2)
        primaey key (ID)
    );

### 3. 指定主键 ###

create table instructor(
        ID char(5) primary key,
        name varchar(20),
        dept_name varchar(20),
        salary numeric(8,2)
    );
    
    或
    
    create table instructor(
        ID char(5) constraint PK_1 primary key,
        name varchar(20),
        dept_name varchar(20),
        salary numeric(8,2)
        primaey key (ID)
    );
    
    主键如有多个属性值则
    
    create table instructor(
        ID char(5),
        name varchar(20),
        dept_name varchar(20),
        salary numeric(8,2)
        primaey key (ID, name, salary)
    );

### 4. 指定外码 ###

create table instructor(
        ID char(5),
        name varchar(20),
        dept_name varchar(20) references department,
        salary numeric(8,2)
    );
    
    或
    
    create table instructor(
        ID char(5),
        name varchar(20),
        dept_name varchar(20),
        salary numeric(8,2),
        foreign key(dept_name) references department
    );

### 5. 删除表 ###

//从数据库中删除一个关系，连数据库模式一并删除
    drop table instructor

### 6. 删除表中内容 ###

//仅删除表中内容
    delete from instructor

### 7. 为现有关系添加属性 ###

alter table instructor add varchar(20) address

关系中所有元组的新增属性的值都为null。

### 8. 从现有关系中删去属性 ###

alter instructor drop address

### 9. 单关系查询 ###

select name
    from instructor

**上面的代码即为从instructor中查询所有的name，有时候我们想要删掉重复，可加入关键词distinct，例如**

select distinct name
    from instructor

**select子句还可带有算术表达式，例如**

select ID, name, dept_name, salary*1.1
    from instructor

**上面这段代码会返回一个与insructor一样的关系，只是salary属性是原来的1.1倍，注意原关系并不发生改变。**

**where子句允许我们只需选出那些在from子句的结果关系中满足特定谓词的元组。例如**

select name
    from instructor
    where dept_name = 'Comp.Sci' and salary > 70000;
    **上面这段代码意为找出所有在Computer Science系并且工资超过70000的教师的名字。**

### 10. 多关系查询 ###

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

**上述代码的意图是“找出所有教师的姓名，以及他们所在系的名称和系所在建筑的名称。”**

**注：1、dept\_name属性既出现在instructor关系中，也出现在department中，关系名被用作前缀来说明我们是用的是哪个属性。2、尽管子句是以select,from,where的次序写出，但是实际运算的顺序是from,where,select。即先求出from选中的关系的笛卡尔积，这个笛卡尔积有大量无效的元组，然后where子句中的位于可用来限制笛卡尔积所建立的组合，最后输出select子句中指定的属性。**

### 11. 自然连接(natural join) ###

**自然连接运算作用于两个关系，并产生一个关系作为结果。自然连接只考虑那些在两个关系模式中都出现的属性上取值相同的元组对。所以对于查询“大学中所有讲授课程的教师，找出他们的姓名以及所讲述的所有课程标识”，我们可以这么写**

select name, course_id
    from instructor natural join teaches

**为了避免不必要的相等属性带来的危险，我们还可以使用自然连接的另一种构造形式**

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

**注：join…using…运算中需要给定一个属性名列表，其两个输入都必须具有指定名称的属性。（using用来指定需要相同的是哪个属性）**

### 12. 更名运算 ###

**我们并不总能直接使用属性名。原因在于首先，from子句中的两个关系可能存在同名的属性。其次，如果在select子句中使用了算术表达式，那么属性就没有名字。因此，我们可以使用old-name as new-name的语法来改变结果中属性的名字**

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

**重命名还可以把一个长的关系名替换成短的，这样在查询的其他地方使用时就会方便。例如**

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

**重命名的另一个重要原因是为了适用于需要比较同一个关系中元组的情况。为此我们需要把一个关系与他自身进行笛卡尔积运算，如果不重命名就不可能把一个元组与另一个区分开来。例如我们要查询“满足条件的所有教师的名字，他们的工资至少比Biology系的某一个教师的工资要高”**

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

**T、S准确的说是被声明为instructor的别名。在SQL标准中被称作相关名称(correlation name)，但也经常被称为表别名(table alias)，或相关变量(correlation variable)，或者 元组变量(tuple variable)**

### 13. 排列元组的显示次序 ###

**order by子句可以让查询结果按排列顺序显示，例如**

select name
    from instructor
    where dept_name = 'Physics'
    order by name;

**该段代码可以按字母序列出Physics系的所有教师名字。**

**order by语句默认使用升序，要使用降序可以用desc来表示，或者使用asc来明确是升序。假设我们想按salary的降序列出整个instructor关系，如果有工资相同的，则按姓名升序排列，则表示如下：**

select *
    from instructor
    order by salary desc, name asc;

### 14. where子句谓语 ###

**SQL提供betwenn比较运算符来说明一个值是小于或等于某个值，同时大于或等于某个值。如果我们想找出工资在90000美元和100000美元之间的教师的名字，可以这样写：**

select name
    from instructor
    where salary between 90000 and 100000;

**类似的也可以使用not between语法**

### 15. 并运算 ###

**为了找出在2009年秋季，或者在2010年春季开课或两个学期都开课的所有课程。代码如下：**

（select course_id
      from section
      where semester = 'Fall' and year = 2009
    ）
    union
    （select course_id
      from section
      where semester = 'Spring' and year = 2010
    ）;

**注：union运算自动去重。若想保留重复则用union all语句。**

### 16. 交运算 ###

**为了找出在2009年秋季和2010年春季同时开课的所有课程的集合。代码如下：**

（select course_id
      from section
      where semester = 'Fall' and year = 2009
    ）
    Intersect
    （select course_id
      from section
      where semester = 'Spring' and year = 2010
    ）;

**同样的若想保留重复，可以使用Intersect all语句。**

### 17. 差语句 ###

**为了找出在2009年秋季开课但没有在2010年春季开课的所有课程，代码如下：**

（select course_id
      from section
      where semester = 'Fall' and year = 2009
    ）
    except
    （select course_id
      from section
      where semester = 'Spring' and year = 2010
    ）;

**注：使用except all可以保留重复。**

## 3. 中级SQL ##

### 1. 左外连接、右外连接、全外连接 ###

### 2. 连接条件（on） ###

select *
    from student join takes on student.ID = takes.ID
    //与下面的查询相同
    
    select *
    from student, takes
    where student.ID = takes.ID

**与自然连接不同的是上述查询会导致ID出现两遍。**

### 3. 视图 ###

#### 1. 虚关系 ####

SQL允许通过查询来定义虚关系，它在概念上包含查询的结果。虚关系并不预先计算和存储。而是在使用虚关系的时候才执行查询被计算出来。

#### 2. 视图的定义 ####

使用**create view**命令来定义视图。

create view v as <查询表达式>

例如，

create view faculty as
    select ID,name,dept_name
    from instructor

还可以显式指定视图中的属性名

create view department_total_salary(dept_name, total_salary) as
    select dept_name. sum(salary)
    from instructor
    group by dept_name

#### 4. 在查询中使用视图 ####

例如

select dept_name
    from department_total_salary
    where total_salary > 10000;

#### 5. 物化视图 ####

特定数据库系统允许存储视图关系，但是它们保证：如果用于定义视图的实际关系改变，视图也跟着的修改。这样的视图称为**物化视图**。

保持物化视图一直在最新状态的过程称为**物化视图维护(materialized view maintainance)**。通常简称**视图维护**。

#### 6. 视图更新 ####

如果定义视图的查询满足下列条件，则称SQL视图是可更新的：

*  from子句中只有一个数据库关系
 *  select子句中只包含关系的属性名，不包含任何表达式、聚集或**distinct**声明。
 *  任何没有出现在select子句中的属性可以取空值，也就是这些属性没有not null约束，也不构成主码的一部分。
 *  查询中不包括group by和having子句。

### 2. 完整性约束 ###

完整性约束保证授权用户对数据库所做的修改不会破坏数据的一致性。因此，完整性约束防止的是对数据的意外破坏。

#### 1.not null 约束 ####

例如

name varchar(20) not null

#### 2. unique约束 ####

例如

unique(ID,dept_name)

unique声明指出了括号中的属性形成了一个候选码。即在关系中没有两个元组能在所有列出的属性上取值相同。然而 候选码的取值可以为空。因为空值不等于其他任何值。

#### 3. check约束 ####

通常用check子句来保证属性值满足指定的条件。例如，

create table section
    (
        course_id varchar(20),
        semester varchar(10),
        check(semester in ('Fall', 'Summer', 'Autumn', 'Winter'))
    );

### 3. 参照完整性 ###

我们往往希望保证在一个关系中给定属性集上的取值也在另一关系的特定属性集的取值中出现，这种情况称为参照完整性。

外码声明**foreign key(dept\_name) references department**表名在每个课程元组中指定的系名必须在department关系中存在。没有这个约束，就会为一门课程指定了一个不存在的系名。

这种要求称为**参照完整性约束(referential-intergrity constraint)或子集依赖(subset dependency)。**

当违反参照完整性约束时，通常的处理是拒绝执行导致完整性破坏的操作。但是，在foreign key子句中可以致命如果被参照关系上的删除或更新动作违反了约束，那么系统必须采取一些步骤通过修改参照关系中的元组来恢复完整性约束。例如，**on delete cascade 或 on update cascade**。

这种情况下如果删除了department中的元组导致了此参照的完整性约束被违反，则该删除不被系统拒绝，而是做级联的删除操作。即删除参照了被删除关系中的元组。

### 4. 事务中对完整性约束的违反 ###

可能会在事务处理的中间步骤违反了完整性约束，而事务结束后没有违反。为了处理这样的情况，SQL标准允许将initially deferred 子句加入到约束声明中。这样的话完整性约束不是在事务的中间步骤上检查，而是在事务结束时检查。

### 5.复杂check条件与断言 ###

check子句中的谓语可以是包含子查询的任意谓词，例如，在关系section上声明如下所示的参照完整性约束

check(time_slot_id in (select time_slot_id from time_slot))))

这个check条件检测，检查在section关系中每个元组的time\_slot\_id的确是在time\_slot关系中的。

### 6. SQL的数据类型与模式 ###

#### 1.默认值 ####

SQL允许为属性指定默认值，例如

create table student
    (
        ID varchar(5),
        name varchar(20) not null,
        dept_name varchar(20) default 'normal'，
        primary key(ID)
    );

#### 2. 大对象类型 ####

SQL提供字符数据的大对象数据类型（clob）和二进制数据的大对象数据类型blob。lob代表（Large Object）。例如

book_review clob (10KB)
    image blob (10MB)
    movie blob (2GB)

### 7. 权限的授予与收回 ###

SQL标准包括select、insert、update和delete权限。所有权限(all privileges)可以作为所有允许权限的简写形式。语句的基本形式如下

grant <权限列表>
    on <关系名或视图名>
    to <用户/用户列表>

授予查询权限：

grant select on department to User

权限列表后可以接属性名，意思是为该关系中的这些属性授予相应权限。例如

grant update (budget) on department to User

**意思是授予用户User在department关系的budget属性上的更新权限。**

我们使用revoke语句来收回用户权限，形式与grant一致。

## 4. 数据库设计和E-R模型 ##

### 4.1 实体-联系模型（entity-relationship） ###

E-R模型在将显示世界实体的含义和和交互映射到概念模式上非常有效，因此，许多数据库设计工具都利用了E-R模型的概念。E-R数据模型采用了三个基本概念：**实体集、联系集和属性**

### 4.2 实体集 ###

**实体**是现实世界中可区别与所有其他对象的一个“事物”或“对象”。例如，大学中每一个人都是一个实体。**每个实体有一组性质**，其中的一些性质课以唯一的标识一个实体。例如身份证号可以唯一的标识一个人。

**实体集（entity set）** 是相同类型即具有相同性质或属性的一个实体集合。例如，一所大学的所有老师的集合可定义为实体集。

**实体**通过一组**属性**来表示。属性是实体集中每个成员所拥有的描述性性质。为某实体集指定一个属性表名数据库为该实体集中每个实体存储相似的信息，但每个实体在每个属性上都有各自不同的值。

**因此，数据库包含一组实体集，每个实体集包括任意数量的相同类型的实体。**

### 4.3 联系集 ###

**联系（relation）** 是指多个实体间的相互关联。例如，我们可以定义关联某个老师和某个学生的联系advisor，这一关系表面该名老师是该名学生的导师。

**联系集（relationship set）** 是相同类型联系的集合。正规的说，联系集是 n ≥ 2 n≥2 n≥2`个实体集上的数学关系。如果$E_1,E_2,...,E_n$`为实体集，那么联系集R是，

|(e_1,e_2,...,e_n)|e_1∈E_1, e_2∈E_2,..,e_n∈E_n|

的一个子集。而 ( e 1 , e 2 , . . . , e n ) (e\_1,e\_2,...,e\_n) (e1,e2,...,en)\`是一个联系。

**实体集**之间的关联称为参与。也就是说，实体集 E 1 , E 2 , . . . , E n E\_1,E\_2,...,E\_n E1,E2,...,En\`**参与（participate）联系集R**。E-R模型中的一个联系实例（relationship instance）表示在所建模的现实世界中命名实体间的一个关联。

**实体在联系中扮演的功能称为实体的角色（role）**。参与一个联系集的实体集通常是互异的，因此角色是隐含的并且一般并不指定。但是，当联系的含义需要解释时角色是很有用的。当参与联系集的实体集**并非互异**的时候就是这种情况。**也就是说，同样的实体集以不同的角色参与一个联系节多于一次。** 在这类联系集中，即称为\*\*自环（recursive）\*\*的联系集中有必要用显式的角色名来指明实体是如何参与联系实体的。例如，一门课是另一门课的先修课。

**联系也可以具有描述性属性（descriptive attribute）**，例如导师跟学生之间的实体集advisor，我们可以将属性date与该联系关联起来。

给定的**联系集**中的一个联系实例必须是**由其参与实体唯一标识**的。

**参与到联系集的实体的数目称为联系集的度（degree）**。二元联系集的度为2，三元联系集的度为3。

### 4.4 属性 ###

每个属性都有一个可取值的范围，称为**属性的域（domain），或者值集(value set)**。

E-R模型中的属性可以按照如下的属性类型来进行划分：

*  **简单（simple）和复合（composite）属性**：简单属性就是不能划分为更小部分的属性。复合属性则可以再分。
 *  **单值（single-value）和多值（multivalued）** 属性：  
    单值属性就是一个属性对一个特定实体只有单独的一个值。例如身份证号。多值属性就是指一个属性可以对应多个值。例如，手机号。
 *  派生(derived)属性：这类属性可以从别的相关属性或实体派生出来。例如人的年龄，可以从生日计算得来。

### 4.5 约束 ###

#### 4.5.1 映射基数 ####

**映射基数(mapping cardinality)**，或基数比率，**表示一个实体通过一个联系集能关联的实体的个数。**

映射基数在描述二元联系集时非常有用，尽管他们可以用于描述设计多于两个实体集的联系集。

对于实体集A和B之间的二元联系集R来说，映射基数必然是以下情况之一：

*  一对一（one to one）：A中的一个实体至多与B中的一个实体相关联，并且B中的一个实体也至多与A中的一个实体相关联。
 *  一对多（one to many）：A中的一个实体可以与B中任意数目的实体相关联，而B中的一个实体至多与A中的一个实体相关联。
 *  多对一（many to one）：A中的一个实体至多与B中的一个实体相关联，而B中的一个实体可以与A中任意数目实体相关联。
 *  多对多（many to many）：A中的一个实体可以与B中任意数目实体相关联，而且B中的一个实体也可以与A中任意数目实体相关联。

#### 4.5.2 参与约束 ####

如果实体集E中的每个实体都参与到联系集R的至少一个联系中，实体集E在联系R中的参与称为\*\*全部（total）**的。如果E中只有部分实体参与到R的联系中，实体集E到联系集R的参与称为**部分（partial）\*\*的。

#### 4.5.3 码 ####

联系集的主码结构依赖于联系集的映射基数。若果联系集是多对多的，那么联系集的主码由参与联系集的实体集的主码的并集组成。

### 4.6 实体-联系图 ###

#### 4.6.1 基本结构 ####

*  分成两部分的矩形代表实体集
 *  菱形代表联系集
 *  线段将实体集连接到联系集
 *  虚线将联系集属性；连接到联系集
 *  双线显示实体在联系集中的参与度（双线是全部参与）
 *  双菱形代表连接到弱实体集的标志性联系集

![image][]

#### 4.6.2 映射基数 ####

实体集之间的联系集可以是一对一，一对多，多对一，多对多的。

*  一对一：联系集向两个实体集各画一个箭头

![image][image 1]

*  一对多：从联系集advisor画一个箭头到实体集instructor，以及一条线段到实体集student。

![image][image 2]

*  多对多：从联系集advisor向实体集instructor和student各画一条线段。

![image][image 3]

实体集和二元联系集之间的一条边可以有一个关联的最大和最小映射基数，用L…h的形式表示，其中l表示最小的映射基数，而h表示最大的映射基数。如下图，

![image][image 4]

**0…\*表示教师可以有零个或多个学生，而1…1表示每个学生必须有且仅有一个导师。**

#### 4.6.3 弱实体集 ####

没有足够的属性以性成主码的实体集称为**弱实体集**称作弱实体集（week entity set）。有主码的实体集称作**强实体集**。

弱实体集必须与另一个称作标识（identitying）或属主实体集（owner entity set）的实体集关联才能有意义。也就是说，**弱实体集存在依赖（existence dependent）于标识实体集。我们称标识实体集拥有（own）它所标识的弱实体集。将弱实体集与其标识实体集相联的联系称为标识性联系（identitying relationship）**。

\*\*标识性联系是从弱实体集到标识实体集多对一的，并且弱实体集在联系集在联系中的参与是全部的。\*\*标识性联系集不应该有任何描述性联系。

虽然弱实体集没有主码，但是我们仍需要区分依赖于特定强实体集的弱实体集中的实体的方法。弱实体集的分辨符（discriminator）是是的我们进行这种区分的属性集合。**弱实体集的分辨符也称为该实体集的部分码。**

![image][image 5]

### 4.7 转换为关系模式 ###

#### 4.7.1 具有简单属性的强实体集的表示 ####

设E是值具有简单描述性属性 a 1 , a 2 , . . . , a n a\_1,a\_2,...,a\_n a1,a2,...,an\`的强实体集。我们用具有n个不同属性的模式E来表示这个实体集。该模式的关系中的每个元组通实体集E的一个实体相对应。

对于从强实体集转换而来的模式，强实体集的主码就是生成的模式的主码。

#### 4.7.2 具有复杂属性的强实体集的表示 ####

通过为每个子属性创建一个单独的属性来处理复合属性（并不为复合属性自身创建一个单独的属性）。例如对于复合属性地址，它包含省份，城市等子属性。在转化为关系模式的时候，把这些子属性都拆分出来。

#### 4.7.3 弱实体集的表示 ####

对于从弱实体集转换而来的模式，该模式的主码由其所依赖的强实体集的主码和弱实体集的分辨符组合而成。

#### 4.7.4 联系集的表示 ####

设R是联系集，那么R的属性是所有参与R的实体集的主码跟R的描述性属性的并集。

## 5. 关系数据库 ##

### 5.1 原子域和第一范式 ###

在关系模型中，我们将属性不具有任何子结构这个思想形式化。如果一个域的元素被认为是不可分的单元，那么这个域是原子的。**如果一个关系模式R的所有域都是原子的，我们就称关系模式R属于第一范式（1NF）。**

### 5.2 码和函数依赖 ###

设R(U)是属性集U上的关系模式，X、Y是U的子集。**若对R(U)的任一关系r，r中不可能存在两个元组在X上的属性相同，而在Y上的属性不同。那么就称Y函数依赖于X（或X决定Y），记作 X → Y X\\rightarrow\{Y\} X→Y\`。**

使用函数依赖这一概念，我们说如果函数依赖 X → Y X\\rightarrow\{Y\} X→Y\`在R(U)上成立，则X是R(U)的一个超码。

### 5.4 Boyce-Codd 范式（BCNF） ###

BCNF消除了所有基于函数依赖所能够发现的冗余。具有函数依赖集F的关系模式R属于BCNF的条件是，对 F + F^+ F\+`中所有形如$α\rightarrow{β}$`的函数依赖，下面一项至少成立：

*   α → β α\\rightarrow\{β\} α→β\`是平凡的函数依赖
 *  α是模式R的一个超码

**一个数据库设计属于BCNF的条件是，构成该设计的关系模式集中的每个模式都属于BCNF**

### 5.5 第三范式(3NF) ###

具有函数依赖集F的关系模式R属于第三范式的条件是：对 F + F^+ F\+`中所有形如$α\rightarrow{β}$`的函数依赖，下面一项至少成立：

*   α → β α\\rightarrow\{β\} α→β\`是一个平凡的函数依赖
 *  α是R的一个超码
 *   β − α β-α β−α\`中的每个属性A都包含于R的一个候选码内

**注意第三个条件并没有说单个候选码必须包含 β − α β-α β−α`中的所有属性，$β-α$`中的每个属性A课能包含于不同的候选码中。**

### 5.6 函数依赖理论 ###

#### 5.6.1 函数依赖集的闭包 ####

**给定关系模式r®，如果r®的每一个满足F的实例也满足f，则R上的函数依赖f被r上的函数依赖集F逻辑蕴含(logically imply)**

我们可以使用以下三条规则去寻找逻辑蕴含的函数依赖。通过反复应用这些规则，可以找出给定F的全部 F + F^+ F\+\`。这组规则称为**Armstrong公理**：

*  自反律：若α为一属性集且 β ∈ α β∈α β∈α`，则$α\rightarrow{β}$`成立
 *  增补率：若 α → β α\\rightarrow\{β\} α→β`成立且y为一属性集，则$yα\rightarrow{yβ}$`成立
 *  传递率：若 α → β α\\rightarrow\{β\} α→β`和$β\rightarrow{y}$`成立,则 α → y α\\rightarrow\{y\} α→y\`成立

#### 5.6.2 属性集的闭包 ####

如果 α → B α\\rightarrow\{B\} α→B`，我们称属性B被α**函数确定（functionally determine）**。令α为一个属性集，我们将函数依赖集F下被α函数确定的所有属性的集合称为F下的**闭包。**，记为$a^+$`。

#### 5.6.3 无损分解 ####

如果我们把r投影至R1和R2上，然后计算投影结果的自然连接，我们仍然得到一模一样的r，这就是无损分解。

我们可以用函数依赖来说明什么情况下分解是无损的。令R、R1、R2和F。R1和R2是R的无损分解，如果以下函数依赖至少有一个属于 F + F^+ F\+\`：

*   R 1 ∩ R 2 → R 1 R1 ∩ R2 \\rightarrow\{R1\} R1∩R2→R1\`
 *   R 1 ∩ R 2 → R 2 R1 ∩ R2 \\rightarrow\{R2\} R1∩R2→R2\`

\*\*换句话说，如果 R 1 ∩ R 2 R1 ∩ R2 R1∩R2\`\*\*是R1或R2的超码，R上的分解就是无损分解。

#### 5.6.4 保持依赖 ####

分解关系模式R后，得到关系模式R1,R2,…,Rn

把 F + F^+ F\+\`中只包含R1属性的函数依赖子集合记为F1。

把 F + F^+ F\+\`中只包含R2属性的函数依赖子集合记为F2。

把 F + F^+ F\+\`中只包含Rn属性的函数依赖子集合记为Fn。

**如果 F 1 ∪ F 2 ∪ . . . ∪ F n F1∪F2∪...∪Fn F1∪F2∪...∪Fn\`和F是等价的，那么称这个分解是保持函数依赖的（dependency preserving）**。

### 5.7分解 ###

#### 5.7.1 3NF分解 ####

1.  先求出F的最小覆盖Fc
2.  为Fc的每个函数依赖 α → β α\\rightarrow\{β\} α→β`生成一个新的关系模式$α∪β$`
3.  如果生成的每个关系模式都不包含R的候选码，就选择R的任意一个候选码A，生成一个新的关系模式A。
4.  检查生成的关系模式，如果 R 1 ∈ R 2 R1∈R2 R1∈R2\`，就把R1删掉。

#### 5.7.2 BCNF分解算法 ####

BCNF分解算法。假设关系模式R有一个非平凡函数依赖 α → β α\\rightarrow\{β\} α→β\`,α不是超码。

我们可以把R分解为一下两个关系模式：

*   α ∪ β α∪β α∪β\`
 *  R-β

如果分解后的两个关系模式还不是BCNF，就继续分解下去。

## 6. 事务管理 ##

### 6.1 事务 ###

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

这些步骤集合（事务）必须作为一个单一的、不可分割的单元出现。因为事务是**不可分割**的，所以要么执行其全部内容 ，要么就根本不执行。这种“全或无”的特性被称为**原子性（atomicity）**。

数据库系统应维护事务的以下性质：

*  原子性（atomicity）：事务的所有操作在数据库中要么全部正确反映出来，要么完全不反应。
 *  一致性（consistency）：隔离执行事务时（换言之，在没有其他事务并发执行的情况下）保持数据库的一致性。即数据不会凭空消失或产生。
 *  隔离性（isolation）：尽管多个事务可能并发执行。但系统保证，对于任一对事务Ti和Tj，在Ti看来，Tj或在Ti开始之前已经完成执行，或者在Ti完成之后开始执行。\*\*也就是说，每个事务都感觉不到系统中有其他事务在并发的执行。\*\*确保并发执行后的系统状态与事务以某种次序串行后的状态是等价的。
 *  持久性：一个事务成功完成之后，它对数据库的变动是永久的，即使出现系统故障。

### 6.2 存储结构 ###

*  易失性存储器（volatile storage）：易失性存储器中的信息通常在系统崩溃后不会幸存
 *  非易失性存储器（nonvolatile storage）：非易失性存储器中的信息会在系统崩溃后幸存。
 *  稳定性存储器（stable storage）：稳定性存储器中的信息永远不会丢失。（理想化存储器）。可以通过近似使得数据  
    丢失的可能性微乎其微。

**为了一个事务能持久，它的修改应该被写入稳定性存储器。同样为了一个事务是原子的，日志记录需要在对磁盘上的数据库做任何改变之前写入稳定性存储器。**

### 6.3 事务原子性和持久性 ###

事务若没能成功地执行完成，这种事务称为**中止（abort）** 了。如果要确保原子性，中止事务必须对数据库的状态不造成影响。因此，**中止事务对数据库所做过的任何改变都必须撤销。一旦中止事务造成的改变被撤销，则说这个事务被回滚**了

成功完成执行的事务称为**已提交（commited）**。一个对数据库进行过更新的已提交事务使数据库进入一个新的一致状态。

**一旦事务已提交，我们不能通过中止它来撤销其造成的影响，唯一方法是执行一个补偿事务（compensate transaction）**

#### 6.3.1 抽象事务模型 ####

事务必须处于以下状态之一：

*  活动的（active）：初始状态，事务执行时处于这个状态。
 *  部分提交的（partially commited）：最后一条语句执行后
 *  失败的（failed）：发现正常的执行不能继续后
 *  中止的（aborted）：事务回滚并且数据库已恢复到事务开始执行前的状态。
 *  提交的（commited）：成功完成后

![image][image 6]

**仅当事务已进入中止状态，我们才说事务已中止。如果事务是提交的或中止的，它称为已经结束的（terminated）。**

### 6.4 调度 ###

一组事务的一个调度必须包含这一组事务的全部指令，并且必须保持指令在各个事务中出现的顺序。

在并发执行中，通过保证所执行的任何调度的效果都与没有并发执行的调度一样，我们可以确保数据库的一致性。**也就是说，调度应该在某种意义上等价于一个串行调度。这种调度称为可串行化。**

#### 6.4.1 可串行化 ####

**冲突可串行化：** 考虑一个调度S，其中含有分别属于I与J的两条连续指令Ii和Ij。若果I与J引用不同的数据项，则交换I与J不会影响调度中任何指令的结果。由于我们只处理read和write指令，因此需要考虑以下四种情况：  
![image][image 7]

**因此，只有在I与J全为read指令时，两条指令的执行顺序才是无关紧要的。**

**当I与J是不同事务在相同的数据项上的操作，并且其中至少有一个是write指令是，我们说I与J是冲突的（conflict）**

**设I与J是调度S的两条连续指令。若I与J是属于不同事务的指令且不冲突，则可以交换I与J的顺序得到一个新的调度S’。S与S’等价。**

**如果调度S可以经过一系列非冲突指令交换转换成S’，我们称S与S’是冲突等价的。**

为了确定一个调度是否**冲突可串行化**，可以构造一个有向图，称为优先图（precedence graph）。顶点集由所有参与调度的事务组成，边集由满足下列三个条件之一的边 T i → T j T\_i\\rightarrow\{T\_j\} Ti→Tj\`组成：  
![image][image 8]

**如果优先图中存在边 T i → T j T\_i\\rightarrow\{T\_j\} Ti→Tj`，则在任何等价于S的串行调度S'中，$T_j$`必出现在 T j T\_j Tj\`之前。**

**如果调度S的优先图有环，则调度S是非冲突可串行化的，若无环，则调度S是冲突可串行化的。**

### 6.5 事务隔离性和原子性 ###

不论什么原因，如果事务Ti失败了，我们必须撤销该事务的影响以确保其原子性。**原子性要求依赖Ti的任何事务Tj（即Tj读取了Ti写的数据）也中止。**

#### 6.5.1 可恢复调度 ####

一个**可恢复调度（recoverable schedule）** 应满足：对于每对事务 T i T\_i Ti`和$T_j$`，如果 T j T\_j Tj`读取了之前由$T_i$`所写的数据项，则 T i T\_i Ti`应先于$T_j$`提交。  
一个不可恢复的例子：

![image][image 9]

#### 6.5.2 无级联调度 ####

级联回滚导致撤销大量工作，我们希望对调度加以限制，避免级联回滚发生。这样的调度称为**无级联调度**。

规范的说，无级联调度（cascadeless schedule）应满足：对于每对事务 T i T\_i Ti`和$T_j$`，如果 T j T\_j Tj`读取了先前由$T_i$`所写的数据项，则 T i T\_i Ti\`必须在这一**读操作**之前提交。

**易知，每一个无级联调度也都是可恢复的调度。**

## 7. 并发控制 ##

### 7.1 基于锁的协议 ###

#### 7.1.1 锁 ####

锁分两种：

*  共享的（shared）：如果事务 T i T\_i Ti`获得了数据项Q上的共享型（shared-mode-lock）（记为S），**则$T_i$`可读但不可写Q。\*\*
 *  排他的（exclusive）：如果事务 T i T\_i Ti`获得了数据项Q上的排他型锁（exclusive-mode-lock）（记为X），**则$T_i$`可写又可读Q。\*\*

假设事务 T i T\_i Ti`请求对数据项Q加A类型锁，而事务$T_j$`当前在数据项Q上拥有B类型锁。尽管数据项Q上存在B类型锁，如果事务 T i T\_i Ti\`可以立即获得数据项Q上的锁，则我们就说A类型锁和B类型锁是相容的。

**一个具体的数据项上可同时有（被不同的事务持有的）多个共享锁。此后的排他锁请求必须一直等待直到该数据项上的所有共享锁被释放。（只要事务还在访问数据项，它就必须拥有该数据项上的锁）**

#### 7.1.2 两段锁协议 ####

该协议要求每个事务分两个阶段提出加锁和解锁申请：

1.  增长阶段（growing phase）：事务可以获得锁，但不能释放锁。
2.  缩减阶段（shrinking phase）：事务可以释放锁，但不能获得新锁。

**起初，事务处于增长阶段，事务根据需求获得锁。一旦该事务释放了锁，它就进入了缩减阶段。**

**在调度中，该事务获得其最后加锁的位置（增长阶段结束点）称为事务的封锁点（lock point）。**

为了避免级联回滚，可以把协议修改为**严格两阶段封锁协议（strict two-phase locking protocol），还要求事务持有的所有排他锁必须在事务提交后方可释放。**

一种自动为事务产生合适的加锁、解锁指令的机制：  
![image][image 10]

[image]: https://note.youdao.com/yws/res/3735/5FBE1740B2D6443E850025240F56DD1B
[image 1]: https://note.youdao.com/yws/res/3745/D718E79AFD5B4616BD6FC166C3AD3C36
[image 2]: https://note.youdao.com/yws/res/3750/6F90D2A28ACD4E518271803F72F4972D
[image 3]: https://note.youdao.com/yws/res/3753/1759979BDF6C42C0AC13C3789BA93C2A
[image 4]: https://note.youdao.com/yws/res/3758/CAEE49F6BB6D481AA157C09FAF225F0D
[image 5]: https://note.youdao.com/yws/res/3789/3D1360C642D34B5FA1571036B1FEAFA7
[image 6]: https://note.youdao.com/yws/res/3950/FC0E02676E024AA5A99F8BEE9B1CA2D3
[image 7]: https://note.youdao.com/yws/res/3967/622F55CFC1944E5C94370A42033E716C
[image 8]: https://note.youdao.com/yws/res/3973/9C0492F654704430BD8F1EEE2BB49A6C
[image 9]: https://note.youdao.com/yws/res/3972/F54EDBEC24E04D7895F9450ABCDB52F3
[image 10]: https://note.youdao.com/yws/res/3971/D495A7DCC75F427DB8E411A98295BC71