并发调度的可串行性
DBMS对并发事务不同的调度(schedule)可能会产生不同的结果
什么样的调度是正确的？
串行化(Serial)调度是正确的
对于串行调度，各个事务的操作没有交叉，也就没有相互干扰，当然也不会产生并发所引起的。如前所述，事务对数据库的作用是将数据库从一个一致的状态转变为另一个一致的状态。多个事务串行执行后，数据库仍旧保持一致的状态。
可串行化(Serializable)调度
多个事务的并发执行是正确的，当且仅当其结果与按某一次序串行地执行这些事务时的结果相同。可串行化调度当然也保持数据库的一致状态
[例]现在有两个事务，分别包含下列操作：
事务T1：读B；A=B+1；写回A
事务T2：读A；B=A+1；写回B
现给出对这两个事务不同的调度策略
可串行性(Serializability)
是并发事务正确调度的准则。在RDBMS中，作为并发控制的正确性准则。一个给定的并发调度，当且仅当它是可串行化的，才认为是正确调度
可串行化调度的充分条件
一个调度Sc在保证冲突操作的次序不变的情况下，通过交换两个事务不冲突操作的次序得到另一个调度Sc‘，如果Sc’是串行的，称调度Sc为冲突可串行化的调度
一个调度是冲突可串行化，一定是可串行化的调度
一般RDBMS都将冲突可串行化作为并发控制的正确性准则
冲突操作（Conflict Operation）
冲突操作是指不同的事务对同一个数据的读写操作和写写操作
Ri (x)与Wj(x) /* 事务Ti读x，Tj写x*/
Wi(x)与Wj(x) /* 事务Ti写x，Tj写x*/
其他操作是不冲突操作
不同事务的冲突操作和同一事务的两个操作不能交换(Commute) ,否则会影响执行的效果
［例］今有调度Sc1=r1(A)w1(A)r2(A)w2(A)r1(B)w1(B)r2(B)w2(B)
把w2(A)与r1(B)w1(B)交换，得到：
r1(A)w1(A)r2(A)r1(B)w1(B)w2(A)r2(B)w2(B)
再把r2(A)与r1(B)w1(B)交换：
Sc2＝r1(A)w1(A)r1(B)w1(B)r2(A)w2(A)r2(B)w2(B)
Sc2等价于一个串行调度T1，T2，Sc1冲突可串行化的调度
冲突可串行化调度是可串行化调度的充分条件，不是必要条件。还有不满足冲突可串行化条件的可串行化调度，称为目标可串行化(view serializability)的调度。 [例]有3个事务, L1和L2是目标等价的（view equivalence） T1=W1(Y)W1(X)，T2=W2(Y)W2(X)，T3=W3(X) 调度L1=W1(Y)W1(X)W2(Y)W2(X) W3(X)是一个串行调度。 调度L2=W1(Y)W2(Y)W2(X)W1(X)W3(X)不满足冲突可串行化。但是调度L2是可串行化的，因为L2执行的结果与调度L1相同，Y的值都等于T2的值，X的值都等于T3的值 *协议
运用*方法时，对数据对象加锁时需要约定一些规则
何时申请*
持锁时间
何时释放*等
两段*协议(Two-Phase Locking，简称2PL)是最常用的一种*协议，理论上证明使用两段*协议产生的是可串行化调度
两段锁协议
指所有事务必须分两个阶段对数据项加锁和解锁
在对任何数据进行读、写操作之前，事务首先要获得对该数据的*
在释放一个*之后，事务不再申请和获得任何其他*
“两段”锁的含义
事务分为两个阶段
第一阶段是获得*，也称为扩展阶段
事务可以申请获得任何数据项上的任何类型的锁，但是不能释放任何锁
第二阶段是释放*，也称为收缩阶段
事务可以释放任何数据项上的任何类型的锁，但是不能再申请任何锁
例
事务Ti遵守两段锁协议，其*序列是 ：
Slock A Slock B Xlock C Unlock B Unlock A Unlock C；
|← 扩展阶段 →| |← 收缩阶段 →|
事务Tj不遵守两段锁协议，其*序列是：
Slock A Unlock A Slock B Xlock C Unlock C Unlock B；
事务遵守两段锁协议是可串行化调度的充分条件，而不是必要条件。
若并发事务都遵守两段锁协议，则对这些事务的任何并发调度策略都是可串行化的
若并发事务的一个调度是可串行化的，不一定所有事务都符合两段锁协议
两段锁协议与防止死锁的一次*法
一次*法要求每个事务必须一次将所有要使用的数据全部加锁，否则就不能继续执行，因此一次*法遵守两段锁协议
但是两段锁协议并不要求事务必须一次将所有要使用的数据全部加锁，因此遵守两段锁协议的事务可能发生死锁
*粒度(Granularity)
*对象的大小称为*粒度(Granularity)
*的对象：逻辑单元，物理单元
例：在关系数据库中，*对象：
逻辑单元: 属性值、属性值集合、元组、关系、索引项、整个索引、整个数据库等
物理单元：页（数据页或索引页）、物理记录等
*粒度与系统的并发度和并发控制的开销密切相关。
*的粒度越大，数据库所能够*的数据单元就越少，并发度就越小，系统开销也越小；
*的粒度越小，并发度较高，但系统开销也就越大
例
若*粒度是数据页，事务T1需要修改元组L1，则T1必须对包含L1的整个数据页A加锁。如果T1对A加锁后事务T2要修改A中元组L2，则T2*等待，直到T1释放A。
如果*粒度是元组，则T1和T2可以同时对L1和L2加锁，不需要互相等待，提高了系统的并行度。
又如，事务T需要读取整个表，若*粒度是元组，T必须对表中的每一个元组加锁，开销极大
多粒度*(Multiple Granularity Locking)
在一个系统中同时支持多种*粒度供不同的事务选择
选择*粒度
同时考虑*开销和并发度两个因素，适当选择*粒度
需要处理多个关系的大量元组的用户事务：以数据库为*单位
需要处理大量元组的用户事务：以关系为*单元
只处理少量元组的用户事务：以元组为*单位
多粒度树
以树形结构来表示多级*粒度
根结点是整个数据库，表示最大的数据粒度
叶结点表示最小的数据粒度
允许多粒度树中的每个结点被独立地加锁
对一个结点加锁意味着这个结点的所有后裔结点也被加以同样类型的锁
在多粒度*中一个数据对象可能以两种方式*：显式*和隐式*
显式*: 直接加到数据对象上的独立*
隐式*: 该数据对象没有独立加锁，是由于其上级结点加锁而使该数据对象加上了锁
显式*和隐式*的效果是一样的！
系统检查*冲突时
要检查显式*
还要检查隐式*
例如事务T要对关系R1加X锁
系统必须搜索其上级结点数据库、关系R1
还要搜索R1的下级结点，即R1中的每一个元组
如果其中某一个数据对象已经加了不相容锁，则T必须等待
对某个数据对象加锁，系统要检查
该数据对象
有无显式*与之冲突
所有上级结点(祖先)
检查本事务的显式*是否与其它事务在该数据对象上的隐式*冲突：(由上级结点已加的*造成的）
所有下级结点(后裔)
看其它事务在下级节点上的显式*是否与本事务的隐式*（将加到下级结点的*）冲突
数据共享与数据一致性是一对矛盾
数据库的价值在很大程度上取决于它所能提供的数据共享度
数据共享在很大程度上取决于系统允许对数据并发操作的程度
数据并发程度又取决于数据库中的并发控制机制
数据的一致性也取决于并发控制的程度。施加的并发控制愈多，数据的一致性往往愈好
数据库的并发控制以事务为单位
数据库的并发控制通常使用*机制
两类最常用的*
并发控制机制调度并发事务操作是否正确的判别准则是可串行性
并发操作的正确性则通常由两段锁协议来保证。
两段锁协议是可串行化调度的充分条件，但不是必要条件