数据库系统概论【五】

一、关系数据理论


问题——什么是一个好的数据库逻辑设计?

关系模式存在的问题 :

  • 数据冗余度太大,浪费存储空间
  • 更新异常(Update Anomalies)
  • 插入异常(Insertion Anomalies),该插入的数据插不进去
  • 删除异常(Deletion Anomalies),不该删除的数据也删去了

好的模式不会发生插入异常、删除异常、更新异常、数据冗余应尽可能少。

这是由于模式中的某些数据依赖引起的。

1、数据依赖

数据依赖是一个关系内部属性与属性之间的一种约束关系,通过属性间值的相等与否体现出来的数据间的相互联系。 是现实世界属性间相互联系的抽象、是数据内在的性质、是语义的体现

  • 函数依赖(Functional Dependency,简记为FD)
  • 多值依赖(Multivalued Dependency,简记为MVD)
  • 连接依赖
  • ……

2、关系模式的简化表示

R(U, D, DOM, F)

  • R:关系名,是符号化的元组语义
  • U:该关系的属性集合
  • D:属性组U中属性所来自的域
  • DOM:属性向域的映象集合
  • F:属性间数据的依赖关系集合

简化:R <U,F>

影响数据库模式设计的主要是 该关系的属性集合U 和 属性间数据的依赖关系集合F

3、规范化-关系的规范化理论

(1)函数依赖

设R(U)是一个属性集U上的关系模式,X和Y是U的子集。若对于R(U)的任意一个可能的关系r,r中不可能存在两个元组在X上的属性值相等, 而在Y上的属性值不等则称“X函数确定Y”或“Y函数依赖于X”,记作X→Y。X称为这个函数依赖的决定属性组,也称为决定因素(Determinant)。

将它想成函数,f(x)=y。所以!一个x只能对应一个值!而一个y可以对应多个x!

问题经常问的是“基本”函数依赖,就是根据语义写最直接的那个函数依赖

例: S(Sno, Sname, Ssex, Sage, Sdept)

F= {Sno→Sname,Sno→Ssex,Sno→Sage,Sno→Sdept}

函数依赖是语义范畴的概念。只能根据数据的语义来确定函数依赖。

(2)平凡函数依赖与非平凡函数依赖

X→Y,Y⊈X,则称X→Y是非平凡的函数依赖。

X→Y,但Y⊆X ,则称X→Y是平凡的函数依赖。

即推出的结果不在原因之内

例:在关系SC(Sno, Cno, Grade)中,

非平凡函数依赖: (Sno, Cno) → Grade

平凡函数依赖: (Sno, Cno) → Sno (Sno, Cno) → Cno

对于任一关系模式,平凡函数依赖都是必然成立的,它不反映新的语义,因此若不特别声明, 我们总是讨论非平凡函数依赖。

(3)完全函数依赖与部分函数依赖

完全函数依赖:设X,Y是关系R的两个属性集合,X’是X的真子集,存在X→Y,但对每一个X’都有X’!→Y,则称Y完全函数依赖于X。

部分函数依赖:设X,Y是关系R的两个属性集合,存在X→Y,若X’是X的真子集,存在X’→Y,则称Y部分函数依赖于X。

*即依据是最小的不能在缺少一个属性了就是完全函数依赖,能推出但是原因中的部分即可推出就是部分函数依赖 *

(4)传递函数依赖

在R(U,F)中,如果X→Y,(Y⊈X),Y↛X,Y→Z,则称Z对X传递函数依赖.记为:X → Z。

注意: 如果Y→X, 即X←→Y,则Z直接依赖于X。

全部路径都是单向的才叫传递函数依赖

4、从函数依赖看码

设K为关系模式R<U,F>中的属性或属性组合。

问题问码是主码,因为主码可简称码

主码,候选码都简称码,如果题目中出现码这个字,需要我们自行根据上下文判断,一般是主码

  • 码是数据系统中的基本概念。所谓码就是能唯一标识实体的属性,他是整个实体集的性质,而不是单个实体的性质。它包括超码,候选码,主码。

  • 若K → U(U完全依赖K),则K称为R的一个候选码(Candidate Key)。

    • 即K能够推出所有的其他属性,且为最小集。则K为候选码
    • 候选码是最小的超码,即K的任意一个真子集都不是候选码
  • 主码:若关系模式R有多个候选码,则选定其中的一个做为主码(Primary key)。

  • 主属性:包含在任何一个候选码中的属性 ,称为主属性(Prime attribute)

  • 非主属性:不包含在任何码中的属性称为非主属性(Nonprime attribute)或非码属性(Non-key attribute)

  • 全码:整个属性组是码,称为全码(All-key)

  • 外码:关系模式 R<U,F>中属性或属性组X 并非 R的码,但 X 是另一个关系模式的码,则称 X 是R 的外部码(Foreign key)也称外码。

