嵌入式数据库现状及事务模型处理技术

1　绪　论

嵌入式数据库系统的兴起可以归功于便携式计算设备的开发兴起。由于这些设备具有通讯能力，用户不仅用它们存储设备本身产生的大量数据，而且需要从中心企业下载资料以便脱线处理，因此，需要这些设备具备成熟的数据管理能力，所需功能常常如此复杂以至于平坦的文件系统不足以处理和操纵这些数据，这就促进了对嵌入式数据库的需求。

嵌入式数据库系统还可以嵌入到大型软件系统或设备中，存储和处理来自于所在设备和其他地方的数据，可以访问监视器、进行诊断以及进行其他工作。例如，“汽车制造商用嵌入式数据库获取关于汽车磨损、毁坏、行程里数和性能等的数据”，“化学植物公司的处理控制系统可以用嵌入式数据库记录通过探测器收集到的日志，这些数据可以下载到大型中心数据库以便改善处理过程”。这样的设备还包括具备上互联网（Internet）功能的智能手机（个人数字助理）、售货机等；智能装置和嵌入式系统也开始用嵌入式数据库，包括一些路由器和hub；嵌入式数据库系统不仅仅存在于时髦的移动设备或固定的灵巧设备中，也可以将嵌入式数据库系统用于成熟的应用环境，这些环境的资源对于今天的完整数据库管理包和需要很多资源的操作系统来说显得贫乏。总之，嵌入式数据库系统可应用于航天、航海、军事武器、工业控制、机器人等各行业以及汽车、家用电器等生活设施中，具有广泛的应用前景。

嵌入式数据库系统的设计目的，是在最小的干涉和最小的系统影响下进行数据存储和恢复。由于嵌入式数据库系统常常需要对环境做出实时反应，此概念建立在实时和近似实时的嵌入式计算中，应准确地称之为嵌入式实时数据库系统。

嵌入式实时数据库系统的研究尚处于初级阶段，目前未见成熟的产品，市面上有一些嵌入式数据库系统和实时数据库系统的产品，但是，嵌入式数据库系统基本上是传统商业数据库系统的剪裁，实时数据库系统在模型和并发控制机制上也并无新意，它们沿用了普通数据库系统的一些控制机制，或加以部分改造。

现在的问题是，一方面，目前的嵌入式数据库系统不具备实时性，但在实际应用中，常常要求系统对外部环境做出实时反应；另一方面，目前的实时数据库系统又由于难以保证高的成功率而不能适应嵌入式环境，因为嵌入式实时数据库系统的基本目标之一就是具有高的成功率从而具备高的可靠性，除此之外，嵌入式实时数据库系统还应该具备一定的主动性，能捕获特殊事件并做出相应反应，因此，严格地说，目前还没有真正意义上的嵌入式实时数据库系统。

嵌入式实时数据库系统同时具备实时性、主动性和嵌入式的特点，并采用了内存数据库的技术，它集成了实时数据库系统、内存数据库系统和主动数据库系统的处理技术。

1.1　嵌入式数据库的现状

嵌入式数据库市场一般不是直接面向用户而是面向设备制造商，设备制造商将嵌入式数据库系统嵌入到设备和应用中，在应用初期，嵌入式数据库主要用于提供对大型、数据密集性应用的数据管理，比如，Intuit′s Quicken金融管理软件。如今，设备中的嵌入式数据库可以与中心数据库通讯，具有与其他设备同步的功能（移动数据库）。

将嵌入式数据库产品分类成表1．1所示的关系型C/S产品、表1．2所示的面向对象C/S产品，以及表1．3所示的嵌入式程序库（它不需要单独的服务器处理）。这些产品各有优劣，因为不同的原因而流行，表1．3中只有gdbm不支持事务和一定程度的并发存取。

如表1．1所示的厂商提供C/S关系型系统。微软公司、Oracle公司、Sybase公司以及Informix公司研制并出售高级终端企业数据库系统和企业数据库引擎。

对于嵌入式系统开发者而言，C/S关系型产品十分流行，因为程序员们已经熟悉了SQL和关系数据库设计，缺点是客户机和服务器之间的通讯要花费额外的代价，并且为在嵌入式系统中安装、运行和维护一个独立的服务处理器增加了复杂度。

表1.1　关系型C/S产品

表1.2　面向对象的C/S产品

表1．2所示的产品似乎很适合嵌入式市场，但很少有人考虑，因为开发者为Unix设计了流行的面向对象数据库并且使它们建立在关于内存管理系统和通讯处理的有关假设上，难以与嵌入式OS接口。然而，可以证明它们可用于基于Linux的系统，比如，FreeBSD可以用于嵌入式设备。面向对象数据库系统之所以流行，是因为它们集成了C＋＋和JAVA程序语言，并且对应用程序员隐藏了数据库设计的复杂性，主要缺点是C/S通讯负担和很少的开发者支持嵌入式OS。

表1.3　嵌入式程序库

表1．3所示的为嵌入式程序库，它的系统直接链接到应用的地址空间，提供简单的语言级API而不是操纵数据的SQL。嵌入式程序库的主要优点是：

①快速执行，因为数据库操作不需要与隔离的服务器通讯。

②提高了可靠性，因为极少的部件运行在嵌入式系统上。

嵌入式程序库的明显缺点是：要求开发者精通非标准化的编程接口。

1.2　实时数据库系统的发展

实时数据库乃指事务和数据都可具备显式定时限制的数据库管理系统，系统的正确执行既要满足逻辑约束又要满足时间约束。同时满足这两种一致性要求的实时数据库事务的处理与传统的数据库相比具有更大的困难，事务处理中的众多不可预测因数的存在，以及时间约束与逻辑约束的并存导致实时事务的模型、调度策略和并发控制技术成为研究热点。

1.2.1　模型

关于实时数据库事务模型的演进成果较多，其中有代表性的有如下一些：

