and possibly heterogeneous databases has led to
the development of federated multidatabase systems
[HM85, LA86, SLSO]. One of the major issues in such
systems is the management of multidatabase transactions.
Since multidatabase transactions frequently involve
long-running activities, some of the requirements
of traditional transactions such as atomicity, isolation,
445 South St.
Morristown, NJ 07962
and durability [Gra78] may become too restrictive for
such transactions. Therefore, there have been several
attempts to introduce a transaction model that would
be more suitable for multidatabase environment.
In this paper, we discuss the execution of Flexible
Transactions based on a multidatabase transaction
model in which atomicity and isolation requirements
of traditional transactions are relaxed. A Flexible
Transaction [RELLSO], is a collection of subtransactions
related by a set of execution dependencies. Associated
with each Flexible Transaction is a set of acceptable
states corresponding to a successful completion
of the global transaction.
The scheduling of Flexible Transactions is more
complex than in the case of nested transactions, because
the scheduler must keep track of execution dependencies
and the acceptable states. Scheduling of
Flexible Transactions using extended Petri Nets has
been discussed in [ELLRSO] and [LEBSO]. Another
scheduling mechanism for Flexible Transactions using
VPL (Vienna Parallel Logic Language) is proposed in
[KPESl].
The approach described in this paper uses an executable
temporal logic language. The main advantage
of using such a language to implement the scheduler
is that its underlying semantics corresponds closely to
the semantics of Flexible Transactions, thus allowing
to achieve the maximum intra-transaction parallelism
allowed by the specification of the Flexible Transaction.
Unlike the proposals referenced above, the scheduler
described here has been implemented and successfully
applied to the scheduling of real telecommunication
applications.
The Ezecutor of Flexible Transactions accepts the
specification of a transaction as an input, and schedules
the subtransactions until the success or failure
conditions of the transaction are satisfied. The processing
of the scheduled subtransactions is supervised
by the execution monitor. Two main software tools
are used to implement the Executor. For scheduling
subtransactions, L.0, a logical parallel language developed
at Bellcore [CCG+Sl, NesSOa, NesSOb], is used.
Since L.0 does not provide the facility to directly access
databases, we use DOL (Distributed Operation
Language) [ROELSO], developed at the University of
Houston, for performing such tasks. The development
of the interface between L.0 and DOL is an important
task in the design of the Executor.
The implementation of the scheduler and the exe-cution monitor was the first phase of a joint research
project involving Bellcore and the University of Houston.
During the second phase of the project, we
have used the Flexible Transaction paradigm to specify
a telecommunication application involving multiple
database systems. The implementation of the scheduler
has provided us with a better understanding of
the Flexible Transaction model, revealing a number of
issues which were not discussed in the original specifications.
This has lead to several additions to the
model and resulted in more precise specifications. We
believe that the experiences gathered in developing
our applications will allow us to gain a deeper insight
into both the strengths and weaknesses of the model
for this class of applications.
The rest of the paper is organized as follows. In
section 2, we review the transaction model, and discuss
some extensions that allow us to capture more
semantics of a transaction. In section 3, we discuss
the implementation of the Executor and describe the
software tools which are used. We also explain the advantages
of using L.0 as the language of the scheduler.
Section 4 presents the conclusions. Appendix A illustrates
an L.0 specification of a Flexible Transaction.
Appendix B gives details of the scheduler. Appendix
C shows how a subtransaction can be expressed as a
DOL program.
2 Flexible Transact ion Model
We assume that each (global) transaction in the Flexible
Transaction model can be specified by providing
the following information [RELLSO]: (a) a set of
subtransactions, (b (scheduling) preconditions assoditions
defining the success of the glo a1 transaction.
The model allows both compensable [Gra81] and noncompensable
subtransactions to coexist within a single
Flexible Transaction. We may take advantage of
the compensability of a subtransaction to increase the
availabilit of data and decrease the possibility of a
deadlock bMS87].
Most nested transaction models use commitment
protocols to assure that all subtransactions constituting
a global transaction are either committed or
aborted. Typically, they assume the existence of a
prepared to commit state. A subtransaction which has
finished all its operations can wait in this state for
a commit or abort signal from the global transaction
manager. However, some DBMSs do not offer a visible
prepared to commit state (e.g. IMS). Execution of a
noncompensable subtransaction in such a DBMS can
violate the consistency of the system. In such systems,
we can execute compensable subtransactions, with the
understanding that they will be compensated, when a
global transaction aborts. In addition, since multidatabase
transactions are frequently long-running activities,
holding the lock on data by the subtransactions
pending in the prepared to commit state, lowers
the availability of the data. A compensable subtransaction
can commit locally and release the lock on data,
ciated with each su b b transaction, and c) a set of conwithout
waiting for a decision from the global transaction,
assuming that it can be compensated if necessary.
The preconditions associated with subtransactions
determine when they can be scheduled for execution.
The precondition for a subtransaction is either an ezecution
dependency, a temporal dependency, or a combination
of both. A subtransaction with an execution
dependency can be executed only in the case of a success
and/or failure of one or more subtransactions. A
dependency on the success of other subtransactions
is referred to as positive dependency. A dependency
on the failure of other subtransactions is referred to
as negative dependency. A subtransaction with temporal
dependency can be executed only before/after
specific time. Subtransactions that do not have execution
dependencies and have temporal dependency of
time zero, the time at which global transaction starts
to execute, are referred to as primary subtransactions.
Figure 1 illustrates a simple dependency among
eight subtransactions of a Flexible Transaction. ST1
and ST6 are primary subtransactions and may start
concurrently. ST2 is scheduled when ST1 succeeds. If
ST2 fails, ST3 is scheduled, and if ST2 succeeds, ST5
is scheduled. ST5 can also be scheduled when ST4
succeeds.
In some situations, several subtransactions can
achieve the same subgoal. This property of multidatabase
transactions is called function replication
[ELLRSO]. Consider the following example.
A travel agent is planning a trip from Los Angeles
to Houston. She has two subgoals to achieve: to find
a seat on a flight to Houston and to reserve a car in
a car rental agency. She has several options for each
part. If she is not able to find a seat on a flight to
Houston, it is useless to rent a car. So renting a car is
positively dependent on finding a seat. Notice that the
failure of a subtransaction such as getting a seat on a
Delta flight does not effect the execution of renting a
car in Avis. Semantically, it is the failure of the subgoal
finding a seat that affects the subgoal renting 4
car. Let us assume that each subgoal can be achieved
by successfully executing any of n subtransactions. In
this case, execution dependencies exist between each
of n rent 4 car options and each of the n find a seat
options which means up to n * n dependency specifications.
This becomes more complicated, if there are
more subgoals with multiple options.
To simplify specification of such dependencies
among subtransactions we introduce the notion of a
cluster. A cluster is a group of subtransactions that
can achieve a given subgoal of a global transaction.
Thus, execution dependencies may involve individual
subtransactions or clusters. Associated with each cluster,
is a condition for the success of the cluster. A subtransaction
with a positive/negative dependency on a
cluster can be executed only after success/failure of a
cluster.
The conditions for the success of a Flexible Transaction
can be specified by providing a set of acceptable
states, defined in terms of the states of each of
the subtransactions. An acceptable state of a Flexible
Transaction is specified in disjunctive normal form.
Four execution states of a subtransaction are: NotST1
ST2
Q
ST8
\ ST7
. -0
ST5
Figure 1. An Execution Dependency Graph
executed (N), Ezecuting (E), Success (S), and Failure
(F). The notion of success or failure of a subtransaction
has different semantics than commit or abort. We
regard the execution state of a subtransaction which is
prepared to commit or is locally committed as S. We
regard the execution state of a subtransaction which
is locally aborted or is compensated as F. These four
execution states can be specified as a state of a subtransaction
in the set of acceptable states. In addition,
we use two additional states that can be assigned to
subtransactions in the set of acceptable states. These
two are described in the following paragraphs.
In some acceptable states, specifying the success or
failure of a subset of subtransactions is sufficient for
the determination of the success of a global transaction.
In such cases, since the execution state of remaining
subtransactions has no effect on determinin
the success of a transaction, we assign Don't care (DT
to the state of such subtransactions. 1) implies any
of four previously discussed execution states. It is
used to simplify the specification of a set of acceptable
states.
In some situations, it might be desirable to concurrently
run several subtransactions with the same
objective, but to allow only one of them to succeed.
Consider concurrent execution of two subtransactions
for reserving seats on two different airlines, each of
which is selling a limited number of tickets at a special
fare for a limited time. The success of one subtransaction
is necessary as a part of an acceptable state.
However, success of both subtransactions is undesirable.
Such conflict can be resolved by requiring that
if one of the two subtransactions succeeds, the other
must fail and leave no effect on the database. To support
concurrent execution of such subtransactions, we
assign S to one of the subtransactions, and Must fail
Success .-.
Primary Q
Subt r ansact ion
(M) to the rest. A subtransaction that is assigned S is
given a higher priority and is used to resolve conflicts
when an acceptable state is reached.l.
Both D and M have no effect on determining
whether an acceptable state has been reached. When
an acceptable state is reached, no further action is
taken for subtransactions whose state is designated as
D in the accepted state. However, all the subtransactions
designated as M in the accepted state are completed
as follows. Before the global transaction commits,
all subtransactions with state Mwhich have been
executed and not failed, must fail. If a subtransaction
is in a prepared to commit state or if it is still executing,
it is forced to abort. If a subtransaction has
committed, its compensating transaction is scheduled
for execution. In the simple two flight reservation example,
the maximum concurrency can be achieved by
specifying S, M), ( N , S), (E, S), (F, S) as the set
A possible set of acceptable states corresponding to
the dependency graph of Figure 1 is shown below as
an example.
of acceptab \ e states.
{ ~ , S , N , ~ , S , M l M , M ) l
M , ~ , D l D , ~ , S , S , N ) l
M, D 1 D, D, M 1 Sl F 1 SI I
~,F1slMs ,lM s ,M lI ,
The Flexible T-ransaction starts executing by
scheduling the primary subtransactions. Upon the
success or failure of a subtransaction, it checksMulti-database applications
Firebird applications can work with several databases at the same time through the client library – something that not all relational database systems allow. Tables from separate databases can not be joined to return linked sets, but cursors can be used to combine information.
If consistency across database boundaries is required, Firebird can manage output sets from querying multiple databases inside a single transaction. Firebird implements automatic two-phase commit when data changes occur, to ensure that changes cannot be committed in one database if changes in another database, within the same transaction context, are rolled back or lost through a network failure.Flexible Executor
Transaction
Specification Subtransactions
Scheduler
Local
Database
System System
Figure 2. The structure of the Executor.
schedules further subtransactions which have execution
dependencies on the finished subtransaction. The
Flexible Transaction succeeds if any of the acceptable
states is reached. This state is referred to as accepted
state. It fails if there is no subtransaction to be scheduled,
no subtransaction is executing, and no acceptable
state is reached.
3 Execution of Flexible Transact
ions
There are two major tasks in the implementation of an
Executor for Flexible Transactions. The first task is
to schedule subtransactions and determine the success
or failure of global transaction. The second task is to
execute subtransactions in the local database systems.
The scheduling algorithm for Flexible Transactions
is implemented using L.0 which allows concise specification
of the scheduling constraints on the subtransactions
[CNSSl]. The Scheduler receives the specification
of a Flexible Transaction consisting of a set of
subtransactions, their dependency set, and the set of
acceptable states2. Appendix A shows the specification
of a Flexible Transaction, expressed in L.O. It
corresponds to the Flexible Transaction shown in Figure
1.
To control the execution of the scheduled subtransactions,
we use the Distributed Operation Language,
DOL, which has been designed to access multiple and
2The specification of a Flexible Transaction can be expressed
in a pseudo language. In this case, the specification must be
translated to L.0 before being passed to the scheduler. The
translation can be done either manually or by a program. In
the latter case, a graphical interface to the user can be designed
to accept the specification, and translate it to L.O. This would
eliminate the user’s need for knowing how to specify a Flexible
Transaction in L.0, and the existence of L.0 will become
transparent.
heterogeneous hardware and software systems. By interfacing
L.0 and DOL, we allow the scheduler to cooperate
with the execution monitor in executing Flexible
Transactions. The structure of the Executor is
illustrated in Figure 2.
3.1 Execution of the subtransactions
Figure 3 shows the state transition diagram for subtransactions
during scheduling. Some state transitions
are determined by the Executor and some by the member
database systems. Once a precondition of a subtransaction
becomes true, it is scheduled for execution.
Upon the failure of a subtransaction (determined by
the member DBMS), its state changes to Local Abort.
Upon the success of a subtransaction (also determined
by the member DBMS), its state changes to Local
Commit, if it has committed, or to Prepared to Commit,
if it waits at the prepared to commit point. At
any of these two points (i.e., Local Commit or Prepared
to Commit), the subtransaction state does not
change until the success or failure of global transaction
is determined.
If the global transaction succeeds, the following
state transitions occur. If a subtransaction is in a Prepared
to Commit state and its success is part of the
accepted state, then it commits and its state becomes
Local Commit. If a subtransaction is in a Prepared
to Commit state and its success is conflicts with the
accepted state, it aborts and its state becomes Local
Abort. If a subtransaction is in a Local Commit state
and its success is a part of the accepted state, its state
remains unchanged. If a subtransaction is in a Local
Commit state and its success is contradictory to the
accepted state, it is compensated (providing that it is
compensable) and its state become Compensated.
If the global transaction fails, the following state
transitions occur. If a subtransaction is in a Prepared
to Commit state, it is aborted and its state becomes
Local Abort. If a subtransaction is in a Local CommitState Transition Determined
by the Executor
D : State Transition Determined
by the member system
(e.g. DBMS)
9No t Executed lE
) Executing
Local Commit
Commit \
Compensated
Figure 3. State Transition Diagram for subtransactions
state, it is compensated (providing that it is compensable)
and its state becomes Compensated.
3.2 Using L.0 to implement the scheduler
L.0 is a rule-based language, which was designed to allow
fast prototyping of software and hardware protocols
[CCG+91]. Such protocols constrain the behavior
of a number of different agents or components, so that
when they act together, as prescribed by the protocol,
a common goal is achieved, such as reliable transmission
of data, fair resource allocation, recovery from an
error state, correct execution of a hardware circuit, or
success or failure of a Flexible Transaction.
Often these protocols are stated as sets of guarded
commands (rules). Each set of guarded commands
specifies the behavior of a particular agent or component.
In hardware, all of the components are active
simultaneously and forever. In the case of Flexible
Transactions, each subtransaction may be viewed as
an agent, and the whole Flexible Transaction may be
viewed as a protocol for coordinating the behavior of
each of these subtransactions. The agents (subtransactions)
need to be active only until success or failure
of the whole Flexible Transaction is detected. In Flexible
Transactions, the protocol each agent is supposed
Local Abort
to follow, is basically the same. Thus, it can be described
via a parameterized set of guarded commands,
which is instantiated once for each subtransaction, using
the data particular to that subtransaction. In general
in software protocols, only some of the agents need
to be active simultaneously at each phase, and often
there are a number of different groups of similar agents
acting simultaneously.
To ease specification of such systems, the fundamental
semantics of L.0 is synchronous execution of
guarded predicates. At each L.0 step, all of the guards
in all of the sets of guarded commands, which are currently
active, are evaluated. Then, in the second phase
of the same step, all of the actions, whose guards were
true are taken. These actions appear to be simultaneous
to the user. The guards in L.0 are usually referred
to as causes, and the actions as effects.
For example in the scheduler of Flexible Transaction
(whose code is in Appendix B), for each subtransaction,
there is one guarded command of the form:
whenever
%
then
339
whether an acceptable state is reached. If not, i
No comments:
Post a Comment