GATE CSE 2004 | Question: 51

Question

Consider the relation Student (name, sex, marks), where the primary key is shown underlined, pertaining to students in a class that has at least one boy and one girl. What does the following relational algebra expression produce? (Note: $\rho$ is the rename operator).

$\displaystyle \pi_{name} \{\sigma_{sex=female} (\text{Student}) \} - \pi_{name} (\text{Student}\bowtie _{(sex=female \wedge x=male \wedge marks \leq m)} \rho_{n, x, m}(\text{Student}))$

• A. names of girl students with the highest marks
• B. names of girl students with more marks than some boy student
• C. names of girl students with marks not less than some boy student
• D. names of girl students with more marks than all the boy students

Comments

Dont use AI bro

 

---

et's analyze the given relational algebra expression step-by-step:

1. First Term:

   $$\pi_{\text{name}}\{\sigma_{\text{sex}=\text{female}}(\text{Student})\}$$

   This produces a relation containing the names of all female (girl) students.

2. Second Term:

   $$\pi_{\text{name}}\left(\text{Student} \bowtie_{(\text{sex}=\text{female} \wedge x=\text{male} \wedge \text{marks} \le m)} \rho_{n, x, m}(\text{Student})\right)$$

   • $\rho_{n, x, m}(\text{Student})$ renames the attributes $(\text{name}, \text{sex}, \text{marks})$ of the $\text{Student}$ relation to $(n, x, m)$.

   • The theta-join $(\bowtie)$ pairs each student $(\text{name}, \text{sex}, \text{marks})$ with each student $(n, x, m)$ such that:

     • The first student is female ($\text{sex}=\text{female}$).

     • The second student is male ($x=\text{male}$).

     • The female student's marks are less than or equal to the male student's marks ($\text{marks} \le m$).

   • Projecting $\pi_{\text{name}}$ from this join yields the names of girl students who have marks less than or equal to at least one boy student (i.e., NOT strictly greater than all boys).

3. Set Difference (First Term $-$ Second Term):

   • This subtracts the set of girls whose marks are $\le$ some boy's marks from the set of all girls.

   • What remains are the names of girl students whose marks are strictly greater than ($>$) all boy students' marks.

Therefore, the relational algebra expression produces the names of girl students with more marks than all the boy students.

Correct Answer: D. names of girl students with more marks than all the boy students

---

for option c:
if some girl have same marks as highest marks of boys, then her name will come into the output list, which is wrong according to the query,
if some girl even have same marks as some boy then her name should not be on the list.

so that's why option c is wrong,

it will be correct if it's written that : names of girl students with marks not less than **or equal**  to some boy student.

Answer 1

OPTION : (D)

​The given query states the following conditions:

$$\boxed{\begin{align}\text{Sex} &= F \land \\ x&= M \land \\ \text{Marks} &\leq m \end{align}} \to (1)$$

Let the relation be $\text{Student} (\text{Name}, \text{Sex}, \text{Marks})$ $$\begin{array} {c c c} \hline \text{Name} & \text{Sex} & \text{Marks} \\\hline S1 & F & 30 \\\hline S2 & F & 10 \\\hline S3 & M & 20 \end{array}$$ $\text{Student} (\text{Name}, \text{Sex}, \text{Marks})$ Relation is renamed as $\text{Student}(n, x, m).$

Taking the cross product of the relations

$$\begin{array} {c c c} \hline \text{No.}  & \text{Name} & \text{Sex} & \text{Marks} & n & x & m  \\\hline 1 & S1 & F & 30 & S1 & F & 30 \\\hline 2 & S1 & F & 30 & S2 & F & 10 \\\hline 3 & S1 & F & 30 & S3 & M & 20 \\\hline  4 & S2 & F & 10 & S1 & F & 30 \\\hline 5 & S2 & F & 10 & S2 & F & 10 \\\hline  {\color{DarkBlue}{6}} & {\color{DarkBlue}{S2}}  & {\color{DarkBlue}{F}}  & {\color{DarkBlue}{10}} &  {\color{DarkBlue}{S3}} & {\color{DarkBlue}{M}}   & {\color{DarkBlue}{20}}  \\\hline 7 & S3 & M & 20 & S1 & F & 30 \\\hline 8 & S3 & M & 20 & S2 & M & 10 \\\hline 9 & S3 & M & 20 & S3 & M & 30  \end{array}$$

