Database Management System: Assignment 8

Total Marks : 20

September 26, 2018

Question 1
Identify the options which are true for Immediate-modification scheme. Marks:2 MSQ

a) Allows updates of an uncommitted transaction to be made to the buffer, or the disk itself,
before the transaction commits.

b) Update log record must be written after a database item is written.

c) Output of updated blocks to disk storage can take place at any time before or after trans-
action commit.

d) Performs updates to buffer/disk only at the time of transaction commit

Answer: a), c)
Explanation:
Refer Module 36 slide 20

1
Question 2
Consider the following state of transactions:

and the statements below:

1. T1 can be ignored.

2. T2 and T3 redone

3. T4 undone

4. T4 redone

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

a) 1), 2), 4)

b) 1), 2), 3)

c) only 1) and 2) but not 3)

d) only 2) and 3) but not 1)

Answer: b)
Explanation: Refer slide 30 in Module 36. Any transactions that committed before the last
checkpoint should be ignored. Therefore, T1 can be ignored (updates already output to disk
due to checkpoint).
Any transactions that committed since the last checkpoint need to be redone. Hence, T2 and
T3 are to be redone.
Any transaction that was running at the time of failure needs to be undone and restarted.
Hence, T4 to be undone.

2
Question 3
Consider the following log sequence:

<T0, start>
<T0, A, 1000, 950>
<T0, B, 2000, 2050>
<T0, commit>
<T1, start>
<T1, C, 700, 600>

What will be the recovery action by immediate modification recovery? Marks:2 MCQ

a) undo T0, redo T1

b) redo T0, redo T1

c) redo T0, undo T1

d) undo T0, undo T1

Answer: c)
Explanation: A and B are set to 950 and 2050 and C is restored to 700. Log records <T1,
C, 700>, <T1, abort> are written out.

3
Question 4
Refer to the RA expression below:

E1 1θ (E2 − E3 )

where E1 , E2 , and E3 are relational algebra expressions.

Identify the correct equivalent RA expression. Marks:2 MCQ

a) E1 ∩ (E2 1θ E3 )

b) (E1 1θ E2 − E1 1θ E3 )

c) (E1 1θ E2 1 E1 1θ E3 )

d) (E1 1θ E2 ∩ E1 1θ E3 )

Answer: b)
Explanation: Let us rename E1 1θ (E2 − E3 ) as R1, (E1 1θ E2 ) as R2 and (E1 1θ E3 ) as
R3. It is clear that if a tuple t belongs to R1, it will also belong to R2. If a tuple t belongs to
R3, t [E3’s attributes] will belong to E3, hence t cannot belong to R1. From these two we can
say that

∀t, t ∈ R1 −→ t ∈ (R2 − R3)

It is clear that if a tuple t belongs to R2 − R3, then t [R2’s attributes] ∈ E2 and t [R2’s
attributes] ∈/ E3. Therefore

∀t, t ∈ (R2 − R3) −→ t ∈ R1

The above two equations imply the given equivalence. This equivalence is helpful because
evaluation of the right hand side join will produce many tuples which will finally be removed
from the result. The left hand side expression can be evaluated more efficiently.

4
Question 5
Marks:2 MCQ
Refer to the representation of two queries in RA below

Identify the correct statement/s.

a) The queries are not equivalent

b) The queries are equivalent as selection operations are associative

c) The queries are equivalent as theta join operations are commutative

d) The queries are equivalent as natural join operations are associative

Answer: d)
Explanation: As per equivalence operation of Relational Expressions

5
Question 6
Consider the following expression below Marks:2 MSQ

Πemp name (((σaddress=”HighStreet” (employee)) 1 work f or 1 Πprojectid,project name (project))

The relation will be:

employee(emp id, emp name, address),

work for(emp id,projectid),
project(projectid, project name)

Identify the correct statement/s.

a) Executing the join (work f or 1 Πprojectid,project name (project)) at first, will increase the
overall query cost

b) Executing the join (σaddress=”HighStreet” (employee) 1 work f or) at first, will increase the
overall query cost

c) The order of execution of joins do not have any impact on the query cost

d) Executing the join (σaddress=”HighStreet” (employee)) 1 work f or at first, will not increase
the overall query cost

Answer: a), d)

Explanation: The join (work f or 1 Πprojectid,name (project)) is likely to be a large rela-

tion, since it contains one tuple for each employee working for one of the projects. As
multiple employees can work in multiple projects, this join will result in large data. In
contrast:(σaddress=”HighStreet” (employee)) 1 work f or is probably a small relation, as out of
the total employees, there will be only a small set living in High street. Hence if we do this
join first, then we get the project list for the small set of employees.

6
Question 7
Consider Index scan where selection condition must be on search-key of index.

Find the appropriate matching between Index and Cost. Marks:2 MCQ

Index

A) primary index, equality on key

B) primary index, equality on non-key

Cost

A) Cost = (hi + 1) * (tT + tS )

B) Cost = hi * (tT + tS ) + tS + tT * b

where,
tT – time to transfer one block
tS – time for one seek
hi – height of B+ Tree
b – number of blocks containing matching records

a) Index : A → Cost : A
Index : B → Cost : B

b) Index : A → Cost : B
Index : B → Cost : B

c) Index : A → Cost : A
Index : B → Cost : A

d) Index : A → Cost : B
Index : B →Cost : A

Answer: a)
Explanation: Refer slide 16 in Module 38

7
Question 8
Let us consider the following statistics for two relations students and courses:

• Number of records of students: nstudents = 60.

• Number of blocks of students: bstudents = 2.

• Number of records of courses: ncourses = 30.

• Number of blocks of courses: bcourses = 5.

Marks:2 MCQ
Now let us consider a natural join of students 1 courses. Identify the number of block
transfers in the worst case. Assume courses as the outer relation.

a) 302

b) 125

c) 152

d) 65

Answer: d)
Explanation: Number of block transfers is 30 * 2 + 5 = 65 if courses is the outer relation

8
Question 9
Identify the incorrect statement based on checkpointing. Marks:2 MCQ

a) All updates are stopped while doing checkpointing.

b) Continue scanning backwards till a record < Ti start > is found for every transaction Ti in
L.

c) Scan backwards from end of log to find the most recent < checkpoint L > record.

d) Scan from starting of log to find the most recent < checkpoint L > record.

Answer: d)
Explanation: Refer slide no 29 in Module 36.

9
Question 10
What is the effect of the UNDO operation corresponding to a log record < Ti , Y, S, K > where
Ti is the transaction, and S and K are the old and new values respectively of a data location
Y? Marks:2 MCQ

a) No change to Y

b) Writes the value S to Y

c) Writes the value K to Y

d) Sets Y to 0

Answer: b)
Explanation: As per the undo operation protocol.

10