5、范式

范式是符合某一种级别的关系模式的集合。关系数据库中的关系必须满足一定的要求。满足不同程度要求的为不同范式。

  • 第一范式(1NF):的所有属性都是不可分的基本数据项

  • 第二范式(2NF):在第一范式的基础上,每一个非主属性都完全函数依赖于主属性

    • 主码若是单一属性则一定满足第二范式
    • 投影解决
  • 第三范式(3ND):在第二范式的基础上,非主键列必须直接依赖于主键,不能存在传递依赖

    • 即第二范式基础上,非主属性之间不能存在函数依赖
    • 投影解决
  • BC范式(BCNF):在第三范式的基础上,每一个决定因素都包含候选键,也就是说,只要属性或属性组A能够决定任何一个属性B,则A的子集中必须有候选键。BCNF范式排除了任何属性(不光是非主属性,2NF和3NF所限制的都是非主属性)对候选键的传递依赖与部分依赖。

    • 即在第三范式的基础上,不能有主键依赖于非主键等情况(注意主键不一定是一个,可能是多组主键)。排除了任何属性对候选键的传递依赖与部分依赖。

    • 例如:学生ID和专业是联合主键这个表的设计满足三范式,有主键,不存在主键的部分依赖,不存在非主键的传递依赖。但是这里存在另一个依赖关系,“专业”函数依赖于“导师”,也就是说每个导师只做一个专业方面的导师,只要知道了是哪个导师,我们自然就知道是哪个专业的了。

      StudentIdMajorAdvisorMajGPA
      1人工智能Edward4.0
      2大数据William3.8
      1大数据William3.7
      3大数据Joseph4.0
    • 投影解决

第二范式(2NF)和第三范式(3NF)的概念很容易混淆,区分它们的关键点在于:

2NF:非主键列是否完全依赖于主键,还是依赖于主键的一部分;

3NF:非主键列是直接依赖于主键,还是直接依赖于非主键列。

二、数据库设计


1、 需求分析阶段

准确了解用户的需求,撰写需求说明

2、概念设计阶段

它是整个数据库设计的关键,通过对用户需求进行综合,归纳与抽象,形成一个独立于具体DBMS的概念模型。E-R图的设计在此阶段。

绘制E-R图为重点,详细查看软件工程。

3、逻辑结构设计阶段

将概念结果转换为某个DBMS所支持的数据模型。也就是指E-R图和关系模型的转换,具体为将实体,实体的属性和实体之间的联系转换为关系模式。

4、数据库物理设计阶段

为逻辑结果选取一个最适合应用环境的物理结构,包括存储结构和存取方法。

5、数据库实施阶段

此阶段利用SQL语句实现逻辑结构设计和物理设计阶段的内容,包括建立数据库,编制与调试应用程序等。

6、数据库运行和维护阶段

运行过程中不断的调整,修改和优化数据库系统。

ER图:①透过关系,n可转化为多条线②两个实体之间必有一个关系(一般是动词,与两个实体名词构成主谓宾关系)

  • 假设有 A,B 两个实体,首先判断一个 A 对应几个 B,再判断一个 B 对应几个 A
  • 如果两边都是 1:1,那么 A 与 B 就是一对一的关系;
  • 如果两边只有一个 1:n,那么 A 与 B 就是一对多的关系;
  • 如果两边都是 1:n,那么 A 与 B 就是多对多的关系

转化为关系模型:
多对多:
实体:①都是属性摆出来先选出主键、
关系:①摆出来,加入链接的实体主键联合起来作为主键,同时又各自作为外键;②自身属性加进去
一对多:
实体:①都是属性摆出来先选出主键;②另外n部分的实体加入1部分的主键作为外键
关系:①关系的属性加入到N部分进去作为普通属性
一对一:
实体:①都是属性摆出来先选出主键;②双方各自加入对方的主键作为外键;
关系:①关系的属性加入到两个实体进去作为普通属性

注意:一个关系可以连出多个实体

三、嵌入式SQL

4-4嵌入式SQL

嵌入式SQL语句

存储过程和函数

PL/SQL存储过程操作实例及其讲解说明

PL/SQL存储过程

