An Optimistic Concurrency Control Approach Applied To .

WSEAS TRANSACTIONS on COMPUTERSWalid Moudani, Nicolas Khoury, Mohamad Husseinway to reduce the number of transaction restarts isto dynamically adjust the serialization order of theconflicting transactions [4]. When some dataconflict with the validating transaction is detected,there is no need to restart the conflicting transactionimmediately. Instead, a serialization order can bedynamically defined as follows: a forwardvalidation is applied when we have a read-writeconflict or write-write conflict between Tv and T jPriority Two Phase Locking (STCHP-2PL) firstjudges whether the conflicting operations meetoperation similarity (i.e. if two different transactionsoperations operate on the same data variable X andreturns similar values of it), then it allows them toexecute concurrently. Therefore it uses an extendedtype of locks called share lock which does notconflict with any lock (Read or Write type locks).Therefore, in addition to the priority of transactionsand temporal consistency checking, The STCHP2PL uses operation similarity factor to guaranteetemporal consistency of transactions and increaseconcurrency.respectively, and a backward validation is appliedwhen we have write-read conflict between Tv andT j respectively.To preserve serializability with OCC methods, ifvalidating transaction Tv has to be serialized beforeactive transaction T j , the following two conditions2.2 Optimistic Concurrency ControlThe basic idea of an optimistic concurrency controlmechanism is that the execution of a transactionconsists of three phases: read, validation and writephases [11]. In the OCC, conflict detection andresolution are both done at the validation phasewhen a transaction completes its executionmust be satisfied [13]: No overwriting: The writes of Tv should notoverwrite the writes of T j No read dependency: The writes of Tv shouldnot affect the read phase of T j2.2.1 Validation phase in OCCIn the validation phase of transaction Ti , the methodchecks that Ti does not interfere with anycommitted transactions or with any othertransactions currently in their validation phase. Inthe OCC methods, the validation phase can beperformed in one of two ways: Backward validation: in methods that performbackward validation, the validating transactioneither commits or aborts depending on whether ithas conflicts with transactions that have alreadycommitted. So this scheme does not allow us totake transaction characteristics into account andit is not suitable for real time database. Forward validation: in methods that performforward validation, the validating transaction orthe conflicting ongoing transactions can beaborted to resolve conflicts. This scheme can beextended to real time database since the timingcharacteristics of transaction can be consideredand proper decision can be taken in aborting,delaying the committing transaction or abortingthe conflicting ongoing transactions [6].There are three possible types of data conflictswhich can induce serialization order between avalidating transaction Tv and a conflictingtransaction T j : Read-Write conflict between Tv and T j canbe resolved by adjusting the serializationorder between Tv and T j as Tv T j . Itmeans that the read of Tv cannot be affectedby T j ’s write. This type of serialization adjustment is called forward ordering.WS (Tv ) RS (T j ) (Write-Read conflict):Write-Read conflict between Tv and T j canbe resolved by adjusting the serializationorder between Tv and T j as T j Tv . Itmeans that the read phase of T j is placed before the write of Tv . This type ofserialization adjustment is called backwardordering.WS (Tv ) WS (T j ) (Write-Writeconflict): Write-Write conflict between Tvand T j can be resolved by adjusting the2.2.2 Dynamic adjustment of serializationorderThe major performance problem with OCC methodsis the late transaction restart. Thus, one importantway to improve the performance of OCC methods isto reduce the number of transaction restarts. OneE-ISSN: 2224-2872RS (Tv ) WS (T j ) (Read-Write conflict):serialization order between Tv and T j asTv T j such that write of Tv cannotoverwrite T j ’s write.421Issue 12, Volume 11, December 2012

