数据视图

数据库系统的一个主要目的是给用户提供数据的抽象视图，即系统隐藏关于数据存储和维护的某些细节。

数据抽象

系统开发人员可以通过以下几个层次上的抽象来对用户屏蔽复杂性：

• 物理层（physical level）：最底层次的抽象，描述数据实际上是怎样存储的。物理层详细描述复杂的底层数据结构
• 逻辑层（logical level）：比物理层稍高的抽象，描述数据库中存储什么数据以及这些数据存在什么关系。这样逻辑层就通过少量简单的结构描述了整个数据库。【注：物理数据独立性：逻辑层不必知道物理层相关的复杂结构】
• 视图层（view level）：最高层次的抽象，只描述整个数据库的某个部分，由于许多用户并不需要关心数据库中的所有信息，而只需访问数据库的一部分。视图层抽象正是为了使这样的用户与系统的交互更简单。

实例与模式

特定时刻存储在数据库中的信息的集合，称为数据库的一个实例（instance）。数据库的总体设计称为数据库模式（schema）。

根据不同的抽象层次，数据库系统可以分为几种不同的模式：

• 物理模式（physical schema）：在物理层描述描述数据库的设计
• 逻辑模式（logical schema）：在逻辑层描述数据库的设计
• 子模式（subschema）：它描述了数据库的不同视图

数据模式

数据库结构的基础是数据模型（data model）。数据模型是一个描述数据、数据联系、数据语义以及一致性约束的概念工具的集合。数据模型提供了一种描述物理层、逻辑层以及视图层数据库设计的方式

数据模型可以划分为四类：

• 关系模型（relational model）：关系模型用表的集合来表示数据和数据间的联系。每个表有多个列，每列有唯一的列名。关系模型时基于记录的模型的一种。
• 实体—联系模型（entity-relationship model）：实体—联系（E—R）数据模型基于对现实世界的这样一种认识：现实世界由一组称作实体的基本对象以及这些对象的联系构成。实体是现实世界中可区别其他对象的一件“时间”或一个“对象”
• 基于对象的数据模型（object-based data model）：面向对象的数据模型可以看成是E-R模型增加了封装、方法（函数）和对象标识等概念后的扩展。对象—关系数据模型结合面向对象的数据模型和关系数据模型的特征
• 半结构化数据模型（semistructured data model）：半结构化数据模型允许相同的数据项含有不同属性集的数据定义。这和早先提到的数据模型形成了对比：在那些数据模型中所有某些特定类型的数据项必须有相同的属性集。XML被广泛地用来表示半结构化数据

【注】网状数据模型（network data model）和层次数据模型（hierarchical data model）先于关系数据模型出现。

数据库语言：

• 数据操作语言（Data-Manipulation Language，DML）：使得用户可以访问或操作那些按照某些适当的数据模型组织起来的数据
• 数据定义语言（Data-Definition Language，DDL）：用于说明数据库模式。数据库系统所使用的存储结构和访问方式是通过一系列特殊的DDL语句来说明的，这些特殊的DDL称作数据存储与定义语言。这些语句定义了数据库模式的实现细节，而这些细节对用户而言，通常是不可见的。
  存储在数据库中的数据值必须满足某些一致性约束（consistency constraint）。
• 域约束（domain constraint）：每个属性都必须对应于一个所有可能取值构成的域。声明一种属性属于某种具体的域就相当于约束它可以取得值。
• 参照完整性（referential integrity）：一个关系中给定属性集上的取值也在另一关系的某一属性集的取值中出现
• 断言（assertion）：一个断言就是数据库需要时刻满足某一条件。【域约束和参照完整性是断言的特殊形式】
• 授权（authorization）：可以对用户加以区别，对于不停地用户在数据库中不同数值上允许不同的访问类型。
  • 读权限（read authorization）：允许读但不能修改数据
  • 插入权限（insert authorization）：允许插入新数据，但不允许修改已有数据
  • 更新权限（update authorization）：允许修改，但不能删除数据

关系数据库

关系数据库基于关系模型，使用一系列表来表达数据以及这些数据之间的联系

关系模型时基于记录的模型的一个实例。基于记录的模型的来源是由于数据库的结构是几种固定格式的记录。每个表包含一种特定类型的记录。每种记录类型定义为固定数目的字段或属性。表的列对应于记录类型的属性。

数据库设计

实体—联系模型

实体—联系模型（E-R）使用一组称为实体的基本对象，以及这些对象间的联系。实体是显示世界中可区别与其他对象的一件“事情”或者一个“物体”。

数据库中实体通过属性（attribute）集合来描述。联系（relationship）是几个实体之间的关联。

同一类型的所有实体的集合称作实体集（entity set），同一类型的所有联系得集合称作联系集合（relationship set）。

数据库的总体逻辑结构（模式）可以用实体—联系图（entity-relationship diagram，E-R图）进行图形化表示。画这种图最常用的方法之一是采用统一建模语言（Unified Modeling Language，UML）。E-R图表示如下：

