UNIT-IV TRANSACTION MANAGEMENT

Transaction, Transaction States, ACID Properties, Schedule, Serializability and Types,

Concurrent Control, Concurrency Control Protocols, Crash Recovery: Introduction To ARIES,
The Log, Write-Ahead Log Protocol, Recovering From A System Crash.

------------------------------------------------------------------------------------------------------------------------------------------

What is a Transaction?

A transaction is logical unit of work with database access operations ( read and write ).

Collections of operations that form a single logical unit of work are called transactions. or A
transaction is an atomic unit of work that should either be completed in its entirety or not done at
all. A transaction is a unit of program execution that accesses and possibly updates various data
items. The transaction consists of all operations executed between the begin transaction and end
transaction after a transaction is committed, database researches to a new consistent state. It may
be rolled back or undone.different operations of a Transaction or the recovery manager of the
DBMS needs to keep track of the following operations:
 BEGIN_TRANSACTION. This marks the beginning of transaction execution.
 READ or WRITE. These specify read or write operations on the database items that are
executed as part of a transaction.
 END_TRANSACTION. This specifies that READ and WRITE transaction operations
have ended and marks the end of transaction execution. at this point it may be necessary to
check whether the changes introduced by the transaction can be permanently applied to the
database (committed) or whether the transaction has to be aborted because it violates
serializability or for some other reason.
 COMMIT_TRANSACTION. This signals a successful end of the transaction so that any
changes (updates) executed by the transaction can be safely committed to the database and
will not be undone.
 ROLLBACK (or ABORT). This signals that the transaction has ended unsuccessfully, so
that any changes or effects that the transaction may have applied to the database must be
undone.
Example: Transfer of 50₹ from Account A to Account B. Initially A= 500₹, B= 800₹. This data is
brought to RAM from Hard Disk.
BEGIN_TRANSACTION
R(A) -- 500 // Accessed from RAM.
A = A-50 // Deducting 50₹ from A.
W(A)--450 // Updated in RAM.
R(B) -- 800 // Accessed from RAM.
B=B+50 // 50₹ is added to B's Account.
W(B) --850 // Updated in RAM.
commit // The data in RAM is taken back to Hard Disk.
 UNIT-IV TRANSACTION MANAGEMENT

END_TRANSACTION
Uses of Transaction Management:
The DBMS is used to schedule the access of data concurrently. It means that the user can access
multiple data from the database without being interfered with each other. Transactions are used to
manage concurrency. It is also used to satisfy ACID properties. It is used to solve Read/Write
Conflict.It is used to implement Recoverability, Serializability, and Cascading. Transaction
Management is also used for Concurrency Control Protocols and Locking of data.
Problems in database Transactions:
1. Inconsistency of results
2. Interference from other transactions.
3. Ambiguity in deciding when to make changes permanent.
To avoid these Problems transaction has properties called ACID properties
ACID properties or Desirable properties of Transaction:
Transactions should possess several properties, often called the ACID properties; they should be
enforced by the concurrency control and recovery methods of the DBMS.The transaction has the
four properties. These are used to maintain consistency in a database, before and after the
transaction.
 Atomicity
 Consistency
 Isolation
 Durability
1. Atomicity: Either all operations of the transaction are properly reflected in the database or none
are. Or A transaction is an atomic unit of processing; it should either be performed in its entirety
or not performed at all. it states that all operations of the transaction take place at once if not, the
transaction is aborted. There is no midway, i.e., the transaction cannot occur partially. Each
transaction is treated as one unit and either run to completion or is not executed at all. Atomicity
involves the following two operations: Abort: If a transaction aborts then all the changes made are
not visible. Commit: If a transaction commits then all the changes made are visible.
Example: Consider a transaction to transfer $50 from account A to account B: A=1000 B=2000
1.read(A)
2.A := A – 50
3.write(A)
4.read(B)
5.B := B + 50
6.write(B)
After completion of the transaction, A consists of Rs 950 and B consists of Rs 2000.If the
transaction T fails after the completion of transaction 3 but before completion of transaction 6,
 UNIT-IV TRANSACTION MANAGEMENT

then the amount will be deducted from A but not added to B. This shows the inconsistent database
state. In order to ensure correctness of database state, the transaction must be executed in entirety.
Atomicity requirement
If the transaction fails after step 3 and before step 6, money will be “lost” leading to an
inconsistent database state Failure could be due to software or hardware The system should ensure
that updates of a partially executed transaction are not reflected in the database
2. Consistency: Once the transaction is executed, it should move from one consistent state to
another.A transaction should be consistency preserving, meaning that if it is completely executed
from beginning to end without interference from other transactions, it should take the database
from one consistent state to another. The integrity constraints are maintained so that the database
is consistent before and after the transaction. The execution of a transaction will leave a database
in either its prior stable state or a new stable state. The transaction is used to transform the
database from one consistent state to another consistent state.
For example: The total amount must be maintained before or after the transaction.
Total before T occurs = 1000+300=1300
Total after T occurs= 2000+400=2400
Therefore, the database is consistent. In the case when T1 is completed but T2 fails, then
inconsistency will occur.
1.read(A)
2.A := A – 50
3.write(A)
4.read(B)
5.B := B + 50
6.write(B)
Consistency requirement in above example: The sum of A and B is unchanged by the execution of
the transaction In general, consistency requirements include Explicitly specified integrity
constraints such as primary keys and foreign keys Implicit integrity constraints
e.g., sum of balances of all accounts, minus sum of loan amounts must equal value of cash-in-
hand A transaction, when starting to execute, must see a consistent database. During transaction
execution the database may be temporarily inconsistent. When the transaction completes
successfully the database must be consistent. Erroneous transaction logic can lead to
inconsistency.
3.Isolation: Although multiple transactions may execute concurrently, each transaction must be
unaware of other concurrently executing transactions. Intermediate transaction results must be
hidden from other concurrently executed transactions. That is, for every pair of transactions Ti
and Tj, it appears to Ti that either Tj, finished execution before Ti started, or Tj started execution
after Ti finished.
 UNIT-IV TRANSACTION MANAGEMENT

Example:
Isolation requirement if between steps 3 and 6 (of the fund transfer transaction) , another
transaction T2 is allowed to access the partially updated database, it will see an inconsistent
database(the sum A+B will be less than it should be).

