GATE CS Mastery
Cheat sheets

GATE CS 2011 · Databases

Question 39

MCQPrinted as CS Q.392 marksWrong answer: −2/3Easy (estimate)

Question

Consider a relational table rr with sufficient number of records, having attributes A1,A2,…,AnA_1, A_2, \dots, A_n and let 1≤p≤n1 \le p \le n. Two queries Q1 and Q2 are given below.

Q1: ΠA1,…,Ak(σAp=c(r))\Pi_{A_1, \dots, A_k} (\sigma_{A_p = c}(r)) where cc is a constant

Q2: ΠA1,…,Ak(σc1≤Ap≤c2(r))\Pi_{A_1, \dots, A_k} (\sigma_{c_1 \le A_p \le c_2}(r)) where c1c_1 and c2c_2 are constants

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

Choose one option
Official answer and solution
Official answer
C
From
Official GATE 2011 answer key

Solution

Compare hash indexing versus ordered (B-tree) indexing on equality and range predicates.

  1. Query Q1 involves point equality selection σAp=c(r)\sigma_{A_p = c}(r). Hash indexing computes the hash bucket directly in O(1)O(1) average time, outperforming ordered index traversals which take O(log⁡N)O(\log N) time.
  1. Query Q2 involves range selection σc1≤Ap≤c2(r)\sigma_{c_1 \le A_p \le c_2}(r). In an ordered index (such as a B+ tree), keys are stored in sorted order with linked leaf pages, enabling efficient range scans. In contrast, standard hashing distributes keys pseudo-randomly across buckets with no ordering, making range queries require scanning the entire table.
  1. Consequently, hashing outperforms ordered indexing on Q1, but not on Q2.
Final answer

C

The answer is the one in the official GATE answer key. The solution is this site's own explanation.

Source

Paper
GATE 2011 Computer Science and Information Technology (CS)
Question
39 of 65, printed as CS Q.39
Section
Computer Science and Information Technology

Report an error in this question

GATE questions are the work of the organising institutes. This site is independent and is not affiliated with them.