数据库理论

数据库

一、绪论

DBMS数据库管理系统：

(1)定义：位于用户与操作系统之间的一层数据管理软件

(2)功能：

DDL:数据定义语言：定义DB中的对象(外模式、模式、内模式)

DML:数据操纵语言：宿主行(嵌入主语言，不能独立使用)、自住型(交互式命令语言，语法简单，可以独立使用)

数据运行管理(数据控制功能):并发控制、存储控制、完整性约束条件的检查和执行、发生故障后的系统恢复。

ps：所有的操作都要再控制程序的统一管理下进行，保证数据库的正确有效。

数据库的建立和维护功能：初始数据装入、数据库的转储、恢复、重组织、系统性能监视、分析——DBMS实用程序实现

DBS数据库系统：

(1)定义：在计算机系统中引入数据库后的系统——采用数据库技术的计算机系统

(2)包括：DB、DBMS(及开发工具)、应用系统、数据库管理员及用户——数据库、硬件、软件、人员

ps:在不引起混淆的情况下，数据库系统简称数据库。

(3)关系：应用程序——DBMS——数据库

(4)特点：

数据结构化

共享性高

冗余度低、避免不相容性与不一致性、易扩充

数据独立性高：物理独立性、逻辑独立性；

数据模型：

(1)定义：数据库中用于提供信息表示、操作手段的形式架构

(2)种类：

概念数据模型：设计DB，不依赖于具体的计算机系统，与DBMS无关；

逻辑数据模型：实现DB，依赖于具体的计算机系统，必须是DBMS支持的某种类型——网状模型、层次模型、关系模型；

概念数据模型：

概念模型中的一些基本概念：

(1)实体：客观存在并相互区别的事物；

(2)属性：实体所具有的特性；

​ 域：属性的取值范围

(3)码(关键字)：唯一标识实体的属性集；(一个或多个属性)；

(4)实体型:实体名及其属性集来刻画同类实体

e.g.学生(学号、姓名、年龄、性别、系、年级)

(5)实体集：同型实体实例的集合

e.g.(050101、张三、20、男、计算机系) 、(050102、李四、21、男、计算机系)...

联系的三种类型：1：1 1：n n：n

E-R图(实体-联系法):

实体：(框内写实体名)

联系：(框内写联系名/e.g.动作，用线将其与有关实体连接，注明联系的类型)

​ n | | 1

​ | |

属性：(框内写属性名，用线将其与有关实体或联系连接)

逻辑数据模型：

三要素:

(1)数据结构：数据库所研究的对象类型的集合；

对象：与数据本身有关的对象、与数据之间联系有关的对象；

​ 数据结构的类型： 决定 数据模型的类型：

​ 层次结构————————————层次模型

​ 网状结构————————————网状模型

​ 关系结构————————————关系模型

(2)数据操作：

对DB中各种对象(型)的实例(值)进行操作；

型——数据的结构和属性的集合；

e.g.学生(学号、姓名、年龄、性别、系、年级) 概念模型中的实体型

值——型的具体赋值；

e.g.(050101、张三、20、男、计算机系) 、(050102、李四、21、男、计算机系)... 概念模型中的实体集

操作：检索

​ 更新：插入

​ 删除

​ 修改

(3)数据的约束条件：

定义：一组完整性规则的集合——给定的数据模型中数据及其联系所具有的制约和依存规则，以保证数据的完整性（即数据的正确、有效、相容）。

数据模型类型:

(1)当前流行的基本数据模型有三类：

层次模型(Hierarchical Model)

网状模型(Network Model)

关系模型(Relational Model)

ps:它们之间的根本区别在于数据之间的联系的表示方式不同（记录型之间的联系方式不同）

(2)按照三类数据模型设计和实现：

（关系、层次、网状） DBMS

（关系、层次、网状） 数据库系统

层次模型:

最早使用的一种模型

数据结构是一棵有向树

特点：有且仅有一个结点无双亲，该结点称为根结点。其他结点有且只有一个双亲。

实例：行政关系、家族关系等

典型代表：IBM公司1968年研制的IMS数据库管理系统

