CH14 事务 Transactions
事务的必要性
从用户的角度看，数据库的一些操作被认为是一个独立的单元。
比如，支票到存储账户的资金转账是一次操作，而实际在数据库中，这些操作是由几个操作组成的。下面这几个操作同理：
WithdrawDepositTransferDividend
拿转账举例，数据库中从X账户转账k元到Y账户，步骤如下：
找到x账户的元组（数据库查询操作）读取X账户的信息到主存中查看X账户是否有K元从x账户中减去K元把X账户的新的余额值写入数据库（数据库更新）找到Y账户的元组（数据库查询）读取Y账户的信息到主存把K元转到Y的账户把Y的新的余额值写到数据库（数据库更新）
在上述的操作中，我们需要保持一致性/正确性和效率。
一致性和正确性体现在转账的金额是正确的。
考虑下面两种特殊的情形：
若是中途发生了系统崩溃，会怎么样？ 若是多用户对统一数据集进行操作？
基于上述两种情形都会造成数据库的不一致性，所以这里我们最终引入了事务的概念：
14.1 事务概念
14.1.1.事务的定义
事务：构成单一逻辑工作单元的操作集合称为事务。
A transaction is a unit of program execution that accesses and possibly updates various data items.事务是访问并可能更新各种数据项的一个程序执行单元
事务常由高级数据操纵语言（SQL）或者是编程语言（C++，JAVA）通过JDBC或者ODBC嵌入式数据库访问书写的用户程序的执行引起的。
事务的界定：用形如begin transaction和end transaction语句（或函数调用）界定。其中执行的全体操作（begin transaction和end transaction之间）的全体操作组成。
begin transactionx = select salary from person where name = 'Gao H...'update person set salary = x*10 where name = 'Gao H...'end transaction
14.1.2 事务的ACID特性
1.原子性（atomacity）
事务是不可分的，要么执行全部内容，要么就根本不执行。因此，如果一个事务开始执行，但是由于某种原因失败，则事务对数据库造成的任何可能的修改都要撤销。“全或无”的特性称为原子性
2.隔离性（isolation）
一个事务是由多个SQL语句构成，数据库要采取特殊处理来保证事务正常执行而不被来自并发执行的数据库语句所干扰。
对于任何一对事务TiT_iTi和TjT_jTj，在TiT_iTi看来，TjT_jTj或者在其开始之前就已经执行，或者在TiT_iTi完成之后开始执行。因此每个事务都感觉不到系统中有其他的事务在执行。
3.持久性（durability）
崩溃后的实务操作必须是持久的。
4.一致性（consistency）
事务必须保证数据库的一致性——如果一个事务作为原子从一个一致的数据库状态开始独立运行，则事务结束时数据库也必须再次是一致的。
14.2 一个简单的事务模型
1.简单事务模型的假设
简单的数据库语言：
我们关注数据何时从磁盘移动到主存，以及合适从主存移动到硬盘。忽略SQL的插入和删除操作。对数据的实际操作仅限于算术操作
2.例子
Example概述：几个账户和一个访问和更新账户的事务集合构成简单的银行应用来阐明事务的概念。事务使用以下的两个操作来访问数据：
read(X):从数据库把数据项X传送到执行read操作的事务的主存缓冲区的一个也称为X的变量中。write(X)：从执行write的事务的主存缓冲区的变量X中把数据项X传回数据库中。
实际的数据库中：write操作并不一定马上更新磁盘中的数据；write的操作结果可以临时存储在某处，以后在写到磁盘上。
但是现在我们假设write操作立即更新数据库。
设TiT_iTi是从账户A过户50元到账户B的事务，那么事务可以定义为：
Ti:read(A);A:=A-50;write(A);read(B);B:=B+50;write(B);
3.ACID的考虑
一致性：一致性体现在不改变A+B之和。完整性约束的自动检查带来便利。
原子性：假设事务执行前账户A和账户B分别有1000元和2000元。假设在事务Ti执行时系统出现故障，导致Ti的执行没有成功完成。假设放生在write(A)执行后，write(B)操作执行之前。在这种情况下，数据库中反映出来的是账户A有950元，账户B有2000元。A+B不再维持原状。——不一致状态 inconsistent state
保证原子性的基本思路——恢复系统 Recovery System：对于事务要执行写操作的数据项，数据库系统在磁盘上记录其旧值。这个信息记录在日志文件中。如果事务没能完成它的执行，那么数据库系统从日志中恢复旧值，使得事务看上去从未执行过。
持久性：一旦事务成功地完成执行，并且发起事务的用户已经被告知资金转账已经发生，系统就必须保证任何系统故障都不会造成此次转账的相关数据丢失。持久性保证一旦事务完成，该事务对数据库所做的所有更新都会是持久的，即使事务执行完成后出现系统故障。
持久性达到的方法：实现下面的任意一条
事务做的更新在事务结束前已经写入磁盘。有关事务已经执行的更新信息已经写到磁盘上，并且此类信息充分，能让数据库在系统出现故障后重新启动时重新构造更新。
恢复系统{原子性持久性恢复系统\begin{cases}原子性\\持久性\end{cases} 恢复系统{原子性持久性
隔离性：如果在A转账到B事务执行过程中，当A中的金额已经减去转账的金额并且已经写回A，而B的总金额加上转账额后还未写回B，数据库暂时是不一致的。如果一个并发运行的事务在这个中间时刻读取A和B的值并计算A+B，它将得到不一致的值。
保证隔离性的一种方式是：串行地执行事务(running transactions serially)
14.4 Transaction State [ATOMACITY & CONSISTENCY]
14.4.1 aborted 终止
事务并非总能成功执行完成，这种事务称为中止(abroed)了。为了确保原子性，中止事务必须对数据库的状态不造成影响，因此，中止事务对数据库所做过的任何改变必须撤销。一旦中止事务造成的变更被撤销，我们说事务已回滚rolled back。
14.4.2 committed 已提交
一个对数据库进行过更新的已提交事务使数据库进入一个新的一致状态，即是系统出现故障，这个状态也必须维持。
14.4.2 事务的状态
active 活动的初始状态，事务执行时处于这个状态
partially commmited 部分提交的
最后一条语句执行后（语句执行完，但是未commit）
failed 失败的
发现正常的执行不能继续后
aborted 中止的
事务回滚并且数据库已经恢复到事务开始执行以前的状态
committed 提交的
成功完后才能后
14.5 Isolation
14.5.1 Advantages of Concurrent Executions
Concurrent Executions的优点：
提高吞吐量和资源利用率
充分利用CPU和磁盘
减少等待时间
减少平均响应时间 average response time：一个事务从提交考试到完成的所需的平均时间
14.5.2 concurrent- control sheme
数据库必须控制事物之间的交互，以防违背隔离性。
14.5.3 Schedules
执行顺序称为调度，表示指令在系统中的执行的时间顺序。
一组事务的一个调度必须包含这一组事务的全部指令，并且必须保持指令在各个事务中出现的顺序。
事务进入提交状态使用commit来表示事务执行失败用abort表示
1.串行调度
属于同一事务的指令在调度中紧挨在一起。
2.并发调度
14.6 Serializable Schedule 可串行化
14.6.1 Notation Used
数据库对象X,Y,Z ： （X,Y,Z）事务T1,T2局部变量a1,a2,…,b1,b2read()&&write()把对象读入局部变量中：a1<-read(X)把局部变量的内容写入数据库对象：write(X， a1)对对象的操作和计算只能在局部变量上进行(例如X <-X +1是不允许的，但是a1 <a1+ 1是可以的)。在某些情况下，不会显示本地操作(以突出显示read()和write()的效果)14.6.2 Example
For serial schedules ：
If transfer comes before dividend
X : 100 -> 50 -> 50.5
Y : 200 -> 250 -> 252.5
If dividend comes before transfer
X : 100 -> 101 -> 51
Y : 200 -> 202 -> 252
In both case, X + Y = 303
14.6.3 Conflict serializability 冲突可串行化
Suppose two transactions (T1 , T2 ) want to operate on the same data object (X)
Four possible scenarios：
T1 Read(X), T2 Read(X)T1 Read(X), T2 Write(X)T1 Write(X), T2 Read(X)T1 Write(X), T2 Write(X)
How does the order of these operations affect the results of the transactions？
指令的冲突：如果指令I和指令J是不同事务在相同数据项上的操作，并且其中至少有一个是write操作，那么I与J是冲突的。
指令顺序的交换：如果I和J不是冲突的，那么可以交换I和J，得到一个新的调度S’，新的调度S’和S等价。
冲突等价 conflict equivalent：如果调度S可以经过一系列非冲突指令交换转换成S’，那么称S和S‘是冲突等价的。
冲突可串行化 conflict serializable：若一个调度S和一个串行调度冲突等价，则称调度S是冲突可串行化的。
基本假设：
每个事务能保证数据库的一致性因此，一组事务串行执行可以保证数据库的一致性如果一个并行调度是冲突可串行化的conflict serializable，那么： 冲突可串行化视图可串行化
14.6.4 Precedence Graph
Precedence Graph优先图：
该图由两部分组成G = （V，E），其中V是顶点集，E是边集
顶点集V：所有参与调度的事务组成边集E：由满足下列三个条件之一的边Ti→TjT_i\rightarrow T_jTi→Tj 在Tj执行read(Q)之前，Ti执行write(Q)在Tj执行write(Q)之前，Ti执行read(Q)在Tj执行write(Q)之前，Ti执行write(Q)
（除了Ti先read（Q），Tj后read(Q)的情况，其他的都有边Ti→TjT_i\rightarrow T_jTi→Tj）
一个调度是冲突可串行化的，当且仅当优先图中无环。
环探测算法的时间复杂度是n2n^2n2，n是节点的数量
如果是无环的，那么串行化顺序serializability order可以通过拓扑排序topological sorting获得
是否有环的检测：
14.7 Isolation Versus Atomacity
14.7.1 Recoverable Schedules
依赖dependent：TjT_jTj读取了TiT_iTi写入的数据，那么说TjT_jTj依赖于TiT_iTi
可恢复调度recoverable schedules：对于每对事务TiT_iTi和TjT_jTj，如果TjT_jTj读取了之前由TiT_iTi所写的数据项，则TiT_iTi要先于TjT_jTj前提交。
14.7.2 Cascadeless Schedules
要使TiT_iTi的故障正确恢复，可能需要回滚若干事务。因为单个事物的故障导致一系列事务回滚的现象称为级联回滚cascading rollback
需要避免级联回滚，这种调度称为无级联调度cascadeless schedule
无级联调度cascdeless schedule：对于每对事务TiT_iTi和TjT_jTj，如果TjT_jTj读取了先前由TiT_iTi所写的数据项，则TiT_iTi必须在TjT_jTj这一读操作前提交
14.8 Concurrency Control
14.8.1 trade off
A database must provide a mechanism that will ensure that all possible schedules are both:
Conflict serializable.Recoverable and preferably cascadeless
如果策略一次只能执行一个事务，则会产生串行调度serial schedules，但并发性很差poor degree of concurrency。
并发控制方案在它们允许的并发量amount of concurrency和它们引起的开销overhead之间进行权衡。
在调度执行后测试它的可序列化性有点晚了：对可串行性的测试可以帮助我们理解为什么并发控制协议是正确的。
目标——开发确保可串行化的并发控制协议。
14.8.2 Weak Levels of Consistency
Some applications are willing to live with weak levels of consistency, allowing schedules that are not serializable。
低一致性，允许非可串行化的调度。
SQL-92中的标准：
Serializable：defualtRepeatable read：只允许事务读取已提交的数据，而且在一个事务两次读取一个数据项的期间，其他事务不得更新该数据——多次读取会是相同的值。该事务不要求与其他的事务可串行化read committed：只允许读已经提交的事务，但是不要求可重复读，比如，两次读取一个数据项期间，另一个事物更新了该数据并且提交。read uncommited：允许读取未提交的数据。最低的一致性要求
14.10 事务的SQL语句表示
Data manipulation language must include a construct for specifying the set of actions that comprise a transaction.
In SQL, a transaction begins implicitly.——事务的开始是隐式的
A transaction in SQL ends by:
Commit work commits current transaction and begins a new one. ——提交commitRollback work causes current transaction to abort. ——放弃abort
In almost all database systems, by default, every SQL statement also commits implicitly if it executes successfully Implicit commit can be turned off by a database directive —— 默认会隐式提交
E.g. in JDBC, connection.setAutoCommit(false)
