Relational algebra "grouping"

Question

Sorry for the vague question topic!

I've got a particular relational-algebra problem that has me and a couple of friends stumped.

Now, here's the question:

For each department, find the maximum salary of instructors in that
department. You may assume that every department has at least one
instructor.

I'll upload the schema as well, as a visual aide.

I've worked this out to a point;

I need a relation that includes all the instructors in any department, we've got that. It's the instructor relation.

Out of that relation i need to 'split' it up into a per-department basis. and once I have that relation I just take the max(salary) and return that.

Problem is, the only way I can think of to do that is something like this:

π(max(salary)(σ(dept_name = x(instructor)))

Where x = whatever dept_name i'm looking for, but If I did it this way, then I'd have to do a new relation for every department!

How would you do it?

(Note: I just copy and paste'd the symbols from wikipedia if you want to use them in your answer)

Answer 1

My relational algebra might be a bit rusty but I think that

dept_name_G_{max(salary)}(
    σ_{ddept_name = idept_name}(
        ρ_{dept_name/ddept_name}(department) ⨯
        ρ_{dept_name/idept_name}(instructor)
    )
)

is what you seek for.

Remember that all projections are just operations on sets. The first thing you would do to connect the information of department and instructor is to bring the information together. So you want to join department and instructor, basically a cross product (⨯):

department = {(depA, 100$), (depB, 200$)}
instructor = {(will, depA, 10$), (bob, depB, 20$), (will, depB, 9$)}
department ⨯ instructor = {
                            (depA, 100$, will, depA, 10$), 
                            (depA, 100$, bob, depB, 20$), 
                            ..., 
                            (depB, 200$, will, depA, 10$), 
                            ...
                          }

So what you would want now is to filter the tuples where the dept_name of the instructor equals the dept_name of the department. But you also notice that you now have a naming collision, namely the column dept_name comes up twice.

As you can't simply do σ_{dept_name = dept_name}(department ⨯ instructor) you need to rename at least one of the dept_name fields. I renamed both for clarity which one belongs to what.

So what you now have is

σ_{ddept_name = idept_name}(
    ρ_{dept_name/ddept_name}(department) ⨯
    ρ_{dept_name/idept_name}(instructor)
)

giving you:

{
 (depA, 100$, will, depA, 10$), 
 (depB, 200$, bob, depB, 20$),
 (depB, 200$, will, depB, 9$)
}

The whole process is a natural join and can be expressed shortly with:

department ⋈ instructor

Now the final step is to project the maximum salary per department. A simple projection can't do that but the aggregation operator can:

{dept_name}_G_{max(salary)}(department ⋈ instructor)

results in

{
 (depA, 10$), 
 (depB, 20$)
}