事务工作流的建模和分析

事务工作流由若干个事务组成，其执行满足松弛原子性．只有良构的事务工作流才能保证所有执行均满足松弛原子性．事务具有不同的可补偿特性和可重复特性，在包含多种控制结构的复杂事务工作流中，事务之间组合失配问题可能造成事务工作流的非良构性．该文给出了事务工作流模型及良构性的形式化定义，提出了一个良构性判断定理，通过一种构造性的方法来有效地验证事务工作流的良构性，还设计了事务工作流的描述语言ISWDL并实现了良构性验证器．     

乐观嵌套工作流事务模型的形式化描述

本文对乐观嵌套工作流事务的基本概念及其规则进行形式化描述,并对乐观嵌套工作流事务的层次化、可串行性进行了讨论。最后得出结论：1）利用乐观嵌套模型来调度事务是可以串行调度的,它能够保证数据的一致性。2）在乐观嵌套工作流事务执行过程中采用多版本的数据管理机制来处理并发事务访问同一数据及其中间状态,是无联级回退的。     

实时数据库事务的互斥与同步

实时数据库事务具有许多不同于传统数据库事务的特性，其互斥和同步问题远比传统数据库事务复杂。该文结合已研制成功的嵌入式实时数据库系统ARTs-EDB，重点讨论实时数据库事务的互斥与同步技术。事务互斥用于实现对数据库共享数据“互斥地”访问。根据数据共享特性的不同，实时事务的互斥可分为两类，一类是通过设置“优先级相关”互斥量而实现的互斥，另一类是通过数据库系统提供的并发控制策略而实现的互斥。事务同步是实时数据库事务的特有要求，主要用于实现嵌套事务内部事务的互相等待与互通消息，以保证嵌套事务的内部一致性。     

并发控制一致性理论的进一步完善

本文从基于断言的一致性定义出发,进一步完善了调度可序列化的充要条件,提出了二类较调度可序列化更弱的一致性调度类,充分计论了几种较保冲突可序列化更弱的一致性调度类之间的相互关系,着重讨论了具有容错能力的一致调度,给出了一个实用的并发控制机制(CCC)。     

实时数据库嵌套事务的并发控制

传统满足可串行化正确性标准的并发控制把数据库作为一个整体来考虑，事务的执行保证数据库的一致性。往往在应用中数据库的不同对象集合之间可以独立保证一致性而不必关心别的对象集合的一致性限制以提高事务执行的并发度，这就比较适合嵌套事务模型中父子事务及兄弟事务之间的应用。本文测对嵌套事务的并发控制进行了讨论。     

关于实时事务调度中的优先级反转

分析了基于优先级的调度策略中优先级反转产生的原因,并且给出了RTDBS中实时平淡事务和实时嵌套事务的并发控制中优先级反转的解决方法。主要有优先级继承,高优先级夭折,优先级顶,避免优先级反转的多版本协议,基于优先级的时标排序及一些求精的算法。     

基于时间戳的并行实时事务调度策略

传统并行事务处理方法不适用于实时数据库，对几种相关事务调度策略进行比较，提出一种基于时间戳的并行实时事务调度策略TS-PRTTS(Timestamp based Parallel Real-Time Transaction Scheduling)，采用M／G／1队列模型，利用时间戳控制子事务同步．实验证明，该策略能较好协调同步控制与通信代价矛盾，在系统负荷较重以及数据倾斜、访问倾斜问题较突出时具有良好的性能。     

一种条件结构的调度算法

操作调度是高级综合中的最重要的任务。本文提出了一种条件结构的调度算法，该算法以一种自低向上的途径将一个具有嵌套条件结构的控制数据流图转化为一个不包含条件结构的等价的控制数据流图，采用一种传统的调度算法产生后者的一个调度，然后从这个调度再导出前者的一个调度，它最大限度地利用了操作之间的潜在的资源共享，当控制数据流图中含有大量的嵌套条件结构时，该算法非常有效     

实时事务二次调度

实时事务调度的主要目的是调度实时事务使其满足事务的时间约束,它包括针对多个事务的CPU调度以及与之紧密相关的在多个并发事务之间的数据、I/O及内存等资源的调度。关于调度有大量的研究成果,包括:Earliest DeadlineFirst(Liu和Layland,1973;Abbott和Garcia-Molina,1988等),Least Slack First(Abbott Garcia,1992),Weighted Prior-ity(Huang et al.,1989),以及控制优先级倒置的可抢占算法等。无论哪种调度方法,在动态实时环境下满足所有事务的截止期都是很困难的,而提高系统成功率是实时事务调度的主要目标,为此,本文从一个新的角度来研究这个问题,探讨实     

