Q$2.[59$ marks$]$ You are given the following three relations in a university database as below

$($with primary keys underlined$)$:

INSTRUCTOR $($Id Name, DeptName, Salary$)$

COURSE $($Cid$,$ Name$)$

TEACHES $($Id$,$ Cid, Semester, Year$)$

The relation INSTRUCTOR has $500$ tuples, and $20$ tuples fit into one block; the relation COURSE

has $200$ tuples, and $20$ tuples fit into one block; the relation TEACHES has $500$ tuples, and $50$

tuples fit into one block. All records are sorted in ascending order of the primary keys of the table

on disk $($TEACHES is first sorted on Id$,$ and then on Cid if two records have the same Id$).$ Assume

that the INSTRUCTOR Id ranges from $1$ to $500,$ COURSE Cid from $1$ to $200.$ It is assumed that a

relation is stored on disk consecutively. Please answer the following questions and show your

calculations clearly.

$($a$)[8$ marks$]$ Answer the following questions and elaborate on your answers.

i$.[4$ marks$]$ Assume that a relation is stored on disk consecutively, how many disk

seeks do we need if we read the entire relation, and read the relation from a certain

block, respectively?

ii$.[4$ marks$]$ Assume that relation INSTRUCTOR has a primary index A and a secondary

index B$.$ On what possible search keys are A and B built, respectively?

$($b$)[30$ marks$]$ Answer the following questions and show your calculations clearly.

i$.[10$ marks$]$ Consider the following SQL query:

select $*$ from COURSE where Name$=$'Data Structure' $or$ Cid $=50$

Assume that relation COURSE has a B$+-$tree index of height $5$ on the Cid attribute.

Further assume that the Cid of COURSE are integers between $1$ to $200.$ What are the

numbers of disk seeks and block transfers associated with the SQL query if we use

the B$+-$tree index? What are the numbers if we do not use the B$+-$tree index?

Should we use the B$+-$tree index? Explain briefly.

ii$.[10$ marks$]$ Consider the following SQL query:

select $*$ from INSTRUCTOR where Name $=$ 'Jack'

If we perform linear search, what are the numbers of disk seeks and block transfers

associated with the SQL query?

iii. $[10$ marks$]$ Consider the following SQL query.

select $*$ from INSTRUCTOR where Id $>100$

Assume that the Id of relation INSTRUCTOR are integers between $1$ and $500.$ Further

assume that INSTRUCTOR has a B$+-$tree index of height $10$ on the Id attribute. If we

use the B$+-$tree for the query, what are the numbers of disk seeks and block transfers

associated with the SQL query?

$($c$)[8$ marks$]$ Assume that relation INSTRCUTOR has a B$+-$tree index of height $3$ on the

DeptName attribute, and a B$+-$tree index of height $4$ on the Name attribute. Further

assume that there are $30$ instructors from the Computer Science Department.

i$.[4$ marks$]$ Is the $B^{+}-$tree on Name a primary or secondary index? Explain briefly.

ii$.[4$ marks$]$ Consider the following SQL query:

select $*$ from INSTRUCTOR where DeptName $=$ 'Computer Science'

If we use the $B^{+}-$tree on the DeptName attribute for the query, what are the numbers

of disk seeks and block transfers associated with the SQL query? The number of

accesses to the blocks that contain pointers to data records in the data file is ignored:

$($d$)[13$ marks$]$ Consider the following SQL query performing the join

operation:

select $*$ from INSTRUCTOR, TEACHES where

INSTRUCTOR.Id $=$

TEACHES.Id

i$.[9$ marks$]$ Assume that $12$ blocks are allocated to the memory buffer. The query is

implemented by nested$-$loop join. Which of the relations should be the inner relation

that leads to a smaller number of seeks and block transfers? Explain your answer by

comparing the two cases with calculating the number of seeks and block transfers,

when different relations are chosen as the inner relation.

ii$.[4$ marks$]$ Assume that INSTRUCTOR has a B$+-$tree index of height $3$ on the Id

attribute. The query is implemented by indexed nested$-$loop join with TEACHES as

the outer relation. What are the numbers of disk seeks and block transfers?