1.

Transaction:- A transaction is logical unit of database processing that include one or more
database access operations these can include insertion, deletion, modification or retrieval
operation. But we are inserted only read and write.

Executing read _ item(x) command include the following steps.

1.Find the address of the disk block that contains item x.

2.Copy the disk block into a butter in main memory .

3.Copy item x from the butter to the program variable named x.

Executing write _ item(x).

1.Find the address of disk block that contains item x.

2.Copy that disk block into a butter of main memory.

3.Copy item x from the program variable name x into the correct location in the butter.

4.Store the update block from the butter back to the disk .

Ex- of transaction:-

T1 T2

Read _ item x read _ item (x)

X: X-N X: X+M

Write _ item(x) write _ item (x);

Read_ item(y)

Y: Y+N

Write _ item (y)

Why concurrency Control is needed.

Now we discuss the types of problem. We encounter with these two transactions if they run
concurrently.

a. The lost update problem

 T1 T2

Read _ item(A) read _ item(A)

A: A-100 A: A-100

Write _ item (A)

Commit 1 write _item (A)

Commit T2

A=500 A=500

A=400 A=400

W: (400) W: (400)

2) Incorrect Summary anomaly (problem)

It one transaction is calculating an aggregate summary function on a number of record while

other transaction are updating some of these records the aggregate function may calculate some
values before they are update and others after they are update.

T1 T2

Read _ item(A) A=500

A: A-100 A=400

Write _ item(A) A=400

Read _ item(A) A=400

A: A+10% of A A=440

Write _item(A) A=440

 read_ item(B) B=700

B: = B +10% of B B=770

Write _ item(B) B =770

Commit T2

Read _ item (B) B=770

B: =B +100 B =870

Write _ item(B) B=870

Commit T1

The database is not consistent after adding 10% interest to all account the total amount should be
R.s 1320 . Where as after the completion of transaction in the above inter leave manner total
amount is R.s 1210.

A=500 500 * 10/100 =50

500+50=550

A=700 700*10/100=70

700+70=770

Total=1320

3) Direty read problem

The problem read occurs when transaction updates a database item and then the
transaction tails for some reason . The update item is access by another transaction before it is
change to back its original value.
 T1 T2

Read _item (X)

X: = X- N;

Write_ item(X)

Read _ item (X)

X: X +M

Write _ item(X)

Read _ item (Y)

Transaction T1 tails and

Must change the value of X back to its old value : meanwhile T2 has read the temporary
incorrect value of X.

4) Unrepeatable reads problem

Let us assume that transaction T1 reads the database object A. While the transaction T1 is
still in progress, transaction T2 updates the data item A and commits it. Meanwhile T1 again
reads A to find that it has a different value even through it has not modified it .

T1 T2

Read _ item (X)

Read _ item (X)

X =X+2

Write _ item (X)

Read _ item(X) Commit

2. Transaction States

1) BEGIN _ TRANSACTION = The beginning of transaction execution.

2) READ or WRITE= read or write operation of database that is part of transaction .

3) END TRANSACTION = This spacities read and write operations ended.

At this point it may be necessary to check whether the changes introduced by the transaction can
be permanently applied to the database or transaction tailed.

4) ACTIVE = A transaction goes into an active state immediately after it starts.

5) PARTIALLY COMMITTED STATE = At this point some recovery protocols needed to

ensure that a system failure will not result in an inability to record the change of the transaction
permanently .

Properties of Transactions (ACID)

Atomicity = Performed entirely or not performed at all.

Consistency = Take the database from one consistent state to another.

Isolation = Execution of a transaction should not be interfered with by any other transaction
executing concurrently.

Durability or permanency = Changes applied to the database by a committed transaction .

These changes must not be lost.

SYSTEM LOG

1. [start _ transaction, T]
2. [Write _ item, T, X. old _ value, new _ value]
3. [read _ item, T, X]
4. [committed, T]
5. [abort, T]

