嵌入式实时数据库系统事务模型及处理技术

3　嵌入式实时数据库系统事务模型

本章首先根据嵌入式实时数据库系统的特点，定义了具有时态特点的数据模型，在分析了事务对数据的操作特点后，提出了基于功能替代的实时事务模型FATM（Function Alternative Transaction Model），该模型定义事务为一组功能等价的替代，任意一个替代成功执行则该事务可以提交，所有的替代都夭折则该事务夭折，这种思想为事务的执行提供了多条路径，提高了事务的成功率，同时为多方案选择提供了语义支持，提高了嵌入式实时数据库系统的应变能力和可预测能力。由于嵌入式实时数据库系统常常在无人工干预的情况下运行，并且处理大量的硬实时事务，硬实时事务一旦夭折将造成系统损失，基于此，对FATM进行扩展得到支持补偿的实时事务模型FACTM（Function Alternative and Compensation Transaction Model），一旦硬实时事务不能在其截止期前提交，则调用其补偿任务，使该硬实时事务安全着陆，避免损失，即：具有补偿性的事务要么提交，要么因补偿而安全着陆。当然，并非所有的事务都是可补偿的，对于这些不可补偿的硬实时事务，系统应尽力保证它满足其截止期要求。

3.1　嵌入式实时数据库系统数据模型

3.1.1　数据分类

嵌入式实时数据库系统常常嵌入到大型设备或大型软件系统中，它与外部设备的接口有别于传统的商业数据库，除了用户输入数据外，还要接受其他设备（如传感器）传送的数据，经过系统处理，得到的结果常常需要触发某个外部设备的活动，如图3．1所示。

图3.1　数据的来源及结果

从数据来源看，嵌入式实时数据库系统所处理的数据主要来自于以下三类：一是外部设备。如来自于传感器的数据。二是用户输入。如由按钮、键盘输入的数据或来自于其他系统的数据库。三是外部数据。有一类重要的数据用于系统控制或其他目的，如串行图、日志等，这些数据不是用户数据，甚至不是传统意义上的数据库数据，但是，它们确实存在而且非常重要，称为外部数据；存取外部数据有利于提高事务成功率，有利于提高系统的可遇见能力和应变能力，这些能力对于嵌入式实时数据库系统而言是非常重要的。

从采集数据的时间上看，数据分为两类：一是周期性数据。很多传感器周期性地采集数据，如流水线控制。二是非周期性数据。非周期性地采集数据，如水库的水位控制。

从数据的有效性看，可以分为两类：

一是时态数据。二是非时态数据。

在嵌入式实时数据库系统中，并非所有数据都是永久有效的，即数据有自己的生命期，某些数据在一定的时刻后可能失效，如嵌入在汽车自动驾驶系统中的数据库系统，昨天的路况数据对于今天就是失效的。嵌入式实时数据库系统强调数据的有效性，一方面是某些数据确实失去了再利用的价值；另一方面也是为了减轻系统的负担，由于系统资源有限、体积较小，不可能如商业数据库系统那样保存大量的历史数据。因此，嵌入式实时数据库系统中的数据具有明显的时间性。

数据库中的数据对象可以是时态的也可以是非时态的，时态对象是随着时间的推移其值可能变得无效的数据对象，与值相对应的是一个时态有效区间；非时态数据对象的值不会随着时间的推移而改变。

从狭义上讲，生命期有限的数据具有时间限制，从广义上讲，生命期无限的数据也具有时间限制，该时限为＋∞。由此，可以用一致的方法描述所有的数据。

从数据来源和性态可进行以下分类：

①连续的数据对象。连续数据对象关系到随时间连续改变的外部对象，又分为以下两类：一是映射数据。一般而言，映射对象的值直接来自于传感器。二是演绎数据。映射数据可能在嵌入式实时数据库系统内部经过计算产生新的数据，称为演绎数据。