Kim建立了一个实时数据库事务模型，它包含硬实时事务和软实时事务，维护数据的时态和逻辑一致性，支持多担保级别。在这个模型下，它设计出一个集成的事务处理方案，提供实时数据库系统的预测能力和一致性，这样，系统中的每个应用被确认取得它们各自的性能目标（担保级），并且维持一致性需求。模拟实验表明：高确认级需要更多的系统资源，代价高于非确认事务。

Braoudakis采取不同的方法，将事务与一个价值函数关联。该价值函数表示时间约束以及所有的重要的系统使命，这个模型可以说明非实时事务、软实时事务、固实时事务和硬实时事务。此模型的特点是用一致的方法处理不同类型的事务，事务价值以及价值函数的观点被应用于两个实时系统以及实时数据库系统中，任务的价值在接纳该任务时被估算出来，根据任务的价值决定是否拒绝或移走一个已经被确认的任务；只要没有更高价值（严格的）的冲突任务到达，被系统接纳的任务有条件地确保完成其执行。

Zhou，Rundensteiner和Shin将面向对象的观点结合到实时数据库系统中，提出了ROMPP——一个实时的对象模型，其中用面向对象的框架探讨了时态和逻辑的一致性和正确性。

1.2.2　实时并发控制策略

在实际应用环境中，许多事务都带有时间特性，需要对特定事件做出定时反应，如：定时采样、在特殊的时间点或时间段检测水库的水位及闸门的位置等，这些工作是传统数据库系统难以胜任的，需要实时数据库系统（RTDBS）的支持。随着计算机速度越来越快，功能越来越强，使用范围越来越广，实时数据库系统越来越重要。例如，它们用于股票交易程序、电话转换系统、虚拟环境系统、网络管理、自动工厂管理、指挥和控制系统中。实时数据库系统是事务或数据带有显示的定时限制的数据库系统，其中带有显示时间限制的事务是实时事务，其典型的形式就是事务截止期。对于具有硬截止期的实时事务，必须在其截止期之前完成，否则其价值为零，甚至导致灾难。对于具有软截止期的实时事务，如果它在其截止期之前不能完成，则价值下降，但系统通常会允许它继续执行。

由于具有时间约束，我们不能沿用传统数据库系统的并发控制协议，因为它们强调所有事务具有平等的地位和相同的调度机会。对于实时数据库系统而言，为了使尽可能多的事务满足它们的截止期，应该将事务的时间信息加入到调度中来，事务越紧急应越早地投入运行。当一个事务正在运行时，如果新到了一个更为紧急的事务，该已执行事务应该让出处理机及对所有资源的控制权，使新到的紧急事务先执行。

具体来说，实时数据库系统中事务的并发执行具有以下特点：

①并发执行的事务具有时间约束和依赖性。实时数据库系统中的事务具有显示的时间约束，当它们并发执行时，事务之间可能存在与时间有关的依赖关系，比如，事务T1必须在事务T2开始执行之前（或提交前/后）开始/提交；一个事务在运行过程中可能触发其他的子事务，被触发事务与此触发事务并发执行，当触发事务完成时，可能不能立即提交，需要等到被它触发的事务也完成以便一起提交；等等。在传统数据库系统中，并发执行的事务间也存在关联，但主要是由于事务间通讯产生的，与我们所指的关联明显具有区别。

②必须满足硬实时事务的截止期要求，尽可能满足软实时事务的截止期要求。在实时数据库系统中，按截止期的特性将实时事务分做硬实时事务和软实时事务，系统必须保证硬实时事务的截止期，否则，该事务在截止期后可能对系统产生危害；同时，虽然软实时事务超过截止期后不会对系统产生危害，但该事务的价值也会急剧下降。由此，并发控制在保证数据一致性的前提下，为了满足事务的截止期要求，应区别对待不同特性的实时事务。

③一个正在运行的事务可以被更为紧急的事务抢占系统资源和CPU控制权。如上所述，当一个紧急事务到达时，为了处理该紧急事务，系统使正在执行（还未完成）的事务夭折，执行该紧急事务。

④由于必须保证事务的原子性，被抢占的事务夭折重启。实时数据库系统的事务与传统数据库系统中的事务相比，具有更为复杂的结构和更强的描述能力，它已不再是平淡的操作序列，典型的事务模型具有分裂结构、嵌套结构等，似乎不必维持事务的原子性。其实不然，从事务的整体角度上来说，由于事务可以嵌套（或分裂）甚至触发多个子事务，其原子性被破坏了，但对于组成该复杂事务的基本事务（子事务）来说，依然应保持原子性，因此，当一个基本事务被抢占后，必须重启。

⑤系统宁愿要及时的部分正确的结果，也不要过时的精确的结果。在资源受限的实时数据库系统中，并发事务竞争系统资源，当系统超载时，必然存在某些事务不能在其截止期内完成，对于某些实时应用环境，在截止期之后的精确结果是无效的。那么，在截止期内，即使得不到精确结果，如果能得到近似结果也比根本没有结果要好得多。比如，在交通管理系统中，为了合理调度汽车，保持各条马路负载的均衡，必须实时探测各条马路上的当前流量，如果不能在限定时间内得到查询结果，常常取一个模糊值作为调度的依据。

⑥事务处理的正确性不仅依赖于逻辑结果，而且依赖于逻辑结果产生的时间。在更多的情况下，用户需要得到精确的实时的计算结果，事务超过截止期后得到的结果可能和截止期前的系统状态相去甚远，其正确性得不到保证。比如，要求事务在3秒内计算机场上的飞机架次，如果该事务在4秒后完成，有可能在最后1秒内机场上增加了1架飞机。

