### SET 6

Question 1

**Which one of the following is a key factor for preferring B+ -trees to binary search trees for indexing database relations?**

A : Database relations have a large number of records

B : Database relations are sorted on the primary key

C : B+ -trees require less memory than binary search trees

D : Data transfer from disks is in blocks

Answer Discuss it!

.

Correct answer is :D

Question 2

**Which one of the following statements about normal forms is FALSE?**

A : BCNF is stricter than 3NF

B : Lossless, dependency-preserving decomposition into 3NF is always possible

C : Lossless, dependency-preserving decomposition into BCNF is always possible

D : Any relation with two attributes is in BCNF

Answer Discuss it!

.

Correct answer is :C

Solution :

It is not always possible to decompose a table in BCNF and preserve dependencies. For example, a set of functional dependencies {AB –> C, C –> B} cannot be decomposed in BCNF. See this for more details.

Question 3

**Let r be a relation instance with schema R = (A, B, C, D). We define r1 = π**_{A, B, C} (r) and r2 = π_{A.D} (r). Let s = r1 * r2 where * denotes natural join. Given that the decomposition of r into r1 and r2 is lossy, which one of the following is TRUE?

A : s ⊂ r

B : r ∪ s = r

C : r ⊂ s

D : r * s = s

Answer Discuss it!

.

Correct answer is :C

Solution :

Consider the following example with lossy decomposition of r into r1 and r2. We can see that r is a subset of s.

Table r
A B C D
---------------------------
1 10 100 1000
1 20 200 1000
1 20 200 1001
Table r1
A B C
------------------
1 10 100
1 20 200
Table r2
A D
-----------
1 1000
1 1001
Table s (natural join of r1 and r2)
A B C D
-----

Question 4

**Let E1 and E2 be two entities in an E/R diagram with simple single-valued attributes. R1 and R2 are two relationships between E1 and E2, where R1 is one-to-many and R2 is many-to-many. R1 and R2 do not have any attributes of their own. What is the minimum number of tables required to represent this situation in the relational model?**

A : 2

B : 3

C : 4

D : 5

Answer Discuss it!

.

Correct answer is :B

Solution :