②离散的数据对象。离散数据对象是稳定的，不会随时间的流逝而失效，即其有效期接近于＋∞。

3.1.2　时态数据模型

传统的时态数据指被周期性更改的数据对象，如传感器采集的数据。我们对此定义做了扩展，时态数据指所有具有有限生命期的数据。

定义3．1：时态数据d是其值随着时间变化的数据。可形象地描述如下：

d：：＝＜S，TI＞

S：：＝｛valuei｜valuei（object，i＝1，2，3，…，n｝

TI：：＝｛TIi｜TIi（t TIi＋1，i＝1，2，3，…，n｝

TIi：：＝｛＜tbi，tei＞｜tbi≤tei∧tbiTb∧te∈e｝

Tb：：＝｛tj｜tjis a time of system，1≤j≤n｝

Te：：＝｛tk｜tkis a time of system 1≤k≤n｝

＜t：：＝is a temporal ordering

一个时态数据对象有多个版本，每个版本与一个时间区间TIi＝＜tbi，tei＞相关。该时间区间表示数据的有效期，其中tb是有效期的起点时刻，时态数据典型地反映了环境中的特定对象，如果该时态数据满足（δ是常量），则称之为周期性时态数据，通常被传感器事务周期性地修改。

时态数据对象d的第i个版本记为：d（valuei，＜tbi，tei＞），常常简记为di，其中，valuei是di的值，＜tbi，tei＞是valuei的绝对有效期，tbi是valuei绝对有效期的开始，tei是valuei绝对有效期的结尾，称为时态数据d的第i个版本的截止期，在此期间valuei是绝对一致的，在tei后valuei不再有效。

定义3．2：对于时态数据d，当且仅当成立，则称d是更新型时态数据，否则称d是终结型时态数据。

某些更新型时态数据的旧版本的截止期就是新版本的开始时间，典型的是传感器周期性地采集数据；终结型时态数据在超过数据截止期后没有新的数据版本，它有别于被删除的数据，该数据对象存在于数据库中，事务能访问到它，但是，其值已经无效。

系统中有大量的更新型时态数据（如锅炉的温度、水库的水位等），也有一些终结型时态数据；有些时态数据可能在某一段时期是更新型时态数据，而在特定时刻又变成终结型时态数据，比如，由传感器更新的时态数据，一旦系统中去除该传感器时，则该数据没有新的版本，但旧版本又失效了，事务既不能提交旧版本的处理结果，又没有新的数据版本可供使用。所以，我们不能笼统地说某时态数据是更新型时态数据，只能说在某时间段内，某时态数据是更新型时态数据。

设实时事务T的时态数据d，按事务识别时态数据截止期的时刻，存在以下几种情况：

第一，事务T开始时就已知其当前版本d（valuei，＜tbi，tei＞）的截止期，此类数据称为定时时态数据，它又有两种：

①周期性被更新的数据。如由传感器传输来的数据，其有效期间为：＜tb，tb＋δ＞，根据该时态数据的开始时间tb和周期长度δ，可以推算出其截止期te＝tb＋δ，此类数据是更新型时态数据。

②非周期性的时态数据。在事务T开始时，已经知道数据d的当前版本di的截止期te，此类数据可能是更新型时态数据，也可能是终结型时态数据。

第二，事务T开始时不知道d当前版本di的截止期，但是在T访问di之后且提交之前这段时间中，di已被其他事务更改，其截止期是被更改时的时间，此类时态数据称为非定时时态数据。

综合以上分析，时态数据可做如下分类：一是定时更新型时态数据。二是定时终结型时态数据。三是非定时更新型时态数据。四是非定时终结型时态数据。

在实时应用中，数据库中对象的值必须正确反映环境的状态，否则，依据数据库中该数据所做的决定就是错误的，存在潜在的危险。事务不仅要读新鲜的数据，而且是时态相关的，这就产生了时态一致性的概念，它包含两个部分：绝对一致性和相对一致性。