⑦数据一致性标准有所放松。传统的数据库一致性标准是可串行化，并发控制的目的是保证数据的逻辑一致性，要求事务是平坦的，具有ACID特性。由于实时数据库系统必须满足数据的时态一致性和逻辑一致性，则此标准过于严格，因为在并发控制算法中，由于事务的重启和/或受阻可能导致无法预计的延迟。为了使尽可能多的事务满足截止期，需要放松正确性标准以满足或兼顾时间一致性要求，早期的努力集中于放松截止期的语义（主要是软实时事务和固实时事务，不能应用于硬实时事务）或事务的ACID特性（特别在可串行性方面）。比如，Kuo和Mok提出了建立在基于语义的正确性标准之上的并发控制策略。

一般做法是，在传统的乐观或悲观并发控制基础上，加以改造以适应实时并发控制的需要。典型的并发控制正确性标准有：

·ε—可串行化并发控制。ε—可串行化（Epsilon－Serializability）是事务处理中的一种正确性标准，它是一种更一般的误差受限的串行化。它允许不一致性数据被读取，并控制不一致性的程度，使误差量限制在一个指定范围，而使数据最终能达到一个一致性状态。ε—可串行化需要数据库的数据空间是一可度量空间，使用ε—可串行化放松逻辑一致性要求以期满足时间一致性要求。

·Δ—可串行性并发控制。Δ—可串行性是基于“相似性”概念的正规可串行性的扩展。相似性概念是指在时间和精确性上有略微差别的数据可以彼此替换地作为事务的可读数据。“相似”是内在地依赖于应用的概念，不同的事务对同样的数据对象可以有不同的相似性要求，两个值有多大的“微细差别”才能算相似，应依特定的应用而定。“相似”是一种二元关系，它是自反的、对称的，但不一定是可传递的。

·基于语义的并发控制。可串行化不是维护逻辑一致性的惟一方法，还可以依据事务在数据库中的操作语义将事务分类，使用兼容集而非可串行化作为正确性标准。在Rhode Island大学开发的RTSORAC系统中使用了基于语义的并发控制技术。

⑧评价并发控制协议性能的标准不是反应时间和系统吞吐率，而是满足事务截止期的比率，即系统的成功率。由于事务需要满足时间约束，其正确性标准也有别于传统的数据库系统，系统不能一味地追求吞吐率，必须将重点转移到满足事务截止期上，只有成功的事务才是正确的事务。

总之，传统的并发控制协议不能满足调度实时事务的要求，需要开发新的适合于实时数据库系统的并发控制协议。

（1）基于锁的并发控制协议

基于锁的并发控制协议主要有以下几种：

①基于优先级的两段锁协议2PL－HP。2PL是经典的传统数据库系统的并发控制协议，事务在读写数据对象之前，必须对此对象上锁，事务保持这些锁直到该事务完成（提交）才释放，如果锁请求被拒绝，则等待，直到持有锁的事务释放这些锁。对于实时数据库系统，两段锁需要使用基于优先级的冲突解决机制来保证高优先级事务不被低优先级事务阻塞。在高优先级机制中，所有解决数据冲突的方法倾向于高优先级事务。当一个事务以冲突方式申请被另一事务持有的锁时，优先级较低的持有者重启，优先级较高的申请者被授予锁；如果申请者的优先级低，它等待优先级较高的锁持有者释放锁。另外，只有当新的读锁申请者的优先级高于所有等待写锁操作时，它才可以加入一组读锁持有者，该协议被称为2PL－HP。

高优先级机制和传统的循环等待机制相似，它们都加入了两段锁来防止死锁。惟一的差别是高优先级机制使用由事务时间限制决定的优先级顺序来进行冲突处理，而循环等待机制使用由事务到达时间决定的时标顺序。很显然，如果优先级分派机制赋予事务惟一的优先级值，并且不动态改变并发事务的相对顺序，高优先级可作为一种死锁预防机制。

②2PL－WP。2PL－WP（等待升级）使用优先级继承机制来解决冲突。优先级继承是为了解决优先级倒置问题。使用这一策略，当优先级倒置发生时，持有锁的低优先级事务将以在等待锁的事务中的最高优先级执行，直到它释放锁。由于优先级的升级，它能够比没有优先级升级时执行得快，这样释放锁就很快。结果是，高优先级事务的阻塞时间可能降低。

然而，使用2PL－WP时事务阻塞的时间仍然不确定，因为数据冲突很高时，优先级继承实际上导致系统中大部分或所有的事务以同一优先级执行。在这种情形下，实时数据库系统的行为显著地降低到传统的数据库。实时并发控制算法的实验性能评价确认在高的数据冲突的情形下，2PL－WP的性能降得很快。Huag研究指明，综合高优先级和等待提升机制解决冲突具有较优的性能。它通常使用高优先级策略操作，只有锁持有事务接近结束时强迫锁申请事务等待，并且由于等待而出现优先级倒置时使用优先级继承。

③2PL－PC。优先级顶是解决优先级倒置的另一种方法。集成实时数据库系统中的优先级顶和封锁机制产生了2PL－PC。这种机制对于硬实时环境很有前途，因为它阻止死锁形成并且严格限制了优先级倒置产生的事务阻塞时间。然而，这种机制需要被每一事务存取的数据对象的优先级知识。这种情形在许多数据库应用中不适用，因为在很多情形下事务执行是数据依赖的，从并发度的角度来说，这一机制很保守。

④RPL。实时锁协议RPL使用上锁和动态调整串行化顺序来解决优先级冲突。串行化顺序调整的基本思路是推迟确定事务之间最后的串行化顺序，这有利于高优先级事务动态调整临时性的串行化顺序，这种机制能防止因事务的优先级顺序和串行化顺序不匹配而导致的阻塞和夭折。在RTL中，为了实现串行化顺序的动态调整，事务的执行和OCC中一样是分阶段的，第一阶段为读段，事务从数据库读数据并且写到局部工作区，然而，与OCC（冲突仅在确认阶段解决）不同的是：RTL在读阶段使用事务优先级解决冲突。在RTL的写阶段，决定了最后的串行化顺序，并且将更新永久地写到数据库。事务读阶段所依赖的控制和局部工作区的使用也提供了潜在的高并发度。