缺点：不能表示两个以上实体型之间的复杂联系和实体型之间的多对多的联系

网状模型：

数据结构是一个有向图

特点：有一个以上的结点没有双亲结点。可以有多于一个的双亲。能表示实体之间的多种复杂联系

典型代表：CODASYL系统（DBTG系统）

关系模型:

关系模型是用二维表格结构来表示实体及实体之间的联系的模型

数据结构是一个“二维表框架”组成的集合

特点：概念简单，用户易懂易用，有严格的数学基础，实体或实体之间的联系都用关系表示，用户的观点里，数据的逻辑结构就是表。大多数数据库系统都是关系型

典型代表：ORACLE、SYBASE、INFORMIX、DB/2、VFP、FoxBase、Access

主要术语：

(1)关系：一个关系对应一张表；

(2)元组：表中的一行；

(3)属性：表中的一列；每列的名称——属性名；

(4)主码：表中的某个属性组，其值能够唯一的表示一个元素

(5)域：属性的取值范围；

(6)分量：元组中的一个属性值；

(7)关系模式：对关系的描述，用关系名(属性1，属性2，属性3...，属性n)来表示；

规则：关系必须是规范化的关系：其最基本的要求是每一个分量是一个不可分的数据项(不允许表中还有表)

操作：

(1)用户对数据的检索操作不过是从原来的表中得到一张新的表。

(2)在用户眼中，无论是原始数据还是结果数据，都是同一种数据结构——二维表。

(3)数据操作是集合操作，即操作对象和操作结果都是若干元组的集合。

(4)把存取路径向用户隐藏起来，用户只要指出“干什么”，不必详细说明“怎么干” ，提高了数据的独立性

数据库系统结构(内部/外部)：

1.从数据库管理系统角度：采用三级模式(内部结构)；ps：后面具体介绍

2.从数据库最终用户角度：分为集中式结构、分布式结构、客户/服务器结构、并行结构(外部体系结构)；

模式的概念：

模式(Schema)：

数据库逻辑结构和特征的描述

是型的描述

反映的是数据的结构及其联系

模式是相对稳定的

模式的一个实例（Instance）

模式的一个具体值

反映数据库某一时刻的状态

同一个模式可以有很多实例

实例随数据库中的数据的更新而变动

三级模式结构：

绝大多数数据库系统在总的体系结构上都具有三级模式的特征

三级模式是对数据的三个抽象级别：e.g.

外模式（用户模式） ————文章

模式（逻辑模式） ————字典

内模式（存储模式） ————0,1储存

优点：

(1)保证数据的独立性

(2)简化了用户接口，方便了用户使用

(3)有利于数据共享

(4)有利于数据安全保密

外模式：

(1)定义：数据库用户看到的数据视图，即与某一应用有关的数据的逻辑结构和特征的描述。

(2)作用：用户通过外模式使用数据库(DB)的数据。

(3)实现：外模式描述语言(外模式DDL)描述用户数据视图。

(4)特点：

外模式通常是模式的子集，不同用户的外模式的描述可以不同。

不同用户的外模式可以互相覆盖，同一外模式可以为某一用户的多个应用所启用

(5)数量：多个

模式：

(1)定义：所有用户的公共视图，即DB中全体数据的逻辑结构和特征的描述。

(2)作用：统一考虑所有用户对数据的需要，综合成一个逻辑整体。

(3)实现：模式描述语言（模式DDL）描述数据在逻辑上的视图。

(4)特点：

它与具体的应用程序及使用的高级程序设计语言无关。

逻辑上的视图，通常以某一种数据模型为基础。

(5)数量：一个

内模式：

(1)定义：数据在数据库系统内部的表示，即对数据的物理结构和存储方式的描述。

e.g.记录是顺序存储还是按照B树结构存储，或是按照hash方法存储，索引的组织方式是什么，数据是否压缩、是否加密，数据的存储记录结构的规定等。

(2)作用：定义数据的物理结构和存储方式。

(3)实现：内模式描述语言（内模式DDL/存储模式DDL）

(4)数量：一个