定义3．3：当且仅当数据d满足所有完整性限制和一致性限制时，数据d是内部一致的。

定义3．4：数据d满足时间限制时是外部一致的。

对于演绎数据对象y，∑ydi用于推导一个新的数据对象y，一个相对有效期rvdy与数据对象∑ydi的集合有关，因此，当数据对象y和集合中任意不大于相对有效期rvdy的数据对象的时间戳不同时，集合∑ydi有一个相对时态一致性，当∑ydi中的所有数据对象是外部一致的，并且∑ydi满足相对时态一致性时，演绎数据对象y的值是时态一致的。

定义3．5：一个连续数据对象是正确的，当且仅当对象值同时满足绝对和相对时态一致性以及完整性约束。

定义3．6：离散数据对象是正确的，当且仅当对象的值是逻辑一致的。

R是一个集合，其中每个元素是不同时态对象的版本。与R相关的相对有效期记为rvi（R）。R在时间t＞0时有一个正确的状态，当且仅当下列条件成立：

①满足所有完整性约束。

②R是时态一致的：

一是是绝对一致的，即：tb（di）≤t≤te（di）；二是R是相对一致的，即：

我们谈到事务T在时间t读数据d时，指T读d的时间t的绝对一致性版本。

在我们的嵌入式实时数据库系统中，当且仅当满足下列条件时，事务T提交：一是它是逻辑一致的；二是它满足其截止期；三是它读取时态一致数据集，并且在它提交时这些数据还是有效的。

3.2　实时事务的执行特点

实时事务有以下执行特点：

（1）与截止期有关的特点

按超过截止期的后果划分，实时事务可以分为以下几类：

①硬实时事务。硬实时事务一旦超过其截止期，将带来系统损失甚至灾难，这是我们应尽力避免的。

②固实时事务。固实时事务一旦超过截止期，则其价值立即为零并不再下降，即事务失去价值同时也不产生负面影响。

③软实时事务。软实时事务一旦超过截止期，则其价值逐渐下降，直到零，其后价值不再下降。

④非实时事务。非实时事务无截止期限制，其价值不随时间而改变。

（2）与到达方式有关的特点

按事务的到达时间划分，事务可以分为以下几类：

①周期性事务。以一定的周期循环地到达和被执行的事务是周期性事务，在嵌入式实时数据库系统中，大量的事务都是周期性的。例如，汽车自动导航系统中路况信息的采集，工业控制中，流水线上的传感器需要周期性地采集控制数据并进行处理，在股票交易系统中，也需要周期性的处理并显示最新股票行情。

②非周期性事务。非周期性事务是由外部事件或内部事件动态驱动的事务。比如，水库的水位到达一定的警戒线后，需采集相关（流量、闸门压力等）数据并做相应处理；嵌入式实时数据库系统中的数据容量饱和时需进行数据库重整，清除无效数据等。

③零星事务。偶尔地执行的事务，通常是非预先安排的，如即席查询。

（3）与数据存取方式有关的特点

事务对数据的存取方式大致分为读、写、修改，由此，按存取数据的方式，可将事务划分为以下几类：

①只写事务。某些事务只向数据库中写数据，比如，传感器事务只写映射数据对象，它们是只写事务；写日志的事务也是只写事务。

②只读事务。读取数据库中的数据并设置执行控制部件的参数的事务，是只读事务。

③修改事务。读取现有的数据值而导出演绎数据，并将这些演绎数据写入数据库中，这样的事务为修改事务。

（4）与运行时间需求有关的特点

按事务执行时间是否可预测，事务划分为以下几类：

①执行时间可预测的事务。由于嵌入式实时数据库系统采用内存数据库技术，在事务的执行过程中无I/O延迟，这为预分析事务的执行时间提供了便利条件。嵌入式实时数据库系统中的很多事务是预设的，其执行路径与外部环境无关，一旦启动便可按既定路径执行，这类事务可将其最坏执行时间WCET作为调度的参数。