⑤基于资源预报的并发控制协议。ōZGR Ulusoy提出的并发控制协议强调资源预报，每个被系统接纳的事务向系统预报自己所需的资源，系统按事务的优先级提供服务。对于一个新到的事务，如果系统不能满足其资源要求，该事务必须等待，直到优先级高的事务释放了所需资源系统才将该事务投入运行，此方法没有死锁的可能。

（2）乐观并发控制协议

在乐观并发控制协议中，事务允许不受阻碍的执行直到它们到达提交点再对它们进行确认，这样，事务的执行包括读、确认、写三个阶段。关键是确认阶段，确认基本上分为向后确认和向前确认两种方法。在向后确认机制中，确认处理针对已提交事务；在向前确认中，事务的确认针对当前运行的事务。

①OCC－FV。如上所述，在实时数据库系统中，数据冲突的解决应该有利于高优先级事务，然而，在向后确认中，没有办法在串行化处理中考虑事务的优先级，因为它处理已经提交的事务，这样向后确认机制不能应用到实时数据库系统。向前确认解决冲突较灵活，正被确认的事务或者冲突的动态事务可能重启，所以它有利于实时数据库系统，而且，向前机制通常比向后机制探测和解决冲突早，资源和时间浪费较少。我们把使用向前确认的乐观算法称为OCC－FV。

需要指出的一点是，与2PL－HP不同，OCC－FV不使用事务优先级信息解决数据冲突，这样，在OCC－FV中，高优先级事务由于低优先级事务提交可能需要重启。已经提出和研究了几种用优先级等待或夭折机制将优先级信息加到OCC－FV中的方法。

②OPT－SACRIFICE。OPT－SACRIFICE是一个乐观协议，它使用优先级驱动夭折来解决冲突。在这个协议中，一个事务到达确认阶段时，如果一个或多个冲突事务比确认的事务优先级高，它就夭折；否则，它就提交并且所有冲突的事务立即重启。该协议以这样的方式使用事务的优先级：确认事务为了与它冲突的高优先级事务而牺牲自己。在这种机制中，采用向后确认的乐观协议，在确认事务大部分执行后，可以结束夭折（排除夭折），因为冲突的高优先级事务仍然在读段。这种机制的另外一个问题是无效牺牲。所谓无效牺牲是指一个事务为之牺牲的是后来被删除的事务。

③OPT－WAIT。在OPT－WAIT机制中，当一个事务到达确认段时，如果它的优先级在所有的冲突事务中不是最高的，它就等待具有较高优先级的事务完成，这一协议使较高优先级的事务首先满足截止期。一个确认事务等待时，可能由于具有较高优先级事务之一的提交而重启，因为优先权给了高优先级事务，这一机制保持了实时冲突处理最初的目标。值得注意的是，该机制中没有无效重启，因为所有的重启是根据要求而做的。

如果一个事务等待一段时间后最终提交了，它导致具有较低优先级的事务在后来某时间重启，从而降低了这些事务满足截止期的机会，这就浪费了资源；随着导致瀑布夭折的阻塞链的形成，这一问题更严重。另外，一个确认事务等待时，新的冲突可能发生，从而使冲突事务的数目和夭折的机会增加。

④WAIT－50。在WAIT－50机制中，只要与之冲突的事务有一半优先级较高，该确认事务必须等待，否则，它就提交，并且如OCC－FV一样，所有冲突事务立即重启。WAIT－50机制的基本观点是最大化阻塞的正面影响，而减少负面影响。

我们很难笼统地对这些并发控制的性能进行排序，因为，它们都有各自适合的环境，一个并发控制协议在一种运行环境下表现出优良的性能，可能在另一种运行环境下的性能却不尽如人意。

衡量实时系统性能的标准的主要指标是系统成功率。即系统中成功提交的事务数与系统接受的事务总数之比。通常有3种性能比较方法：一是基于真实实时系统的性能比较；二是基于模拟的性能比较；三是基于分析的性能比较。不管使用哪种性能比较方法，得出的结论是一致的。

其一，有限资源的条件下，所有的事务是软实时事务。实验表明，OCC －FV比2PL－HP饱和稍微早一些，并且具有较差的平均延迟时间性能，原因是OCC－FV的重启数略高。当系统受资源数量所限时，重启的数目对于系统的性能有显著的影响，因为随着重启增多资源冲突也增多。由于基于重启的高优先级机制失去了一些基本的阻塞因素，2PL－HP部分使用阻塞来解决冲突，并且在有限资源的情形下执行比OCC－FV好，2PL－HP性能较优的另一个原因是它探测冲突比OCC－FV早。

其二，在软实时和无限资源的条件下。假定延迟事务比正常事务的优先级高。实验表明，在一定的工作负载点，两种算法的丢失百分比和平均延迟时间剧烈增加。因为没有资源冲突，剧增仅由数据冲突引起，我们称为数据冲突剧增（DC）。进一步分析可知：在乐观协议中，所有的数据冲突通过重启解决，剧增的原因是重启。如果数据冲突级很高，那么，事务忙于重复重启，事务就没有任何进展。

在这种无限资源的条件下，OCC－FV在丢失百分比和平均延迟时间方面的性能较优。随着负载增加，两种算法之间的性能差异变大。可以推断，在无限资源情形下OCC－FV优于2PL－HP。

其三，在硬实时和有限资源情况下。实验显示了在系统负载范围很广的情形下两种算法的丢失百分比：对于每秒10个事务的低到达率，两个协议没有明显的不同，随着到达率增加，OCC－FV确实比2PL－HP优。

实验中OCC－FV比2PL－HP的重启数少，从而能够较好的利用资源，2PL－HP因无效重启引起性能下降，随着负载增加，性能下降更快，因错过截止期而必须删除的事务数增加。