WSEAS TRANSACTIONS on COMPUTERSWalid Moudani, Nicolas Khoury, Mohamad Husseinthe time interval of the active transaction isadjusted. Non-serializable execution is detectedwhen the timestamp interval of an active transactionshuts out and transaction is restarted.To support dynamic adjustment of serializationorder, a dynamic timestamp assignment method isused. For each transaction, Ti there is a timestampcalled the latest commit timestamp LCT (i) toindicate its serialization order relative to othertransactions. Initially, the value of LCT (i) is set tobe . If Ti has been backward adjusted, LCT (i) isalso used to detect whether Ti has accessed anyinvalid data at its validation test. Upon successfullypassing its validation test, the validating transactionTi is assigned a final serialization timestamp.The OCC-DATI is enhanced by using the theimportance of transactions found from transactionobject attributes [7]. A real-time transaction objectincludes the attributes priority, deadline, andimportance. The conflict resolution section usesdynamic adjustment of serialization order similarlyto OCC-DATI but with the following conditions:- Transactions of high importance should not berestarted because of data conflict withtransactions of low importance when forwardadjustment is applied.- Transactions of high importance should not bebackward adjusted, but conflicting lowerimportance should be restarted when backwardadjustment is applied.2.3 OCC methodsThe different OCC methods proposed in theliterature differ in the way of conflict resolutionduring the validation phase. Below, we describeshortly the most important optimistic methods inliterature. Table 1 shows the different terms andparameters applied in OCC methods.Using importance or criticalness of the transactionin place of the priority in the conflict resolution ofOCC method avoids the dilemma of priority basedconflict resolution, because transactions with veryshort deadline (i.e. very high priority) are notnecessarily more critical than transactions with highimportance.A method which is similar to OCC-DATI isproposed in [16]. The conflict resolution in thismethod uses real-time serializability and theimportance of transaction attribute. A transaction ofhigher importance should precede a transaction oflower importance in real-time history. Therefore, thetransaction of higher importance should not beforward adjusted after a transaction of lowerimportance. Thus, if this is the case a transaction oflower importance is restarted. As well, in backwardadjustment, we must ensure real-time serializableexecution. Therefore, transactions of highimportance should not be backward adjusted;instead, conflicting transactions having lowerimportance should be restarted.2.3.1 OCC method using Dynamic adjustment ofserialization order using timestamp interval(OCC-DATI)In [4], a method called OCC-DATI is presentedallowing to minimize the number of transactionrestarts by adjusting the serialization orderdynamically between conflicting and validatingtransaction. In OCC-DATI all the checking isperformed at the validation phase of eachtransaction, where it will be either forward orbackward adjusted based on the conflict type. Aserious conflict occurs when a conflicting activetransaction has to be both backward and forwardadjusted. The validating transaction is allowed tocommit if the validity of all its accessed data are stillsound and there is no serious conflict.At the beginning of the validation, the finaltimestamp of the validating transaction TS (Tv ) isdetermined from the timestamp interval allocated tothe transaction Tv . The timestamp intervals of allother concurrently running and conflictingtransactions must be adjusted to reflect theserialization order. We set TS (Tv ) to the validationtime if it belongs to the time interval of Tv or tomaximum value from the time interval otherwise.The adjustment of timestamp intervals of activetransactions iterates through the ReadSet (RS) andWriteSet (WS) of validating transaction. Whenaccess has been made to the same objects both invalidating transaction and in the active transaction,E-ISSN: 2224-28722.3.2 Real-time OCC Method with DynamicAdjustment of Serialization Order (OCC-DASO)A method called OCC-DASO was proposed in [13]using the Thomas' write rule for updating thedatabase with the writes of the validatingtransactions during the write phase. In this method,the number of transaction restarts is reduced byusing dynamic adjustment of serialization order,422Issue 12, Volume 11, December 2012

WSEAS TRANSACTIONS on COMPUTERSWalid Moudani, Nicolas Khoury, Mohamad HusseinTable 1. List of parameters used in OCCneeds forward adjustment with respect to thevalidating transaction Tv . In the final step of thevalidation test, If Tv has not been selected for restart;we have to assign the final values to the conflictingand the validating transactions’ tables, and updatethe read and write timestamps of data. By applyingThomas' write rule in its write phase, Tv will onlyupdate the database with its writes on theappropriate data item (with the valid timestamp).which is supported with the use of a dynamictimestamp assignment scheme, and the Thomas'write rule.The validation phase of OCC-DASO is divided intofour steps: The first step of the validation phase is totest whether Tv has accessed any invalidated data.Second step detects the read-write conflicts betweenthe set of the active transactions, T j and thevalidating transaction Tv . The third step is to detectwhether a backward-adjusted transaction T j , alsoE-ISSN: 2224-2872423Issue 12, Volume 11, December 2012

