Describe the wait-die and wound-wait protocols for deadlock prevention. Define three concurrency problems: dirty read, non-repeatable read, phantoms.
Wait-die and wound-wait protocols for deadlock prevention:
We can prevent deadlocks by giving each transaction a priority and ensuring that lower priority transactions are not allowed to wait for higher priority transactions (or vice versa). One way to assign priorities is to give each transaction a timestamp when it starts up. The lower the timestamp, the higher the transaction priority that is, the oldest transaction has the highest priority.
If a transaction Ti requests a lock and transaction Tj holds a conflicting lock, the lock manager can use one of the following two policies:
Wait-die scheme: It is a non-preemptive technique for deadlock prevention. When transaction Ti requests a data item currently held by Tj, Ti is allowed to wait only if it has a timestamp smaller than that of Tj (That is Ti is older than Tj), otherwise Ti is rolled back (dies)
For example:
Suppose that transaction T22, T23, T24 have time-stamps 5, 10 and 15 respectively. If T22requests a data item held by T23 then T22 will wait. If T24 requests a data item held by T23, then T24 will be rolled back.
Wound-wait scheme: It is a preemptive technique for deadlock prevention. It is a counterpart to the wait-die scheme. When Transaction Ti requests a data item currently held by Tj, Ti is allowed to wait only if it has a timestamp larger than that of Tj, otherwise Tj is rolled back (Tj is wounded by Ti)
For example:
Suppose that Transactions T22, T23, T24 have time-stamps 5, 10 and 15 respectively. If T22 requests a data item held by T23, then data item will be preempted from T23 and T23 will be rolled back. If T24 requests a data item held by T23, then T24 will wait.
Dirty read:
Situation: Connection A reads an object that has been modified by Connection B but Connection B has not committed yet. Here, Connection B rollback transaction and uncommitted data is already read by Connection A.
This is known as “Dirty Read”
Problem: Transaction T2 was permitted to read the intermediate result of transaction T1 before the transaction T1 was terminated.
Solution: Prevent T2 from reading the account balance until the transaction T1 is terminated. i.e. either committed or rollback.
|
T1 |
T2 |
|
R(A) |
|
|
A=A-100 |
|
|
W(A) |
|
|
|
R(A) |
|
|
X=A*0.02 |
|
|
A=A+X |
|
|
W(A) |
|
R(A) |
|
|
FAILS |
|
Non-repeatable read:
Situation: Connection A performs aggregate sum of accounts, at same time Connection B modifies the database. This is resulted into Inconsistent Analysis
Problem: of unrepeatable read occurs when a transaction reads a several values from database while other transaction updating those values.
Solution: prevent other transaction to read the values from the database until one transaction release it.
|
T1 |
T2 |
|
R(A) |
|
|
|
R(A) |
|
|
A=A+100 |
|
|
W(A) |
|
R(A) |
|
Phantoms: The Phantom Problem can occur in database management systems in scenarios involving concurrency, and can cause unexpected and faulty behavior. The phantom problem is explained as in course of a transaction, two identical queries are executed, and the collection of rows returned by the second query is different from the first.
Example: A transaction that scans a relation (e.g. find all accounts in Kolkata) and a transaction that inserts a tuple in the relation (e.g. insert a new account at Kolkata) may conflict in spite of not accessing any tuples in common. If only tuple locks are used, non-serializable schedules can result: the scan transaction may not see the new account, yet may be serialized before the insert transaction.
Write the difference between procedural and non-procedural query language.
Define a Foreign key. Why is the concept needed? How does it play a role in the join operation?
What is Resource management?
Write short notes on the following :
a) BFS
b) Tail recursion
What is WAP? Why it is used?
What are the propositions of Putnam’s model?
Difference between Inspections and Walkthrough
Discuss Quality Assurances
