edited by
7,932 views
30 votes
30 votes

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 by

10 Answers

0 votes
0 votes

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)

0 votes
0 votes

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.

Related questions

23 votes
23 votes
1 answer
1
Kathleen asked Sep 25, 2014
7,165 views
Given two union compatible relations $R_1(A, B)$ and $R_2 (C, D)$, what is the result of the operation $R_1 \Join_{ A = C \wedge B = D} R_2$?$R_1 \cup R_2$$R_1 \times R_2...
47 votes
47 votes
2 answers
4
Kathleen asked Sep 25, 2014
9,755 views
There are five records in a database.$$\begin{array}{|c|c|c|c|} \hline \textbf {Name} & \textbf {Age} & \textbf {Occupation} & \textbf{Category } \\\hline \text{Rama} & ...