Copyright ACM, 2000

Mechanisms for Specifying Communication Behavior in Object Oriented Database Systems

Paulo F. Pires, Mário Roberto F. Benevides and Marta Mattoso

Computer Science Department

COPPE - Federal University of Rio de Janeiro

P.O. Box 68511, Rio de Janeiro, RJ, 21945-970, Brazil

Fax: +55 21 2906626

e-mail: pires, mario, marta @cos.ufrj.br

Abstract: Most object oriented concurrency control is dedicated to increase method execution concurrency, however they do not consider the inter-object behavior. In this paper we present mechanisms to deal with the communication behavior in OODBMS. We define linguistic constructors that describe both the internal and the external object communication behavior. We also present a decentralized transaction model and a protocol that guarantee the correct method execution for a single object (intra-object) and for a group of objects (inter-object) that cooperate to accomplish an activity.

Introduction

The communication among objects in an object-oriented system can be classified in internal and external levels [2]. The internal level (intra-object) describes the semantics of the object operations, that is, which operations can be executed concurrently and which are the correct operation execution sequences. The external level (inter-object) describes the cooperation among collections of independent objects to accomplish a task, that is, which are the correct message exchange sequences among different objects of this group. The external level is also composed by dynamic interactions between independent objects and the communication constraints on these interactions. The union of these two levels is the communication behavior of the objects.

An Object Oriented (OO) or Object Relational (OR) Database Management System (DBMS) may considerably increase its semantic power if the object communication behavior is incorporated to its object model. Conventional object-oriented models do not have explicit mechanisms to specify the object communication behavior. Therefore, the communication behavior is encapsulated into type definitions or implicit in sequences of method calls. Thus, those conventional models do not capture an important semantic information, transferring to the programmer the management of the code responsible for the object communication behavior.

The goal of our work is to incorporate mechanisms to deal with the communication behavior in OODBMS, especially those that are compatible with the ODMG-2.0 [3] standard. We define linguistic constructors that describe both the internal and the external object communication behavior. We also present a decentralized transaction model and a protocol that guarantee the correct method execution for a single object (intra-object) and for a group of objects (inter-object) that cooperate to accomplish an activity.

Many works, in the concurrency control area, use some kind of commutative-based mechanism to increase the method execution concurrency. Some [10, 11] present concurrency control protocols based on method commutativity, disregarding linguistic issues. Others [12, 13] define constructors for specifying the correct method execution sequences for one object type. These constructors are similar to languages that specify concurrent process like CCS [7], CSP [8] and p -calculus [9] and essentially describe the external behavior of objects without taking into account serializability issues. Francesco and Vaglini [4] propose the inclusion, in a database language, of a constructor to specify semantic conflicts and constraints derived from object type semantics. However, they do not consider the inter-object communication behavior.

In the object-oriented approach, it is believed that the type abstraction is too fine-grained for developing large-scale systems [1,2, 6, 14, 15, 16, 17]. Thus, there is a need for semantic constructors to model dynamic interactions among cooperative objects and also to group types in a task (transaction) oriented way. Nevertheless, none of these approaches consider the intra-object communication behavior.

Our work extends the ideas of Francesco and Vaglini [4] integrating the internal and external communication behavior of objects. We propose a common framework, the communication behavior constructor, for considering both the internal and external communication behaviors of objects. This feature contributes to the design and implementation of a transaction. Thus a programmer can specify a transaction and the internal concurrency control of each object using the same framework (the communication behavior constructor).

We also propose a specification and implementation of a modular transaction service that could be used as an add-on to OODBMS. This transaction service is fully distributed and it is specified using object-oriented technology. Independent objects compose the transaction service. Each database object is responsible for its own concurrency control while an independent scheduler (a coordinator) controls each transaction. Hence, there is no centralized control. Finally, our service is naturally distributed and its specification fully exploits the object-oriented computational model.

The remainder of this work is organized as follows. Section 2 describes the communication behavior constructor and presents a transaction protocol that is restricted to flat transactions. In Section 3 we extend the transaction protocol to support nested transactions and we also specify an object-oriented transaction service that supports object communication behavior. Section 4 shows a case study. Finally, Section 5 concludes our work and presents future directions.

The Communication Behavior Specification

We propose a common framework to handle both the internal and external communication behaviors of objects through a linguistic constructor named communication behavior. This constructor is based in the concurrent behavior constructor proposed by Francesco and Vaglini [4]. However, we extended their ideas so that the constructor would be able to handle the inter-object communication behavior. In Section 2.1 we present the specification of the communication behavior constructor while its implementation through a transaction protocol appears in Section 2.2.