T1 T2
1. read(A)
2. A := A – 50
3. write(A)
read(A), read(B), print(A+B)
4. read(B)
5. B := B + 50
6. write(B
Isolation can be ensured trivially by running transactions serially That is, one after the other.
However, executing multiple transactions concurrently has significant benefits.
4. Durability: The changes applied to the database by a committed transaction must persist in the
database. These changes must not be lost because of any failure. The durability property is used to
indicate the performance of the database's consistent state. It states that the transaction made the
permanent changes. They cannot be lost by the erroneous operation of a faulty transaction
Transaction States : State transition diagram illustrating the states for transaction execution.

1. Active.
2. Partially committed.
3. Committed.
4. Failed state.
5. Terminated State/Aborted

State transition diagram illustrating the states for transaction execution.

1. Active state: The active state is the first state of every transaction. In this state, the transaction is
being executed. the transaction stays in this state while it is executing. A transaction enters into an
active state when the execution process begins. During this state read or write operations can be
 UNIT-IV TRANSACTION MANAGEMENT

performed. For example: Insertion or deletion or updating a record is done here. But all the
records are still not saved to the database.
2. Partially committed: A transaction goes into the partially committed state after the end of a
transaction. or after the final statement has been executed. In the partially committed state, a
transaction executes its final operation, but the data is still not saved to the database.
3. Committed: When the transaction is committed to state, it has already completed its execution
successfully. Moreover, all of its changes are recorded to the database permanently. A transaction
is said to be in a committed state if it executes all its operations successfully. In this state, all the
effects are now permanently saved on the database system.
4. Failed state: A transaction considers failed when any one of the checks fails or if the transaction
is aborted while it is in the active state. or after the discovery that normal execution can no longer
proceed. If any of the checks made by the database recovery system fails, then the transaction is
said to be in the failed state. In the example of total mark calculation, if the database is not able to
fire a query to fetch the marks, then the transaction will fail to execute.
5. Terminated State/ Aborted: State of transaction reaches terminated state when certain
transactions which are leaving the system can’t be restarted. If any of the checks fail and the
transaction has reached a failed state then the database recovery system will make sure that the
database is in its previous consistent state. If not then it will abort or roll back the transaction to
bring the database into a consistent state.After aborting the transaction, the database recovery
module will select one of the two operations: Re-start the transaction, Kill the transaction.
Implementation of Atomicity and Durability:
The recovery-management component of a database system implements the support for atomicity
and durability.
The shadow-database scheme: assume that only one transaction is active at a time. a pointer called
db_pointer always points to the current consistent copy of the database. all updates are made on a
shadow copy of the database, and db_pointer is made to point to the updated shadow copy only
after the transaction reaches partial commit and all updated pages have been flushed to disk.in
case transaction fails, old consistent copy pointed to by db_pointer can be used, and the shadow
copy can be deleted.The shadow-database scheme:

Assumes disks to not fail Useful for text editors, but extremely inefficient for large databases:
executing a single transaction requires copying the entire database
 UNIT-IV TRANSACTION MANAGEMENT

Concurrent Executions: Multiple transactions are allowed to run concurrently in the system.
Advantages are: The advantages of concurrency control are as follows −
1. Waiting time will be decreased.
2. Response time will decrease.
3. Resource utilization will increase.
4. System performance & Efficiency is increased.
Increased processor and disk utilization, leading to better transaction throughput CPU activity and
I/O activity. The cpu and the disk in computer system can operate in parallel.
E.g. one transaction can be using the CPU while another is reading from or writing to the disk
Reduced average response time for transactions: short transactions need not wait behind long
ones. Mix of transactions running on a system ,some short and long.If transaction run serially
Short transaction may have to wait for a preceding long transaction to complete which lead
Unpredictable delay in running a transactions.
Concurrency control schemes – mechanisms to achieve isolation That is, to control the interaction
among the concurrent transactions in order to prevent them from destroying the consistency of the
database .
Concurrency control techniques
The concurrency control techniques are as follows −
 Locking
 Types of Locks
 Shared Lock [Transaction can read only the data item values]
 Exclusive Lock [Used for both read and write data item values]
 Time Stamping
 Optimistic
Schedule:A series of operation from one transaction to another transaction is known as schedule.
It is used to preserve the order of the operation in each of the individual transaction.
Different Types of Schedules:
1. Serial Schedule
2. Non-serial Schedule
i.Serializable schedule
 Conflict Serializability
 View Serializability
ii.Non-Serializable Schedules
 Recoverable Schedules
 Cascading Schedule
 Cascadeless Schedule
 Strict Schedule
 UNIT-IV TRANSACTION MANAGEMENT

 Non-Recoverable Schedules or Irrecoverable Schedules

1. Serial Schedule: The serial schedule is a type of schedule where one transaction is executed
completely before starting another transaction. All the transactions execute serially one after the
other. When one transaction executes, no other transaction is allowed to execute.
For example: Suppose there are two transactions T1 and T2 which have some operations. If it has
no interleaving of operations, then there are the following two possible outcomes:Execute all the
operations of T1 which was followed by all the operations of T2.Execute all the operations of T2
which was followed by all the operations of T1.
Example-01:
T1 T2
------------------------------------------------------
read(A);
A:=A-50;
write(A);
read(B);
B:=B+50;
write(B).
read(A);
temp=A*0.1;
A:=A-temp;
write(A);
read(B);
B:=B+temp;
write(B).
 UNIT-IV TRANSACTION MANAGEMENT

In this schedule, There are two transactions T1 and T2 executing serially one after the other.
Transaction T1 executes first. After T1 completes its execution, transaction T2 executes. So, this
schedule is an example of a Serial Schedule.
Example-02: schedule2:
T1 T2
--------------------------------------------------------
read(A);
temp=A*0.1;
A:=A-temp;
write(A);
read(B);
B:=B+temp;
write(B).
read(A);
A:=A-50;
write(A);
read(B);
B:=B+50;
write(B).
In this schedule, There are two transactions T1 and T2 executing serially one after the other.
Transaction T2 executes first. After T2 completes its execution, transaction T1 executes. So, this
schedule is an example of a Serial Schedule.
2. Non-serial Schedule
This is a type of Scheduling where the operations of multiple transactions are interleaved. If
interleaving of operations is allowed, then there will be non-serial schedule. It contains many
possible orders in which the system can execute the individual operations of the transactions. This
might lead to a rise in the concurrency problem. The transactions are executed in a non-serial
manner, keeping the end result correct and same as the serial schedule.In non-serial schedules,
Multiple transactions execute concurrently.Operations of all the transactions are interleaved or
mixed with each other.
Characteristics: Non-serial schedules are NOT always,Consistent,Recoverable,Cascadeless,Strict
Example 3:schedule3:current schedule equivalent to schedule1
T1 T2
------------------------------------------------------
read(A)
A:=A-50
write(A)
 UNIT-IV TRANSACTION MANAGEMENT

read(A)
temp=A*0.1
A:=A-temp
write(A)
read(B);
B:=B+50;
write(B).

read(B);
B:=B+temp;
write(B).
In this schedule,There are two transactions T1 and T2 executing concurrently.The operations of
T1 and T2 are interleaved.So, this schedule is an example of a Non-Serial Schedule.
Example 4:schedule4:current schedule
T1 T2
---------------------------------------------------
read(A)
A:=A-50
read(A)
temp=A*0.1
A:=A-temp
write(A)
read(B)

write(A)
read(B)
B:=B+50
write(B)
B:=B+temp
write(B)
In this schedule,There are two transactions T1 and T2 executing concurrently. The operations of
T1 and T2 are interleaved. So, this schedule is an example of a Non-Serial Schedule.
Serializable: If a given non-serial schedule of ‘n’ transactions is equivalent to some serial
schedule of ‘n’ transactions, then it is called as a serializable schedule.It is mainly used in the
Non-Serial scheduling to verify whether the scheduling will lead to any inconsistency or not.A
nonserial schedule will be serializable if its result is equal to the result of its transactions executed
serially.A serializable schedule helps in improving both resource utilization and CPU throughput.
 UNIT-IV TRANSACTION MANAGEMENT

Serial Schedules Vs Serializable Schedules

Serial Schedules Serializable Schedules
No concurrency is allowed. Thus, all the Concurrency is allowed. Thus, multiple
transactions necessarily execute serially one transactions can execute concurrently.
after the other.
Serial schedules lead to less Serializable schedules improve both resource
Resource utilization and CPU throughput. utilization and CPU throughput.
Serial Schedules are less efficient as compared Serializable Schedules are always
to serializable schedules.(due to above reason) better than serial schedules. (due to above
reason)
Types of Serializability: Serializability is mainly of two types
1.Conflict Serializability
2.View Serializability
Conflict Serializability: If a given non-serial schedule can be converted into a serial schedule by
swapping its non-conflicting operations, then it is called as a conflict serializable schedule.
Conflicting Operations: Two operations are called as conflicting operations if all the following
conditions hold true for them
 Both the operations belong to different transactions,
 Both the operations are on the same data item
 At least one of the two operations is a write operation
Example: Consider the following schedule-
T1 T2
----------------------------
R1(A)
W1(A)
R2(A)
R1(B)
In this schedule,W1 (A) and R2 (A) are called as conflicting operations.This is because all the
above conditions hold true for them.
Checking Whether a Schedule is Conflict Serializable Or Not:
Follow the following steps to check whether a given non-serial schedule is conflict serializable or
not
Step-01:Find and list all the conflicting operations.
Step-02:Start creating a precedence graph by drawing one node for each transaction.
Step-03:Draw an edge for each conflict pair such that if Xi (V) and Yj (V) forms a conflict pair
then draw an edge from Ti to Tj.This ensures that Ti gets executed before Tj.
 UNIT-IV TRANSACTION MANAGEMENT

Step-04:Check if there is any cycle formed in the graph.If there is no cycle found, then the
schedule is conflict serializable otherwise not.
View Serializability:
View Equivalent Schedules: Consider two schedules S1 and S2 each consisting of two
transactions T1 and T2.Schedules S1 and S2 are called view equivalent if the following three
conditions hold true for them.
Condition-01: For each data item X, if transaction Ti reads X from the database initially in
schedule S1, then in schedule S2 also, Ti must perform the initial read of X from the database.
Thumb Rule :”Initial readers must be same for all the data items”.
Condition-02:If transaction Ti reads a data item that has been updated by the transaction Tj in
schedule S1, then in schedule S2 also, transaction Ti must read the same data item that has been
updated by the transaction Tj.
Thumb Rule :“Write-read sequence must be same.”.
Condition-03:For each data item X, if X has been updated at last by transaction Ti in schedule S1,
then in schedule S2 also, X must be updated at last by transaction Ti.
Thumb Rule :“Final writers must be same for all the data items”.
Non-Serializable Schedules: A non-serializable schedule is not guaranteed to produce the same
effect as produced by some serial schedule on any consistent database.
The non-serializable schedule is divided into two types,
1.Recoverable and
2.Non-recoverable Schedule OR Irrecoverable Schedules
Recoverable Schedules: A transaction performs a dirty read operation from an uncommitted
transaction And its commit operation is delayed till the uncommitted transaction either commits or
roll backs then such a schedule is called as a Recoverable Schedule.
Types of Recoverable Schedules,A recoverable schedule may be any one of these kinds
1.Cascading Schedule
2.Cascadeless Schedule
3.Strict Schedule
Cascading Schedule: If in a schedule, failure of one transaction causes several other dependent
transactions to rollback or abort, then such a schedule is called as a Cascading Schedule or
Cascading Rollback or Cascading Abort. It simply leads to the wastage of CPU time.
Cascade less Schedule: If in a schedule, a transaction is not allowed to read a data item until the
last transaction that has written it is committed or aborted such a schedule is called as a Cascade
less Schedule.
Strict Schedule:If in a schedule, a transaction is neither allowed to read nor write a data item until
the last transaction that has written it is committed or aborted, then such a schedule is called as a
Strict Schedule.
 UNIT-IV TRANSACTION MANAGEMENT

2.Irrecoverable Schedules: If in a schedule,A transaction performs a dirty read operation from an

uncommitted transaction And commits before the transaction from which it has read the value
then such a schedule is known as an Irrecoverable Schedule.
Some Anomalies Associated with Interleaved Execution:
Different types of problems encounter when two simple transactions if they run concurrently.
 Dirty Read Problem
 Unrepeatable Reads (RW Conflicts) or Unrepeatable Read Problem
 The Lost Update Problem(WW Conflicts)
 Phantom Read Problem
1. Dirty Read Problem: Reading the data written by an uncommitted transaction is called as dirty
read. Reading Uncommitted Data (WR Conflicts) or The Temporary Update (or Dirty Read)
Problem. The first source of anomalies is that a transaction T2 could read a database object A that
has been modified by another transaction T1, which has not yet committed. Such a read is called a
dirty read. This read is called as dirty read because: There is always a chance that the
uncommitted transaction might roll back later. Thus, uncommitted transaction might make other
transactions read a value that does not even exist. This leads to inconsistency of the database.
Example
T1 T2
-----------------------------
R(A)
W(A)
. R(A) // Dirty Read
. W(A)
. commit;
failure
Here,
T1 reads the value of A.T1 updates the value of A in the buffer.T2 reads the value of A from the
buffer.T2 writes the updated the value of A.T2 commits.T1 fails in later stages and rolls back.
In this example,T2 reads the dirty value of A written by the uncommitted transaction T1.
T1 fails in later stages and roll backs.Thus, the value that T2 read now stands to be incorrect.
Therefore, database becomes inconsistent.
NOTE:Dirty read does not lead to inconsistency always.It becomes problematic only when the
uncommitted transaction fails and roll backs later due to some reason.
2. Unrepeatable Reads (RW Conflicts) or Unrepeatable Read Problem
The unrepeatable problem occurs when two or more read operations of the same transaction read
different values of the same variable. This problem occurs when a transaction gets to read
 UNIT-IV TRANSACTION MANAGEMENT

unrepeated i.e. different values of the same variable in its different read operations even when it
has not updated its value.
T1 T2
-----------------------------
R(X)
R(X)
W(X)
R(X);//unrepeated
Here,T1 reads the value of X (= 100 say).T2 reads the value of X (= 100).T1 updates the value of
X (from 100 to 150 say) in the buffer.T2 again reads the value of X (but = 150).In this
example,T2 gets to read a different value of X in its second reading.T2 wonders how the value of
X got changed because according to it, it is running in isolation.
3. The Lost Update Problem(WW Conflicts) ( blind write) OR Overwriting Uncommitted Data
(WW Conflicts):
In the lost update problem, an update done to a data item by a transaction is lost as it is
overwritten by the update done by another transaction.This problem occurs when multiple
transactions execute concurrently and updates from one or more transactions get lost.
Example
T1 T2
-----------------------------
R(A)
W(A)
. W(A)
. commit
commit
Here,T1 reads the value of A (= 10 say).T2 updates the value to A (= 15 say) in the buffer.T2 does
blind write A = 25 (write without read) in the buffer.T2 commits.When T1 commits, it writes A =
25 in the database.
In this example,T1 writes the over written value of A in the database.Thus, update from T1 gets
lost.
NOTE
This problem occurs whenever there is a write-write conflict.In write-write conflict, there are two
writes one by each transaction on the same data item without any read in the middle.
4. Phantom Read Problem
This problem occurs when a transaction reads some variable from the buffer and when it reads the
same variable later, it finds that the variable does not exist.
Example:
 UNIT-IV TRANSACTION MANAGEMENT

T1 T2
-----------------------------
R(A)
W(A)
delete(A)
R(A)
Here,T1 reads A.T2 reads A.T1 deletes A.T2 tries reading A but does not find it.In this
example,T2 finds that there does not exist any variable X when it tries reading X again.T2
wonders who deleted the variable X because according to it, it is running in isolation.
Dirty Read Problem

7.Concurrency Control Protocols:

The concurrency control protocols ensure the atomicity, consistency, isolation, durability and
serializability of the concurrent execution of the database transactions.Therefore, these protocols
are categorized as:

 Lock Based Concurrency Control Protocol

 Time Stamp Concurrency Control Protocol
 Validation Based Concurrency Control Protocol

Lock Based Concurrency Control Protocol or Lock Based Protocols:

A DBMS must be able to ensure that only serializable, recoverable schedules are allowed, and that
no actions of committed transactions are lost while undoing aborted transactions. A DBMS
typically uses a locking protocol to achieve this. A locking protocol is a set of rules to be followed
by each transaction in order to ensure that even though actions of several transactions might be
interleaved, the net effect is identical to executing all transactions in some serial order.
Two-phase Locking Techniques for concurrency control :

Locks :

A lock is a variable associated with a data item that describes the status of the item with respect to
possible operations that can be applied to it. There is one lock for each data item in the database.
Locks are used as a means of synchronizing the access by concurrent transactions to the database
items. A Lock is a mechanism to control the access on the particular Data Item. There are various
modes in which a data item may be locked several types of locks are used in concurrency control
 Binary Locks
 Shared/Exclusive (or Read/Write) Locks

Binary Locks:

A binary lock can have two states or values.locked and unlocked (or 1 and 0, for simplicity). Two
operations, lock_item and unlock_item, are used with binary locking.A transaction requests access
 UNIT-IV TRANSACTION MANAGEMENT

to an item X by first issuing a lock_item(X) operation. If LOCK(X) = 1, the transaction is forced

to wait. If LOCK(X) = 0, it is set to 1 (the transaction locks the item) and the transaction is
allowed to access item X. When the transaction is through using the item, it issues an
unlock_item(X) operation, which sets LOCK(X) back to 0 (unlocks the item) so that X may be
accessed by other transactions.

If the simple binary locking scheme described here is used, every transaction must obey the
following rules:

1. A transaction T must issue the operation lock_item(X) before any read_item(X) or

write_item(X) operations are performed in T.

2. A transaction T must issue the operation unlock_item(X) after all read_item(X) and
write_item(X) operations are completed in T.

3. A transaction T will not issue a lock_item(X) operation if it already holds the lock on item X.

4. A transaction T will not issue an unlock_item(X) operation unless it already holds the lock on
item X.

Merits of Binary Locks :

They are simple to implement since they are effectively mutually exclusive and establish isolation
perfectly.Binary Locks demand less from the system since the system must only keep a record of
the locked items.

Drawbacks of Binary Locks :Binary locks are highly restrictive.They do not even permit reading
of the contents of item X. As a result, they are not used commercially.

2.Shared/Exclusive (or Read/Write) Locks

Shared: If a transaction Ti has obtained a shared-mode lock (denoted by S) on item Q,

then Ti can read, but cannot write, Q.It is also known as a Read-only lock. In a shared lock, the
data item can only read by the transaction.It can be shared between the transactions because when
the transaction holds a lock, then it can't update the data on the data item.

Exclusive: If a transaction Ti has obtained an exclusive-mode lock (denoted by X) on

item Q, then Ti can both read and write Q.In the exclusive lock, the data item can be both reads as
well as written by the transaction.This lock is exclusive, and in this lock, multiple transactions do
not modify the same data simultaneously.

READ-LOCKED:If a transaction only requires to read the contents of item X and the lock only
permits reading. This is also known as a shared lock. allow several transactions to access the same
item A if they all access A for reading purposes only.This is because read operations on the same
item by different transactions are not conflicting.However, if a transaction is to write an item A, it
must have exclusive access to A.For this purpose, a different type of lock called a multiple-mode
lock is used.
 UNIT-IV TRANSACTION MANAGEMENT

In this scheme—called shared/exclusive or read/write locks—there are three locking operations: A

lock associated with an item A, LOCK(A), now has three possible states:

 read_lock(A),
 write_lock(A), and
 unlock(A).

A read-locked item is also called share-locked because other transactions are allowed to read the
item, whereas a write-locked item is called exclusive-locked because a single transaction
exclusively holds the lock on the item.When we use the shared/exclusive locking scheme, the
system must enforce the following rules:

1. A transaction T must issue the operation read_lock(X) or write_lock(X) before any

read_item(X) operation is performed in T.

2. A transaction T must issue the operation write_lock(X) before any write_item(X) operation is
performed in T

3. A transaction T must issue the operation unlock(X) after all read_item(X) and write_item(X)
operations are completed in T.3

4. A transaction T will not issue a read_lock(X) operation if it already holds a read (shared) lock
or a write (exclusive) lock on item X.

Conversion of Locks:

 Upgrade Lock
 Downgrade Lock

a transaction that already holds a lock on item X is allowed under certain conditions to convert the
lock from one locked state to another it is possible for a transaction T to issue a read_lock(X) and
then later to upgrade the lock by issuing a write_lock(X) operation.If T is the only transaction
holding a read lock on X at the time it issues the write_lock(X) peration, the lock can be
upgraded; otherwise, the transaction must wait. It is also possible for a transaction T to issue a
write_lock(X) and then later to downgrade the lock by issuing a read_lock(X) operation.
Two-Phase Locking: There are a number of variations of two-phase locking
(2PL).Basic,Conservative,Strict, and Rigorous Two-Phase Locking.

The Two-Phase Locking Protocol :

one protocol that ensures conflict-serializability is the two phase locking protocol.in 2PL
protocol requires that each transaction issue lock and unlock requests in two phases.

A transaction is said to follow the Two-Phase Locking protocol if Locking and Unlocking can be
done in two phases. There are two phases of 2PL:

Growing phase: or expanding:In the growing phase A transaction may obtain locks but may not
release any lock.In the growing phase, a new lock on the data item may be acquired by the
 UNIT-IV TRANSACTION MANAGEMENT

transaction, but none can be released.New locks on data items may be acquired but none can be
released.

Shrinking phase:

A transaction may release locks but may not obtain any new locks. In the shrinking phase,
existing lock held by the transaction may be released, but no new locks can be acquired. The two-
phase locking protocol divides the execution phase of the transaction into three parts. In the first
part, when the execution of the transaction starts, it seeks permission for the lock it requires. In the
second part, the transaction acquires all the locks. The third phase is started as soon as the
transaction releases its first lock. In the third phase, the transaction cannot demand any new locks.
It only releases the acquired locks. In the below example, if lock conversion is allowed then the
following phase can happen:
Upgrading of lock (from S(a) to X (a)) is allowed in growing phase.Downgrading of lock (from
X(a) to S(a)) must be done in shrinking phase.
Example: 2PL

The following way shows how unlocking and locking work with 2-PL.

Transaction T1:Growing phase: from step 1-3,Shrinking phase: from step 5-7

Lock point: at 3,

Transaction T2:Growing phase: from step 2-6,Shrinking phase: from step 8-9,Lock point: at 6

Strict Two-phase locking (Strict-2PL):the most popular variation of 2PL is strict 2PL,The most
widely used locking protocol, called Strict Two-Phase Locking. Cascading rollbacks can be
avoided by a modification of two-phase locking called the strict two-phase locking protocol A
transaction T does not release any of its exclusive (write) locks until after it commits or aborts.
Hence, no other transaction can read or write an item that is written by T unless T has committed,
 UNIT-IV TRANSACTION MANAGEMENT

leading to a strict schedule for recoverability. This protocol requires not only that locking be two
phase, but also that all exclusive-mode locks taken by a transaction be held until that transaction
commits. This requirement ensures that any data written by an uncommitted transaction are
locked in exclusive mode until the transaction commits, preventing any other transaction from
reading the data.Strict 2PL is not deadlock-free.
Strict 2PL,has two rules.

(1) If a transaction T wants to read (respectively, modify) an object, it first requests a shared
(respectively, exclusive) lock on the object.

(2) All locks held by a transaction are released when the transaction is completed.

The first phase of Strict-2PL is similar to 2PL. In the first phase, after acquiring all the locks, the
transaction continues to execute normally.The only difference between 2PL and strict 2PL is that
Strict-2PL does not release a lock after using it.Strict-2PL waits until the whole transaction to
commit, and then it releases all the locks at a time.Strict-2PL protocol does not have shrinking
phase of lock release.
T1 T2

---------------------------------

X(A)

R(A)

W(A)

T1would obtain an exclusive lock on A first and then read and write A .Then, T2 would request a
lock on A. However, this request cannot be granted until T1 releases its exclusive lock on A, and
the DBMS therefore suspends T2.T1 now proceeds to obtain an exclusive lock on B, reads and
writes B, then finally commits, at which time its locks are released.T2’s lock request is now
granted, and it proceeds. In this example the locking protocol results in a serial execution of the
two transactions
Schedule Illustrating Strict 2PL

Example

T1 T2

----------------------------------------------

X(A)

R(A)

W(A)

X(B)

R(B)
 UNIT-IV TRANSACTION MANAGEMENT

W(B)

Commit

X(A)

R(A)

W(A)

X(B)

R(B)

W(B)

Commit

Schedule Illustrating Strict 2PL with Serial Execution

Example2:

T1 T2

-------------------------------

S(A)

R(A)

S(A)

R(A)

X(B)

R(B)

W(B)

Commit

X(C)

R(C)

W(C)

Commit

Schedule Following Strict 2PL with Interleaved Actions

Rigorous two-phase locking protocol:

A more restrictive variation of strict 2PL is rigorous 2PL, which also guarantees strict
schedules.In this variation, a transaction T does not release any of its locks (exclusive or shared)
until after it commits or aborts, and so it is easier to implement than strict 2PL.Notice the
difference between conservative and rigorous 2PL: the former must lock all its items before it
 UNIT-IV TRANSACTION MANAGEMENT

starts, so once the transaction starts it is in its shrinking phase; the latter does not unlock any of its
items until after it terminates (by committing or aborting), so the transaction is in its expanding
phase until it ends.
Concurrency Control Based on Timestamp Ordering or Timestamp-Based Protocols :

 Timestamps
 The Timestamp Ordering Algorithm
 Basic Timestamp Ordering (TO).
 Thomas’s Write Rule

Timestamps:

A timestamp is a unique identifier created by the DBMS to identify a transaction. timestamp

values are assigned in the order in which the transactions are submitted to the system, so a
timestamp can be thought of as the transaction start time. We will refer to the timestamp of
transaction T as TS(T).Concurrency control techniques based on timestamp ordering do not use
locks; hence, deadlocks cannot occur.

The Timestamp Ordering Algorithm

the algorithm associates with each database item X two timestamp (TS) values:

1. read_TS(X). The read timestamp of item X is the largest timestamp among all the timestamps
of transactions that have successfully read item X that is, read_TS(X) = TS(T), where T is the
youngest transaction that has read X successfully.

2. write_TS(X). The write timestamp of item X is the largest of all the timestamps of transactions
that have successfully written item X—that is,write_TS(X) = TS(T), where T is the youngest
transaction that has written X successfully.

Basic Timestamp Ordering (TO):

Every transaction is issued a timestamp based on when it enters the system.Suppose, if an old
transaction Ti has timestamp TS(Ti), a new transaction Tj is assigned timestamp TS(Tj) such that
TS(Ti) < TS(Tj). The protocol manages concurrent execution such that the timestamps determine
the serializability order.The timestamp ordering protocol ensures that any conflicting read and
write operations are executed in timestamp order.Whenever some Transaction T tries to issue a
R_item(X) or a W_item(X), the Basic TO algorithm compares the timestamp of T with R_TS(X)
& W_TS(X) to ensure that the Timestamp order is not violated.
This describes the Basic TO protocol in the following two cases.

1. Check the following condition whenever a transaction Ti issues a Read (X) operation:

If W_TS(X) >TS(Ti) then the operation is rejected.If W_TS(X) <= TS(Ti) then the operation is
executed.Timestamps of all the data items are updated.

2. Check the following condition whenever a transaction Ti issues a Write(X) operation:

 UNIT-IV TRANSACTION MANAGEMENT

If TS(Ti) < R_TS(X) then the operation is rejected.If TS(Ti) < W_TS(X) then the operation is
rejected and Ti is rolled back otherwise the operation is executed.Where,TS(TI) denotes the
timestamp of the transaction Ti.

R_TS(X) denotes the Read time-stamp of data-item X.W_TS(X) denotes the Write time-stamp of
data-item X.

Advantages and Disadvantages of TO protocol:

TS protocol ensures freedom from deadlock that means no transaction ever waits.But the schedule
may not be recoverable and may not even be cascade- free.

Thomas’s Write Rule.:

A modification of the basic TO algorithm, known as Thomas’s write rule, does not enforce
conflict serializability, but it rejects fewer write operations by modifying the checks for the
write_item(X) operation as follows:

1.If R_TS(X) > TS(T), then abort and roll back T and reject the operation.

2.If W_TS(X) > TS(T), then don’t execute the Write Operation and continue processing.

This is a case of Outdated or Obsolete Writes.

Remember, outdated writes are ignored in Thomas Write Rule but a Transaction following Basic
TO protocol will abort such a Transaction.

3.If neither the condition in 1 or 2 occurs, then and only then execute the W_item(X) operation of
T and set W_TS(X) to TS(T)

8.Crash Recovery:
Different Types of Failures: Failures are generally classified as transaction, system, and media
failures.There are several possible reasons for a transaction to fail in the middle of execution:
1. A computer failure (system crash):
A hardware, software, or network error occurs in the computer system during transaction
execution. Hardware crashes are usually media failures—for example, main memory failure.
2. A transaction or system error: Some operation in the transaction may cause it to fail, such as
integer overflow or division by zero. Transaction failure may also occur because of erroneous
parameter values or because of a logical programming error. Additionally, the user may interrupt
the transaction during its execution.
3. Local errors or exception conditions detected by the transaction: During transaction execution,
certain conditions may occur that necessitate cancellation of the transaction.
For example, data for the transaction may not be found. An exception condition, such as
insufficient account balance in a banking database, may cause a transaction, such as a fund
withdrawal, to be cancelled. This exception could be programmed in the transaction itself, and in
such a case would not be considered as a transaction failure.
 UNIT-IV TRANSACTION MANAGEMENT

4. Concurrency control enforcement: The concurrency control method may decide to abort a
transaction because it violates serializability or it may abort one or more transactions to resolve a
state of deadlock among several transactions .Transactions aborted because of serializability
violations or deadlocks are typically restarted automatically at a later time.
5. Disk failure: Some disk blocks may lose their data because of a read or write malfunction or
because of a disk read/write head crash. This may happen during a read or a write operation of the
transaction.
6. Physical problems and catastrophes: This refers to an endless list of problems that includes
power or air-conditioning failure, fire, theft, sabotage, overwriting disks or tapes by mistake, and
mounting of a wrong tape by the operator
Failures of types 1, 2, 3, and 4 are more common than those of types 5 or 6.Whenever a failure of
type 1 through 4 occurs, the system must keep sufficient information to quickly recover from the
failure. Disk failure or other catastrophic failures of type 5 or 6 do not happen frequently; if they
do occur, recovery is a major task.
CRASH RECOVERY

The recovery manager of a DBMS is responsible for ensuring two important properties of
transactions: atomicity and durability. It ensures atomicity by undoing the actions of transactions
that do not commit and durability by making sure that all actions of committed transactions
survive system crashes, and media failures (e.g., a disk is corrupted).The recovery manager is one
of the hardest components of a DBMS to design and implement.
steal: if a frame is dirty and chosen for replacement ,the page it contains is written to disk even if
the modifying transaction is still active.

Noforce: pages in the buffer pool that are modified by transaction are not forced to disk when the
transaction commits.

INTRODUCTION TO ARIES

ARIES is a recovery algorithm that is designed to work with a steal, no-force approach. When the
recovery manager is invoked after a crash, restart proceeds in three phases:

1. Analysis: Identifies dirty pages in the buffer pool (i.e., changes that have not been written to
disk) and active transactions at the time of the crash.

2. Redo: Repeats all actions, starting from an appropriate point in the log, and restores the
database state to what it was at the time of the crash.

3. Undo: Undoes the actions of transactions that did not commit, so that the database reflects only
the actions of committed transactions.

Consider the simple execution history illustrated

log sequence number (LSN)

 UNIT-IV TRANSACTION MANAGEMENT

When the system is restarted, the Analysis phase identifies T1 and T3 as transactions that were
active at the time of the crash, and therefore to be undone; T2 as a committed transaction, and all
its actions, therefore, to be written to disk; and P1, P3, and P5 as potentially dirty pages. All the
updates (including those of T1 and T3) are reapplied in the order shown during the Redo phase.
Finally, the actions of T1 and T3 are undone in reverse order during the Undo phase; that is, T3’s
write of P3 is undone, T3’s write of P1 is undone, and then T1’s write of P5 is undone.
There are three main principles behind the ARIES recovery algorithm:

Write-ahead logging: Any change to a database object is first recorded in the log; the record in the
log must be written to stable storage before the change to the database object is written to disk.

Repeating history during Redo: Upon restart following a crash, ARIES retraces all actions of the
DBMS before the crash and brings the system back to the exact state that it was in at the time of
the crash. Then, it undoes the actions of transactions that were still active at the time of the crash
(effectively aborting them)
Logging changes during Undo: Changes made to the database while undoing a transaction are
logged in order to ensure that such an action is not repeated in the event of repeated (failures
causing) restarts.

The Log: The log, sometimes called the trail or journal, is a history of actions executed by the
DBMS. Physically, the log is a file of records stored in stable storage, which is assumed to survive
crashes; the most recent portion of the log, called the log tail, is kept in main memory and is
periodically forced to stable storage. Every log record is given a unique id called the log sequence
number (LSN) any record id, fetch a log record with one disk access given the LSN.LSNs should
be assigned in monotonically increasing order; the LSN can simply be the address of the first byte
of the log record. For recovery purposes, every page in the database contains the LSN of the most
recent log record that describes a change to this page. This LSN is called the pageLSN.
A log record is written for each of the following actions:

 Updating a page
 Commit:
 Abort:
 UNIT-IV TRANSACTION MANAGEMENT

 End:
 Undoing an update:

Updating a page: After modifying the page, an update type record is appended to the log tail. The
pageLSN of the page is then set to the LSN of the update log record.
Commit: When a transaction decides to commit, it force-writes a commit type log record
containing the transaction id the log record is appended to the log, and the log tail is written to
stable storage, up to and including the commit record
The transaction is considered to have committed at the instant that its commit log record is written
to stable storage.
Abort: When a transaction is aborted, an abort type log record containing the transaction id is
appended to the log, and Undo is initiated for this transaction
End: when a transaction is aborted or committed, some additional actions must be taken beyond
writing the abort or commit log record.After all these additional steps are completed, an end type
log record containing the transaction id is appended to the log.
Undoing an update:When a transaction is rolled back (because the transaction is aborted, or during
recovery from a crash), its updates are undone. When the action described by an update log record
is undone, a compensation log record, or CLR, is written.
types of Log Records:

 Update Log Records

 Compensation Log Records

Update Log Records:The fields in an update log record are illustrated Every log record has certain
fields: prevLSN, transID, and type. The set of all log records for a given transaction is maintained
as a linked list .the prevLSN field; list must be updated whenever a log record is added. The
transID field is the id of the transaction generating the log record, and the type field obviously
indicates the type of the log record. Additional fields depend on the type of the log record.

Fig:Contents of an Update Log Record

The pageID field is the page id of the modified page the length in bytes and the offset of the
change are also included. The before-image is the value of the changed bytes before the
change;the after-image is the value after the change.An update log record that contains both
before- and after-images can be used to redo the change and to undo it.A redo-only update log
record will contain just the after-image; similarly an undo-only update record will contain just the
before-image.
 UNIT-IV TRANSACTION MANAGEMENT

Compensation Log Records:A compensation log record (CLR) is written just before the change
recorded in an update log record U is undone.
Other Recovery-Related Data Structures

Transaction table: This table contains one entry for each active transaction. The entry contains
(among other things) the transaction id, the status, and a field called lastLSN, which is the LSN of
the most recent log record for this transaction.The status of a transaction can be that it is in
progress, is committed, or is aborted.

Fig: Instance of Log and Transaction Table

Dirty page table: This table contains one entry for each dirty page in the buffer pool, that is, each
page with changes that are not yet reflected on disk. The entry contains a field recLSN, which is
the LSN of the first log record that caused the page to become dirty. Note that this LSN identifies
the earliest log record that might have to be redone for this page during restart from a crash.
Write-Ahead Logging (WAL) Protocol
Maintain a log file separate from data files that contains the changes that transaction make to
database.
▶ Assume that the log is on stable storage.
▶ Log contains enough information to perform the necessary undo and redo actions to restore the
database.

DBMS must write to disk the log file records that correspond to changes made to a database
object before it can flush that object to disk.
 UNIT-IV TRANSACTION MANAGEMENT

Buffer Pool Policy: STEAL + NO-FORCE

▶ This decouples writing a transaction’s dirty pages to database on disk from committing the
transaction.
▶ We only need to write its corresponding log records.
▶ If a transaction updates a 100 tuples stored in 100 pages, we only need to write 100 log
records (which could be a few pages) instead of 100 dirty pages.
The DBMS stores all a transaction’s log records in volatile storage (usually backed by buffer
pool).All log records pertaining to an updated page are written to non-volatile storage before the
page itself is over-written in non-volatile storage.A transaction is not considered committed until
all its log records have been written to stable storage.
Write a <BEGIN> record to the log for each transaction to mark its starting point.
When a transaction finishes, the DBMS will:
▶ Write a <COMMIT> record on the log
▶ Make sure that all log records are flushed before it returns an acknowledgement to
application.
▶ This allows us to later redo the changes of the committed txns by replaying the log records.
Each log entry contains information about the change to a single object:
▶ Transaction Id
▶ Object Id
▶ Before Value (UNDO)
▶ After Value (REDO)
Buffer Pool Policies :Almost every DBMS uses NO-FORCE + STE

Check pointing

A checkpoint is like a snapshot of the DBMS state, and by taking checkpoints periodically,the
DBMS can reduce the amount of work to be done during restart in the event of a subsequent
crash.

Why do we need Checkpoints?

 UNIT-IV TRANSACTION MANAGEMENT

Whenever transaction logs are created in a real-time environment, it eats up lots of storage space.
Also keeping track of every update and its maintenance may increase the physical space of the
system.

Eventually, the transaction log file may not be handled as the size keeps growing. This can be
addressed with checkpoints. The methodology utilized for removing all previous transaction logs
and storing them in permanent storage is called a Checkpoint.

What is a Checkpoint ?

The checkpoint is used to declare a point before which the DBMS was in the consistent state, and
all transactions were committed. During transaction execution, such checkpoints are traced. After
execution, transaction log files will be created.Upon reaching the savepoint/checkpoint, the log
file is destroyed by saving its update to the database.
Then a new log is created with upcoming execution operations of the transaction and it will be
updated until the next checkpoint and the process continues.Checkpointing in ARIES has three
steps or How to use Checkpoints in database ?

Steps :

Write begin_checkpoint record into log.

Collect checkpoint data in the stable storage.

Write end_checkpoint record into log.

The behavior when the system crashes and recovers when concurrent transactions are executed is
shown below –Understanding Checkpoints in multiple Transactions

The recovery system reads the logs backward from the end to the last checkpoint i.e. from T4 to
T1.It will keep track of two lists – Undo and Redo.

Whenever there is a log with instruction <Tn, start>and <Tn, commit> or only <Tn, commit> then
it will put that transaction in Redo List.

T2 and T3 contain <Tn, Start> and <Tn, Commit> whereas T1 will have only <Tn, Commit>.
Here, T1, T2, and T3 are in the redo list.

Whenever a log record with no instruction of commit or abort is found, that transaction is put to
Undo List

<Here, T4 has <Tn, Start> but no <Tn, commit> as it is an ongoing transaction. T4 will be put in
the undo list.
 UNIT-IV TRANSACTION MANAGEMENT

Advantages of using Checkpoints:

It speeds up data recovery process.

Most of the dbms products automatically checkpoints themselves.

Checkpoint records in log file is used to prevent unnecessary redo operations.

Since dirty pages are flushed out continuously in the background, it has very low overhead and
can be done frequently.

RECOVERING FROM A SYSTEM CRASH:

When the system is restarted after a crash, the recovery manager proceeds in three phases, as
shown in Figure

The Analysis phase begins by examining the most recent begin checkpoint record,whose LSN is
denoted as C proceeds forward in the log until the last log record. The Redo phase follows
Analysis and redoes all changes to any page that might have been dirty at the time of the crash;
this set of pages and the starting point for Redo (the smallest recLSN of any dirty page) are
determined during Analysis. The Undo phase follows Redo and undoes the changes of all
transactions that were active at the time of the crash; again, this set of transactions is identified
during the Analysis phase.
Notice that Redo reapplies changes in the order in which they were originally carried out; Undo
reverses changes in the opposite order, reversing the most recent change first.
The three phases of restart are
 Analysis Phase
 Redo Phase
 Undo Phase
1.Analysis Phase :The Analysis phase performs three tasks:
1. It determines the point in the log at which to start the Redo pass.
2. It determines pages in the buffer pool that were dirty at the time of the crash.
3. It identifies transactions that were active at the time of the crash and must be undone.
Analysis begins by examining the most recent begin checkpoint log record and initializing the
dirty page table and transaction table to the copies of those structures in the next end checkpoint
record. Thus, these tables are initialized to the set of dirty pages and active transactions at the time
of the checkpoint.
 UNIT-IV TRANSACTION MANAGEMENT

2.Redo Phase:
During the Redo phase, ARIES reapplies the updates of all transactions, committed or
otherwise.The Redo phase begins with the log record that has the smallest recLSN of all pages in
the di
rty page table constructed by the Analysis pass because this log record identifies the oldest update
that may not have been written to disk prior to the crash.
Starting from this log record, Redo scans forward until the end of the log. For each redoable log
record (update or CLR) encountered, Redo checks whether the logged action must be redone.
The action must be redone unless one of the following conditions holds:
1.The affected page is not in the dirty page table, or
2.The affected page is in the dirty page table, but the recLSN for the entry is greater than the LSN
of the log record being checked, or
3.The pageLSN is greater than or equal to the LSN of the log record being checked.
The first condition obviously means that all changes to this page have been written to disk.
Because the recLSN is the first update to this page that may not have been written to disk,
the second condition means that the update being checked was indeed propagated to disk.
The third condition, which is checked last because it requires us to retrieve the page, also ensures
that the update being checked was written to disk,because either this update or a later update to
the page was written.
If the logged action must be redone:
1. The logged action is reapplied.
2. The pageLSN on the page is set to the LSN of the redone log record. No additional log record is
written at this time.
3. Undo Phase
The Undo phase scans backward from the end of the log.The goal of this phase is to undo the
actions of all transactions that were active at the time of the crash, that is, to effectively abort
them. This set of transactions is identified in the transaction table constructed by the Analysis
phase.
The Undo Algorithm
Undo begins with the transaction table constructed by the Analysis phase, which identifies all
transactions that were active at the time of the crash, and includes the LSN of the most recent log
record (the lastLSN field) for each such transaction. Such transactions are called loser
transactions.
All actions of losers must be undone, and further, these actions must be undone in the reverse of
the order in which they appear in the log.
Consider the set of lastLSN values for all loser transactions.
 UNIT-IV TRANSACTION MANAGEMENT

Let us call this set ToUndo. Undo repeatedly chooses the largest (i.e., most recent) LSN value in
this set and processes it, until ToUndo is empty.
To process a log record:
If it is a CLR, and the undoNextLSN value is not null, the undoNextLSN value is added to the set
To Undo; if the undoNextLSN is null, an end record is written for the transaction because it is
completely undone, and the CLR is discarded.
If it is an update record, a CLR is written and the corresponding action is undone, and the
prevLSN value in the update log record is added to the set To Undo.
When the set To Undo is empty, the Undo phase is complete. Restart is now complete, and the
system can proceed with normal operations.

******************************************************************************