（计算机软件与理论专业论文）基于语义的长事务处理方法的研究.pdf

基于语义的长事务处理方法的研究 摘要 f 事务处理在数据库系统中一直占据着重要的地位。随着数据库应用的普及， 尤其在一些新兴的应用领域中出现了大量的长事务，如何处理好长事务以避免长 事务造成的系统性能下降成为数据库工作者研究的重要课题。 利用事务的语义将长事务分解后可以有效地提高并发度，但如何保证分解后 事务的正确调度一直是一个很重要的问题。事务处理的目标是要保证多个事务并 发执行的正确性。由于传统的可串行性理论无法直接适用于分解后的事务，因此 事务分解后正确性标准的研究对于长事务处理具有重要意义。有了可行的正确性 判定方法就可以进一步保证给出正确的并发控制算法。利用事务的语义对长事务 进行分解是长事务处理的一种有效方法，然而要求事务分解满足分解特性必然使 一些长事务无法分解。为了处理这种情况，在事务分解的基础上提出进一步利用 对象的语义信息提高系统的并发度。文 本文主要围绕四个方面展开：长事务的分解方法、利用事务语义的长事务处 理、利用对象语义的长事务处理方法以及同时利用事务和对象语义的长事务处理 方法。具体工作如下： 1 怕于在对于事务集进行分解之后一般要通过手工的形式化方法来证明该 分解满足分解特性。为了克服这个缺点，】本文通过对一致性约束集进行分类，给 出了一个判定可分解事务类型的算法，并证明对可分解事务类型进行分解所得到 的分解一定满足分解特性。 2 在利用事务语义方面，本文提出了基于语义的事务分解的正确性标准， 并且给出一种基于有向图的正确性判定方法。在此基础上分别给出了基于锁协议 和乐观方法的并发控制算法，并证明这两种算法所产生的历史是正确历史。 3 在利用对象语义方面，本文给出了基于语义可串行性的乐观并发控制算 法和一种基于并发控制和恢复的统一模型给出的基于锁协议的并发控制算法这 两种算法都克f e t 现有的基于语义可串行性的并发控制算法所存在的缺陷。0 4 本文给出了一种同时利用事务和对象语义的长事釜处理方法。在事务分 解的基础上利用语义单元进步提高了并发度，给出了正确性标准和基于有向图 的正确性判定方法，最后给出了一种基于乐观方法的并发控制算法，并证明该算 法所产生的历史是正确历史。 关键词：事务处理：并发控制? 可串行性j 长事务人 苎王堕墨塑丝蔓堑壁里查鳖盟堑壅 一 a b s t r a c t t r a n s a c t i o nm a n a g e n m e n ti sv e r yi m p o r t a n ti nd a t a b a s em a n a g e m e n ts y s t e m w i t ht h e p o p u l a r i z a t i o n o fd a t a b a s e a p p l i c a t i o n ，e s p e c i a l l y i ns o m ea d v a n c e d a p p l i c a t i o n s ，t h e r e # r em a n yl o n g l i v e dt r a n s a c t i o n s i t i sa ni m p o r t a n tt a s kt od e a l w i t h l o n g 1 i v e dt r a n s a c t i o n t oa v o i dt h ed e c r e a s eo f s y s t e mp e r f o r m a n c e t r a n s a c t i o n sa r ed e c o m p o s e db a s e du p o nt h e s e m a n t i c so ft r a n s a c t i o n s t o i m p r o v et h ec o n c u r r e n c yo fs y s t e m ，b u ti t i sac r i t i c a lq u e s t i o nt oe n s u f et h ec o r r e c t e x e c u t i o no fd e c o m p o s e dt r a n s a c t i o n s 1 1 1 eo b j e c t i v eo f t r a n s a c t i o nm a n a g e m e n ti st o e n s u r et h ec o r r e c te x e c u t i o no fc o n c u r r e n tt r a n s a c t i o n s s i n c et h es e r i a l i z a b i t i t yo f t r a d i t i o n a lt r a n s a c t i o nm o d e lc a n n o tb eu s e di nt h es c h e d u l i n go fd e c o m p o s i t i o no f t r a n s a c t i o n sd i r e c h 轼t h er e s e a r c ho n t h ec o i t c ：c t n c s sc r i t e r i o na f t e rt h ed e c o m p o s i t i o n o ft r a n s a c t i o n si sa n i m p o r t a n t t a s k i ti s h e l p f u l f o rt h e c o n c u r r e n c y e o n t r o l m e c h a n i s mt og i v eas i m p l ed e c i d i n gm e t h o do f c o r r e c t n e s sc r i t e d o n i ti sag o o d m e t h o dt od e c o m p o s el o n g - l i v e dt r a n s a c t i o n sb a s e d o nt h es e m a n t i c so ft r a n s a c t i o n s ， b u tt h e r ea r es t i l ls o m el o n g l i v e dt r a n s a c t i o n st h a tc a n n o tb ed e c o m p o s e dh e c a u s eo f t h ed e c o m p o s i t i o ni t s e l f , w h i c hs h o u l ds a t i s f yd e s i r a b l ep r o p e r t i e sw i t hr e s p e c tt ot h e o r i g i n a l c o l l e c t i o no f 。t r a n s a e t i o n s t h e r e f o r e b a s e do nt h e d e c o m p o s i t i o n o f t r a n s a c t i o n s ，t h es e m a n t i co fo b j e c t i s e x p l o i t e d t o i m p r o v et h ec o n c u r r e n c yo f t r a n s a c t i o n s i nt h i sp a p e r , t h e r ea r ef o o ra s p e c t st ob ec o n s i d e r e d ：t h ed e c o m p o s i t i o nm e t h o d o fl o n g 1 i v e dt r a n s a c t i o n ，l o n g - l i v e dt r a n s a c t i o np r o c e s s i n gb a s e do ns e m a n t i c so f t r a n s a c t i o n ，b a s e do ns e m a n t i c so fo b j e c ta n db a s e do ns e m a n t i c so f t r a n s a c t i o na n d o b i e c tc o n c u r r e n t l y t h em a i n c o n t r i b u t i o n sa t ea sf o l l o w i n g ： 1 ad e c o m p o s i t i o no ft r a n s a c t i o n ss e ts h o u l db ep r o v e dt o s a r i s f yd e s i r a b l e p r o p e r t i e sw i t hr e s p e c tt ot h eo r i g i n a lc o l l e c t i o no f t r a n s a c t i o n sb yf o r m a im e t h o d t o o v e r c o m et h i sd r a w b a c k ，b yc l a s s i f y i n gt h ec o n s i s t e n c yc o n s t r a i n t ss e tw e p r o p o s ea l l a l g o r i t h m ，w h i c hc a nd e c i d et h es e to f t r a n s a c t i o nt y p e st h a tc a nb ed e c o m p o s e d 2 w ep r o p o s et h ec o r r e c t n e s sc r i t e r i o no fs e m a n t i c b a s e dd e c o m p o s i t i o no f t r a n s a c t i o n sa n dg i v ead e c i d i n gm e t h o db a s e do nd i r e c t e dg r a p h f i n a l l yw e p r o p o s e t w o c o n c u r r e n c y c o n t r o la l g o r i t h m sb a s e do ni o c ka n d o p t i m i s t i cm e t h o dr e s p e c t i v e l y 3 、p r o p o s ea no p t i m i s t i cc o n c u r r e n c yc o n t r o 【a l g o r i t h mb a s e do ns e m a n t i c s e r i a l i z a b i l i t ya n dal o c k b a s e dc o n c u r r e n c yc o n t r o la l g o r i t h mw i t hau n i f i e dm o d e lo f u n i f y i n gc o n c u r r e n c yc o n t r o l a n dr e c o v e r y t h e s et w o a l g o r i t h m s o v e r c o m et h e d r a w b a c k so f t h e e x i s t i n gc o n c u r r e n c yc o n t r o la l g o r i t h m s 4 am e t h o db a s e do nt h es e m a n t i c so ft r a n s a c t i o n sa n do b j e c t sc o n c u r r e n t l yi s g i v e nt o d e a lw i t hl o n g l i v e dt r a n s a c t i o n s t h es e m a n t i cu n i ti su s e db a s e do n t r a n s a c t i o n sd e c o m p o s i t i o nt oi m p r o v et h ec o n c u r r e n c yo fs y s t e m s t h ec o r r e c t n e s s c r i t e r i o na n dad e c i d i n gm e t h o db a s e do nd i r e c t e d g r a p h a r e g i v e n f i n a l l y ，a c o n c u r r e n c yc o n t r o la l g o r i t h mb a s e do no p t i m i s t i cm e t h o di sp r o p o s e d k e y w o r d s ：t r a n s a c t i o n m a n a g e m e n t ，c o n c u r r e n c yc o n t r o l ，s e r i a l i z a b i l i t y , l o n g - l i v e d t r a n s a c t i o n i v - 第一章绪论 1 1 引言 第一章绪论 由于数据库资源是很宝贵的，只允许单用户独占数据库一般出现在微型机的 应用上，而对于在运输、金融、通讯、制造、政府及军事等领域中的数据库应用 必然会提出多用户共享数据库的要求。如果每个用户都只是读取数据库中的数 据，也不会有什么问题，但是有的用户可能要更新数据库中的数据，这时就必须 有一个机制来保证这种更新操作不会影响其他用户对数据库的访问，这个机制就 是事务处理。简单地说，事务处理的任务就是要保证多个用户能够正确地共享数 据库资源，使每个用户都不受其他用户的影响，从而也感觉不到其他用户的存在。 用户是通过调用程序与数据库打交道的，因此从用户的角度看事务就是一个 包含数据库和事务操作的一个或多个程序的执行。数据库操作是指对数据库中数 据的读操作和写操作。事务操作包括：开始( s t a r t ) ，提交( c o m m i t ) 和i l ( a b o r t ) 。 一个程序通过开始操作告诉数据库系统它将开始执行一个事务，通过提交或中止 操作表明该事务的结束。通过提交操作该程序告诉数据库系统这个事务已经正常 结束，它的影响可以在数据库中保持持久；通过中止操作该程序告诉数据库系统 这个事务非正常结束，需要消除掉它的影响。所以从数据库系统的角度看，一个 事务是一个由开始操作开始，后面跟着若干数据库操作，最后跟着一个提交或中 止操作构成的序列。 事务一般表示三个不同的单位：逻辑单位、原子单位和恢复单位i “i 。逻辑单 位是指每个事务的执行都有自己的上下文，前面操作的结果可以为后面的操作所 用，不同事务的上下文间相互隔离。原子单位是指把一个事务的执行当作原子动 作，而不受其它事务的干扰。恢复单位是指如果一个事务由于某种原因被中止或 不能完成，则已经执行的操作所造成的影响应该被消除掉。然而有时这些单位不 一定表示一个事务，如在s a g a s 模型d 9 1 中，一个事务称为s a g a 表示一个逻辑 单位，而它的子事务表示原子单位，s a g a s 模型支持两种不同的恢复单位：s a g a 或子事务。 传统的事务模型通过可串行性【i “4 6 1 来保证事务表示一个原子单位，通过严格 性”j 来保证事务的恢复单位。这样的模型很适合传统的数据库应用，这里事务 通常都持续很短的时间，一般只有几秒钟。随着数据库技术应用领域不断扩大， 如在计算机辅助设计( c a d ) 和软件工程( c a s e ) ，地理信息系统( g 1 s ) 和工作流系 统( w f m s ) 等领域，这些新兴领域中通常包括长事务( 1 0 n g 1 i v e dt r a n s a c t i o n ) 。在现 第一章绪论 有的数据库中一般利用锁机制来实现事务的原子单位和恢复单位，一个事务拥有 的数据库对象的锁直至该事务提交( 或中止) 。显然，等待长事务释放它所拥有的 锁将造成不能接受的延迟，导致系统性能严重下降。另外，将一个长事务看作一 个恢复单位，当中止一个长事务时将会造成很大的损失，甚至是用户所不能接受 的。因此传统的数据库技术在处理这些新的应用时会显得力不从心，对于这样的 长事务应用，需要提出新的事务处理概念，事实上应该改变事务的原子单位和恢 复单位的传统概念来适应新的数据库应用的要求，具体地说应该改善事务的原子 单位和恢复单位，如“原子单位”“恢复单位” “事务”。 本文将从以下几方面探讨基于语义的长事务处理方法：利用事务的语义将长 事务分解来改善事务的原子单位和恢复单位；利用对象的语义改善事务的原子单 位以及同时利用事务和对象的语义来改善事务的原予单位和恢复单位。这些方法 都可以提高事务的并发度。下面首先给出事务处理的一些基本概念，然后对长事 务处理方法的相关工作做一下简要的介绍，最后介绍一下本文的主要内容。 1 2 事务处理的基本概念 1 2 1 事务特性 事务有下面四个特性： ( 1 ) 原子性( a t o m i c i t y ) ：事务的执行或者全部完成或者什么也没做，不允许 事务执行一部分就结束。 ( 2 ) 一致性( c o n s i s t e n c y ) ：事务要保持数据库的一致性，如果事务在满足一 致性的数据库上执行，那么当该事务完成时，数据库仍然是一致的。 ( 3 ) 隔离性( i s o l a t i o n ) ：事务执行时好像只有它自己在运行，而没有其他的事 务在执行。 ( 4 ) 持久性( d u r a b i l i t y ) ：一旦事务执行成功并且执行了提交操作，则该事务 对数据库造成的影响即使在系统发生故障时也不能丢失。 事务处理系统通过一种追踪事务执行的数据库机制来保证事务的原子性。如 果事务在完成之前失败，事务处理系统将撤消该事务更新操作的影响，只有当事 务顺利完成时，事务处理系统才允许该事务的更新永久地保留在数据库中。 数据库的一致性是指数据库要满足所有的完整性约束。事务的原子性、隔离 性和持久性是由事务处理系统保证的。事务的一致性要由事务定义本身和事务处 理系统共同来保证，也就是说无论一组事务的定义是否使得它们保证数据库的一 致性，事务处理系统将负责保证事务的原子性、隔离性和持久性。严格地说，事 务处理系统只负责保证事务的原子性、隔离性和持久性，而保证事务具有一致性 第一章绪论 的任务就落在了事务的设计者身上一j 。 一组事务满足隔离性是指这些事务的执行与一次执行一个事务的某个串行 执行效果相同。若系统真正地一次只处理一个事务，那样做将是很低效的，所以 事务隔离性的任务就是当多个事务并发执行时，使每个用户都感觉系统只为自己 服务而没有其他的工作。如果一组事务中的每个事务都具有一致性，这组事务的 任意一个串行执行将保持数据库的一致性，如果这组事务满足隔离性，则这组事 务的并发执行将与某个串行执行等价，那么这个并发执行也将保持数据库的一致 性。可见，事务的一致性和隔离性联合起来将使一组事务的并发执行保持数据库 的一致性。 事务处理系统主要通过一种称为日志的机制来保证事务的持久性，当一个事 务正在执行时，将该事务的更新操作记录在一个日志文件中。当系统处理事务的 提交操作时，首先要保证所有在日志中的记录已经存储在磁盘上，然后表明事务 已经确实提交且该事务的更新结果是持久的，可以立刻或者在将来合适的时候将 更新结果写入数据库中。然而，如果在事务提交之后并且在将更新结果写入数据 库之前系统发生故障，系统在重启后可以重读日志检查已经提交的事务的每个更 新操作，从而对数据库进行修复。 1 2 2 并发执行的正确性标准 一组事务的并发执行使它们的操作交织在一起，这样的一个执行称为历史 ( h i s t o r y ) 【8 】。历史指出事务中操作执行的相对次序，由于有些操作可以并行执行， 因此一个历史被定义为偏序( p a r t i a lo r d e r ) 。如果事务t 。指定它的两个操作的次序， 那么在任何包含t i 的历史中这两个操作必须以这个次序出现。一个历史还要指 定它所包含的发生冲突的操作的次序，当两个操作访问同一个数据项，而且至少 有一个操作是写操作，则称这两个操作冲突，用r ( x ) ( 或w i ( x ) ) 表示事务t ，对数 据项x 的读( 或写) 操作，t 的提交和中止分别记作c ，和a i 。下面给出文【8 中关于 事务并发执行的正确性标准的一些基本概念。 定义1 1 历史( h i s t o r y ) 一个定义在事务集t = t i ，t 。) 上的完全历史 h ，是一个由次序关系 “构成的操作的偏序： ( 1 ) h 2 u l t i ( 2 ) h u i ： t ； ( 3 ) 任意两个属于h 的冲突操作p ，q ，或者有p hq 或者有q hp 。 条件( 1 ) 表明h 包含t f ，t n 的操作，条件( 2 ) 表明h 保持每个事务中的 所有操作的次序( i 表示事务t i 中操作的执行次序) ，条件( 3 ) 表明在h 中的每一对 第一章绪论 冲突操作的次序是由 h 确定的。 定义1 2 等价( e q u i v a l e n t ) 如果两个历史h 和h ，满足下面两个条件，则称h 和h ，等价： ( 1 ) 定义在相同的事务集上，并且有相同的操作； ( 2 ) 以相同的方式处理已经提交的事务中发生冲突的操作，设p 和q 分别属 于已经提交的事务t i 和t j ，并且p 和q 冲突，如果p hq ，则有p 一q 。 定义1 3 串行历史( s e r i a lh i s t o r y ) 完全历史h 中的任意两个事务t i 和t i ，或 者t i 的所有操作在t i 的所有操作之前或者相反，则称h 是串行历史。 串行历史是并发执行正确性的基础，但是串行历史本身不是并发执行，利用 等价的概念得到并发执行的正确性标准可串行性： 定义1 4 可串行化历史( s e r i a l i z a b l e ( s r ) h i s t o r y ) 历史h 存在一个与h 等价 的串行历史，则称h 是可串行化历史。 1 2 3 正确性的判定方法 可串行性的判定一般是使用 行化 ( s e r i a l i z a t i o ng r a p h ) ，历史h 的串行化 图，记作s g ( h ) ，是一个有向图。该图的节点由h 中已经提交的事务构成，t i 的一个操作p 与t j 的一个操作q 冲突且p 在q 之前则构造一条有向边t i 斗t j 。 下面给出一个串行化图的例子： r 3 ( x 卜+ w 3 ( x ) c 3 舡一心么心 ? r 2 ( x ) 叶w 2 ( y p + c 2 。g ( h ，：t ： ：i ) t ， 可以利用串行化图判定一个历史是否是可串行化的： 定理1 1 8 1 历史h 是可串行化的当且仅当s g ( h ) 是无环的。口 这个串行化定理在证明一个并发控制机制的正确性时是非常重要的。 1 2 4 并发控制和恢复 并发控制机制的作用是控制事务的并发执行，保证并发执行的正确性。并发 控制机制一般利用锁、时标、串行化图等手段保证事务的一致性和隔离性，并发 第一章绪论 控制机制可分为两大类：悲观控制和乐观控制。悲观控制要求在执行一个事务的 数据访问之前要实现它与其它并发事务的同步，保证可串行性。乐观控制在事务 执行一个操作时不保证可串行性，当这些事务提交时再检查这些并发事务是否存 在冲突，如果没有冲突则事务提交。否则事务回滚。 在事务执行过程中，任何偶然的故障( 包括系统故障、磁盘介质故障和事务 故障等) 都可能导致事务的失败，使数据库处于不一致的状态。恢复机制的作用 就是当发生故障而使数据库处于不一致状态时，将数据库回复到一个一致性状 态。恢复机制一般采用日志( 1 0 9 ) 、重做( r e d o ) 和撤消( u n d o ) 等技术，从而保证了事 务的原子性和持久性。 关于恢复有两个重要的概念：可恢复的( r e c o v c r a b l e ) 和严格的( s t d c t ) t 8 1 。 如果满足下面三个条件，称t i 在执行中从t i 读取了x ： i t i 在t i 写x 之后读x ； 2 t i 在t i 读x 之前没有中止： 3 如果存在一个事务在t i 写x 和t i 读x 之间写x ，则该事务在t 读x 之前 已经中止。 t i 在执行中从t i 读取了某个数据项，称t 读取了t 。 定义1 5 可恢复的( r e c o v e r a b l e ( r c ) ) 历史h 中每个事务都在它所读取的事 务提交之后提交，则称h 是可恢复的。 定义1 6 严格的( s t r i c t ( s t ) ) 历史h 中若存在w j ( x ) o i ( x ) ( i j ) ，则或者有 a j 给出了实现语义( 对象语义) 可串行性的乐观并发控制算法和基于锁协议 的并发控制算法。 给出了一种同时利用事务和对象语义的长事务处理方法。 1 5 本文的组织 第二章介绍了事务的分解特性，给出一种帮助用户得到满足分解特性的分解 的算法。 第三章介绍了利用事务的语义的长事务处理方法，给出了正确性标准和基于 有向图的正确性判定方法，最后以此为基础给出了并发控制算法。 第四章介绍了利用对象的语义的长事务处理方法，重点介绍两种并发控制算 法。 第五章介绍了一种同时利用事务和对象语义的长事务处理方法，给出了正确 性标准和基于有向图的正确性判定方法，最后给出并发控制算法。 第六章总结了全文并对将来的工作进行了展望。 第二章基于语义的事务分解特性 2 1 引言 第二章基于语义的事务分解特性 随着数据库技术应用的普及，在一些新的应用中出现了长事务，由于长事务 的特点是长期占用资源，使得一些短事务被迫长时间等待长事务所占用的资源， 严重降低了系统性能。为此许多研究者提出了利用事务的语义信息将长事务分解 为多个事务步的解决方法，一个事务步结束后可以释放它所占用的资源，从而提 高了系统的性能。但这些研究基本上都是用于实现由开发者提供的事务分解的调 度，而很少关心事务分解应具备的特性和如何得到具备这些特性的分解。文【5 】 正是在这样的背景下提出了研究分解本身的重要性，并给出了事务分解所应具备 的五个特性，但它在判定一个分解是否具备这五个特性时，只能通过手工方式用 形式化证明来验证，若分解不具备这五个特性时，也没有给出解决办法。作者在 最后也指出这种方法离实用还有一段距离，要实现这种方法的自动化，还有许多 工作要做。针对文【5 】中这个遗留问题本章给出一种解决方法，对用户给出的事 务类型进行分类，找出可以分解的事务类型提供给用户，由用户对这些事务类型 根据实际需要进行分解。可以证明，由这种方法得到的分解将满足分解特性，从 而解决了文【5 中要用手工的形式化方法证明的问题。 为便于说明分解特性，引用文f 5 忡的一个宾馆数据库的例子，这个例子是 用z 规范语言 4 8 1 来描述的。z 是一种基于集合理论、一阶谓词逻辑和模式演算的 规范语言。表2 1 简单列出了在例子中用到的一些标记。 表2 ：l 自然数的集合 a 集合a 的幂 拌a集合a 的粒度 集合的差( 也称模式隐藏) a b b 向前用b 复合a x 卜_ v 有序对( x ，y ) a+b 从a 到b 的部分函数( p a r t i a lf u n c t i o n ) a mb 从a 到b 的部分单射函数 b a从关系a 的域中去掉集合b ab 值域为集合b 的关系a 第二章基于语义的事务分解特性 d o r a a关系a 的域 l a b a关系a 的值域 a ob 用函数b 覆盖( o v e r r i d d e n ) 函数a x 变量x 是一个输入 x !变量x 是一个输出 在一个操作之前的状态变量 x ， 在一个操作之后的状态变量 a a操作前后状态发生变化的模式a e a 操作前后状态未发生变化的模式a 2 2 事务分解的主要思想 事务分解是指将一个事务分解为若干步，如事务t i 可以分解为n 步( 通常 n 1 ) t 订，t i 2 ，t i 。，这些步应按顺序来完成被分解事务的所有操作，如需 执行事务t i 时，应首先执行t m 当t i i 提交之后，t 。2 才能开始执行，t 。2 提交之 后依次开始执行下一步，直到最后一步t 。提交之后才完成了t i 的所有操作。由 于每一步的执行都具有事务的原子特性，故称之为事务步。 事务分解为多个事务步后，该事务将不再具有原子性，原因是该事务可能提 交了部分事务步后中止。由于传统的向后恢复( b a c k w a r dr e c o v e r y ) 只能用于撤消 一个尚未提交的事务步已经执行的操作，而不能用于撤消已经提交的事务步，况 且被中止的事务已经提交的事务步可能对其它事务已经造成了影响，而且这些受 影响的事务可能已经提交，所以此时需要考虑利用向前恢复( f o r w a r dr e c o v e r y l 从语义上撤消被中止的事务已经提交的事务步。所采用的方法是执行一个为提交 的部分事务步定义的补偿事务步来从语义上消除已经提交的事务步所造成的影 响。详细分析请参见文 5 1 8 】 1 9 。 另外一个问题是事务分解为多个事务步后，使得该事务不再具有隔离性。原 因是由于一个事务可以提交它的部分事务步，而此时其它事务可以看到这个事务 提交部分事务步后的状态，从而破坏了隔离性。提交部分事务步的事务由于还没 有完成该事务的所有操作，因此可能使数据库处于不一致的状态，这样，其它事 务就看到了数据库不一致的状态。文【5 对于这个问题的解决方法是将分解之后 可能出现的不一致状态进行分类，分为用户可接受的不一致状态和用户不可接受 的不一致状态，具体是通过改写完整性约束集得到扩展的完整性约束集，使得每 个事务步执行前后都处于一致性状态或用户可接受的不一致状态。为了保证分解 的正确性，文【5 】给出正确语义历史( c o r r e c ts e m a n t i ch i s t o r y 见定义2 6 ) 的概念来 第二章基于语义的事务分解特性 保证分解的正确性。 下面给出文【5 】中的一个宾馆数据库的例子： 宾馆数据库有一个对象的集合，两个在这些对象上的一致性约束和三种类型 【g u e s t ，r o o m s t a t u s ：；a v a i l a b l eit a k e n t o t a l ：1t 图2 1 宾馆数据库的最初的规范 的事务。这里，假设有两个类型g u e s t 和r o o m ，分别用来列举所有可能的顾客 和所有可能的宾馆房间。全局变量t o t a l 表示宾馆中的房间总数。 在z 中状态和操作都是用一种称为模式的二维的表示法来描述，在模式中对 象声明出现在顶部，关于对象的约束出现在底部。在模式h o t e l 中定义了数据库 的状态并且列出了该数据库中的对象。自然数r e s 对当前的预定( r e s e r v a t i o n s ) 计 数。部分单射( p a r t i a li n j e c t i o n ) 函数r m 使g u e s t 和r o o m 联系起来，使得一个顾 客至多预定一个房间，一个房间也只能被一个顾客预定。当然，这些要求都可以 根据需要通过修改对象声明和约束来改变。部分函数( p a r t i a lf u n c t i o n ) s t 记录了 每个房间的状态。关于宾馆数据库中对象的完整性约束出现在模式h o t e l 的底部。 这里定义了两个约束： ( 1 ) # r m = r e s ：已经预定了房间的顾客( g u e s t ) 数目( r m 函数的大小) 等于预 定总数( r e 曲； 第二章基于语义的事务分解特性 ( 2 ) d o m ( s t t a k e n ) = r a nr m ：被占用的房间集合( d o m ( s t t a k e n ) ) 正是顾客( g u e s t ) 所预定的房间集合( r a nr m ) 。 宾馆数据库中有三种类型的事务：r e s e r v e ，c a n c e r ，r e p o a 。事务r e s e r v e 为 顾客g ? 预定一个房间并将所指定的房间r ! 作为输出。 r e s e r v e 的前提条件( p r e c o n d i t i o n ) 是： a ) 已经预定的房间数( r e s ) t j , 于宾馆的房间数( t o t a l ) ，即还有空房间； b 1 该顾客g ? 必须是一个新顾客。 r e s e r v e 的后置条件( p o s t c o n d i t i o n ) 是： a ) 选择一个状态为a v a i l a b l e ( 空闲的) 的房间r f ； b ) 预定的房间数增加1 ； c ) 房间r ! 的状态改为t a k e n ( 被占用) ； d ) 将有序对g ? 卜r ! 】j i l 入到函数r m 中。 事务c a n c e l 取消顾客g ? 的预定。 c a n c e l 的前提条件是g ? 是一个已经预定了房间的顾客； c a n c e l 的后置条件是： a ) 预定的房间数减l ( r e s 减1 ) ； b ) 从函数r m 的定义域去掉g ? ： c ) 顾客g ? 的房间的状态改为a v a i l a b l e ( 空闲的) 。 事务r e p o r t 没有前提条件，只是输出s t 和r m 。由于初始化的过程对后面 的分析无关重要，因此这里忽略了初始化的过程，而假设数据库已经被初始化为 一致的状态。 在这个例子中，数据库用一个对象的集合和在这些对象上的一致性约束或不 变式( i n v a r i a n t s ) 来表示，不变式是定义在这些对象上的谓词。在任意时刻数据库 的状态由数据库中对象的值确定，当对象的值满足所给定的不变式时，数据库的 状态就是一致的。 第二章基于语义的事务分解特性 事务是改变数据库状态的操作，与每个事务关联的是一个前提条件的集合和 一个后置条件的集合。前提条件限制了一个事务可以应用的数据库状态，即当满 足一定的条件时才能执行该事务，后置条件在一个事务完成后强制数据库进入另 一个状态，即改变了对象的值。前提条件和后置条件一起保证如果在一致性状态 下执行一个事务，那么事务完成后的数据库仍然处于一致性状态。 图2 2 一个简单的分解 ( a ) 标准的数据库状态分类 ( b ) 允许不一致状态的数据库状态分类 图2 3 数据库状态的分类 第二章基于语义的事务分解特性 图2 4 宾馆数据库的一个有效分解 - 1 4 第二章基于语义的事务分解特性 2 3 辅助变量 文【1 9 】中的s a g a 模型要求将事务分解后得到的每个事务步的执行都应满足 一致性约束，这个要求显然过于苛刻。 假设将事务r e s e r v e 分解为下面三个事务步： 步l ：增加预定的房间数； 步2 ：选择一个状态为a v a i l a b l e ( 空闲的) 的房间，并将状态值改为t a k e n ( 被 占用) ； 步3 ：将在步2 中选择的房间分配给顾客。 图2 2 给出了这种朴素( n a i v e ) 分解的描述。 由于n a i v e r l 增加了r e s 的值，而没有改变r m 的值，执行n a i v e r l 后将不 能满足# r m = r e s 。n a i v e r 2 改变了s t ，而没有改变r m ，得到的数据库状态不 满足# r m = r e s ，同时也不满足d o m ( s t t a k e n ) = r a nr m 。可见，这样的分 解在s a g a 模型中无法应用。 文 5 】放宽了一致性约束的要求，使那些执行后不能满足原来一致性约束的 事务步在满足放宽的条件下能够执行。图2 3 表达了这个思想。 s t 表示所有一致性状态的集合，s t = s t ：s t 满足i ) ，其中i 为初始的 一致性约束集。放宽i 得到一个扩展的一致性约束集为i ，要求事务分解后的每个 事务步在执行后都满足f ，s t 表示所有放宽后一致性状态的集合，s t = fs t ： s t 满足i ) 。图2 3 ( b ) 中的环表示了不一致但可以接受的数据库状态的集合。文 【5 引入了辅助变量( a u x i l i a r yv a r i a b l e s ) 来改写致性约束集i 得到i ，并且在每个 事务步中插入若干辅助变量，使每个事务步执行后都可以满足i 。如图2 4 所示 利用辅助变量对图2 3 的朴素分解进行了改写。下一节将介绍文 5 】所提出的分解 特性。 2 4 分解特性 2 4 1 复合特性 因为在事务步中插入辅助变量的作用是用来分析，而不需要实现，所以插入 辅助变量后的事务步序列应该与被分解的事务有相同的执行效果。下面介绍的复 合特性就是用来保证这一点的。 特性1 复合特性( c o m p o s i t i o np r o p e r t y ) 设事务t 的事务步序列为s s i 。，s t 是满足初始的一致性约束集i 的一个状态，则如果不考虑辅助变量，在 s t 上独立( i ni s o l a t i o n ) 执行事务步序列s ，s 。与在s t 上执行事务t 是等价 第二章基于语义的事务分解特性 的。 如果a u x 和a l a x 嚷示辅助变量，则用z 规范( s p e c i f i c a t i o n ) 语言来描述的复合 特性如下：l ( s i lg bs i n ) ( a u ) 【，a u x ) t i 。 这里的表示等价，从z 规范语言来讲是指等价符号两边可以得到相同谓 词定义的模式，从实现来讲是指两边执行了完全相同的操作。 等价符号的左边给出在初始状态满足i 的情况下同一事务的事务步复合并且 同时隐藏辅助变量，等价符号的右边是初始的事务。 2 4 2 敏感事务隔离特性 定义2 1 敏感事务( s e n s i t i v et r a n s a c t i o n ) 事务t 如果满足下面两个条件之 一，则称t 为敏感事务： ( 1 ) t 输出的数据将被用户看到； ( 2 ) t 输出的数据必须以一致的数据库数据为基础。 文 s f j i 入敏感事务的目的是用来保证用户不能在他们的终端看到不一致的 数据。由上面的讨论可知，在这个模型中允许事务访问不满足一致性约束的数据 库状态( 即s t is t 中的状态) ，但应该保证敏感事务不能看到不满足一致性约束 的状态。 特性2 敏感事务隔离特性即使敏感事务t 的分解可能访问s t s t 中的 数据库状态，但所有由t 。产生的输出数据与完全基于s t 中的一致性状态得到的 输出数据相同。 2 43 一致执行特性 如果一个事务步的前提条件没有满足或用户终止一个事务，或者系统崩溃， 则该事务将不能成功执行完成。此时会出现的一个问题是：在确定一个事务能否 完成之前，它的部分事务步可能已经提交。 假设事务r e s e r v e 在r 1 提交之后中止，应该有种机制来消除r l 造成的影响。 但是使用传统的向后恢复( b a c k w a r dr e c o v e r y ) 方法，由于r 1 已经提交，因此将 r 1 执行之前的状态保存下来是不可能的。而且因为其他事务的一些事务步可能 已经读取了r l 修改的值，所以这里只能采用向前恢复( f o r w a r dr e c o v e r y ) 的方法。 利用补偿事务步，从语义上消除已经提交的事务步r 1 造成的影响而不干扰已经 读取r l 的事务。 补偿事务步也是一种原予事务步，但与其它事务步不同，它不是用来完成一 个事务，而是从语义上消除一个事务已经提交的部分事务步造成的影响。将一个 事务t 分解为n 个事务步s s i 2 ，s 同时还需要定义n 1 个补偿事务 第二章基于语义的事务分解特性 步，记作c i 2 ，c i 。，补偿事务步c b 从语义上消除已经提交的事务步序列 s ，s 川_ ”造成的影响。这里所采用的方法与文【1 8 1 和【1 9 】中的表示方法不 太一样，在那里补偿事务步c “从语义上消除单个事务步s u 造成的影响，显然这 两种方法没有本质区别，为简单起见，这里采用文 5 q u 的表示方法。在前面的 例子中，事务r e s e r v e 的两个补偿事务步是c o m p r 2 和c o m p r 3 。 前面的宾馆数据库例子中的r 1 ，r 2 ，r 3 ，c a n c e l ，r e p o r t ，c o m p 2 和c o m p r 3 表示不同的事务步和补偿事务步的类型。由于历史反映了事务的实际执行，同一 个类型的事务步在实际执行的历史中可能有多个实例，因此应