The answer is B, i.e minimum 3 tables. Strong entities E1 and E2 are represented as separate tables. In addition to that many-to-many relationships(R2) must be converted as seperate table by having primary keys of E1 and E2 as foreign keys. One-to-many relaionship (R1) must be transferred to 'many' side table(i.e. E2) by having primary key of one side(E1) as foreign key( this way we need not to make a seperate table for R1). Let relation schema be E1(a1,a2) and E2( b1,b2). Relation E1( a1 is the

Question 5

**The following table has two attributes A and C where A is the primary key and C is the foreign key referencing A with on-delete cascade.**

A C

-----

2 4

3 4

4 3

5 2

7 2

9 5

6 4

The set of all tuples that must be additionally deleted to preserve referential integrity when the tuple (2,4) is deleted is:

A : (3,4) and (6,4)

B : (5,2) and (7,2)

C : (5,2), (7,2) and (9,5)

D : (3,4), (4,3) and (6,4)

Answer Discuss it!

.

Correct answer is :C

Solution :

When (2,4) is deleted. Since C is a foreign key referring A with delete on cascade, all entries with value 2 in C must be deleted. So (5, 2) and (7, 2) are deleted. As a result of this 5 and 7 are deleted from A which causes (9, 5) to be deleted.

Question 6

**The relation book (title, price) contains the titles and prices of different books. Assuming that no two books have the same price, what does the following SQL query list? **

select title

from book as B

where (select count(*)

from book as T

where T.price > B.price) < 5

A : Titles of the four most expensive books

B : Title of the fifth most inexpensive book

C : Title of the fifth most expensive bookTitles of the five most expensive books

D : Titles of the five most expensive books

Answer Discuss it!

.

Correct answer is :D

Solution :

When a subquery uses values from outer query, the subquery is called correlated subquery. The correlated subquery is evaluated once for each row processed by the outer query.
The outer query selects all titles from book table. For every selected book, the subquery returns count of those books which are more expensive than the selected book. The where clause of outer query will be true for 5 most expensive book. For example count (*) will be 0 for the most expensive book and count(*) will be 1 f

Question 7

**Consider a relation scheme R = (A, B, C, D, E, H) on which the following functional dependencies hold: {A–>B, BC–>D, E–>C, D–>A}. What are the candidate keys of R?**

A : AE, BE

B : AE, BE, DE

C : AEH, BEH, BCH

D : AEH, BEH, DEH

Answer Discuss it!

.

Correct answer is :D

Solution :

A set of attributes S is candidate key of relation R if the closure of S is all attributes of R and there is no subset of S whose closure is all attributes of R.

Closure of AEH, i.e. AEH+ = {ABCDEH}

Closure of BEH, i.e. BEH+ = {ABCDEH}

Closure of DEH, i.e. DEH+ = {ABCDEH}

Question 8

**Consider the following log sequence of two transactions on a bank account, with initial balance 12000, that transfer 2000 to a mortgage payment and then apply a 5% interest.**

1. T1 start
2. T1 B old=12000 new=10000
3. T1 M old=0 new=2000
4. T1 commit
5. T2 start
6. T2 B old=10000 new=10500
7. T2 commit

Suppose the database system crashes just before log record 7 is written. When the system is restarted, which one statement is true of the recovery procedure?

A : We must redo log record 6 to set B to 10500

B : We must undo log record 6 to set B to 10000 and then redo log records 2 and 3.

C : We need not redo log records 2 and 3 because transaction T1 has committed

D : We can apply redo and undo operations in arbitrary order because they are idempotent

Answer Discuss it!

.

Correct answer is :C

Solution :

Once a transaction is committed, no need to redo or undo operations.

Question 9

**Consider the relation account (customer, balance) where customer is a primary key and there are no null values. We would like to rank customers according to decreasing balance. The customer with the largest balance gets rank 1. ties are not broke but ranks are skipped: if exactly two customers have the largest balance they each get rank 1 and rank 2 is not assigned**

Query1:
select A.customer, count(B.customer)
from account A, account B
where A.balance <=B.balance
group by A.customer
Query2:
select A.customer, 1+count(B.customer)
from account A, account B
where A.balance < B.balance
group by A.customer

Consider these statements about Query1 and Query2.

1. Query1 will produce the same row set as Query2 for
some but not all databases.
2. Both Query1 and Query2 are correct implementation
of the specification
3. Query1 is a correct implementation of the specification
but Query2 is not
4. Neither Query1 nor Query2 is a correct implementation
of the specification
5. Assigning rank with a pure relational query takes
less time than scanning in decreasing balance order
assigning ranks using ODBC.

Which two of the above statements are correct?

A : 2 and 5

B : 1 and 3

C : 1 and 4

D : 3 and 5

Answer Discuss it!

.

Correct answer is :C

Question 10

**Consider the relation "enrolled(student, course)" in which (student, course) is the primary key, and the relation "paid(student, amount)" where student is the primary key. Assume no null values and no foreign keys or integrity constraints. Given the following four queries:**

Query1: select student from enrolled where
student in (select student from paid)
Query2: select student from paid where
student in (select student from enrolled)
Query3: select E.student from enrolled E, paid P
where E.student = P.student
Query4: select student from paid where exists
(select * from enrolled where enrolled.student
= paid.student)

Which one of the following statements is correct?

A : All queries return identical row sets for any database

B : Query2 and Query4 return identical row sets for all databases but there exist databases for which Qu

C : There exist databases for which Query3 returns strictly fewer rows than Query2

D : There exist databases for which Query4 will encounter an integrity violation at runtime.

Answer Discuss it!

.

Correct answer is :A

Solution :

The output of Query2, Query3 and Query4 will be identical. Query1 may produce duplicate rows. But rowset produced by all of them will be same.

Table enrolled

student course
---------------
abc c1
cs_2006 c1
abc c2
pqr c1
Table paid
student amount
-----------------
abc 20000
cs_2006 10000
rst 10000

Output of Query 1

abc

abc

cs_2006

Output of Query 2

abc

cs_2006

Question 11

**Consider the relation enrolled(student, course) in which (student, course) is the primary key, and the relation paid(student, amount), where student is the primary key. Assume no null values and no foreign keys or integrity constraints. Assume that amounts 6000, 7000, 8000, 9000 and 10000 were each paid by 20% of the students. Consider these query plans (Plan 1 on left, Plan 2 on right) to "list all courses taken by students who have paid more than x".**

A disk seek takes 4ms, disk data transfer bandwidth is 300 MB/s and checking a tuple to see if amount is greater than x takes 10 micro-seconds. Which of the following statements is correct?

A : Plan 1 and Plan 2 will not output identical row sets for all databases.

B : A course may be listed more than once in the output of Plan 1 for some databases

C : For x = 5000, Plan 1 executes faster than Plan 2 for all databases

D : For x = 9000, Plan I executes slower than Plan 2 for all databases.

Answer Discuss it!

.

Correct answer is :C

Solution :

Assuming that large enough memory is available for all data needed. Both plans need to load both tables courses and enrolled. So disk access time is same for both plans.

Plan 2 does lesser number of comparisons compared to plan 1.

1) Join operation will require more comparisons as the second table will have more rows in plan 2 compared to plan 1.

