Concurrency Control Theory
Definitions
1.每个事务的结果要么是COMMIT要么是ABORT。如果COMMIT了，所有事务的修改都会被保存，如果ABORT了，所有事务的修改都会被撤销。ABORT可以是事务本身自己调用，也可以是被DBMS调用。
2.事务的正确性和速度都是需要保证的，其中正确性准则是ACID准则。
Atomicity：原子性要确保一个事务中的操作要么都发生，要么都不发生。
Consistency：如果每个事务都是一致的，并且数据库在处理事务前也是一致的，那么这个数据库就认为是一致的。
Isolation：每个事务的执行都是孤立的。
Durability：如果一个事务commit了，那么它对数据库的影响就会一直持续存在。
ACID：Atomicity
Approach1：Shadow Paging
DBMS把pages复制一遍并且将事务作用在这些复制的page上面，一旦事务commit了，原先的page就会被换成新的page。这个做法因为要复制，效率比较低下，而且复制page容易造成内存碎片，不实用。
Approach2：Logging
数据库在进行事务之前先把事务要进行的操作写在日志中，这个日志会同时存在与内存和磁盘之中。这样如果一个事务被自身给终止了，那么DBMS就会根据内存中的日志来恢复整个数据库；如果事务被写入到磁盘中了，就会根据磁盘上的日志来恢复数据库。
而且日志除了有可以恢复的功能，还能够先预处理出所有可能读/写的page，根据这些page对操作进行重排来提高效率。被commit的操作也不是立刻写入到磁盘中，可能是将一段时间内所有的commit操作都写入到磁盘中，那么这个时候如果数据库出现了故障，损失的也就是这段时间的操作，数据库会根据内存中的日志来还原。
ACID：Isolation
有两种并发协议，一种是悲观协议，它会假设所有的事务都是冲突的，因此在一开始就不会让问题发生。另外一种是乐观协议，它会假设事务之间很少会发生冲突，因此在执行事务之前不会进行检查，而是等事务执行完再来检查有没有问题，如果有问题就撤销所有的操作。
并发协议的目的是为了生成一种执行方案，使得这个执行方案等同某种顺序执行方案。当我们提交了两个事务时，这两个事务可能并不会按照我们提交的先后顺序执行，并且事务内部的操作也可能会交错执行。
事务之间可能会存在冲突：读-写冲突、写/读冲突、写/写冲突。也就是说凡是两个事务中对同一个object进行的操作中涉及到写，就认为这两个事务会产生冲突。
Serializable
如果一个调度方案等同于一个顺序执行的方案，那么这个方案就是serializable的。
如果一个调度方案可以通过连续交换不冲突的操作来等同于一个顺序执行的方案，那么这个方案就是conflict serializable的。大多数数据库可以判断一个方案是不是conflict serializable的。但是还有一种类型叫做view serializable。因为数据库能够看到的仅仅是事务中我要对某个对象进行读操作/写操作，因此数据库并不能确保事务最后执行出来的结果在逻辑上是正确的。比如时间先后顺序的要求数据库是不知道的，这就需要在应用层上对这些事务进行调度，比如强制让一个事务先执行完再来执行另一个事务等等，数据库做不到这一点。因为数据库不知道应用层如何翻译理解这些数据。
Dependency Graphs
我们用一种叫做依赖图的结构来判断一个方案是不是conflict serializable的。每个事务都当作图中的一个点，如果一个操作x在事务a中和事务b中的操作y冲突了，并且x的在y前面被执行，那么就从a连一条边到b。这里的冲突就是上面说的三种冲突类型。如果这个依赖图中存在环，那么就说明这个调度方案不是conflict serializable的。