2 IEEE TRANSACTIONS ON KNOWLEDGE AND DATA ENGINEERING, VOL. 6, NO. 1, FEBRUARY 1993

is not violated, local schedules must be validated by the MDBS. However, the local serialization orders are neither reported by the local database systems, nor can they be determined by controlling the submission of global subtransactions or observing their execution order. To determine the serialization order of the global transactions at each LDBS, the MDBS must deal not only with direct conflicts that may exist between the subtransactions of multidatabase transactions, but also with the indirect conflicts that may be caused by local transactions. Since the MDBS has no information about the existence and behavior of local transactions, determining if an execution of global and local transactions is globally serializable is difficult. An example illustrating this problem is presented in the next section.

Several solutions have been proposed in the literature to deal with this problem, however, most of them are not satisfactory. The main problem with the majority of the proposed solutions is that they do not provide a way of assuring that the operation execution order of global transactions, which can be controlled by the MDBS, is reflected in the local serialization order of the global transactions produced by the LDBSs. For example, it is possible that a global transaction Gi is executed and committed at some LDBS before another global transaction Gj, but their local serialization order is reversed. In this paper, we address this problem by introducing a technique that disallows such local schedules, and enables the MDBS to determine the serialization order of global transactions in each participating LDBS. Our method does not violate the local autonomy and is applicable to all LDBSs that ensure local serializability. Unlike other solutions that have been proposed in the literature, our technique can be applied to LDBSs that provide interfaces at the level of set-oriented queries and updates (e.g., SQL or QUEL).

Having established a method to determine the local serialization order of global transactions in LDBSs, we introduce optimistic and conservative methods that enforce global serializability. In addition, we propose efficient refinements of these methods for multidatabase environments where the participating database systems use cascadeless or rigorous schedulers [6], [7]. We show that multidatabase scheduling is simplified in multidatabase environments where all local systems are cascadeless. Further simplifications are possible if LDBSs use one of the many common schedulers that ensure that transaction serialization orders are analogous to their commitment order. We show that in such multidatabase environments the local serialization order of global transactions can be determined by controlling their commitment order at the participating LDBSs. Although we address the problem of enforcing global serializability in the context of a multidatabase system, the solutions described in this paper can be applied to a Distributed Object Management System [8].

This paper is organized as follows. In Section II, we identify the difficulties in maintaining global serializability in MDBSs and review related work. The multidatabase model and our assumptions and requirements towards lo-

cal database management systems are discussed in Section III. In Section IV, we introduce the concept of a ticket and propose the Optimistic Ticket Method (OTM) for multidatabase transaction management. To guarantee global serializability, OTM requires that the LDBSs ensure local serializability. In Section V, we introduce the Conservative Ticket Method (CTM) that also requires global transactions to take tickets but is free from global restarts. Variations of OTM and CTM that use simpler global schedulers but work only in multidatabase systems in which all local systems are cascadeless are presented in Section VI. In Section VII we introduce the concept of implicit tickets and propose the Implicit Ticket Method (ITM) which does not require subtransaction tickets but works only in multidatabase environments where the participating LDBSs are rigorous. Integrating the methods above in mixed multidatabase schedulers is discussed in Section VIII. Finally, in Section IX, we summarize our results.

II. Problems in maintaining global
serializability and related work

Many algorithms that have been proposed for transaction management in distributed systems are not directly applicable in MDBSs because of the possibility of indirect conflicts caused by the local transactions. To illustrate this point consider Figure 2 which depicts the execution of two multidatabase transactions G1 and G2, and a local transaction T1. If a transaction Gi reads a data object a, we draw an arc from a to Gi. An arc from Gi to a denotes that Gi writes a. In our example, the global transactions have subtransactions in both LDBSs. In LDBS1, G1 reads a and G2 later writes it. Therefore, G1 and G2 directly conflict in LDBS1 and the serialization order of the transactions is G1 ! G2. In LDBS2, G1 and G2 access different data items: G1 writes c and later G2 reads b. Hence, there is no direct conflict between G1 and G2 in LDBS2. However, since the local transaction T1 writes b and and reads c, G1 and G2 conflict indirectly in LDBS2. This indirect conflict is caused by the presence of the local transaction T1. In this case, the serialization order of the transactions in LDBS2 becomes G2 ! T1 ! G1.

In a multidatabase environment, the MDBS has control over the execution of global transactions and the operations they issue. Therefore, the MDBS can detect direct conflicts involving global transactions, such as the conflict between G1 and G2 at LDBS1 in Figure 2. However, the MDBS has no information about local transactions and the indirect conflicts they may cause. For example, since the MDBS has no information about the local transaction T1, it cannot detect the indirect conflict between G1 and G2 at LDBS2. Although both local schedules are serializable, the global schedule is non-serializable, i.e. there is no global order involving G1, G2 and T1 that is compatible with both local schedules.

In the early work in this area, the problems caused by indirect conflicts were not fully recognized. In [9], Gligor and Popescu-Zeletin stated that a schedule of multidatabase transactions is correct if multidatabase transactions have