二级映像功能：

为了实现三个抽象层次的联系和转换，数据库系统在这三级模式中提供了两层映像：

外模式/模式映像:

定义：外模式与模式之间的对应关系。

作用：实现了外模式与模式之间的联系和转换。

特点：对于每个外模式，都有一个外模式/模式映象。

数量：多个

模式/内模式映像:

定义：DB全局逻辑结构与存储结构之间的对应关系。

作用：实现了模式与内模式之间的联系和转换。

特点：由于模式、内模式唯一，只有一个模式/内模式映象。

数量：一个

DBMS结构图：

操作系统(OS)：DB、DBMS

数据的逻辑独立性：

当数据的逻辑结构改变了——模式改变——外模式/模式映像做相应改变——外模式不变——应用程序不变

所以：外模式/模式映象保证数据的逻辑独立性

数据的物理独立性：

当数据的物理结构改变了——内模式改变——模式/内模式映像做相应改变——模式不变——外模式/模式映像不变——外模式不变——应用程序不变

结论：模式/内模式映象保证数据的物理独立性

二、关系数据库

关系模型概述：

关系：

关系表示：实体，实体之间的关系；

关系实际上是二维表；每一行：元组；每一列：属性；

关系是从笛卡儿积中选取的有意义的子集——在关系的数学定义里解释

关系操作：

(1)查询：

选择、投影、连接、除、并、交、差、

(2)数据更新：

插入、删除、修改

ps：查询的表达能力是其中最重要的部分

特点：操作对象和结果都是：集合=关系=二维表。

代数方式（关系代数）

关系代数——用对关系的运算来表达查询要求的方式。包括选择、投影、连接、除、并、交、差、笛卡尔积。

逻辑方式（关系演算）

关系演算——用谓词来表达查询要求的方式。

数据操纵语言DML：

分成关系查询语言和关系更新语言两大类：

关系查询语言：

是更新语言的基础，是主要研究对象，根据其理论基础不同分为：

(1)关系代数语言

(2)关系演算语言

(3)具有关系代数和关系演算双重特点的语言。

特点：

(1)它们均是抽象的查询语言

(2)它们是设计各种高级关系数据语言的基础和指导思想

(3)它们能用来评估实际系统中查询语言能力的标准和基础

(4)高度非过程化——存取路径的选择由DBMS完成，而不用用户完成。

完整性约束：

实体完整性、参照完整性、用户定义完整性

关系数据结构：

域：

略

笛卡儿积：

给定一组任意集合D1,D2,…Dn(它们可以包括相同的元素)

这n个集合的笛卡儿积为： D1×D2×…×Dn={(d1,d2,…dn)| di∈ Di,i=1,2…,n}

笛卡儿积也是一个集合,其中:Di称为域;每一个元素(d1,d2,…dn) 叫做一个n元组(简称元组);

元素中每一个值di叫做一个分量；

Di的基数用mi(i=1,2,…,n)表示,则笛卡儿积的D1×D2×…×Dn的基数为所有域的基数的累乘乘积

关系的数学定义：

笛卡儿积 D1×D2×… ×Dn 的任一个子集称为定义在域D1,D2,…,Dn上的n元关系(Relation)，可用R(D1,D2,…,Dn )表示。

其中R为关系名，n称为关系的目或度(Degree)；

该子集元素是关系中的元组；

关系中的元组个数是关系的基数;

同样可以把关系看作是一个二维表，表的框架由Di(i=1,2…,n)构成，每一行对应一个元组，表的每一列对应一个域,给每个域起一个名字,称为属性;

具有相同关系框架的关系称为同类关系;

关系是从笛卡儿积中选取的有意义的子集：解释：

设 D1=手机类型集合={摩托罗拉、NOKiA、三星} D2 =配件集合={摩托罗拉充电器， NOKiA充电器、三星充电器}

(1)其笛卡儿积有：3*3=9个；

(2)构造一个手机关系，可表示为：

​ 手机（手机类型，手机充电器）——只有6个有意义，

手机

​ 手机类型 手机充电器