Schedule:-
A schedule S of N transactions T1,T2…… Tn is an ordering of operations of the
transactions subject to the constraint that for each transaction that participates in S , the operation
of T1 in S must appear in the same order in which they occur in T1.

T1: RT1(X), RT1(Y), WT1(X), WT1(Y)

T2: RT2(X), RT2(Y), WT2(X), WT2(Y)

T3: RT3(X), RT3(Z), WT3(X), WT3(Z), RT3(X), WT3(Y)

Ex. Of Schedules

S1: RT1(X) RT1(Y) WT1(X) WT1(Y) RT2(X) RT2(Y) WT2(X) WT2(Y) RT3(X) RT3(Z) WT3(X)
WT3(Z) RT3(X) WT3(Y)

S2: RT1(X) RT2(X) RT3(X) RT1(Y) RT2(Y) RT3(Z) WT1(X) WT2(X) WT3(X) WT1(Y) WT2(Y) WT3(Z)
RT3(X) WT3(Y)

Conflict Operation:-

Two operations are conflict if

(1) They are from two different transactions.

(2) They access the same data item
(3) At the least one of them is a write operations.

Ex:-

RT1(X) & RT2(X)

RT1(X) & WT1(X)

RT2(Y) & WT3(Z)

RT1(X), WT2(X)

Recoverability of Schedules:-
A schedule S is said to be recoverable it no transaction T in S commits until all
transactions T that have written an item that T reads have committed.

SC r1(x), w1(x), r2(y), w2(x), c2, a1

r1 (x), w1(x), r2(x), r1(y), w2(x), w1(y), c1, c2

S2:- RT1(x) RT1(y), WT1(x) WT1(y) RT2(x) RT2(y) WT2(x) WT2(y) RT3(x) RT3(z) WT3(x) WT3(z) RT3(y)
WT3(y) commit T1 commit T2 commit T3
Serial Schedule:-
A schedule S is a serial if for every transaction T participating in the schedule all the
operations of T are executed consecutively in the schedule otherwise the schedule is called non-
serial.

T1 T2 T1 T2

Read _ item(x) 500 read_item(x) 500

X: =X-N 490 X := X-N 490

Write _item(x) 490 write_item (x) 490 read_item(x) 490

Read _ item(y) 400 X :=

X+M 500

Y: = Y+N 410 read_item (y) 400

Write _item(y) write_item(x) 500

490 read_item (X) Y := Y+N

490+10 X := X+M write_item (y) 410

500 write_item(x)

Serial Schedule Non Serial Schedule

Result Equivalent
Serializability :- Determine which of the non-serial schedules always give a correct result &
which may give erroneous results . The concept used to characterized schedules in this manner is
that of serialzability of a schedule.

A transaction S of N transactions is serializable if it is equivalent to some serial schedule

of the same N transactions.

Equivalent:-

Result, conflict, view.

1) Result Equivalent:- Two schedules are result equivalent if they produce the same final
state of the database.
A schedule S of N transaction is result serializable if it is result equivalent to
some serial schedule.

S1 S2 X=100

Read _ item(x) read _ item(x)

X: =X +10 X: = X *1.1
Write _ item (x) write _ item(x)

1. Conflict Equivalent – Two schedules are said to conflict equivalent if the order of any two
conflicting operations is the same in both schedules.
A schedule is S to be conflict serializable if it is conflict equivalent to some serial
schedules S’

T1 T2

read_item (X)
X := X-N
Write_item (X)
read_item (X)
X := X+N
write_item (X)
read_item (Y)
Y := Y+N
write_item (Y)
 Conflict Equivalent

Algorithm for testing conflict serializability of a schedule S:

1. For each transaction Ti create a node letter Ti.