WSEAS TRANSACTIONS on COMPUTERSWalid Moudani, Nicolas Khoury, Mohamad Husseintransaction or aborting the conflicting ongoingtransactions. Three schemes are presented in [6]such as: OCC-forward validation with virtual runpolicy: In this scheme (OCC-FV) the transactionthat reaches its validation phase is allowed tocommit if it is not a virtual first run transactionand all the active conflicting transactions whichare in their read phases are immediately abortedand restarted if they are rerun transactions. Incase some of the conflicting read phasetransactions are in their first run, instead ofaborting them they enter their virtual run andcontinue their read phase so as to bring dataobjects required to buffer, assuming the systembuffer has a high retention effect, then atransaction in its second run and onward does notneed to access the disk since the data objects arealready in memory. When the virtual runtransaction completes its read phase, it is abortedand resubmitted to the system to start its realsecond run. It is clear that there is no point toallow restarted rerun transaction to complete itsread phase in virtual mode since all its data itemsare already in memory. This scheme does nottake the transactions timing constraints intoaccount and favors the validating one to save theamount of progress done by the validatingtransaction since it is near completion and willdefinitely complete if it is not restarted. OCC-sacrifice with virtual run policy: In thisscheme (OCC-OS) when a transaction reaches itsvalidation phase, it is aborted if one or moreconflicting transactions have higher priority thanthe validating one; otherwise it commits and allthe conflicting read phase transactions arerestarted immediately. This method usestransaction priority (timing constraints) in such away that the validating transaction sacrificesitself for the sake of conflicting ones with higherpriority. OCC-abort 50 with virtual run policy: In thisscheme (OCC-A50) when a transaction reachesits validation phase, its priority is checkedagainst those conflicting transactions in the readphase. If more than 50% of the transactions intheir read phase have higher priority than thetransaction in its validation phase, the validatingtransaction is aborted and all other transactionsare allowed to continue. If the number oftransactions in the read phase having higherpriority than validating transaction is less than orequal to 50%, the validating transaction isallowed to commit and all the other transactionsare restarted.The OCC-DASO is enhanced in [11] by using aparameter called transaction finish degree (TFD)which can avoid the near-to-complete transactionsrestarts. TFD values are calculated for the set oftransactions that have conflict with the validatingtransaction Tv , and whose deadlines are smaller thanTv ’s deadline. TFD can depict if an adjustment ofserialization order is necessary or can be avoidedand both the conflicting transactions can meet theirdeadlines. The validation phase is divided intopreparation phase and adjustment phase. Inpreparation phase, TFD values are computed andserious conflict is checked. The reordering oftransaction commitment is performed in adjustmentphase. According to the TFDV values, thecommitment order is decided; either forwardordering Tv T j or backward ordering T j Tv , incondition that a serious conflict does not exist. If aserious conflict occurs between Tv and T j then thevariable versions read by the transactions aremodified.2.3.3 OCC method for accessing temporal databased on Validation factor and transactiondeferrable time (OCC-VFTDT)In [10], the proposed method is designed in which achecking algorithm is carried out to guarantee theuse of validate data that fit with the transactionscheduling process. The checking process ensuresthat all temporal data in the read set of a transactionremain valid during all its execution time which willguarantee the temporal consistency of thistransaction.Afterward, the key factor concurrency controlalgorithm is adjusting validation rules duringvalidation phase, which schedules the prioritytransactions that are near to complete by assertingvalidation factor. The validation algorithmcalculates the validation factor of the validatingtransaction, which is a variable calculated from thecurrent time, the start time and the deadline time ofthe transaction, and calculates the temporaldeferrable time of the transaction tsd t (T ) .2.3.4 OCC with virtual run policyTo support real-time transaction processing, amethod is proposed by integrating the new criteriaand issues of CPU and I/O scheduling, and the timecognizant conflict resolution scheme into the OCCmethod [6]. This method considers the timingcharacteristics of transaction and proper decisioncan be taken in aborting, delaying the committingE-ISSN: 2224-2872424Issue 12, Volume 11, December 2012

