Tuple calculus: unsure if my reasoning is correct

Question

I'm currently working through a tuple calculus question and I ran into a situation where I have two answers that seem correct to me and I am unsure if my logic is wrong or if they are both correct answers (and if so, is one more correct than the other).

I am trying to find the sid of the store that supplies every item. The schemas are:

Stores(sid: integer, sname: string)

Items(iid: integer, iname: string)

Supplies(sid: integer, iid: integer, price: integer)

What I came up with was:

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

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

My reasoning is that I am looking for the sid where for all Items there is an entry in the Supplies table that corresponds to the iid. The only real difference between my answers is that the second one doesn't use a second separate Supplies table which allows us to cut out the additional S2.sid = S1.sid. My textbook has a similar question to this and has an answer similar to 1 but my reasoning gets me the second answer.

Answer 1

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.)