2) The joined table of two tables will will have more rows, so more comparisons are needed to find amounts greater than x.

Question 12

**The following functional dependencies are given:**

AB -> CD, AF -> D, DE -> F, C -> G , F -> E, G -> A

Which one of the following options is false?

A : CF+ = {ACDEFG}

B : BG+ = {ABCDG}

C : AF+ = {ACDEFG}

D : AB+ = {ABCDFG}

Answer Discuss it!

.

Correct answer is :C

Solution :

Closure of AF or AF+ = {ADEF}, closure of AF doesn’t contain C and G.

Option (D) also looks correct. AB+ = {ABCDG}, closure of AB doesn’t contain F.

Question 1

.

Correct answer is :D

Question 2

.

Correct answer is :C

Solution :

It is not always possible to decompose a table in BCNF and preserve dependencies. For example, a set of functional dependencies {AB –> C, C –> B} cannot be decomposed in BCNF. See this for more details.

Question 3

_{A, B, C}(r) and r2 = π

_{A.D}(r). Let s = r1 * r2 where * denotes natural join. Given that the decomposition of r into r1 and r2 is lossy, which one of the following is TRUE?

.

Correct answer is :C

Solution :

Consider the following example with lossy decomposition of r into r1 and r2. We can see that r is a subset of s.

Table r A B C D --------------------------- 1 10 100 1000 1 20 200 1000 1 20 200 1001 Table r1 A B C ------------------ 1 10 100 1 20 200 Table r2 A D ----------- 1 1000 1 1001 Table s (natural join of r1 and r2) A B C D -----

Question 4

.

Correct answer is :B

Solution :

