Overcoming Heterogeneity and Autonomy in Multidatabase Systems

A multidatabase system (MDBS) is a software system for integration of preexisting and independent local database management systems (DBMSs). The transaction management problem in MDBSs consists of designing appropriate software, on top of local DBMSs, such that users can execute transactions that span multiple local DBMSs without jeopardizing database consistency. The difficulty in transaction management in MDBSs arises due to the heterogeneity of the transaction management algorithms used by the local DBMSs, and the desire to preserve their local autonomy. In this paper, we develop a framework for designing fault-tolerant transaction management algorithms for MDBS environments that effectively overcomes the heterogeneity- and autonomy-induced problems. The developed framework builds on our previous work. It uses the approach described in S. Mehrotra et al. (1992, in “Proceedings of ACM–SIGMOD 1992 International Conference on Management of Data, San Diego, CA”) to overcome the problems in ensuring serializability that arise due to heterogeneity of the local concurrency control protocols. Furthermore, it uses a redo approach to recovery for ensuring transaction atomicity (Y. Breitbart et al., 1990, in “Proceedings of ACM–SIGMOD 1990 International Conference on Management of Data, Atlantic City, NJ;” Mehrotra et al., 1992, in “Proceedings of the Eleventh ACM SIGACT–SIGMOD–SIGART Symposium on Principles of Database Systems, San Diego, CA;” and A. Wolski and J. Veijalainen, 1990, in “Proceedings of the International Conference on Databases, Parallel Architectures and Their Applications”, pp. 321–330), that strives to ensure atomicity of transactions without the usage of the 2PC protocol. We reduce the task of ensuring serializability in MDBSs in the presence of failures to solving three independent subproblems, solutions to which together constitute a complete strategy for failure-resilient transaction management in MDBS environments. We develop mechanisms with which each of the three subproblems can be solved without requiring any changes be made to the preexisting software of the local DBMSs and without compromising their autonomy.     

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

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

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

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

Supporting consistent updates in replicated multidatabase systems

Replication is useful in multidatabase systems (MDBSs) because, as in traditional distributed database systems, it increases data availability in the presence of failures and decreases data retrieval costs by reading local or close copies of data. Concurrency control, however, is more difficult in replicated MDBSs than in ordinary distributed database systems. This is the case not only because local concurrency controllers may schedule global transactions inconsistently, but also because local transactions (at different sites) may access the same replicated data. In this article, we propose a decentralized concurrency control protocol for a replicated MDBS. The proposed strategy supports prompt and consistent updates of replicated data by both local and global applications without a central coordinator.     

多库中并发控制的研究和实现

多库是一组分布在多个结点上自制的数据库系统的集合,每个局部数据库系统可能使用不同的并发控制协议。自制和异构为保证多库系统的全局可串性带来了困难。本文首先描述了多库中全局可串性问题,然后介绍了并发控制服务CCS系统的特点及系统的逻辑流程,最后讨论了系统中各个接口对象的设计及实现。     

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.     

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.     

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     

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.     

Transaction recovery in federated autonomous databases

Transaction management for federated database systems (FDBSs), where each participating DBMS is autonomous, supports global transactions that can access more than one database. A number of concurrency control algorithms exist for the failure-free environment. Handling transaction failure, due to concurrency control or site related reasons, becomes especially difficult in the presence of autonomy. Due to local autonomy, carrying out 2-phase commit may not be possible. This can be simulated by providing a server on top of the pre-existing DBMS at each site, which is responsible for submitting the local operations to the associated DBMS and communicating with the transaction's originating site. In this paper we formalize the problem of ensuring transaction consistency in an FDBS environment in the presence of failure. The key problem is that due to autonomy, the local DBMS and FDBS may have different views of an execution sequence generated at a site.Local recoverability is identified as the property of local execution sequences necessary for correctness. The other main problem is of guaranteeing that the various locally recoverable histories are consistent with each other. These identified properties are necessary and sufficient conditions for the correctness of FDBS recovery algorithms, and can be used to evaluate the correctness of the proposed algorithms. This paper also presents an FDBS recovery algorithm that has been proved to be correct. Formal proofs of all properties and a comparison of different algorithms are provided. Recommended by: Y. BreitbartThis work was supported in part by sub-contract #B09530013 from Honeywell SSDC, under contract #F30602-91-C-0128 from Rome Laboratory of the US Air Force.On leave from Computer Science Department, Heilongjiang University, People's Republic of China.     

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     