②执行时间不可预测的事务。并非所有事务都像上述事务一样是可预测执行时间的，有些事务在执行过程中，需要采集来自外部或内部的参数，并且这些参数控制着事务的执行路径，如果我们无法预测这些参数的准确值，则该事务的执行时间是不可预测的。

综合以上特点，典型的实时数据库应包含以下类型的事务：

（1）1类事务

具有硬截止期的周期性事务，所有的数据和运行时间都假设能预先知道。由于1类事务只写连续数据，它只要求时态一致性，在合适的调度策略下可以保持其硬时间约束。根据事务担当的角色，1类事务可分为三个子类：

①1A事务。维护数据库的绝对时态一致性，它们周期性的将外部对象写到相应的映射对象中，1A类事务是只写事务并且只写映射对象（具有单一写的特性）。

②1B类事务。维护演绎数据的时态一致性，它们周期性地从一些数据（主要是连续数据对象）计算出演绎对象的新值，并且写到数据库中，假设一个演绎对象只有一个写事务。

③1C类事务。周期性的检索数据对象值并且将控制决定送给执行器或将被检索的数据显示在监视器上，它们是只读事务。

（2）2类事务

有严格的时间约束，该约束来自于其响应时间，而不像1类数据那样来自于数据的属性，但是它们不必是周期性的，不必预先知道其资源需求的优先级知识，可能串行化地访问离散数据对象，所以，我们不能总是保证2类事务的截止期。

（3）3类事务

不属于以上两类事务的事务，可能是软或硬实时事务，它们的数据和运行时间需求不总是已知的，它们可能访问连续数据和离散数据。

3.3　基于替代的实时事务模型

3.3.1　事务模型

为了在实时动态环境下提高嵌入式实时数据库系统的成功率，我们提出了支持功能替代性的事务模型，其意义体现在两个方面：

①嵌入式系统必须具备可预见能力，在尽可能无人工干预下透明地运行，要求实时事务应具备较强的对实时环境的应变能力，功能替代为此提供语义支持。

②以替代作为并发控制和调度的基本单位可以提高事务的成功率。

“功能替代”是指一个实时事务的执行有多种途径。我们曾定义实时事务由若干事务步组成［130，131］，现在让事务步包含一些功能等价的子事务（或操作），由于功能等价，这些子事务是可以相互替代的，只要其中有一个子事务能成功执行，则该事务步能成功执行，因此，对于一个实时事务，只要其每个事务步中有一个子事务成功执行，则该实时事务就成功执行，可以提交。

“功能替代”源于实时应用的需求。在实时应用中，对于紧迫关键的任务常常有多个方案以提高其成功率。一个典型的例子就是在现代国防防御系统中，为达到防御的目的，一个任务应有多种备选方案，以便任务的成功率提高到最高程度，进而在每个任务中可能有多个战略步骤，实现每个战略步骤又需要有多种子方案；另外，从事务执行所经历的路径来看，当一个事务由于资源竞争被高优先级事务抢占，或因其他原因运行失败而需要重启时，如果依然重复被抢占事务的原执行路径，而导致其重启的原因并没有消除，则势必造成再次重启。然而，如果该事务在重启时能选择另一条可替代的路径，则可能避开障碍而获得成功，从而提高了该事务的成功率。由此可见，为了提高嵌入式实时数据库系统的成功率，必须提供能支持功能替代性的事务模型。

一个具有时间限制的应用为一个实时事务，它由若干任务（或事务步）组成，为适应嵌入式环境高应变能力和高可靠性的要求，每个任务又由若干功能等价的子事务组成，在每个任务（事务步）中取一个也只取一个子事务所组成的集合称为该事务的一个“替代集”，一个替代集中各子事务按相应任务在事务中的顺序执行，则是该事务的一个“替代”。

定义3．7：事务步（任务步）定义为：

TK：：＝｛＜st＞｝

st：：＝＜SUBTRAN＞｜＜OP＞