The answer is B, i.e minimum 3 tables. Strong entities E1 and E2 are represented as separate tables. In addition to that many-to-many relationships(R2) must be converted as seperate table by having primary keys of E1 and E2 as foreign keys. One-to-many relaionship (R1) must be transferred to 'many' side table(i.e. E2) by having primary key of one side(E1) as foreign key( this way we need not to make a seperate table for R1). Let relation schema be E1(a1,a2) and E2( b1,b2). Relation E1( a1 is the

Question 5

A C

-----

2 4

3 4

4 3

5 2

7 2

9 5

6 4

The set of all tuples that must be additionally deleted to preserve referential integrity when the tuple (2,4) is deleted is:

.

Correct answer is :C

Solution :

When (2,4) is deleted. Since C is a foreign key referring A with delete on cascade, all entries with value 2 in C must be deleted. So (5, 2) and (7, 2) are deleted. As a result of this 5 and 7 are deleted from A which causes (9, 5) to be deleted.

Question 6

select title

from book as B

where (select count(*)

from book as T

where T.price > B.price) < 5

.

Correct answer is :D

Solution :

When a subquery uses values from outer query, the subquery is called correlated subquery. The correlated subquery is evaluated once for each row processed by the outer query. The outer query selects all titles from book table. For every selected book, the subquery returns count of those books which are more expensive than the selected book. The where clause of outer query will be true for 5 most expensive book. For example count (*) will be 0 for the most expensive book and count(*) will be 1 f

Question 7

.

Correct answer is :D

Solution :

A set of attributes S is candidate key of relation R if the closure of S is all attributes of R and there is no subset of S whose closure is all attributes of R.

Closure of AEH, i.e. AEH+ = {ABCDEH}

Closure of BEH, i.e. BEH+ = {ABCDEH}

Closure of DEH, i.e. DEH+ = {ABCDEH}

Question 8

1. T1 start 2. T1 B old=12000 new=10000 3. T1 M old=0 new=2000 4. T1 commit 5. T2 start 6. T2 B old=10000 new=10500 7. T2 commit

Suppose the database system crashes just before log record 7 is written. When the system is restarted, which one statement is true of the recovery procedure?

.

Correct answer is :C

Solution :

Once a transaction is committed, no need to redo or undo operations.

Question 9

Query1: select A.customer, count(B.customer) from account A, account B where A.balance <=B.balance group by A.customer Query2: select A.customer, 1+count(B.customer) from account A, account B where A.balance < B.balance group by A.customer

Consider these statements about Query1 and Query2.

1. Query1 will produce the same row set as Query2 for some but not all databases. 2. Both Query1 and Query2 are correct implementation of the specification 3. Query1 is a correct implementation of the specification but Query2 is not 4. Neither Query1 nor Query2 is a correct implementation of the specification 5. Assigning rank with a pure relational query takes less time than scanning in decreasing balance order assigning ranks using ODBC.

Which two of the above statements are correct?

.

Correct answer is :C

Question 10

Query1: select student from enrolled where student in (select student from paid) Query2: select student from paid where student in (select student from enrolled) Query3: select E.student from enrolled E, paid P where E.student = P.student Query4: select student from paid where exists (select * from enrolled where enrolled.student = paid.student)

Which one of the following statements is correct?

.

Correct answer is :A

Solution :

The output of Query2, Query3 and Query4 will be identical. Query1 may produce duplicate rows. But rowset produced by all of them will be same.

Table enrolled

student course --------------- abc c1 cs_2006 c1 abc c2 pqr c1 Table paid student amount ----------------- abc 20000 cs_2006 10000 rst 10000

Output of Query 1

abc

abc

cs_2006

Output of Query 2

abc

cs_2006

Question 11

A disk seek takes 4ms, disk data transfer bandwidth is 300 MB/s and checking a tuple to see if amount is greater than x takes 10 micro-seconds. Which of the following statements is correct?

.

Correct answer is :C

Solution :

Assuming that large enough memory is available for all data needed. Both plans need to load both tables courses and enrolled. So disk access time is same for both plans.

Plan 2 does lesser number of comparisons compared to plan 1.

1) Join operation will require more comparisons as the second table will have more rows in plan 2 compared to plan 1.

2) The joined table of two tables will will have more rows, so more comparisons are needed to find amounts greater than x.

Question 12

AB -> CD, AF -> D, DE -> F, C -> G , F -> E, G -> A

Which one of the following options is false?

.

Correct answer is :C

Solution :

Closure of AF or AF+ = {ADEF}, closure of AF doesn’t contain C and G.

Option (D) also looks correct. AB+ = {ABCDG}, closure of AB doesn’t contain F.