# Find the highest graded student in each state, using Relational Algebra

Suppose I have a table of students, containing their ID, grade and state:

``````-------------------------
| id  |  grade  | state |
------------------------
|  1  |    83   |   CA  |
|  2  |    94   |   TX  |
|  3  |    92   |   WA  |
|  4  |    78   |   CA  |
``````

And I want the ID of the students in each state with the highest grade (ex. 1, 2 and 3), how would I go about doing that?

I know how to find the maximum (can do the cross product (renaming as R1 and R2) and then select R1.grade < R2.grade for those who aren't the top, and subtract that from the original database). But I'm confused at how to do that for each state.

I don't actually feel very comfortable with relational algebra, so, I'll do it first using standard SQL and then use a tool called RelaX - relational algebra calculator 0.18.2 to do the translation.

First, the table you wrote, I'll call it students, and define it and fill it with:

``````CREATE TABLE students
(
id INTEGER PRIMARY KEY,
state TEXT
) ;

INSERT INTO students
VALUES
(1, 83, 'CA'),
(2, 94, 'TX'),
(3, 92, 'WA'),
(4, 78, 'CA') ;
``````

RelaX will translate this into a dataset, represented by the following tuples:

``````group: Joan (imported from SQL)

students = {
1        , 83          , 'CA'
2        , 94          , 'TX'
3        , 92          , 'WA'
4        , 78          , 'CA'
}
``````

In order to find what you're looking for, we first need a table with tuples in the form `(state, grade)`, having the maximum grade of each state. This query is done, in SQL with a `MAX(grade)` per `state` using a `GROUPs BY state`. You would write it like:

``````SELECT
FROM
students AS s2
GROUP BY
state ;
``````

Next, you need to `JOIN` this table (that is named `max_grades`) to the `students` one, and you do it `ON` equal states, and equal grade (i.e.: the max grade per state)...

``````SELECT
s1.id
FROM
students AS s1
JOIN
(
SELECT
FROM
students
GROUP BY
state
``````

... and this gets translated by RelaX to the following relational algebra expression and reponse:

s1.id
1
2
3 NOTE1:

1. If several students of one state would have the max grade, this expression would return ALL of them, not just an arbitrary one of that state.

Alternative:

If you cannot `GROUP BY`, you can use another construct:

``````SELECT DISTINCT
id
FROM
students
EXCEPT
SELECT
s1.id
FROM
students AS s1
JOIN students AS s2 ON s1.state = s2.state AND s1.grade < s2.grade
``````

This goes a bit more in-line with your original thinking, although I personally find it less clear...

The translation to relational algebra is:

π id students - π s1.id ρ s1 students ⨝ s1.state = s2.state and s1.grade < s2.grade ρ s2 students EDIT: I did not read carefully and gave an answer for SQL, in case poster is interested. Please let me know if you are not interested and then I will delete.

SQL: I think using a derived table works. Let's call your table 'Students':

``````SELECT id FROM Students JOIN
(SELECT State, Max(Grade) AS MaxGrade FROM Students GROUP BY State ) AS T
ON T.State=Students.State