数据库系统

数据是数据库中存储的基本对象，是描述事物的符号记录。数据的种类包括文本、图形、图像、音频、视频、学生的档案记录、货物的运输情况等。

数据库（DB）是长期存储在计算机内、有组织的、可共享的大量数据的集合。数据库的基本特征包括数据按一定的数据模型组织、描述和存储；可为各种用户共享；冗余度较小；数据独立性较高；易扩展。

数据库系统（DBS）是一个采用了数据库技术，有组织地、动态地存储大量相关数据，方便多用户访问的计算机系统。其由下面四个部分组成：

• 数据库：统一管理、长期存储在计算机内的，有组织的相关数据的集合；
• 硬件：构成计算机系统包括存储数据所需的外部设备；
• 软件：操作系统、数据库管理系统及应用程序；
• 人员：系统分析和数据库设计人员、应用程序员、最终用户、数据库管理员DBA。

数据库管理系统（DBMS）的功能包括：实现对共享数据有效的组织、管理和存取；包括数据定义、数据库操作、数据库运行管理、数据的存储管理、数据库的建立和维护等。

DBMS的分类：关系数据库系统RDBS、面向对象的数据库系统OODBS、对象关系数据库系统ORDBS。

数据库系统的体系结构：集中式数据库系统（所有东西集中在DBMS电脑上)、客户端/服务器体系结构（客户端负责请求和数据表示，服务器负责数据库服务）、并行数据库系统（多个物理上在一起的CPU）、分布式数据库系统（物理上分布在不同地方的计算机）。

三级模式——两级映像

• 内模式：管理如何存储物理的数据，对应具体物理存储文件。
• 模式：又称为概念模式，就是我们通常使用的基本表，根据应用、需求将物理数据划分成一张张表。
• 外模式：对应数据库中的视图这个级别，将表进行一定的处理后再提供给用户使用。
• 外模式一模式映像：是表和视图之间的映射，存在于概念级和外部级之间，若表中数据发生了修改，只需要修改此映射，而无需修改应用程序。
• 模式一内模式映像：是表和数据的物理存储之间的映射，存在于概念级和内部级之间，若修改了数据存储方式，只需要修改此映射，而不需要去修改应用程序。

以上的数据库系统实际上是一个分层次的设计，从底至上称为物理级数据库（实际为一个数据库文件）、概念级数据库、用户级数据库，各层情况如下：

数据库设计

需求分析：即分析数据存储的要求，产出物有数据流图、数据字典、需求说明书。

概念结构设计：就是设计E-R图，也即实体-联系图，与物理实现无关，说明有哪些实体，实体有哪些属性。

逻辑结构设计：将E-R图，转换成关系模式，也即转换成实际的表和表中的列属性，这里要考虑很多规范化的东西。

物理设计：根据生成的表等概念，生成物理数据库。

E-R模型

数据模型三要素：数据结构（所研究的对象类型的集合）、数据操作（对数据库中各种对象的实例允许执行的操作的集合）、数据的约束条件（一组完整性规则的集合）。

用E-R图来描述概念数据模型，世界是由一组称作实体的基本对象和这些对象之间的联系构成的。在E-R模型中，使用椭圆表示属性（一般没有）、长方形表示实体、菱形表示联系，联系的两端要填写联系类型，示例如下图：

各概念如下：

• 实体：客观存在并可相互区别的事物。可以是具体的人、事、物或抽象概念。如人、汽车、图书、账户、贷款。
• 弱实体和强实体：弱实体依赖于强实体的存在而存在。
• 实体集：具有相同类型和共享相同属性的实体的集合，如学生、课程。
• 属性：实体所具有的特性。
• 属性分类：简单属性和复合属性；单值属性和多值属性；NULL属性；派生属性。
• 域：属性的取值范围称为该属性的域。
• 码（key）：唯一标识实体的属性集。
• 联系：现实世界中事物内部以及事物之间的联系，在E-R图中反映为实体内部的联系和实体之间的联系。

联系类型：一对一1：1、一对多1：N、多对多M：N。

属性分类：简单属性和复合属性（属性是否可以分割）、单值属性和多值属性（属性有多个取值）、NULL属性（无意义）、派生属性（可由其他属性生成）。

关系模型中数据的逻辑结构是一张二维表，由行列组成。用表格结构表达实体集，用外键标识实体间的联系。

优点：建立在严格的数学概念基础上；概念单一、结构简单、清晰，用户易懂易用；存取路径对用户透明，从而数据独立性、安全性好，简化数据库开发工作。

缺点：由于存取路径透明，查询效率往往不如非关系数据模型。

