Question 6 of 8: Relational algebra — Bids/Auctions/Ratings

Question 6: Relational algebra — Bids/Auctions/Ratings (5+5+10=20 marks)

Question text not reproduced: the examination questions are © Engineers and Geoscientists BC. Open the official past paper (linked at the top of this page) to read the question, then follow the worked solution below.

Given. Bids(auctionID, bidder, price, quantity); Auctions(auctionID, seller, item, quantity, expires); Ratings(seller, stars). The stated uniqueness rule (one bidder's bids on one auction all have distinct prices) makes (auctionID, bidder, price) a key of Bids; as noted in part (c), none of the three queries actually depends on it.

Find. Three relational-algebra expressions using only the classic operators π (project), σ (select), &Join; (natural join), × (cross product), ∪/∩/− (set union/intersect/difference), ρ (rename) — no SQL, no built-in MAX.

Approach. (a) is a select-then-join-then-project. (b) needs the same attribute (seller) restricted two different ways and then intersected. (c) is the classic "maximum via self-join and set difference" construction, since basic relational algebra has no aggregate MAX operator: a price is NOT the maximum if some OTHER row's price beats it, so subtract every "beaten" price from the set of all candidate prices.

1. (a) Bidders on "Beanie Baby" auctions. Restrict Auctions to the item, join to Bids on the shared auctionID, then keep only the bidder column: $$\pi_{\text{bidder}}\big(\sigma_{\text{item}=\text{"Beanie Baby"}}(\text{Auctions}) \Join \text{Bids}\big)$$ The natural join matches on auctionID (the only shared attribute), so every surviving Bids row belongs to a Beanie-Baby auction; projecting onto bidder alone then automatically de-duplicates repeat bidders (relational algebra results are sets).
2. (b) Sellers with both a 1-star AND a 5-star rating. Compute the two seller sets independently, then intersect — intersection is exactly the "both/and" combinator over two independently-restricted projections of the SAME attribute: $$\pi_{\text{seller}}\big(\sigma_{\text{stars}=1}(\text{Ratings})\big) \;\cap\; \pi_{\text{seller}}\big(\sigma_{\text{stars}=5}(\text{Ratings})\big)$$ A UNION here would be wrong (it would return sellers with EITHER rating, not both); intersection is what forces membership in both restricted sets simultaneously.
3. (c) Highest bid price for "Beanie Baby" auctions. First isolate the candidate rows — every Bids row that belongs to a Beanie-Baby auction: $$BB \;=\; \pi_{\text{Bids.*}}\big(\sigma_{\text{item}=\text{"Beanie Baby"}}(\text{Auctions}) \Join \text{Bids}\big)$$ A price is NOT the maximum exactly when some other candidate row's price is strictly greater; self-join two renamed copies of BB and keep the price wherever it is dominated: $$\text{Dominated} \;=\; \pi_{BB_1.\text{price}}\Big(\sigma_{BB_1.\text{price} \,<\, BB_2.\text{price}}\big(\rho_{BB_1}(BB) \times \rho_{BB_2}(BB)\big)\Big)$$ Subtracting the dominated prices from ALL candidate prices leaves only the price(s) nothing beats — the maximum: $$\text{Highest} \;=\; \pi_{\text{price}}(BB) \;-\; \text{Dominated}$$ The uniqueness rule stated in the preamble (one bidder never has two equal-priced bids on the same auction) is not actually needed for correctness here — the set-difference construction returns the true maximum price even with ties across DIFFERENT bidders, since a tied price is never strictly dominated by the other tied price and so survives the subtraction.