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     

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

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

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.     

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     

多库系统的两阶段局部代理失败恢复策略

从保证全局事务的ACID性及实际的可操作性出发，提出了一种较为可靠的两阶段局部代理的工作流程，使用局部代理作为全局事务管理系统与局部数据库的中间层，模拟出符合2PC协议的状态，从而在多数据库的事务处理中使用2PC协议，在最大限度保证异构数据库自治的前提下，从一定程度上解决了全局事务的原子性保证问题和局部站点失败恢复的问题     

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

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

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.     

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.     

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     

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     

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 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.     

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     

一种多数据库事务模型

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

网格数据库事务管理策略

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

传感器网络中协作实时数据库事务的提交控制

传统的事务模型由于其严格的ACID特性无法适应传感器网络中协作事务的实时性要求.因此着重研究传感器网络中协作实时数据库事务的提交机制.首先,分析传感器网络中实时数据库应用的协作特性,放松事务的严格ACID要求,运用控制区域的概念提出一种基于事务的行为语义控制区域的事务模型.然后,给出该模型的提交、回滚、可见规则及能保证数据库一致性和协作事务实时性的三阶段提交协议,并通过补偿事务保证外化信息准确性.性能测试表明,该模型及提交机制提高了采集数据的外化率和协作实时事务的成功率.     

基于事务语义的多数据库系统并发存取控制方法

本文提出了一种多数据库系统（MDBS）的基于事务语义的并发存取控制方法。文中首先按对数据库一致性的影响将事务分类;接着提出了新的MDBS的并发调度的非可串行正确性准则;然后;叙述了称为“事务语义协议”的并发存取控制原理和方法,给出了全局调度和交付的算法和方法正确性证明。     

Highly available and reliable communication protocols for heterogeneous systems

Existing and legacy software systems are the product of lengthy and individual development histories. Interoperability among such systems offers the support of global applications on these systems. However, interoperability among these heterogeneous systems is hampered by the absence of a reliable communication environment that supports the development of global applications.In this paper, we show how a generic communication framework can serve as a testbed for the specification, verification, and execution of distributed communication protocols. The development of distributed, global concurrency protocols is much simpler than using traditional tools, like RPC (remote procedure call), because our framework provides a high-level communication mechanism that frees the protocol designer from thinking in a message-based style. We present several protocols that are consistent with realistic assumptions about local database systems, and proofs of their correctness and consistency preservation. We also show that the execution of these protocols is fault-tolerant. The distribution of systems can be chosen according to application requirements, without adaptation of protocols. Fault tolerance can be fine-tuned within the framework itself, so that verified protocols do not need modifications in this case either.Besides protocols for traditional transaction processing, we present communication protocols for advanced transaction models that relax one or more of the ACID properties of transactions. These advanced transaction models enable local autonomy and thus are much better suited for heterogeneous environments.