这里要注意的一点是，在某一负载级以后，两种算法的重启数目降低，这种降低的原因是在那个负载点之后，删除丢失截止期事务时，资源冲突和数据冲突减少。

其四，在硬实时和无限资源条件下。实验表明，在系统负载范围很广的固实时系统中，OCC－FV优于2PL－HP。一般地，随着系统可用物理资源的增加，两个协议之间的性能差别增加。

（3）实时事务的调度算法

简单地讲，调度就是给出事务或任务执行的一个排序（编序），不同的系统目标有不同的调度算法。传统数据库系统追求的目标是系统吞吐量及平均响应时间，而实时数据库系统追求的目标是单个事务定时限制的满足及全系统满足定时限制事务的比率最大。事务的调度是一个NP难度问题，依据实时事务的特点，研究人员提出了各具特色的调度策略，归纳起来，最具代表性的有：

①最早放行最优先（ERF—Earliest Release First）。该策略将最高优先级指派给具有最早“放行”（release）时间的事务。所谓放行时间就是事务可以开始执行的最早时间，与此相连的有事务到达（Arrive）时间、事务接纳（Admission）时间。这三者是有区别的。事务到达时间就是事务进入系统或在系统中生成的时间，而进入系统的事务并不能马上执行（往往在磁盘上），还要为其分配数据及代码所需要的内存等，取得这些资源的事务才被系统接纳，接纳后的事务也不一定就能立即执行，因为可能与其他事务在时间上存在相关性而要被“扣留”一段时间，在过了这段时间之后才能被“放行”而调度执行。有时就以接纳或到达时间考虑，若如此，ERF策略就是通常的“先来先服务”（FCFS）策略。

ERF策略的主要优点是简单，而主要缺点是它根本不管事务的截止期，歧视截止期紧迫而放行晚的事务，特别优待那些没有那么紧的截止期而更老的事务，这对实时系统显然是不合适的。一种非常适合ERF的场合是大多数事务具有同样的价值函数，且截止期自放行时间起都是一定长的时间，在这种情况下，事务按放行时间排序基本上也就等价于按截止期排序，如银行和航空订票事务处理系统就可采用该策略。

②截止期最早最优先（EDF—Earliest Deadline First）。具有最早截止期者优先级最高，这是一种获得广泛应用的调度策略，其主要缺点是它让已过或几乎要过截止期者获得最高优先级，而这种事务无论如何不能满足其截止期，这显然不合适。

③可达截止期最早最优先（EFDF—Earliest Feasible Deadline First）。具有最早的可达截止期者优先级最高，所谓一个事务T的截止期是当前时间“可达到”的，乃指t0＋（et（T）－P）≤D。这里t0为当前时间，et（T）、P分别为事务T的执行时间估算和已执行时间，D为其截止期。如果所有的事务都具有不可达截止期，则按EDF指派优先级。这样具有不可达截止期的事务可不必立即夭折。因为一方面E和D都留有余地；另一方面它还有机会（当系统没有可达截止期的事务时）获得服务，这对软实时事务很有用。此外，EFDF策略显然克服了EDF的缺点，是其改进版本。

④空余时间最短最优先（LSF—Least Slack First）。事务T的空余时间S ＝d－（t0＋E－P），即推迟t的执行而仍然能满足其截止期的可推迟时间量估算。该策略将最高优先级分派给具有最短空余时间的事务。要注意LSF与EDF和EFDF两者都不一样，它考虑了当前时间与剩余执行时间估算，因此，随事务的停止执行，其优先级动态上升，而若事务在执行，则因当前时间t0与事务的已执行时间P同步增加，故S不变，因而优先级也不变。该策略也有类似于EDF的缺点，同样可限制S≥0，即只考虑可达截止期情形。

⑤价值最高最优先（HVF—Hightest Value First）。每一事务有一价值函数，其值最大者最优先。问题是如何合理地构造价值函数，一个例子是：

V（t）＝c（w1（τ－τs）－w2d＋w3P－w4S）

其中：t0、d、P、S的意义同上，c、τs分别为t的危急度、开始时间，wi （i＝1，2，3，4）为加权因子。

⑥价值密度最大最优先（GVDF—Greatest Value Density First）。价值密度（Value Density）函数为：

即事务完成时的期望价值与实现该价值所需计算量的比最大者优先级最高。显然，对于期望价值一样的事务该策略偏向较短者，因为它每单位消耗时间所获得的价值更大，与上面的HVF策略一样，这里也有如何设计价值函数的问题。

不难看出，RTDB中优先级分派策略一般均要考虑事务的截止期。对于一般的事务，其截止时间可由用户给定或由系统根据用户的要求来计算。对于嵌套事务，如何根据根（父）事务的时间特性确定后代（子）事务的截止期进而确定各自的优先级是一个比较复杂的问题。

⑦速率单调分析（RMA）。RMA是一种统计性的对周期性硬实时事务进行调度的算法，它要求预先知道数据对象和事务的执行时间，最高优先级赋予具有最短生命周期的事务。

⑧非精确调度（Imprecise Scheduling）。非精确调度放松了传统调度标准，有“滤网法”（sieve）和“里程碑法”（miletone）两种非精确调度方法。滤网法要求系统提供多个算法，并且提供的算法具有所需执行的时间与结果的精确度呈正比的关系，即时间越长该算法的结果的精确度越高。里程碑法要求系统提供的算法是可以分割的，执行到每个分割点（或里程碑）都可以给出近似的结果，随着更多的分割点被执行，系统的结果也越来越精确，显然，里程碑法的算法必须是可重入的。

⑨多标准调度（Multi－criteria Scheduling）。多标准调度的目标可以基于多个标准，如实时数据库中尽可能地满足时间约束和逻辑约束。

1.3　内存数据库研究现状