The Communication Behavior Constructor

Two parts compose the communication behavior constructor (B): commutativity (R) and constraint (W) specifications:

Commutativity specification is a sequence of conditional rules that defines when a pair of methods (m1, m2) can be executed in any order without affecting the resulting observation a programmer may see on the object state. Thus, a commutativity specification states when two methods do not conflict.

A constraint specification is a set of rules, which defines constraints in external object behavior. Each rule (constraint) has the form entry ® F. F is a regular expression containing method object names and defines a language (L(F)) whose strings are concatenations of these names. The entry part is a logical expression composed by: (i) a method name with its formal parameters (M(P)); and (ii) condition C concerning parameters of M and/or the object state. C or M(P) can be omitted. If C is omitted then it is assumed to be true. If M(P) is omitted then the rule is valid to any method.

A constraint has a limited lifetime, its start point is specified by an entry condition and it stays active until a string of L(F) is recognized.

The inter-object communication behavior models activities, which are performed by database objects. These activities are object communication patterns that explicitly capture behavioral dependencies among cooperative objects [2]. An activity can be modeled as a complex object that has relationships to each one of objects that cooperate to accomplish the activity. These objects are the activity compound objects. Behavioral relationships and message exchanges occurring in an activity can be modeled using specific constraints defined against its compound methods.

In order to specify the inter-object communication behavior the constraint specification that is defined by the regular expression entry ® F, must be able to represent sequences of method executions composed by methods from different object types. Thus, the entry and F definitions were extended to consider both occurrences of methods from the object type itself and of methods from object types linked to it through ODL relationship attributes.

Internal Object Transaction Protocol

In this Section we describe the internal object transaction protocol that implements the object communication behavior constructor. This protocol is similar to the one proposed by Francesco and Vaglini [4]. Basically, we propose an object-oriented implementation of the protocol proposed by them.

Transactional Object Type

The abstract type TransacionalObject (Figure 1) implements the required operations for the internal object concurrency control. Through these operations an object can participate in the transaction protocol described in Section 3.

The commutativityTable instance variable stores for each type the specification of method commutativity. This instance variable is a bi-dimensional matrix R ranging over method names, whose elements are boolean expressions: mi(Pi) || mj(Pj) when C , that is, R [mi, mj] = C


interface TransactionalObject ( )

{

attribute TCommutativityTable commutativityTable;

attribute TGuardTable guardTable;

attribute TConstraintConflictTable constraintConflictTable;

attribute TConflictTable conflictTable;

attribute TWaitQueue waitQueue;

attribute TAutomatonStateList automatonStateList;

attribute TActiveTransactionList activeTransactionList;

// operations

void requestCommit ( );

void commit( );

void abort ( )

}


Figure 1 Transactional Object Type specification.

The guardTable stores instance variable constraint descriptions and can be modified at each transaction step. This structure has as many rows as constraints and each row has three columns. The first column corresponds to the entry and is the guard of the constraint (condition and expected event), the second is a pointer to the present state of the automaton which is associated with the constraint, the last is a flag which is true if the automaton is active, and false if not. If W is empty the guardTable contains only a position whose flag is false.

The constraintConflictTable instance variable has a structure whose columns are composed by the constraint (W) while each row corresponds to a different object method (m). This instance variable can also be modified at each transaction step. For each method (m), the constraintConflictTable instance variable holds: (i) false, either if m can be accepted by the active automaton i in its present state or if i is inactive; and (ii) true, if m cannot be accepted by the active automaton i.

Another instance variable, named conflictTable, is dynamically associated to each transaction Ti. It is created at the first request of Ti and destroyed when Ti commits or aborts. Each row corresponds to a different object type method (m). For each method, conflictTablei [m] contains a condition under which a future call to m conflicts with a method previously executed by Ti. As particular cases, we may have that: (i) conflictTablei [m] = false, when m (if invoked by a transaction Tj Ti) conflicts with no method previously executed by Ti; and (ii) conflictTablei [m] = true, when m can no longer be allowed to execute, because it conflicts with at least one method executed by Ti.

The activeTransactionList instance variable stores a list of all active and not committed transactions that access the object. A flag is linked to each transaction and holds: (i) false if the transaction does not request commit; and (ii) true otherwise.

An object responds to a commit request only when all flags stored in activeTransactionList holds true. At this point the object is prepared to commit. When an object receives an abort message, it sends abort messages to all transactions stored in activeTransactionList.

