Semantic concurrency control in object-oriented database systems

Semantic Concurrency Control in Object-Oriented Database Systems Peter Muth', Thomas C. Rakow', Gerhard Weikum2,Peter Brossler3, Christof Hasse2 1 GMD Integrated Publication &

Information Systems Institute D-W6100 D m s t a d t Germany (muth, rakow )@darmstadt.gmd.de

2 ETHZurich Computer Science Dept. CH-8092 Zurich Switzerland ( weikum, hasse }@inf.ethz.ch

rency control protocols that operate on pages, e.g., lock all pages that are accessed by a transaction, or on the storage atoms (i.e., flat records) onto which the components of complex objects are mapped [Ca91]. The only access modes that are distinguished for concurrency control purposes are read access and write access. With such conventional implementation techniques for transaction management, data-contention problems, i.e., response time degradation caused by excessive concurrency control conflicts, are likely to occur in performance-critical OODBS applications, because transactions tend to be longer in applications with complex operations on complex objects. To avoid or alleviate potential data contention, the following issues must be addressed by an acceptable concurrency control protocol in OODBSs (cf. [SZSS]): 1 . Object structure: Concurrency control should generally operate on objects rather than pages or storage atoms, thus making the additional data modeling power of OODBSs available to the transaction management. This objective entails the ability to exploit the structure of complex objects; that is, to be able to lock or perform conflict tests on components of complex objects. In doing this, care must be taken so as to avoid excessive overhead for managing locks or performing conflict tests. Another difficulty in this approach is to detect and properly handle conflicting accesses to components that are shared by non-disjoint complex objects. 2. Operation semantics: The semantics of operations, or "methods", on encapsulated objects should be exploited to enhance concurrency. This requires an explicit specification of the compatibility of methods that are defined on an object type. Such a specification can be based on the commutativity of methods; that is, invoking two commutative methods on the same object is not considered as a conflict. For example, on an object of. type Queue, enqueueing the same item by two concurrent transactions is not a conflict because the order of these updates is insignificant in the sense that it cannot be observed by

Abstract This paper presents a new locking protocol for object-oriented database systems (OODBSs). The protocol can exploit the semantics of methods invoked on encapsulated objects. Compared to conventional page-oriented or recordoriented concurrency controlprotocols, our protocol greatly improves the possible concurrency because commutative method executions on the same object are not considered as a conflict. Unlike previous work on concurrency control for abstract data types (ADTs),the protocol takes care of the fact that ADTs can be implemented in terms of other ADTs. Therefore, methods on ADT objects can in turn invoke methods on other ADT objects or even the same object. To ensure that each method execution appears as an indivisible action, the dynamic method invocation hierarchies that result from transaction executions are treated as open nested transactions. In an open nested transaction, the locks of a subtransaction are released when the subtransaction completes ana' only a semantic lock is held further by the parent of the subtransaction.

1 Introduction 1.1 Motivation Object-oriented database systems (OODBSs) are generally viewed as a promising technology for two reasons: 1) better support of advanced data-intensive applications such as CAD, computer-aided publishing, or office automation, mainly by providing the capabilities for modeling, storing, and manipulating complex objects, and 2) better software engineering in building large application systems that consist of reusable modules, mainly by providing support for encapsulated objects, i.e., instances of abstract data types. It is also generally felt that there is still a lack of efficient implementation techniques for OODBSs. One of the potential performance deficiencies is transaction management. Virtually all state-of-the-art systems, both OODBS products and research prototypes, employ conventional concur-

233 1063-638WS3$03.00 0 1993 IEEE

3 University of Bremen Computer Science Dept. D-W2800 Bremen 33 Germany pb@ informatikmi-Bremen.de

the two executions of the Enqueue method nor by any method on queues that may be invoked later.

ably use a combination of conventional data manipulation through SQL-like languages and user-defined methods. This is especially true for extended relational systems that are evolving towards OODBSs.

