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

---

@gatecse Sir , is it safe to assume that for the 2nd query that is Q2 , the file is ordered on the attribute Ap ??

---

@Thadymademe No, that is not a safe assumption, and more importantly, you don't need to make it to solve the problem.

The problem guarantees ordered indexing, but it says nothing about the physical ordering of the data file. You can have an ordered index on a completely unordered data file (a non-clustered or secondary index).

---

Hashing will outperform ordered indexing if we do point search.
However, Hashing will not be beneficial if we do range search.

Answer 1

(C) Hashing works well on the 'equal' queries, while ordered indexing works well better on range queries too. For ex consider B+ Tree, once you have searched a key in B+ tree , you can find range of values via the block pointers pointing to another block of values on the leaf node level.

Comments

Hope it helps a bit.

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.

https://www.geeksforgeeks.org/gate-gate-cs-2011-question-39/

---

Is Hashing there in current GATE syllabus??

---

@amar100 Yes it is, but dont worry, dont need to study it separately, Hashing learnt in Data structures is sufficient 

Answer 2

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

it explains with the same example

Comments

@vijju532 Thanx !

Answer 3

Hashing is generally better at retrieving records having a specified value of the key.

If range queries are common, ordered indices are to be preferred.

https://www.cse.iitb.ac.in/~sudarsha/db-book/slide-dir/ch12.pdf

Comments

Indexing perform better in range queries like in B+-trees.

Answer 4

Typically, ordered indexing is used unless it is known in advance that range queries will be infrequent, in which case hashing is used like Q2:πA1,…,Ap(σc1≤Ap≤c2(r)) . Hash organizations are particularly useful for temporary files created during query processing, if lookups on a key value are required and no ranges queries will be performed like Q1:πA1,…,Ap(σAp=c(r)).

c is correct

Answer 5

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 6

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.