Application Specific Transaction Management in Multidatabase Systems

We present a transaction model for multidatabase systems with autonomous component systems, coined heterogeneous 3-level transactions. It has become evident that in such a system the requirements of guaranteeing full ACID properties and full local autonomy can not be reconciled. In the heterogeneous 3-level transaction model, semantics of actions and specific properties of the architecture of multidatabase systems and of applications are utilized to define application specific compromises between these competing goals. We consider different definitions of conflicts between actions together with application specific sets of allowed (autonomous) local transactions and global subtransactions. A formal model for serializability is given. It is proven that heterogeneous 3-level transactions guarantee all consistency constraints that are ensured in serial executions. In contrast to most other models, we do not require data to be partitioned into global and local data. In particular, heterogeneous 3-level transactions even allow the same data to be updated by local and global transactions in parallel, if these updates are found to be semantically non-conflicting. Recovery is handled by inverse actions. We present a formal framework for this approach which is fully integrated into serializability theory by considering inverse actions as ordinary actions. This has an important impact on the relationship of concurrency control and recovery in our model: By changing the definition of conflicts between actions in order to tailor the model according to application needs, recovery is implicitly affected and no further explicit adaptation of recovery algorithms is necessary. The heterogeneous 3-level transaction model assumes component database systems to support ACID transaction properties. Further properties of local transactions or interfaces of the component database systems are not required. We describe a prototype implementation of heterogeneous 3-level transactions in the object-oriented database system VODAK.     

A theory of global concurrency control in multidatabase systems

This article presents a theoretical basis for global concurrency control to maintain global serializability in multidatabase systems. Three correctness criteria are formulated that utilize the intrinsic characteristics of global transactions to determine the serialization order of global subtransactions at each local site. In particular, two new types of serializability, chain-conflicting serializability and sharing serializability, are proposed and hybrid serializability, which combines these two basic criteria, is discussed. These criteria offer the advantage of imposing no restrictions on local sites other than local serializability while retaining global serializability. The graph testing techniques of the three criteria are provided as guidance for global transaction scheduling. In addition, an optimal property of global transactions for determinating the serialization order of global subtransactions at local sites is formulated. This property defines the upper limit on global serializability in multidatabase systems.     

A non-two-phase locking protocol for global concurrency control indistributed heterogeneous database systems

A concurrency control method is proposed for global transactions in a distributed heterogeneous database system. This method is applicable when the database sites are interconnected in a rooted tree fashion. It guarantees deadlock freedom in addition to serializability. A general architecture of a heterogeneous system is given. The global transaction manager (GTM) decomposes the global transactions initiated at a site and the subtransactions received from other sites into smaller subtransactions, some of which are sent to the GTMs of the other sites, and those remaining, called g-local transactions, are to be executed by the local transaction manager (LTM) at that site. A concurrency control mechanism ensures serializability among: the local transactions (including the g-local transactions of the global ones) at each site, the global transactions and the global and local transactions together     

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.     

P2P多数据库系统中的事务并发控制研究

P2P多数据库系统是一种分布式的数据库系统,它是P2P计算系统和传统数据库系统的结合体.P2P计算系统的动态性使得P2P多数据库系统的事务管理缺少全局控制机制.在事务传播过程不存在循环的前提下,文章提出了一种保证P2P多数据库系统中事务全局串行化的并发控制协议,它通过控制一系列全局事务传播过程中每个熟识关系的两级串行化来实现.     

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     

多数据库系统中的一致性维护

在多数据库环境中存在着全局事务和局部事务,它们必须相互协作,从而为应用程序提供一致性的数据。为了维护多数据库系统（MDBS）的一致性,提出一种事务管理机制。该机制基于扩展事务的原理,对全局子事务和局部事务进行扩展,并为各个局部数据库引进一些控制表。局部数据库管理系统（LDBMS）和局部数据库和控制表之上执行扩展务,这些扩展事务负一局可串行性及事务的恢复。由于它不依赖于LDBMS的各种特征,因此该方法易于实现,是实用的。     

An extended transaction to maintain consistency and recovery in multidatabase systems

A complete practical solution to transaction management preserving multidatabase consistency in the presence of multidatabase updates and failures is presented. The approach developed does not require support for the two-phase commit (2PC) protocol in the participating local database management systems (LDBMSs). Furthermore, it does not violate local autonomy; the source code of the LDBMSs is not modified in any way and the multidatabase system (MDBS) does not access or modify any control information of the LDBMS. The principles of the 2PC protocol in the process of global transaction commitment are adopted. The presented method does not rely on any specific concurrency control mechanism for LDBMSs. Consideration is given to global transaction failures due to subtransaction aborts by the LDBMSs and local site crashes. The recovery process is based on undo operations. While a global transaction is in progress, the tables accessed by subtransactions of this transaction at each local site are locked using specially initiated table locks. These locks are stored and maintained in the local database itself as control tables. The approach taken is easy to implement, and its limitations are discussed.     

