edited by
5,599 views
33 votes
33 votes
  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 by

2 Answers

Best answer
33 votes
33 votes

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 by
3 votes
3 votes
For A) variable(if the key is found in any internal node),constant(always logN),variable,constant

Related questions