COMP3278 Introduction to Database Management Systems
Assignment 3 – Relational Algebra, Functional Dependency & BCNF
Due Date: April 14, 17:30
Q1 Consider the following relational tables:
• Users (uID, name)
• Restaurants (rID, name, cruise, michelinStar, maxBooking)
o michelinStar is a number in a rating system used by the Michelin Guide to
evaluate restaurants. The value can be 1, 2, or 3. You can assume all restaurants
stored in this table are Michelin restaurants.
o maxBooking is the maximum number of bookings the restaurant can serve in the same
period of time.
• Booking (uID, rID, bdate, startTime, endTime)
o Foreign keys: uID referencing Users (uID), rID referencing Restaurants (rID)
o bdate is the date of the booking in the formant DD-MM-YYYY. We can assume that no
booking will span across two days.
o The time intervals [startTime, endTime] (both in the format (HH:MM) denotes the
period of time that the restaurant (denoted by rID) booked by the user (denoted by uID).
Please give the expression trees after optimization (You can use assignment operator and
more than one trees to answer each question):
1. [5%] Find the distinct uID of the users(s) who booked a restaurant of “Thai” cruise in
February of 2023.
2. [10%] Find the distinct rID of the restaurant(s) that is both:
• booked by the user with name as “Kit”, and
• the restaurant has been booked for more than 100 times.
3. [10%] Find the distinct uID,name of the user(s) who have booked all Michelin 3 stars
“Japanese” cruise restaurants.
4. [10%] Find the distinct rID, date, startTime, endTime of the restaurant(s) that is over-
booked in the period of time (i.e., the number of bookings of the restaurant on the same date,
startTime, endTime exceeds maxBooking of that restaurant, you can ignore
overlapping time intervals in the booking records.)
5. [20%] Find the distinct uID,r1name,r2name of the user(s) who made more than one
booking in the same period of time, where r1name and r2name are the names of the
restaurant(s) that the user has booked in the same period of time, and r1name and r2name
can be the same (Please take the booking of all restaurants, and overlapping time intervals into
consideration.)
Q2 [15%] Given the relation schema R (A, B, C, D, E) with the following functional dependencies set
F = {A→B, BD→E, C→D, E→A} which hold on R.
Find and proof all candidate keys in R.
Q3 [15%] Given the relation schema R (A, B, C, D, E) with the following functional dependencies set
F = {A→BCD, D→B, E→AD} which hold on R.
If R is decomposed to the following R1 and R2
R1 = (A, B, E) and R2 = (C, D, E)
a. Is the decomposition dependency-preserving? Explain your answer.
b. Suggest two different ways to handle the unpreserved dependencies in the above
decomposition.
Q4 [15%] Given the relation schema R (A, B, C, D, E) with the following functional dependencies set
F = {B →A, B →D, BE → D, C →E} which hold on R.
Give a lossless join and dependency preserving decomposition of R into relations in BCNF. Show
your steps and proof.
Submission
• Please submit one PDF file to Moodle on or before the deadline of this assignment.
• Should you have any enquiries, please feel free to post on Moodle. TA Tom
zerong@connect.hku.hk will be very happy to help. Thank you!
We wish you enjoy learning database technologies in this course!