20世纪80年代中期以来，主存数据库系统引起了越来越多的数据库研究者们的极大兴趣，时至今日，人们已对它的体系结构、数据组织与存取方法、事务处理、并发控制、恢复技术等方面进行了大量的探讨与研究，取得了丰富的成果。在体系结构方面，为了支持主存数据库系统的恢复，人们从系统硬件、软件支持上入手，开发了新的体系结构，比如，使用多处理机结构，一个处理机专用于有关恢复方面的处理；以专用的NVRAM做活动日志、工作区等。

与磁盘驻留数据库相比，虽然内存数据库可以提供更加快速的响应时间和更高的吞吐率，但它具有易失性，因此，需要更加强有力的恢复机制，有关这方面的工作取得了一些进展。

内存数据库的恢复机制一般基于两种技术：一是基于日志的恢复技术；二是基于影子页的恢复技术。

在基于日志的恢复机制中，事务处理产生的所有数据由日志保留，一旦系统崩溃，使用磁盘上的日志文件进行恢复处理，但磁盘读写降低了系统效率。为了解决这个问题，可使用“预提交”协议，即事务提交时，只要有关的日志记录写入固定的缓冲区，即可释放事务的锁，而无须等日志写入磁盘后，这样，可以减少阻塞延迟，加速并发控制事务的响应时间。另外，可以使用非易失性的内存作为日志缓冲区，还可以过滤日志减少日志数量。

在基于影子页的机制中，在事务生命期内，数据库为每个页维护两个映象：当前页和影子页。在事务开始时，标识两个页，影子页在事务运行期间不改变，当前页有可能被事务的写操作改变，系统崩溃时，影子页用于将数据库恢复到崩溃前的正确状态。其优点是快速高效，缺点是需要额外空间维护影子页和大量的页表指针，需要频繁地清理垃圾。有些方案试图结合以上两种技术，但效果不适合实时数据库。研究表明，对内存数据库而言，影子页技术比日志技术更好。

在存取方法方面，人们开发了许多新的、有利于内存数据存取的数据存储组织与索引结构及存取策略，链接桶哈希（CBH）提供了快速随机存取稳定文件的能力，但是不适合动态文件，因为它需要哈希表的全局组织以便扩展或收缩其地址范围。改进的线性哈希、受控搜索多方向哈希、可扩展链接桶哈希，T＊树和Hybrid－TH树对此做了改进。

在事务处理方面，主要在事务的提交及与之相联的日志记录、查询优化，尤其是链接查询的优化等方面，进行了多方面的研究，开发了一些有效的技术。(www.xing528.com)

在并发控制方面，人们提出了二级层次封锁方案、乐观并发控制法，但究竟哪种方法更适合主存数据库系统，目前还没有定论。有的用简单2PL协议，有的认为在主存数据库系统中不需要并发控制，而用“完全串行”执行，但是，串行执行对短事务也许可行，但对长事务则不合适。

1.4　主动数据库研究现状

传统数据库系统是“被动的”，因为仅当用户或应用程序“要它动时，它才动”，它只能对现存信息进行处理，而主动数据库能够主动监视当前信息，推断当前还不存在的、未来的状态的出现，一旦这些状态出现能启动相应的活动（或程序）。诸如自动化生产、控制和通信系统、电力或数据网管理、证券交易系统等，其数据及应用活动有很强的时间性，并且要求能自动监视特定的情形和活动、及时感应当前外部环境、能自动采取相应的行动。现代应用的需求使得实时主动数据库的研究成为数据库研究领域的重要热点。

主动数据库的研究热点集中在主动规则的设计，主动规则源于AI知识表示的产生式系统，将其引入数据库系统，不仅增加了数据库的知识表示和推理能力，也改变了事务的响应执行方式。主动规则在实时数据库系统中的重要应用还包括实时系统的资源管理、实时事务的接纳控制（Admission Control）以及实时事务的应急措施（Contingency Plan）、实时事务的预分析预处理等。集成于实时数据库中的主动规则，一般使用ECA（Event－Condition－Action）规则模型，同时对规则模型增加时间约束的表达和处理能力，并规定主动规则触发执行的优先级，保证规则执行的可终止性和结果的确定性。

然而，主动实时数据库中存在一个不可回避的矛盾：一方面，实时系统是反应式系统，需要主动规则系统的支持；另一方面，用于反应式行为的主动规则的触发执行，将影响实时事务的完成时间。

“主动能力”很早就被用于表示具有数据视图的自动更新以及数据完整性、一致性的自动维护机制等，但这只是用于数据库管理系统本身功能的实现与加强，不能直接支持应用语义的主动性要求，谈不上真正的“主动数据库”。进一步的发展是直接支持显式的主动应用语义，如用于实现监控、报警（alert）等。实现上述功能的早期系统包括POSTGRES以及其他关系数据库管理系统Ariel、Starburst、STRIP等。后来，集成具有反应式系统行为的数据库管理系统相继出现，著名的有HiPAC、SAMOS（Universitat Zurich），其他主动面向对象数据库系统的还包括Ode（AT＆T）、REACH（Technical University of Darmstadt）、ACOOD以及DeeDS（University of Skovde）。其中HiPAC、REACH和DeeDS主动数据库系统还集成了对时间约束的处理，从而具有实时主动数据库系统的特征。

主动数据库系统的特点主要通过其实现的规则系统的特征来体现。规则系统具有如下特征：一是主动规则由事件驱动，典型的是由事务引发的状态变迁或操作触发；二是主动规则的执行语义与数据库事务的执行语义一致，通过事务的执行来反映规则的执行；三是主动能力被DBMS集成为统一的机制，主动规则作为一类共享数据由系统维护，支持DBMS和应用两者的功能。