关系模型

1.关系数据库的结构

关系数据库由表的集合构成，每个表有唯一的名字。

表中一行代表一组值之间的一种联系。在数学术语中，元组（tuple）只是一组值的序列（或列表）。在n个值之间的一种联系可以在数学上可以在用关于这些值的一个n元组（n-tuple）来表示。换言之，n元组就是一个有n个值的元组，它对应于表中的一行

在关系模型中，关系用来指代表，而元组用来指代行，属性指代的是表中的列。

关系实例（relation instance）：表示一个关系的特定实例，即所包含的一组特定的行

对于关系的每个属性，都存在一个允许取值的集合，称为该属性的域（domain）。

【注】： 空（null）值是一个特殊的值，表示值未知或者不存在。

2.数据库模式

数据库模式（database schema）与数据库实例（database instance）的区别：前者是数据库的逻辑设计，后者是给定时刻数据库中数据的一个快照。

3.码（key）

一个元组的属性值必须是能够唯一区分元组的，即一个关系中没有两个元组在所有属性上的取值都相同。

超码（superkey）：是一个或多个属性的集合，这些属性的集合可以使我们在一个关系中唯一地表示一个元组。【注：超码中可能包含无关紧要的属性】

如果K是一个超码，那么K的任意超集也是超码。
候选码（candidate key）：它们的任意真子集都不能成为超码，这样的最小超码称为候选码
【注：A ⊇ B，则 A 集是 B 的超集，也就是说 B 的所有元素 A 里都有，但 A 里的元素 B 就未必有。】

主码（primary key）：代表数据库设计者选中的、主要用来在一个关系中区分不同元组的候选码。【注：码（无论是主码、候选码还是超码）是整个关系的一种性质，而不是单个元组的性质。码的指定代表了被建模的事物在现实世界中约束】

主码应该选择那些值从不或极少变化的属性。习惯将一个关系的主码属性列在其他属性前面。

一个关系模式（r1）可能在它的属性中包含另一个关系模式（r2）的主码。这个属性在r1上称作参照r2的外码（foreign key）。关系r1也称为外码依赖的参照关系（referencing relation），r2叫做外码的参照关系（referenced relation）。

参照完整性（referential integrity constraint）：要求参照关系中任意元组在特定属性上的取值必然等于被参照关系中某个元组在特定属性上的取值。

4.模式图

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

处外码约束之外，模式图没有显示表示出参照完整性约束

5.关系运算

连接运算：把分别来自两个关系的元组对合并成单个元组。

笛卡尔积运算：从两个关系中合并元组，但不同于连接运算，其结果包含来自两个关系元组的所有对，无论它们的属性值是否匹配。

SQL数据定义

数据库中的关系集合必须由数据定义语言（DDL）指定给系统。SQL不仅能定义一组关系，还能够定义每个关系的信息：

1.基本类型

每种类型都可能包含一个被称作为空值的特殊值。空值表示一个缺失的值，该值可能存在但并不为人所知，或者可能根本不存在。

2.自然连接

自然连接（natural join）运算 作用于两个关系，并产生一个关系作为结果。不同于两个关系上的笛卡尔积，它将第一个关系的每个元组与第二个关系的所有元组都进行连接；自然连接只考虑那些在两个关系模式中都出现的属性上取值相同的元组对。

3.视图（view)

视图其实就是一条查询sql语句，用于显示一个或多个表或其他视图中的相关数据。视图将一个查询的结果作为一个表来使用，因此视图可以被看作是存储的查询或一个虚拟表，与真实表不同，视图不会要求分配存储空间，视图中也不会包含实际的数据。视图只是定义了一个查询，视图中的数据是从基表中获取，这些数据在视图被引用时动态的生成。由于视图基于数据库中的其他对象，因此一个视图只需要占用数据字典中保存其定义的空间，而无需额外的存储空间，并且基表的变化会导致视图相应的改变。

4.事务（transaction）

事务由查询和（或）更新语句的序列组成。SQL标准规定当一条SQL语句被执行，就隐式地开始了一个事务。下列SQL语句之一会结束一个事务：

• Commit work：提交当前事务，也就是将事务所做的更新在数据库中持久保存。在事务被提交后，一个新的事务自动开始。
• Rollback work：回滚当前事务，即撤销该事务中所有SQL语句对数据库的更新。这样，数据库就恢复到执行该事务第一条语句之前的状。

当在事务执行过程中检测到错误时，事务回滚是有用的。在某种意义上，事务提交就像对编辑文档的变化存盘，而回滚就像不保存变化退出编辑。一旦某事务执行了commit work，它的影响就不能用rollback work来撤销了。数据库系统保证在发生诸如某条SQL语句错误、断电、系统崩溃这些故障的情况下，如果一个事务还没有完成commit work，其影响将被回滚。在断电和系统奔溃的情况下，回滚会在系统重启之后执行。

