[大数据]数据库系统概论整理(Part Ⅱ)

数据库的基本概念

• 数据：描述事物的符号记录
• 数据库：长期存放在计算机内、有组织、可共享的大量数据的集合
• 数据库管理系统：是位于用户和操作系统之间的一层数据管理软件
• 数据库系统：由数据库、数据库管理系统、应用程序和数据库管理员组成的存储、管理、处理和维护数据的系统

数据模型

层次模型：适用一对多的联系

• 优点：①数据结构比较简单清晰 ②查询效率高
• 缺点：①不适合现实世界中多对多的联系 ②对插入和删除操作的限制比较多 ③查询子结点必须通过双亲结点

网状模型

• 优点：①可表示实体间的多种复杂联系 ②存取效率较高
• 缺点：①结构复杂，不利于用户掌握 ②数据独立性差

关系模型

• 优点：①严格建立在数学概念基础上 ②数据结构简单、清晰 ③数据独立性高、安全保密性高
• 缺点：查询效率不高

三级模式和二级映像

三级模式

• 内模式：对应于物理级，处于数据库系统的最底层
• 模式：对应于概念级，处于数据库系统的中间层
• 外模式：对应于用户级，处于数据库系统的最高层

二级映像

• 外模式/模式映像：当模式改变时，可以使外模式保持不变，保证了数据与程序的逻辑独立性
• 模式/内模式映像：当存储结构改变时，可以使模式保持不变，保证了数据与程序的物理独立性

范式

• 第一范式(1NF)：每一个分量必须是不可分的数据项
  1NF $消除非主属性对码的部分函数依赖$ 2NF $消除非主属性对码的传递函数依赖$ 3NF $消除主属性对码的部分和传递函数依赖$ BCNF $消除非平凡且非函数依赖的多值依赖$ 4NF

数据库设计

• 数据库设计的特点：①三分技术，七分管理，十二分基础数据 ②整个设计过程中要把数据库结构设计和对数据的处理设计紧密结合起来
• 数据库设计的阶段：①需求分析 ②概念结构设计 ③逻辑结构设计 ④物理结构设计 ⑤数据库实施 ⑥数据库运行和维护

查询优化

• 代数优化：指关系代数表达式的优化，即按照一定的规则，通过对关系代数表达式进行等价变换，改变代数表达式中操作的次序和组合，使查询执行更高效
• 物理优化：是指存取路径和底层操作算法的选择
  ①基于规则的启发式优化：指那些在大多数情况下都适用，但不是在每种情况下都是最好的规则
  ②基于代价估算的优化：使用优化器估算不同执行策略的代价，并选出具有最小代价的执行计划
  ③两种结合的优化方法：先使用启发式规则，选取若干较优的候选方案，减少代价估算的工作量；然后分别计算这些候选方案的执行代价，较快地选出最终地优化方案

游标

• 游标实际上是一种能从包括多条数据记录的结果集中每次提取一条记录的机制。游标充当指针的作用。尽管游标能遍历结果中的所有行，但它一次只指向一行。
  声明游标(DECLARE CURSOR)：仅仅是一条说明性语句
  打开游标(OPEN CURSOR)：此时游标处于活动状态，指针指向查询结果集中地第一条记录
  读取游标(FETCH CURSOR)：把游标指针向前推进一条记录，同时将缓冲区中的当前记录取出来
  关闭游标(CLOSE CURSOR)：解除与当前查询结果集的联系

流程控制

流程控制语句主要有条件控制语句和循环控制语句

• 条件控制语句：IF语句、IF-THEN语句、IF-THEN-ELSE语句和嵌套的IF语句
• 循环控制语句：LOOP、WHILE-LOOP和FOR-LOOP

命名块和匿名块

• 匿名块每次执行时都用进行编译，它不能被存储到数据库中，也不能在其他过程化SQL块中调用
• 过程和函数都是命名块，它们被编译后保存在数据库中，称为持久性存储模块，可以被反复调用，运行速度较快

事务