​ 摩托罗拉 摩托罗拉充电器

​ NOKiA NOKiA充电器

​ 三星 三星充电器

——————————————————————只有6个有意义

码、候选码、主码:

(1) 码：在给定的关系中，具有唯一标识元组的一个或一组属性,称为关系的码(关系键)

ps:码的性质：唯一性、最小性

(2)候选码：如果在关系中，具有码特性的属性或属性组有多个，则把它们都称为关系的候选码(关系候选键)

(3)主码：当一个关系中有多个候选码时，我们从候选码中选择一个作为关系的主码(主关系键)

ps:每个关系都必定有且只有一个主码 ，对于一个关系,主码一经选定,通常是不能随意改变的

结论：

(1)任何关系必有码；

(2)任何关系必有主码，且主码唯一；

(3)任何关系必有候选码，候选码可能不唯一；

(4)当关系只有一个候选码时，该关系的码就是其候选码，也是其主码。

ppt第26页。

关系的完整性：

关系代数：

六、关系规范化：

关系模式：

五元组 R < U ， D ， dom ， F >

R:关系名 U:属性组 D：属性的域 dom：属性到域的映射

1NF(第一范式)

定义：原子属性（即属性是不可再分的数据项），则R∈1NF

结论：1NF的定义也是关系的性质（其中一条），1NF是规范化条件中最基本的一条，关系模型要求关系必须满足1NF。

2NF(第二范式)

定义： R ∈1NF 且 KEY f->非主属性，则R ∈2NF。

注意：只有关系的每一个非主属性都完全函数依赖于候选码，该关系才属于2NF 。

解释：候选码缺一不可，全部候选码才可推出非主属性；

补充：采用投影分解法将一个1NF的关系分解为多个2NF的关系，可以在一定程度上减轻原1NF关系中存在的插入异常、删除异常、数据冗余度大、修改复杂等问题。

3NF(第三范式)

定义： R∈2NF且不存在 KEY t->非主属性，则R ∈3NF。

注意：只要关系的某一个非主属性传递函数依赖于候选码，该关系就不属于3NF 。

补充：

若R∈3NF，则R的每一个非主属性既不部分函数依赖于候选码也不传递函数依赖于候选码。

如果R∈3NF，则R也是2NF。

采用投影分解法将一个2NF的关系分解为多个3NF的关系，可以在一定程度上解决原2NF关系中存在的插入异常、删除异常、数据冗余度大、修改复杂等问题。

将关系模式分解成3NF模式集的算法：

对于关系模式R和R上成立的FD集F，先求出F的最小依赖集，然后把最小依赖集中那些左部相同的FD用合并规则合并起来；

对最小依赖集中，每个FD X→Y去构成一个模式XY；

在构成的模式集中，如果每个模式都不包含R的候选码，那么把候选码作为一个模式放入模式集中。

e.g.

设关系模式R(ABCDE)，R的最小依赖集为{A→B,C→D}。R的候选码是ACE。

根据最小依赖集，可知3NF的模式集为{AB,CD}。再加入由候选码组成的模式ACE，因此最后的模式集为{AB,CD,ACE}

计算FD集F的最小依赖集Fm的算法:

1.根据分解规则得到一个与F等价的FD集G：G中每个FD的右边均为单属性（FD右边属性单一化）；

（例，存在A→CE， 变为A→C 、A→E ）

2.在G中每个FD中消除左边冗余的属性（去掉FD左边多余属性）；

（例，存在CE→A ， E→A ，则去除CE→A ）

3.在G中消除冗余的FD（去掉多余依赖函数）。

e.g.

F={A→B ， B→A ， B→C ， A→C ， C→A }

① A→B ， G＝F－ {A→B }＝ {B→A ， B→C ， A→C ， C→A }

​ A＋G ＝AC(A属性能在G属性集中推出什么属性)， B 不属于 A＋G (删了A→B后，A在G属性集中是否还能推出B属性)

② B→A ，G＝F－ {B→A }＝ {A→B ， B→C ， A→C ， C→A }