4.完整性约束

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

1.单个关系上的约束

create table命令可以定义关系表，还可以包括完整性约束语句。除了主码约束之外，还有许多其他地方包括在create table命令中的约束。允许的完整性约束包括：

• not unll：禁止在属性上插入空值
• unique
• check(<谓词>)

形式化关系查询语言

1.选择运算

2.投影运算

1、内联接（典型的联接运算，使用像 = 或 <> 之类的比较运算符）。

包括相等联接和自然联接。内联接使用比较运算符根据每个表共有的列的值匹配两个表中的行。例如，检索 students和courses表中学生标识号相同的所有行。

2、外联接

外联接可以是左向外联接、右向外联接或完整外部联接。在 FROM子句中指定外联接时，可以由下列几组关键字中的一组指定：

• LEFT JOIN或LEFT OUTER JOIN
  左向外联接的结果集包括 LEFT OUTER子句中指定的左表的所有行，而不仅仅是联接列所匹配的行。如果左表的某行在右表中没有匹配行，则在相关联的结果集行中右表的所有选择列表列均为空值。
  • RIGHT JOIN 或 RIGHT OUTER JOIN
    右向外联接是左向外联接的反向联接。将返回右表的所有行。如果右表的某行在左表中没有匹配行，则将为左表返回空值。
  • FULL JOIN 或 FULL OUTER JOIN
    完整外部联接返回左表和右表中的所有行。当某行在另一个表中没有匹配行时，则另一个表的选择列表列包含空值。如果表之间有匹配行，则整个结果集行包含基表的数据值。

3、交叉联接

交叉联接返回左表中的所有行，左表中的每一行与右表中的所有行组合。交叉联接也称作笛卡尔积。

FROM 子句中的表或视图可通过内联接或完整外部联接按任意顺序指定；但是，用左或右向外联接指定表或视图时，表或视图的顺序很重要。有关使用左或右向外联接排列表的更多信息，请参见使用外联接。

聚集函数（aggregate function）

聚集函数输入值的一个汇集，将单一值作为结果返回。

使用聚集函数对其进行操作的汇集中，一个值可以出现多次，值出现的顺序是无关紧要的。这样的汇集称为多重集（multiset）。集合（set）是多重集的特例，其中每个值都只出现一次。

数据库管理系统（Database Management System,DBMS）

数据库管理系统是位于用户与OS之间的一层数据管理软件。其主要功能：

• 数据定义功能
  DBMS提供数据定义语言（Dta Definition Language，DDL），用户通过它可以方便地对数据库中的数据对象进行定义
• 数据组织、存储和管理
  DBMS要分类组织、存储和管理各种数据，包括数据字典、用户数据、数据的存取路径等
• 数据操纵功能
  DBMS提供数据操纵语言（Data Manipulation Language，DML），用户可以使用DML操纵数据，实现对数据库的基本操作，例如查询、插入、删除和修改等
• 数据库的事物管理和运行管理
  数据库在建立、运用和维护时，由数据库管理系统统一管理、统一控制，以保证数据的安全性、完整性、多用户对数据的并发使用及发生故障后的系统恢复
• 数据库的建立和维护功能
  包括：数据库初始数据的输入、转换功能，数据的转储、恢复功能，数据库的重组织功能和性能监视、分析功能等。这些功能通常是由一些实用程序或管理工具完成的
• 其他功能
  • DBMS与网络中其他软件系统的通信功能
  • 一个DBMS与另一个DBMS或文件系统的数据转换功能
  • 异构数据库之间的互访和互操作功能

关系模型（relational model）

关系 （relation）： 一个关系对应通常说的一张表
元祖（tuple）：表中的一行即为一个元组

属性（attribute）：表中的一列即为一个属性。给每一个属性起一个名称即属性名
码（key）：也称为码键。表中的某个属性组，它可以唯一确定一个元组
域（domain）：属性的取值范围
分量：元组中的一个属性值
关系模式：关系的描述一般表述为：关系名(属性1，属性2，…,属性n)

事务

构成大一逻辑工作单元的操作集合称为事务。即使有故障，数据库系统也必须保证事务的正确执行——要么执行整个事务，又要么属于该事务的操作一个也不执行。

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

ACID特性：

• 原子性：事务的所有操作在数据库中要么全部正确反映出来，要么完全不反映
• 一致性：隔离执行事务时（换言之，在没有其他事务并发执行的情况下）保持数据库的一致性
• 隔离性：尽管多个事务可能并发执行，但系统保证，对于任何一对事务Ti和Tj，在Ti看来，Tj要么在Ti开始之前已经完成执行，要么在Ti完成之后执行。因此，每个事务都感觉不到事务中有其他事务在并发执行
• 持久性：一个事务成功完成之后，它对数据库的改变必须是永久的（即使出现系统故障）

事务的原子性和持久性

