1.2k views
1. The following table refers to search items for a key in $B$-trees and $B^+$ trees.
 B−tree B+−tree Successful search Unsuccessful search Successful search Unsuccessful search X1 X2 X3 X4
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?
 A B 1 2 2 4 6 6 9 2 3 4 5 7 8 10
2. The tuples (2,11) and (11,6) are now inserted into R. What are the additional tuples that are inserted in V?
edited | 1.2k views
0

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

 A B 1 3 1 4 2 5

For Part B) ii)

 A B $11$ $7$ $11$ $8$ $2$ $6$ $1$ $11$
edited
+3

contents of view is

1 , 3

1, 4

2, 5

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

First one was typo, Second I missed it. You are right !
+2
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 ?
+2

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 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
+9

"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