主动数据库的规则模型一般使用ECA模型，上述三个规则部件的不同组合使得规则的表现形式各有不同，主要有以下三种形式：一是EC－A形式：定义规则时，仅需要声明条件（Condition）和活动（Action）部分，事件（Event）的声明是隐式的；二是E－CA形式：规则的三个部件均需要声明，但作为活动的先决条件与活动成为一体，省略了规则的条件评价和规则执行之间的耦合方式，耦合方式相关于规则的执行语义；三是E－C－A形式：规则的三个部件均需要声明，还要提供E－C以及C－A之间的耦合方式。

主动规则能力与所支持的事件相关，上述所有的主动数据库系统都支持数据库事件，HiPAC和ETM系统不支持外部事件的概念，HiPAC和POSTGRES系统支持时间事件和复杂事件，Starburst系统也支持复杂事件。它基于关系数据模型，支持面向集的规则，其规则执行语义还考虑了规则或事务执行的一系列操作的“纯效果”。

数据库产生式规则语言来源于人工智能的产生式规则语言。一般来说，人工智能的产生式规则具有形式：“pattern→action”，这类规则被称为基于“模式”（pattern－based）的规则，当工作存储器中的数据与“模式”匹配时，规则被触发。由此可见，基于“模式”的规则语言通常都隐含这样的假设：“仅当工作存储器中出现匹配的新数据时，规则处理器才进行处理”，因此，规则隐含地由事件触发。数据库中的规则语言ECA与人工智能中的规则语言之间最主要的不同是：“数据库中的规则显式地定义了触发事件”。

（1）HiPAC规则

ECA规则模型首先在HiPAC项目中被提出，HiPAC中的规则系统具有丰富的表达能力和执行语义，这种规则具有如下形式：

on ＜Event＞

if ＜Condition＞

then ＜Action＞

该类规则被称为基于“事件”的（event－based）规则。当“事件”发生时，规则被激活，一旦规则被激活，“条件”将被评价（相当于进行模式匹配），如果“条件”被满足，那么，相应的“活动”（action）被执行。

系统的主要特征有：

①规则支持的事件包括“数据库事件”、“时间事件”、“外部事件”及“复杂事件”；

②规则执行方式包括“立即”、“推迟”和“分离”耦合方式；

③支持规则的串联触发执行；

④使用嵌套事务模型实现多规则的并发执行。

HiPAC规则系统中使用嵌套事务模型，触发的规则作为子事务执行，但子事务之间没有控制结构，这意味着子事务可按任意的次序串行执行或并发执行，这将导致规则执行的行为难以控制和理解。随着规则集的增大其规则的终止性与执行结果的确定性无法保证。

系统HiPAC扩展为规则处理，有三种耦合方式，分别对应于规则的条件评价和活动执行的三个可能的时间点。

①“立即”触发。它是基本的耦合方式，触发事务或规则被挂起（suspend）并等待被触发的规则执行完成，在被触发规则执行完成后，解挂等待的触发事务并调度执行。

②“推迟”触发。被触发的规则将推迟到触发事务的提交点执行，即：被触发的规则并没有在事件的发生点立即执行，而是被推迟到触发事务的提交点执行，在触发事务的提交点，先让被触发的规则完成执行再提交。

③“分离”触发。被触发的规则作为一个独立的事务执行，“分离”触发方式增大了事务执行的并发度。“分离”触发方式还可以进一步分为：“无因果依赖”的分离方式（causally independent）和“有因果依赖”的分离方式（causally dependent）。在前一种情形中，无论触发事务是否提交或夭折，不影响被触发事务的执行；在后一种情形中，触发事务必须在被触发事务结束之前完成。这种对分离触发方式的进一步分类是基于实际应用考虑的。例如，在实时系统中，触发事务对实际环境的控制是不可逆的，即：事务的夭折不可能撤销被触发事务对实际环境已产生的影响，因而可进一步规定：在触发事务完成后，被触发事务才可执行。

对触发耦合语义更详细的讨论，包括“条件”评价和“活动”执行使用各自独立的耦合方式，即E－C耦合和C－A耦合，可能的组合有7种（见表1．4），它们都必须满足“条件评价一定在活动执行以前实施”的约束。

表1.4　耦合方式的不同组合

①条件评价和活动执行都使用立即耦合方式，在事件发生后立即执行。（立即，立即）

②条件评价使用立即方式，而活动执行使用推迟方式。（立即，推迟）

③条件评价使用立即方式，而活动执行使用分离方式。（立即，分离）

④条件评价和活动执行都使用推迟方式。（推迟，推迟）

⑤条件评价使用推迟方式，而活动执行使用分离方式。（推迟，分离）

⑥条件评价和活动执行在同一独立事务中执行。（分离，分离）

⑦条件评价在一独立事务中执行，活动执行在另一独立事务中被执行。（分离，分离）

当规则活动被执行或者规则条件被评价时，触发其他规则的事件可能被引发，这导致串联触发情形的出现。在最坏情形下，串联触发可能形成环，从而导致规则触发执行的不可终止性。通常规则系统应该提供规则分析工具，尽可能地发现和避免那些潜在的不可接受的串联触发情形的出现。但是，完全避免不可终止性的惟一方法是对触发的深度加以限制。在极端情况下，可以完全不允许串联触发的发生，然而这种强行中断串联触发可能导致数据库的不一致，以及规则处理语义的混乱。

当规则事件发生时，可能触发规则库中的多条规则，如何决定哪一条规则被执行（或规则执行的顺序）的过程称为“冲突解决”。冲突解决需要集成考虑以下的情况，如规则执行是独立于数据库的应用程序，还是与应用程序融为一体；数据库操作是面向集的还是面向实例的，是否应该把不可分的事务思想包括进处理的循环中等。

（2）Starburst规则

Starburst规则系统仅支持数据库事件，并且在规则定义中增加precedes 和follows子句，这些子句规定了规则执行的次序（在冲突解决策略中使用），其规则语言的语法如下所示：

Create rule name on table

When trigger－operations

［if condition］

then action－list

［precedes rule－list］

［follows rule－list］