OP：：＝＜OB－OP＞｜＜TM－OP＞

SUBTRAN：：＝＜TRANSACTION＞

其中：OB－OP和TM－OP分别表示数据库的对象操作（如插入、删除等）和事务管理操作（如BEGIN、COMMIT等）。

定义3．8：实时事务定义为一个四元组BT：：＝（TS，R，S，＜t）

TS＝｛TKi｜1≤i≤n｝；

TKi＝｛stij｜1≤ij≤ip｝

R：：＝（＜DR＞＜PR＞）

其中：DR和PR分别是一个数据资源集和一个处理资源（如CPU时间、缓冲区等）集；S是执行BT所需的约束；＜t是子事务（或操作）之间的时序。

定义事务由一组具有特定资源需求任务组成，这些任务之间存在一定的时序，并且要满足特定的完整性约束。例如：

TRANSACTION A1

SELECT a1，b1FROM xuesheng WHERE id＞19000001

…

UPDATE…

END TRANSACTION A1

在现实世界中，某些活动可能与其他活动是等价的，例如，某人在工商银行开了2个账户，在农业银行开有1个账户，当他要取款时，如果没有其他限制，则从任意一个存折上取款都能达到他的目的；再比如，一个人要从武汉到北京，他可以选择乘飞机、火车或汽车，甚至在中间（任务步）转车（或飞机），他还可以选择不同的路径：直接路径、转道。多方案的存在，使事务执行有多种选择，提高了成功率。

定义3．9：设TS＝｛TKi｜1≤i≤n｝为事务T的任务集，称：

（i＝1，2，…，n） 为任务TKi的功能等价子事务集；

③四元组FX＝（ff，FR，FC，＜t）为T的一个替代。

ff、FR、FC和＜t分别为关于FX的子事务集、资源需求集、约束集和时序。

其中：表示“功能等价”，E｜表示“存在一个也只存在一个”。

以上定义表明：事务A1包含了子事务B1、B2和C，其中B1和B2是等价的，只要执行其中一个便可。

从功能等价的角度，可以给出嵌入式实时事务的形式定义。(www.xing528.com)

定义3．10：一个实时事务是一个四元组T：：＝（FF，RS，CS，＜T）

实时事务T任一替代的成功意味着T的成功，即T通过任何一个FXi按子时序执行来实现，因此，实时事务处理的根本问题就是如何选择一个FXi在满足FRi和FCi的前提下按子时序来执行并使其成功，替代成为事务调度和并发控制的基本单位。

定义3．11：一个任务TK的度定义为该任务的功能等价子事务集SUB （TK）的度，即其中子事务的个数，记做Dg（TK）。

定义3．12：事务T的度定义为事务所包含的任务的个数。记为Dg（T）。

对于一个实时事务T，在每一个任务的子事务集中任取一个子事务执行，就能实现T的功能。分别由各任务的不同子事务组成的集合，在功能上是可彼此替代的，于是有以下定义：

定义3．13：一个事务的执行度定义为它的替代的个数，记做Dg（GT），有：

由此，一个实时事务实际上具有复杂的三维结构，而不是二维的层次结构（见图3．2）。换言之，实时事务由多个功能等价的替代组成，而替代又包含了多个子事务。

图3.2　实时事务结构示意图

3.3.2　实时事务的特性

实时事务具有的一般特性包括如下几个方面：

（1）时间约束

实时事务都有时间限制，典型的表现为截止期，按截止期的紧迫程度不同分为硬截止期、软截止期等，具有硬截止期的实时事务就是硬实时事务，具有软截止期的事务就是软实时事务。

（2）复杂的结构

实时事务具有复杂的结构，实时事务由一组子事务（事务步）组成，子事务又可能有自己的子事务，由此，事务内部和事务之间可能存在各种结构，如分层、嵌套、分裂、合并、彼此通讯等。

（3）事务之间的执行依赖性