There are two more instance variables: a wait queue (waitQueue) storing suspended methods (along with their transaction identifiers) and an automaton state list (automatonStateList) storing a consistent state for each automaton. The interface of the TransactionalObject type is composed by three methods: requestCommit, commit, and abort. These methods are accessed by the Transaction Management Service and are described in Section 3.

Transaction Service

We propose a modular transaction service that is built on top of the intra-object transaction protocol described in the Section 2.2. This transaction service is fully distributed, each object is responsible for its own internal concurrency control while an independent object named Transaction Coordinator manages each transaction (activity). Three object types compose this transaction service: Clients that are application programs, Transactional Servers, and Transaction Coordinators.

The Transactional Server type is a specialization of the abstract type TransactionalObject. Operations derived from the abstract type TransactionalObject implement the internal object concurrency control. These operations allow an object to participate in the transaction protocol.

The TransactionalObject type contains the following public methods: requestCommit, commit, abort. These methods are the object interface to the OODBMS transaction service. We describe the semantic of these methods in the Section 3.1.1.

Transaction Coordinators are objects that manage the commitment protocol (Figure 2). These objects receive commit or abort requests from client objects and execute the commitment protocol. In order to implement the commitment protocol these objects must provide the following public methods: begin, register(serverId), prepared(vote), commit(idsServerList), abort(idsServerList) and done(idServer). We describe the semantic of these methods in the Section 3.1.

External Object Transaction Protocol

The protocol that controls transactions is the two phase commit protocol - 2PC [18], which is used to enforce atomicity in distributed environments. The concurrency control that we propose in this work considers each OODBMS object as autonomous units regarding its internal concurrency control. Thus the 2PC is necessary to enforce transaction atomicity.

Protocol Execution

A client object initiates a new transaction through a call to the begin method of a coordinator object that was previously instantiated by the client. When the client object invokes a server object method, it passes the identification of the coordinator object that controls the transaction along with the method call. Then, the object server invokes the register(serverId) method of the coordinator object to inform that this server object (sending its identification as a parameter) is participating in the transaction that is controlled by this coordinator object.

The commitment protocol is initiated when a client object invokes the commit method of a coordinator object. The protocol is executed as follows:

  1. Beginning of the first phase: The coordinator object begins the first phase of the protocol by invoking the requestCommit method of all server objects involved in the transaction. Identifiers of these objects are available at the transactionalServersList instance variable of the coordinator object and it is updated whenever a new register(serverId) message arrives.
  2. The coordinator object waits for the answer of all the participating server objects.
  3. When a requestCommit message arrives at a server object it updates the activeTransactionList instance variable adding the identifier of the coordinator object that sent the requestCommit message. When a server object receives its first requestCommit message it blocks new transaction requests (those that are not stored at activeTransactionsList) updating the waitQueue instance variable with identifiers of invoked methods along with identifiers of coordinator objects of those new transactions. The server object will send a prepared(true) message indicating that it is prepared to commit only after it has received requestCommit messages from all coordinator objects stored at its activeTransactionsList instance variable. A transaction server object can also send a prepared(false) message for instance, if it is not prepared to commit either due to a local failure or because it received an abort message from another coordinator object.
  4. Beginning of the second phase: When a coordinator object receives prepared(true) messages from all transaction server objects that participate in the transaction, the coordinator object decides to commit the transaction. If a coordinator object receives one or more prepared(false) messages it can decide to abort the transaction. It can also decide to abort the transaction due to a time out of any prepared messages.
  5. A coordinator object sends commit or abort messages (according to its decision) to all server objects that participate in the transaction. If the coordinator object decides to interrupt a transaction (sending abort messages), server objects that participate in the transaction must abort all operations that belong to the aborted transaction.
  6. Server objects reply a commit or abort message sending done(serverId) message to the coordinator object.
  7. The commitment protocol is concluded after the reception, by the coordinator object, of done messages from all server objects involved in the transaction. Then, the coordinator object informs the end of the transaction to the client object. Thereafter the client object can destroy the coordinator object or use it in another transaction.

 The client object can also decide to invoke the abort method of the coordinator object. In this case, the commitment protocol is executed in only one phase. The coordinator object sends abort messages directly to all the server objects those participate in the transaction.

When a coordinator object initiates the commitment protocol it is possible that not all server objects have registered due to fail or network overload. In this scenario, the coordinator object would not consider unregistered server objects as participants in the transaction, taking to a dysfunction of the commitment protocol. To solve this problem, the client object passes as parameter, in the commit (or abort) method call, a list containing all server object identifiers involved in the transaction. Thus, the coordinator object is aware of which server objects participate in the transaction.