主动实时数据库的事务处理

现在越来越多的研究关注于主动实时数据库。提出了主动实时数据库下的事务概念模型，这个模型是专门用在实时环境下的嵌套事务模型；介绍了一个事务执行模型的执行原理及该模型各个模块的功能；最后提出了一个事务调度算法，并在此基础上与别的常见的算法进行了性能分析。     

Unifying concurrency control and recovery of transactions with semantically rich operations

The classical theory of transaction management contains two different aspects, namely concurrency control and recovery, which ensure serializability and atomicity of transaction executions, respectively. Although concurrency control and recovery are not independent of each other, the criteria for these two aspects were developed orthogonally and as a result, in most cases these criteria are incompatible with each other.

Recently a unified theory of concurrency control and recovery for databases with read and write operations has been introduced in [19, 1] that allows reasoning about serializability and atomicity within the same framework. In [19, 1] a class of schedules (called prefix reducible), which guarantees both serializability and atomicity in a failure prone environment with read/write operations was introduced. Several protocols were developed to generate such schedules by a database concurrency control mechanism.

We present here a unified transaction model for databases with an arbitrary set of semantically rich operations. We investigate constructive characterization of the class of prefix reducible schedules with semantically rich operations. It turns out that unlike databases with only read/write operations, the exact characterization of prefix reducible schedules in databases with arbitrary operations is rather infeasible. Thus, we propose here several sufficiently rich subclasses of prefix reducible schedules, and design concurrency control protocols that guarantee both serializability and atomicity for schedules from these classes.     

Revisiting Transaction Management in Multidatabase Systems

A lot of research efforts have focused on global serializability, global atomicity, and global deadlocks in multidatabase systems. Surprisingly, however, very few transaction processing model exists that ensures global serializability, global atomicity, and freedom from global deadlocks in a uniform manner. In this paper, we examine previous transaction processing models and propose a new transaction processing model that generates globally serializable and deadlock-free schedules in failure-prone multidatabase systems. A new transaction processing model adopts rigid conflict serializability as a correctness criterion on global serializability, and follows an emulated 2PC, criteria for global commitment, and an abort-based multidatabase recovery scheme for global serializability in failure-prone multidatabase systems. In addition, a deadlock-free policy is suggested where rigid conflict serializability is enforced when each subtransaction, including redo transactions, begins its execution. To practically support a new transaction processing model, Rigid Ticket Ordering (RTO) methods are designed. The proposed transaction processing model has the following improvements: (a) it resolves abnormal direct conflicts identified in this paper, (b) it imposes no restrictions on the execution of local transactions, and (c) it relaxes the restrictions on the execution of global transactions.     

On rigorous transaction scheduling

The class of transaction scheduling mechanisms in which the transaction serialization order can be determined by controlling their commitment order, is defined. This class of transaction management mechanisms is important, because it simplifies transaction management in a multidatabase system environment. The notion of analogous execution and serialization orders of transactions is defined and the concept of strongly recoverable and rigorous execution schedules is introduced. It is then proven that rigorous schedulers always produce analogous execution and serialization orders. It is shown that the systems using the rigorous scheduling can be naturally incorporated in hierarchical transaction management mechanisms. It is proven that several previously proposed multidatabase transaction management mechanisms guarantee global serializability only if all participating databases systems produce rigorous schedules     

On serializability

Concurrent execution of database transactions is desirable from the point of view of speed, but may introduce inconsistencies. A commonly used criterion of correctness of a concurrent execution of transactions is serializability, i.e., the equivalence of the execution to some serial schedule or schedules. In the literature several transaction models have been used and several different notions of serializability have been introduced. In this paper, we investigate the various serializability families in the general transaction model, in the two-step model, and in the restricted two-step model. We also examine these families in the multiversion database model.This research was supported in part by a Japan Society for the Promotion of Science Research Fellowship, in part by a Scientific Research Grant-in-Aid from the Ministry of Education, Science and Culture of Japan, and in part by the Natural Science and Engineering Research Council of Canada under Grant No. A1617. Most of this work was done when the first author was a Visiting Professor in the Department of Applied Mathematics and Physics, Kyoto University, Kyoto, Japan.     

Static and dynamic aspects of goal-oriented concurrency control