2. For each case in S where Tj executes a read_item (X) after T i executes a write_item (X)
create an edge (Ti Tj) is the precedence graph.
3. For each case in S where Tj executes a write_item (X) after T j executes a read_item (X)
create an edge (Ti Tj) is the precedence graph.
4. For each case in S where Tj executes a write_item (X) after T j executes a write_item (X)
create an edge (Ti Tj) is the precedence graph.
5. The schedule S is serializable if & only iff the precedence graph has no yell.

T1 T2 T3

read_item (Z)

read_item (Y)

write_item (Y)

read_item (Y)

read_item (Z)

read_item (X)

write_item (X) write_item (Y)

write_item (Z)

read_item (X)
read_item (Y)

read_item(Y)

write_item (X)

T1 X,Y T2

Y Y,Z Cycle X (T1 T2), Y (T2 T3)

T3 Cycle X (T1 T2), YZ (T2 T3), Y (T3 T1)

T1 T2 T3

read_item (Y)

read_item (Z)

read_item (X)

write_item (X) write_item (Y)

write_item (Z)

read_item (Z)

read_item (Y)

read_item(Y)

write_item (Y)

write_item (Y)

read_item (X)

write_item (X)
T1 X,Y T2

Y Y,Z

T3

View Serialzability – The schedules S & S1 are said to be view equivalent if the following three
conditions are met:

1. For each data item Q if transaction T i reads the initial value of Q in schedule S, then
transaction Ti must be in schedule S1 also read the initial value of Q.
2. For each data item Q if transaction Ti executes read (Q) in schedule S1 and that value was
produced by transaction Tj (if any), then transaction Ti must in schedule S1, also read the
value of Q that was produced by transaction Tj.
3. For each data item Q, the transaction (if any) that performs the final write (Q) operation
in schedule S must perform the final write (Q) operation in S1.

T1 T2 T1 T2 T1 T2
read (A) read(A) read (A)
A := A-50 temp := A*0.1 A := A-50
write (A) A := A – temp write(A)
read (B) write (A) read(A)
B := B+50 read(B) temp := A*0.1
write (B) B := B+ temp
read (A) write (B)
temp := A*0.1 read (A)
A := A – temp A := A + 50
write (A) write(A)
read (B) read(B)
B := B + temp B := B+50
write (B) write (B)

1 & 2 are not view equivalent.

2 & 3 are view equivalent
  We say that a schedule S is view serializable if it is view equivalent to a serial
schedule.

Deadlock Prevention with Transaction Timestamp: A transaction timestamp is a unique

identifier to each transaction based on its starting time. If a transaction starts earlier then the
former has smaller value timestamp then the latter. There are two scheme for prevention:
1. Wait Die
2. Wound Wait
Let us assume Tj acquire a lock on an item A and then T i comes along and tries to lock the same
item.

Wait Die:
If TS(Ti) < (Tj) then allow Ti to wait for Tj to release its lock otherwise abort and restart
Ti with the same timestamp.

Wound – Wait:
If TS(Ti) < (Tj) then abort Tj and restart Tj with the same timestamp. Otherwise
let Ti wait for Tj to release its lock.

Suppose T1 starts time 1 so TS (T1) = 1 & TS (T2) = 2

And T2 has locked item A and T1 attempts to lock item A.
 In case of wait die, TS (T1) < TS (T2) so T1 will wait for T2 to release the lock.
 In case of wound wait TS (T1) < TS(T2) so T2 will be aborted.

Deadlock Prevention Without Timestamp:

1. No waiting: If a transaction is unable to obtain a lock on an item, it is aborted and

is restarted after a certain dely.
2. Cautious Waiting: This approach by avoiding unnecessary termination of
transactions. If Ti tries to access a data item then T j has locked then if Tj is not
waiting on another resource allow Ti to wait for Tj to release the lock otherwise
abort Tj.
Deadlock Detection:
Wait For Graph
 For each transaction T currently running draw a node.
 If transaction Ti is waiting for a resource that transaction Tj has locked draw a directed