Selecting the tuple (row$\# 6$ from the above table), which satisfies the condition $(1)$ and PROJECTING $\Pi_{name} \implies \boxed{S2}$

$\Pi_{name} ( \sigma_{sex=F} (\text{Student}) ) = \boxed{\begin{matrix} S1 \\ S2 \end{matrix}}$​

Hence, the query:

$\Pi_{name} \begin{bmatrix} \sigma_{sex=F} (student) \end{bmatrix} - \Pi_{name} \begin{bmatrix} student \bowtie \sigma_{x,x,m} (student) \\ sex = F \wedge \\ x= M \wedge \\ marks \leq m \end{bmatrix}$

$\boxed{\begin{matrix} S1 \\ S2 \end{matrix}} – \boxed{S2} = \boxed{S1}$

Let us take another relation data of $\text{Student}(\text{Name}, \text{Sex}, \text{Marks})$ $$\begin{array} {c c c} \hline \text{Name} & \text{Sex} & \text{Marks} \\\hline S1 & M & 100 & \text{> highest marks of M student} \\\hline S2 & F & 50 & \text{> highest marks of F student} \\\hline S3 & M & 40 \\\hline S4 & F & 30 \end{array}$$

Taking the cross product $$\begin{array} {c c c} \hline \text{No.}  & \text{Name} & \text{Sex} & \text{Marks} & n & x & m  \\\hline  1 & S1 & M & 100 & S1 & M & 100  \\\hline  2 & S1 & M & 100 & S2 & F & 50  \\\hline 3 & S1 & M & 100 & S3 & M & 40   \\\hline 4 & S1 & M & 100 & S4 & F & 30  \\\hline  {\color{DarkBlue}{5}} & {\color{DarkBlue}{S2}}  & {\color{DarkBlue}{F}}  & {\color{DarkBlue}{50}} &  {\color{DarkBlue}{S1}} & {\color{DarkBlue}{M}}   & {\color{DarkBlue}{100}}  \\\hline 6 & S2 & F & 50 & S2 & F & 50  \\\hline 7 & S2 & F & 50 & S3 & F & 40 \\\hline 8 & S2 & F & 50 & S4 & F & 30  \\\hline 9 & S3 & M & 100 & S1 & M & 100   \\\hline 10 & S3 & M & 100 & S2 & F & 50  \\\hline 11 & S3 & M & 100 & S3 & M & 40 \\\hline 12 & S3 & M & 100 & S4 & F & 30  \\\hline {\color{DarkBlue}{13}} & {\color{DarkBlue}{S4}}  & {\color{DarkBlue}{ F}} & {\color{DarkBlue}{30}}  & {\color{DarkBlue}{S1}}  & {\color{DarkBlue}{M}}  & {\color{DarkBlue}{100}} \\\hline 14 &  S4 & F & 30 & S2 & F & 50 &   \\\hline  {\color{DarkBlue}{15}}  & {\color{DarkBlue}{S4}}  & {\color{DarkBlue}{ F}} & {\color{DarkBlue}{30}}  & {\color{DarkBlue}{S3}}  & {\color{DarkBlue}{M}}  & {\color{DarkBlue}{40}}   \\\hline 16 & S4 & F & 30 & S4 & F & 30   \\\hline  \end{array}$$

Consider the row numbers $5, 13, 15$ from the above table,

$\boxed{\begin{matrix} S2 \\ S4 \end{matrix}} \implies$  Female students who scored less than equal to some Male students.

$\Pi_{name} [ \sigma_{sex=F} (\text{Student}) ] = \boxed{\begin{matrix} S2 \\ S4 \end{matrix}}$

Hence, the result of the query will be:

$\boxed{\begin{matrix} S2 \\ S4 \end{matrix}} -\boxed{ \begin{matrix} S2 \\ S4 \end{matrix}} = \{\}$

From the above relational data of table Student(Name, Sex, Marks)

(D) is the correct option

In short,

$\{ \geq \text{All boys} \} = \mid \text{universal}\mid - \mid < \text{some M} \mid$

$\{ > \text{All boys} \} = \mid \text{universal} \mid - \mid \leq \text{some M} \mid$

$\{ \geq \text{some boys} \} = \mid \text{universal} \mid - \mid < \text{all M} \mid$

Comments

Question contains a JOIN operation. So cross product

---

When there is no common column name in two tables and we perform natural join then it acts as a cartesian product.

As in the above Q , Between Student(Name,Sex, Marks) and  Student(n,x,m) there is no common column name so cartesian product is taken

---

but where is the join operator in the query, I can see it. Is it implicit, please clarify...

Answer 2

lets try to break the query into parts and then resolve

Lets take the second part :

Here, cross product of two copies of Student relation is carried out. To effectively write the selection criteria, one relation of student is renamed with new attributes as name to n,sex to x and marks to m.

Now after having taking the cross product, selection operation is performed on the result based on below criteria :

which selects all such females whose marks are less or equal to atleast one male student (atleast one male student M1 should exist whose marks must be either greater or equal to the marks of Female student F1 for the record to be selected by the selection statement) .

Now, if we look at the first part,

This selects all female students from the relation.

Now if we look the original problem, it is more or like A-B

A - B = A intersection B'

If we consider the second part of the problem as B which gives all female students which have marks either less or equal to atleast one male student

complement of this statement would be

all female students which have marks more than all the male students.

And this if taken intersection with all female students

will give all female students with marks more than all male students

So, Option (d) is the answer.

Comments

perfect, intuitive till last intersection part :-)