Nested Transactions

Nested transactions can be defined as transactions that are executed inside other transactions [5]. The nested transaction model is based on the idea of breaking the transaction in a subtransaction hierarchy. The main transaction is denominated parent transaction and it may start subtransactions, which behave as dependent transactions. A subtransaction can also start a group of other subtransactions, thus creating a hierarchical structure of transaction executions. A transaction that has no ancestral is denominated a top-level transaction and has the same semantics of flat transactions (not nested). If a subtransaction aborts, then all its effects must be canceled. This includes all effects generated by its own subtransactions. However, the execution of an abort in a subtransaction does not abort its parent transaction. The parent transaction should only be informed of the occurrence of the subtransaction abort. During a subtransaction execution, updates made by the subtransaction are not visible to other transactions or subtransactions. When a subtransaction commits, its updates become visible to its parent transaction and to all its siblings (subtransactions with the same parent). A subtransaction has the isolation and the atomicity properties with regard to its sibling subtransactions. However, effects of a subtransaction only become permanent when the top-level transaction commits.

Figure 2 - Nested Transaction Object Model

The nested transaction model can be directly applied to an OODBMS. Each method of an object can be programmed as a transaction. Thus, a method can be executed as an independent transaction (top-level transaction) or it can be called by another transaction, therefore executing as a subtransaction. Thus, nested method calls create a group of transactions that follows the nested transaction model.

Protocol Execution

The nested transaction protocol has the same execution rules as the flat transaction protocol. However, a transaction can have different levels and coordinator objects can assume two different behaviors; i.e. top-level transaction coordinator or subtransaction coordinator.

The top-level transaction coordinator operates with the same protocol of flat transactions (2PC). Subtransaction coordinator objects execute a commit protocol slightly different. In order to manage subtransactions subtransaction coordinator objects execute a commit protocol in three phases. To implement this protocol, a new class, denominated SubtransactionCoordinator, must be added to the transaction model (Figure 2).

The SubtransactionCoordenator class is a specialization of the Coordinator class where the method requestCommit(serverIdsList) is added. Server objects that start subtransactions invoke this method to begin the commit of the subtransaction. The nested transaction protocol is explained in Section 4.1.

Nested Transaction Protocol Example

Consider classes CheckingAccount and SavingsAccount. The CheckingAccount class represents the financial movements of a bank customer and it has the following methods: balance that returns the available amount of money in the checking account; deposit that adds a certain amount of money to the checking account, withdraw that debits an amount of money from the checking account. Also, it is known that the withdraw method can only be executed if balance is larger or equal to the withdraw value. Some properties of the class CheckingAccount can be derived from the semantic of its methods. For example, two successive calls to balance always commute, because balance is a read operation and does not affect the object state. Also, two successive calls to withdraw always commute, because the object state is the same despite the method execution order. Methods balance and withdraw commute only if the withdraw amount is less than the amount of money in the account. Different results can be observed depending on the method execution order between balance and withdraw methods in a CheckingAccount object. However, if the value of the withdraw is greater than the amount of money in the account, the reading of a balance will be the same, despite of the execution order between the withdraw and balance methods. A similar result is achieved when a withdraw method is performed before or after a deposit method execution. If the value of the withdraw is smaller or equal to the value of the balance, the object state will be the same, despite of the execution order of methods. On the other hand, if this condition is not satisfied, the execution order of these methods can lead to different states (a withdraw cannot be accepted prior to a deposit). Finally, different results are always achieved when a balance method is executed before or after a deposit method.

The class SavingsAccount represents savings of a bank customer and it has the following methods: balance that returns the available amount of money in the savings account; transfer that adds a certain amount of money to the savings account, this method considers that the savings is always made as a money transfer from the checking account to the savings account; withdraw that debits an amount of money from the savings account and transfers it to the checking account using the deposit CheckingAccount method. A savings account withdraw can only be done if the balance of the savings account is greater or equal to the withdraw value. Some properties of the class SavingsAccount can be derived from the semantic of its methods. First, two successive calls to balance always commute, because balance is a read operation and does not affect the object state. Two successive calls to withdraw also commute, because the object state after the execution of these operations is the same in all cases. The balance and withdraw methods are only independent if they are executed in a SavingsAccount object whose amount of money is smaller than the withdraw value. In fact, different results are achieved depending on the order execution between balance and withdraw methods in a SavingsAccount object. Nevertheless, if the withdraw is not accepted due to fund inadequacy, the reading of this balance will be the same, despite of the execution order between the balance and withdraw methods. A similar result is achieved when a withdraw is performed before or after a transfer method execution. If the value of the withdraw is smaller or equal to the value of the amount of money of the savings account, the object state will be the same despite of the execution order of methods. On the other hand, if the described condition is not satisfied, the execution order of methods can lead to different states (a withdraw method execution cannot be accepted before a transfer method is executed). Finally, different results are always achieved when a balance is performed before or after a transfer method execution.

