Database Management System: Assignment 8

Total Marks : 100

August 28, 2023

Question 1
Assume an immediate database modification scheme. Consider the following log records
for transactions T1, T2, T3 and T4: Marks: 2 MCQ

steps Details of log

1 hT1,starti
2 hT2,starti
3 hT1,A,500,600i
4 hT1,commiti
5 hT2,B,200,400i
6 hcheckpoint{T2} i
7 hT3,starti
8 hT2,commiti
9 hT3,C,200,500i
10 hT4,starti
11 hT4,D,600,1000i
12 hT4,commiti

If there is a crash just after step 12 and the recovery of the system is successfully completed,
identify the correct action for the above scenario.

a) No Action: T1; Redo: T4; Undo: T2, T3

b) No Action: T2; Redo: T4; Undo: T1, T3

c) No Action: T1; Redo: T2, T3; Undo: T4

d) No Action: T1; Redo: T2, T4; Undo: T3

Answer: d)
Explanation: In the immediate database modification scheme, during recovery after a
crash, a transaction needs to be redone if and only if both hTi , starti, hTi , commiti are
present in the log. Otherwise, undo is required.
Any transactions that are committed before the last checkpoint should be ignored(updates
already output to disk due to the checkpoint).
Redo list contains transaction {T2, T4} and undo list contains transaction {T3} and for
transaction {T1} no need any action because it is already committed before checkpoint.
Hence, option d) is the answer.

1
Question 2
Let us consider the following statistics for searching for a condition in a given relation.
Marks:2 MCQ

• Number of blocks containing record of the relation (b) = 70

• Time to transfer one block (tb ) = 0.2 milliseconds

• Time for one seek (ts ) = 10 milliseconds

Identify the cost of selection query on a key attribute using linear search file scan.

a) 10.2 milliseconds

b) 17 milliseconds

c) 24 milliseconds

d) 10 milliseconds

Answer: b)
Explanation: If selection is on a key attribute, cost = (b/2) block transfers + 1 seek
Cost=((70/2)*0.2) + 10 = 17 milliseconds.
For more details refer to Module 38, slide 15.

2
Question 3
Assume an immediate database modification scheme. Consider the following log records for
transactions T1, T2, T3 and T4: Marks: 2 MSQ

steps Details of log

1 hT3,starti
2 hT3,A,200,400i
3 hT2,starti
4 hT2,B,300,600i
5 hT2,commiti
6 hcheckpoint{T3} i
7 hT1,starti
8 hT1,C,400,800i
9 hT4,starti
10 hT3,commiti
11 hT4,D,300,700i

If there is a crash just after step 11 and the recovery of the system is successfully completed,
identify the correct action for the above scenario.

a) After recovery completion, value of A will be 200.

b) After recovery completion, value of A will be 400.

c) After recovery completion, value of C will be 400.

d) After recovery completion, value of C will be 800.

Answer: b), c)
Explanation: In the immediate database modification scheme, during recovery after a
crash, a transaction needs to be redone if and only if both hTi , starti, hTi , commiti are
present in the log. Otherwise, undo is required.
Any transactions that are committed before the last checkpoint should be ignored(updates
already output to disk due to the checkpoint).
Redo list contains transaction {T3} and undo list contains transactions {T1, T4} and for
transaction {T2} no need any action because it is already committed before checkpoint.
As per the process of transaction recovery, options (b) and (c) are correct.

3
Question 4
Let us consider the following statistics for two relations Mountain Climber and Trekk Schedule:
Marks: 2 MCQ

• Number of records of Mountain Climber: nMountain Climber = 4000.

• Number of blocks of Mountain Climber: bMountain Climber = 400.

• Number of records of Trekk Schedule: nTrekk Schedule = 2000.

• Number of blocks of Trekk Schedule: bTrekk Schedule = 200.

Identify the required number of block transfers and seeks if the smaller relation fits entirely
in memory, use that as the inner relation using Nested-loop join.

a) 800400 block transfers and 2 seeks

b) 800200 block transfer and 2 seeks

c) 600 block transfers and 2 seeks

d) 400 block transfers and 2 seeks

Answer: c)
Explanation: If the smaller relations (Trekk Schedule) fit entirely into the memory, it is a
must to use that relation as the inner relation in Nested-loop join.
As a result, each block will only be read once.
Hence, the total number of block transfers will be: bMountain Climber + bTrekk Schedule
=400 + 200
= 600.
Total number of seeks required: 2.
For more details refer to 38.31 of lecture material.

4
Question 5
Consider the log record of Transaction T1 with one operation instance O1 used in a recovery
system with early lock release, B+ tree based concurrency control. Marks: 2 MCQ

Step Operation
1 hT1, starti
2 hT1, A, 700, 200i
3 hT1, O1, operation–begini
4 hT1, B, 300, 600i
5 hT1, C, 200, 400i
6 hT1, O1, operation–end,(B, -300),(C, -200)i
7 crash or abort here

Choose the correct set of log entries for the recovery of transactions.

