COMP2400/6240 – Relational Databases
Assignment on Database Theory
Assignment on Database Theory (Solutions)
Due date: 23:59, 8 October 2019
This assignment will be marked out of 15. It 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.
Instructions:
• This assignment should be done by a group of two students or individually. COMP2400 students can only be
paired with other COMP2400 students. COMP6240 students can only be paired with other COMP6240 students.
• You must submit two files on Wattle before the due date:
1. “u1234567-u7654321-ass2.pdf” (replace u1234567 and u7654321 with your UID and your group partner’s
UID, respectively). Make sure you only upload the PDF file, not a Word or text file. This PDF file
should contain a JPEG figure as the EER diagram exported from TerraER.
2. “u1234567-u7654321-ass2.xml” (replace u1234567 and u7654321 with your UID and your group partner’s
UID, respectively). This is the XML file that corresponds to the EER diagram drawn by TerraER.
• For each group, you only need to submit a single copy of your assignment on Wattle under either your UID
or your partner’s UID.
• 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 effects an assessment, you should follow the
ANU’s special consideration process (http://www.anu.edu.au/students/program-administration/assessments-
exams/special-assessment-consideration).
• 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 4 Marks
ACTRides is a car rental company which has been founded recently in Canberra. It currently has 5 branches opened
in Acton, Belconnen, Dickson, Braddon and Woden, respectively. ACTRides is planning to expand to areas such as
Tuggeranong and Manuka in the future. A branch has a unique address but may have multiple telephone numbers.
Each rental car must be associated with exactly one ACTRides branch. A rental car can be identified by its registration
number and has the information about the model and the production year. Each employee working at ACTRides has
a tax file number (TFN), a name and an address. ACTRides employees consist of managers, mechanics and customer
service representatives. Every employee must work at exactly one branch. A customer of ACTRides should provide
their drivers license number, their name and a contact number. A customer can rent a car from an ACTRides branch
and details about the rental such as the rental period and price should be recorded. If a customer is not satisfied
with the rental service provided, this customer may submit a complaint to a customer service representative and thus
a distinct reference number and detailed description of the complaint should be recorded. The manager of a branch
will handle all the complaints with respect to this branch and has an urgent contact number in case of emergency.
Mechanics working at a branch inspect the cars associated with the branch and record the condition and inspection
date. A car must be inspected at least two times per year. Each mechanic has a skill level and might have another
mechanic as the supervisor. The supervisor must have a higher skill level compared to the mechanics supervised by
this supervisor.
Your task is to design an Enhanced Entity Relationship (EER) diagram for the above database, which should include
entities, relationships, attributes and constraints wherever appropriate (you can make more assumptions if necessary).
1
You also need to identify the requirements that cannot be captured in an EER-diagram.
Requirements that cannot be captured in the EER-diagram:
• A car must be inspected at least two times per year.
• The supervisor must have a higher skill level compared to the mechanics supervised by this supervisor.
Question 2 4 Marks
Consider the relation schema R={A, B, C, D, E} and the following set Σ of FDs:
• A → B
• AB → DE
• C → B
• BE → AC
2
2.1 What are the candidate keys of R? Justify your answer (i.e., include the main steps used for finding the candidate
keys). (2 Mark)
Consider 1 attribute at a time. Only the closure of A will give you all the attributes in R:
{A}+ = {AB}+ = {ABDE}+ = {ABCDE} 3
Hence {A} is a candidate key.
Consider combinations of 2 attributes which do not contain A. Only the closure of BE and CE will give you all
the attributes in R:
{BE}+ = {BEAC}+ = {ABCDE} 3
{CE}+ = {CE}+ = {BCE}+ = {ABCDE} 3
Hence {BE} and {CE} are also candidate keys.
There is only one combination of 3 attributes {BCD} that does not contain A, BE or CE, but {BCD} is not a
superkey becasue {BCD}+ = {BCD}.
In summary, {A}, {BE} and {CE} are three candidate keys of R.
2.2 Find a minimal cover of Σ. Justify your answer (i.e., include the main steps used for finding a minimal cover).
(2 Mark)
To find the minimal cover we first ensure that all the FDs determine only one attribute:
Σ
′
= {A→ B,C → B,AB → D,AB → E,BE → A,BE → C}
Now check for redundant attributes on the determining side:
Replace AB → D with A→ D? D ∈ {A}+ under Σ? yes 3 Replace AB → D with A→ D
Replace AB → E with A→ E? E ∈ {A}+ under Σ? Yes 3 Replace AB → E with A→ E
Replace BE → C with B → A? A ∈ {B}+ under Σ? No 7 No replacement
Replace BE → C with E → C? C ∈ {E}+ under Σ? No 7 No replacement
Replace BE → A with B → A? A ∈ {B}+ under Σ? No 7 No replacement
Replace BE → A with E → A? A ∈ {E}+ under Σ? No 7 No replacement Now we get:
Σ
′
= {A→ B,C → B,A→ D,A→ E,BE → A,BE → C}
Lastly check if any FDs are redundant:
A→ B? B ∈ {A}+ under Σ
′
− {A→ B}? {A}+ = {ADE}+ = {ADE} 7 Keep A→ B
C → B? B ∈ {C}+ under Σ
′
− {C → B}? {C}+ = {C} 7 Keep C → B
A→ D? D ∈ {A}+ under Σ
′
− {A→ D}? {A}+ = {ABE}+ = {ABCE} 7 Keep A→ D
A→ E? E ∈ {A}+ under Σ
′
− {A→ E}? {A}+ = {ABD}+ = {ABD} 7 Keep A→ E
BE → A? A ∈ {BE}+ under Σ
′
− {BE → A}? {BE}+ = {BCE}+ = {BCE} 7 Keep BE → A
BE → C? C ∈ {BE}+ under Σ
′
− {BE → C}? {BE}+ = {ABE}+ = {ABDE} 7 Keep BE → C
Therefore our minimal cover is (in both minimal ΣM and canonical ΣC form):
ΣM = {A→ B,C → B,A→ D,A→ E,BE → A,BE → C}
ΣC = {A→ BDE,C → B,BE → AC}
3
Question 3 2 Marks
Consider the relation schema Appointment={Customer, Date, Staff, Room, Branch} and the following set Σ of FDs:
• Branch, Date, Staff → Room
• Customer, Date → Staff
• Branch, Date, Room → Staff
• Branch, Customer, Date → Room
Is the above relation schema Appointment in BCNF? If not, identify a BCNF decomposition for Appointment.
You need to include the main steps used for identifying the BCNF decomposition. Check if this BCNF decomposition
is dependency preserving. (2 Mark)
We alias the attributes to the first letter of their names for brevity, and order alphabetically.
To check whether Appointment in BCNF, we need check whether all the FDs meet the BCNF requirement (that for
all X → Y in Appointment, X is a super key). We check the closure of the determining side of each FD to see if all
the attributes of Appointment are included:
{BDS}+ = {BDRS} 7
{CD}+ = {CDS} 7
{BDR}+ = {BDRS} 7
{BCD}+ = {BCDR}+ = {BCDRS} 3
Hence, Appointment is not in BCNF.
Now we select FDs that violate BCNF requirements and use them to decompose Appointment iteratively.
We first select BDS → R and produce the following relations and associated FDs.
RA = {B,C,D, S} ΣRA = {CD → S}
RB = {B,D,R, S} ΣRB = {BDR→ S,BDS → R}
Note that BCD → R is lost.
Note that RB (with respect to ΣRB = {BDR → S,BDS → R}) is now in BCNF because both BDR and BDS are
superkeys. However, RA (with respect to ΣRA = {CD → S}) is not in BCNF because CD is not a superkey in RA.
Thus we select CD → S and produce the following decomposition of RA into RA1 and RA2.
RA1 = {B,C,D} ΣRA1 = ∅
RA2 = {C,D, S} ΣRA2 = {CD → S}
RB = {B,D,R, S} ΣRB = {BDR→ S,BDS → R}
Now RA1, RA2 and RB are in BCNF and thus S = {RA1, RA2, RB} is the BCNF decomposition of Appointment.
To verify whether S is dependency-preserving, we need to check whether:
( ⋃
R∈S
ΣR
)
?−→ {BCD → R}
4
So we check {BCD}+ under the collected FDs: {BCD}+ = {BCDS}+ = {BCDRS}. Since we can determine R
from BCD, this FD can be recovered and this decomposition is dependency-preserving.
NOTE: There may be different ways for BCNF decomposition depending on the order of FDs selected. This is just
one such possible decomposition.
Question 4 4 Marks
Consider the following database schema of a booking system.
CUSTOMER = {CustomerID, Name, Phone}
PK: {CustomerID}
EMPLOYEE = {EmployeeID, Name}
PK: {EmployeeID}
HOTEL = {HotelNo, RoomNo, Phone}
PK: {HotelNo, RoomNo}
BOOKING = {CID, EID, HNo, RNo, Date, Price}
PK: {CID, EID, HNo, RNo, Date}
FK: [CID] ⊆ CUSTOMER[CustomerID], EID ⊆ EMPLOYEE[EmployeeID],
[HNo, RNo] ⊆ HOTEL[HotelNo, RoomNo]
4.1 Answer the following question using relational algebra expressions. You are encouraged to use relational algebra
expressions to represent intermediate results if needed.
[a] Find all the employees who have never helped any customer to book rooms in a hotel named “WestWorld” (i.e.,
HNo = ‘WestWorld’). List their EmployeeIDs. (1 Mark)
πEmployeeID(EMPLOYEE)− πEID(σHNo=′WestWorld′(BOOKING))
5
[b] Find all the customers who have booked exactly one hotel room on 10-01-2019. List their CustomerIDs and names.
(1 Mark)
C1 = πCustomerID,Name(πCID(σDate=‘10−01−2019′(BOOKING)) 1CID=CustomerID CUSTOMER)
S2 = ρB1(BOOKING) 1(B1.CID=B2.CID)
∧
(B1.Date=B2.Date)
∧
((B1.HNo6=B2.HNo)
∨
(B1.RNo 6=B2.RNo)) ρB2(BOOKING)
C2 = πCustomerID,Name(CUSTOMER 1(CustomerID=B1.CID)
∧
(B1.Date=′10−01−2019′) S2)
Result = C1 − C2
4.2 Optimize the following relational algebra query (Your marks will depend on how well you present the key ideas of
query optimization in your answer). In addition to this, draw the query trees correspond to queries before and after
your optimisation.
πCustomerID,Name,Date,HNo(σ(CID=CustomerID)
∧
(HNo=HotelNo)
∧
(RNo=RoomNo)
∧
(Price>200)(BOOKING ×
CUSTOMER×Hotel)) (2 Mark)
Figure 1: Final query tree after optimising.
Question 5 1 Marks
Consider the relation schema R={A, B, C} and the following set Σ of FDs:
• A → B
• A → C
• B → A
• B → C
• C → A
• C → B
How many different minimal covers can be derived from Σ? List all the minimal covers that you can derive from Σ.
(1 Mark)
All FDs determine only one attribute and there are no redundant attributes on the determining side.
Now we can visualise the FDs in a graph as given below.
6
A
B C
We can remove different combinations of redundant FDs and obtain five minimal covers as shown below.
Minimal cover 1:
Considering A→ B and B → C, we can remove A→ C as it is redundant.
Considering C → B and B → A, we can remove C → A as it is redundant.
ΣM1 = {A→ B,B → C,C → B,B → A}
A
B C
Minimal cover 2:
Considering A→ C and C → B, we can remove A→ B as it is redundant.
Considering B → C and C → A, we can remove B → A as it is redundant.
ΣM2 = {A→ C,C → B,B → C,C → A}
A
B C
Minimal cover 3:
Considering C → A and A→ B, we can remove C → B as it is redundant.
Considering B → A and A→ C, we can remove B → C as it is redundant.
ΣM3 = {C → A,A→ B,B → A,A→ C}
A
B C
Minimal cover 4:
Considering A→ B and B → C, we can remove A→ C as it is redundant.
7
Considering C → A and A→ B, we can remove C → B as it is redundant.
Considering B → C and C → A, we can remove B → A as it is redundant.
ΣM4 = {A→ B,B → C,C → A}
A
B C
Minimal cover 5:
Considering C → B and B → A, we can remove C → A as it is redundant.
Considering A→ C and C → B, we can remove A→ B as it is redundant.
Considering B → A and A→ C, we can remove B → C as it is redundant.
ΣM5 = {A→ C,C → B,B → A}
A
B C
+++++
8