1
2
3
4
5
6
CREATE [OR REPLACE] PROCEDURE procedure_name 
[(parameter_name [IN | OUT | IN OUT] type [, ...])]
{IS | AS}
BEGIN
< procedure_body >
END procedure_name;
  • procedure-name是要创建的存储过程的名称。
  • *[OR REPLACE]*选项允许修改现有的过程。
  • 可选参数列表包含参数的名称,模式和类型。IN表示将从外部传递的值,OUT表示将用于返回过程外的值的参数。
  • procedure-body包含可执行部分。
  • 使用AS关键字而不是IS关键字来创建存储过程。

以下示例演示如何创建一个简单的存储过程,执行时它只显示字符串“Hello World!”在屏幕上。

1
2
3
4
5
6
7
8
9
10
11
12
> SET SERVEROUTPUT ON SIZE 99999;
> CREATE OR REPLACE PROCEDURE greetings
> AS
> BEGIN
> dbms_output.put_line('Hello World!');
> END;
> /
> -- 执行存储过程
> exec greetings;
> -- 或者
> EXECUTE greetings;
>

四、数据库恢复技术


1、事务

所谓事务是用户定义的一个数据库操作序列,这些操作要么全做要么全不做,是一个不可分割的工作单元。

事务定义语句

  • BEGIN TRANSACTION: 为事务的开始
  • COMMIT: 提交事务的所有操作
  • ROLLBACK: 当出现错误时,将已完成操作全部撤销,回滚到事务开始时的状态

定义方式

  • 显示定义: 显示调用数据库定义语句
  • 隐式定义: 系统按默认规则自动进行

事务的特性(ACID):原子性(Atomicity)、一致性(Consistency)、隔离性(Isolation)和持续性(Durability)

  • (1) 原子性

    • 事务是数据库的逻辑工作单位,事务中包含的诸操作要么都做,要么都不做。
  • (2) 一致性

    • 事务执行的结果必须是使数据库从一个一致性状态变到另一个一致性状态。
  • (3) 隔离性

    • 一个事务的执行不能被其他事务干扰。即一个事务内部的操作及使用的数据对其他并发事务是隔离的,并发执行的各个事务之间不能互相干扰
  • (4) 持续性

    • 指一个事务一旦提交,它对数据库中数据的改变就应该是永久性的。接下来的其他操作或故障不应该对其执行结果有任何影响。

事务是恢复和并发控制的基本单位。保证事务ACID特性是事务管理的重要任务。

故障种类以及恢复策略

  • (1) 事务内部的故障

    有的可以通过事务程序本身发现,如转账时发现账户余额不足。更多的故障是非预期的,是不能由应用程序处理的,如运算溢出、并发事务发生死锁而被选中撤销该事务、违反了某些完整性限制等

    • 恢复策略:

      1> 反向扫描日志文件,查找该事务的更新操作
      2> 对事务的更新操作执行逆操作
      3> 继续查找该事务的其他更新操作,并做同样处理,直至读到该事务的开始标记,事务故障恢复就完成了。

  • (2) 系统故障

    指造成系统停止运转的任何事件,使得系统要重新启动。例如:硬件错误(CPU故障)、操作系统故障、DBMS代码错误、系统断电等。这类故障影响正在运行的所有事务,但不破坏数据库。这时主存内容,尤其是数据库缓冲区(在内存)中的内容都被丢失,所有运行事务都非正常终止。发生故障时,一些尚未完成的事务的结果可能已送入物理数据库,从而造成数据库可能处于不正确的状态。

    恢复子系统必须在系统重新启动时让所有非正常终止的事务回滚,强行撤销(UNDO)所有未完成事务。另一方面,有些已完成的事务可能有一部分甚至全部留在缓冲区,尚未写回到磁盘上的物理数据库中,系统故障使得这些事务对数据库的修改部分或全部丢失,这也会使数据库处于不一致状态,因此应将这些事务已提交的结果重新写入数据库。所以系统重新启动后,恢复子系统除需要撤销所有未完成的事务,还需要重做(REDO)所有已提交的事务,以将数据库真正恢复到一致状态。

    • 恢复策略:

      1.正向扫描日志文件,找出故障发生前已经提交的事务(有BEGIN有COMMIT),记入重做事务。同时找出未完成的事务(只有BEGIN),加入撤销队列

      2.对撤销队列中的事务进行撤销处理:反向扫描并执行逆操作

      3.对重做队列中的各个事务进行重做处理:正向扫描并重做

  • (3) 介质故障

    也称硬故障,如磁盘损坏、磁头碰撞、强磁场干扰等。

    • 恢复策略

      1.装入最新的数据库后备副本,对于动态转储还需同时装入转储开始时刻的日志文件副本

      2.装入相应的日志文件副本(转储结束时刻的日志文件副本),重做已完成的事务

  • (4) 计算机病毒:产生故障的原因,本身不是故障,可能产生故障2或3

