mformatlon into the database, updating the
inventory, notlfymg accounting, prmtmg a shlp-
pmg order, and so on Such office LLTs mimic
real procedures and hence can cope with mter-
leaved transactions In reality, one does not phy-
sically lock the warehouse until a purchase order
1s fully processed Thus there 1s no need for the
computerized procedures to lock out the mven-
tory database until they complete
Once again, the bank and office LLTs we
have presented are not Just collections of normal
transactions, they are sagas There IS an apphca-
tlon “constramt” (not representable by the data-
base consistency constraints) that the steps of
these actlvltles should not be left unfinished The
apphcatlons demand that all accounts be pro-
cessed or that the purchase order 1s fully pro-
cessed If the purchase order 1s not successfully
completed, then the records must be straightened
(e g , inventory should not reflect the departure of
the Item) In the bank example, It may always
be possible to move forward and finish the LLT
In this case, It may not be necessary to ever com-
pensate for an unfinished LLT
The notion of saga 1s related to several
exlstmg concepts For example,
a
saga 1s like a
nested transaction [Mossa, LyncSSa, Lync86a],
except that
(a) A saga only permits two levels of nesting
the top level saga and simple transactions,
and
(b) At the outer level full atonuclty 1s not pr+
vlded That IS, sagas may view the partial
results of other sagas
Sagas can also be viewed as special types of tran-
sactlons running under the mechanisms described
m [Garc83a] The restrlctlons we have placed on
the more general mechanisms make It much
simpler to implement (and understand) sagas, m
consequence making It more likely that they be
used m practice
Other related ideas include [GlfT85a], which
describes “independent atomic actions”, similar to
sagas, and [Kort85a] which considers long tran-
sactions m a CAD environment EMPACT, a dls-
trlbuted
database application
described
m [Norm83a], uses “suspense files” containing
update transactions to be run at remote systems
to implement updates of replicated distributed
data
Two ingredients are necessary to make
sagas feasible a DBMS that supports sagas, and
LLT’s that are broken mto sequences of transac-
tions In this paper we focus on how to obtain
these ingredients m a centralized database sys-
tem Note that smce the concept of saga 1s quite
simple, one does not require complex or novel
lmplementatlon mechanisms (As a matter of
fact, as discussed m Section 7, sagas can be fully
implemented on top of an exlstmg DBMS ) Thus,
the emphasis m this paper 1s not on presenting
novel lmplementatlon techniques but on suggest
mg the appropriate ones for a simple, clean, and
efficient implementation of sagas
In Section 2 through 7 we study the ample-
mentatlon of a saga processmg mechamsm We
start by dlscussmg how an apphcatlon program-
mer can define sagas, and then how the system
can support them We mltlally assume that com-
pensating transactions can only encounter system
failures Later on, m Section 6, we study the
effects of other failures (e g , program bugs) m
compensatmg transactions Due to space hmlta-
tlons, we only discuss sagas m a centralized sys-
tem, although clearly they can be implemented m
a distributed database system
In Sections 8 and 9 we address the design of
LLTs We first show that our model of sequential
transaction execution for a saga can be general-
ized to include parallel transaction execution and
hence a wider range of LLTs Then we discuss
some strategies that an apphcatlon programmer
may follow m order to write LLTs that are
indeed sagas and can take advantage of our pro-
posed mechamsm
2. USER FACILITIES
From the point of view of an apphcatlon
programmer, a mechanism IS required for mform-
mg the system of the beginning and end of a
saga, the begmnmg and end of each transaction,
and the
compensating transactions This
mechanism could be slmllar to the one used m
conventional
systems
to manage
transactions [Gray78a]
In particular, when an apphcatlon program
wishes to m&late a saga It issues a began-saga
command to the system This 1s followed by a
series of begwtran8actron, end-tranaactton com-
mands that indicate the boundaries of each tran-
saction
Between transactions the application
can perform operations that do not involve access
to the database, such as manipulation of local
variables Wlthm a transaction the application
can issue conventional database access com-
251