《云数据管理：挑战与机遇》2.3.1　预备知识

本节书摘来自华章出版社《云数据管理》一书中的第2章，第3节，作者迪卫艾肯特·阿格拉沃尔，更多章节内容可以访问云栖社区“华章计算机”公众号查看

预备知识

数据库由对象的集合组成，如x、y、z。假设每个对象都有一个值，所有对象的值构成了数据库的状态。通常情况下，这些状态必须满足数据库的一致性约束。数据库对象支持两种原子操作：针对x的读和针对x的写，或者r[x]和w[x]。事务的概念在数据库系统中至关重要。一个事务是按照一定偏序执行的操作的集合。事务ti执行的操作记作ri[x]和wi[x]。如果一个事务是正确的，即，如果一个事务在一致数据库上单独执行，那么该事务可以将数据库转换成另外一个一致状态。

事务的执行必须是原子的，即必须满足如下两个属性：

1. 事务之间互不干扰。

2. 事务中的操作要么全部执行，要么都不执行。

事务ti以commit(ci)或abort(ai)操作结束。并发控制协议可以确保并发执行的事务彼此之间互不影响。恢复协议可以确保all-or-nothing属性。

如果两个操作的执行顺序对结果有影响，即，如果其中一个是写操作，那么这两个操作是冲突的。给定一个事务集合T，T上的一个历史H是针对所有事务操作的偏序，该顺序反映了操作执行的顺序（事务顺序和冲突操作顺序）。

数据库管理系统必须满足ACID特性，即

原子性（atomicity）：每个事务要么全部执行，要么都不执行，即all-or-none属性。

一致性（consistency）：每个事务是一个一致的执行单位。

隔离型（isolation）：事务之间互不影响。

持久性（durability）：事务的效果是永久的。

当一个并发事务集合执行时，事务的正确性概念必须以每一个事务都是一致的（ACID中的C）为前提，因此，如果事务是隔离执行的，数据库将从一个一致状态转换成另外一个一致状态。因此，如果事务集合串行执行，那么可以保证其正确性。特别是，对于一个调度H中的任意两个事务ti和tj，如果ti的所有操作在H中都位于tj的所有操作之前，或者相反，那么H是串行的。

为了允许事务之间在一定程度上并发执行，产生了可串行化的概念。如果一个历史的执行结果与一个串行历史的执行结果等价，那么该历史是可串行化的。如果两个历史产生相同的结果，即所有的事务写入相同的值，我们认为这两个历史是等价的。由于我们不知道哪些事务执行写操作，事务就需要从相同的事务中读数据，最终写入的值也相同。不幸的是，识别可串行化的历史是NP完全问题[Papadimitriou, 1979]。因此，产生了一个更强的可串行性概念，称之为冲突可串行性。

回想一下，如果针对相同对象的两个操作中，至少有一个是写操作，那么这两个操作是冲突的。如果两个历史H1和H2定义在相同的操作集合之上（相应的事务集合也相同），并且这两个历史中所有的冲突操作的顺序都一致，那么H1和H2是冲突等价的。如果一个历史H和某一个串行历史Hs是冲突等价的，那么H就是冲突可串行化的。既然串行执行是正确的，那么就可以保证冲突可串行化历史也是正确的