### SET 4

Question 1

**Consider two transactions T1 and T2, and four schedules S1, S2, S3, S4 of T1 and T2 as given below: **

T1 = R1[X] W1[X] W1[Y]

T2 = R2[X] R2[Y] W2[Y]

S1 = R1[X] R2[X] R2[Y] W1[X] W1[Y] W2[Y]

S2 = R1[X] R2[X] R2[Y] W1[X] W2[Y] W1[Y]

S3 = R1[X] W1[X] R2[X] W1[Y] R2[Y] W2[Y]

S4 = R1[X] R2[Y]R2[X]W1[X] W1[Y] W2[Y]

Which of the above schedules are conflict-serializable?

A : S1 and S2

B : S2 and S3

C : S3 only

D : S4 only

Answer Discuss it!

.

Correct answer is :B

Solution :

There can be two possible serial schedules T1 T2 and T2 T1. The serial schedule T1 T2 has the following sequence of operations R1[X] W1[X] W1[Y] R2[X] R2[Y] W2[Y] And the schedule T2 T1 has the following sequence of operations. R2[X] R2[Y] W2[Y] R1[X] W1[X] W1[Y] The Schedule S2 is conflict-equivalent to T2 T1 and S3 is conflict-equivalent to T1 T2

Question 2

**The following key values are inserted into a B+-tree in which order of the internal nodes is 3, and that of the leaf nodes is 2, in the sequence given below. The order of internal nodes is the maximum number of tree pointers in each node, and the order of leaf nodes is the maximum number of data items that can be stored in it. The B+-tree is initially empty. 10, 3, 6, 8, 4, 2, 1. The maximum number of times leaf nodes would get split up as a result of these insertions is**

A : 2

B : 3

C : 4

D : 5

Answer Discuss it!

.

Correct answer is :B

Question 3

**Let R and S be relational schemes such that R={a,b,c} and S={c}. Now consider the following queries on the database.Which of the following are equivalent ? **

A : I and II

B : I and III

C : II and IV

D : III and IV

Answer Discuss it!

.

Correct answer is :A

Solution :

I and II describe the division operator in Relational Algebra and Tuple Relational Calculus respectively.

Question 4

**Consider the following relational schema: **

Suppliers(__sid:integer__, sname:string, city:string, street:string)

Parts(__pid:integer__, pname:string, color:string)

Catalog(__sid:integer__, pid:integer, cost:real)

Consider the following relational query on the above database:

SELECT S.sname

FROM Suppliers S

WHERE S.sid NOT IN (SELECT C.sid

FROM Catalog C

WHERE C.pid NOT IN (SELECT P.pid

FROM Parts P

WHERE P.color<> 'blue'))

Assume that relations corresponding to the above schema are not empty. Which one of the following is the correct interpretation of the above query?

A : Find the names of all suppliers who have supplied a non-blue part.

B : Find the names of all suppliers who have not supplied a non-blue part.

C : Find the names of all suppliers who have supplied only blue parts

D : Find the names of all suppliers who have not supplied only blue parts.

Answer Discuss it!

.

Correct answer is :A

Solution :

The subquery “SELECT P.pid FROM Parts P WHERE P.color<> ‘blue’” gives pids of parts which are not blue. The bigger subquery “SELECT C.sid FROM Catalog C WHERE C.pid NOT IN (SELECT P.pid FROM Parts P WHERE P.color<> ‘blue’)” gives sids of all those suppliers who have supplied blue parts. The complete query gives the names of all suppliers who have supplied a non-blue part

Question 5

**Consider the following relational schema: **

Suppliers(__sid:integer__, sname:string, city:string, street:string)

Parts(__pid:integer__, pname:string, color:string)

Catalog(__sid:integer__, pid:integer, cost:real)

Assume that, in the suppliers relation above, each supplier and each street within a city has a unique name, and (sname, city) forms a candidate key. No other functional dependencies are implied other than those implied by primary and candidate keys. Which one of the following is TRUE about the above schema?