---

Thanks a lot

---

A - B = A intersection B'  (imp property)

Answer 3

Answer is D

because 1st query result = all Female candidate

2nd Query = All the Female Student Whose Marks Less than from Male Student

and Ques = 1st Query - 2nd Query = Girl Student with more marks than all the male Student

Comments

2nd: Female student where every female has got some male who has higher marks than her.

Answer 4

                 -----------------------------------------------       ---------------------------------------------------------------------------------

                                             A                                                                                                              B

B: The inner part finds out  "all female students who have got less or equal marks than all boys".

A: The outer part  "All female students"

Now A-B gives "All female students who have got more marks than all boys".      ans d)

In the inner part B: there is self-cross product with attribute names being renamed. So sex denotes attribute sex of the first table while x denotes sex attribute of the 2nd table. Similarly marks and m.

Answer 5

THIS MIGHT HELP

Observe that A) cannot be the answer because when checking an extreme condition i.e. lowest marks it'll give tuples NOT FOR THE HIGHEST MARKS OF GIRL STUDENT

As this relational algebra is giving output as Nitisha & Shimonti. 

Also note that if you go for another extreme i.e. highest marks 98 then it'll give you 0 tuples because the top scorer NITISHA will also get deleted.

Therefore answer is D.

(NOTE:- Stud subscript 'xyz' is for convenience only don't bother about it)

 

 

Answer 6

1st  -  Πname(σsex=F(Student)) - Here we get all female student name.

 

2nd  - πname(Student(sex=female∧x=male∧marks≤m)ρn,x,m(Student)) - Here every female student is mapped to male students then from condition  (marks≤m)  we get all female student whose marks is less than male students.

1st - 2nd give name of female student whose mark is greater than male student.

ans-D