Relational Algebra – Do My Operations Produce Desired Results?

I think the key point here is the fact that relational algebra eliminates duplicates from its result. So if you use a Project operator to get only iid and price, it will give you the list of bids excluding the duplicate bids. If you subtract this list from the whole bids you will get the bids those are duplicates..

I am not sure though.. Would you please comment on how you feel about this approach?

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,
    grade INTEGER,
    state TEXT
) ;

INSERT INTO students
    (id, grade, state)
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 = {
    id:number, grade:number, state:string
    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
    state, max(grade) AS grade
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
            state, max(grade) AS grade
        FROM 
            students
        GROUP BY
            state
    ) AS max_grades 
    ON s1.state = max_grades.state AND s1.grade = max_grades.grade

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

π _s1.id ρ _s1 students ⨝ _{s1.state = max_grades.state and s1.grade = max_grades.grade} ρ _{max_grades} ( π _{state, grade} γ _{state; MAX(grade)→grade} ρ _s2 students)

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