• 所谓事务是用户定义的一个数据库操作序列，这些操作要么序列要么全做，要么全不做，是一个不可分割的工作单位
• COMMIT提交：即提交事务的所有操作**。具体地说就是将事务中所有对数据库的更新写回到磁盘上的物理数据库中去，事务正常结束。
• ROLLBACK回滚：即在事务运行的过程中发生了某种故障，事务不能继续进行，系统将事务中对数据库的所有已完成的操作全部撤销，回滚到事务开始时的状态。
• 事务的ACID特性：原子性、一致性、隔离性、持续性

• 数据库系统中可能发生的故障：
  ①事务内部的故障
  如运算溢出、并发事务发生死锁而被选中撤销该事务、违反了某些完整性限制而被终止等
  恢复方法：强行回滚 (这类恢复操作称为事务撤销)
  ②系统故障【不破坏数据库】
  如CPU故障、操作系统故障、DBMS代码错误/系统断电等
  恢复方法：
  对于未完成的事务，系统重启后回滚
  对于已提交的事务，需要重做
  ③介质故障【破坏数据库】
  如磁盘损坏、磁头碰撞、瞬时强磁场干扰等
  ④计算机病毒【破坏数据库】

数据库恢复技术

• 恢复的基本原理：冗余
• 建立冗余数据最常用的技术是数据转储和登记日志文件
  ①数据转储
  所谓转储即数据库管理员定期地将整个数据库复制到磁带、磁盘或其他存储介质上保存起来的过程。这些备用的数据称为后备副本或后援副本。当数据库遭到破坏后可以将后备版本重新装入，但重装后备副本只能将数据库恢复到转储时的状态，要想恢复到故障发生时的状态，必须重新运行自转储以后的所有更新事务。
• 转储可分为静态转储和动态转储
  静态转储：系统在无运行事务时进行的转储操作，即转储操作开始的时刻数据库处于一致性状态，而转储期间不允许(或不存在)对数据库的任何存取、修改活动。
  优点：简单，转储的数据保证正确有效
  缺点：转储必须等待正运行的事务结束，降低了数据库的可用性
  动态转储：转储期间允许对数据库进行存取或修改
  优点：转储和用户事务可以并发执行
  缺点：转储的数据不能保证正确有效
• 转储还可以分为海量转储和增量转储
  海量转储：每次转储全部数据库
  增量转储：每次只转储上一次转储后更新过的数据
• 数据转储有两种方式，分别可以在两种状态下进行，因此数据转储方法可以分为4类：动态海量转储、动态增量转储、静态海量转储、静态增量转储

②登记日志文件

• 日志文件是用来记录事务对数据库的更新操作的文件。日志文件主要有两种格式：以记录为单位的日志文件和以数据块为单位的日志文件
• 日志文件的作用：可以用来进行事务故障的恢复和系统故障恢复，并协助后备副本进行介质故障恢复
• 登记日志文件必须遵循的两条原则：①登记的次序严格按并发事务执行的时间次序 ②必须先写日志文件，后写数据库
  如果先写了数据库修改，而在运行记录中没有登记这个修改，则以后就无法恢复这个修改了。如果先写日志，但没有修改数据库，在恢复时只不过是多执行一次UNDO操作，并不会影响数据库的正确性。

恢复策略

• 事务故障：是指事物在运行至正常终点前被终止，这时恢复子系统应利用日志文件撤销(UNDO)此事务已对数据库进行的修改【事务故障的恢复是由系统自动完成的】
• 系统故障：撤销故障发生时未完成的事务，重做已完成的事务【系统故障的恢复是由系统在重新启动时自动完成的】
• 介质故障：重装数据库，然后重做已完成的事务【介质故障的恢复需要数据库管理员介入，但数据库管理员只需要重装最近转储的数据库副本和有关的各种日志文件副本，然后执行系统提供的恢复命令即可，具体的恢复操作仍由数据库管理系统完成。】

检查点和数据库镜像

• 检查点概念的提出：解决利用日志技术恢复数据库时会浪费大量时间的问题
• 检查点记录是一类新的日志记录。
  检查点记录的内容包括：①建立检查点时刻所有正在执行的事务清单 ②这些事务最近一个日志记录的地址
