Assignment On Database Management System
Question
Task:
Prepare a report addressing the following questions based on the concepts of database management system:
- List the ACID properties. Explain the usefulness of each.
- Consider the following two transactions:
T13: read(A);
read(B);
if A = 1 then B := B - 1;
write(B).
T14: read(B);
read(A);
if B = 1 then A := A - 1;
write(A).
Let the consistency requirement be A = 1 or B = 1, with A = 1 and B = 1 as the initial values.
- Show that every serial execution involving these two transactions preserves the consistency of the database.
- Show a concurrent execution of T13 and T14 that produces a nonserializable schedule.
- Is there a concurrent execution of T13 and T14 that produces a serializable schedule?
- What are the difference between shared lock and exclusive lock.
- Describe the phenomenon of cascading rollback. How can cascading rollback be avoid in a cascadeless schedule?
- What is the two-phase locking protocol? What is the strict two-phase locking protocol? What is the rigorous two-phase locking protocol? What benefit does strict two-phase locking protocol provide? What benefit does rigorous two-phase locking protocol provide?
- Consider the log in Figure 16.5 below. Suppose there is a crash just before the < T0 abort> log record is written out. Explain what would happen during recovery. Describe the redo and undo phase of the recovery algorithm.
Answer
1. List the ACID properties of database management system. Explain the usefulness of each
ACID - Atomicity, Consistency, Isolation, Durability
These are the properties that the transactions on the database should ensure.
Atomicity :
The atomicity property ensure that the transaction is atomic. An atomic transaction is either fully completed, or not started. Also known as ‘All or nothing rule’. Transactions cannot be partial.
Atomicity ensures that
- Abort - If a transaction is unable to complete for any reason, then the database system should return to its state before the start of the transaction. Changes will not be visible.
- Commit - If any transaction is success it should be completed entirely. Changes will be visible.
Consistency :
A transaction enforces consistency and integrity in the system that the system in in valid state after the transaction. It refers to the correctness of the database.
On the successful completion of transaction, the system has to be in valid state and in case of errors, the system should rollback to the previous valid state automatically.
Isolation :
Isolation property should ensure that the transaction to appear as isolated execution of transaction, even when there are many concurrent transactions being executed in the system.
Concurrency control is the key to achieve the isolation of the transactions.
If the transactions are not isolated, then the individual transactions may lead to inconsistence of the system by accessing inconsistent data for performing transactions.
Durability :
Durability ensures that all the transactionis made permanent and committed on the system.
It is responsible for the recovery control of the system.
This property ensures to make the transactions persistent on the database system. Storage to the permanent and non-volatilememory is performed.
2. Consider the following two transactions: (10 points)
T13: read(A);
read(B);
if A = 1 then B := B - 1;
write(B).
T14: read(B);
read(A);
if B = 1 then A := A - 1;
write(A).
Let the consistency requirement be A = 1 or B = 1, with A = 1 and B = 1 as the initial values.
a. Show that every serial execution involving these two transactions preserves the consistency of the database.
There are two possible serial execution as below:
Case 1: T13, T14
Case 2: T14, T13
consistency requirement be A = 1 or B = 1
The following table of transactions show that both serial executions are able to maintain consistency
|
|
Case 1: T13, T14 |
|
Case 2: T14, T13 |
||||
|
T13 |
Transaction |
A |
B |
T14 |
Transaction |
A |
B |
|
read(A); |
1 |
1 |
read(B); |
1 |
1 |
||
|
read(B); |
1 |
1 |
read(A); |
1 |
1 |
||
|
if A = 1 then B := B - 1; |
1 |
0 |
if B = 1 then A := A - 1;
|
0 |
1 |
||
|
write(B) |
1 |
0 |
write(A).
|
0 |
1 |
||
|
T14 |
read(B); |
1 |
0 |
T13 |
read(A); |
0 |
1 |
|
read(A); |
1 |
0 |
read(B); |
0 |
1 |
||
|
if B = 1 then A := A - 1;
|
1 |
0 |
if A = 1 then B := B - 1;
|
0 |
1 |
||
|
write(A).
|
1 |
0 |
write(B). |
0 |
1 |
||
b. Show a concurrent execution of T13 and T14 that produces a nonserializable schedule.
The concurrent execution of T13 and T14 with non-serializable schedule
|
T13 |
T14 |
|
read(A); |
|
|
read(B); |
|
|
|
read(B); |
|
|
read(A); |
|
if A = 1 then B := B - 1; |
|
|
write(B) |
|
|
|
if B = 1 then A := A - 1; |
|
|
write(A) |
|
|
|
c. Is there a concurrent execution of T13 and T14 that produces a serializable schedule?
From question a , we know that serializable schedule results in A= 1 , B=1. Suppose if we execute T13 read(A), and when schedule ends B=0 in T14.Similarly, when T14 read(A), and the schedule ends A=0 in T13.
3. What are the difference between shared lock and exclusive lock.
|
Shared Lock |
Exclusive Lock |
|
Allows a resource to be shared for many tasks/transactions |
Only one task/transaction can own the resource |
|
Read only request |
Update or write lock |
|
Last as long as the transaction holds |
Last until rollback or commit of the transaction |
|
Sharing of resources |
No sharing , and acquires exclusive access |
|
Allows multiple accesses/transactions |
Prevents others to access the resource |
4. Describe the phenomenon of cascading rollback. How can cascading rollback be avoid in a cascadeless schedule?
Cascading rollback is the phenomenon where a failure of a single transaction leads to the series of transaction rollbacks. It is the wastage of CPU times and undo significant amount of work done. It is a dirty read problem.
Example:
|
T1 |
T2 |
T3 |
|
Read(A) Write(A) |
|
|
|
|
Read(A) Write(A) |
|
|
|
|
Read(A) Write(A) |
Here when T1 transaction fails, it will lead to the rollback of series of transactionT2 and T3.
Cascadeless schedule can help in avoiding cascading rollback.
In cascadeless schedule, a pair of transactions Ti and Tj , Tj reads data written by Ti after the commit of Ti transaction. This ensures that the failure of the Ti does not lead to the aborting of other transactions Tj and avoids cascading rollback.
|
T1 |
T2 |
T3 |
|
Read(A) Write(A) Commit |
|
|
|
|
Read(A) Write(A) Commit |
|
|
|
|
Read(A) Write(A) Commit |
5. What is the two-phase locking protocol? What is the strict two-phase locking protocol? What is the rigorous two-phase locking protocol? What benefit does strict two-phase locking protocol provide? What benefit does rigorous two-phase locking protocol provide?
Two-phase locking protocol
A transaction is said to follow two phase locking protocol if locking and unlocking happens in 2 different consecutive phases during transaction’s execution,
Growing phase – New locks acquired and no locks released
Shrinking phase – Existing locks are released and no new locks acquired.
|
T1 |
T2 |
|
Lock-S(A) |
|
|
|
Lock-S(A) |
|
Lock-S(B) |
|
|
UnLock-S(A) |
|
|
|
Lock-X(C) |
|
UnLock-S(B) |
|
|
|
UnLock-S(A) |
|
|
UnLock-S(C) |
Strict two-phase locking protocol
This protocol acquires all locks similar to two-phase locking protocol but will release all exclusive locks only at the end after the transaction commit happens. This ensures to not release locks with uncommitted transactions. All locks release at a time after commit.
Here unlock happens after commit of the transaction
|
T1 |
T2 |
|
Lock-X(A) |
|
|
Commit; |
|
|
UnLock-X(A) |
Lock-X(A) |
|
|
Commit |
|
|
UnLock-X(A) |
Rigorous two-phase locking protocol
This protocol acquires all locks similar to two-phase locking protocol but will release all exclusive and shared locks only at the end after the transaction commit happens.
|
T1 |
T2 |
|
Lock-X(A) |
|
|
Lock-S(B) |
|
|
Commit; |
|
|
UnLock-X(A) |
Lock-X(A) |
|
UnLock-S(B) |
Lock-S(B) |
|
|
Commit |
|
|
UnLock-X(A) |
|
|
UnLock-S(B) |
Benefits of Strict two-phase locking protocol
It produces cascadeless schedules, and avoids cascading rollback
Benefits of Rigorous two-phase locking protocol
Avoids cascading rollback and no deadlock possibilities.
If there are two conflicting transactions, then their commit order gives the serializability order.
6. Consider the log in Figure 16.5 below. Suppose there is a crash just before the < T0 abort> log record is written out. Explain what would happen during recovery. Describe the redo and undo phase of the recovery algorithm. (8 points)
If a transaction fails before reaching its commit point , the effects of the transaction has to be undone , which is rollback involving undo and redo. This is detailed in recovery algorithm.
Belie are the steps,
- Identify uncommitted transactions
- Identify the committedtransaction
- Undo the updates of the uncommitted transactions
- Redo the updates made by committedtransactions.
During the undo phase, the system scans the log backwards from the end (rewind).
Whilescanning if the system identifies a log record of the transaction T2updating A, and A will be reset with the previous valueA=500;
After the identification of the state record of T2, an abort record isadded to the transaction T2.
As the undo-list does not keep any more transactions in its record,the undo phase terminates the whole process in order to complete the recovery.
Once the entire recovery process completes, the variables will be reset to; A=500, B=2000, C=600.
The added logrecords during recovery process includes the following:< T2,A,500 >; < T2abort >; < T0,B,2000 >; < T0, abort >