Transaction decomposition using transaction semantics

Serializability has been widely accepted as the correctness criterion for databases subject to concurrent access. However, in a number of the newer and most challenging application areas, serializable execution may not be feasible.

? Serializable execution is generally implemented using a two-phase locking algorithm that locks items in the database to delay transactions that are in danger of performing in a non-serializable fashion. Such delays are unacceptable in high performance database systems that must process hundreds, and perhaps thousands, of transactions per second and in systems supporting long-running transactions.

? In systems in which data is distributed across a federated database, a global transaction is decomposed into a set of local subtransactions executed at a subset of the sites. Serializable execution in such systems not only incurs a performance penalty, but also requires the component systems to cooperate (for example in a two phase commit protocol), with a resulting loss of site autonomy. In many applications, the component systems either can not or will not agree to the required cooperation.

A number of models have recently been proposed in which transactions are decomposed into smaller, atomic, interleavable steps. These models have the potential for improving performance since locks are released at the end of each step. Models of distributed transactions have also been proposed with the similarity that subtransactions correspond to steps. In most of this work serializability is no longer guaranteed. In this paper we propose a new, application-oriented, correctness criterion that utilizes transaction semantics. We treat transactions as programs whose semantics can be analyzed at design time. The effect of each transaction is specified using pre- and postconditions, and any schedule that preserves these conditions is permissible. Such schedules can produce database states that could not be reached by any serial execution. In addressing the issue of performance, we use transaction semantics to decompose transactions into steps and describe a concurrency control that controls step interleaving in such a way that assertions are preserved. The same model can be used to study the interleaving of subtransactions of concurrent distributed transactions.     

Multi-level transaction management for complex objects: Implementation,performance, parallelism

Multi-level transactions are a varlant of open-nested transactions in which the subtransactions correspond to operations at different levels of a layered system architecture. They allow the exploitation of semantics of high-level operations to increase concurrency. As a consequence, undoing a transaction requires compensation of completed subtransactions. In addition, multi-level recovery methods must take into consideration that high-level operations are not necessarily atomic if multiple pages are updated in a single subtransaction. This article presents algorithms for multi-level transaction management that are implemented in the database kernel system (DASDBS). In particular, we show that multi-level recovery can be implemented in an efficient way. We discuss performance measurements using a synthetic benchmark for processing complex objects in a multi-user environment. We show that multi-level transaction management can be extended easily to cope with parallel subtransactions within a single transaction. Performance results are presented with varying degrees of inter- and intratransaction parallelism.     

Transaction management issues in a failure-prone multidatabase system environment

This paper is concerned with the problem of integrating a number of existing off-the-shelf local database systems into a multidatabase system that maintains consistency in the face of concurrency and failures.The major difficulties in designing such systems stem from the requirements that local transactions be allowed to execute outside the multidatabase system control, and that the various local database systems cannot participate in the execution of a global commit protocol. A scheme based on the assumption that the component local database systems use the strict two-phase locking protocol is developed. Two major problems are addressed: How to ensure global transaction atomicity without the provision of a commit protocol, and how to ensure freedom from global deadlocks.     

Global scheduling for flexible transactions in heterogeneousdistributed database systems

A heterogeneous distributed database environment integrates a set of autonomous database systems to provide global database functions. A flexible transaction approach has been proposed for the heterogeneous distributed database environments. In such an environment, flexible transactions can increase the failure resilience of global transactions by allowing alternate (but in some sense equivalent) executions to be attempted when a local database system fails or some subtransactions of the global transaction abort. We study the impact of compensation, retry, and switching to alternative executions on global concurrency control for the execution of flexible transactions. We propose a new concurrency control criterion for the execution of flexible and local transactions, termed F-serializability, in the error-prone heterogeneous distributed database environments. We then present a scheduling protocol that ensures F-serializability on global schedules. We also demonstrate that this scheduler avoids unnecessary aborts and compensation     

Overview of multidatabase transaction management

