COMP2400/6240 - Relational Databases
Due date: 23:59, 11 October, 2022
Instructions:
• This assignment must be done individually (no group work).
• This assignment will count for 15% of the final grade. Marks are assigned for the process of finding
a solution, not only for the result. Hence, include all essential ideas and steps that are necessary to
derive a solution.
• You must submit a single PDF file named as “u1234567.pdf” (replace u1234567 with your UID). Make
sure you only upload a PDF file, not a Word or text file.
• You should try your best to type the solutions. The scanned images of handwritten texts and equations
can be unreadable for marking. As for the EER diagram, you are highly recommended to export a
JPEG file from TerraER and include it in the PDF file.
• Late submission is not granted under any circumstance. You will be marked on whatever you have
submitted at the time of the deadline. Please take careful note of deadlines and adhere to them. Of
course, if you find yourself in a situation beyond your control that you believe significantly affects
an assessment,
• Plagiarism will attract academic penalties in accordance with the ANU guidelines. A student in this
course is expected to be able to explain and defend any submitted assessment item. The course
convener can conduct or initiate an additional interview about any submitted assessment item for
any student. If there is a significant discrepancy between the two forms of assessment, it will be
automatically treated as a case of suspected academic misconduct.
Question 1 3 Marks
Band-Aid is a booking agency that represents local Canberra bands by booking their shows nationally. The
employees of Band-Aid are classified into two non-overlapping categories, agents and administrators. An
agent represents one or more bands and can be contacted via their personal office phone or work email.
Each administrator belongs to a department which offers administrative support to all agents of the agency.
Note that the internal relationship between agents and administrators isn’t something Band-Aid cares to
track. Administrative departments include accounts, contracts, and promotions. Each Band-Aid employee
can be uniquely identified by their employee number.
Each band has a name, can be uniquely identified by their Australian Business Number (ABN), and may
have a number of band members. Band-Aid also stores the name, phone, and email of the best point of
contact for the band. Each band is represented by a particular agent and Band-Aid likes to record the date
that representation began. If a band has just joined the agency (or they aren’t very popular!) then the
agency may never have booked a show for the band.
Band-Aid maintains a list of venues. Each record includes the venue’s name, a distinct address, phone
number, and the venue capacity. Band-Aid likes to keep a comprehensive list of venues, including new
venues or venues where they’re yet to book a show.
The primary purpose of Band-Aid is to book shows. Each show is hosted by a particular venue. One or
more of the bands Band-Aid represents would perform at the show. When Band-Aid books a show, they
record the date and ticket price, and once the show is finalised, the number of tickets sold. Each show is
assigned a unique show ID.
Your task is to design an Enhanced Entity Relationship (EER) diagram that captures the above requirements. It should include entities, relationships, attributes, and constraints where appropriate. You may
make more assumptions, if necessary, but any assumptions should be noted. If there are any requirements
that cannot be captured in an EER-diagram, then they should also be identified.
1
Question 2 5 Marks
Consider the relation schema R = {A, B, C, D, E, F, G} and the following set Σ of FDs:
• C → BG
• AE → F
• CF → EA
• A → DF
2.1 What are the candidate keys of R? Justify your answer (i.e., include the main steps used for finding
the candidate keys). (1 Mark)
2.2 Find a minimal cover of Σ and include the main steps used for finding a minimal cover. (2 Marks)
2.3 Demonstrate why R, given Σ, does not satisfy 3NF, and then identify a 3NF decomposition for R.
You need to include the main steps used for identifying the 3NF decomposition. (2 Marks)
Question 3 3 Marks
Consider the relation schema Booking={Airline, Date, Destination, FlightNo, PassengerName, Origin,
PassportNo, Seat, Terminal} and the following set Σ of FDs:
• Airline → Terminal
• FlightNo → Airline, Origin, Destination
• PassportNo → PassengerName
• FlightNo, PassportNo, Date → Seat
• FlightNo, Date, Seat → PassportNo
Which, for brevity, we can alias the attributes and restate as Booking={A, D, E, F, N, O, P, S, T} and Σ:
• A → T
• F → AOE
• P → N
• FPD → S
• FDS → P
3.1 Is the above relation schema Booking in BCNF? If not, identify a BCNF decomposition for Booking
and check if your BCNF decomposition is dependency-preserving. You need to include the main steps
used for identifying the BCNF decomposition. (2 Marks)
3.2 Consider another set Σ1 of FDs on Bookings:
• Airline → Terminal
• FlightNo → Airline, Origin, Destination
• PassportNo → PassengerName
• FlightNo, PassportNo, Date → Terminal, Seat
• FlightNo, Date, Seat → PassportNo, PassengerName
Which can be similarly aliased as:
• A → T
• F → AOE
• P → N
2
• FPD → TS
• FDS → PN
Are Σ and Σ1 equivalent? Justify your answer. (1 Mark)
Question 4 4 Marks
The following table contains the relational algebra operators covered in our course. You should only use
these operators to answer the following questions.
σφR Selection by condition φ
πA1,...,An R Projection onto the set of attributes {A1 . . . , An}
ρR
′
(A1,...,An)R Renaming the relation name to R
′
and attribute names to A1, . . . , An
ρR
′R Renaming the relation name to R
′
ρ(A1,...,An)R Renaming the attribute names to A1, . . . , An
R1 ∪ R2 Union of two relations R1 and R2
R1 ∩ R2 Intersection of two relations R1 and R2
R1 − R2 Difference of two relations R1 and R2
R1 × R2 Cartesian product of two relations R1 and R2
R1 ▷◁φ R2 Join of two relations R1 and R2 with the join condition φ
R1 ▷◁ R2 Natural join of two relations R1 and R2
φ1
V
φ2 condition φ1 AND condition φ2
φ1
W
φ2 condition φ1 OR condition φ2
Consider a relational database schema S with the following relation schemas:
• Movie(title, production year, genre) with the primary key {title, production year}
• Person(id, first name, last name, year born) with the primary key {id}
• Director(id, title, production year) with the primary key {title, production year} and with the
foreign keys [title, production year] ⊆ Movie[title, production year] and [id] ⊆ Person[id]
• Writer(id, title, production year, credits) with primary key {id, title, production year} and with the
foreign keys [title, production year] ⊆ Movie[title, production year] and [id] ⊆ Person[id]
4.1 Answer the following questions using relational algebra queries only using the operators in the above
table. (2 Marks)
[a] List the ids, first and last names of directors who have never written any movie(s). (1 Mark)
[b] A person has worked on a movie if this person is a director, a writer, or both a director and
writer, of this movie. List the ids of persons who have worked on at least two distinct movies. (1 Mark)
4.2 Optimise the following relational algebra query. Your marks will depend on how well you optimise
the query in your solution. Additionally, draw the query trees of the query before and after your
optimisation. (2 Marks)
πDirector.idσ(Director.id=Person.id)
V
(year born>production year−40)(Director × Person)
−πidσ(year born<1970) W
(production year>2010)(Writer ▷◁ Person)
+++++