Page 168 - DCAP402_DCAO204_DATABASE MANAGEMENT SYSTEM_MANAGING DATABASE

Unit 9: Transaction Management

Deadlock Detection Notes

Deadlocks can be detected using a wait-for graph, which consists of a pair G = (V,E),
1. V is a set of vertices (all the transactions in the system)
2. E is a set of edges; each element is an ordered pair T T.
i j
If T T is in E, then there is a directed edge from T to T , implying that T is waiting for T to
i j i j i j
release a data item. When T requests a data item currently being held by T , then the edge T T
i j i j
is inserted in the wait-for graph. This edge is removed only when T is no longer holding a data
j
item needed by T .
i
The system is in a state of deadlock if the wait-for graph has a cycle. You must make use of a
deadlock-detection algorithm periodically to look for such cycles.
Figure 9.2: Deadlock Detection

9.12.2 Deadlock Recovery

When a deadlock is detected, some transaction will have to be rolled back to break the deadlock.
Selecting that transaction, as a victim will incur minimum cost. Rollback will determine the
distance the transaction needs to be rolled back. Total rollback aborts the transaction and then
restarts it. The more effective method of deadlock recovery is to rollback transaction only as far
as necessary to break the deadlock. Starvation occurs if the same transaction is always selected
as a victim. You can include the number of rollbacks in the cost factor calculation in order to
avoid starvation.

9.13 Insert and Delete Operation

If two-phase locking is used:
1. A delete operation may be performed only if the transaction deleting the tuple has an
exclusive lock on the tuple to be deleted.
2. A transaction that inserts a new tuple into the database is given an X-mode lock on the
tuple.
Insertions and deletions can lead to the phantom phenomenon.
1. A transaction that scans a relation (e.g., find all accounts in Bombay) and a transaction that
inserts a tuple in the relation (e.g., insert a new account at Bombay) may be in conflict with
each other, despite the fact that the two transactions are not accessing any tuple in common.
2. If only tuple locks are used, non-serialisable schedules may be the result: the scan than
transaction may not see the new account, yet may be serialised before the insert transaction.
The transaction scanning the relation reads the information that indicates what tuples the relation
contains, while a transaction inserting a tuple updates the same information.

LOVELY PROFESSIONAL UNIVERSITY 161