A : The schema is in BCNF

B : The schema is in BCNF

C : The schema is in 2NF but not in 3NF

D : The schema is not in 2NF

Answer Discuss it!

.

Correct answer is :A

Solution :

A relation is in BCNF if for every one of its dependencies X → Y, at least one of the following conditions hold:

X → Y is a trivial functional dependency (Y ⊆ X)

X is a superkey for schema R

Since (sname, city) forms a candidate key, there is no non-tirvial dependency X → Y where X is not a superkey

Question 6

**Consider a B+-tree in which the maximum number of keys in a node is 5. What is the minimum number of keys in any non-root node?**

A : 1

B : 2

C : 3

D : 4

Answer Discuss it!

.

Correct answer is :B

Solution :

2d-1 = 5

2d = 6

d = 3

d-1=2

Question 7

**A relational schema for a train reservation database is given below.**

What pids are returned by the following SQL query for the BELOW instance of the tables?

SELECT pid

FROM Reservation ,

WHERE class ‘AC’ AND

EXISTS (SELECT *

FROM Passenger

WHERE age > 65 AND

Passenger. pid = Reservation.pid)

A : 1,0

B : 1,2

C : 1,3

D : 1,5

Answer Discuss it!

.

Correct answer is :C

Question 8

**Which of the following concurrency control protocols ensure both conflict serialzability and freedom from deadlock? **

I. 2-phase locking

II. Time-stamp ordering

A : I only

B : II only

C : Both I and II

D : Neither I and II

Answer Discuss it!

.

Correct answer is :B

Solution :

2 Phase Locking (2PL) is a concurrency control method that guarantees serializability. The protocol utilizes locks, applied by a transaction to data, which may block (interpreted as signals to stop) other transactions from accessing the same data during the transaction’s life. 2PL may be lead to deadlocks that result from the mutual blocking of two or more transactions.

Timestamp-based concurrency control algorithm is a non-lock concurrency control method. In Timestamp based method, deadlock cannot occur as no transaction ever waits.

Question 9

**Consider the following schedule for transactions T1, T2 and T3.Which one of the schedules below is the correct serialization of the above? **

A : T1 -> T3 -> T2

B : T2 -> T1 -> T3

C : T2 -> T3 -> T1

D : T3 -> T1 -> T2

Answer Discuss it!

.

Correct answer is :A

Question 10

**Which of the following functional dependencies hold for relations R(A, B, C) and S(B, D, E): **

B -> A

A -> C

The relation R contains 200 tuples and the rel ation S contains 100 tuples. What is the maximum number of tuples possible in the natural join of R and S (R natural join S)

A : 100

B : 200

C : 300

D : 2000

Answer Discuss it!

.

Correct answer is :A

Solution :

From the given set of functional dependencies, it can be observed that B is a candidate key of R. So all 200 values of B must be unique in R. There is no functional dependency given for S. To get the maximum number of tuples in output, there can be two possibilities for S.

1) All 100 values of B in S are same and there is an entry in R that matches with this value. In this case, we get 100 tuples in output.

2) All 100 values of B in S are different and these values are present in R also. In this case also, we get 100 tuples.

Question 1

T1 = R1[X] W1[X] W1[Y]

T2 = R2[X] R2[Y] W2[Y]

S1 = R1[X] R2[X] R2[Y] W1[X] W1[Y] W2[Y]

S2 = R1[X] R2[X] R2[Y] W1[X] W2[Y] W1[Y]

S3 = R1[X] W1[X] R2[X] W1[Y] R2[Y] W2[Y]

S4 = R1[X] R2[Y]R2[X]W1[X] W1[Y] W2[Y]

Which of the above schedules are conflict-serializable?

.

Correct answer is :B

Solution :