①开始依赖。开始依赖表明某事务T的开始依赖于其他事务的特定状态，根据条件，开始依赖又分为以下几种情况：一是若T1开始，则T2必须先开始，称T1开始依赖于T2开始，记为T1BDB T2；二是若T1开始，则T2必须已经提交，称T1开始依赖于T2提交，记为T1BDC T2；三是若T1开始，则T2必须已经夭折，称T1开始依赖于T2夭折，记为T1BDA T2；四是若T1开始，则T2必须已经完成，称T1开始依赖于T2完成，记为T1BDF T2；五是若T1开始，则T2必须被阻塞而等待，称T1开始依赖于T2等待，记为T1 BDW T2；六是若T1开始，则T2必须已经失败，称T1开始依赖于T2失败，记为T1BDL T2……

②提交依赖。提交依赖表明某事务T的提交依赖于其他事务的特定状态，根据条件，提交依赖又分为以下几种情况：一是若T1提交，则T2必须先提交，称T1提交依赖于T2提交，记为T1CDC T2；二是若T1提交，则T2必须先夭折，称T1提交依赖于T2夭折，记为T1CDA T2；三是若T1提交，则T2必须先结束，称T1提交依赖于T2结束，记为T1CDF T2；四是若T1提交，则T2必须开始，称T1提交依赖于T2开始，记为T1CDB T2……

③夭折依赖。夭折依赖表明某事务T的提交依赖于其他事务的特定状态，根据条件，夭折依赖又分为以下几种情况：一是若T2夭折，则T1必须夭折，称T1夭折依赖于T2夭折，记为T1ADA T2；二是若T2夭折，则T1必须等待，称T1夭折依赖于T2等待，记为T1ADA T2……

④排他夭折依赖。排他夭折依赖表示事务的夭折与特定事务的状态有关，与其他事务无关。比如，T1仅仅只夭折依赖于T2，不会夭折依赖于其他事务，即：若则T1排他夭折依赖于T2，记为T1ADX T2。

（4）事务之间的相关性

实时事务之间的相关性主要表现为以下几种：

①结构相关。由事务的复杂结构引起的联系，如嵌套事务中父子事务的联系。

②数据相关。由不同事务共享数据而引起的联系。

③行为相关。由事务的数据相关性及在共享数据对象上的交互作用而引起的联系。

④时间相关。表明事务的执行顺序和紧迫程度。

3.3.3　替代的特性

替代是实时事务的组成部分，它能完成所对应的实时事务的功能，在特殊情况下，当实时事务由一个替代组成时，该替代就是一个实时事务。确切地说，替代是实时事务的一个特例。除了具有上述实时事务一般性质外，替代本身具有以下特征：

（1）功能等价性

由事务的定义可知，事务的替代FXi（1≤i≤n）是功能等价的，等价于T的功能。这包含了两层含义：一个实时事务T的替代是彼此功能等价的；任意替代与该事务T是等能等价的。功能等价性决定了系统可以调度实时事务T的任意替代来执行T，实时事务具有多个替代充分体现了其健壮性，大大提高了实时事务适应系统运行环境的能力。

（2）性能差异性

对于实时事务T：：＝（FF，RS，CS，＜t），由于集合元素的惟一性，有：

同一事务的不同替代FXi和FXj虽然功能等价，但它们在执行时间、占用的系统资源等方面一定存在差异，必然导致不同的替代之间存在性能差异。性能差异性表明“不同的替代适应不同的系统环境”。

理想的情形是系统能选择最适应运行环境的替代实施运行，为了使事务的成功率达到最高，最好是多个替代并发执行。至于执行哪些替代以及多少替代并发执行由系统的资源情况决定。

对于实时事务T，根据定义3．9和定义3．10及事务本身的语义，我们有：

其中，Ri、Ci分别为与任务TKi相联的资源和约束；Rij和Cij分别为与子事务stij相联的资源与约束。

（3）结构同构性

