Global Scheduling for Flexible Transactions in Heterogeneous Distributed Database Systems.
AbstractA 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. In this paper, 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.
Introduction
A heterogeneous distributed database system (HDDBS) integrates a set of autonomous database
systems to provide global database functions. In a HDDBS environment, transaction management
is handled at both the global and local levels. As a confederation of pre-existing local
Current address: MCC, 3500 West Balcones Center dr, Austin,
databases, the overriding concern of any HDDBS must be the preservation of local autonomy
[Lit86, GMK88, BS88, Pu88, Vei90, VW92]. This is accomplished through the superimposition
of a global transaction manager (GTM) upon a set of local database systems (LDBSs). Global
transactions are submitted to the global transaction manager, where they are parsed into a set of
global subtransactions to be individually submitted to local transaction management systems at local
sites (LSs). At the same time, local transactions are directly submitted to the local transaction
management systems. Each local transaction management system maintains the correct execution
of both local and global subtransactions at its site. It is left to the global transaction manager to
maintain the correct execution of global transactions.
The preservation of the atomicity and isolation of global transactions is fundamental in achieving
the correct execution of global transactions. Preserving the atomicity or semantic atomicity
[GM83] of global transactions in the HDDBS systems has been recognized as an open and difficult
issue [SSU91]. The traditional two-phase commit protocol (2PC) developed in distributed
database environments has been shown [LKS91a, SKS91, MR91, BZ94] to be inadequate to the
preservation of the atomicity of global transactions in the HDDBS environment. For example, some
local database systems may not support a visible prepare-to-commit state, in which a transaction
has not yet been committed but is guaranteed the ability to commit. In such situations, a local
database system that participates in a HDDBS environment may unilaterally abort a global sub-transaction
without agreement from the global level. Moreover, even if the local database systems
are assumed to support a prepare-to-commit state (as in traditional distributed database systems),
the potential blocking and long delays caused by such states severely degrade the performance. The
concept of compensation, which was proposed [GM83] to address the semantic atomicity of long-running
transactions, has been shown [LKS91a] to be useful in the HDDBS environment. Using
this technique, the global subtransactions of a global transaction may commit unilaterally at local
sites. Semantic atomicity guarantees that if all global subtransactions commit, then the global
transaction commits; otherwise, all tentatively committed global subtransactions are compensated.
Mehrotra et al. [MRKS92] have identified the class of global transactions for which the semantic
atomicity can be maintained in the HDDBS environment. Each global transaction contains a
set of subtransactions which are either compensatable, retriable, or pivot, and at most one sub-transaction
can be pivot. In [ZNBB94], it was shown that this class can be extended by specifying
global transactions as flexible transactions. Flexible transaction models, such as ConTracts, Flex
Transactions, S-transactions, and others [DHL91, ELLR90, BDS increase the failure resilience
of global transactions by allowing alternate subtransactions to be executed when an LDBS fails or a
subtransaction aborts. In a non-flexible transaction, a global subtransaction abort is followed either
by a global transaction abort decision or by a retry of the global subtransaction. With the flexible
transaction model, there is an additional option of switching to an alternate global transaction
execution. The following example is illustrative:
Example 1 A client at bank b 1 wishes to withdraw $50 from her savings account a 1 and deposit it
in her friend's checking account a 2 in bank b 2 . If this is not possible, she will deposit the $50 in her
own checking account a 3 in bank b 3 . With flexible transactions, this is represented by the following
set of subtransactions:
savings account a 1 in bank b 1 ;
checking account a 2 in bank b 2 ;
checking account a 3 in bank b 3 .
In this global transaction, either is acceptable, with preferred. If t 2 fails,
. The entire global transaction thus may not have to be aborted even if t 2 fails. 2
Flexibility allows a flexible transaction to adhere to a weaker form of atomicity, which we term
semi-atomicity, while still maintaining its correct execution in the HDDBS. Semi-atomicity allows
a flexible transaction to commit as long as a subset of its subtransactions that can represents the
execution of the entire flexible transaction commit. By enforcing semi-atomicity on flexible trans-
actions, the class of executable global transactions can be enlarged in a heterogeneous distributed
database system [ZNBB94]. The effect of retrial and compensation methods were investigated to
preserve semi-atomicity on flexible transactions. However, the design of scheduling approaches to
global concurrency control for the execution of flexible transactions has not been carefully investigated

Global concurrency control considering the effect of compensation with respect to traditional
transaction model has been extensively studied. In [KLS90], a formal analysis is presented of those
situations in which a transaction may see the partial effect of another transaction before these
partial effects are compensated. It is then proposed in [LKS91a] that, to prevent an inconsistent
database state from being seen in a distributed database environment, a global transaction should
be unaffected by both aborted and committed subtransactions of another global transaction. A
concurrency control correctness criterion, termed serializability with respect to compensation (SRC),
is further proposed in [MRKS92] to preserve database consistency in the HDDBS environment
throughout the execution of global transactions possessing no value dependencies among their
subtransactions. This criterion prohibits any global transaction that is serialized between a global
transaction G i and its compensating transaction CG i from accessing the local sites at which G i
aborts. All these proposed approaches are inadequate to a situation in which value dependencies
are present among the subtransactions of a global transaction. Value dependencies, which specify
data flow among the global subtransactions of each global transaction, are important characteristics
of flexible transactions.
In this paper, we will propose a concurrency control criterion for the execution of flexible and
local transactions in the HDDBS environment. We will carefully analyze the effects of compensa-
tion, retry, and switching to alternate executions on global concurrency control. We will propose
a specific correctness criterion for schedules of concurrent flexible and local transactions, called
F-serializability, in the HDDBS environment. We will then demonstrate that an F-serializable
execution maintains global database consistency. We will also present a graph-based scheduling
protocol for flexible transactions that ensures F-serizalibility.
This paper is organized as follows. Section 2 introduces the system and flexible transaction
models. In Section 3, we discuss the issues relevant to global concurrency control on the execution
of flexible and local transactions. Section 4 proposes a global concurrency control criterion. In
Section 5, we offer a scheduling protocol to implement the proposed criterion. Concluding remarks
are presented in Section 6.
Preliminaries
In this section, we shall introduce the system and transaction models that will be used in the rest
of the paper.
2.1 System Model
The system architecture under consideration is shown in Figure 1. A HDDBS consists of a set of
each LDBS i is a pre-existing autonomous database management
system on a set of data items D i at a local site (LS i ), superimposed on which is a global transaction
manager (GTM). We assume that there is no integrated schema provided and users know the
existence of local database systems. The set of data items at a local site LS i is partitioned into
local data items, denoted LD i , and global data items, denoted GD i , such that LD
and . The set of all global data items is denoted GD,
transactions are submitted to the GTM and then divided into a set of subtransactions which are
submitted to the LDBSs individually, while local transactions are directly submitted to LDBSs.
We assume that the GTM submits flexible transaction operations to the local databases through
servers that are associated with each LDBS.
In a HDDBS, global consistency means that no integrity constraints among the data in the
different local databases are violated. As with transactions on a database, global and flexible
transactions on a HDDBS should be defined so that, if executed in isolation, they would not violate
the global consistency of the HDDBS. The concurrency control protocol schedules the concurrent
execution of the flexible subtransactions in the HDDBS such that global consistency is maintained.
However, unlike monolithic databases where all the data are strictly controlled by a single trans-
Computer Network
GTM interpreter
User
local
transactions
local
transactions
Server Server
Server
GTM GTM GTM
Gi

Figure

1: The HDDBS system model.
action manager, HDDBSs submit transactions to autonomous local databases. Thus, the HDDBS
transaction manager cannot ensure that transactions submitted independently to local databases
do not violate global integrity constraints. Following the previous research commonly proposed
in the community [BST90], we assume that all local transactions do not modify the global data
items in GD. Note that this will not prevent the local transactions to read global data items, as
long as the execution of the local transaction maintains local integrity constraints. Based on this
assumption, local transactions maintain both local and global integrity constraints.
2.2 Flexible Transaction Model
From a user's point of view, a transaction is a sequence of actions performed on data items in
a database. In a HDDBS environment, a global transaction is a set of subtransactions, where
each subtransaction is a transaction accessing the data items at a single local site. The flexible
transaction model supports flexible execution control flow by specifying two types of dependencies
among the subtransactions of a global transaction: (1) execution ordering dependencies between
two subtransactions, and (2) alternative dependencies between two subsets of subtransactions. A
formal model has been offered in [ZNBB94]. Below, we shall provide a brief introduction of this
model.
be a repertoire of subtransactions and P(T ) the collection of all subsets
of T . Let t We assume two types of control flow relations to be defined
on the subsets of T and on P(T ), respectively:
and (2) (preference) T i   T j if T i is preferred to T j (i 6= j). If T i   T j , we also say that T j is
an alternative to T i . 1 Note that T i and T j may not be disjoint. Both precedence and preference
relations are irreflexive and transitive. That is, they define partial order relations. In other words,
for each t
The precedence relation defines the correct parallel and sequential execution ordering dependencies
among the subtransactions. The semantics of the precedence relation refers to the execution
order of subtransactions. t 1 OE t 2 implies that t 1 finishes its execution before t 2 does. Note that
may start before or after t 1 finishes. The preference relation defines the priority dependencies
among alternate sets of subtransactions for selection in completing the execution of T . For instance,
implies that either t j and t k must abort when t i commits or t j and t k should not be
executed if t i commits. In this situation, ft i g is of higher priority than to be chosen for
execution.
A flexible transaction is defined as follows:
transaction T is a set of related subtransactions
on which the precedence (OE) and preference ( ) relations are defined.
The execution of a flexible transaction may contain several alternatives. Let T i be a subset
of T , with a precedence relation OE defined on T i . It is defined that (T i ; OE) is a partial order of
subtransactions. is a representative partial order, abbreviated as OE-rpo, if the execution
of subtransactions in T i represents the committed execution of the entire flexible transaction T .
Clearly, if (T i ; OE) is a OE-rpo, then there are no subsets T i1 and T i2 of T i such that T i1   T i2 .
The structure of a flexible transaction T can thus be depicted as a set of OE-rpos f(T
of subtransactions, with S k
may contain more than one subtransaction
at a local site. Let (T ; OE) be a OE-rpo of T . A partial order (T 0 ; OE 0 ) is a prefix of (T ; OE),
denoted
ffl for all
ffl for each t 2 T 0 , all predecessors of t in T are in T 0 .
A partial order (T 0 ; OE 0 ) is the prefix of (T ; OE) with respect to t 2 T , denoted (T 0
prefix of (T ; OE) and T 0 contains only all predecessors of t in T . A partial order (T 0 ; OE 0 )
is the suffix of (T ; OE) with respect to t 2 T , denoted
in contains only t and all successors of t in T .
In general, the alternate relationship need not exist only between two individual subtransactions; one subtransaction
may be a semantic alternative of several subtransactions.
2 Note that when transaction becomes a traditional global transaction.
We now use prefixes and suffixes to show how a flexible transaction can switch from executing
one OE-rpo to executing a lower-priority alternative. Intuitively, if OE-rpos
some prefix and the subtransactions t immediately following that prefix in the execution of
continue execution from the point where the shared prefix completed.
In this case, the set of ft forms a switching set, formally defined as follows:
be subtransactions in OE-rpo (T ; OE) of a flexible trans-action
forms a switching
set of (T ; OE) if
ffl there is a OE-rpo (T 0 ; OE 0 ) of T such that prefix of (T 0 ; OE 0 ), and
A switching point is a subtransaction in a switching set which relates one OE-rpo to another
OE-rpo.
be two OE-rpos of flexible transaction T . We say that
has higher priority than p 2 in T , denoted are T 1i ' T 1 and T 2j ' T 2 such that
. The preference relation defines the preferred order over alternatives. We state that two
subsets have the same priority if there is a T i ae T such that T i   T j and T i   T k , but
The execution of a flexible transaction T at any moment must be uniquely determined. We say
that a flexible transaction T is unambiguous if the following conditions are satisfied:
ffl For any switching set in a OE-rpo (T ; OE) of T ,
has no two alternatives with the same priority.
ffl None of the OE-rpos of T are in a priority cycle such that p i 1
for a
permutation
Note that the set of all OE-rpos of a flexible transaction may not be clearly ranked, even if it is
unambiguous. The aborting of subtransactions determines which alternative OE-rpo will be chosen.
In the remainder of this paper, we assume that all flexible transactions are unambiguous. The
following example is given in [ZNBB94]:
Example 2 Consider a travel agent information system arranging a travel schedule for a customer.
Assume that a flexible transaction T has the following subtransactions:
the plane fare from account a 1 ;
the plane fare from account a
reserve and pay for a non-refundable plane ticket;
rent a car from Avis;
limo seat to and from the hotel.
The following OE-rpos are defined on the above subtransactions:
is the switching set of p 1 and ft 4 g is the switching set of both p 1 and p 3 . With these
switching sets, we have g. Clearly, the set of OE-rpos in this
flexible transaction is unambiguous. Note that cannot be
ranked in any preferred order. 2
In each OE-rpo of subtransactions, the value dependencies among operations in different sub-transactions
define data flow among the subtransactions. Let (T ; OE) be a OE-rpo and T have sub-transactions
We say that
is value dependent on t j 1
the execution of one or more operations in t j t
is determined by the values read by t
Each subtransaction is categorized as either retriable, compensatable, or pivot. We say that
a subtransaction t i is retriable if it is guaranteed to commit after a finite number of submissions
when executed from any consistent database state. The retriability of subtransactions is highly
determined by implicit or explicit integrity constraints. For instance, a bank account usually has
no upper limit, so a deposit action is retriable. However, it usually does have a lower limit, so a
withdrawal action is not retriable.
A subtransaction is compensatable if the effects of its execution can be semantically undone
after commitment by executing a compensating subtransaction at its local site. We assume that
a compensating subtransaction ct i for a subtransaction t i will commit successfully if persistently
retried. 3 ct i must also be independent of the transactions that execute between t i and ct i . Local
database autonomy requires that arbitrary local transactions be executable between the time t i is
committed and the time ct i is executed, and these local transactions must be able to both see and
overwrite the effects of t i during that time. For example, consider a HDDBS that has account a in
LS 1 and account b in LS 2 , with the integrity constraints a - 0 and b - 0. Suppose a transaction T 1
transfers $100 from a to b. The withdrawal subtransaction t 1 at LS 1 is compensatable, while the
deposit subtransaction t 2 at LS 2 is not. The compensation of t 2 may violate the integrity constraint
local transaction which is executed between t 2 and its compensating subtransaction takes
the amount of b. Note that both t 1 and t 2 are compensatable in the traditional distributed database
environment, which ensures that the transactions that are executed between t 2 and its compensating
subtransaction ct 2 are commutative with ct 2 [KLS90, BR92].
A subtransaction t i is a pivot subtransaction if it is neither retriable nor compensatable. For
3 This requirement, termed persistence of compensation, has been discussed in the literature [GM83].
example, consider a subtransaction which reserves and pays for a non-refundable plane ticket.
Clearly, this subtransaction is not compensatable. This subtransaction is also not retriable, since
such a ticket might never be available.
The concept of semi-atomicity was introduced in [ZNBB94] for the commitment of flexible
transactions. The execution of a flexible transaction T is committable if the property of semi-
atomicity is preserved, which requires one of the following two conditions to be satisfied:
ffl All its subtransactions in one OE-rpo commit and all attempted subtransactions not in the
committed OE-rpo are either aborted or have their effects undone.
effects of its subtransactions remain permanent in local databases.
We will now define the commit dependency relationships between any two subtransactions of
a flexible transaction that should be obeyed in the commitment of these subtransactions. We say
that t j is commit dependent on t i , denoted t if the commitment of t i must precede that of
t j to preserve semi-atomicity. Clearly, if t i OE t j in (T i These de-
pendencies, which are determined by the execution control flow among subtransactions, are termed
e-commit dependencies. To ensure that the execution of a OE-rpo can terminate, the commitment of
compensatable subtransactions should always precede that of pivot subtransactions, which in turn
should precede the commitment of retriable subtransactions. These dependencies are termed t-
commit dependencies. Also, for those subtransactions which are retriable, value dependencies must
be considered in determining a commitment order. Each retriable subtransaction remains retriable
without resulting in any database inconsistency, as long as all other subtransactions that are value
dependent upon it have not committed. Such dependencies are termed v-commit dependencies.
We say that a flexible transaction is well-formed if it is committable. Well-formed flexible
transactions have been identified in [ZNBB94] for which the semi-atomicity can be maintained.
Well-formed global transactions have been identified in [MRKS92] for which the semantic atomicity
[GM83] can be maintained. We assume, in this paper, that the flexible transactions are well-formed
for the discussion of global concurrency control. We say that a database state is consistent if it
preserves database integrity constraints. As defined for traditional transactions, the execution of a
flexible transaction as a single unit should map one consistent HDDBS state to another. However,
for flexible transactions, this definition of consistency requires that the execution of subtransactions
in each OE-rpo must map one consistent HDDBS state to another.
In the above discussion, we have used banking and travel agency as application examples. It has
been recognized that the concept of flexible transactions can be extended to specify the activities
involving the coordinated execution of multiple tasks performed by different processing entities
93]. For instance, in manufacturing applications, flexible transactions are used to
specify and control the data flow between agile partner applications. Typical inter-task dependencies
include: (1) Ordering dependencies which define the parallel and sequential executions among
tasks, (2) Trigger dependencies which define the contingency executions among tasks, and (3) Real-time
dependencies which define real-time constraints on tasks; e.g., a chronological dependency is
defined by specifying the start time and the expected completion time of tasks. These dependencies
can be realized using the flexible transaction model. The extension of these dependencies have also
been recognized in the the concept of workflow which has been used as a specification facility to
separate control and data flows in a multi-system application from the rest of the application code
3 Issues in Global Concurrency Control
In this section, we will discuss various inconsistent scenarios that may arise when compensation
or retrial are allowed. These observations are important input for the establishment of a suitable
global concurrency control correctness criterion.
3.1 Global Serializability
Global serializability [BS88, BGMS92] is an accepted correctness criterion for the execution of
(non-flexible) global and local transactions in the HDDBS environment. A global schedule S is
globally serializable if the committed projection from S of both global transactions in the HDDBS
environment and transactions that run independently at local sites is conflict-equivalent to some
serial execution of those transactions. 4 In the traditional transaction model, it has been shown that
a global schedule S is globally serializable if and only if all m) are serializable and there
exists a total order O on global transactions in S such that, for each local site LS k (1 - k - m), the
serialization order of global subtransactions in S k is consistent with O [GRS91, MRB
Note that each global transaction can have more than one subtransactions at a local site, as long
as their serialization order is consistent with O. That is, if global transaction G 2 precedes global
transaction G 3 and follows global transaction G 1 in the serialization order, then the serialization
order of all subtransactions of G 2 must precede that of all subtransactions of G 3 and follow that
of all subtransactions of G 1 at each local site.
Following the definition of semi-atomicity on flexible transactions, a committed flexible transaction
can be considered as a traditional global transaction that contains only the subtransactions in
its committed OE-rpo. Some subtransactions in the flexible transaction which do not belong to the
committed OE-rpo may have committed and their effects are compensated. In this discussion, we
call such subtransactions invalid subtransactions. Invalid subtransactions and their compensating
transactions are termed surplus transactions, as their effects are not visible in the HDDBS once
4 See [BHG87] for the definitions of committed projection and conflict equivalence.
the flexible transaction has committed.
Let S be the global schedule containing the concurrent executions of both the subtransactions
(and compensating subtransactions) of flexible transactions l and a set of local transactions.
c be the projection from S of the committed local transactions and the subtransactions of
the committed OE-rpos of We extend global serializability to treat surplus transactions as
local transactions:
Definition 3 (Global serializability) A global schedule S is globally serializable if the projection
of committed local, flexible, and surplus transactions in S is conflict-equivalent to some serial
execution of these transactions.
In the rest of this paper, for the sake of similicity, we assume that each global transaction has
at most one subtransaction at each local site. However, all the theorems can be directly applied to
the general situation where multiple subtransactions are permitted in each global transaction. In
the case of flexible transaction, we consider that each OE-rpo of a flexible transaction has at most
one subtransaction at a local site. Note that T may still contain more than one subtransaction at
a local site, provided that they are in different OE-rpos.
We denote executed before operation im be the
subtransactions at local sites LS 1 . LSm in the committed OE-rpo of flexible transaction T i , and
jm be the analogous subtransactions in the committed OE-rpo of flexible transaction T j . t ip
and t jp both are executed at local site LS p . Let ! s be a serialization ordering on transactions, with
indicating that the execution of t ip must be serialized before that of t jp on the LDBS on
which they executed. Applying the above global serializability theory in the execution of flexible
transactions, we have the following theorem:
Theorem l be the well-formed flexible transactions in global schedule S. Assume that
all LDBSs maintain serializability on the local transactions and subtransactions at their sites. The
global serializability of S is preserved if, for S c , there exists a permutation T
of
such that, for any T i
p for all local sites LS p , where
Several solutions have been proposed to enforce the serializable execution of global transactions,
including forced local conflicts [GRS91]. These approaches are readily applicable to flexible trans-
actions. However, globally serializable schedules may no longer preserve database consistency in
the execution of flexible and local transactions, because the global serializability criterion fails to
consider the constraints on the committed subtransactions which are not a part of the committed
OE-rpos, and on their compensating subtransactions. In fact, every commit protocol which uses compensation
during the execution of flexible transactions may face difficulties with the preservation
of the consistency of globally serializable schedules.
3.2 Problematic Situations
We will now consider some scenarios that may arise if compensation or retrial are allowed. Before
discussing these scenarios, we first introduce the concept of the serialization point, which is similar
to the existing notion of the serialization event [ED90] and serialization function [MRB
Definition 4 (Serialization point) Let t ip and t jp be two subtransactions executed on local site
LS p . Operation o ip of t ip is a serialization point of t ip in global schedule S if, for any subtransaction
t jp , there exists an operation o jp of t jp such that t ip !
The determination of serialization points depends on the concurrency control protocol of the
LDBS. For instance, if the local database system uses strict two-phase locking (pessimistic concurrency
control), then the serialization point can fall anywhere between the moment when the
subtransaction takes its last lock and its commitment [MRB local conflicts are forced,
each subtransaction updates a shared data item at the local site. The order of these updates forms
the serialization order. A detailed discussion of this procedure can be found in [MRB
that, in general, any individual transaction may not have a serialization point in the schedule. This
is the case when serialization graph testing [BHG87] is used as the concurrency control protocol.
However, in enforcing globally serializable schedules, we must determine the serialization orders of
subtransactions at local sites in order to deal with local indirect conflicts [GRS91, MRB
Thus, we assume that the serialization point of each subtransaction can be determined at the local
site. We also assume that, with the help of forced local conflicts, we can ensure that the serialization
point is reached after the transaction begins, and before it commits (the bounded serialization
point assumption).
First, let us consider the following example:
Example 3 Consider a HDDBS that has data items a, b at LS p and data item c at LS p+1 . Let
the integrity constraints be a ? c and b ? c. Two flexible transactions T 1 and T 2 at local site LS p
are executed as follows:
which does a := b, executes its serialization point, enforcing t 1p ! s t 2p . t 2p has read data
item b that was written by t 1p .
ffl t 1p+1 , which does c := c \Gamma 1, aborts; T 1 makes a global decision to abort.
Compensating subtransaction ct 1p , which does b := b + 1, is executed. 2
In this example, all the effects of T 1 are eventually removed from the execution, including the
effects of t 1p . Global serializability is preserved, because flexible transaction T 1 was aborted and
correctly compensated for, even though its effects were read by flexible transaction T 2 . However,
proceeds based on the reading of the data item that was updated by t 1p and thus may be
inconsistent. Consider an initial database state a = 5; 4. The resulting database state
after the execution of ct 1p would be a 4, which is inconsistent.
The concept of isolation of recovery [LKS91b, LKS91a] states that a global transaction should
be unaffected by both the aborted and the committed subtransactions of other global transactions.
In addition, the above example shows that, if a global transaction is affected by a committed sub-transaction
which must later be compensated, the task of constructing the compensating subtransaction
will be greatly complicated by the need to restore database consistency. Such compensating
subtransactions must be capable of undoing any effects that may have been seen by other global
transactions. For example, in the above example, ct 1p must restore not only data item b but also
data item a. However, it is also undesirable for ct 1p to have to check for reads by other global sub-
transactions. Note that the effects of the compensated subtransactions on local transactions need
not be considered if we assume that the execution of a subtransaction transfers the local database
from one consistent state to another. This leads us to the following observation:
necessary condition for maintaining database consistency in an execution containing
concurrent flexible transactions in which compensating subtransactions undo only the effects
of their corresponding compensatable subtransactions is that, for each compensatable subtransaction
t ip of T i at given local site LS p (1 - p - m), subtransactions that are subsequently serialized at the
local site must not read the data items updated by t ip until either T i makes a global decision to commit
the OE-rpo containing t ip or the compensating subtransaction for t ip has executed its serialization
point.
As a further complication, a compensating subtransaction ct ip may still unilaterally abort and
need to be retried. Some conflicting subtransactions may have to be aborted to ensure that they
are serialized after ct ip . To avoid such undesirable cascading aborts, we must delay the execution
of the serialization point of such conflicting subtransactions until one of the following conditions
holds for
ffl The flexible transaction containing t ip has made a decision to commit the OE-rpo which contains
t ip .
ct ip has committed.
The following example is also problematic:
Example 4 Two flexible transactions T 1 and T 2 at local site LS p are executed as follows:
makes a global decision to commit.
executes its serialization point.
executes its serialization point, enforcing t 1p ! s t 2p .
which is retriable, unilaterally aborts.
ffl t 1p is resubmitted and re-executes its serialization point. Now we have t 2p ! s t 1p , which
contradicts the order t 1p ! s t 2p that was enforced.
At this point, if the serialization order is not consistent with those at other local sites, t 2p must be
aborted. 2
To avoid cascading aborts, we make the following observation:
necessary condition for avoiding cascading aborts when a subtransaction is retried
is to ensure that a subtransaction does not execute its serialization point until all retriable
subtransactions that precede it in the serialization order of the execution and have not been aborted
have successfully committed.
If, in this situation, we do not avoid the cascading abort, we also can allow a situation where
compensation must be cascaded:
makes a global decision to commit.
executes its serialization point.
executes its serialization point, enforcing t 1p ! s t 2p . Then it commits.
which is retriable, unilaterally aborts.
ffl t 1p is resubmitted and re-executes its serialization point. Now we have t 2p ! s t 1p , which
contradicts the order t 1p ! s t 2p that was enforced.
In this case, T 2 must backtrack to compensate for t 2p , so that the correct serialization order can be
attained at LS p . Unfortunately, if t 2p is not compensatable, this may be impossible.
Whether or not the global transaction is flexible, using either compensation or retrial to regain
consistency leads to blocking. Furthermore, for flexible transactions, switching to an alternate
OE-rpo can also create problems. Let us consider an alternate in flexible transaction T 1 . Let
1n be the preferred OE-rpo, and let t 11 OE t 1j be the second alternate OE-rpo. Note that
t 1j is at a different local site than any subtransaction in the preferred OE-rpo. We then have the
following example, where T 1 should be serialized before
Example 5 The executions of two flexible transactions T 1 and T 2 are given as follows:
which is pivot, commits (therefore T 1 makes a global decision to commit).
executes its serialization point.
executes its serialization point.
unilaterally aborts.
chooses an alternate OE-rpo and submits t 1j . It has yet to execute its serialization point, so
we now have t 2j ! s t 1j , which contradicts the serialization order that was enforced.
At this point, t 2j must be aborted to maintain global serializability. 2
Again, if the cascading abort is not avoided, we can also allow a cascading compensation
situation:
which is compensatable, commits.
which is pivot, commits (and T 2 makes a global decision to commit).
issuing compensating subtransaction ct 1p .
different OE-rpo, issuing subtransaction t 0
1p .
We now have t
1p , which contradicts the serialization order Furthermore, since
t 2p is not compensatable, the only way to regain global serializability is to abort the entire flexible
transaction T 1 .
We observe and later prove that if the cascading abort is avoided, then the cascading compensation
cannot occur. To avoid cascading aborts in this situation, we have the following observation:
Observation 3 A necessary condition for avoiding cascading aborts when an alternate OE-rpo is
attempted is to ensure that, at any local site, an LDBS does not execute the serialization point
of a subtransaction until, for all uncompleted flexible transactions that precede it in the global
serialization order, no alternate subtransaction can possibly be initiated.
Observations 1, 2 and 3 above indicate that some blocking of the execution of subtransactions
which reach their serialization point early may be unavoidable with a concurrency control algorithm
designed to avoid cascading aborts. This blocking will result in the delay of the commitment
operations of these subtransactions. Observations 1 and 2 relate directly to delays which are
caused by compensation or retrial and which cannot therefore be avoided by any global transaction
model that uses these techniques to regain consistency after a subtransaction aborts.
Observation 3 concerns delays that arise only with flexible transactions. There are conflicting
considerations here; the more flexible (and therefore more failure-resilient) global transactions will
be prone to greater delays. Global transactions with less flexibility, which are less resilient to failure,
will have fewer delays. Consequently, while the flexible transaction approach can indeed extend
the scope of global transactions, it does cause more blocking than does the traditional transaction
model.
The observations we have made concerning concurrency control will play a dominant role in the
design of concurrency control algorithms for maintaining global serializability on the execution of
flexible and local transactions. Following these observations, we see that the execution of a flexible
transaction may be greatly affected by the concurrent execution of other flexible transactions.
4 A Global Scheduling Criterion
We will now propose a new concurrency control criterion for the execution of flexible and local
transactions. This criterion, termed F-serializability, places restrictions on global serializability.
Thus, the set of F-serializable schedules is a subset of globally serializable schedules. Following
Observations 1-3, we see that only Observation 1 has an effect on the definition of such a criterion,
while Observations 2 and 3 will impact on the design of a concurrency control protocol.
4.1 Serializability with Flexible Transactions
Clearly, the database inconsistency that may be caused by compensation can be prevented in a
globally serializable execution simply by requiring that, for each compensatable subtransaction
t i of T i at given local site LS conflicting subtransactions that are subsequently
serialized at the local site do not execute their serialization points until either T i makes a global
decision to commit the OE-rpo containing t i or the compensating subtransaction for t i has executed
its serialization point.
A less restrictive approach is also possible. By definition, a compensating subtransaction ct i
should be able to compensate the effect of t i regardless of what transactions execute between t i
and ct i . However, such transactions may propagate the effect of t i to other transactions and such
propagation cannot be statically considered in ct i . For flexible transaction T j following T i in the
global serialization order, if subtransaction t j of T j accesses (reads or writes) the data items not
written by t i of T i , t j will definitely not propagate the effect of t i and can then be serialized between
ct i in the same manner as any local transaction. Only when t j accesses the data items written
by t i may database inconsistency result. Let AC(t) denote the set of data items that t accesses and
commits, RC(t) denote the set of data items that t reads and commits, and WC(t) denote the set
of data items that t writes and commits. We define a compensation-interference free property on
global schedules as follows:
Definition 5 (Compensation-interference free) A global schedule S is compensation-interference
subtransaction t j which is serialized between a subtransaction t i and its compensating
transaction ct i in S, WC(t
We now propose a new global concurrency control criterion as follows:
Definition 6 (F-serializability) Let S be a global schedule of a set of well-formed flexible transactions
and local transactions. S is F-serializable if it is globally serializable and compensation-
interference free.
Note that, in Definition 6, the execution of a well-formed flexible transaction may result in
both a committed flexible transaction and some surplus transactions. Comparing the definition of
F-serializable schedules given above with that of global serializable schedules given in Definition
3, we can easily see that the set of F-serializable schedules is a subset of globally serializable
schedules. However, if we had followed the traditional definition of global serializability in which
all subtransactions and their compensating subtransactions of a flexible transaction at a local site
are treated as a logically atomic subtransaction, then the set of F-serializable schedules would be a
superset of globally serializable schedules. For example, consider a committed flexible transaction
T 1 which has generated a surplus pair of subtransaction t 1 and its compensating subtransaction
ct 1 . Let another flexible transaction T 2 contain data items such that RC(t 1
can be F-serialized between t 1 and ct 1 , but cannot be globally serialized
between t 1 and ct 1 . In addition, since the surplus pair of the subtransactions belong to a different
representative partial order from the committed one, these subtransactions can be treated as a
separate global transaction.
Theorem 2 given below demonstrates that F-serializability ensures global database consistency.
We first show that the compensation-interference free property in an F-serializable global schedule
is inherited in its conflict equivalent schedule.
Given an F-serializable global schedule S, any schedule S 0 that is conflict-equivalent to
S is compensation-interference free.
Proof: The proof proceeds by contradiction. Suppose we do have a schedule S 0 that is conflict-
equivalent to S and is not compensation-interference free. There then exists a subtransaction t j
such that it is serialized between a subtransaction t i and its compensating transaction ct i in S 0 ,
and t j accesses some data item d written by t i . Since S 0 is conflict equivalent to S, t j must also
access d written by t i in S and is serialized between t i and ct i in S. Consequently, S is not
compensation-interference free, contradicting the given condition. 2
Without loss of generality, we assume that, in the below theorem, all local, flexible, or surplus
transactions in S are committed. Thus, S is identical to S c .
Theorem 2 An F-serializable schedule S preserves global database consistency.
Proof: Let S be an F-serializable schedule that transfers a consistent database state DS 0 to a
new database state DS 1 . Let S be its equivalent global serial schedule, where T i
n) is a committed local, flexible, invalid or compensating (sub)transaction. By lemma 1
we know that S 0 is compensation-interference free. We now demonstrate that DS 1 is consistent.
We first prove that every local, flexible, or invalid (sub)transaction reads consistent database
state. The proof proceeds by induction on the position of each transaction in S
Basis: Obviously, T 1 can only be either local, flexible or invalid (sub)transaction. Since T 1 reads
from DS 0 , it reads consistent database state.
Induction: Assume that for all transactions T i , is not a compensating
subtransaction, then T i reads consistent state. Consider T k . There are two cases:
is a local transaction.
Since all transactions preserve local database consistency, T k thus reads locally
consistent database state.
is an invalid subtransaction or a committed flexible transaction.
Let D be the set of all data items existing in the global database. Let D 0 be D\Gammafthe set
of data items updated by those invalid subtransactions appeared in T 1
compensating subtransactions appeared after T k g. Since S 0 is compensation-interference free,
reads only the state of D 0 . Thus, T k reads only consistent database state.
By the semantics of compensation, the partial effects of invalid subtransactions in S 0 are semantically
compensated by their compensating subtransactions. Since no effects of invalid subtransactions
are seen by other transactions before they are compensated, any inconsistencies caused by
these invalid subtransactions are restored by their compensating subtransactions. Let S 00 be S 0
restricted to those transactions that are neither invalid subtransactions or their compensating sub-
transactions. Thus, S 00 consists only the serial execution of atomic local and flexible transactions.
Since each transaction in S 00 sees a consistent database state, then S 00 preserves the global database
consistency. Therefore, DS 1 is consistent. 2
4.2 Avoiding Cascading Aborts and Compensations
be maintained in global schedule S. The following rules are necessary
and sufficient for a flexible transaction scheduler to follow in order to avoid cascading aborts for
serialization reasons:
ffl No subtransaction of flexible transaction T j can execute its serialization point until all retriable
subtransactions of flexible transactions T i such that T
ffl No subtransaction of flexible transaction T j can execute its serialization point until all alternative
subtransactions of flexible transactions T i such that T have committed or
can no longer participate in T i 's committed OE-rpo.
Proof: The necessary condition was shown in Observations 2 and 3.
The sufficient condition can be shown by the observation that cascading aborts really occur when
some subtransaction t j of some flexible transaction T j is serialized before a subtransaction t i of some
flexible transaction T i on the same local database, with . The above conditions ensure that
the serialization point of a subtransaction, which fixes its place in the local database's serialization
order, is not made until all subtransactions that could precede it in the global serialization order
are either committed or decided against. Since no earlier subtransaction can attempt to execute a
new subtransaction on the local database, no cascading abort can occur. 2
Recall from Example 5 that cascading compensations can occur when a subtransaction t 2 reads
from some uncommitted subtransaction t 1 and then commits. If t 1 later aborts, t 2 must be compensated
for. We show the following theorem with respect to cascading compensations:
Theorem 3 A flexible transaction scheduler avoids cascading compensations if it avoids cascading
aborts.
Proof: Assume that the scheduler avoids cascading aborts. This means that it never needs to force
the abort of an uncommitted subtransaction t because of the violation of serialization. By Lemma
2, this is guaranteed by delaying the execution of the serialization point of t until all subtransactions
which must be serialized previously have committed. Therefore, t cannot have committed before
these subtransactions commit. Thus, t need never be compensated for. So cascading compensation
is also avoided. 2
5 A Scheduling Protocol
In this section, we present a GTM scheduling protocol that ensures F-serializability on the execution
of local and flexible transactions, and avoids cascading aborts. This protocol is based on the
assumption that if the concurrency control protocol of a local database does not allow the HDDBS
to determine the serialization point for each subtransaction, a ticket scheme similar to [GRS91] can
be implemented on the local database. Thus, the serialization point for a subtransaction is always
reached between the time the subtransaction begins and the time it commits.
For the GTM scheduling protocol, we propose a execution graph testing method to avoid the
high overhead of keeping track of serialization points, to ensure F-serializability, and to avoid
aborts. For scheduling purposes, we maintain a stored subtransaction execution graph (SSEG)
among subtransactions to be scheduled. The SSEG is defined as follows:
Definition 7 (Stored Subtransaction Execution Graph) The Stored Subtransaction Execution
Graph (SSEG) of a set of flexible transactions in global schedule S is a directed graph whose
nodes are global subtransactions and compensating subtransactions for those flexible transactions,
and whose edges must serialize before t i due to preference, precedence, or
conflict.
Global subtransaction nodes are labeled t m
ip for flexible transaction T i running on local site p.
If more than one global subtransaction is defined for T i on LS p , then the nodes can be ordered
by the   order of their OE-rpos, and m indicates this node's position in that order. If t m
ip is
compensatable, its compensating subtransaction's node is ct m
ip . We begin with a few definitions.
A flexible transaction commits once its pivot subtransaction commits. We say that a flexible
transaction robustly terminates once all subtransactions in the committed OE-rpo have committed
and all compensating subtransactions for committed subtransactions not in the committed OE-rpo
have also committed.
The GTM scheduling protocol assumes that each global subtransaction and compensating sub-transaction
predeclares its read- and write- sets. It includes node and edge insertion and deletion
rules, and an operation submission rule. All nodes and edges associated with a flexible transaction
are inserted as a unit. If some edge insertion fails for flexible transaction T i , no edges may be
inserted for subsequent flexible transaction T j until either the insertion succeeds or all edges for T i
have been deleted. Nodes and edges for flexible transaction T i are inserted into the SSEG according
to the following rules:
Node Insertion Rule: Insert a node for each subtransaction defined for T i . For each
compensatable subtransaction insert a node ct m
ip .
Edge Insertion Rule: For subtransaction t m
ip , where edge insertion does not cause a
cycle:
1. For each previously-scheduled t n
hp .
2. For each previously-scheduled ct n
ct m
hp .
3. If t m
ip is compensatable, insert edge ct m
ip .
4. If t m
ip is (e-, v-, or t-) commit-dependent on t n
iq .
5. For all
ip . If t n
ip is compensatable, insert edge t m
ct n
ip .
The first two edge insertion cases ensure F-serializability. The third rule ensures that in a
surplus pair the invalid subtransaction precedes its compensating transaction. The rest of the cases
ensure that, for all flexible transactions, the resulting schedule is commit-dependency preserving
and all alternatives are attempted in   order.
Nodes and edges are deleted from the SSEG according to the following rules:
Node Deletion rule:
1. Upon completion of a flexible transaction backtrack, delete all nodes representing
subtransactions in the current switching set or its successors, as well as the nodes
representing their compensating subtransactions.
2. Upon commitment of a subtransaction or compensating subtransaction, delete its
node.
3. Upon commitment of a pivot or a retriable subtransaction, delete all nodes representing
its alternatives and their successors in the flexible transaction, as well as
the nodes representing the compensating subtransactions of these deleted nodes.
4. Upon robust termination of a flexible transaction, delete its remaining nodes.
Edge Deletion Rule: Delete all edges incident on deleted nodes.
The operations of a global subtransaction of T i are submitted to the local databases according
to the following rule.
Operation Submission Rule: Submit operations of a subtransaction (including begin
and commit) to its local database only if its node in the SSEG has no outgoing edges.
The SSEG algorithm is defined based on the above rules. Note that the implementation of
the Operation Submission Rule can vary depending on what concurrency control mechanism is
used at each local site. If each local DBMS uses the strict two-phase locking as its concurrency
control mechanism, then the serialization point of a subtransaction can be controlled by the GTM
As a result, some operations of a subtransaction t i of a flexible transaction may be
submitted before other subtransactions which are serialized before t i reach their serialization points.
However, for other concurrency control mechanisms, we generally cannot have such gain from the
local DBMSs.
We now show that the SSEG algorithm maintains global consistency. We begin with a basic
lemma on the restraints the SSEG places on the execution, then apply that to the scheduling
algorithm.
Lemma 3 If there is an edge t jq ! t ip in the SSEG, then if both t ip and t jq execute and commit,
t ip must serialize before t jq .
Proof: By the operation submission rule, no operation of t jq (including begin and commit) can be
executed until the node t jq has no outgoing edges. Therefore, t jq cannot begin (and consequently
by the bounded serialization point assumption cannot execute its serialization point) until the edge
deleted. By the edge deletion rule, the edge is only deleted once the node t ip is deleted.
By the node deletion rule, the node t ip is only deleted once the subtransaction commits. By the
bounded serialization point assumption, t ip must have executed its serialization point before it
commits. Therefore, t ip must have executed its serialization point before t jq could possibly have
executed its serialization point, so the two subtransactions must serialize in the order that t ip
precedes t jq . 2
Note also that if there is an edge t jq ! t ip in the SSEG, but one of them does not commit, but
either fails to execute or aborts, then at most one of them is present in the serialization order, so
how they are actually executed is unimportant.
Theorem 4 Consider two flexible transactions T i and T j . T i is F-serialized before T j if the nodes
and edges of T i are inserted before those of T j .
Proof: Since all nodes are inserted for T i before any nodes are inserted for T j , we know by the
edge insertion rule that all edges between subtransactions of T i and subtransactions of T j must be
directed from some subtransaction of T j to some subtransaction of T i in the same local database.
Consider some local site LS p at which T i and T j conflict. By the first edge insertion rule, there is
an edge t jp ! t ip in the SSEG. By Lemma 3 this means that if both subtransactions execute and
commit, t ip serializes before t jp at LS p . If one of the two subtransactions does not commit, then
the two committed OE-rpos of the flexible transactions may not both have subtransactions at LS p .
In such a case, LS p will not have any effect on the serialization order of T i and T j .
If t ip is executed and is later compensated for, and t jp is also executed, we have the following
two cases:
Case 1: The compensation-interference free condition does not hold between the execution of t ip
and t jp . By the second edge insertion rule, there is an edge t jp ! ct ip in the SSEG, so the operations
of t jp could not be submitted until this edge is deleted. By Lemma 3, if both t jp and ct ip execute
and commit, this means that ct ip must serialize before t jp .
Case 2: The compensation-interference free condition does hold. There is then no edge
ct ip , and t jp may be interleaved between t ip and ct ip . However, the resulting schedule is still
compensation-interference free.
Consequently, T i is F-serialized before T j . 2
Following Theorem 4, we can see that the SSEG algorithm maintains global consistency. We
now also show that the SSEG algorithm has the additional desirable property of avoiding cascading
aborts and cascading compensations. We know by Theorem 3 that if it avoids cascading aborts,
then it avoids cascading compensations. Therefore, we show the following:
Theorem 5 The SSEG protocol for scheduling flexible transactions avoids cascading aborts.
Proof: By Lemma 3, we know that if, for subtransactions t i and t j , there is an edge
must serialize before t j . In fact, similar reasoning shows us that if such an
edge exists in the SSEG, then t i must either commit, abort, or be removed from consideration
before t j can begin. Thus, for this proof, we merely need to show that edges are inserted into the
SSEG that are sufficient to prevent a concurrent execution that allows for a cascading abort.
The first condition for avoiding cascading aborts is that no subtransaction of flexible transaction
T j can execute its serialization point until all retriable subtransactions of any T i such that T
have committed. The first case in the edge insertion rule enforces this by inserting edges t m
ip
for all previously-scheduled t n
ip .
The second condition for avoiding cascading aborts is that no subtransaction of flexible trans-action
T j can execute its serialization point until all alternative subtransactions of any flexible
transaction T i such that T have committed or can no longer participate in T i 's
committed OE-rpo. The first case in the edge insertion rule also enforces this.
Since the SSEG protocol ensures that both conditions necessary for avoiding cascading aborts
are enforced, the theorem holds. 2
Thus, we have shown that the SSEG algorithm maintains global consistency. We have also
shown that the SSEG algorithm has the additional desirable property of avoiding cascading aborts
and cascading compensations. Based on the rules for insertion and deletion of nodes and edges in
SSEG as well as the operation submission rule, the SSEG algorithm can be efficiently implemented
in the HDDBS environment.
6 Conclusions
This paper has proposed a new correctness criterion on the execution of local and flexible transactions
in the HDDBS environment. We have advanced a theory which facilitates the maintenance of
F-serializability, a concurrency control criterion that is stricter than global serializability in that it
prevents the flexible transactions which are serialized between a flexible transaction and its compensating
subtransactions to affect any data items that have been updated by the flexible transaction.
Consequently, no effect of a compensatable subtransaction is spread to other flexible transactions
before it is compensated. In order to prevent cascading aborts, the effects of retrial and alternatives
on concurrency control must also be considered. These factors generate unavoidable blocking
on the execution of flexible transactions. Thus, trade-off between flexibility of specifying global
transactions and high concurrency on the execution of flexible transactions remains.



--R

Using Flexible Transactions to Support Multi-System Telecommunication Applications
Merging Application-centric and Data-centric Approaches to Support Transaction-oriented Multi-system Workflows
Overview of Multidatabase Trans-action Management
Concurrency Control and Recovery in Databases Systems.

Multidatabase Update Issues.
Reliable Transaction Management in a Multidatabase System.
Scheduling with Compensation in Multidatabase Systems.
A transactional model for long-running activities
A paradigm for concurrency control in heterogeneous distributed database systems.
A Multidatabase Transaction Model for InterBase.
Using Semantic Knowledge for Transaction Processing in a Distributed Database.
Node Autonomy in Distributed Systems.
On Serializability of Multidatabase Transactions Through Forced Local Conflicts.
A Formal Approach to Recovery by Compensating Transactions.
A multidatabase interoperability.
A Theory of Relaxed Atomicity.
An Optimistic Commit Protocol for Distributed Transaction Management.
Atomic commitment for integrated database systems.
The Concurrency Control Problem in Multidatabases: Characteristics and Solutions.
A transaction model for multidatabase systems.
Superdatabases for Composition of Heterogeneous Databases.

On Transaction Workflows.
Database systems: Achievements and opportunities.
Transaction Concepts in Autonomous Database Environments.
Prepare and commit certification for decentralized trans-action management in rigorous heterogeneous multidatabases
A theory of global concurrency control in multidatabase systems.
Ensuring Relaxed Atomicity for Flexible Transactions in Multidatabase Systems.
--TR

--CTR
Heiko Schuldt , Gustavo Alonso , Catriel Beeri , Hans-Jrg Schek, Atomicity and isolation for transactional processes, ACM Transactions on Database Systems (TODS), v.27 n.1, p.63-116, March 2002
flexible transactions;concurrency control;heterogeneous and autonomous database;serializability;transaction management