A new correctness criterion for schedules of update transactions is proposed, which captures users' intended changes to the database. This is motivated by the observation that traditional serializability may lead to anomalies by not taking into account semantics related to such intended changes. The alternate criterion —goal-correctness — is orthogonal to serializability, and is based on realizing goals associated with each transaction. The problems involved in goal-oriented concurrency control are first identified in a general framework. The analysis suggests that this approach is practical only for restricted transaction languages where goals can be inferred and manipulated efficiently. One such language is then considered, capturing a class of updates of practical interest. For this language, it is shown that goal-oriented concurrency control is tractable and compares favorably to serializability with respect to complexity: testing goal-correctness takes polynomial time, while testing serializability is NP-complete. The set of schedules which are correct with respect to the two criteria are incomparable. Thus, goal-correctness may allow increased concurrency. The results highlight the feasibility and advantages of goal-oriented concurrency control in restricted frameworks. The paper also discusses the dynamic aspects of goal-oriented concurrency control; in particular, an optimistic approach to the dynamic generation of goal-correct schedules is presented.An extended abstract of this paper appeared in the Proceedings of the 2nd Symposium on Mathematical Fundamentals of Database Systems (MFDBS), LNCS 364 (Springer, 1989) pp. 398–414.This author was supported in part by the National Science Foundation, under Grant Number IRI-8816078.     

Cooperative transaction hierarchies: Transaction support for design applications

Traditional atomic and nested transactions are not always well-suited to cooperative applications, such as design applications. Cooperative applications place requirements on the database that may conflict with the serializability requirement. They require transactions to be long, possibly nested, and able to interact with each other in a structured way. We define a transaction framework, called acooperative transaction hierarchy, that allows us to relax the requirement for atomic, serializable transactions to better support cooperative applications. In cooperative transaction hierarchies, we allow the correctness specification for groups of designers to be tailored to the needs of the application. We usepatterns andconflicts to specify the constraints imposed on a group's history for it to be correct. We also provide some primitives to smooth the operation of the members. We characterize deadlocks in a cooperative transaction hierarchy, and provide mechanisms for deadlock detection and resolution. We examine issues associated with failure and recovery.     

安全数据库系统中的事务

在多级安全数据库系统中经典的BLP模型的“向上写”违反了数据库的完整性,并产生隐通道和带来多实例问题,事务间的提交和回退依赖也会产生隐通道,在对事务安全性分析的基础上提出了安全事务模型和安全事务正确性标准一安全冲突可串行化(SCSR),最后给出了一个避免隐通道的安全并发控制算法．     

混合的实时嵌套事务并发控制协议

嵌套事务作为扩展事务模型的一种,提供了事务内部的并行性和更好的失败恢复选择,具有较为广泛的应用,然而却给事务并发控制带来了更高的复杂性,尤其在实时数据库中事务具有时间限制.针对实时嵌套事务模型,提出了一种混合并发控制协议,对同一事务树内的子事务采用锁协议,对不同事务树之间的事务采用基于动态调整串行化顺序的乐观并发控制协议,提高了事务的成功率,最后证明了协议的正确性.     

Exploiting abstraction relationships'' semantics for transaction synchronization in KBMSs

Currently, knowledge sharing is turning out to be a crucial area that needs to be supported by Knowledge Base Management Systems (KBMSs). We propose an approach for transaction synchronization in KBMSs-LARS (Locks using Abstraction Relationships' Semantics). We show how we obtain serializability of transactions thereby providing different locking granules. The main benefit of our technique is the high degree of potential concurrency, which is obtained by means of a logical partitioning of the knowledge base (KB) grounded in the abstraction relationships, and the provision of many lock types to be used on the basis of each partition. In this way, we capture the abstraction relationships' semantics which are contained in a KB graph for transaction synchronization purposes and enable the exploitation of the inherent parallelism in a knowledge representation approach.     

Using tickets to enforce the serializability of multidatabasetransactions

To enforce global serializability in a multidatabase environment the multidatabase transaction manager must take into account the indirect (transitive) conflicts between multidatabase transactions caused by local transactions. Such conflicts are difficult to resolve because the behavior or even the existence of local transactions is not known to the multidatabase system. To overcome these difficulties, we propose to incorporate additional data manipulation operations in the subtransactions of each multidatabase transaction. We show that if these operations create direct conflicts between subtransactions at each participating local database system, indirect conflicts can be resolved even if the multidatabase system is not aware of their existence. Based on this approach, we introduce optimistic and conservative multidatabase transaction management methods that require the local database systems to ensure only local serializability. The proposed methods do not violate the autonomy of the local database systems and guarantee global serializability by preventing multidatabase transactions from being serialized in different ways at the participating database systems. Refinements of these methods are also proposed for multidatabase environments where the participating database systems allow schedules that are cascadeless or transactions have analogous execution and serialization orders. In particular, we show that forced local conflicts can be eliminated in rigorous local systems, local cascadelessness simplifies the design of a global scheduler, and that local strictness offers no significant advantages over cascadelessness