​ B＋G ＝ABC， A ∈ B＋G(关系B→A冗余) ，所以去掉 B → A 得Ｆ1＝ {A→ B，B→C，A→C，C→A }(依次删一个关系，若证明冗余后删除，后面的集合用删除后的新集合验证)

③ B→C ，G＝F1－ {B→C }＝ {A→B ， A→C ， C→A }

​ B＋G ＝B， C 不属于 B＋G

④ A→C ，G＝F1－ {A→C }＝ {A→B ， B→C ， C→A }

​ A＋G ＝ABC， C ∈ A＋G ，所以去掉 A → C得Ｆ2＝ {A→B ， B→C ， C→A }

​ ⑤C→A ，G＝F2－ {C→A }＝ {A→ B ， B→ C}

​ C＋G ＝C， A 不属于C＋G

所以Ｆ2＝ {A→B ， B→C ， C→A } 是最小依赖集

上述算法中，操作步骤的顺序很重要，不能颠倒。

BCNF(修正的第三范式)

定义 设关系模式R<U，F>∈1NF，如果对于R的每个函数依赖X→Y，若Y不属于X，则X必含有候选码，那么R∈BCNF。(决定因素包含码，则R ∈ BCNF )

解释：若R∈BCNF，则每一个决定属性集都包含候选码

ps:若R∈3NF 则 R不一定∈BCNF

4NF(第四范式)

多值依赖:一个主码可以决定多组值

e.g.R(A,B,C) F(A->B,A->C) R不属于4NF;分解成：R(A,B) 和 R(A,C)

5NF(第五范式)

定义：一个表可以分成三个子表，而又可以通过自然连接合到一起；

十一、数据库恢复

事务的基本概念

(1)定义:

事务（Transaction）——用户定义的一个数据库操作序列，这些操作要么全做，要么全不做，是一个不可分割的工作单位。

常用字母T代表事务。

(2)语句:

1. BEGIN TRANSACTION事务的开始

2.COMMIT提交，事务中的更新操作结果写回物理DB，事务执行成功地结束。

3.ROLLBACK回滚，撤销事务中的更新操作，滚回到事务开始状态，事务执行不成功地结束

ps:语句1是事务的开始，语句2，3是事务的结束。

(3)性质: ACID特性

1.原子性（Atomicity） 事务是一个不可分割的工作单位。

2.一致性（Consistency） 事务执行的结果是使DB始终处于一致性（正确）状态。

3.隔离性（Isolation） 事务的执行不受其他事务干扰。

4.持续性 / 永久性（Durability） 事务一旦提交，对DB的改变是永久的。

十二、并发控制

并大控制概述

事务的执行方式：

(1)串行执行——每个时刻只有一个事务运行，其他事务必须等到这个事务结束后才能运行；

缺点：许多系统资源处于空闲状态；

(2)并行执行——并行事务的并行操作轮流交叉运行。

优点：减少了处理机的空闲时间，提高了系统的效率。

缺点：多事务同时存取DB，若不加控制，可能会存取和存储不正确的数据，破坏DB的一致性。

并发控制：

1.定义：多事务同时对DB操作的控制和管理。

2.原理：用正确方式调度并发操作。

3.作用：避免数据不一致性，使一个事务的执行不受其他事务干扰。

4.基本单位：事务（T）。

5.主要方法：封锁机制

数据不一致性：

1.丢失修改

T1与T2从数据库中读入同一数据A并修改，T2的提交结果破坏了事务T1提交的结果，导致T1的修改被丢失。

2.不能重复读

T1读取数据后 ，T2执行更新操作，使T1无法再现前一次读取结果。

3.读“脏”数据

T1修改某一数据，并将其写回磁盘，T2读取同一数据后，T1由于某种原因被撤消，这时T1已修改过的数据恢复原值T2读到的数据就与数据库中的数据不一致，是不正确的数据，又称为“脏”数据。

ps:总体来说就是因为事务一旦开始操作数据，操作的数据就不会再改变；

封锁(Locking)

(1)定义：事务T在对数据对象操作之前，先向系统发出请求，对该数据对象加锁。

