GATE IT 2007 | Question: 68

Question

Consider the following relation schemas :

• b-Schema = (b-name, b-city, assets)
• a-Schema = (a-num, b-name, bal)
• d-Schema = (c-name, a-number)

Let branch, account and depositor be respectively instances of the above schemas. Assume that account and depositor relations are much bigger than the branch relation.

Consider the following query:

П_c-name (σ_{b-city = "Agra" ⋀ bal < 0} (branch ⋈ (account ⋈ depositor)

Which one of the following queries is the most efficient version of the above query ?

• A. П_c-name (σ_{bal < 0} (σ_{b-city = "Agra"} branch ⋈ account) ⋈ depositor)
• B. П_c-name (σ_{b-city = "Agra"} branch ⋈ (σ_{bal < 0} account ⋈ depositor))
• C. П_c-name ((σ_{b-city = "Agra"} branch ⋈ σ_{b-city = "Agra"} ⋀  _{bal < 0} account) ⋈ depositor)
• D. П_c-name (σ_{b-city = "Agra"} branch ⋈ (σ_{b-city = "Agra"} ⋀  _{bal < 0} account ⋈ depositor))

Comments

option (c) and (d) are clearly invalid as they use b-city as an attribute of account schema in the query which is not present in account schema.

and for finding correct between a and b

consider the case where all account holders have the negative balance.(worst case)

---

Here for C and D both we are not doing a conditional join as we use the selection operator along with the join which is not the syntax for theta/conditiona join.

 

---

early use of selection :)

Answer 1

It should be A. As in B we are doing a join between two massive table whereas in A we are doing join between relatively smaller table and larger one and the output that this inner table gives (which is smaller in comparison to joins that we are doing in B) is used for join with depositer table with the selection condition.

Options C and D are invalid as there is no b-city column in a-Schema.

---

Lets see in detail. Let there be 100 different branches. Say about $10$% of accounts are below $0$. Also, let there be $10,000$ accounts in a branch amounting to $1,000,000$ total accounts. A customer can have multiple accounts, so let there be on average $2$ accounts per customer. So, this amounts to $2,000,000$ total entries in depositor table. Lets assume these assumptions are true for all the branches. So, now lets evaluate options A and B.

1. All the accounts in Agra branch, filter by positive balance, and then depositor details of them. So, 

• Get branch name from branch table after processing $100$ records
• Filter $10,000$ accounts after processing $1,000,000$ accounts belonging to Agra
• Filter 1000 accounts after processing 10,000 accounts for positive balance
• Get $500$ depositor details after processing $2,000,000$ entries for the given $1000$ accounts (assuming $1$ customer having $2$ accounts). So, totally this amounts to $2,000,000,000$ record processing.
• So totally $\approx$ 2 billion records needs processing.

2. All the positive balance accounts are found first, and then those in Agra are found.

• Filter $100,000$ accounts after processing $1,000,000$ accounts having positive balance
• Find the deposito details of these accounts. So, $100,000 $*$ 2,000,000$ records need processing and this is a much larger value than for query A. Even if we reduce the percentage of positive balance ($10$ we assumed) the record processing of query A will also get reduced by same rate. So, overall query A is much better than query B.

Comments

@Godlike Both queries A and B are correct but A is more optimized as branches are less than accounts, so saves lot of time .

---

I believe there is a bit of technical error in the example that you have demonstrated. Assuming that each customer owns only single accounts (i.e., there are no joint accounts in the accounts instance, which does seem to be the case when you state ‘Get \(500\) depositor details after processing \(2,000,000\) entries for the given \(1000\) accounts’), and that on average there are \(2\) accounts per customer, we have a one-to-many mapping from the depositor instance to the accounts instance. So, to have \(1,000,000\) accounts in the accounts instance, we should actually have \(500,000\) entries in depositor instance on average, and not \(2,000,000\), right? And if that’s the case, then option A requires a total of 500 million record processing on average, and option B requires at least a total of 50 thousand million record processing on average, right?

---

Thanks

Answer 2

B) as  b  is very small compared to a and d which is  also taken in account also from the fact that there is a condition  (σb-city = "Agra" branch which already filter  city as agra making it small  and before that σbal < 0 account ⋈ depositor filter  and give selected tables so ⋈  between them will give same result and better one.
Please correct If Not also 3 and 4 are wrong as σb-city = "Agra" ⋀  bal < 0 account ⋈ depositor selects city from account ⋈ depositor which is not in either Schemas.

Comments

Yes. That is correct. We should always do select before join to avoid unnecessary tuples being considered for join.

(For an SQL query this is not strictly required as most DBMS will rearrange the query to make it efficient)

---

Thanks  for verifying :)

---

Sorry I missed this sentence "account and depositor relations are much bigger than the branch relation"

That makes A the best answer. 

---