• 系统使用检查点方法进行恢复时要建立两个事务队列：①UNDO-LIST ②REDO-LIST
• 数据库镜像概念的提出：为避免磁盘介质出现故障影响数据库的可用性
• 数据库镜像：根据数据库管理员的要求，自动把整个数据库或其中的关键数据复制到另外一个磁盘上，每当主数据库更新时，数据库管理系统自动把更新后的数据复制过去，由数据库管理系统自动保证镜像数据与主数据库的一致性。这样，一旦出现介质故障，可由镜像磁盘继续提供使用，同时数据库管理系统自动利用镜像磁盘数据进行数据库的恢复，不需要关闭系统和重装数据库副本。在没有出现故障时，数据库镜像还可以用于并发操作，即当一个用户对数据加排他锁修改数据时，其他用户可以读镜像数据库，而不必等待该用户释放锁。

并发控制

• 事务的串行执行方式：每个时刻只有一个事务运行，一个事务的开始必定是另一个事务的结束
• 事务的交叉并发执行方式：每个时刻还是只有一个事务运行，但事务可以轮流交叉运行(单处理机系统中)。虽然单处理机系统中的并行事务并没有真正地并行运行，但是减少了处理机的空闲时间，提高了系统的效率。
• 事务的同时并发方式：多个处理机同时运行多个事物，实现多个事务真正的并行运行
  

• 并发操作可能会使事务的ACID特性遭到破坏，此时带来的数据不一致性包括三种：丢失修改、不可重复读、读"脏"数据

1. 丢失修改：两个事务同时读数据并进行修改，其中一个事务提交的结果破坏了另一个事务提交的结果，如飞机订票系统
2. 不可重复读：一个事务读取数据后，另一个事务对其进行了更新操作，使得前一个事务无法再读取到之前的数据
   不可重复读包括三种情况(其中，后两种情况称为幻影现象)：
   ①事务1读取数据，事务2修改了数据
   ②事务1读取数据，事务2删除了数据
   ③事务1读取数据，事务2插入了数据
3. 读"脏"数据：事务1修改了某一数据后将其写回磁盘，事务2读取该数据，由于某些原因，事务1将修改操作撤销，此时数据恢复原值，那么事务2读取到的数据就出现了不一致的现象

• 并发控制的主要技术：
  ①封锁
  基本的封锁类型：排他锁(X锁)和共享锁(S锁)
  排他锁又称为写锁，只允许事务读取和修改数据对象A
  共享锁又称为读锁，事务可以读数据对象，但不能修改数据对象
  封锁协议：何时申请X锁或S锁、持续时间、何时释放等
  一级封锁协议【可防止丢失修改】：事务T在修改数据R之前必须对其加Ｘ锁，直到事务结束才释放
  二级封锁协议【可防止丢失修改和读"脏"数据】：在一级封锁协议基础上增加事务T在读取数据R之前必须先对其加S锁，读完后即可释放S锁
  三级封锁协议【可防止丢失修改、读"脏"数据和不可重复读】：在一级封锁协议基础上增加事务T在读取数据R之前必须先对其加S锁，直到事务结束才释放
  ②时间戳
  时间戳方法给每一个事务盖上一个时标，即事务开始执行的时间。每个事务具有唯一的时间戳，并按照这个时间戳来解决事务的冲突操作。如果发生冲突操作，就回滚具有较早时间戳的事务，以保证其他事务的正常执行，被回滚的事务被赋予新的时间戳并从头开始执行。
  ③乐观控制法
  乐观控制法认为事务执行时很少发生冲突，因此不对事务进行特殊的管制，而是让它自由执行，事务提交前再进行正确性检查。如果检查后发现该事务执行中出现过冲突并影响了可串行性，则拒绝提交并回滚该事务。乐观控制法又被称为验证方法(certifier)。
  ④多版本并发控制
  多版本并发控制和封锁机制相比，主要的好处是消除了数据库中数据对象读和写操作的冲突，有效地提高了系统的性能

活锁和死锁