由于实时事务T的任意一个替代都是由T的各任务步中选取一个子事务而组成，因此，这些替代是同构的。

定理3．1：一个实时事务的所有替代在结构上是同构的，都同构于该事务。

证明：对于实时事务T＝＜TS，R，＜t，C＞，

首先定义一个代数系统：V1＝＜AA，＜t＞

AA＝TS＋R＋C

其含义是带有资源请求R和约束C的任务集，任务集间的时序为＜t，V1实际上是实时事务T的空间。

在该空间上定义函数h：h（TKi＋Ri＋Ci）＝stir＋Rir＋Cir

再定义代数系统：V2＝＜BB，＜t＞

BB＝ST＋SR＋SC

其中：ST＝stir

SR＝Rir

SC＝Ci （i＝1，2，…，n， r＝1，2，…，mi）

因为从各任务中选取的子事务的执行依然保持任务间的时序，故有：

h（TKi＋Ri＋Ci＜tTKj＋Rj＋Cj）＝h（sti1＋Ri1＋Ci1） ＜th（stj1＋Rj1＋Cj1）

即：h（AAi＜tAAj）＝h（AAi）＜th（AAj） 且h（AA）＝BB

所以 V1与V2是同态。

∵TKi＋Ri＋Ci≠TKj＋Rj＋Cj时，h（sti1＋Ri1＋Ci）≠h（stj1＋Rj1＋ Cj），

∴h是双射，于是V1与V2同构。

由定义3．9知，V2构成T的一个替代FXr，V1与V2是同构意味着实时事务T与其一个替代FXr同构。

再由于r的任意性，推导出不同的替代都与实时事务T同构，由此，定理得证。

（4）排异性

在单处理机系统中，如果不允许一个事务的多个替代并行，则排异性体现在实时事务每次只能有一个替代参与事务调度，只有当该替代夭折同时在时限许可的条件下，才可能使另外一个替代参与事务调度。

（5）事务执行时间的多元性

既然事务有多个替代，各替代的估算执行时间就都是该事务的估算执行时间，是由替代估算执行时间组成的一个多元组。

（6）事务的应变性

事务的部分替代夭折并不能使事务夭折，如果时间许可，还可从另外的替代重启。即：

其中，Run（T）表示执行事务T中正在运行的替代的集合，D（T）表示T的截止期，t0表示系统当前时间，SF表示平均松弛因子，et（FXj）表示FXj的估算执行时间。

事务在系统中的处理过程是：首先选择某些替代执行，如果它们成功则提交该事务，否则，进行时间判断，如果则可以启动这样的替代FXj，否则夭折该事务。与传统的事务不同，基于替代的事务可以绕开资源阻塞从另外的路径执行。

3.3.4　替代与实时事务的关系

事务由替代组成，替代与事务有着相辅相成的关系，主要体现在以下几方面：

（1）替代是事务的特例

这可从两个方面来理解：第一，由上所述，替代具有事务的一切性质；第二，当事务由一个替代组成时，该替代就是一个事务。

（2）替代与事务保持同构

当实时事务以任务为基本单位时，与替代在结构上保持着同构，即实时事务的任务模型结构与替代保持同构。用图3．3和图3．4描述它们的这种关系。其中图3．3表示一个实时事务，图3．4表示该实时事务对应的替代集。

图3.3　实时事务示意图

图3.4　图3.3所示实时事务的功能替代集

（3）替代开始依赖于事务

当系统调度到一个事务时，从事务中选取若干（一个或多个）替代，因此，只有当事务开始时，其替代才能开始。即：

Begin（T）→EFXi∈T Begin（FXi）

其中，Begin（T）表示T开始。

它说明：事务T开始意味着其替代开始，因为替代是事务的基本执行单位。

（4）事务成功依赖于替代

由于替代是事务的基本执行单位，只有某个替代完全执行该事务才能提交。

EFXi∈T Commit（FXi）→Commit（T）