Besides rules described previously, some constraints can be imposed to the external behavior of classes CheckingAccount and SavingsAccount. For instance, we can restrain the amount of withdraws at weekends. This can be specified by a constraint rule containing an entry composed by the condition value <= maxValue and by the method call withdraw(value) (first constraint rule of Figure 3). Other restrictions can be specified, for instance, the withdraw method cannot be executed when the account balance is zero.

The semantic described above is completely dissociated from the class definition when conventional ODL is used. Consequently this semantic specification is postponed to the application program and different users may not become aware of this behavior. However with simple extensions we can incorporate the communication behavior to type class definition.

The complete specification of the CheckingAccount and SavingsAccount, using the ODL syntax, is presented in Figure 3.

An Example Scenario With Nested Transactions

This Section shows how the communication behavior expressed in the class definitions is combined with the nested transaction protocol. Consider that a transaction T1 (that is managed by the Coordinator object CT1) performs a saving of $150.00 in the SavingsAccount object SA (transfer (150.00, CT1)) (Figure 4). Suppose also that there is no active automata or transactions in SA. Then the SA.commutativityTable instance variable, derived from the commutative specification of the communication behavior of the class SavingsAccount, is defined as follows:

interface CheckingAccount ( ) {

attribute Long balanceValue;

attribute TClient client;

attribute SavingsAccount SAList;

// type methods

Long balance ( );

void withdraw ( in Long value );

void deposit ( in Long value );

ComunicationBehavior: // Comunication Behavior Specification

//Commutativity Specification

balance || balance;

deposit || deposit;

withdraw (value1)|| withdraw(value2)

when ( not (value1+value2) > balance() and value1 < balance() and value2 < balance() and value1 <> value2 );

balance || withdraw(value) when value > balance();

withdraw(withdrawValue) || deposit(depVal) when withdrawValue < = balance();

// Constraint Specification

date Î weekend ® (withdraw(withdrawValue) when withdrawValue <= maxValue + deposit(value) + balance() )* date Ï weekend;

balance = 0 ® (balance())* deposit(depVal); }

Interface SavingsAccount ( ) {

attribute Long balanceValue;

attribute TClient client;

attribute CheckingAccount CA;

// type methods

Long balance ( );

void transfer ( in Long value );

void withdraw (in Long value );

ComunicationBehavior: // Comunication Behavior Specification

// Commutativity Specification

balance || balance;

transfer || transfer;

withdraw (value1)|| withdraw (value2)

when ( not ( value1+value2) > balance() and value1 < balance() and value2 < balance() and value1 <> value2 );

balance || withdraw (value) when value > balance();

withdraw (withdrawVal) || transfer(transferVal) when withdrawVal < = balance;

// Constraint Specification

date() Î weekend ® (withdraw (withdrawVal) when withdrawVal <= maxValue + transfer (transferVal) + balance)* date Ï weekend;

balance = 0 ® (balance())* transfer (transferVal); }

Figure 3 Definition of CheckingAccount and SavingsAccount classes.

 

balance

withdraw(withdrawVal2)

transfer(transfVal2)

balance

true

withdrawVal2 > balance()

false

transfer(withdrawVal1)

withdrawVal1>= balance()

not ( withdrawVal1

+ withdrawVal2) > balance()

and withdrawVal1< balance()

and withdrawVal2< balance()

and withdrawVal1<> withdrawVal2)

withdrawVal1<= balance()

transfer(transfVal1)

False

withdrawVal2<= balance()

true

Suppose that the state s of SA has the balanceValue=200.00 instance variable. When this request arrives at SA, it verifies if T1 already belongs to its active transaction list (SA.activeTransactionsList). Since there is no active transaction, SA sends a register(SA) message to the coordinator object CT1. If, for instance, date()Ï weekend, and all guards in SA.guardTable have value false; it means that all automata remain inactive and the request transfer(150.00, CT1) can be executed. The SA.conflictTableListt1 instance variable is created for T1 as follows:

Balance

True

Withdraw (withdrawVal)

False

Transfer (transferVal)

False

Since the execution of the transfer method performs a call to the withdraw method of the CheckingAccount object associated to the SavingsAccount object SA (CA:=SA.cc), a subtransaction is started by SA. In order to start a new subtransaction, SA instanciates a subtransaction Coordinator CST1.1. Next, SA invokes the begin method of CST1.1 starting a new subtransaction T1.1. Then, SA invokes the withdraw (150.00, CST1.1) method of the object CA.

Suppose that there is no active automata or transactions in CA. The CA.commutativityTable instance variable derived from the commutative specification of the communication behavior of the class CheckingAccount, is defined as follows:

 

balance

withdraw(withVal2)

deposit(depVal2)

balance

true

valueTransfer > balance()

false

withdraw (withVal1)

withVal1 >= balance()

not (withVal1 + withVal2) > balance()

and withVal1 < balance()

and withVal2 < balance()

and withVal1 <> withVal2)

withVal1 <= balance()

deposit(depVal1)

false

withVal2 <= balance()

true

Suppose that the withdraw(150.00, CST1.1) request done by SA, is the first request to CA and it is in a state s in which the balanceValue=150.00. When this request arrives at CA it verifies if the transaction T1.1 already belongs to its active transaction list (CA.activeTransactionsList). Since there is any active transaction, CA sends a register(CA) message to the Coordinator object CST1.1. Suppose that date()Ï weekend thus, all guards in CA.guardTable have value false; therefore, all automata remain inactive and the withdraw(150.00, CST1.1) method can be executed. The CA.conflictTableListt2 instance variable is instantiated to the transaction T1.1 as follows:

Balance

True

withdraw (withVal)

False

deposit (depVal)

False

Now, suppose that another transaction T2 requests the execution of a withdraw(300.00, CT2) method of the object CA. When this request arrives at CA it verifies whether that the transaction T2 already belongs to its active transaction list (CA.activeTransactionsList). Since the only active transaction is T1.1 ( T2), CA sends a register(CA) message to the Coordinator object of T2 (CT2). Since CA.guardTable[2,1] = true, the automaton 2 become active (CA.guardTable[2,3] = true) and CA.ConstraintConflictTable is modified as follows:

 

Constraint 1

Constraint 2

Balance

False

False

withdraw (withVal)

False

True

deposit (depVal)

False

False

Instance variables CA.conflictTableListT2 and CA.ConstraintConflictTable[withdraw,2] must be verified:

NOT ( transfVal1+ transfVal2) > balance() AND transfVal1< balance() AND transfVal2< balance() AND transfVal1<> transfVal2 )

Therefore, there is a conflict and the method execution is not allowed. Since transaction T2 does not belong to the active transaction list in CA, it is inserted in the wait queue (CA.waitQueue instance variable).