事务并非总能成功地执行完成，称该事务中止（aborted）了。如果要确保原子性，中止事务必须对数据库的状态不造成影响。因此，中止事务对数据库所做过的任何改变必须撤销。一旦中止事务造成的变更被撤销，就称事务已回滚（roll back）。恢复机制负责管理事务中止。典型的方法是维护一个日志（log）。每个事务对数据库的修改都首先会记录到日志中。

成功完成执行的事务称为已提交（commited）。一个对数据库进行过更新的已提交事务时数据库进入一个新的一致状态（即使出现系统故障，这个状态也必须保持）。

一旦一个事务已提交，便不能通过中止来撤销其造成的影响。撤销已提交事务所造成的影响的唯一方法是执行一个补偿事务（compensating transaction）。

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

【注】

• 只有在事务已经进入提交状态后，才说事务已提交
• 仅当事务已进入中止状态，才说事务已中止
• 如果事务是提交或中止的，称为已经结束的（terminated）

事务从活动状态开始，当事务完成它的最后一条语句就进入了部分提交状态。此时，事务已经完成执行，但由于实际输出可能仍临时驻留在主存中，因此一个硬件故障可能阻止其成功完成，于是事务仍可能不得不中止。

接着数据库系统往磁盘上写入足够的信息，确保即使出现故障时事务所做的更新也可能在系统重启后重新创建，当最后一条这样的信息写完后，事务就进入提交状态。

系统判定事务不能继续正常执行后（例如，由于硬件或逻辑错误），事务就进入失败状态。这种事务必须回滚。这样，事务就进入中止状态。此时，系统有两种选择：

• 重启（restart）事务，但仅当引起事务中止的硬件错误或不是由事务的内部逻辑所产生的软件错误时。重启的事务被看成是一个新事务。
• 杀死（kill）事务，这样做通常是由于事务的内部逻辑造成的错误，只有重写应用应用程序才能改正，或者由于输入错误，或所需数据在数据库中没有找到。

  事务持久性

  事务处理系统通常允许多个事务并发地执行。数据库必须控制事务之间的交互，以防止它们破坏数据库的一致性。系统通过并发控制机制的一系列机制来保证这一点。

当数据库系统并发地执行多个事务时，相应的调度不必是串行的。若有两个并发执行的事务，操作系统可能先选择其中的一个事务执行一小段时间，然后切换上下文，执行第二个事务一段时间，接着又切换回第一个事务执行一段时间，如此下去。在多个事务的情形下，所有事务共享CPU时间。

并发控制

1.基于锁的协议

确保隔离性的方法之一就是要求对数据项以互斥的方式进行访问。实现该需求最常用的方法是：只允许事务访问当前该事务持有锁的数据项。

常见的锁：

要求每个事务都要根据自己将对数据项Q进行的操作类型申请（request）适当的锁。该事务将请求发送给并发控制管理器。事务只有在并发控制管理器授予（grant）所需锁之后才能进行其操作。这两种锁类型的使用可以让多个事务读取一个数据项但是限制同时只能有一个事务进行写操作。

要使用一个数据项，事务Ti必须首先给该数据项加锁。如果该数据项已经被另一个事务加上了不相容类型的锁，则在所有其他事务持有的不相容类型锁被释放之前，并发控制管理器不会授予锁。因此Ti只好等待，直到所有 其他事务持有的不相容类型的锁被释放。

【注】

1. 相容：令A与B代表任意的锁类型，假设事务Ti请求对数据项Q加A类型锁，而事务Tj当前在数据项Q上拥有B类型锁。尽管数据项Q上存在B类型锁，如果事务Ti可以立即获得数据项Q上的锁，则说A类型的锁与B类型的锁是相容的（compatible）。

• 一个事务只要还在访问数据项，它就必须拥有该数据项上的锁。此外，让事务对数据项作最后一次访问后，立即释放该数据项上的锁也未必是可去的，因为有可能不能保证可串行性。

将要求在系统中的每一个事务遵从称为封锁协议（locking protocol）的一组规则，这些规则规定事务何时对数据项进行加锁、解锁。封锁协议限制了可能的调度数目。这些调度组成的集合是所有可能的可串行化调度的一个真子集。

锁的授予

当事务申请对一个数据项加某一类型的锁，且没有其他事务在该数据项上加了与此类型相冲突的锁，则可以授予锁。

两阶段封锁协议

保证可串行性的一个协议是两阶段封锁协议（two-phase locking protocol）。该协议要求两个事务分两个阶段提出加锁和解锁申请。

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

最初，事务处于增长阶段，事务根据需要获得锁。一旦该事务释放了锁，它就进入缩减阶段，并且不能在发出加锁请求。

对于任何事务，在调度中该事务获得其最后加锁的位置（增长阶段结束点）称为事务的封锁点（lock point）。这样，多个事务根据可以根据它们的封锁点进行排序。实际上，这个顺序就是事务的一个可串行化顺序。