(2)功能：使事务T对该数据对象有一定的控制，在T释放它的锁之前，其他事务不能更新该数据对象。

(3)种类：

1.排他锁 / 写锁（Exclusive Locks，简称X锁）

形式：Xlock R 解锁：Unlock R

结果：T对R可读可写，其他T对R不能再加任何锁，其他T对R既不可读又不可写

2.共享锁 / 读锁（Share Locks，简称S锁）

形式：Slock R 解锁：Unlock R

结果：T对R可读但不可写，其他T对R不能再加X锁但可以加S锁，其他T对R可读但不可写

封锁协议

定义：封锁协议（Locking Protocol）——在运用封锁技术对数据加锁时，要约定一些规则。

例如：在运用X锁和S锁对数据对象加锁时，要约定何时申请X锁或S锁、何时释放封锁等。

一级封锁协议

内容：T修改数据之前必须先加X锁，直到T结束（包括正常结束COMMIT和非正常结束ROLLBACK）才释放。

作用：防止修改丢失

二级封锁协议

内容：一级封锁协议 ＋ T读数据之前必须先加S锁，读完后即可释放S锁。

作用：防止修改丢失 ，防止读“脏”数据

三级封锁协议

内容：一级封锁协议 ＋ T读数据之前必须先加S锁，直到T结束才释放。

作用：防止修改丢失 ，防止读“脏”数据，防止不可重复读

活锁和死锁

活锁

1.产生活锁的原因——未按申请的先后顺序获得锁。

造成活锁的结果——事务T1释放锁后，事务T2始终不能获得锁。

2.解决：先来先服务策略——分为封锁步骤要求和释放锁步骤要求

（1）封锁子系统按请求封锁的先后次序对事务排队；

（2）数据的锁一释放，批准申请队列中第一个T获得锁。

死锁

1.产生死锁的原因——两个事务T1，T2都已封锁了一些数据，然后又都请求对已被对方事务封锁的数据加锁。

​ 造成死锁的结果——事务T1和T2都不能获得再次加的锁。

2.解决：

（1）预防方法：

一次封锁法——T一次将所有要使用的数据全部加锁，否则不执行。

​ 举例： T1将R1、R2一次加锁，T1执行完后释放R1、R2的锁，T2再继续执行，就不会发生死锁。

​ 缺点：降低并发度 ∵ 封锁范围扩大

顺序封锁法——预先规定一个封锁顺序，所有T按顺序对数据加锁，在释放时按反向顺序进行。

​ 缺点：维护封锁顺序的成本高；很难按规定的顺序去加锁∵ 封锁请求是动态的——难以实现

（2）诊断方法：

超时法——如果T的等待时间超过了规定的时限，就认为发生了死锁。

​ 优点：简单。

​ 缺点：有可能误判；若时限设置得太长，不能及时发现死锁。

等待图法——有向图G（T，U）。

T为结点的集合，结点表示正在运行的事务；U为边的集合，边表示事务等待的情况。若图中有回路，则表示出现了死锁。

（3）解除方法：

选择一个处理代价最小的事务，将其撤销，释放此事务持有的所有锁，使其他事务得以继续运行下去。

并发调度的可串行性

可串行性

若多个事务，并行调度的结果＝串行调度的结果，则该并行调度是可串行化的调度(即并行调度的结果正确)。并行事务具有是可串行性(即并行事务是正确的)。

准则

一个给定的并发调度是正确的调度 等价于 它是可串行化的

两段锁协议

作用：保证并发调度的可串行性，即并发事务的正确性。

内容：两段锁(2PL)

1.在读、写之前，T先获得对数据的封锁；

2.一旦释放一个封锁，不再获得任何锁；

含义:

1.扩展阶段：获得封锁；2.收缩阶段：释放封锁；

举例：

事务1的封锁序列：

Slock A ... Slock B ... Xlock C ... Unlock B ... Unlock A ... Unlock C；

事务2的封锁序列：

Slock A ... Unlock A ... Slock B ... Xlock C ... Unlock C ... Unlock B；

事务1遵守两段锁协议，而事务2不遵守两段协议。