那么E-R模型如何转换为关系模型呢(实际就是转换为多少张表）?

每个实体都对应一个关系模式；

联系分为三种：1:1联系中，联系可以放到任意的两端实体中，作为一个属性(要保证1:1的两端关联)；1:N的联系中，联系可以单独作为一个关系模式，也可以在N端中加入1端实体的主键；M:N的联系中，联系必须作为一个单独的关系模式，其主键是M和N端的联合主键。明确了有多少关系模式，就知道有多少张表，同时，表中的属性也确定了，注意联系是作为表还是属性，若是属性又是哪张表的属性即可。

关系代数

关系模式在代数运算时可以理解为数据库中的表，两个概念通用。

并：结果是两张表中所有记录数合并，相同记录只显示一次。

交：结果是两张表中相同的记录。

差：S1-S2，结果是S1表中有而S2表中没有的那些记录。

笛卡尔积：S1*S2，产生的结果包括S1和S2的所有属性列，并且S1中每条记录依次和S2中所有记录组合成一条记录，最终属性列为S1+S2属性列，记录数为S1*S2记录数。

投影：实际是按条件选择某关系模式中的某列，列也可以用数字表示。

选择：实际是按条件选择某关系模式中的某条记录。

自然连接的结果显示全部的属性列，但是相同属性列只显示一次，显示两个关系模式中属性相同且值相同的记录。

效率问题：关系代数运算的效率，归根结底是看参与运算的两张表格的属性列数和记录数，属性列和记录数越少，参与运算的次数自然越少，效率就越高。因此，效率高的运算一般都是在两张表格参与运算之前就将条件判断完。

关系数据库的规范化

函数依赖

给定一个x，能唯一确定一个Y，就称X确定Y，或者说Y依赖于x，例如Y=x*x函数。函数依赖又可扩展以下两种规则：

• 部分函数依赖：A可确定C，（A,B）也可确定C，（A,B）中的一部分（即A）可以确定C，称为部分函数依赖。
• 传递函数依赖：当A和B不等价时，A可确定B，B可确定C，则A可确定C，是传递函数依赖；若A和B等价，则不存在传递，直接就可确定C。

函数依赖的公理系统（Armstrong）

设关系模式R<U，F>，U是关系模式R的属性全集，F是关系模式R的一个函数依赖集。对于R<U，F>来说有以下的：

自反律：若Y⊆X⊆U，则X→Y在 R 上成立。

增广律：若X→Y在 R 上成立，且Z⊆U，则XZ→YZ在 R 上成立

传递律：若X→Y和Y→Z在 R 上成立，则X→Z在 R 上成立

合并规则：若X→Y，X→Z，则X→YZ在 R 上成立

伪传递率：若X→Y，WY→Z，则XW→Z在 R 上成立

分解规则：若X→Y，Z⊆Y，则X→Z在 R 上成立

键与约束

超键：能唯一标识此表的属性的组合。

候选键：超键中去掉冗余的属性，剩余的属性就是候选键。

主键：任选一个候选键，即可作为主键。

外键：其他表中的主键。

候选键的求法：根据依赖集画出有向图，从入度为0的节点开始，找出图中一个节点或者一个节点组合，能够遍历完整个图，就是候选键。

主属性：候选键内的属性为主属性，其他属性为非主属性。

实体完整性约束：即主键约束，主键值不能为空，也不能重复。

参照完整性约束：即外键约束，外键必须是其他表中已经存在的主键的值，或者为空。

用户自定义完整性约束：自定义表达式约束，如设定年龄属性的值必须在0到150之间。

触发器：通过写脚本来规定复杂的约束。本质属于用户自定义完整性约束。

范式

范式总体如下：

第一范式1NF

关系中的每一个分量必须是一个不可分的数据项。通俗地说，第一范式就是表中不允许有小表的存在。

1NF可能存在的问题：1NF是最低一级的范式，范式程度不高，存在很多的问题。比如用一个单一的关系模式学生来描述学校的教务系统：学生(学号，学生姓名，系号，系主任姓名，课程号，成绩）。

这个表满足第一范式，但是存在如下问题：

数据冗余：一个系有很多的学生，同一个系的学生的系主任是相同的，所以系主任名会重复出现。

更新复杂：当一个系换了一个系主任后，对应的这个表必须修改与该系学生有关的每个元组。

插入异常：如果一个系刚成立，没有任何学生，那么这个无法把这个系的信息插入表中。

删除异常：如果一个系的学生都毕业了，那么在删除该系学生信息时，这个系的信息也丢了。

第二范式2NF

如果关系R属于1NF，且每一个非主属性完全函数依赖于任何一个候选码，则R属于2NF。通俗地说，2NF就是在1NF的基础上，表中的每一个非主属性不会依赖复合主键中的某一个列。

按照定义，上面的学生表就不满足2NF，因为学号不能完全确定课程号和成绩（每个学生可以选多门课）。将学生表分解为：学生(学号，学生姓名，系编号，系名，系主任）、选课(学号，课程号，成绩），每张表均属于2NF。

学生表

选课表

第三范式3NF

在满足2NF的基础上，表中不存在非主属性对码的传递依赖。继续上面的实例，学生关系模式就不属于3NF，因为学生无法直接决定系主任和系名，是由学号->系编号，再由系编号->系主任，系编号->系名，因此存在非主属性对主属性的传递依赖，将学生表进一步分解为：学生(学号，学生姓名，系编号）、系（系编号，系名，系主任)、选课(学号，课程号，成绩），每张表都属于3NF。

学生表

系表

选课表

BC范式BCNF

是指在第三范式的基础上进一步消除主属性对于码的部分函数依赖和传递依赖。通俗的来说，就是在每一种情况下，每一个依赖的左边决定因素都必然包含候选键，

上图中，候选键有两种情况：组合键（S,T）或者（S,J），依赖集为{SJ—T，T—J}，可知，STJ三个属性都是主属性，因此其达到了3NF（无非主属性），然而，第二种情况，即（S，J）为候选键的时候，对于依赖T->J，T在这种情况不是候选键，即T-J的决定因素不包含任意候选码，因此上图不是BCNF。要使上图关系模式转换为BCNF也很简单，只需要将依赖T->J变为TS->J即可，这样其左边决定因素就包含了候选键之一S。

模式分解

范式之间的转换一般都是通过拆分属性，即模式分解，将具有部分函数依赖和传递依赖的属性分离出来，来达到一步步优化，一般分为以下两种：

保持函数依赖分解

对于关系模式R，有依赖集F，若对R进行分解，分解出来的多个关系模式，保持原来的依赖集不变，则为保持函数依赖的分解。另外，注意要消除掉冗余依赖（如传递依赖）。

实例：设原关系模式R（A,B,C），依赖集F（A->B,B->C,A->C）,将其分解为两个关系模式R1（A,B）和R2（B,C），此时R1中保持依赖A->B,R2保持依赖B->C，说明分解后的R1和R2是保持函数依赖的分解，因为A->C这个函数依赖实际是一个冗余依赖，可以由前两个依赖传递得到，因此不需要管。

保持函数依赖的判断(补充，第2点不强求)：如果F上的每一个函数依赖都在其分解后的某一个关系上成立，则这个分解是保持依赖的（这是一个充分条件）。也即我们课堂上说的简单方法，看函数每个依赖的左右两边属性是否都在同一个分解的模式中。

无损分解

分解后的关系模式能够还原出原关系模式，就是无损分解，不能还原就是有损。当分解为两个关系模式，可以通过以下定理判断是否无损分解。

定理：如果R的分解为p={R1，R2}，F为R所满足的函数依赖集合，分解p具有无损连接性的充分必要条件是R1∩R2->（R1-R2）或者R1∩R2->（R2-R1）。当分解为三个及以上关系模式时，可以通过表格法求解。

并发控制

事务管理

事务：由一系列操作组成，这些操作，要么全做，要么全不做，拥有四种特性：

• （操作）原子性：要么全做，要么全不做。
• （数据）一致性：事务发生后数据是一致的，例如银行转账，不会存在A账户转出，但是B账户没收到的情况。
• （执行）隔离性：任一事务的更新操作直到其成功提交的整个过程对其他事务都是不可见的，不同事务之间是隔离的，互不干涉。
• （改变）持续性：事务操作的结果是持续性的。

事务是并发控制的前提条件，并发控制就是控制不同的事务并发执行，提高系统效率，但是并发控制中存在下面三个问题：

• 丢失更新：事务1对数据A进行了修改并写回，事务2也对A进行了修改并写回，此时事务2写回的数据会覆盖事务1写回的数据，就丢失了事务1对A的更新。即对数据A的更新会被覆盖。
• 不可重复读：事务2读A，而后事务1对数据A进行了修改并写回，此时若事务2再读A，发现数据不对。即一个事务重复读A两次，会发现数据A有误。
• 读脏数据：事务1对数据A进行了修改后，事务2读数据A，而后事务1回滚，数据A恢复了原来的值，那么事务2对数据A做的事是无效的，读到了脏数据。

封锁协议

X锁是排它锁（写锁）。若事务T对数据对象A加上X锁，则只允许T读取和修改A，其他事务都不能再对A加任何类型的锁，直到T释放A上的锁。

S锁是共享锁（读锁）。若事务T对数据对象A加上S锁，则只允许T读取A，但不能修改A，其他事务只能再对A加S锁（也即能读不能修改），直到T释放A上的S锁。

共分为三级封锁协议，如下：

一级封锁协议：事务在修改数据R之前必须先对其加X锁，直到事务结束才释放。可解决丢失更新问题。

二级封锁协议：一级封锁协议的基础上加上事务T在读数据R之前必须先对其加S锁，读完后即可释放S锁。可解决丢失更新、读脏数据问题。

三级封锁协议：一级封锁协议加上事务T在读取数据R之前先对其加S锁，直到事务结束才释放。可解决丢失更新、读脏数据、数据重复读问题。