I also find this answer correct, as bal<0 is selecting on bigger table first

Answer 3

I guess the most efficient one is this one:

$\prod_{c\_name}(((\sigma_{b\_city="Agra"}branch)\bowtie(\sigma_{bal<0}account))\bowtie depositor)$
 

though it is not given in the options.

Am I right @Arjun sir?

Comments

Actually it won't make much of a difference to query A. Because, we first filter positive balance account here and then find those in Agra. In query A this is done in reverse. So, it matters if number of positive balance accounts are very few. You can see the accepted anaswer now..

---

I was thinking structurally most correct query for being most efficient without considering anything about what the current instance of relation may contain.

---

Not really. You are first filtering based on "balance" and natural join first filter on the join condition which is "branch" first in option A. So, which one is better depends on the instance.

---

which one is better depends on the instance

Q. Does that means that option A can be more efficient than the one I put above in some relation instances?

I think it will not be. And the one I put above will always be better than others. I followed one fact that I believe is correct: "Whenever there is a condition with constant, apply them first before performing joins, so that join computation will be smaller". In option A, account is joined as it is, without first applying condition (bal<0), which is what I tried to do.
(May be we should not waste time if this is trivial, but still was thinking above one will perform better than in options in all cases)

---

No it is not trivial. Intuitively that looks correct. But may not work always. I had given an example in the accepted answer. Your query closely follows the option A, but lets analyze it more

1. All the positive balance accounts in Agra branch and then depositor details of them. So, 

• Get branch name from branch table after processing 100 records
• Filter 100,000 accounts with positive balance after processing 1,000,000 accounts b
• Filter 1000 accounts after processing 100,000 accounts belonging to Agra
• Now, it follows query A.

So, totally we processed, 100 + 1,000,000 + 100,000 records.

In query A we process, 100 + 1,000,000 + 10,000 records.

The difference is negligible, still numerically Query A performed better. But this is just because of the assumptions I used for the instance.

---

Didnt get your explanation exactly. So gave some more time to it. I tried using your number wherever possible and came up with this. Still feels option A will be not efficient than the query I suggested in any situation.

---

In option A, the select of branch = "Agra" is done before join is performed. Your braces are not correct.

---

ohhhh right. Now I have made corrections and I can see what you were saying:

However, now I want to ask will option A will always perform better than my query.
Also want to generalize this. My query follows approach of "applying all constant based filters first before performing any join". While option A query follows below approach:
(I tried to figure out the idea behind this approach. May not be completely correct. But please correct me if I am wrong)

• apply constant based filters on next smallest table one by one to make them even smaller
• each time after applying constant based filter on next smallest table, join the result with next biggest table (if it makes sense to perform such join in order to obtain the desired output tuples)
• after performing join with next biggest table, apply constant based filter on it (if it makes sense to perform such join in order to obtain the desired output tuples)

So does the query 1 approach above always generate the better performance than the approach of my query?

Initially I felt yes that query 1 approach will always perform better than my query approach. But now I feel this completely depends on the relation instance and size of output of filters applied. Am I right with all that?

---

Yes, as I told query A wont always perform better than your one - that might be why your query is not among the choices. When IIT profs make questions, usually answer is very easy to pick as there won't be much ambiguity. If your query was added to the options, we cannot easily pick an answer.

Now, optimizing query is not a simple task. So, I don't think there exist an algorithm like you said which works for all instances and gives the best query execution plan. Usually one has to see how a query is performing on an instance and thus optimize it further.

---

billion thanks sir for confirmation

---

Great explanation @Arjun Sir

Answer 4

When optimizing relational algebra expressions, the goal is not only logical correctness but also minimization of intermediate result sizes. This is especially critical when one relation is small and others are large. 

Instance:

$$
\texttt{branch:}
\quad
\begin{array}{|c|c|c|}
\hline
\texttt{b-name} & \texttt{b-city} & \texttt{assets} \\
\hline
B1 & \texttt{Agra} & 500 \\
B2 & \texttt{Delhi} & 600 \\
B3 & \texttt{Mumbai} & 700 \\
\hline
\end{array}
$$

$$
\texttt{account:}
\quad
\begin{array}{|c|c|c|}
\hline
\texttt{a-num} & \texttt{b-name} & \texttt{bal} \\
\hline
A1 & B1 & -100 \\
A2 & B1 & 200 \\
A3 & B1 & 300 \\
A4 & B2 & -50 \\
A5 & B2 & -60 \\
A6 & B3 & -70 \\
\hline
\end{array}
$$

$$
\texttt{depositor:}
\quad
\begin{array}{|c|c|}
\hline
\texttt{c-name} & \texttt{a-num} \\
\hline
C1 & A1 \\
C2 & A2 \\
C3 & A3 \\
C4 & A4 \\
C5 & A5 \\
C6 & A6 \\
\hline
\end{array}
$$

