# GATE2002-17

2.4k views
1. The following table refers to search items for a key in $B$-trees and $B^+$ trees.
$$\begin{array}{|ll|ll|} \hline & \textbf {B-tree} & & \textbf {B}^+\text{-tree} \\\hline \text{Successful search } &\text{ Unsuccessful search} &\text{Successful search } & \text{ Unsuccessful search} \\\hline \text{X_1} &\text{X_2} & \text{X_3} &\text{X_4}\\\hline \end{array}$$
A successful search means that the key exists in the database and unsuccessful means that it is not present in the database. Each of the entries $X_1, X_2, X_3$ and $X_4$ can have a value of either Constant or Variable. Constant means that the search time is the same, independent of the specific key value, where variable means that it is dependent on the specific key value chosen for the search.
Give the correct values for the entries $X_1, X_2, X_3$ and $X_4$ (for example $X_1 = \text{Constant},$ $X_2 = \text{Constant }, X_3 = \text{Constant}, X_4=\text{ Constant})$
2. Relation $R(A,B)$ has the following view defined on it:
CREATE VIEW V AS
(SELECT R1.A,R2.B
FROM R AS R1, R as R2
WHERE R1.B=R2.A)
1. The current contents of relation $R$ are shown below. What are the contents of the view $V$?
$$\begin{array}{|c|c|} \hline \text {A} & \text {B} \\\hline \text {1} & \text{2} \\ \text{2}& \text{3} \\ \text{2} &\text{4}\\ \text {4} & \text{5} \\ \text{6}& \text{7} \\ \text{6} &\text{8} \\ \text{9} & \text{10}\\\hline \end{array}$$
2. The tuples $(2,11)$ and $(11,6)$ are now inserted into $R.$ What are the additional tuples that are inserted in $V$?

edited
2

Notice -> Here a successful search means that the key exists. They are not talking about data. In case of data answer may change because in B+Tree presence of key does not always grantee that corresponding data will be there.

For A)

X1 = Variable (Key can be found @ Internal nodes at various levels)
X2 = Constant
X3 = Variable, We need to just check where key is present/absent, not to access Data. (A successful search means that the key exists in the database and unsuccessful means that it is not present in the database.) So Variable
X4 = Constant

For Part B) i) Write down two copies of the same table for comparison side by side. Just map B of first to A of the second copy. Those matching tuples take A of first table & B of seconds.

Content of View A

$$\begin{array}{|c|c|} \hline \textbf {A} & \textbf {B} \\\hline \text {1} & \text{3} \\\hline \text{1} & \text{4} \\\hline \text{2} & \text{5} \\\hline \end{array}$$
For Part B) ii)

Additional tuples getting inserted:

$$\begin{array}{|c|c|} \hline \textbf {A} & \textbf {B} \\\hline \text {11} & \text{7} \\\hline \text{11} & \text{8} \\\hline \text{2} & \text{6} \\\hline \text{1} & \text{11} \\\hline \end{array}$$

edited
3
@akash , please check once

contents of view is

1 , 3

1, 4

2, 5

and in additional tuples

1 , 11  also should present.
0
Updated @pramod.

First one was typo, Second I missed it. You are right !
10
X3 is variable, bcoz once we get all the way down to leaf, now it all depends on key value, where it is present in the leaf.
If a leaf contains 'd' keys then in worst case we may need to check all d keys and last key will match.

right ?
9

For Xwe are searching for a node in B+ tree. Search key can be present in the internal nodes or in leaf nodes. So search time is variable. And for X4 (unsuccessful search) we will traverse till leaf node always. So constant.

right?

0
if we are searching for a data value(not just key) then $X3$ will be constant right?
0
@reena

yes i think because record pointers available at leaf itself. we can access data value by going to the leaf only which makesconstant time
0
yes x3 should be constant, because search will always end at leaf node only.

and once ypu are at leaf node the time of  searching with in the leaf node is d only...so whatever the value it maybe, search time is same; hence constant!
1

Even if we want to search for data values

We always have to go to leaf node and within leaf there can be 'd' key so searching in those 'd' keys  doesn't make it variable ???

0

@ suppose data is asked then in case of B+tree ,we would have to go till leaf that will be "fixed " and there in leaf it could be any of   'd' keys and we know 'd', is fixed that is the order we would know firsthand,so so worst case time if fixed it does not depend on key value which is searched.

1 vote
For A) variable(if the key is found in any internal node),constant(always logN),variable,constant
0

x1= variable bcz B tree depends on where the  data pointer is present,

x2= constant i.e data is not present

x3= Constant,data is presnt in leaf level ,so for successful  search it will be constant as constant means search time is same and independent of specific key value ,, .i.e we have to access leaf level independent of its vaue,

where as X4 will variable bcz its unsuccessful so it  depends on key value
13

"A successful search means that the key exists in the database" which means if the in the B+tree search is successful in any internal node that is enough you do not have to go to the leaf level...that suggests it is variable. And for the unsuccessful search you have to traverse the leaf level to to decide whether it is there or not...internal nodes do not contain all the key that are present in the leaf level.

0
Yes for safe side it need to be varaible only . If the key what we are searching is present in the internal node then its fine but if you not you would have to traverse down to the leaf node and possible do linear searching there with the help of sibbling pointer . SO it should be varaible only
0

But in Unseccesful search ,after reaching leaf node ..there may be d keys where d is Order(Leaf)

So in worst case we have to search over entire leaf node

But for some cases we immediately found that key is not present

eg Leaf <1,3,5,7,9,15>

For search(2) and search(11) is time required same ??

2
if the search time depends upon

1) comparission of numbers ===> it is variable

2) No.of Blocks ===> it is constant
0
Then what should be answer in exam
0
From the question, i didn't get on which they are interested,

i will go with No.of Blocks, rather than no.of comparissions, due to at a time we will fetch a block itself. But it is not a rule, it is depend upon your opinion
0

The reason for Successful search in B+ tree Variable (X3)..is The search key we want may be  in Internal node or it may be in leaf ..as all keys are not at two places only some ...so number of blocks are varying for successful search in B+ tree

But check sachin sir comment on this

X3 is variable, bcoz once we get all the way down to leaf, now it all depends on key value, where it is present in the leaf.
If a leaf contains 'd' keys then in worst case we may need to check all d keys and last key will match.

right ?

0
as i commented, it's their ( sachin sir ) opinion, that questioner interested in no.of comparissions.

Unfortunately, in successful search those two opinions are matched :)

## Related questions

1
5.6k views
A $B^+$ - tree index is to be built on the Name attribute of the relation STUDENT. Assume that all the student names are of length $8$ bytes, disk blocks are of size $512$ bytes, and index pointers are of size $4$ bytes. Given the scenario, what would be the best choice of the degree (i.e. number of pointers per node) of the $B^+$ - tree? $16$ $42$ $43$ $44$
For relation R=(L, M, N, O, P), the following dependencies hold: $M \rightarrow O,$ $NO \rightarrow P,$ $P \rightarrow L$ and $L \rightarrow MN$ R is decomposed into R1 = (L, M, N, P) and R2 = (M, O). Is the above ... . Is the above decomposition dependency-preserving? If not, list all the dependencies that are not preserved. What is the highest normal form satisfied by the above decomposition?
A university placement center maintains a relational database of companies that interview students on campus and make job offers to those successful in the interview. The schema of the database is given below: ... $five$ students were offered jobs, the name of the degree and the average offered salary of students in this degree program.