The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+15 votes
879 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?
asked in Databases by Veteran (69k points) | 879 views

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.

2 Answers

+14 votes
Best answer

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)

Additional tuples getting inserted ->

A B
11 7
11 8
2 6
1 11


 

answered by Veteran (49.5k points)
edited by
@akash , please check once

contents of view is

1 , 3

1, 4

2, 5

and in additional tuples

1 , 11  also should present.
Updated @pramod.

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

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?  

if we are searching for a data value(not just key) then $X3$ will be constant right?
@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
+1 vote
For A) variable(if the key is found in any internal node),constant(always logN),variable,constant
answered by Boss (6.9k points)
Answer for A)

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

"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.

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


Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

33,705 questions
40,252 answers
114,340 comments
38,860 users