Correct result: Only account $A1$ is in "Agra" and has $\texttt{bal < 0}$ → output: $\{C1\}$.

Now evaluate all options.

---

Option A:  
$$
\Pi_{\texttt{c-name}} \left( \sigma_{\texttt{bal < 0}} \left( \sigma_{\texttt{b-city = "Agra"}}(\texttt{branch}) \bowtie \texttt{account} \right) \bowtie \texttt{depositor} \right)
$$

Steps:

1. $\sigma_{\texttt{b-city="Agra"}}(\texttt{branch}) = \{(B1, \texttt{Agra}, 500)\}$
2. Join with $\texttt{account}$ → accounts at B1: $A1, A2, A3$ → 3 tuples
3. $\sigma_{\texttt{bal < 0}}$ → only $A1$ → 1 tuple
4. Join with $\texttt{depositor}$ → $C1$
5. Project → $\{C1\}$

Correct Result. Peak intermediate size: 3 tuples (after step 2).

---

Option B:  
$$
\Pi_{\texttt{c-name}} \left( \sigma_{\texttt{b-city = "Agra"}}(\texttt{branch}) \bowtie \left( \sigma_{\texttt{bal < 0}}(\texttt{account}) \bowtie \texttt{depositor} \right) \right)
$$

Steps:

1. $\sigma_{\texttt{bal < 0}}(\texttt{account}) = \{A1, A4, A5, A6\}$ → 4 tuples
2. Join with $\texttt{depositor}$ → $\{C1, C4, C5, C6\}$ → 4 tuples
3. $\sigma_{\texttt{b-city="Agra"}}(\texttt{branch}) = \{(B1, \texttt{Agra}, 500)\}$
4. Final join on $\texttt{b-name}$: only $A1$ (B1) matches → $C1$
5. Project → $\{C1\}$

Correct Result:  Peak intermediate size: 4 tuples (after step 2).

Even in this tiny instance, Option B processes more data: 4 vs. 3 tuples. The gap widens dramatically at scale.

---

Option C:  
$$
\Pi_{\texttt{c-name}} \left( \left( \sigma_{\texttt{b-city = "Agra"}}(\texttt{branch}) \bowtie \sigma_{\texttt{b-city = "Agra"} \land \texttt{bal < 0}}(\texttt{account}) \right) \bowtie \texttt{depositor} \right)
$$

Selection $\sigma_{\texttt{b-city = "Agra"} \land \texttt{bal < 0}}(\texttt{account})$ is invalid: $\texttt{account}$ has no $\texttt{b-city}$.

Semantically incorrect.

---

Option D:  
$$
\Pi_{\texttt{c-name}} \left( \sigma_{\texttt{b-city = "Agra"}}(\texttt{branch}) \bowtie \left( \sigma_{\texttt{b-city = "Agra"} \land \texttt{bal < 0}}(\texttt{account}) \bowtie \texttt{depositor} \right) \right)
$$

Same error: $\texttt{b-city}$ not in $\texttt{account}$.

Semantically incorrect.

---

Scalability Insight from This Instance

In the example:

• Agra branch has 3 accounts,
• But 4 accounts in total have $\texttt{bal < 0}$ (including 3 outside Agra).

Thus:

• Option A never sees the 3 non-Agra negative accounts,
• Option B processes all 4, then discards 3 in the final join.

Now scale up:

• Suppose 100 branches, 1,000,000 accounts,
• Agra: 10,000 accounts,
• Negative balance: 100,000 accounts (only 1,000 in Agra).

Then:

• Option A intermediate after join: 10,000 → after filter: 1,000
• Option B intermediate after filter: 100,000 → after depositor join: ~200,000
• The 20$\times$ blowup in Option B arises directly from the pattern visible even in our small instance.

Therefore

• Options C and D are invalid due to attribute misuse.
• Options A and B are correct, but Option A minimizes intermediate results by using the small $\texttt{branch}$ relation to restrict $\texttt{account}$ early.
• The constructed instance explicitly shows that Option B processes more tuples even at small scale, and this difference scales linearly with data size.

Therefore, Option A is the most efficient.

Answer 5

As the conditional expression contains the comparison of attributes with constants so they can be applied independently  for filtering out some tuples  before performing the join operation over the relations because this will reduce the relation to smaller ones and join can be easily on smaller relations.

Given query is inefficient as join is performed before the selecting the tuples from the relation so we have to select the efficient query from options.

Option A have condition ( bal < 0 ) which is performed after performing join of branch and account So, inefficient.

Option C have condition ( b-city = 'agra' ) with account relation but b-city is not there in account. So, inefficient.

Option D is nearly same as C, so inefficient.

Option B is the most efficient one as filtering of tuples is performed before joining.

Therefore, Option B is correct.

Comments

Account & Depositor much bigger than Branch. B is very costly, A is answer !