对于一次调度其中涉及的相关事务，无论是什么原因，如果事务Ti失败了，为保证事务的原子性我们必须撤消该事务对数据库造成的影响，即将事务Ti回滚。同时由于系统中事务的并发执行，还必须确保那些依赖于Ti的任何事务Tj(即Tj读取了由Ti所写的数据)也必须同时撤消掉（即回滚掉）。

可恢复调度与不可恢复调度

如图所示，事务T7读取了事务T6所写的数据A，如果事务T6发生故障而回滚，就有可能引起T7的回滚，因此事务T6必须在T7提交之前进行提交，才能保证调度中事务是可恢复的。

对于可恢复调度，我们可以假设事务T7先提交，而事务T6后提交，事务T6在提交的过程中发生了故障，这时候事务T6可以回滚，而事务T7已经提交成为结束的事务，因此无法回滚，这势必造成调度中的事务无法恢复，因此事务T6必须先于事务T7提交，才能保证数据库在执行事务出现中断时，可以会滚到数据库 原来的状态。

由上可以看出，对于每对事务Ti和Tj，如果Tj读取了由Ti所写的数据项，则Ti应先于Tj提交。我们把这样的调度称为可恢复调度。相反，如果在调度中，Tj读取了Ti写入的值，而且先于Ti执行提交操作，那么这个调度室不可恢复的。

级联回滚和无级联回滚

例如，有两个人（两个事务Ti和Tj），一个 好人(Tj)，一个坏人(Ti)，坏人(Ti)在某个人家里偷了钱(Ti执行读取操作)，并将其收入囊中（Ti执行写操作），然后坏人将偷来的钱给好人花（Tj读取了Ti写入的数据项“偷的钱”），最后这个盗窃案被破获了（事务在执行中出现中断），坏人进了监狱（Ti开始回滚），好人也同样被逮捕了（Tj也开始回滚）。可以看出，好人受到了坏人的影响（两个事务之间产生了级联）。因此他们都会出现回滚。

对于非级联回滚，可以简单的说他们之间没有相互产生“写”操作的影响。科学的解释如下：

因一个事务故障导致一系列事务回滚的现象称为级联回滚，系统应该避免级联回滚。例如下图所示，事务T9读取了事务T8写的数据A，事务T10读取了事务T9写的数据A，如果调度10的指令已经执行完事务T10的read(A)，而这时事务T8发生了故障必须回滚，势必引起事务T9和T10的回滚。

级联回滚需要撤消大量的工作，所以，在数据库设计的时候要尽量避免级联回滚。

为了避免调度中事务的级联回滚，对于每对事务Ti和Tj，如果Tj读取了由Ti所写的数据项，则Ti必须在Tj读取之前提交。

级联回滚可以通过将两端封锁协议改为严格两端封锁协议（strict two-phase locking protocol）。加以避免。这个协议除了要求封锁是两段以外，还要求事务持有的所有排他锁必须在事务提交后方可释放。这个要求保证未提交事务所写的任何数据在该事务提交之前以排他锁方式加锁，防止其他事务读这些数据。

另一个两段封锁协议的变体是强两段封锁协议（rigorous two-phase locking protocol），它提交之前不得释放任何锁。

对于下面两个事务：

以上观察提示我们对之前的两阶段封锁协议加以修改，使之允许锁转换（lock conversion）。将提供一种将共享锁升级为排他锁，以及将排他锁降级为共享锁的机制。

• 升级（upgrade）：表示从共享到排他的转变
• 降级（downgrade）：表示从排他到共享的转变

锁转换不能随意进行。锁升级只能发生在增长阶段，而锁降级只能发生在降级阶段。

封锁的实现

锁管理器（lock manager）可以实现为一个过程，它从事务接受消息并反馈消息。锁管理器过程针对锁请求消息返回授予消息，或者要求事务回滚的消息（发生死锁时）。解锁消息只需要得到一个确认回答，但可能引发其他等待事务的授予锁消息。

锁管理器使用以下的数据结构：锁管理器为目前已加锁的每个数据项维护一个链表，每一个请求为链表中一条记录，按请求到达的顺序排序。它使用一个以数据名为索引的散列表来查找链表中的数据项。这个表叫做锁表（lock table）。一个数据项的链表中记每一条记录表示由哪个事务提出的请求，以及它请求什么类型的锁，该记录还表示该请求是否已授予锁。

锁管理器这样处理请求：

• 当一条锁请求消息到达时，如果相应数据项的链表存在，在该链表末尾增加一个记录；否则，新建一个仅包含该请求记录的链表。
  • 在当前没有加锁的数据项上总是授予第一次加锁请求，但当事务向已被加锁的数据项申请加锁时，只有当请求与当前持有的锁相容，并且所有的先前的请求都已授予锁的条件下，锁管理器才为该请求授予锁；否则，该请求只好等待。
