GATE CS 2011 Q.32 (CS Q.32): SQL Queries and Integrity Constraints

Consider a database table $T$ containing two columns $X$ and $Y$ each of type integer. After the creation of the table, one record $(X=1, Y=1)$ is inserted in the table.

Let $MX$ and $MY$ denote the respective maximum values of $X$ and $Y$ among all records in the table at any point in time. Using $MX$ and $MY$ , new records are inserted in the table 128 times with $X$ and $Y$ values being $MX+1$ , $2*MY+1$ respectively. It may be noted that each time after the insertion, values of $MX$ and $MY$ change.

What will be the output of the following SQL query after the steps mentioned above are carried out?

SELECT Y FROM T WHERE X=7;

127

255

129

257

Official answer and solution

Official answer: A
From: Official GATE 2011 answer key

Solution

Formulate recurrences for the sequence of inserted records and compute the value of Y when X equals 7.

The table initially contains the single record $(X_1 = 1, Y_1 = 1)$ . Thus initially $MX = 1, MY = 1$ .

Each subsequent insertion creates a record with $X_{k} = MX + 1 = X_{k-1} + 1$ and $Y_k = 2 \times MY + 1 = 2 Y_{k-1} + 1$ .

Solving the recurrence $Y_k = 2 Y_{k-1} + 1$ with $Y_1 = 1$ :

$k = 1$ : $X = 1, Y = 1 = 2^1 - 1$
$k = 2$ : $X = 2, Y = 2(1) + 1 = 3 = 2^2 - 1$
$k = 3$ : $X = 3, Y = 2(3) + 1 = 7 = 2^3 - 1$
In general, for record $k$ , $X_k = k$ and $Y_k = 2^k - 1$ .

For the query WHERE X = 7, we have $k = 7$ :

Y = 2^7 - 1 = 128 - 1 = 127

Final answer

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: 32 of 65, printed as CS Q.32
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.

Question

Solution

Source