Question Discussion & Solution

The query asks for students who have enrolled in at least one course from *every* department. This is a classic 'division' problem in Relational Algebra.

Let's define the two relations needed for the division:

1. The set of all (student ID, department) pairs where the student has taken at least one course from that department. Let's call this R_SD (Student-Department).

   R_SD = πsID, dept(Enrolled ⋋ Course)

   The natural join Enrolled ⋋ Course will result in tuples (sID, cID, cName, dept). Projecting sID, dept from this gives us exactly what we need for R_SD.

2. The set of all distinct departments. Let's call this R_D (Departments).

   R_D = πdept(Course)

Now, we want to find sIDs such that for every department in R_D, there is a corresponding (sID, dept) tuple in R_SD. This is equivalent to R_SD ÷ R_D.

The division operator R(A,B) ÷ S(B) can be simulated using other relational algebra operators as follows:

πA(R) - πA((πA(R) × S) - R)

In our case, A = {sID}, R = R_SD, and S = R_D. Substituting these:

πsID(R_SD) - πsID((πsID(R_SD) × R_D) - R_SD)

Let's expand R_SD and R_D back into their full expressions:

πsID( πsID, dept(Enrolled ⋋ Course) ) simplifies to πsID(Enrolled ⋋ Course). This represents all students who have enrolled in at least one course.

So the correct expression is:

πsID(Enrolled ⋋ Course) - πsID((πsID(Enrolled ⋋ Course) × πdept(Course)) - πsID, dept(Enrolled ⋋ Course))

Let's analyze the options:

• Option A: This perfectly matches our derived correct expression, implementing the division simulation correctly.

• Option B: Uses πsID(Student) instead of πsID(Enrolled ⋋ Course) as the initial set of student IDs. This means it considers all students present in the Student relation, even those who haven't enrolled in any course. While the final subtraction might filter them out, the interpretation of "students who have enrolled" typically implies starting with the set of actually enrolled students. This makes Option A more precise for the given query.

• Option C: The Cartesian product part is (πsID, dept(Enrolled ⋋ Course) × πdept(Course)). This product would result in a relation with attributes (sID, dept, dept), which is not compatible with πsID, dept(Enrolled ⋋ Course) for set difference. For the division simulation, the left part of the Cartesian product must project only the 'A' attributes (sID in this case), making the intermediate relation (sID, dept) schema for the set difference operation.

• Option D: This expression πsID(Enrolled) - πsID(Enrolled ⋋ σdept = 'Math'(Course)) finds students who have enrolled in at least one course, but none of those courses are from the 'Math' department. This is a completely different query from the one asked.

Therefore, Option A is the correct Relational Algebra expression.

The given expression σ(π(R ⋈ S), F) first performs a natural join (⋈) between R and S, then projects (π) the required attributes, and finally applies a selection (σ) based on condition F. The equivalent expression π(σ(R ⋈ S, F), A) first performs the natural join and selection together, then projects the required attributes. This is because selection can be applied before projection without changing the result, as long as the selected attributes are part of the final projection.

The question asks for employees who work on *every* project associated with the 'Research' department. This is a classic relational division problem (A ÷ B), where A is `WorksOn(EmpID, ProjID)` and B is `P_RES(ProjID)`.

Relational division (A ÷ B) can be expressed using fundamental relational algebra operators (projection, cross product, and set difference) as: `π_{attributes_of_A_not_in_B}(A) - π_{attributes_of_A_not_in_B}( (π_{attributes_of_A_not_in_B}(A) × B) - A )`

In this case:

• `A = WorksOn(EmpID, ProjID)`
• `B = P_RES(ProjID)`
• Attributes of A not in B = `EmpID`

Substituting these into the formula, we get:

`π_EmpID(WorksOn) - π_EmpID( (π_EmpID(WorksOn) × P_RES) - WorksOn )`

Let's analyze the components of this expression:

1. `π_EmpID(WorksOn)`: This gives the set of all unique `EmpID`s of employees who work on at least one project. Let's call this `AllEmpIDs`.
2. `(π_EmpID(WorksOn) × P_RES)`: This is the Cartesian product of `AllEmpIDs` and `P_RES`. It generates all possible `(EmpID, ProjID)` pairs where `EmpID` is from `AllEmpIDs` and `ProjID` is from `P_RES`. This represents all *expected* `WorksOn` tuples if every employee worked on every 'Research' project. Let's call this `ExpectedWorksOn`.
3. `ExpectedWorksOn - WorksOn`: This set difference finds all `(EmpID, ProjID)` pairs that are in `ExpectedWorksOn` but *not* in `WorksOn`. In other words, these are the `(EmpID, ProjID)` pairs where an employee *should* work on a 'Research' project (according to `ExpectedWorksOn`) but *doesn't* (according to `WorksOn`). This effectively identifies the 'missing' projects for each employee relative to the 'Research' projects.
4. `π_EmpID(ExpectedWorksOn - WorksOn)`: This projects the `EmpID`s from the previous result. This gives the set of `EmpID`s of employees who failed to work on *at least one* project from `P_RES`. Let's call this `EmpIDsWhoMissed`.
5. `AllEmpIDs - EmpIDsWhoMissed`: Finally, we subtract the `EmpIDsWhoMissed` from `AllEmpIDs`. The remaining `EmpID`s are those who did *not* miss any 'Research' project, meaning they worked on *every* project in `P_RES`.

Therefore, Option A is the correct expression.

Let's analyze other options:

• Option B: `π_EmpID(WorksOn ⋈ P_RES)`
  This expression finds the `EmpID` of employees who work on *at least one* project in `P_RES`. This is not the same as working on *every* project.
• Option C: `π_EmpID(WorksOn) - π_EmpID(WorksOn ⋈ (π_ProjID(Project) - P_RES))`
  • `π_ProjID(Project) - P_RES`: This gives the set of all `ProjID`s that are *not* associated with the 'Research' department (non-research projects). Let's call this `NonResearchProjects`.
  • `WorksOn ⋈ NonResearchProjects`: This gives `(EmpID, ProjID)` pairs where the employee works on a `NonResearchProject`.
  • `π_EmpID(WorksOn ⋈ NonResearchProjects)`: This gives `EmpID`s of employees who work on *at least one* non-research project. Let's call this `EmpIDsWithNonResearchWork`.
  • `π_EmpID(WorksOn) - EmpIDsWithNonResearchWork`: This expression yields `EmpID`s who work *only* on research projects (if they work at all). An employee who works on all research projects AND some non-research projects would be excluded by this option, which is incorrect according to the question's requirement.
• Option D: `π_EmpID(WorksOn ⋈ P_RES) - π_EmpID(WorksOn ⋈ (π_ProjID(Project) - P_RES))`
  • `π_EmpID(WorksOn ⋈ P_RES)`: EmpIDs who work on *at least one* research project.
  • `π_EmpID(WorksOn ⋈ (π_ProjID(Project) - P_RES))`: EmpIDs who work on *at least one* non-research project.
  • The entire expression then finds `EmpID`s who work on *at least one* research project AND *do not* work on any non-research project. Similar to Option C, this is too restrictive and excludes employees who satisfy the condition but also work on other non-research projects.

The final answer is $oxed{A}$