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, you should send an Email to Yu Lin  with the title “Special Consideration for Assignment 2 (Database Theory)” along with the supporting documents.

•  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 require- ments.  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.

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

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

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)