arc from Ti to Tj.
 When Tj release the lock erase the arc.
 If we can find a cycle then a deadlock exists.
 Abort one of the transactions to break the cycle.

T1: R1(A) W1(A) R1(B) W1(B) R1(C) W1(C) R1(D) W1(D) R1(E) W1(E)
T2: R2(E) W2(E) R2(A) W2(A) R2(B) W2(B) R2(H) W2(H)
T3: R3(F) W3(F) R3(B) W3(B)

T1: R1(A) W1(A) R1(B) W1(B) R1(C) W1(C) R1(D) W1(D)……….

T2: R2(E) W2(E)
T3: R3(F) W3(F)

T1 E T2

T3

Logging with Differed Updates: This approach is concerned with following updates:

1. When a transaction T begins, a begin type record is written to log.

2. During the execution for every update an update type record is approached to log.
3. If all actions comprising of T are successfully completed, commit record append to log.
  Now the records in log with respect to transaction T are all posted to the database
and end type record is append.

begin T

T: RT(A) LSN Type Er. id

A := A – 100 01 begin T

WT(A) 02 update T, A, 400

RT(B) 03 update T, B, 600

B := B+100 04 commit T

WT(B) 05 end T

Commit T

end T

Logging with Immediate Updates: In this approach all the updates of a transaction are posted
to a database immediately and a record is kept in log. In such situations every update type of
record in log must keep track of old value as well as new value.

LSN Type tr. Object Old Value new value

01 begin T
02 update T, A 500 400
03 update T, B 500 600
04 commit T

Lock Based Concurrency Control

Lock: A lock is a variable associated with a data item and describes the states of the item with
respect to applicability of reads, writes of a schedule. There is one lock for each data item.
Binary Lock: Having just two possible states namely lock and unlock.

Multistate Lock: Shared lock, Exclusive Lock, Unlock.

Granuality Of Lock: Locks can be applied to:

 A single data item.

 An entire row of a table
 A page (Memory Segment) (Many Rows)
 An entire table
 A entire database.

Two Phase Lock Protocol (2PL): A transaction obeys two phase locking mechanism if in one
phase it locks all the required items and in the second phase it unlocks these items. These two
phases are called growing and shrinking phases. There are 2 types of 2PL:
1. Strict 2PL: In this scheme two phases obey the following:

a. If a transaction T wants to read a database object it first requests a shared lock on

the object. If it wants to modify an object it requests an exclusive lock on the
object. This is called growing phase.
b. Released allo locks called shrinking phase. In this variation a transaction T does
not release any of its exclusive lock until after it commits or aborts strict 2PL is
not deadlock tree.

2. Conservative 2PL:

a. In this scheme the transaction pre declares which items it will work with and it
acquires all locks before any work is done.
b. Lock is released when transaction finishes its activities on the item.

3. Rigrous 2PL:

a. In this variation a transaction T does not release any of its lock (exclusive or
shared) until after it commits or aborts.

T: R(A) W(A) R(B) W(B) R(C) W(C) R(D) W(D)

Conservative:
X(A) X(B) X(C) X(D) R(A) W(A) U(A) R(B) W(B) U(B) R(C) W(C) U(C) R(D) W(D) U(D)

Strict:
X(A) R(A) W(A) X(B) R(B) W(B) XR(C) U(C) X(D) R(D) W(D) U(A) U(B) U(D)
Rigrous:
X(A) R(A) W(A) X(B) R(B) W(B) X(C) R(C) W(C) X(D) R(D) W(D) U(A) U(B) U(C) U(D)

Distributed Database:

Characteristics:
 Location Transparency
 Replication
 Formulation
Advantages:
 Local Control of Data
 Increasing Database Capacity
 System Availability
 Added Efficiency
Disadvantages:
 Update of replicated data
 More complex query processing
 Complex Shared data management.
 Complex Recovery
 Difficult Management of Data Dictionary
 Complex Database Design