• 当锁管理器收到一个事务的解锁消息时，它将与该事务相对应的数据项链表中的记录删除，然后检查随后的记录。如果有，就看该请求能否被授权。如果能，锁管理器授权该请求并处理其后记录，如果还有，类似地一个接一个地处理。
• 如果一个事务中止，锁管理器删除该事务产生的正在等待加锁的所有请求。一旦数据库系统采取适当动作撤销该事务，该中止事务持有的所有锁将被释放 。

这个算法保证了锁请求无饿死现象，因为在先前接受到的请求正在等待加锁时，后来者不可能获得授权。

死锁处理

如果存在一个事务集，该集合中的每个事务在等待该集合中的另一个事务，则称系统处于死锁状态。处理死锁问题采用两种方法：

• 死锁预防（deadlock prevention）：保证系统永不进入死锁状态。

1. 通过对加锁请求进行排序或要求同时获得所有的锁来保证不会发生循环等待
   • 最简单的机制要求每个事务在开始之前封锁它的所有数据项。此外，要么一次全部封锁要么全不封锁。缺点：（1）在事务开始前通常很难预知哪些数据项需要封锁。（2）数据项使用率可能很低，因为许多数据项可能封锁很长时间却用不到
   • 对所有的数据项强加一个次序，同时要求事务只能按次序规定的顺序封锁数据项。
2. 每当等待有可能导致死锁时，进行事务回滚而不是等待加锁

• 死锁检测（deadlock detection）与死锁恢复（deadlock recovery）：检查系统状态的算法周期性地激活，判断有无死锁发生。如果发生死锁，则系统必须试着从死锁从恢复。为实现这一点，系统必须：（1）维护当前将数据项分配给事务的有关信息，以及任何尚未解决的数据项请求信息（2）提供一个使用这些信息判断系统是否进入死锁状态的算法（3）当检测算法判定存在死锁时，从死锁中恢复
  • 当且仅当等待图包含环时，系统中存在存在死锁。在该环中的每个事务称为死锁状态。要检测死锁，系统需要维护等待图，并周期性地激活一个在等待图中搜索环的算法。
  • 从死锁中恢复：当一个检测算法存在死锁时，系统必须从死锁中恢复（rocover）。解除死锁最通常的做法是：回滚一个或多个事务。需要采取三个步骤：
    • 选择牺牲者：给定出图死锁状态的事务集，为解除死锁，必须决定回滚哪一个事务以打破死锁。应使事务回滚带来的代价最小
    • 回滚：一旦决定了要回滚那个事务，就需要决定事务事务回滚多远。（1）彻底回滚（total rollback） ：中止该事务，然后重新开始（2）部分回滚（partial rollback）：事务只回滚到可以解决死锁处。这种回滚要求系统维护所有正在运行事务的额外状态信息。更确切地说，需要记录锁的申请/授予序列和事务执行的更新
    • 饿死：在系统中，如果选择牺牲者主要基于代价因素，有可能同一事务总是被选为牺牲者。这样该事务不能完成其指定任务，就会发生饿死（starvation）。

恢复系统

恢复机制（recovery scheme）将数据库恢复到故障发生前的一致的状态，还必须提供高可用性（high availability），即：它必须将数据库崩溃后不能使用的时间缩短到最短。

1.故障分类

