Convert query in words to relational algebra

Answer

I'm going to rename your tables a bit:

Store(s) -- store [s.sid] has name [s.sname]
Item(i) -- item [i.iid] has name [i.iname]
Offer(o) -- store [o.sid] offers item [o.iid] for $[o.price]

You want the tuple(s) s of the form < sid > where

-- store s.sid offers every item, ie
-- for all Items i: store s.sid offers item i.iid, ie
-- for all Items i: there exists Offer o: [o.sid = s.sid ∧ o.iid = i.iid], ie
∀ i ∈ Items ∃ o ∈ Offer [o.sid = s.sid ∧ o.iid = i.iid]

The query for such stores--and there can be more than one such store--is:

{ s : < sid > | ∀ i ∈ Items ∃ o ∈ Offer [o.sid = s.sid ∧ o.iid = i.iid] }

Your answer 2

I am looking for the sid where for all Items there is an entry in the Supplies table that corresponds to the iid.

That has a "for-all for which there-exists", just like my solution. But your proposed answer 2 has a "there-exists for which for-all":

{ P | ∃ S1 ∈ Supplies(
        P.sid = S1.sid
    ∧ ∀ i ∈ Items(S1.iid = i.iid)
    )}

That asks for tuples P where there is an offer S1 where [P's sid is S1's sid and for all Items S1's iid is that item's iid]. I hope you can see that this involves a single iid being the same as all the ones in Item, not what you want.

Your answer 1

{ P | ∃ o ∈ Offer (
        P.sid = o.sid
    ∧ ∀ i ∈ Item (∃ o2 ∈ Offer (o2.iid = i.iid ∧ o2.sid = o.sid))
    )}

Notice from above that the ∀ ... means store o.sid offers every item. So:

{ P | ∃ o ∈ Offer (P.sid = o.sid
    ∧ store o.sid offers every item  )
    )}

If there are no offers and some stores then every store offers every item. But since there are no offers, it's false that ∃ o ∈ Offer (P.sid = o.sid)). No Ps make that true. So this is {}. So this is not the answer.

(Your answer 1 may be modified from a textbook answer expressed by Codd's original relational division operator. But so dividing Offers by Items doesn't actually return tuples s where store s.sid offers every item. It returns rows where store s.sid offers every item AND there is at least one item. So the answer is not expressed by Offers/Items.)

(Indeed 2 has an extra ∃ compared to your natural language description and my answer, but it's the outer ∃. So your solution 1 is in that way reminiscent of the correct answer.)

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