2.1k views

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.

edited | 2.1k views
+3

In relation COURSES  ,(comma) missing

COURSES (Cno.name) -> COURSES (Cno. , name)

0
see detail explanation at the last of this page...
+1
https://dbis-uibk.github.io/relax/calc.htm#

check queries on this tool, it's awesome.
0
$\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?

$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)$
by Active (2.7k points)
edited
0
this is the correct answer. Rest all above give wrong answer.
0

This seems the best answer. @Arjun sir please check this.

I've always one doubt whenever see this type of questions.How to think like this in exam hall within a time limit.

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

http://docdro.id/T8OxQBt
by Boss (17.4k points)
0
@sachin

we will select CNO for stud_no=2310 and rename CNO as pre-cno in COMPLETED relation and then perform divison of PreReq table with the table created above. Right??
0
No, it won't work. Say if student completed two courses C1 and C2 that are prerequisite for C3 and C4 respectively. Then what will ur query return?. It will return Null table.
Bcoz neither C3 has both prerequisite as C1 and C2 nor C4 has both prerequisite.
0
so can u write the correct query in relational algebra as sql both??
0

RESULT←((ρ(Course,Cno)(PREREQ))÷S)

The division operation p(P) ÷ q(Q) only makes sense when Q ⊆ P.

In the above assignment, there are no common attributes between the two relations as the only common attribute 'Cno' has been renamed to 'Course', so the division makes no sense.

Your answer is incorrect because it is not even a valid expression.

0
Can I do this

Project courseno (Select studentno=2310 (completed join pre requisite))
+1

Will this work for the below database?

Courses

 Cno Cname c1 A c2 B c3 C c4 D c5 E

Pre-Req

 Cno Pre-Cno c1 c3 c2 c1 c2 c4 c5 c2 c5 c3

In graphical form:

Which shows that c3 and c4 do not need any pre-course and rest others do. There shouldn't be any cycle in this graph otherwise no course can ever be completed. Like if pre-course for c1 is c2 and pre-course for c2 is c1 then we cannot make any progress.

 Sno Cno s1 c3 s1 c4 s2 c1 s3 c2

Now if I want to know what are the courses that s1 can complete after having taken the pre-courses, then:

pre courses taken by s1 are c3 and c4.

With the knowledge of c3 and c4 only c1 can be completed.

After taking c1, s1 can then take c2 and then c5. But these shouldn't be the current result.

According to the query:

S will have {c3,c4} and when we divide pre-req with it, the result we get is null. Isn't it? If so then this is not giving correct result.

@Sachin I saw the pdf you attached.. But there you haven't considered the case if a student has completed more than one course.

0

SπCno(σstudent_no=2310(COMPLETED))

R←πCnoCno X S

M←πCno(Pre-Req - R)

πCno(πCno(Cno) - (M∪S) )

I am getting this.

For S1,

S={c3,c4}

R= <c1,c3>, <c1,c4>,<c2,c3>,<c2,c4>,<c3,c3>,<c3,c4>,<c4,c3>,<c4,c4>,<c5,c3>,<c5,c4>

M= πCno(<c2,c1>,<c5,c2>) = {c2,c5}

πCno(Cno - (M∪S) )= πCno({c1,c2,c3,c4,c5} - ( {c2,c5}∪{c3,c4}) ) = c1

For S2, answer should be c3 and c4 only because they don't need any pre-course.

Please correct me if wrong.

0

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

0

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

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';
)
by Boss (30.5k points)
+2
But question is for relational algebra query.
0
arjun sir can u plz write RELATIONAL ALGEBRA for it?? i am not able to figure out. :-(
+1

The one given by @mint below looks right to me. Verify
ΠCno.(PRE-REQ ⋈pre Cno.=Cno.   ΠCno.Sno.=2310(COMPLETED)))

0
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
0

@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' ) ) ;

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}

YCno.(PRE-REQ pre Cno.=Cno.   X)

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

by Active (1.3k points)
0
I got the same answer. I am wondering my no one commented here before. Veterans ?
+3

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

0
There maybe more than one prereq for a single course.
+1 vote
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' ) ) ;

Is this query correct ?
by (51 points)
reshown by

This should be the answer.

ΠCno(PRE-REQ) - ΠCno(PRE-REQ - ρPRE-REQ.Cno/CnoPRE-REQ.Cno,pre-Cno((σstudent_no=2310 (COMPLETED))⋈Cno=pre-Cno PRE-REQ)))

by Active (1.7k points)
edited

I came up with two approach for this Question.

Note- Questions in which "ALL" keyword is used, most probably would be solved with division operation.

by Active (2.5k points)

Correct me If I am Wrong..

by (229 points)
edited

Here's one way to do it:

(it helps if you write down what is happening to the relations after every expression)

Select courses done by student no. 2310

$Temp_1 \leftarrow \Pi_{Cno}[\sigma_{Student\_no=2310}(COMPLETED)]$

Rename the relation to student_courses and its attribute to Pre_Cno to make it ready for division

$\rho_{student\_courses(Pre\_Cno)}(Temp_1)$

All courses paired with the courses done by student 2310

$Temp_2 \leftarrow COURSES \times student\_courses$

Select Cno's from COURSES

$Temp_3 \leftarrow \Pi_{Cno}(COURSES)$

Rename it to misc_courses and its attribute to Cno1 to distinguish it from Cno

$\rho_{misc\_courses(Cno1)}(Temp_3)$

Final dividend
$Temp_4 \leftarrow \sigma_{misc\_courses.Cno1=Temp_2.Cno}(misc\_courses \times Temp_2)$

This will give us all the courses (twice, once as Cno1 and the other as Cno) with their names paired with each of the courses done by student no. 2310 (as Pre_cno) so that dividing this by the PRE_REQ relation will give you the name and course no. (as Cno1) of the required courses

$Temp_4 \div PRE\_REQ$

(Have a look at the wiki page if you don't know what the division operator does)

by Active (1k points)

some points to be noted:

1) pre req graph can't contain a cycle..like pre requisite of c2 is c1 and vice versa
2) suppose pre requisite of c9 is c1,c2 then in completed table no student can complete combination of courses like c9,c1  ;  c9,c2  ; c9  ;

combinations must be like c1;   c2;   c9,c1,c2 ;  etc

cause no student can complete only c9 or c9 with c2 only as c9 requires both c1 and c2 to be completed..

3) there must be at least one course with 0 pre-requisites and 1 course that is pre-requisite of no other course. Meaning there must be at least 1 sink( no outward path edge, and at least 1 inward path edge) in pre requisite graph made from pre-req table.And there will be at least 1 source (no inward path edge , and at least 1 out ward path edge)

4) there may be isolated vertices in pre-requisite graph.. having no pre requisite and not pre requisite of any other course.

4)answer will be the courses for with if we list the pre requisites then for each course,the pre requisites will be subset of courses completed by stud2310.

PLEASE CORRECT ME IF I'M WRONG IN ANY STATEMENT.
by (129 points)

1
2