The commitment protocol of the transaction T1 is described as follows:

  1. To start the commitment protocol of the transaction T1 the Client object sends a commit(serverIds) message to the Coordinator object of T1 (CT1).
  2. When CT1 receives the commit(serversIds) message it starts the first phase of the commitment protocol sending a requestCommit(CT1) message to SA (it is the only Server object that participates in T1 serverIds = { SA }).
  3. When SA receives the requestCommit(CT1) message it updates its activeAscendingTransactionsList instance variable indicating that the transaction T1 (managed by CT1) has already requested its commit. Following, SA queries its activeDescendingTransactionsList instance variable to check if T1 has any descending transaction. Since there is a descending transaction (SA.activeDescendingTransactionsList(T1)={T1.1}), SA must send a requestCommit(serverIds) message to the Coordinator object (CST1.1) of T1.1.
  4. When CST1.1 receives a requestCommit(serverIds) message it starts the first phase of T1.1 commitment protocol sending a requestCommit(CST1.1) message to object CA which is the only object that participates in T1.1 (serverIds={CA}).
  5. When the CA receives the requestCommit(CST1.1) message it updates its CA.activeAscendingTransactionsList instance variable indicating that T1.1 (managed by CST1.1) has already requested its commit. Next, CA queries its activeDescendingTransactionsList instance variable verifying whether T1.1 has any descending transaction. Since there is no descending transaction (CA.activeDescendingTransactionsList(T1.1)={ }), CA must verify whether that all active transactions have already requested their commit. Since the CA.activeDescendingTransactionsList={T1.1} instance variable and T1.1 has already requested its commit, CA must send a prepared(true, CA) message to CST1.1.
  6. After receiving the prepared(true, CA) message, CST1.1 updates its transacionalServersList instance variable indicating that CA is prepared to commit and it verifies if there is another Server object under its control. Since CST1.1.transacionalServersList = {CA}, CST1.1 can start the second phase of T1.1 commitment protocol by sending a prepared(true, CST1.1) message to its client object (CST1.1.transacionalServersList = {SA}).
  7. When SA receives the prepared(true, CST1.1) message it updates its activeDescendingTransactionsList instance variable, indicating that T1.1 is ready to commit, and it verifies if there is another subtransaction that is not ready to commit. Since SA.activeDescendingTransactionsList={T1.1}, there is no other subtransaction and SA must query SA.activeAscendingTransactionsList to verify if all ascending transactions have already requested their commit. Since T1 has already sent its requestCommit message and SA.activeAscendingTransactionsList={T1}, SA sends a prepared(true, SA) message to CT1.
  8. After receiving the prepared(true, SA) message, CT1 updates its transacionalServersList instance variable indicating that SA is prepared to commit and it verifies if there is another Server object that is not prepared to commit. Since CT1.transacionalServersList={SA}, CT1 starts the second phase of T1 commitment protocol, sending a commit(CT1) message to SA, which is the only object that participates in T1 (CT1.transacionalServersList = {SA}).
  9. When SA receives the commit(CT1) message it updates its SA.activeAscendingTransactionsList instance variable indicating that T1 (managed by CT1) committed. Next, SA queries its activeDescendingTransactionsList instance variable to verify if T1 has any descending transaction. Since there is a descending transaction (SA.activeDescendingTransactionsList(T1)={T1.1}), SA must send a commit message to the Coordinator object (CST1.1) of T1.1. Thereafter, SA waits for the done message from the Subtransaction Coordinator object of T1.1.
  10. When CST1.1 receives a commit(serverIds) message it starts the third phase of T1.1 commitment protocol by sending a commit(CST1.1) message to object CA. Thereafter, CST1.1 waits for the done message from CA.
  11. CA locally commits T1.1. When the CA receives the commit(CST1.1) message it updates its CA.activeAscendingTransactionsList instance variable indicating that T1.1 (managed by SC1) committed. Next, CA queries its activeDescendingTransactionsList instance variable verifying if T2 has any descending transaction. Since there is no descending transaction (CA.activeDescendingTransactionsList(T1.1)={ }), CA locally commits T1.1 and sends a done(CA) message to CST1.1.
  12. When CST1.1 receives the done(CA) message it ends T1.1 commitment protocol sending a done(CST1.1) message to SA.
  13. When SA receives the done(CST1.1) message it updates its SA.activeDescendingTransactionsList instance variable indicating that T1.1 (managed by CST1.1) has already committed. Following, SA queries its activeDescendingTransactionsList instance variable to see if there is any descending transaction (with the same ancestral transaction as T1.1) that did not commit. Since SA.activeDescendingTransactionsList(ancestral(T1.1))={T1.1}, there is no other descending transaction and SA can locally commit the transaction ancestral(T1.1) = T1. Then, SA sends a done(SA) message to CT1.
  14. Finally, CT1 finishes the T1 top-level transaction commitment protocol by sending an ackCommit message to the transaction Client object (CT1.clientObject).

The client object can also decide to invoke the abort method of the coordinator object of the top-level transaction. In this case, the commitment protocol is performed in only one phase. The coordinator object sends abort messages to all server objects that participate in the transaction. Then, server objects send abort messages to all subtransaction coordinator objects. These objects perform the abort protocol recursively until an abort message reaches a server object that run atomic transactions. Note that these atomic transactions must belong to the same tree as the top-level transaction.

 

Figure 4 - A nested transaction scenario.

 

 

The internal concurrency control protocol of server objects can lead to a deadlock when a server object (S) invokes a method of another server object (S) that participates in some ascending transaction (t) of a transaction (t) which is started by S. If the server object S has already received a requestCommit message, then active transactions will be already grouped and any new transaction will be automatically blocked by S. Thus, the transaction t will be blocked by server object (S) leading to a deadlock because transaction t depends on transaction t to proceed. To solve this problem, the top-level transaction identifier is passed as parameter in the begin method of the coordinator object.

Conclusions

