Operational semantics of transactions(8)

Mathematics is forcing towards a consistent framework of theory development. Computer Science is an engineering discipline and sometimes suffers from ad-hoc definitions. Transactions are a concept that is commonly used in the database area. It is often def

Release as early as possible:Whenever the trans-action does not need the data from loca-

tion the lock is released.If the transaction

aborts a specific recovery technique is nec-

essary.

Release at the end of the transaction:All locks obtained by the transaction are released at

the end.

The utilization of the ReadLock(location)and WriteLock(location)is similar.Read locks are collected as long as there is no write attempt.If there is a write attempt to loc by t then the set of read lock to the location is singleton ReadLock= {t}or empty.Otherwise the transaction either must be aborted or must cause an abort of the other transactions using this location.

In the case of occupied locks two options can be applied:

Aborting the transaction:The transaction cannot be continued and is aborted.

Delaying the transaction:The transaction is transferred to a wait state.The state is

changed whenever all locks can be obtained.

The invocation of aborted or not completed transactions may be ordered by a number of ap-proaches,e.g.,

Kill-wait approach:If a transaction t makes a re-quest that competes with an operation of

another transaction t then the order of the

transaction request thefirst transaction to

wait if the order of t is less than that of t .

In the other case t is aborted.

Wait-die approach:If the transaction t is com-peting with another transaction t and the

order of thefirst transaction is less than

that of the second thefirst transaction is

aborted.In the other case,thefirst trans-

action waits.

Typical orders are based on time stamps.

The locking may be performed on locations or on clusters of locations,e.g.,pages.In this case we use predicate locks which specify the granularity of locking.

Intermediate storage solutions:We may execute all transactionsfirst and use an intermediate storage UsedDB(loc)for the data that have already been obtained by other transactions.In this case,the ReadOwnDB rule is changed by a locking rule:

ReadOwnDB(where:Location):

IF UsedDB(loc)=undef∨

UsedDB(loc)=Self

THEN

CurrentDB(Self,loc):=StableDB(loc)

UsedDB(loc):=t

ELSE Status(Self):=aborted

ENDIF

In a similar form the FreeOwnDB rule is changed by adding actions for release of locations in UsedDB.

The variety of solutions discussed for lock space solutions is also applicable to the case of inter-mediate storage.

Monitor-based solutions:Shared data environments can be enhanced by monitors,i.e.,extensions of the objects by modules acting similar to an access and write guard.Any transaction accessing or

writing to objects performs its operation through the monitor associated with that object.Moni-tors are therefore locking programs on the stor-age level.If an object is unlocked then a trans-action may access the object and write to the object.A transaction may obtain object locks and release them in the FreeOwnDB rule.

We may distinguish,therefore,a number of ap-proaches for implementing monitors similar to the implementation of lock space solutions.The transaction is performing in the BOT a message exchange with the StableDB.Similarly to lock space solutions,optimistic and pessimistic strate-gies and release strategies can be applied.

Let us change the rule set used above for the pes-simistic locking at the beginning and abortion of the transaction if the locks cannot be obtained: CreateOwnDB:

CurrentDB(Self,*):=undef

Transfer4Write(Self,*):=undef

FOR ALL x∈

{loc|read(loc)∈Content(Self)

∨write(loc)∈Content(Self)} DO

IF Lock(loc)=undef

THEN Lock(loc):=t

ELSE Status(Self):=failed

ENDDO

This locking technique is combined with release at the end by a change of the following rule: FreeOwnDB:

FOR ALL loc:(Lock(loc)=t)

DO Lock(loc):=undef

ENDDO

The other rules remain unchanged.

Now we can prove the following property: Proposition3Transaction execution in the in-private setting based

·on pessimistic locking at the beginning

·with the aborting option if locks cannot be obtained ·with release at the end

is a conservative refinement of the relation˘Ξ

−→. Similar propositions can be derived for the other iso-lation solutions.Most DBMS use locking techniques. Older DBMS have used also techniques based on in-termediate storage.These solutions have shown sim-ilar performance parameters as locking techniques.

Monitor-based techniques are not used in classi-cal relational DBMS.These solutions are currently experienced to real-time and distributed databases. As far as we know,however,these techniques are not well-documented.

3.5Operational Semantics for Transactions

in the In-Place Setting

Let us now discuss in brief the in-place setting for transactions.We follow the approach used in section 3.4.We introduce the general state description.We can derive similar properties.The in-place setting is an optimistic strategy.If the transactions does not abort the treatment is much simpler than in the case of the in-private setting.This advantage is,however,