In this paper, the primary concern is the operation semantics. We present a locking protocol that can exploit the semantics of methods on encapsulated objects and can deal with complex objects. Throughout the paper, we assume that complex objects are disjoint, that is, do not have any referentially shared subobjects. The OODBS concurrency control protocol that we have developed is, in principle, able to cope with referentially shared subobjects. However, there are still a number of open issues on the implementation side; and for the sake of a simpler presentation, we do not cover the case of non-disjoint complex objects here. Our approach allows methods on encapsulated objects to in turn invoke methods on other objects. The basic idea is to treat the dynamic method invocation hierarchy of an OODBS transaction as an open nested transaction [MRKN92,WS921 in which method executions that invoke further methods correspond to subtransactions (i.e., nonleaf nodes in the transaction tree). We have developed a locking protocol for OODBSs that ensures "semantic serializability", that is, serializability with respect to the semantics of the methods that are invoked as top-level actions. The main problem that has been addressed in order to adopt open nested transactions to an OODBS is the following. In an ideal OODBS, encapsulated objects should be accessed only through the object-type-specific methods that are (user-) defined on objects. However, in a real-life environment, some transactions may want to "bypass" the encapsulation of an object and rather access the object directly through a conventional, generic data manipulation language such as (extended or "object-oriented") SQL. Therefore, OODBS transaction management has to deal with the coexistence of "truly object-oriented" transactions that invoke object-type-specific methods and "conventional" transactions that access objects directly. The conceivable reasons for bypassing the encapsulation of an object are the following. Transactions may invoke methods on the underlying implementation objects of an encapsulated object for efficiency reasons, rather than operating at the "official" interface of the encapsulated object. "Object-assembly'' queries on complex objects require the structure of an encapsulated complex object to be revealed. It is virtually impossible to foresee all possible user actions on an object and to provide appropriate objecttype-specific methods. Applications on OODBSs will undergo a fair amount of evolution during their lifetime, especially since there is a lack of both database design methodology and practical field experience. Applications will prob-

The conclusion from the above arguments is that the coexistence of "truly object-oriented" transactions and "conventional" transactions will become increasingly important. The locking protocol that is presented in this paper copes with this coexistence in a reasonably efficient way.

1.2 Related Work Previous work on concurrency control in OODBSs has mostly concentrated on the issue of object structure, that is, exploiting the structure of complex objects for enhanced concurrency [BR88, KBG89, PS87] or reduced overhead [KBG89, He901. Our approach is more related to previous work on concurrency control for abstract data types (ADTs) [HW88, Ke87, RL79, SG88, SS84, We88, We891. However, this previous work assumes that all ADT objects are directly implemented by the storage manager. This means that ADTs cannot be implemented in terms of other ADTs. In OODBSs, the capability to reuse encapsulated types for building other, more powerful types is a crucial feature and must therefore be dealt with by the transaction manager. Our approach allows methods on encapdated objects to in. turn invoke methods on other objects. Our approach to deal with the resulting method invocation hierarchies is based on open nested transactions and the related work on multilevel transactions [BBG89, BSW88, CF90, LMWF92, Ma87, MGG86, MRKN92, RGN90, Wa84, Wei9 1, WS921. However, the structure of multilevel transaction trees is constrained such that operations at the same level of the tree belong to the same system layer. This structural limitation is waived in the more general notion of open nested transactions. In this paper we have addressed the important problem that encapsulated objects may be "bypassed". Our approach is also related to the previous work on "closed" nested transactions [Mo85]. However, most of the work on closed nested transactions is restricted to read/ write locking and does not support semantically rich operations. ADT operations are allowed in the nested transaction models of [FLMW88, HH88, AE921. In [FLMW88], however, such operations can appear only as transaction leaves. That is, the important case of implementing ADT operations by means of other "lower-level'' ADTs is not considered. The models of [HH88] and [AE92] formally allow ADT operations at arbitrary levels in the tree; however, each invoked operation inherits all conflicts of its descendants. Thus, these models do not exploit the semantics of the non-leaf operations, and are therefore, in this respect, comparable to [FLMW88].

234

1.3 Outline of the Paper

Modeling orders as subobjects of items may appear as a somewhat arbitrary choice; however, the purpose of this scenario is merely to illustrate concurrency control problems and our solution rather than schema design issues. The scenario does not include customer objects, since this would necessarily introduce shared subobjects, which are not covered in this paper. For the same reason, we assume that an order always refers to exactly one item. We do allow, however, that multiple orders (of the same customer) are handled within one transaction.

The rest of the paper is organized as follows. In Section 2 we introduce a simple 00DBS-style order-entry application that will serve as a running example. In Section 3 we review the principles of open nested transactions. In Section 4 we discuss the problem of bypassing encapsulated objects in more detail and present our locking protocol to cope with the problem. We conclude with an outlook on open issues that are being addressed toward developing an efficient full-fledged transaction management for OODBSs.

2.2 Methods

2 An OODBS Application Example

Item and Order are encapsulated object types, indicated by the dashed boxes in Figure 1. The methods provided on Item are the following (i stands for the object-id of an Item object):

In this section we sketch a simplified OODBS application scenario which will serve as a running example for the rest of the paper. We do not refer to a particular object-oriented data model, but rather restrict ourselves to an object-structure graph model as a lowest common denominator, to be as general as possible.

0

NewOrder ( i , CustomerNo, Quantity) retums OrderNo, enters a new order into the Orders of item i , and initializes the order status to "new" ShipOrder ( i , OrderNo) records the fact that the ordered quantity of item i is shipped to the customer and updates the Quantity-onhand

2.1 Objects The scenario describes a simple order-entry application (cf. [TPC90]). The object schema graph of the database is depicted in Figure l. The database (OB)consists of a set of items (object type Items). Each item is a tuple object (Item) that is composed of various atomic objects and of a set of orders (Orders) for the item. Each order is a tuple object (Order) that is composed of atomic objects. A component of Order that is especially relevant for our scenario is the Status of an order, which keeps track of the shipment (including billing) and payment of an order.

PayOrder ( i , OrderNo) records the fact that the order of item i is paid by the .customer TotalPayment(i)retums Money computes the total value (i.e., Price*Quantity) of the orders that are already paid by scanning all orders of item i We can define a compatibility matrix for the methods of an encapsulated object type, based on the following definition of commutativity. Two method invocations f and g on the same Item object commute if and only if the two possible sequential executions off and g are indistinguishable for both f and g and for all possible sequences of methods of object type Item that may be invoked subsequently. This means that the two sequential executionsfg and gf are behaviorally equivalent. The two executions may leave the underlying implementation objects in different states. However, the retum values off and g are identical in both executions, and also all subsequent method invocations will retum the same values regardless of whether f was executed before g or vice versa. The compatibility matrix for the object type Item is shown in Figure 2. We assume that the ordering of shipment and payment is irrelevant (i.e., payment may be received before the item is shipped to the customer, without giving a discount to the customer); hence Shiporder and PayOrder are compatible methods.

DB

Items: Set Of Item Item

Figure 1: Object Schema of the Order-Entry Example

235

ject types Items and Orders, in the example), we assume that a primary key is defined among the atomic components of the set's member type (e.g., ItemNo, OrderNo). We further assume that a Select operation (i.e., a "generic method") is provided that returns the object-id of a set element with a specified key. For brevity, we will omit the necessary SeZect operations in all examples and will rather refer directly to object-ids (e.g., write "Shiporder (i,o)" rather than "Shiporder (i?Select (i.Orders,OrderNo))"). For a tuple-type object I , the selection of a component c is simply denoted as t.c. Finally, for an atomic object a, the only operations we consider here are Getfa)to read the value of the object and Putfa)to update the value of the object.

NewOrder Item

ShipOrder CustomerNo, (i, OrderNo) Quantity) (i.

NewOrder ok (i, CustomerNo,Quantity)

conflict

Shiporder (i, OrderNo)

conflict

conflict

ok (i, OrderNo)

ok

ment (i)

Figure 2: Compatibility Matrix for the Methods of Object Type Item

2.3 Transactions We will consider the following five transaction types in the order-entry scenario: T1: ship two orders for two different items to a customer (invoke Shiporder on the items) T2: record a customer's payment of two orders for two different items (invoke PayOrder on the items) T3: check the shipment of two orders for two different items ordered by one customer (invoke Teststatus on the orders) T4: check the payment of two orders for two different items ordered by one customer (invoke Teststatus on the orders) T5: compute the total payment (i.e., total value of all orders that are already paid) for an item (invoke TotalPayment on the item) Transactions of these types will be expanded into method invocation trees dynamically. In particular, the method invocations that result from executing a method on an object may depend on the state of the object. For example, the invocation of the TotalPayment method (within a transaction of type T5) will first examine the status of an order and will read the quantity of the order only if the status is "paid" or "shipped&paid".

The methods provided on orders (i.e., the object type Order) serve to keep track of the status of an order. The following two methods are defined: Changestatus (0,event) records the fact that one of the following events has occurred: the order o has been shipped or paid (thus, the status of an order can be "new", "shipped", "paid', or "shipped&paid') Teststatus (0,event) returns Boolean returns true if the specified event has already occurred The compatibility matrix for the methods of object type Order is shown in Figure 3. The Changestatus method commutes with itself, since its semantics is to add another event to a set of events. It does not remember the ordering in which the events occurred.

1 TestStatus (0,paid)

conflict Status (0,shipped)

ok

ok

conflict

ok

ok

ok

conflict

ok

ok

Status (0,paid)

3 Principles of Open Nested Transactions

(0,shipped)

In this section, we review the main principles of open nested transactions [BSW88, MRKN92, RGN90, WS921 (cf. also [Da78, Gr81]), on which our approach to OODBS concurrency control is based. An open nested transaction is essentially a tree of operation invocations, usually referred to as "actions". The edges in the tree represent the callercallee rerationship between actions; that is, the children of a node in the transaction tree are invoked to implement the action that is associated with the node. We will label the

(0,paid)

Figure 3: Compatibility Matrix for the Methods of Object 'Qpe Order In addition to the methods that are (user-) defined on the encapsulated object types Item and Order, generic operations are provided for the generic types (or type constructors) set and tuple, as well as for atomic types. For a set (i.e., the ob-

236

nodes of a transaction tree with the names of the invoked operations together with their actual parameters. We assume that there exists a semantic conflict test for each possible pair of operation invocations. The conflict test will typically assume that each action is associated with a specific object, and needs to consider only pairs of actions that operate on the same object. The conflict test for a pair of actions does usually not depend on the descendants of the actions, but rather refers only to the observable behavior (i.e., the specified semantics) of the two invoked operations.' This property is a crucial prerequisite for a modular implementation of the proposed semantic concurrency control and for reasoning about its correcmess in a modular manner. The most common form of conflict test is to look up a compatibility matrix like the ones given in Section 2. Such a compatibility matrix is typically based on state-independent commutativity properties of operations, taking into account the actual input parameters of operations. More general forms of conflict test, based on state-dependent or retum-value commutativity [Bee83, CRR91, LMWF92, O'N86, We881, are possible within the framework of open nested transactions; however, in this paper, we restrict ourselves to exp1.oiting state-independent commutativity. A concurrent execution of a set of open nested transactions is essentially a partial order of the actions of the executed transactions. A concurrent execution is called "semantically serializable" if it is equivalent to a serial execution of the transaction roots in the following sense [BBG89]: a serial execution can be stepwise constructed from the original execution by 1. exchanging the order of two adjacent, non-interleaving subtrees if their roots are commuting actions, and by 2. reducing an isolated subtree to its root, where a subtree is called isolated if all its descendants are serial and the entire subtree is ordered with respect to all other actions (i.e., not interleaved with other subtrees). Different kinds of concurrency control protocols can be used for open nested transactions. In the following, we will consider a locking protocol because locking protocols are commonly used and are known for their efficiency. Considering other concurrency control protocols is outside the scope of this paper, but can be useful for specific types of applications. An efficient locking protocol for open nested transactions proceeds as follows. Each row (or column) in the compatibility matrix of an object type (i.e., essentially each operation) is associated with a semantic lock mode; the compatibility of the lock modes is derived from the entries

of the compatibility matrix in a straightforward fashion [Ko83, SS841. Each action of an open nested transaction needs to acquire a semantic lock, according to the invoked operation. Thus, exploiting the semantics of the operations allows us to execute two compatible update operations on the same object concurrently, that is, without blocking. However, two conflict-free actions may still have conflicts among their descendants, that is, on the underlying implementation objects. The locks acquired by the descendants prevent unacceptable "low-level" inconsistencies and ensure that "higher-level" actions appear as if they were indivisible. This means essentially that non-leaf nodes of the transaction tree are executed as subtransactions, and that semantic serializability is guaranteed for each set of subtransactions the roots of which operate on the same obj e ~ t . Note ~ , ~ that reasoning about the semantic commutativity of operations is meaningful only if the operations are indivisible, as assumed by the previous work on ADT synchronization, or are made to appear indivisible, as in multilevel transactions and open nested transactions. The locks of the actions in a subtransaction are released upon the completion of the subtransaction, rather than being passed to the subtransaction's parent as in the conventional model of "closed" nested transactions [Mo85]. Only the transaction root holds semantic locks for its children (i.e., top-level actions) until the end of the transaction. This means that subtransactions commit, that is, expose their effects, independently of the commit of their ancestors; hence the name "open" nested transactions. However, because the parent of a committed subtransaction holds a "higher-level" semantic lock, the effects of the subtransaction are visible only to such actions that commute with the root of the subtransaction.This locking protocol ensures semantic serializability,that is, equivalence to a serial execution as viewed by the top-level actions of the executed transactions. Open nested transactions gain concurrency, that is, reduce the number of lock conflicts, by exploiting the semantics of operations at all levels of the transaction trees, and by committing subtransactions early. The consequence of the early commit is that transaction aborts (and the undo phase of crash recovery) can no longer be implemented by restoring the pre-transaction state of the modified storagelevel objects (i.e., objects modified by the leaves of a transaction tree). Rather committed subtransactions need to be compensated by means of appropriate "inverse" operations. The necessary compensating subtransactions are again subject to the semantic concurrency control protocol sketched above. Recovery issues for open nested transac2. Transactions may actually be viewed as actions that operate on the object "Database". 3. Since the transaction tree is buildup by method calls, amethod is allowed to operate on the same object as one of its ancestors.

1 For actions on complex objects with referentially shared subobjects, this statement must be interpreted carefully. The case of non-disjoint complex objects is not considered in this paper.

237

T1

T2

I

Paydrder (i2,02)

C

I

ChangeStatus (01, shipped)

Get (il.QOH)

b Get (01.Status)

Put (01Status)

Changestatus (01, paid)

Put (il.QOH)

ChangeStatus (02, paid)

b Get (ol.Status)

Put (ol.Status)

h

ChangeStatus (02, shipped)

Get Put (i2.QOH) (i2.QOH)

b

Get Put Get (02.Status) (02.Status) (02.Status)

Put (02.Status)

1 Figure 4: Concurrent Execution of Two Open Nested Transactions this protocol does not consider the case in which an encapsulated object may be manipulated by both invoking methods on the object itself and by directly invoking methods on the underlying implementation objects. In fact, the protocol of Section 3 is correct (i.e., ensures semantic serializability) only if the transaction trees that are dealt with satisfy the following properties:

tions and the special case of multilevel transactions are furiher discussed in [BSWSS, Ga83, HW91, LKS91, MGG86, MR91, WHBM90, Wei911; in the extended OODBS context of this paper, recovery issues are not yet addressed. It seems fairly natural to view the method invocation hierarchy of an OODBS transaction as an open nested transaction (cf. also [BM91, DHL91, RGN901). A concurrent execution of two transactions from the order-entry example of Section 2 is shown in Figure 4. The ordering of actions is from left to right; note that some of the non-leaf actions are concurrent (i.e., their descendants are interleaved). The example execution is semantically serializable, based on the compatibility matrices discussed in Section 2, and it can actually be generated by the locking protocol described above.

0

All pairs (f, g) of potentially conflicting actions (on the same object) have the same depth in their transaction trees, and for each pair (f’, g’) of ancestors off and g that have the same depth in their transaction trees, f ’ and g’ operate on the same object.

The example of Figure 4 in Section 3 satisfies these two conditions. However, Figure 5 shows an example that violates the conditions. In this example, transaction T3 bypasses the encapsulated object il by directly invoking TestStatus on the subobject 01. With the protocol of Section 3, the locks of a subtransaction would be released at the end of the subtransaction. Thus, at the beginning of transaction T3, transaction T1 would hold merely a ”Shiporder” lock on item i l , because the subtransaction that corresponds to the Shiporder action is already completed. However, granting the Teststatus lock to transaction T3 at this point is incorrect, since the Changestatus (01, shipped) action of T1 and the Teststatus (01, shipped) action of T3 are not commutative. Because of the analogous subsequent actions on the Order object 02, semantic serializability is no longer guaranteed.

4 A Semantic Locking Protocol for OODBS Transactions In this section, we present our semantic locking protocol for OODBS transactions. In Subsection 4.1, we discuss the problems that are posed by the possible bypassing of encapsulated objects, and present the main ideas to cope with these problems. In Subsection 4.2, we present the complete locking protocol for OODBS transactions.

4.1 Coping with the Bypassing of Encapsulated Objects Our approach is based on the locking protocol for open nested transactions that is sketched in Section 3. However,

Shiporder (i2,02)

Shiporder (il.01)

238

Shiporder (i2.02)

Shiporder (i1,ol)

I k Changestatus (o1,shipped) Get (o1,QOH)

I

Get(ol.Status)

Put (o1,QOH)

TestStatus (o1,paid)

I

Put (ol.Status)

Get (ol.Status)

TestStatus (02,paid)

I

...

Get (o2,Status)

Figure 6: Conflicting Actions with Commutative and Committed Ancestors sider the retained lock by T4 any more, since ChangeStaus (01, shipped) and Teststatus (01, paid) commute. So, in addition to keeping retained locks, the locking protocol has to take into account commutative ancestors if a conflict with a retained lock is detected. If the two conflicting actions have a pair of commutative ancestors one of which is already committed, then the requested lock can be granted despite formally conflicting with the retained lock. The committed ancestor is necessarily the ancestor of the action that holds the retained lock, since, at this point, none of the ancestors of the lock requestor can be committed.

The described problem could not occur if all transactions had observed the two constraints sketched above. Then, either Teststatus (01, shipped) could not have been called directly by T3, or TI would have to invoke ChangeStatus (01, shipped) directly. In the first case, if Teststatus were called by a newly defined method Checkorder ( i l , 01) invoked on item i l , the conflict between Shiporder and Checkorder would be detected, and T3 would be blocked until the commit of T I . In the second case, if TI invoked Changestatus (01, shipped) directly, the corresponding "Changestatus" lock on 01 would be held until the commit of T1 and would thus block the Teststatus action of T3. A first step towards solving the problem is the following. Locks are no longer released at the end of a subtransaction, but rather converted into retained locks (similar to a protocol for closed nested transactions [Mo85]).For the above example, this means that the lock for Changestatus (01, shipped) is still held by TI as a retained lock, when T3 requests a "Teststatus (01, shipped)" lock. Thus, the conflict would be detected, and T3 would be blocked. Of course, retained locks that are held by a subtransaction are disregarded by (i.e., do never block) subsequent subtransactions within the same transaction. However, there are also less obvious cases in which a "formal" conflict with a retained lock should be ignored to achieve the highest possible concurrency. The desired effect of a retained lock on other transactions actually depends on the ancestors of the action that holds the lock and the ancestors of the action that requests the lock. We distinguish two cases, depending on the commit status of the ancestors.

-

Case 2 commutative but not yet committed ancestor: Now assume that the ancestor of the action that holds the retained lock is not yet completed (i.e., none of the two commutative ancestors is completed). Figure 7 shows such an example. In this example, the Totalpayment method bypasses the encapsulation of type Order by directly reading the order statu^.^ When T5 requests a "Get" lock on 01 Status (i.e., essentially a read lock), T1 has completed its Changestatus (01, shipped) action, but Shiporder ( i l , 01) is not yet completed. That is, the subtransaction that corresponds to the ShipOrder action holds retained locks for Get (01 Status) and Put (01.Status), and non-retained locks for Changestatus (01, shipped) and Get (01, QOH). Thus, upon the lock request of T5, a conflict is detected with Put (01 .Status). However, there exists a commutative ancestor pair Shiporder (il,ol) and Totalpayment ($l , o l ) of the two conflicting actions. Unlike case 1 above, however, tne lock requestor (i.e., the subtransaction of T5) must be blocked until the Shiporder subtransaction of TI is committed.

-

Case 1 commutative and committed ancestor: Consider the example of Figure 6 . Assume TI has finished Shiporder ( i l , 01) operation, and is currently executing Shiporder (i2,02).At this point, T4 could be executed because it simply checks the payment of an order, and is therefore not affected by any ShipOrder operation. However, without additional considerations, T4 would be blocked by a conflict between Get (01 .status) of T4 and the retained lock of Put (01 .status) held by T I . This blocking is actually unnecessary for the following reason: as soon as ChangeStatus (01, shipped) is completed, there is no need to con-

4.2 The Locking Protocol As discussed in Subsection 4.1, locks of committed subtransactions are retained to determine all conflicts between OODBS transactions even if encapsulated objects are bypassed. In addition, the ancestors of the conflicting actions are considered to determine if the actions have a commuta4. Assume that this is done for efficiency reasons, or because TotulPuyment was implemented before the TestStatus method was added to the encapsulated type Order (cf. Section 2).

239

T1 /* ship two orders for two different items to the same customer */

T5 /* compute the total payment for an item */ I

-

Shiporder (i1,ol)

Ship rder (i2,02)

k

Totalpayment (il)

...

Get (ol.Status)

Put (ol.Status)

Get (ol.Status)

Get (ol.Quantity)

...

Figure 7: Conflicting Actions with CommutatiC but not yet Committed Ancestws creating further children in the method invocation tree. After completing the execution of the children, the locks that have been acquired for the children are converted into retained locks. If t is a top-level transaction, all the locks held by t and its subtransactions are released. Finally, t is re-

tive ancestor pair. In this case, the conflict is in fact an implementation-based ”pseudo-conflict”, and the action that requests the conflicting lock is allowed to proceed as soon as the commutative ancestor of the lock holder commits. Figures 8 and 9 show the complete locking protocol in a pseudo-code notation. The pseudo-code of Figure 8 describes the execution of an open nested transaction, including lock requests and possible queueing, the invocation of children actions (recursive call of exec-transaction), and the conversion into retained locks or releasing of locks. The pseudo-code of Figure 9 describes the actual conflict test.

procedure exec-transaction (t) begin t.waits-for-set := empty for all locks h that are held or have been requested on t.object do b := test-conflict (h, t); /* transaction/subtransaction b blocks t */ if b # nil then add b to t.waits-for-set

The pseudo-code refers to the following conceptual ”data structures”: A lock (or ‘actually lock control block) is associated with a method name, an object id on which the method operates, optionally a list of actual parameters of the method, and the identification of a subtransaction that corresponds to the invoked method and holds or requests locks for its children. The ancestor chain of a subtransaction t is a sorted list of the (identifications of the) ancestors o f t in bottomup order.

fi od if t.waits-for-set is not empty then record the lock request of t in the queue of t.object wait for the completion of all transactions/ subtransactions in t.waits-for-set

The waits-for-set of a subtransaction t is a set of other transactions or subtransactions that are blocking t. Invoking a method on an object creates a new subtransaction t. A lock on t.object is requested in a mode that is derived from tmethod and possibly the actual parameters of t. The function test-conflict is called for each lock h that is currently held or has already been requested (but is not yet granted) on t.object. test-conflict returns the identification of a (sub)transaction b that must be completed before the lock can be granted. If nil is returned, no conflict exists and t can proceed acquiring the lock. Otherwise, t is added to the wait-for-set of b. Since there may be multiple holders of locks on t.object and/or multiple earlier lock requestors in the lock queue of t.object5, t may have to wait for the completion of more than one transactiodsubtransaction. t is blocked until all transactions/subtransactionsin its waitsfor-set are completed. As soon as t has acquired its lock, the method tmethod is actually executed on t.object, possibly

fi acquire lock on t.object

for all s in t.children do exec-transaction (s) od; if t.parent = nil then /* end of top-level transaction */ release all locks else convert all locks into retained locks

fi remove t from all waits-for-sets of other

transactions/subtransactions end exec-transaction Figure 8: Pseudo-code for Executing an Open Nested Transaction in an OODBS

5. We require that requested locks are granted in FCFS order.

240

moved from all waits-for-sets in which it was included, in order to resume the transactions/subtransactions that were blocked by t. The function test-conflict (h, r ) (Figure 9) is called to determine whether the lock requestor r is in conflict with the lock holder h. In addition, if a conflict is detected, then test-conflict retums the identification of the (sub)transaction h’ the commit of which r has to wait for. If h and r commute or belong to the same top-level transaction, no conflict is found and nil is retumed. If a conflict exists, the algorithm checks for commutative pairs of actions h’, r’ in the ancestor chains of h and r. If such an ancestor pair is found, the algorithm determines if h’ is already completed. This is done by inspecting the commit status of h’. Function test-conflict retums nil if h’ is indeed already committed; otherwise, h’ is retumed. If no pair of commutative ancestors is found, the root of h is retumed. In this case, r has to wait for the top-level commit of the transaction h belongs to.

function test-conflict (h, r) returns taid /* tests a lock requestor r against a held lock h and returns nil or the ancestor of h the commit of which r needs to wait for */ begin if h and r commute or h and r belong to the same top-level transaction then return nil fi for all h’ in the ancestor chain of h do for all r’ in the ancestor chain of r do if h’ and r’ commute then if h’ is completed then return nil else return h’ /* r may be resumed upon */ /* completion of h’ */ ti

5 Conclusion In this paper, we have developed an extended locking protocol for open nested transactions in OODBSs. The protocol is able to cope with the problem of ”bypassing the encapsulation of objects” in a reasonably efficient way. The protocol has the following beneficial properties.

ti od /* for all r’ */ od /* for all h’ */ return root of h /* worst case: waiting for the top-level commit */ end test-conflict

It can exploit the semantics of methods to enhance concurrency.

Figure 9: Pseudo-code for the Conflict Test of Open Nested Transactions in an OODBS

It does not impose any restrictions on the structure of transactions (i.e., the way in which methods are invoked). In particular, methods on encapsulated objects can in tum invoke other methods on other objects. It is based on a well-developed theoretical foundation [BBG89] that is useful in reasoning about the correctness of the protocol.

demadds for advanced transaction management methods and the promising results we achieved so far, we believe that it is worthwhile to pursue our open nested transaction approach to address these problems.

It preserves conventional page- or record-oriented locking protocols as special cases.

References

In this paper, we did not address the problem of non-disjoint complex objects. Our algorithm is, in principle, able to ensure semantic serializability also in the presence of such objects. The problem in this case is to test conflicts between method invocations on different but potentially non-disjoint complex objects. The approach that we pursue within our semantic locking protocol is to reconsider the commutativity of actions on different objects whenever there is a lock conflict on a potentially shared component during the execution of the actions’ descendants. So far, we have not considered recovery for OODBS transactions. Our approach will be to extend the recovery methods for multi-level transactions [WHBMBO, HW9 11 towards OODBS transactions. Because of the application

[AE92] Agrawal, D., El Abbadi, A., A Non-Restrictive Concurrency Control Protocol for Object-Oriented Databases, EDBT Conf., 1992 [BBG89] Been, C., Bemstein, P.A., Goodman, N., A Model for Concurrency in Nested Transactions Systems, Journal of the ACM Vo1.36 No. 1, 1989 [Bee831 Been, C., Bemstein, P.A., Goodman, N., Lai, M.Y., Shasha, D.E., A Concurrency Control Theory for Nested Transactions, ACM PODC Conf., 1983 [BM91] Been, C., Milo, T., A Model for Active Object Oriented Database, VLDB Conf., 1991 [BR88] Badrinath, B.R., Ramamritham, K., Synchronizing Transactions on Objects, IEEE Transactions on Computers Vo1.37 No.5. 1988

241

[BSW88] Been, C., Schek, H.-J., Weikum, G., Multi-Level Transaction Management, Theoretical Art or Practical Need?, 1st Int. Conf. on Extending Database Technology, Venice, 1988, Springer, LNCS 303 [Ca91] Cattell, R.G.G. (Guest editor), Special Section on Next-Generation Database Systems, Communications of the ACM Vo1.34 No.10, 1991 [CF90] Cart, M., Fenie, J., Integrating Concurrency Control into an Object-Oriented Database System, 2nd Int. Conf. on Extending Database Technology, Venice, 1990, Springer, LNCS 4 16 [CRR911 Chrysanthis, P.K., Raghuram, S., Ramamritham, K., Extracting Concurrency from Objects: A Methodology, ACM SIGMOD Conf., 1991 [Da78] Davies, C.T., Data Processing Spheres of Control, IBM Systems Joumal Vo1.17 No.2, 1978 [DHL91] Dayal, U., Hsu, M., Ladin, R., A Transactional Model for Long-Running Activities, VLDB Conf., 1991 [FLMW88] Fekete, A., Lynch, N., Memtt, M., Weihl, W., Commutativity-Based Locking for Nested Transactions, Technical Report MIT/LCS/TM-370, MIT, Cambridge (Mass.), 1988, to appear in: Joumal of Computer and System Sciences [Ga83] Garcia-Molina, H., Using Semantic Knowledge for Transaction Processing in a Distributed Database, ACM TODS Vol.8 No.2, 1983 [Gr81] Gray, J., The Transaction Concept: Virtues and Limitations, VLDB Conf., 1981 [He901 Herrmann, U., Dadam, P., Kuspert, K., Roman, E.A., Schlageter, G., A Lock Technique for Disjoint and Non-Disjoint Complex Objects, 2nd Int. Conf. on Extending Database Technology, Springer, 1990 [HH88] Hadzilacos, T., Hadzilacos, V., Transaction Synchronization in Object Bases, ACM PODS Conf., 1988 [HW88] M.P. Herlihy, W.E. Weihl: Hybrid Concurrency Control for Abstract Data Types. ACM PODS Conf., pp. 201-210, 1988. [HW91] Hasse, C., Weikum, G., A Performance Evaluation of Multi-Level Transaction Management, VLDB Conf., 1991 [KBG89] W. Kim, E. Bertino, J.F. Garza: Composite Objects Revisted. Proc. SIGMOD 89. In: SIGMOD Record 18(2), 337-347, 1989. [Ke87] Kelter, U., Concurrency Control for Design Objects with Versions in CAD Databases. Information Systems 12, 137-143, 1987. [Ko83] Korth, H.F., Locking Primitives in a Database System, Joumal of the ACM Vo1.30 No. 1, 1983 [LKS91] Levy, E., Korth, H.F., Silberschatz, A., A Theory of Relaxed Atomicity, ACM PODS Conf., 1991 [LMWF92] Lynch, N., Merritt, M., Weihl, W., Fekete, A., Atomic Transactions, Morgan Kaufmann, 1992 [Ma871 Martin, B.E., Modeling Concurrent Activities with Nested Objects, Int. Conf. on Distributed Computing Systems, Berlin, 1987

[Mo85] Moss, J.E.B., Nested Transactions: An Approach to Reliable Distributed Computing, MIT Press, 1985 [MGG86] Moss, J.E.B., Griffeth, N.D., Graham, M.H., Abstraction in Recovery Management, ACM SIGMOD Conf., 1986 [MR91] Muth, P., Rakow, T., Atomic Commitment for Integrated Database Systems, IEEE Conf. on Data Engineering, 1991 [MRKN92] Muth, P., Rakow, T.C., Klas, W., Neuhold, E.J., A Transaction Model for an Open Publication Environment, in: A.K. Elmagarmid (Ed.), Database Transaction Models for Advanced Applications, Mogan Kaufmann, 1992 [O’N86] O’Neil, P.E., The Escrow Transactional Method, ACM TODS Vol. 11 No.4, 1986 [PS87] D.J. Penney, J. Stein: Class Modification in the Gemstone Object-Oriented DBMS. Proc. OOPSLA 87. In: SIGPLAN Notices 22(12), 111-117, 1987. [RGN90] Rakow, T.C., Gu, J., Neuhold, E.J., Serializability in Object-Oriented Database Systems, IEEE Conf. on Data Engineering, 1990 [RL79] Rypka, D. J., Lucido, A. P.: Deadlock Detection and Avoidance for Shared Logical Resources, IEEE Transactions on Software Engineering, Vol. 5, No. 5, 1979 [SG88] Shasha, D., Goodman, N.: Concurrent Search Structure Algorithms, ACM TODS Vo1.13 No.1, 1988 [SS841 Schwarz, P.M., Spector, A.Z., Synchronizing Shared Abstract Types, ACM Transactions on Computer Systems V01.2 No.3, 1984 [SZ89] Skarra, A.H., Zdonik, S.B., Concurrency Control and Object-Oriented Databases, in: W. Kim, EH. Lochovsky (eds.), Object-Oriented Concepts, Databases, and Applications, ACM Press, 1989 [TPC90] Transaction Processing Performance Council, TPC Benchmark C (Order-Entry), Working Draft 4.1, 1990 [Wa84] Walter, B.: Nested Transactions whith Multiple Commit Points: An Approach to the Structuring of Advanced Database Applications, VLDB Conf., 1984 [We881 Weihl, W.E., Commutativity-Based Concurrency Control for Abstract Data Types, IEEE Transactions on Computers Vo1.37 No.12, 1988 [We891 W.E. Weihl: Local Atomicity Properties: Modular Concurrency Control for Abstract Data Types. ACM TOPLAS 11(2), 249-282, 1989. [Wei913 Weikum, G., Principles and Realization Strategies of Multilevel Transaction Management, ACM TODS Vo1.16 No.1, 1991 [WHBM90]Weikum, G., Hasse, C., Broessler, P., Muth, P., Multi-Level Recovery, ACM PODS Conf., 1990 [WS92] Weikum, G., Schek, H.-J., Concepts and Applications of Multilevel Transactions and Open Nested Transactions, in: A.K. Elmagarmid (Ed.), Database Transaction Models for Advanced Applications, Morgan Kaufmann, 1992

242