An Object Oriented Database Management System (OODBMS) or an Object Relational Database Management System (ORDBMS) may considerably increase its semantic power if the object communication behavior is incorporated to its object model. Thus, we present a linguistic constructor that may be added to class definition and express both the internal and external communication behaviors. The case study shows the simple syntax expressing the semantic of the communication behavior concentrated in one place. We also present a transaction model and a protocol that implement the concurrency control embedded in the class definition.

Considering each method as a single transaction and introducing data structures based on automata to control the object behavior, we presented dynamic interactions and independent schedulers that cooperate on the three phase commit protocol. The example also shows how nested transactions can execute concurrently since each scheduler controls its own group of objects and the only centralized control occurs at commit with the involved objects on the transaction.

Therefore, through this distributed control we improve the concurrency level and granularity of transactions. This distributed control is made possible through the proposed data structures shown along the example. Despite the number of auxiliary data structures for each database object, they may be incorporate to the descriptors that already accompany objects to memory and they are easier to handle than the large lock tables and other set structures.

Thus, we believe that the management cost of those auxiliary structures is compensated by their adequacy to the object oriented memory model implementation together with a high-level semantic power expression.

References

  1. Helm, G., Holland, I.M., Gangopadhyay,D., "Contracts: Specifing Behavioral Composition in Object Oriented Systems. In Proceedings of ACM OOPSLA, pp. 169-180, Ottawa. Canada, 1990.
  2. Liu, L., Meersman, R., "The Building Blocks for Specifying Communication Behavior of Complex Objects: An Active Driven Approach", ACM Transactions on Database Systems, vol.21, no.2, pp. 157-207, Jun, 1996.
  3. Cattel, R. G. G., Barry, D.K. (eds), The Object Databases Standard: ODMG-2.0, Morgan Kaufmann Publishers, EUA, 1997.
  4. Francesco, N., Vaglini, G., "Concurrent Behavior: A Construct to Specify the External Behavior of Objects in Objects Databases", Distributed and Parallel Databases, vol.2, no.1, pp.3358, Jan, 1994.
  5. Linch, N., et al, Atomic Transactions, Morgan Kaufmann Publishers, EUA, 1994.
  6. Wirfs-Brock, R., Wilkerson, B., "Object-oriented design: a responsibility-driven approach, in Proceedings of ACM OOPSLA, pp.71-76, New Orleans L.A., Oct 1989.
  7. Milner, R., Communication and Concurrency. International Series in Computer Science. Prentice-Hall, Englewood Cliffs, NJ, 1989.
  8. Hoare, C. A. R., Communicating Sequential Processes. Prentice-Hall, London, 1985.
  9. Milner, R., Parrow, J., Walker, D., "A calculus for mobile process (Parts I and II)", Information and Computation, vol.100, pp.1-77, 1992.
  10. Herlihy, M.P., Weihl, W.E., "Hybrid concurrency control for abstract date types," J. Comput. System Sci., vol. 43, pp. 25-61, 1991.
  11. Schwarz, P.M., Spector, A.Z., "Synchronizing shared abstract types," ACM TOCS, vol. 2, pp. 23-250, 1984.
  12. Nierstrasz, O., Papathomas, M., "Viewing object as patterns of communicating agents", in Proc. ECOOP/OOPLA 90, 1990.
  13. Van Den Bos, J., Lafra, C., "PROCOL: a parallel object oriented language with protocols", Proc. OOPSLA 89, SIGPLAN Notices, vol. 24, no. 10, pp. 95-102, 1989.
  14. Lieberherr, K., "Object-oriented programming with class dictionaries", J. Object-Oriented Program. 1, vol. 3, pp. 8-22, 1988.
  15. Dayal, U., Hsu, M., Ladin, R., "A transaction model for longrunning activities", in Proceedings of the Seventeenth International Conference on Very Large Databases, pp.113-122, Barcelona, Spain, Sep, 1991.
  16. Ngu, A. H. H., "Transaction modeling", in Proceedings of the International Conference on Date Engineering, pp.234-241, Los Angeles, CA, Feb, 1989.
  17. Markowitz, V. M., "Representing processes in the extended entity-relationship model", in Proceedings of the International Conference on Date Engineering, 103-110, Los Angeles, CA, Feb, 1990.
  18. Bernstein, P.A., Hadizlacos, V., Goodman, N., Concurrency Control and Recovery in Databases Systems, Addison-Wesley, USA, 1987.

Copyright 2000 ACM

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. To copy otherwise, to republish, to post on servers or to redistribute to lists, requires prior specific permission and or fee.
SAC 2000 March 19-21 Como, Italy
(c) 2000 ACM 1-58113-239-5/00/003>...>$5.00