GATE CSE 1998 | Question: 27

Question

Consider the following relational database schemes:

• COURSES (Cno, Name)
• PRE_REQ(Cno, Pre_Cno)
• COMPLETED (Student_no, Cno)

COURSES gives the number and name of all the available courses.

PRE_REQ gives the information about which courses are pre-requisites for a given course.

COMPLETED indicates what courses have been completed by students

Express the following using relational algebra:

List all the courses for which a student with Student_no 2310 has completed all the pre-requisites.

Comments

https://dbis-uibk.github.io/relax/calc.htm#

check queries on this tool, it's awesome.

---

$\text{COMPLETED-COURSES} \leftarrow \rho \ (\sigma_{(student\_no = 2310)} \text{COMPLETED})$

 

$\pi_{\text{PRE-REQ.Cno}} (\text{COMPLETED-COURSES}\ \boxtimes \ _{\text{(COMPLETED-COURSES.Cno} = \text{PRE-REQ.pre-Cno)}} \text{PRE-REQ}) $

 

Is this relational algebra expression correct?

---

those who are confused that we can use division operator use or not bt  division is not relation algebra operator so we have to write division operator in terms of basic operators.

Answer 1

$T_1$ will have all the available course numbers

$T_2$ will have all the course numbers completed by student2310

$T_3$  will have the combination of all the courses and the courses completed by student2310

$\text{PRE_REQ} - T_3$ (set minus operation) will return us all the entries of $\text{PRE_REQ}$ which are not there in $T_3,$

Suppose $\langle C_1,C_5\rangle$ is a particular tuple of $(\text{PRE-REQ} - T_3),$

Now what does it imply? $\implies$ It implies that $C_5$ is one of the prerequisite course for $C_1$ which has not been completed by $C_5$. Proof: If student2310 would have completed $C_5$ then definitely $\langle C_1,C_5 \rangle$ should have been there in  $T_3$ (remember $T_3$ is the combination of all the courses and the courses completed by student2310) and in that case $(\text{PRE_REQ} - T_3)$ can not have  $\langle C_1,C_5 \rangle$ as a tuple.

So, for any such $\langle C_1,C_5 \rangle$ tuple, $(\langle C_1,$ any  course id$\rangle)$ of $\text{PRE_REQ} - T_3, C_1$  should not be printed as output (Since there is some prerequisite course for $C_1$ which student2310 has not completed).

Now, suppose we have not got any tuple as a result of $(\text{PRE_REQ} - T_3)$ where $C_2$ is there under cno attribute $(\langle C_2,$ any course id$\rangle ),$ what does it imply?$\implies $ It implies that student2310 has completed all the prerequisite courses $C_2.$

Hence, in order to get the final result we need to project cno from $(\text{PRE_REQ} - T_3)$ and subtract it from $T_1.$

• $T_1 \leftarrow \pi_{\text{cno}}(\text{COURSES})$
• $T_2 \leftarrow \rho_{T_2(\text{std2310completedcourses})}(\pi_{\text{cno}}(\sigma_{\text{student_no} = 2310}(\text{COMPLETED})))$
• $T_3 \leftarrow T_1 \times T_2$
• $T_4 \leftarrow \rho_{T_4(\text{cno, pre_cno})}(\text{PRE_REQ}-T_3)$
• $Result \leftarrow T_1 - \pi_{\text{cno}}(T_4)$

Comments

@Abhrajyoti00 @Kabir5454 @samarpita @Pranavpurkar

is this correct

I have first selected all the courses completed by the student no 2310,
and then renamed that as $PRE\_CNO.$ 
now the relation PRE_REQ is divided by the above result which should return the all cno of courses whose pre requisites are completed by 2310 .

and finally the join with courses to retrieve the course names.
 

---

Projecting name??, I think we have to project Cno. Correct me If I am wrong!

---

@JAINchiNMay I think your query is wrong, it is giving those courses whose prerequisites are all the courses completed by student 2310. But there might be a course whose prerequisite is only one course and it completed by student 2310, so it should come in output but in case of your query it will not come in output

Answer 2

SQL query will be 

SELECT cno 
FROM Completed, Pre-Req  
WHERE student_no = '2310'  
GROUP BY cno  
HAVING pre-Cno IN (
    SELECT C.cno 
    FROM Completed AS C
    WHERE C.student_no = '2310';
    )

Comments

But question is for relational algebra query.

---

arjun sir can u plz write RELATIONAL ALGEBRA for it?? i am not able to figure out. :-(

---

The one given by @mint below looks right to me. Verify
Π_Cno.(PRE-REQ ⋈_{pre Cno.=Cno.}   Π_Cno.(σ_Sno.=2310(COMPLETED)))

---

Is it right sql query for above scenario???

select COURSES.cno
from COURSES,PRE-REQ,COMPLETED
where
PRE-REQ.pre-Cno=COMPLETED.Cno
and
COMPLETED.student_no=2310
and
COURSES.cno = PRE-REQ.cno
and
PRE-REQ.cno=COMPLETED.cno
and
COMPLETED.cno=COURSES.cno

---

@amarVashishth I think your sql query won't work because "IN" operator is a shorthand for multiple "OR" conditions in SQL so here any course no will be displayed for which any one of the pre-req course has been completed But here we need For All condition.

SELECT Cno
FROM Courses C1
WHERE NOT EXIST ( ( SELECT Pre-cno
                                       FROM PRE-REQ P1
                                       WHERE C1.Cno=P1.Cno
                        EXCEPT
                                       SELECT Cno
                                       FROM COMPLETED C2
                                       WHERE C2.student_no='2310' ) ) ;
 

---

I have also came with same answer

Answer 3

$S \leftarrow \pi_{Cno}(\sigma_{student\_no=2310}(COMPLETED))\\RESULT \leftarrow ((\rho_{(Course,Cno)}(PRE-REQ)) \div S )$

http://docdro.id/T8OxQBt

Comments

MiNiPanda yes i also think in the same way. Sourav Basu answer seem to be same as yours.

---

@Arjun Sir, Please check this answer

---

yes, this is wrong. It is outputting the courses only if the student has not completed any other courses than its prerequisites.

Answer 4

RA query: Π_Cno.(PRE-REQ ⋈_{pre Cno.=Cno.}   Π_Cno.(σ_Sno.=2310(COMPLETED)))   

make it in two parts:

X= Π_Cno.(σ_Sno.=2310(COMPLETED))      {X gives all the tuples in which 2310 is present}

Y=Π_Cno.(PRE-REQ ⋈_{pre Cno.=Cno.}   X)   

I think Y is the required answer... correct me if i wrong.

Comments

I got the same answer. I am wondering my no one commented here before. Veterans ?

---

PRE-REQ gives the information about which courses are pre-requisites for a given course, hence a course may have many prerequisite courses. In that case suppose a course C1 has two prerequisite courses- CP1 and CP2, now even if Sno-2310 completes only one of those prerequisite courses then also above query will print C1, which it should not, if and only if Sno-2310 completes both CP1 and CP2 then only it should print C1

---

There maybe more than one prereq for a single course.