Part -1:
1. Review questions
(a) What is the two-phase locking protocol? How does it guarantee serializability?
(b) Describe the wait-die and wound-wait protocols for deadlock prevention.
(c) Describe the cautious waiting, no waiting, and timeout protocols for deadlock prevention.
(d) What is a timestamp? How does the system generate timestamp?
2. Modify the data structure for multiple-mode locks (shared and exclusive) and the algorithm for read_lock(X), write_lock(X), and unlock(X) so that upgrading and downgrading of locks are possible. (The lock and unlock operations can be found on the course page under "figures for Chapter 20"; Hint: The lock needs to check the transaction id(s) that hold the lock, if any.) (20)
read_lock (X):
B: if LOCK (X)="unlocked"
then begin LOCK (¬ X) "read-locked"; no_of_reads(X) 1
end
else if LOCK(X)="read-locked"
then no_of_reads(X) ¬ no_of _reads(X) + 1
else begin wait (until LOCK (X)="unlocked" and
the lock manager wakes up the transaction);
go to B
end;
write_lock (X):
B: if LOCK (X)="unlocked"
then LOCK (X) ¬ "write-locked"
else begin
wait (until LOCK(X)="unlocked" and
he lock manager wakes up the transaction);
go to B
end;
unlock_item (X):
if LOCK (X)="write-locked"
then begin LOCK (X) "unlocked;" wakeup one of the waiting transactions, if any
end
else if LOCK(X)="read-locked"
then begin
no_of_reads(X) ¬ no_of_reads(X) - 1;
if no_of_reads(X)=0
then begin LOCK (X)="unlocked"; wakeup one of the waiting transactions, if any
end
end;
3. Apply the timestamp ordering algorithm to the schedules of Figure 19.8(b) and (c), and determine whether the algorithm will allow the execution of the schedules. (the figures can be found on the course page under "figures for chapter 19".)
4. The compatibility matrix of Figure 20.8 shows that IS and IX locks are compatible. Explain why this is valid. (the figures can be found on the course page under "figures for chapter 20".)
5. What is ‘certify' lock? Explain why this kind of locks is needed for multiversion 2PL.
|
IS |
IX |
S |
SIX |
X |
|
yes |
yes |
yes |
yes |
no |
| IX |
yes |
yes |
no |
no |
no |
| S |
yes |
no |
yes |
no |
no |
| SIX |
yes |
no |
no |
no |
no |
| X |
no |
no |
no |
no |
no |
Part -2:
1. What is the shadow paging principle? Assume that a database contains 7 pages and during the execution of a transaction page 5 and 1 are changed. Give the structures of the current directory and shadow directory before and after the transaction execution, respectively.
2. (a) Consider the five types of transactions given in Fig. 1. If "deferred update" strategy is used, which needs to be redone after the crash?
(b) Consider the five types of transactions given in Fig. 1. If "immediate update" strategy is used, which needs to be undone/redone after the crash?
3. (a) Discuss the two main types of constraints on specializations and generalization.
(b) How does a category differ from a regular shared subclass?
(c) Map the EER diagram shown in Fig. 4.1 into a relational schema.
4. Construct an R-tree over a set of records for geographical objects with the following coordinates [(x1, y1), (x2, y2)]:
[(0, 40), (60, 50)] ---- road1
[(40, 0), (60, 40)] ---- road2
[(15, 25), (35, 35)] ---- house1
[(70, 40), (80, 50)] ---- house2
[(70, 5), (80, 15)] ---- house3
[(35, 25), (80, 35)] ---- pipeline
Assume that each node (either leaf or interior) can store 3 entries.
5. Given the spatial database shown in the lecture notes on Spatial and Temporal Data Management. Design an SQL statement to find all the cities which are closer to Limerick than to Dublin.