• 事务故障(transaction failure）：
  • 逻辑错误（logical error）：事务由于某些内部条件（如非法输入、找不到数据、溢出或超出资源限制）而无法继续正常执行。
  • 系统错误（system error）：系统进入一种不良状态（如死锁），结果事务无法继续正常执行，但该事务可以在以后的某个时间重新执行。
• 事务故障(transaction failure）：硬件故障，或者是数据库软件或操作系统的漏洞，导致易失性存储器内容的丢失，并使得事务处理停止。而非易失性存储器仍完好无损。硬件错误和软件漏洞致使系统中止，而不破坏非易失性存储器内容的假设称为故障-停止假设（fail-stop assumption）。设计良好的系统在硬件和软件层有大量的内部检查，一旦有错误发生就会将系统停止。
• 磁盘故障(disk failure）：在数据传送过程中由于磁头损坏或故障造成磁盘块上的内容丢失。其他磁盘上的数据拷贝，或者三级介质（如DVD或磁带）上的归档备份可用于从这种故障中恢复。

要确定系统如何从故障中恢复，首先需要确定用于存储数据的设备故障方式。其次必须考虑这些故障方式对数据库内容有什么影响。然后就可以提出在故障发生后仍保证数据库一致性以及事务的原子性的算法，这些算法称为恢复算法，由两部分组成：

• 在正常事务处理时采取措施，保证有足够的信息可用于故障恢复。
• 故障发生后采取措施，将数据库内容恢复到某个保证数据库一致性、事务原子性及持久性的状态。

数据访问

数据库系统常驻于非易失性存储器（通常为磁盘），在任何时间都只有数据库的部分内容在主存中。数据库分成为块（block）的定长存储单位。块是磁盘数据传送的单位，可能包含多个数据项。

事务由磁盘向主存输入信息，然后再将信息输出回磁盘。输入和输出操作以块为单位完成。位于磁盘上的块称为物理块（physical block），临时位于主存的块称为缓冲块（buffer block）。内存中用于临时存放块的区域称为磁盘缓冲区（disk buffer）。

缓冲块最终写到磁盘，要么是因为缓冲区管理器出于其他用途需要内存空间，要么是因为数据库系统希望将B的变化反映到磁盘上。如果数据库系统发执行output(B)，则称数据库系统对缓冲块B进行强制输出（force-output）。

恢复与原子性

为达到保持原子性的目标，必须在修改数据库本身之前，首先向稳定存储器输出信息，描述要做的修改。这种信息能帮助确保已提交事务所做的所有修改都反映到数据库中（或者在故障后的恢复过程中反映到数据库中）。这种信息还能确保中止事务所做的任何修改都不会持久存在于数据库中。

1. 日志记录

使用最为广泛的记录数据库修改的结构就是日志（log）。日志是日志记录（log record）的序列，它记录数据库中的所有更新活动。

更新日志记录（update log record）描述一次数据库写操作，其具有如下几个字段：

• 事务标识（transaction identifier）：是执行write操作的事务的唯一标识
• 数据项标识（data-item identifier）：是所写数据项的唯一标识。通常是数据项在磁盘上的位置，包括数据项所驻留的块的块标识和块内偏移量
• 旧值（old value）：是数据项的写前值
• 新值（new value）：是数据项的写后值
  如下是一些日志记录类型：

每次事务执行写操作时，必须在数据库修改前建立该次写操作的日志记录并把它加到日志中。一旦日志记录已存在，就可以根据需要将修改输出到数据库中。并且能够撤销已经输出到数据库中的修改，这就是利用日志记录中的旧值字段来做的。

为了从系统故障个磁盘故障中恢复时能使用日志记录，日记必须存放在稳定存储器中。

2. 数据库修改

日志记录使得系统在事务必须中止的情况下能能够对事务所做的修改进行撤销；并且在事务已经提交单在修改已存放到磁盘上的数据库中之前系统崩溃的情况下能够对事务所做的修改进行重做。

如果一个事务执行了对磁盘缓冲区或磁盘自身的更新，就说这个事务修改了数据库；而对事务在主存中自己私有的部分进行的更新不算数据库修改。如果一个事务知道它提交时都没有修改数据库，就称其采取了延迟修改（deferred-modification）技术。如果数据库修改在事务仍然活跃的发生，就称它采用了立即修改（immediate-modification）技术。延迟修改所付出的开销是，事务需要创建更新过的所有的数据项的本地拷贝；而且如果一个事务读它更新过的数据项，它必须从自己的本地拷贝中读。

3.事务提交

当一个事务commit日志记录——这是该事务的最后一个日志记录——输出到稳定存储器后，就称这个事务提交（commit）。这时所有更早的日志都已经输出到稳定存储器中。故日志中就有足够的信息来保证，即使发生了系统崩溃，事务所做的更新也可以重做。如果系统崩溃发生在日志记录<Ti commit>输出到稳定存储器之前，事务Ti将回滚。这样，包含commit日志记录的块的输出就是单个原子动作，它导致一个事务的提交

使用日志，系统可以对付任何故障，只要它不导致非易失性存储器中信息的丢失。恢复系统使用两个恢复过程，它们都利用日志来找到每个事务Ti更新过的数据项的集合，以及它们各自的旧值和新值。

• redo(Ti):将事务Ti更新过的所有数据项的值都设置为新值
  • 通过redo来执行更新的顺序十分重要；当从系统崩溃中恢复时，如果对一个特定数据项的多个更新的执行顺序不同于它们原来的执行顺序，那么该数据项的最终状态将是一个错误的值。大多数的恢复算法，都没有把每个事务的重做分别执行，而是对日志进行一次扫描，在扫描过程中每遇到一个redo日志记录就执行redo动作。这种方法能够确保保持更新的顺序，并且效率更高，因为仅需要整体读一遍日志，而不是对每个事务读一遍日志。
• undo(Ti):将事务Ti更新过的所有数据项的值都恢复成旧值
  • undo操作不仅将数据项恢复成它的旧值，而且作为撤销过程的一个部分，还写日志记录来记下所执行的更新。这些日志记录是特殊的redo-only日志记录，因为它们不需要包含所更新的数据项的旧值
  • 当对于事务Ti的undo操作完成后，它写一个<Ti abort>日志记录，表明撤销完成了。对于每一个事务，undo(Ti)只执行一次，如果在正常的处理中该事务回滚，或者在系统崩溃后的恢复中既没有发现事务Ti的commit记录，也没有发现事务Ti的abort记录。其结果是，在日志记录中每一个事务最终或者有一条commit记录，或者有一条abort记录。

发生系统崩溃之后，系统查阅日志以确定为保证原子性需要对哪些事务进行重做，哪些事务进行撤销。

• 如果日志包括<Ti start>记录，但不包括<Ti commit>，也不包括<Ti abort>记录，则需要对事务Ti进行撤销
• 如果日志包括<Ti start>记录，以及<Ti commit>或<Ti abort>记录，需要对事务Ti进行重做。

4.检查点

一种简单的检查点为：（a）在执行检查点操作的过程中不允许执行任何更新 （b）在执行检查点的过程中将所有更新过的缓冲块都输出到磁盘

检查点的执行过程为：

1. 将当前位于主存的所有日志记录输出到稳定存储器
2. 将所有修改的缓冲块输出到磁盘
3. 将一个日志记录<checkpoint L>输出到稳定存储器，其中L是执行检查点是正活跃的事务的列表

【注意】：
要找出事务集合T和确实T中的每个事务是否有commit或abort记录出现在日志中，只需要检查日志中从最后一条checkpoint日志记录开始的部分。

恢复算法

1. 事务回滚

2. 系统崩溃后的恢复

崩溃发生后当数据库重启时，恢复动作分两阶段进行：

• 在重做阶段，系统通过从最后一个检查点开始，正向地扫描日志来重放所有事务的更新。重放的日志记录包括在系统崩溃之前已回滚的事务的日志记录，以及在系统崩溃发生时还没有提交的事务的日志记录。这个阶段还确定能够在系统崩溃发生时未完成，因此必须回滚事务。这样的未完成事务或者在检查点时是活跃的，因此会出现在检查点记录的事务列表中，或者是在检查点之后开始的。
• 

分布式系统

在分布式数据库系统（distributed database system）中，数据库存储在几台计算机中。分布式数据库中的计算机之间通过诸如高速私有网络或者因特网那样的通信媒介相互通信。它们不共享主存储器或磁盘。分布式系统中的计算机在规模和功能上是不变的。

对于分布式系统中的计算机有多种不同的称呼，例如站点（site）或结点（node）。如今主要采用站点以强调这些系统的物理分布。

无共享并行数据库与分布式数据库之间的主要区别在于：在分布式数据库系统中，将事务区分为局部事务和全局事务。局部事务（local transaction）是仅访问在发起事务的那个站点上的数据的事务。全局事务（global transaction）或者访问发起事务的站点之外的某个站点上的数据，或者访问几个不停站点上的数据

分布式数据库的优点：

• 数据共享（sharing data）：建立分布式数据库的主要优点是，它提供了一个环境使一个站点上的用户可以访问存放在其他站点上的数据。
• 自治性（autonomy）：通过手机开分布的方式来共享数据的主要优点在于，每个站点可以对本地存储的数据保持一定程度的控制。在集中式系统中，中心站点的数据库管理员对数据库进行控制。在分布式数据库中，有一个全局数据库管理员负责整个系统。有一部分责任被委派给每个站点的本地数据库管理员。每个管理员可有不同程度的局部自治。
• 可用性（availability）：在分布式系统中，如果一个站点发生故障，其他站点还能继续运行。如果数据项在几个站点上进行了复制（replicate），需要某个特定数据项的事务可以在这几个站点的任何一个上找到该数据项。于是，一个站点的故障不一定意味着整个系统停止运转。

系统必须检测到一个站点发生故障，并需要采取适当的动作来从故障中恢复。系统不能在使用故障点的服务。最后，当故障点恢复了或者修复好了，还需要有一定的机制来将它平滑地重新集成到系统中。

实现问题

在构建分布式数据库系统时，事务的原子性是个重要问题。如果一个事务在两个站点上运行，其很可能在一个站点上提交而在另一个站点上中止，导致不一致状态。两阶段提交（Two-Phase Commit，2PC）协议可以确保这种情况不会出现。

2PC的基本思想是：每个站点将事务执行到部分提交状态，然会将提交权交给一个单独的协调站点，事务这一时刻在该站点上称为处于准备状态。仅当该事务在执行它的站点上均到达准备状态时，协调站点才决定提交该事务。否则，协调站点会决定终止该事务。每个执行该事务的站点必须遵循协调站点的决定。如果当事务处于准备状态时一个站点发生故障，当该站点从故障状态恢复时它必须处于一个状态——提交或中止该事务，这取决于协调站点的决定。

分布式数据库的另一个问题是：并发控制。由于一个事务可以访问在几个站点上的数据项，因此这几个站点上的事务管理器可能需要协调以实现并发控制。如果用到锁，则可以在包含被访问数据项的站点上局部地执行封锁，然而可能会发生设计由多个站点发起的事务的死锁。所以死锁检测必须跨越第一个站点。分布式数据库中更容易发生故障，因此不仅仅是计算机可能出现故障，而且通信链路也可能发生故障。当故障发生时，数据项的赋值是数据库继续运转的关键。