WSEAS TRANSACTIONS on COMPUTERSWalid Moudani, Nicolas Khoury, Mohamad HusseinThis method respects the temporal consistency ofdata items as well as real time transactions.Furthermore, we introduce the concept of similarityand data criticalness factor to obtain a better realtime performance while guaranteeing temporal andlogical consistency. Moreover OCC-SIDASO takesinto consideration the importance of transactionduring conflict resolution and applies a dynamicadjustment of serialization order only if thetemporal consistency of data and transactions arenot being violated. In addition, we relaxserializability criterion by introducing datasimilarity and operation similarity, by allowing twoconflicting operation to commit if they meetoperation similarity which means when they areslightly different we consider them as acceptable.The OCC-SIDASO method resolves conflicts usingtime intervals of the transactions. Every transactionmust be executed within a specific time slot.When an access conflict occurs, it is resolved usingthe read and write sets of the conflicting transactionstogether with the allocated time slot. Time slots areadjusted when a transaction commits. In thisprotocol, every transaction in the read phase isassigned a timestamp interval. This interval is usedto record a temporary serialization order inducedduring the execution of the transaction. At the startof the execution, the timestamp interval of atransaction T is initialized as S (T ), d (T ) .Whenever the serialization order of the transactionis induced by its data operation or the validation ofother transactions, its timestamp interval is adjustedto represent the dependencies.2.4 Comparison of OCC and PCC methodsIn this section we compare the described methodsaccording to different parameters shown in Table 2.In OCC methods, either the validating transaction orthe conflicting ongoing transaction can be aborted toresolve conflict. Moreover, dynamic adjustment ofserialization order is used to reduce the number oftransaction restarts caused by conventional OCCand to take the proper decision in aborting ordelaying the committing transaction or aborting theconflicting ongoing transaction. Most of theliterature methods based on OCC-DATI don’tsupport temporal consistency of data andtransactions except for one (OCC-VFTDT), andmany of them favor transactions with higherimportance. Our proposed algorithm using theOCC-DATItechnique,supportstemporalconsistency of data and transactions, and takes inconsideration the importance of transactions and thecriticalness factor of data. The algorithm alsoattempts to outperform the previous methods byreducing the number of transaction restarts andincreasing the concurrency level while maintainingthe data valid as much as possible.3 OCC method using Similarity andImportance of transaction andDynamic Adjustment of SerializationIn this section, we describe an OptimisticConcurrency Control using Similarity andImportance of transaction and Dynamic Adjustmentof Serialization Order called OCC-SIDASO. Favors transactions with highimportance or priority Uses dynamic adjustment Causes system memoryoverheadCPU and I/O schedulingUses optimistic concurrencycontrolUses locking techniques(pessimistic method)- risk ofDeadlocks Support transactions temporalconsistencyE-ISSN: 2224-2872 Supports data temporalconsistencyOCC-DASOTHCP-2PL (PCC)STHCP-2PL (PCC)OCC-VFTDTOCC-DATIOCC-PDATIMVOCC-TFDOCC-FV with virtual run policyOCC-sacrifice with virtual run policyOCC-abort50 with virtual run policySupports real-timetransactionsCriteria/methods Table 2. Parameters used to compareOCC and PCC methods425Issue 12, Volume 11, December 2012

WSEAS TRANSACTIONS on COMPUTERSWalid Moudani, Nicolas Khoury, Mohamad HusseinOCC-SIDASO– VALIDATE ( ) {( ( ))( ) Else( ) max ( ) ;( ( ) ;( )){((( ))( ) ( )) ( ) ( ) []) ( ( ) [(( ), [;( ), [;) [( ), [ [( );( )) {(((( ) ( ) )( , , ); ()() )( , , ); ()() )( , , ); ( ) [])( ); } ( )( ) max( )( ) max( ),( ),( ) ;( ) ;}Commit}( ) to database;Fig 1. Validation algorithm of OCC-SIDASO( ,){,( ) ( )){( ( ) {CommitReturn;}Else IF ( ( ) ( ( ) ((()( ) ( (,) (,) ) )( ) to database;, ) () )( ) [,) AND( ) ) OR( ) 1 , [;Else( );}Else( );}Fig 2. Forward Adjustment of OCC-SIDASOE-ISSN: 2224-2872426Issue 12, Volume 11, December 2012

WSEAS TRANSACTIONS on COMPUTERSWalid Moudani, Nicolas Khoury, Mohamad HusseinIn the remain of this section we present the : (i)validation phase algorithm of OCC-SIDASO, (ii)Operation similarity and data criticalness and (iii)temporal consistency checking algorithm.not critical. Otherwise, a forward adjustment ofserialization order is applied to the active conflictingtransaction Ta by adjusting the timestamp intervalof Ta . This adjustment of timestamp interval of theactive transaction iterates through the readset (RS)and writeset (WS) of validating transaction Tv . Notethat, forward adjustment will only be allowed if theforwarding of the conflicting transaction Ta does notviolate the temporal consistency of data andtransactions. This temporal consistency check isdone by the CHECK POTENTIAL TC( Ta )procedure which will be explained later in thissection.3.1 Validation phase algorithm of OCCSIDASOThis section presents the algorithm of validationphase OCC-SIDASO shown in figure 1. At thebeginning of the validation, the final timestamp ofthe validating transaction TS (Tv ) is determinedfrom the timestamp interval allocated to thetransaction Tv . The timestamp intervals of all otherconcurrently running and conflicting transactionsmust be adjusted to reflect the serialization order.We set TS (Tv ) to the validation time if it belongs tothe time interval of Tv or to maximum value fromthe time interval otherwise.The adjustment of timestamp intervals of an activetransaction iterates through the readset (RS) andwriteset (WS) of validating transaction. Whenaccess has been made to the same objects both invalidating transaction and in the active transactionand at least one of the operations is a writeoperation, then we have a conflict and the followingprocedures should be called accord

devoted to designing concurrency control methods for RTDBS and to evaluating their performance. Most of these algorithms use serializability as correctness criteria and are based on one of the two basic concurrency control mechanisms: Pessimistic Concurrency Control [3, 12] or Optimistic Concurrency Control [2, 4, 5, 6, 11]. However, 2PL