其中，Commit（FXi）表示提交FXi。

（5）事务夭折依赖于替代

如果事务的所有替代夭折则该事务夭折。即：

其中，Abort（T）表示夭折T。

（6）替代具有与所属事务同样的截止期

替代只是为事务的执行提供多条路径，不改变事务的时间约束，所以，所有替代的截止期是相同的，等于该事务的截止期。

（7）替代的资源需求集合是事务资源需求集合的子集

由定义3．10知，为执行FXi所要求的资源，1≤i≤n｝

有：FRi＞RS

替代的资源需求是事务资源需求的子集，事务只需满足FRi就能运行替代FXi，而无须满足RS，这有可能减少系统资源耗费，减少事务受阻的机会，从而降低死锁的可能。

（8）替代保持事务与外界的某些联系（约束），如依赖性、时间一致性等

事务包含多个替代，使事务的内部结构更加复杂，但是在数据库系统环境中，事务依然作为一个整体保持与外界的联系，替代不会改变实时事务与其他实时事务之间的联系，包括事务之间的依赖性、一致性等。

3.4　支持补偿的实时事务模型

嵌入式实时数据库系统中，有些实时事务对外部环境做出即时反应，在它提交之前就有可能启动各种外部活动，对外部环境产生了影响，当该事务夭折时，无法通过传统意义下的“还原”（undo）来消除它所产生的影响，必须由“补偿”事务来完成这个任务。

替代提高了事务的成功率，但是并不能保证事务的绝对成功，当所有替代都失败或在其截止期前不能成功执行替代时，需要采取补偿措施，特别是某些不具备替代性的实时事务在失败时需要补偿。

在支持补偿的实时事务模型ACTM中，具有补偿性的实时事务包含主任务和补偿任务两部分。扩展上述实时事务模型，得到支持补偿的事务模型如下：

定义3．14：支持替代/补偿性的实时事务定义为ET：：＝（PT，CT，CC）

从定义可见，支持补偿性的实时事务由主任务、补偿任务和它们之间的补偿关系组成，当主任务夭折时，相应的补偿任务对它进行补偿，消除主任务的影响，该影响通常指数据库以外的影响，因为主任务夭折时，其数据操作结果不会写到数据库中。主任务是具备替代性的事务，而补偿任务是传统的实时事务集，所包含的这些事务不具备替代性，它们分别与主任务中特定的替代保持补偿关系，因此，存在以下关系：

换言之，对于实时事务T中的每个补偿任务，都存在替代与之保持补偿关系。但是，任意替代不一定存在补偿任务与之保持补偿关系，当补偿任务集为空集时，实时事务T是不可补偿的。

如果从主任务和补偿任务之间的对应关系来看，支持补偿的实时事务又可以做如下定义：一个支持替代/补偿的实时事务ET由一组功能可替代的任务组组成，每个任务组都能完成该实时事务的功能。一个任务组由一个主任务和相应的补偿任务组成，主任务可能是功能等价的替代集，它们按一定的时序执行图3．5描述的事务的结构。

ACTM的事务保持了实时事务的一般特性，此外，还有如下特性：

①主任务与补偿任务的对应关系。主任务与特定的补偿任务保持对应，即不同的主任务可能对数据库（外部环境）产生不同的影响，需要做不同的补偿。

图3.5　支持替代补偿的实时事务结构示意图

②替代与补偿任务的多对一关系。替代在功能上等价，因此，很可能不同的替代所需补偿是一样的。

③主任务不可缺省，补偿任务可缺省。一个实时事务中不能没有主任务，否则该实时事务就没有存在的必要，但是，它可能没有补偿任务。在实际应用中体现为：不是所有的动作都是可以补偿的。

替代与补偿从不同的侧面提高系统性能，在事务的截止期前，当事务的一个替代失败时可以选取其他替代继续执行，以此提高成功率，一旦事务到达截止期而又没有成功执行，则执行补偿任务，以此提高系统可靠性。