There can be two possible serial schedules T1 T2 and T2 T1. The serial schedule T1 T2 has the following sequence of operations R1[X] W1[X] W1[Y] R2[X] R2[Y] W2[Y] And the schedule T2 T1 has the following sequence of operations. R2[X] R2[Y] W2[Y] R1[X] W1[X] W1[Y] The Schedule S2 is conflict-equivalent to T2 T1 and S3 is conflict-equivalent to T1 T2

Question 2

.

Correct answer is :B

Question 3

.

Correct answer is :A

Solution :

I and II describe the division operator in Relational Algebra and Tuple Relational Calculus respectively.

Question 4

Suppliers(

__sid:integer__, sname:string, city:string, street:string)

Parts(

__pid:integer__, pname:string, color:string)

Catalog(

__sid:integer__, pid:integer, cost:real)

Consider the following relational query on the above database:

SELECT S.sname

FROM Suppliers S

WHERE S.sid NOT IN (SELECT C.sid

FROM Catalog C

WHERE C.pid NOT IN (SELECT P.pid

FROM Parts P

WHERE P.color<> 'blue'))

Assume that relations corresponding to the above schema are not empty. Which one of the following is the correct interpretation of the above query?

.

Correct answer is :A

Solution :

The subquery “SELECT P.pid FROM Parts P WHERE P.color<> ‘blue’” gives pids of parts which are not blue. The bigger subquery “SELECT C.sid FROM Catalog C WHERE C.pid NOT IN (SELECT P.pid FROM Parts P WHERE P.color<> ‘blue’)” gives sids of all those suppliers who have supplied blue parts. The complete query gives the names of all suppliers who have supplied a non-blue part

Question 5

Suppliers(

__sid:integer__, sname:string, city:string, street:string)

Parts(

__pid:integer__, pname:string, color:string)

Catalog(

__sid:integer__, pid:integer, cost:real)

Assume that, in the suppliers relation above, each supplier and each street within a city has a unique name, and (sname, city) forms a candidate key. No other functional dependencies are implied other than those implied by primary and candidate keys. Which one of the following is TRUE about the above schema?

.

Correct answer is :A

Solution :

A relation is in BCNF if for every one of its dependencies X → Y, at least one of the following conditions hold:

X → Y is a trivial functional dependency (Y ⊆ X)

X is a superkey for schema R

Since (sname, city) forms a candidate key, there is no non-tirvial dependency X → Y where X is not a superkey

Question 6

.

Correct answer is :B

Solution :

2d-1 = 5

2d = 6

d = 3

d-1=2

Question 7

What pids are returned by the following SQL query for the BELOW instance of the tables?

SELECT pid

FROM Reservation ,

WHERE class ‘AC’ AND

EXISTS (SELECT *

FROM Passenger

WHERE age > 65 AND

Passenger. pid = Reservation.pid)

.

Correct answer is :C

Question 8

I. 2-phase locking

II. Time-stamp ordering

.

Correct answer is :B

Solution :

2 Phase Locking (2PL) is a concurrency control method that guarantees serializability. The protocol utilizes locks, applied by a transaction to data, which may block (interpreted as signals to stop) other transactions from accessing the same data during the transaction’s life. 2PL may be lead to deadlocks that result from the mutual blocking of two or more transactions.

Timestamp-based concurrency control algorithm is a non-lock concurrency control method. In Timestamp based method, deadlock cannot occur as no transaction ever waits.

Question 9

.

Correct answer is :A

Question 10

B -> A

A -> C

The relation R contains 200 tuples and the rel ation S contains 100 tuples. What is the maximum number of tuples possible in the natural join of R and S (R natural join S)

.

Correct answer is :A

Solution :

From the given set of functional dependencies, it can be observed that B is a candidate key of R. So all 200 values of B must be unique in R. There is no functional dependency given for S. To get the maximum number of tuples in output, there can be two possibilities for S.

1) All 100 values of B in S are same and there is an entry in R that matches with this value. In this case, we get 100 tuples in output.

2) All 100 values of B in S are different and these values are present in R also. In this case also, we get 100 tuples.