A multidatabase system (MDBS) is a facility that allows users access to data located in multiple autonomous database management systems (DBMSs). In such a system,global transactions are executed under the control of the MDBS. Independently,local transactions are executed under the control of the local DBMSs. Each local DBMS integrated by the MDBS may employ a different transaction management scheme. In addition, each local DBMS has complete control over all transactions (global and local) executing at its site, including the ability to abort at any point any of the transactions executing at its site. Typically, no design or internal DBMS structure changes are allowed in order to accommodate the MDBS. Furthermore, the local DBMSs may not be aware of each other and, as a consequence, cannot coordinate their actions. Thus, traditional techniques for ensuring transaction atomicity and consistency in homogeneous distributed database systems may not be appropriate for an MDBS environment. The objective of this article is to provide a brief review of the most current work in the area of multidatabase transaction management. We first define the problem and argue that the multidatabase research will become increasingly important in the coming years. We then outline basic research issues in multidatabase transaction management and review recent results in the area. We conclude with a discussion of open problems and practical implications of this research.     

一种多数据库事务模型

分析了多数据库系统中事务的特征，给出了多数据事务和事务经历的形式化描述，在此基础上，提出了多数据库事务正确性标准MDB-可串行化，最后给出了,基于MSG图的多数据库串行化定理。     

On Concurrency Control in Multidatabase Systems with an Extended Transaction Model

A major concurrency control problem that we have to cope in multidatabase systems is the global deadlock detection and resolution problem. This detection must take into account the autonomy of local systems, which make impossible the visibility of the state of local transactions. A well-known approach to detect such deadlocks, called potential global deadlocks, is one based on the potential conflict graph (PCG) appropriate for the multidatabase transaction model with a global commit protocol. This classical transaction model is very constraining for applications manipulating great volumes of information, and where subtransaction terminations (commit or abort) of global transactions are not totally dependant. In this paper we present an effective potential global deadlock characterization, and an efficient potential global deadlock detection algorithm, in multidatabase systems with an extended transaction model more suited for such applications.     

Global committability in multidatabase systems

Develops a formal basis for research into the reliability aspects of transaction processing in multidatabase systems (MDBSs). We define a new correctness notion called `global committability' for the correct unilateral commit and the retry recovery of global transactions in an autonomous MDBS environment. This notion makes it easier to ensure the isolation property of global transactions when the retry approach is applied. The formalization work illustrates that the conventional serializability and recoverability notions are not sufficient to specify the correct execution (i.e. isolated execution and recovery) of global transactions when the unilateral commit and the retry recovery are used to ensure the atomicity of global transactions. This work is significant because the unilateral commit and the retry recovery are an attractive complementary means to the undo recovery (whose correct schedule is specified by the conventional recoverability notion) for advanced transaction applications with the characteristics of site autonomy and long-lived execution     

Query optimization in multidatabase systems considering schemaconflicts

In a multidatabase system, the participating databases are autonomous. The schemas of these databases may be different in various ways, while the same information is represented. A global query issued against the global database needs to be translated to a proper form before it can be executed in a local database. Since data requested by a query (or a part of a query) is sometimes available in multiple sites, the site (database) that processes the query with the least cost is the desired query processing site. The authors study the effect of differences in schemas on the cost of query processing in a multidatabase environment. They first classify schema conflicts to different types. For each type of conflict, they show how much more or less complex a translated query can become in comparison with the originally user-issued global query. Based on this observation, they propose an analytical method that considers the conflicts between local databases and finds the database(s) that renders the least execution cost in processing a global query. This research introduces a new level of query optimization (termed the schema-level optimization) in multidatabase environments. The results provide a new dimension of enhancement for the capability of a query optimizer in multidatabase systems     

网格数据库事务管理策略

网格技术的本质就是提高资源的共享能力和实现计算资源的协同处理能力.网格数据库就是使传统数据库能够充分利用网格平台的这种优势,实现传统数据库的存储、管理、处理、分析等能力的共享和协同.网格数据库中的事务也存在全局事务和局部事务之分,对全局事务要保证得到正确的执行结果,其串行化是关键.给出了网格数据库全局事务的形式化定义,以及全局事务实现串行化的条件,并进行了相关证明.     

Divergence control for distributed database systems

This paper presents distributed divergence control algorithms for epsilon serializability for both homogeneous and heterogeneous distributed databases. Epsilon serializability allows for more concurrency by permitting non-serializable interleavings of database operations among epsilon transactions. We first present a strict 2-phase locking divergence control algorithm and an optimistic divergence control algorithm for a homogeneous distributed database system, where the local orderings of all the sub-transactions of a distributed epsilon transaction are the same. In such an environment, the total inconsistency of a distributed epsilon transaction is simply the sum of those of all its sub-transactions. We then describe a divergence control algorithm for a heterogeneous distributed database system, where the local orderings of all the sub-transactions of a distributed epsilon transaction may not be the same and the total inconsistency of a distributed epsilon transaction may be greater than the sum of those of all its sub-transactions. As a result, in addition to executing a local divergence control algorithm in each site to maintain the local inconsistency, a global mechanism is needed to take into account the additional inconsistency Recommended by: Meichum Hsu