Commit protocols for externalized-commit heterogeneous database systems

In designing a heterogeneous database systems, one of the main technical challenges is developing techniques for ensuring global commit. That is, guaranteeing that a transaction spanning multiple individual database management systems (DBMSs) either commits at all the participating DBMSs or at none of them. Previous work in this area typically assumes that the participating DBMSs do not provide a mechanism for interacting with their commit facilities. While this is true in many cases, in practice there are systems which support a programmatic interface to their commit protocols. We refer to database systems offering such facilities asexternalized commit DBMSs.The focus of this paper is on commit protocols for these systems. We propose two new commit protocols for externalized commit DBMSs. The first may be used to obtain global commit in heterogeneous database systems composed of DBMSs with different 2-phase commit protocols (e.g., centralized and linear). The second protocol is more general, and ensures global commit even if the participating DBMSs employ 3-phase commit protocols. The more general protocol also preserves database autonomy, since it does not block a DBMS upon failure of another system. We describe both protocols in detail and prove their correctness. Recommended by: M. RusinkiewiczThis work was partially supported by an IBM Research Initiation Grant.     

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     

层次结构的多数据库系统中事务执行的正确性准则

研究了层次式多数据库中事务执行的正确性问题.给出了层次式多数据库的定义和结构以及建立在其上的事务结构,根据多数据的特点提出了一种层次式多数据库中事务执行正确性准则,并举例说明其应用,最后给出了该标准的评价以及应用展望.     

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.     

Quantification of autonomy on multidatabase systems

Amultidatabase system is an interconnected collection of autonomous databases each managed by an autonomous database management system (DBMS). When integrating multiple DBMSs, the key is the autonomy of the underlying participants. Much research has been undertaken in the past five years aimed at describing and building an integrated multidatabase system, but to date the termautonomy has only been defined intuitively. This article provides a rigorous definition for autonomy tailored to the multidatabase environment specifically but applicable to any system environment that involves the collaboration of autonomous participants. The major contribution of this article is a technique that measures autonomy along multiple dimensions so a single numeric value describing the amount of autonomy violated by a particular system design is quantified. This has a two-fold implication. First, the technique described forces researchers to consider autonomy from several different aspects that may not be the central focus of their research, but must be considered because assumptions made regarding one aspect of a system may have implications in other areas. Second, the value can be used as a measure for direct comparison among different systems or proposals. Finally, the article demonstrates the quantification technique's applicability by applying it to several recent multidatabase research efforts.     

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

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

Transaction management in distributed heterogeneous database management systems

Current distributed, heterogeneous database management systems (DBMSs) address the issue of distributed transaction management (DTM) in two different ways: some systems rely solely on unmodified local transaction managers (LTMs), thereby helping preserve local DBMS autonomy, but limit functionality (e.g. allow only unsynchronized retrievals, preclude distributed updates, etc.); others maintain full functionality but require the (re)design of the LTMs to enforce homogeneous DTM across all heterogeneous DBMSs, thereby giving up most of the local DBMS autonomy.

The goal of the work presented here is to establish the minimum set of modifications to LTMs that allow synchronized retrievals and distributed updates (whenever semantic conflicts can be resolved), and will continue to maintain a high degree of local DBMS autonomy. The problems of: (1) distribution of responsibility between DTM and LTMs, (2) concatenation of functionally-equivalent LTM mechanisms, and (3) providing compensation mechanisms for functionally-limited LTMs are introduced. Solutions to the above problems are shown to exist. However, the interconnection of autonomous, heterogeneous DBMSs is significantly more difficult than anticipated, despite communication standardization and current optimism.     

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.