并发控制和备份恢复
事务支持
事务（transaction）| 由单个用户或者应用程序执行的，完成读取或者更新数据库内容的一个或者一串操作
事务是数据库的逻辑操作单位，应用程序的一次执行就是一个事务或者多个事务
事务处理过程中，允许数据库的一致性（consistency）暂时遭到破坏，但最终是转换为一致的状态
事务处理的两种结果：
- 执行成功，事务被提交（commit）
- 未执行成功，数据库必须还原到事务开始之前的一致状态，称为回滚（rolled back）或撤销（undone）
已提交的事务不能被撤销，被撤销的事务可以一段时间后重启
使用BEGIN TRANSACTION、COMMIT、ROLLBACK来划定事务的界限，如果不使用这些分界词，通常会把整个程序视为一个事务，DBMS将在程序正确结束后自动执行COMMIT操作，或者如果程序不能成功执行，则将自动执行ROLLBACK操作
- 部分提交（PARTIALLY COMMITTED）：当最后⼀条语句被执⾏后，事务可能会处于部分提交状态。有可能发现该事务破坏了可串⾏化或者违反了完整性约束，因此事务必须被撤销。或者，系统可 能出现故障，事务更新的数据没有被安全地写到存储设备上，系统恢复后重新提交。
- 失败（FAILED）：事务无法被提交或者事务还处于ACTIVE状态时被撤销时，事务处于FAILED状态
事务的性质
- 原子性（atomicity）：全部或者都不，事务是一个不可分割的单元，要么全部执行，要么都不执行
- 一致性（consistency）：事务必须将数据库从一种一致的状态转换到另一种一致的状态
- 隔离性（isolation）：事务的执行相互独立，未完成事务的中间结果对其他事务不可见
- 持久性（durability）：成功提交的事务的结果要永久地记录在数据库中，不能因为以后的故障而丢失
数据库体系结构
并发控制
并发控制 | 管理数据库上的并发操作以使之互不冲突的过程
必要性
如果两个以上的用户访问数据库，其中至少一个用户在更新数据，则这些操作之间可能相互干扰，导致数据库处于不一致的状态
虽然两个事务自身可能正确，但交叉操作可能会产生错误结果
并发可能导致的问题
- 丢失更新问题（Lost update problem）：一个用户的更新操作成功完成，结果却被另一个用户的操作结果取代
可以禁止T1读取balx的值，直到T2完成更新
- 未提交依赖问题（Uncommitted dependency problem）：允许一个事务看到另一个未提交事务的中间结果，会出现这个问题
可以禁止T3读取balx的值，直到T4成功提交或者撤销
- 不一致分析问题（Inconsistent analysis problem)：某事务正从数据库中读取多个数据的值，但是另一个事务却在其读取过程中修改了其中某些数据的值
可以禁止T6在T5更新完成前操作来避免
可串行性（Serializability）与可恢复性
并发控制的目标：以一种避免事物之间相互干扰的方式对事务进行调度，从而防止上述问题的发生
可以强制事务串行执行（run transactions serially），但会限制系统并发性
调度（schedule） | 一组并发事务操作的序列
串行调度（serial schedule） | 每一个事务的操作都按顺序执行且各事务之间的操作没有任何交叉的调度
非串行调度（nonserial schedule） | 一组并发事务的操作相互交叉执行的调度
可串行性（serializability）目标：寻找那些既能使事务并发执行又互不干扰的非串行调度，从而产生一个能由串行执行产生的数据库状态
如果一组事务并发执行，当且仅当（非串行）调度能够产生和某些串行执行相同的结果，这样的调度是正确的，称为可串行化（serializable）的
读写操作
- 两个事务都只是读取某一数据项，则不会相互冲突，两个事务的执行次序无关紧要
- 两个事务要读写的数据项完全没有交集，则不会相互冲突，两个事务的执行次序无关紧要
- 如果一个事务写某个数据项，而另一个事务读或写同一个数据项，两个事务的执行次序非常重要
如果满足以下条件，称两个操作存在冲突：
- 两个操作都属于不同的事务
- 两个操作都在同一个数据项上进行
- 至少有一个操作是写操作
冲突可串行化（conflict serializability）：需要满足无环
在限定写规则下，总能产生一个优先图（precedence graph）（或串行化图），用于检测调度是否为冲突可串行的
视图可串行化（view serializability）：
调度S1、S2视图等价条件：
- 对每个数据项x，如果在调度S1中，事务Ti读取了x的初值，在调度S2中，事务Ti也必须读取x相同的初值（相同初值）
- 在调度S1中，对于事务Ti对数据项x的每一个读操作来说，若Ti读取的x的值是由事务Tj写入的，那么在调度S2中，事务Ti也必须读取由事务Tj修改的x的值（读取的修改方相同）
- 对于每一个数据项x来说，若在调度S1中，其最后写操作是由事务Ti执行的，那么在调度S2中，对数据项x的最后写操作也应该由同一事务执行（最后修改方相同）
若某调度视图等价于一个串行调度，则其为视图可串行的
视图可串行化检测：带标记的优先图
可恢复性：
假设调度中的每一个事务都不失败，则可串行化就标识出那些能够维护数据一致性的调度
若事务失败，事务的原子性要求我们必须撤销事务对数据库造成的影响
可恢复调度：如果$T_j$读取了$T_i$修改过的数据项，那么事务$T_i$的提交操作应该在事务$T_j$的提交操作前，若调度中的每一对事务$T_i$和$T_j$都满足上述要求，则称调度为可恢复调度
并发控制技术：加锁和时间戳（timestamping）
加锁方法
加锁 | 用来控制并发访问数据的过程。当一个事务正在访问数据库时，可以用锁柜拒绝其他事务的访问请求，从而避免产生不正确的结果
- 共享锁：事务只能读而不能修改该数据项
- 互斥锁：事务既可以读也可以修改该数据项，其他的事务无法读取或者修改该数据项
锁的使用方法：
- 任何需要访问数据项的事务首先要对数据项加锁，如果只读则申请共享锁，若果需要读写则申请互斥锁
- 如果数据项没有被其他事务加锁，则允许事务对其加锁
- 如果数据项已经被加锁，则由DBMS判断当前的加锁请求是否和已经存在的锁相容。如果对已经加上共享锁的数据项请求加上共享锁，则请求被认可；否则，事务必须等待，直至现有的锁被释放
- 事务持有锁直至它在执行期间显式地释放锁或者它被终止（撤销或者提交）。只有当互斥锁被释放时，写操作的结果才能对其他事务可见
简单加了锁也不能让调度变成可串行调度，即事务完成对一个数据项加锁解锁，释放锁太早
两段锁（2PL） | 如果事务中所有的加锁操作都出现在第一个解锁操作前，则该事务是遵循两段锁协议的
- 扩展阶段（growing phase）：事务可以获取它所需要的全部锁，但不能释放任何一个锁
- 收缩阶段（shrinking phase）：事务可以释放它所有的锁，但不能再获取任何新的锁
2PL防止丢失更新问题
2PL防止出现未提交依赖问题
2PL防止出现不一致分析问题
可以证明，若每个事务遵循两段锁协议，那么调度必然是冲突可串行的
级联回滚（cascading rollback）
虽然遵循2PL，但仍然存在问题
为避免级联回滚，要求事务最后提交才允许释放所有锁：严格2PL（rigorous 2PL）
弱严格2PL：只要求互斥锁到事务的最后再释放
活锁：长时间等待，不能获得任何新锁；可以使用优先级系统来避免
死锁
死锁：两个事务互相等待对方的上锁的数据项；DBMS撤销一个或多个事务，并要求DBMS能够自动重启被撤销的事务，但它不能
死锁处理技术
- 超时：比较简单，等待加锁的事务，等待时间最多等于系统设定的等待时间，否则超时重启
- 死锁预防：很难，一般不用；wait-die（等待-死亡法）和wound-wait（伤害-等待法）
- 死锁检测和恢复：构造等待图（wait-for graph），有环死锁；周期性生成等待图来检测
死锁后的恢复：
- 对死锁牺牲者的选择
- 事务回滚的程度
- 避免饿死
时间戳（timestamping）
时间戳 | 由DBMS创建的、标识事务的相对启动时间的、具有唯一性的标识符
每当有新事务启动时，逻辑计数器值+1
时间戳技术 | 一种并发控制协议，它用以下方式确定事务的顺序——越早的事务，时间戳越小，在发生冲突时优先级越高
若某事务企图读或写一个数据项，则只有当该数据项最近一次的修改是由一个较早的事务执行时，才允许该事务进行读或写；否则请求读/写的事务将被赋予一个新的时间戳后重启
读时间戳：最后一个读取该数据项的事务的时间戳
写时间戳：最后一个写（更新）该数据项的事务的时间戳
工作原理：事务T时间戳为ts(T)
事务T发出读请求read(x)
- ts(T)<write_timestamp(x)，则撤销T，以一个新的（较晚的）时间戳重启
- 否则可以执行读操作，置read_timestamp(x)=max(ts(T),read_timestamp(x))
事务T发出写请求write(x)
- ts(T)<read_timestamp(x)，说明数据项已被一个较新的事务读取，则回滚事务T并以一个新的时间戳重启
- ts(T)<write_timestamp(x)，说明数据项已被一个较新的事务更新，则回滚事务T并以一个新的时间戳重启
- 否则可以执行写操作，置write_timestamp(x)=ts(T)
CS：冲突可串行化；VS：视图可串行化；
数据项的粒度
粒度（granularity） | 受到保护的数据项的大小，是并发控制协议中收到保护的基本单位
