（十六、十七）数据库并发控制(上) 1. 简介和引入知识 1. 事物 1. 事物的概念
事物这个概念在数据库中可谓是最为常见。它是指一些列操作序列(一个或一个以上)当一个事务被提交给了DBMS（数据库管理系统），则DBMS需要确保该事务中的所有操作都成功完成且其结果被永久保存在数据库中，如果事务中有的操作没有成功完成，则事务中的所有操作都需要被回滚，回到事务执行前的状态（要么全执行，要么全都不执行）;同时，该事务对数据库或者其他事务的执行无影响，所有的事务都好像在独立的运行。从事物的概念出发。就可以引出事物的四大特性。
一些形式化的定义为了方便后面的描述
A,B,C来表示数据对象
R(A),W(B) 来表示对于数据对象的读写操作
2. 事物的四大特性这里感觉cmu ppt里面对于四种特性一句话的概括特别好。
原子性(Atomicity): all or nothing
一致性(Consistency): it looks correct to me
隔离性(Isolation): as if alone
持久性(Durability): survive failures
3. 确保原子性的机制首先考虑这样一个问题。加入我把当前账户的$100取出转账给andy。但是在我们取出它之后，转账给andy之前这个事物突然终止了。或者停电了。这样如果dbms什么都不做，就有100 ¥ 蒸发掉。那么如何解决这一问题。
1. Logging(日志）
dmbs的日志会记录所有的行为。这样就可以当事物被abort的时候撤销这个事物已经执行了的无效行为。几乎所有的DBMS都是用了这种方法
2. Shadow Paging
在这种机制下DBMS复制所有的page。当事物对这些page进行改变的时候。会改变这些page的副本。只有当这个事物成功commit之后。这些被改变的副本就会对其他用户可见。
2. 两种常见的并发协议和例子并发协议指的是。dbms如何控制多个事物的交错执行。
两种最常见的协议分别是
悲观协议: 从一开始就不要让问题出现。
乐观协议: 假设冲突非常少。只有当发生的时候才会解决它
下面来看一些并发交错执行的例子
1. 顺序执行exampleAssume at first A and B each have $1000.
左边T1先执行T2后执行整个执行过程大概如下
T1:
A = A - 100 = 900
B = B + 100 = 1100
T2 :
A = A * 1.06 = 954
B = B * 1.06 = 1166
右边则T2先执行。T1后执行。执行的结果和左边是完全一致的
2. INTERLEAVING EXAMPLE (GOOD)
可以发现对于左边。虽然在两个事物之间有交叉。但是最后的结果是一样的。我们说左边这个调度是可序列化的。
3. INTERLEAVING EXAMPLE (BAD)
对于上面的操作。他最后的结果和序列化的结果不一样。则这个调度就是不正确的
3. 几种冲突发生冲突的操作主要分为下面三大类
Read-Write Conflicts (R-W)
Write-Read Conflicts (W-R)
Write-Write Conflicts (W-W)
1. READ-WRITE CONFLICTS读写冲突造成的问题就是不可重复读的问题
事物T1先开始执行。首先读出来A的值发现位10。接下来执行权交给了事物T2运行。T2对A进行了写操作。但是对于事物T1而言，它会认为它没有对A进行了修改操作。因此当事物T2提交之后，执行权回到T1的时候，T1再读取A发现读出来的为19。这里就存在这错误。
2. WRITE-READ CONFLICTS读未提交的数据(脏读)
这里发生的问题就是。事物T1先修改了A的值，但是后面这个事物被abort了。但是T2以为这个值已经被修改了。所以它直接读了T1修改完之后读值进行了操作。
3. WRITE-WRITE CONFLICTS
这里对于T1而言它不知道A被重新写了两次。
2. CONFLICT SERIALIZABILITY INTUITION首先通过两个例子看一下有冲突的可以序列化的调度。和有冲突不能序列化的调度
冲突的几种情况在上面已经介绍过了
可以发现左边和右边并不等价。
那如何判断一个调度是否是冲突可序列化的那。最常用的算法就是依赖图算法(lab4中也有用到这个)
点：事物来表示点
边：如果事物Ti的一个操作Oi与事物Tj的一个操作Oj发生冲突。并且操作Oi发生在Oj之前。那么存在一条从事物Ti指向事物Tj的边
如果出现环。则无法冲突可序列化