• 避免活锁的简单方法是采用先来先服务的策略
• 预防死锁通常有以下两种方法：
  ①一次封锁法：要求每个事务必须一次将所有要使用的数据全部加锁，否则就不能继续执行
  存在的问题：①一次就将以后要用到的全部数据加锁，扩大了封锁的范围，降低了系统的并发度　②数据是不断变化的，所以很难事先精确地确定每个事务要封锁的对象，为此只能扩大封锁范围，这就降低了并发度
  ②顺序封锁法：预先对数据对象规定一个封锁顺序，所有事务都按这个顺序实施封锁
  存在的问题：①数据不断变化，使得维护封锁顺序非常困难，成本很高　②很难事先确定每一个事务要封锁哪些对象，因此很难按顺序去施加封锁
• 在操作系统中广为采用的预防死锁的策略并不太适合数据库的特点，因此数据库管理系统在解决死锁的问题上普遍采用的是诊断并解除死锁的方法。
• 诊断死锁的方法一般使用超时法或事务等待图法
• 解除死锁的原则：选择一个处理死锁代价最小的事务，将其撤销，释放此事务持有的所有的锁，使其他事务得以继续运行下去

并发调度的可串行性

• 可串行化调度的定义：多个事务的并发执行是正确的，当且仅当其结果与按某一次序串行地执行这些事务的结果相同，称这种调度策略为可串行化(serializable)调度
• 冲突操作是指不同的事务对同一个数据的读写操作和写写操作
• 一个调度Sc在保证冲突操作的次序不变的情况下，通过交换两个事务不冲突操作的次序得到另一个调度Sc’，如果Sc’是串行的，称调度Sc为冲突可串行化的调度。若一个调度是冲突可串行化，则一定是可串行化的调度。因此可以用这种方法来判断一个调度是否是冲突可串行化的。(冲突可串行化调度是可串行化调度的充分条件，不是必要条件)

• 数据库管理系统目前普遍采用两段锁协议来保证调度是可串行化的
• 两段锁的两个阶段：
  ①获得封锁，也称为扩展阶段：可以申请获得任何数据项上的任何类型的锁，但是不能释放任何锁
  ②释放封锁，也称为收缩阶段：可以释放任何数据项上的任何类型的锁，但是不能再申请任何锁
• 若并发执行的所有事务均遵守两段锁协议，则对这些事务的任何并发调度策略都是可串行化的(事务遵循两段锁协议是可串行化调度的充分条件，而不是必要条件)

封锁的粒度

• 封锁对象的大小称为封锁粒度。封锁的粒度越大，数据库所能够封锁的数据单元就越少，并发度就越小，系统开销也越小
• 多粒度封锁：在一个系统中同时支持多种封锁粒度供不同的事务选择
• 多粒度封锁中一个数据对象可能以两种方式封锁，显示封锁和隐式封锁
  显示封锁：应事务的要求直接加到数据对象上的封锁
  隐式封锁：该数据对象没有独立加锁，是由于其上级结点加锁而使该数据对象加上了锁
• 一般地，对某个数据对象加锁，系统要检查该数据对象上有无显式封锁与之冲突；再检查其所有上级结点，看本事务的显式封锁是否与该数据对象上的隐式封锁(即由于上级结点已加的封锁造成的)冲突；还要检查其下级所有结点，看它们的显式封锁是否与本事务的隐式封锁(将加到下级结点的封锁)冲突。

意向锁

• 概念的提出：为了解决系统检查数据对象上封锁冲突时的低效率而引进的一种新型锁
• 意向锁的含义：如果对一个结点加意向锁，则说明该结点的下层结点正在被加锁；对任一结点加锁时，必须先对它的上层结点加意向锁。
• 三种常用的意向锁：意向共享锁、意向排他锁、共享意向排他锁
  意向共享锁(IS锁)：如果对一个数据对象加IS锁，表示它的后裔结点拟(意向)加S锁
  意向排他锁(IX锁)：如果对一个数据对象加IX锁，表示它的后裔结点拟(意向)加X锁　
  共享意向排他锁(SIX锁)：如果对一个数据对象加SIX锁，表示对它加S锁，再加IX锁，即SIX=S+IX