2、恢复的实现技术

建立冗余数据:

  1. 数据转储
  • 静态转储:系统中无运行事务时进行的转储,转储期间不允许任何事务执行。
    优点:得到的一定是一个数据一致性的副本
    缺点:降低了数据库的可用性

    动态转储:转储和用户事务可以并发执行
    优点:系统可用性较好
    缺点:转储得到的副本不一定一致,因此必须建立日志文件等级转储期间各事务对数据库的修改活动

    海量转储:每次转储整个数据库,恢复更方便
    增量转储:每次只转储上一次转储后更新过的数据,恢复较复杂

  • 登记日志文件

    具有检查点的恢复技术

1、 在日志文件中增加检查点记录

2、 增加重新开始文件

3、 恢复子系统在登录日记文件期间动态地维护日志

五、并发控制


1、概述

不同的多事务执行方式

  • 事务串行执行: 每个时刻只有一个事务运行
  • 交叉并发方式: 并行事务的并行操作轮流交叉运行
  • 同时并发方式: 每个处理机可以运行一个事务,多个处理机可以同时运行多个事务

并发控制原因: 防止多个事务并发存取数据库时产生的同时读取和/或修改同一数据而造成的数据不一致性

  • 并发控制能保证事务的一致性,事务是并发控制的基本单位

事务并发执行带来的数据不一致问题

  • 丢失修改: 事务 T1 和 T2 读入同一数据并修改,T2 提交的结果破坏 T1 的提交,导致 T1 的修改被丢失

  • 不可重复读: 事务 T1 读取数据后,事务 T2 执行更新操作,使 T1 无法再现前一次读取结果

    • 包含三种情况: 后两种不可重复读有时也称为幻影现象

      事务 T1 读取某数据后,事务 T2 对其修改,当事务 T1 再次读该数据时,得到与前一次不同的值
      事务 T1 读取某数据后,事务 T2 删除其中部分记录,当 T1 再次读该数据时,发现某些记录消失
      事务 T1 读取某数据后,事务 T2 插入一些记录,当 T1 再次读该数据时,发现多了一些记录

  • 读脏数据: 事务 T2 读取事务 T1 修改的数据后,数据库回滚到 T1 修改前,则 T2 读取的数据即为脏数据

2、封锁

  • 封锁: 事务 T 在对某个数据对象操作之前,先向系统发出请求,对其加锁。

    加锁后事务 T 就对该数据对象有了一定的控制,在事务 T 释放锁之前,其它的事务不能更新此数据对象

封锁类型

  • 排它锁(X锁): 又称写锁,若事务 T 对数据对象 A 加上 X 锁,则只允许 T 读取和修改 A
  • 共享锁(S锁): 又称读锁,若事务 T 对数据对象 A 加上 S 锁,则其它事务只能读取 A,不能修改 A

封锁协议

  • 一级封锁协议:事务 T 在修改数据 A 之前,先对其加 X 锁,直到事务结束才释放

    解决了丢失修改问题

  • 二级封锁协议:事务 T 在读数据 A 之前,先对其加 S 锁,读完后释放

    解决了丢失修改与读脏数据问题

  • 三级封锁协议:事务 T 在读数据 A 之前,先对其加 S 锁,直到事务结束后释放

    解决了丢失修改、读脏数据、不可重复读问题

3、活锁和死锁

(1)活锁

  • 事务 T1 封锁了数据 R
  • 事务 T2 又请求封锁 R,于是 T2 等待
  • T3 也请求封锁 R,当 T1 释放了 R 上的封锁之后系统首先批准了 T3 的请求,T2 仍然等待
    T4
  • 又请求封锁 R,当 T3 释放了 R 上的封锁之后系统又批准了T4的请求……
  • T2 有可能永远等待,这就是活锁的情形