hT1,C,200i
hT1,B,300i
a) hT1,O1,operation–aborti
hT1,A,700i
hT1,aborti

hT1,C,400,200i
hT1,B,600,300i
b) hT1,O1,operation–aborti
hT1,A,700,200i
hT1,aborti

hT1,C,200,400i
hT1,B,300,600i
c) hT1,O1,operation–aborti
hT1,A,700i
hT1,aborti

hT1,C,400,200i
hT1,B,600,300i
d) hT1,O1,operation–aborti
hT1,A,700i
hT1,aborti

Answer: d)
Explanation: Step i: Scan the log records backward.
Step ii: For step 6, hT1, O1, operation-end, (B, -300),(C, -200)i log is found; so, logical
undo is required for operation O1 on the variables C and B using the information (subtraction
of 200 for C variable) and (subtraction of 300 for B variable). That means we have to delete the
previous modifications on B and C. So, add the following logs for steps 5, 4 and 3 respectively:
hT1,C,400,200i, hT1,B,600,300i and hT1,O1,operation–aborti.
Step iv: For step 2, add the log hT1, A, 700i.
Step v: For step 1, add the log hT1, abort i.
Hence, option (d) is correct.

5
Question 6
Consider the following state of transactions and the statements below.

1. Only T1 can be ignored.

2. T1 , T2 and T3 can be ignored.

3. T2 , T3 , T4 , and T6 need to be redone.

4. T4 and T6 need to be redone.

5. Only T5 needs to be undone.

Identify the correct group of statements from the options below. Marks:2 MCQ

a) 1), 2), 3), 5)

b) 1), 3), 4), 5)

c) 1), 3), 5)

d) 2), 4), 5)

Answer: d)
Explanation: Any transaction that is committed before the last checkpoint should be ignored.
Therefore, T1 , T2 , and T3 can be ignored (updates already output to disk due to the last
checkpoint).
Any transaction that is committed since the last checkpoint, needs to be redone. Hence, T4
and T6 are to be redone.
Any transaction that was running at the time of failure, needs to be undone and restarted.
Hence, only T5 is to be undone.
Hence, option (d) is correct.

6
Question 7
Consider the following relational schema: Marks: 2 MCQ
Mountain Climber(MCid, MC name, Address, EmailID)
Trekk Details(Tname, Altitude, Diff Level)
Trekk Schedule(MCid, Tname, Start date, End date)

Two query trees are given below.

Figure 1:
Figure 2:

Identify the correct statement for the above two query trees.

a) Two query trees are equivalent as identical operations (irrespective of their positions) are
used in both trees.

b) Two query trees are not equivalent as selection or projection operation cannot be carried
out before or after the natural join operation.

c) Two query trees are equivalent and the query tree of Figure 1 will lead to more efficient
query processing.

d) Two query trees are equivalent and the query tree of Figure 2 will lead to more efficient
query processing.

Answer: c)
Explanation: Two query trees are equivalent, and Figure 1 will lead to more efficient query
processing because performing the selection operation as early as possible reduces the size of
the relation to be joined.
Hence, option (c) is correct.

7
Question 8
Consider the following relational schema: Marks: 2 MSQ
Mountain Climber(MCid, MC name, Address, EmailID)
Trekk Details(Tname, Altitude, Diff Level)
Trekk Schedule(MCid, Tname, Start date, end date)
Identify the option(s) that represent equivalent Query trees.

a)

b)

c)

d)

Answer: a), d)
Explanation: As per the equivalence rules of relational algebra expressions, options a) and
d) are correct. For more details refer to Module 39, slides 11,12.

8
Question 9
Identify the cost estimation of a query evaluation plan, if 500 blocks are required to be
transferred from the disk and the required number of disk seeks is 20.

• Time to transfer one block: tT = 2 milliseconds.

• Time for one seek: tS = 0.2 seconds.

Marks:2 MCQ

a) 1.2 Seconds

b) 2.2 Seconds

c) 5 Seconds

d) 5.2 Seconds

Answer: c)
Explanation: Cost for b block transfers plus S seeks will be (b ∗ tT + S ∗ tS ) seconds
=(500 ∗ 2 ∗ 10−3 ) + (20 ∗ 0.2) seconds
= (1 + 4) Seconds
= 5 Seconds
For more details refer to 38.12 of lecture material.
Hence, option c) is the answer.

9
Question 10
Which of the following statements is (are) true? Marks: 2 MSQ

a) Physical blocks are those blocks residing on the disk.

b) System buffer blocks are those blocks which reside temporarily in the main memory.

c) System buffer blocks are those blocks residing on the disk.

d) The log is a sequence of schedules, which maintains information about topological order-
ings of each schedule.

Answer: a), b)
Explanation: The log is a sequence of log records, which maintains information about
update activities on the database, kept on any stable storage.
Physical blocks are those blocks residing on the disk.
System buffer blocks are the blocks residing temporarily in main memory.
Hence, options (a) and (b) are the correct answers.
For more details refer to Module 36.

10