执行语义简单表述为：在触发事务结束时，从被触发的规则集中选出一合适的规则执行（合适的规则是指：规则的条件评价为“真”，并且不冲突于precedes和follows子句的次序要求。若有多个规则是“合适”的，则仅触发一个规则执行）。此规则的执行可触发其他规则甚至本身，当此规则执行结束，继续在新的触发规则集中选出下一个“合适”的规则。Starburst规则不支持时间事件、执行方式仅相当于“推迟”耦合方式，虽然支持串联触发，但非嵌套结构。

由此可见，Starburst系统强制规则按串行方式执行，使得可并发执行的规则只能串行执行，这将影响系统的效率。

（3）基于图的规则语言

基于图的规则语言的主要思想是基于简单CA规则执行的时间关系，引入“依次关系”S（Sequence）、“同步关系”Y（Ynchronization）与“并发关系”P（Parallel），将多个CA规则按时间语义关系组成“规则图”RG（Rule Graph），相同的规则集可对应不同的RG，分别联系于不同的事件，从而形成一种E－RG主动规则。

E－RG主动规则具有以下特点：

①由最基本的时间关系引入了规则图RG中的控制结构（S、Y和P关系）。

②避免由规则任意并发执行而导致的规则行为难于控制和理解的问题。

③规则图RG中具有的局部并发性避免了强制规则串行执行的低效率。

④相同的CA规则集使用不同的控制结构可对应于不同的RG，增加了CA规则的使用灵活性。

基于图的主动规则模型E－RG可描述为三元组＜Event，RG，Coupling＞，事件Event的发生触发规则图RG的执行，规则图RG由简单的CA规则集以及规则间时序关系S、P、Y组成，规则图的执行必须满足RG所含的时序关系，规则图中具有P关系的简单规则可被并发的调度执行，这体现了E－RG规则执行的规则内的并发性。另外，E－RG规则的执行也支持同一事件触发多个规则的并发执行的情形，这体现为E－RG规则执行的规则间的并发性。

（4）识时规则系统

在实时数据库中，主动规则应具有识时性，这表现在时间事件、时间条件和活动的定时限制三个方面。基本的时间事件包括绝对时间事件和相对时间事件。使用实时逻辑中的时间算子构成复杂时间事件，但规则系统中对复杂时间事件的支持有着一定的难度。

在时间条件的评价和定时限制的实现都要求系统具有“识时”能力和实时处理能力，这些是实时数据库应具有的基本能力。时间条件和定时限制实际上都是一种时间约束，在主动规则模型ECA中，集成时间约束的表达方式在不同的系统中，表现形式各异：

在Snoop系统的规则定义中，给出时间约束和相应的应急处理（contingency action）。该规则的语义是：如果活动action1不能在规定的时间内完成，那么活动action2应该被执行。

on event

if condition

do action1

within time

otherwise action2

在系统REACH中，规则中时间约束的定义使用了时间操作After，Before和Until算子，事务的调度使用了价值函数value（t）。该示例规则的含义是：在分析结果传递到其他结点之前，在规定的时间间隔内对传感器的测量必须完成。

on measure1and measure2

if ok（sensor1）and ok（sensor2）

do analysis；propagate result；

time constraint（after trig－event，

before min（ts（measure1）＋6s，ts（measure2）＋10s），

value（t）＝a＊（ts（trig－event）＋min（ts（measure1）＋6s，

ts（measure2）＋10s）－t）/t

在系统ARTS－II中，主动实时描述语言ARTS－DL对触发器的定义和定时限制的说明部分如下：

触发器的定义：

Trigger：：＝TRIGGER｛＜Trigger－id＞（＜Situation－spec＞，＜Action－spec＞）；｝

Trigger－id：：＝＜identifier＞

Situation－spec：：＝EV：＜Event－id＞CON：［＜Ev－Priority＞］［Timing－cond］［Non－Timing－cond］

定时限制的说明：

Timing－constraint：：＝＜Tran－event－id＞IS＜Timing－spec＞

Timing－spec：：＝＜Time－item＞｜［Time－item］WITH＜Time－in －terval＞

1.5　本书的主要研究内容和创新之处

本书主要研究嵌入式实时数据库事务的特点和相关的管理策略与方法，包括：事务的特性、事务模型的定义、事务的预分析处理、事务接纳控制、事务优先级的分派、并发控制机制、调度策略等。由于嵌入式实时数据库具有人工干预少、可靠性要求高、应变能力强等特点，在这些方面与传统的实时数据库系统相比都有所不同，最基本的特性是事务模型更加复杂，事务具有功能替代性，对于一个活跃的事务而言，只有当其所有替代都夭折时，该事务才能夭折，与此相关的一系列新的管理机制保证了事务具有高成功率，系统具有高吞吐率和高适应能力。

嵌入式实时数据库系统因其所处环境和承担的任务与传统的实时数据库系统不同，我们不能简单地沿用传统实时数据库系统的技术和方法，必须根据其特点进行研究，其中，研究要点如下：

①嵌入式实时数据库系统的特点；

②事务的特点；

③事务模型；

④事务的预分析；

⑤事务并发控制机制；

⑥事务的调度策略；

⑦系统可预见能力的提高等。

本书在全面分析、综合国内外相关研究成果的基础上，根据嵌入式实时数据库系统的新特点，对嵌入式实时数据库系统事务处理的核心理论和相关技术进行了系统研究，具备创新性，主要工作如下：

①提出了新的支持替代与补偿的实时事务模型，在语义上支持嵌入式应用。

②设计出相应的事务预分析方法，特别是替代的生成算法、事务动态执行时间估算、可调度性分析等策略与方法。

③给出了一套支持前述事务模型的接纳控制方法，将提高系统总价值作为接纳控制的目的。

④根据事务的替代性，提出了二重调度策略。

⑤提出了与事务模型和调度相匹配的并发控制策略。