GATE CSE 2011 | Question: 39

Question

Consider a relational table $r$ with sufficient number of records, having attributes $A_1, A_2, \dots ,A_n$ and let $1 \leq p \leq n$. Two queries $Q1$ and $Q2$ are given below.

• $Q1: \pi_{A_1, \dots ,A_p} \left(\sigma_{A_p=c}\left(r\right)\right)$ where $c$ is a constant
• $Q2: \pi_{A_1, \dots ,A_p} \left(\sigma_{c_1 \leq A_p \leq c_2}\left(r\right)\right)$ where $c_1$ and $c_2$ are constants.

The database can be configured to do ordered indexing on $A_p$ or hashing on $A_p$. Which of the following statements is TRUE?

• A. Ordered indexing will always outperform hashing for both queries
• B. Hashing will always outperform ordered indexing for both queries
• C. Hashing will outperform ordered indexing on $Q1$, but not on $Q2$
• D. Hashing will outperform ordered indexing on $Q2$, but not on $Q1$

Comments

Useful link: http://www.cs.sfu.ca/CourseCentral/354/zaiane/material/notes/Chapter11/node21.html

Answer 1

OPENING A DISCUSSION THREAD, please give your inputs.

Saying

Hashing works well on the 'equal' queries, while ordered indexing works well better on range queries too.

is acceptable if we know that the query is on the primary key. Isn’t it?

Because suppose if we have multiple rows with $A_{p=c}$, considering that $A_{p}$ is a non-key attribute then this is equivalent to ordering on a non-key attribute i.e. clustered indexing. Now if we have multiple rows with $A_{p=c}$ then it means that it is spread over multiple blocks of data, and in case of hashing this will lead to multiple block access.

Whereas clustered indexing on the non-key attribute $A_{p}$ will have O(log n) complexity. And i would argue in a similar fashion for the range query.

Now coming to this question, we don’t know whether $A_{p}$ is a key or non-key attribute. Therefore considering the worst-case scenario, indexing must be preferred for both the queries because of low average lookup-time.

@Arjun sir, @Sachin Mittal 1 sir, @Deepakk Poonia (Dee) sir,@ dd sir, @ gatecse, @ Shaik Masthan sir please comment if possible.

Answer 2

Answer: (C)

Explanation: If record are accessed for a particular value from table, hashing will do better. If records are accessed in a range of values, ordered indexing will perform better. See this for more details.