(2)死锁

  • 死锁: 多个事务因竞争资源而出现的互相等待现象

    • 事务T1封锁了数据A,事务T2封锁了数据B,然后T1请求封锁B,与此同时T2也请求封锁A,但因为两个事务的请求都需要等待对方释放锁,这样就出现了永远在等待对方的死锁。
  • 死锁的预防

    • 一次封锁法: 要求每个事务必须一次将所有要使用的数据全部加锁,否则不能继续执行
    • 顺序封锁法: 预先对数据对象规定一个封锁顺序,所有事物都按该顺序实施封锁
  • 破坏死锁产生条件的预防方法

    • 破坏互斥条件:让资源允许共享
    • 破坏不可剥夺条件:有两种方法
      ① 当其申请的资源得不到满足时,放弃其原先占有的资源
      ② 高优先级进程申请的资源被占用时,将强迫该低优先级进程放弃已占有资源
    • 破坏零散请求条件:采用静态分配策略,即当一个进程在得到其所需要的所有资源之后才执行
    • 破坏循环等待条件:按照资源的特性,给资源从小到大编号,进程必须按照从小到大的顺序申请资源,且规定进程占有的资源号必须小于申请的资源号才能提出申请
  • 死锁的诊断

    • 超时法: 若事务等待时间超过规定时限,就认为发生死锁

      • 时间设置短,容易误判
      • 时间设置长,死锁不能及时发现
    • 等待图法: 采用有向图 G = (T, U)

      • T: 为结点集合,每个结点表示正在运行的事务
      • U: 为边的集合,每条边表示事务等待的情况

      若 T1 等待 T2,则画一条从 T1 指向 T2 的边

4、并发调度的可串行性

  • 可串行化调度: 多个事务的并发执行正确,当且仅当其结果与按某一次序串行执行这些事务时的结果相同

    • 可串行性是并发事务正确调度的准则
    • 一个给定的并发调度,当且仅当它是可串行化的,才认为是正确调度
  • 冲突可串行化调度: 调度 Sc 在保证冲突操作次序不变的情况下,通过交换两个事务不冲突操作的次序得到另一个调度 Sc’,如果 Sc’ 是串行的,称调度 Sc 为冲突可串行化的调度

    一个调度是冲突可串行化,一定是可串行化的调度

    冲突可串行化调度可串行化调度充分条件,不是必要条件。还有不满足冲突可串行化条件的可串行化调度。

  • 冲突操作: 指不同的事务对同一个数据的读写操作和写写操作

5、两段锁协议

  • 两段锁协议: 指所有事务必须分两个阶段对数据项加锁和解锁。在对任何数据进行读、写操作之前,事务首先要获得对该数据的封锁,在释放一个封锁之后,事务不再申请和获得任何其他封锁

    • 第一阶段是获得封锁,也称为扩展阶段

      • 事务可以申请获得任何数据项上的任何类型的锁,但是不能释放任何锁
    • 第二阶段是释放封锁,也称为收缩阶段

      • 事务可以释放任何数据项上的任何类型的锁,但是不能再申请任何锁
    • 同样的,事务遵守两段锁协议是可串行化调度的充分条件,而不是必要条件。

      若并发事务都遵守两段锁协议,则对这些事务的任何并发调度策略都是可串行化的
      若并发事务的一个调度是可串行化的,不一定所有事务都符合两段锁协议

  • 封锁粒度(Granularity):封锁对象的大小
    封锁粒度与系统的并发度并发控制的开销密切相关:

    • 封锁的粒度越大,数据库所能够封锁的数据单元就越少,并发度就越小,系统开销也越小;
      封锁的粒度越小,并发度较高,但系统开销也就越大

    • 同时考虑封锁开销和并发度两个因素,适当选择封锁粒度

      • 需要处理多个关系的大量元组的用户事务:以数据库为封锁单位
      • 需要处理大量元组的用户事务:以关系为封锁单元
      • 只处理少量元组的用户事务:以元组为封锁单位
    • 多粒度树:
      以树形结构来表示多级封锁粒度;根结点是整个数据库,表示最大的数据粒度;叶结点表示最小的数据粒度
      如下图 三级粒度树。根结点为数据库,数据库的子结点为关系,关系的子结点为元组:

      多粒度封锁协议:
      ① 允许多粒度树中的每个结点被独立地加锁
      ② 对一个结点加锁意味着这个结点的所有后裔结点也被加以同样类型的锁
      ③ 在多粒度封锁中一个数据对象可能以两种方式封锁:显式封锁和隐式封锁
      显式封锁: 直接加到数据对象上的封锁
      隐式封锁: 是该数据对象没有独立加锁,是由于其上级结点加锁而使该数据对象加上了锁
      (ps:显式封锁和隐式封锁的效果是一样的)
      对某个数据对象加锁,系统要检查:

数据库复习总结

数据库系统概论 第十一章课

-----------------------本文结束 感谢阅读-----------------------
坚持原创技术分享,您的支持将鼓励我继续创作!恰饭^.^~