Notices
Notice: Exam Form BE IV/II & BAR V/II (Back) for 2076 Magh
Routine: BE IV/II & BAR V/II - 2076 Magh
Result: BCE I/II exam held on 2076 Bhadra
Result: All (except BCE & BEI) I/II exam held on 2076 Bhadra
Notice: Exam Center for Barrier Exam (2076 Poush), 1st Part
View All
View Old Questions
Computer Engineering(BCT)
Electrical Engineering(BEL)
Electronics and Communication(BEX)
View All
View Syllabus
Computer Engineering(BCT)
Electrical Engineering(BEL)
Electronics and Communication(BEX)
View All

Notes of Database Management System [CT 652]

Transaction Processing and Concurrency Control

 

ACID Properties

Transactions

- Transaction is a single logical unit of operation which on collection performs some meaningful actions.
- The system should ensure proper execution of transactions
- Either the entire transaction executes or none of them executes
- The system also manages concurrent execution of transactions
- Each transaction access and possible updates various data items.


ACID Properties

1. Atomicity
- Either the entire transaction completes or none of it completes
- Transaction is indivisible

2. Consistency
- Execution of transaction must preserve database consistency
- If a transaction runs from a consistent database state. The database must be in consistent state after the end of transaction

3. Isolation
- A transaction should not appear its effects on other concurrent transactions
- Each transaction must operate properly without interference from concurrent operations.
- For a pair of Ti and Tj it appears to Ti that either Tj finished execution before Ti started or Tj started execution after T: templates.

4. Durability
- The changes made to the database by a transaction must be persistent even if the system fails or crashes


Transaction model

- Active state : the transaction is executing in the state
- Partially commited: the final statement has been executed.
- Commited : the transaction is completely successfully.
- Failed: Normal execution can not be proceed.
- Aborted:Transaction is rolled back and database is restored

states-of-transaction


Concurrent Executions

- The system allows multiple transactions to run concurrently
- It increase cpu and data utilization increasing throughputs.
- It reduces the average response time of transaction
- Concurrency control scheme must be formulated to control interaction among transactions to prevent database consistency


Schedule

- Schedule is the sequence of instructions that specify chronological order in which instructions of concurred transactions are executed.
- It must preserve the consistency of the database.


Example of Schedule

Consider the given figure:

serialize


Serializability Concept

- A schedule is serial if for every transaction participating in the schedule , all operations of a transaction executed consecutively in the schedule
- A schedule is serializable if it is not serial but is equivalent to some serial schedule of same transactions
- Two schedules are result equivalent if they produce the same final state of the database


Forms of Schedule Equivalence

1) Conflict serializablity
- To actions Ai and Aj executed on same data object by Ti and Tj conflicts if either one of them is write operation
- If Ai and Aj are consecutive non conflicting actions belonging to Ti and Tj we can swap Ai an Aj without changing result
- If schedule S can be transformed to S by a series of Swap m, S and S’ are conflict equivalent
- A schedule S is conflict serializable , if it is conflict equivalent to a serial schedule.

conflicts


Test for conflict serializability

- For each transaction Ti in schedule S create a node labeled T: in the precedence graph
- For each case in S where Tj executes write(X) , create edge (Ti – Tj )
- For each case in S where where Tj executes write(X) after Ti – Tj )
- S is serializable if graph has no cycle.

test


View Serializability

- The two schedules S2 and S2 are view equivalent if:
- For each data item Q if transaction T: reads initial value of Q in S1 then tranactions Ti must read initial value of B in S2
- For each data item Q If ti reads Q after Tj writes Q in S1 then T1 must read B after Ti writes Q in S2
- For each data item Q, if Ti writes final value of Q in S1 , then Ti must writes final value of Q in S2
- A schedule is view serializable if it is view equivalent to a serial schedule.

Consider transactions:
T1 : r1(Q) , w1(Q)
T2 : w2 (Q)
T3: w3 (Q)
Schedule S: r1(Q) , w2(Q) ,W1(Q) ,w3(Q)

Let s be serial schedule : s’ : r1(q), w2(q), w1(q), w3(q)
T1 reads initial value of Q in S and s’
No condition
T3 writes final value of Q in S and S’
S is view serializable.


Recoverable Schedule

- A schedule is recoverable if a transaction Tj reads a data item previously written by Transaction Ti then Ti should commit before Tj commits.
- Cascading rollback is a mechanism that performs a series of transaction rollbacks if a single transaction fails
- Cascade less schedule is the schedule in which for each pair of transactions Ti and Tj such that Tj reads data item previously written by Ti , Tj must commit before Tj reads.


Lock Based Protocols

- It is a protocol that ensures that when one transaction is accessing a data item , no other transaction can modify that data item with the use of locks
- A lock based protocol is a set of rules followed by all the transactions while requesting and releasing locks
- The transaction holding the lock on that item can only access that data item.
- Locks can be in two modes. The transaction holding shared mode lock (lock-s) can only read data item. - The transaction holding exclusive mode lock (lock-x) can both read and write data item


Lock compatibility Matrix

 

  S X
S T F
X F F

 

- Transaction request concurrency control manager for locks.
- A transaction may be granted a lock an item if request lock is compatible with locks already held on the item by other transactions.
- Any no of transactions can hold shared locks on an item
- If lack us not granted , the requesting transaction must wait

Disadvantages
1. Deadlock
2. Starvation


Two phase locking Protocol

Phase 1 : Growing phase
- Transaction may obtain locks
- Transaction may not release locks.

Phase 2 : Shrinking phase
- Transaction may release locks
- Transaction may not obtain locks.

- It results in deadlock
- It may cause cascading rollback (Use strict two phase locking )
- Rigorous two phase locking (holds all locks until commit)


Lock conversion

- It is a mechanism for upgrading a shared lock to exclusive lock and downgrading an exclusive lock to a shared lock.
- Upgrade takes place in growing phase
- Downgrade takes place in shrinking phase.
- It assures serializability


Implementation of lock conversion

- Lock manager replies to a lock request by sending lock grant message
- In case of deadlock it sends msg asking for rollback
- The requesting transaction waits until its request is answered
- It maintains data structure called lock table
- Lock table is in memory hash table indexed on name of data being locked
- Lock table also records type of lock granted or requested
- New requests added to the end of queue
- If transaction aborts , all of its requests are deleted


Deadlock Handling and Prevention

Deadlock is the condition in which all transactions in a set are holding locks to some data items and waiting for locks to other data items being currently held by other transactions of some set


Deadlock prevention

1. Ensure no cyclic waits
- All locks should be acquired together before execution
- Ordering requests for locks

2. No wait
- Wait-die scheme/rollback (T: waits only if it has time stamp smaller than that of Tj otherwise rolled back
- Wound wait scheme
- Timeout based scheme


Deadlock Detection

- Deadlock can be described as a wait for graph G- (V,E)
- V is for all transactions
- E is edges showing Ti- Tj
- If ti – Tj is in E , there is directed edge from Ti to Tj Implying that Ti is waiting for Tj to release the lock.
- The system is in deadlock if wait-for graph has a cycle.

Sponsored Ads