Research School of Computer Science, The Australian National University COMP2400/COMP6240 – Relational Databases
2016, Semester 2
Lab 5, Week 7
FDs and Normalisation (Solutions)
The purpose of this lab is to deepen your understanding of functional dependencies (FDs) and two normal forms: 3NF and BCNF.
To motivate the study of FDs, we start with discussing several update anomalies that may occur when database design allows the existence of redundant data. Then we will practice on finding keys, determining implied FDs and computing minimal covers. To help you understand the normal forms 3NF and BCNF, we will do some exercises on a normalisation example.
By the end of this week’s lab session, you should have a clear idea about answering the following questions:
1
• • • • • •
What are functional dependencies?
How can we find keys by computing the closure of attributes?
How can we determine implied functional dependencies?
What is a minimal cover and how to compute it?
Why are FDs needed for normalisations?
What is BCNF? What is 3NF? What are the differences between 3NF and BCNF?
Update Anomalies
(1). Consider the relation shown in Figure 1 which has the primary key {SSN, Pnumber} together with the following functional dependencies. What update anomalies may occur in the relation? Give an example if possible.
{SSN} → {EmployeeName} and {Pnumber} → {ProjectName,Plocation}
SSN
Pnumber
Hours
EmployeeName
ProjectName
Plocation
11
1
32.5
Smith
Newbenefit
Bellaire
11
2
7.5
Smith
Databases
Sugarland
22
3
40
Narayan
Softwares
Houston
33
1
20
English
Newbenefit
Bellaire
33
2
7.5
English
Databases
Sugarland
Figure 1: A relation for Exercise (1)
Solution:
The FDs {SSN} → {EmployeeName} and {Pnumber} → {ProjectName,Plocation} can cause the anomalies. For example,
• If a project temporarily has no employees working on it, its information (Pnum- ber,ProjectName, Plocation) will not be represented in the database when the last employee working on it is removed (deletion anomaly).
• A new project cannot be added unless at least one employee is assigned to work on it (insertion anomaly).
• Changing the name of a project or an employee requires us to update every tuple that records the name of this project or employee (modification anomaly).
The reason for the occurrence of these anomalies is that the given relation represents the relationship between employees and projects, and at the same time represents in- formation concerning the entities employee and project.
2 Inspection Example
Consider the following relation of the relation schema Inspection held at the MyHome real estate agency:
2
PropertyNo
Address
Date
Time
StaffNo
StaffName
CameraID
PR4
6 Masson St
18-Oct-11
10:00
S137
Mike Jenk
C211
PR16
8 Berry St
22-Apr-12
09:00
S114
Sue Wang
C323
PR4
6 Masson St
01-Oct-13
12:00
S114
Sue Wang
C323
PR16
8 Berry St
21-Apr-12
13:00
S114
Sue Wang
C323
A set Σ of FDs for representing the business rules of Inspection is as follows:
– fd1: {PropertyNo} → {Address};
– fd2: {StaffNo} → {StaffName};
– fd3: {PropertyNo, Date} → {StaffNo, Time};
– fd4: {StaffNo, Date} → {CameraID};
– fd5: {StaffNo, Date, Time} → {PropertyNo};
– fd6: {Date, Time, CameraID} → {PropertyNo}.
(2). Find all the keys and prime attributes w.r.t. Σ. Solution: The keys are:
• {PropertyNo, Date};
• {Date, Time, CameraID}; • {StaffNo, Date, Time}.
This is because the closure of {Date, PropertyNo}, {Date, Time, CameraID} or {StaffNo, Date, Time} is the set of all attributes of Inspection, with respect to Σ. Moreover, if removing any one attribute from {Date, PropertyNo}, {Date, Time, CameraID} or {StaffNo, Date, Time}, the closure of the left attributes, e.g., {PropertyNo} or {Date} for {Date, PropertyNo}, does not contain all attributes of Inspection.
The prime attributes are: Date, Time, PropertyNo, StaffNo and CameraID. The non- prime attributes are: StaffName and Address.
(3). Does {StaffNo} → {CameraID} hold on any relation of Inspection that satisfies Σ? If so, explain why; otherwise, give a counterexample.
Solution:
No, {StaffNo} → {CameraID} does not hold. This can be proven by computing the clo- sure of (StaffNo)+ in terms of Σ, i.e., (StaffNo)+ ={StaffNo, StaffName} and CameraID ∈/ (StaffNo)+.
A counterexample can be made by adding two tuples into the relation that satisfies all the given functional dependencies but does not satisfy {StaffNo} → {CameraID}.
3
PropertyNo
Address
Date
Time
StaffNo
StaffName
CameraID
PR4
6 Masson St
01-Oct-13
12:00
S114
Sue Wang
C323
PR16
8 Berry St
21-Apr-12
13:00
S114
Sue Wang
C100
(4). Is the given set of FDs minimal? If not, give a minimal cover. Solution: It’s not minimal. One possible solution is as follows:
• {StaffNo} → {StaffName};
• {PropertyNo} → {Address};
• {PropertyNo, Date} → {StaffNo};
• {PropertyNo, Date} → {Time};
• {StaffNo, Date} → {CameraID};
• {Date, Time, CameraID} → {PropertyNo}.
The steps are as follows:
Starting with the given set Σ of FDs,
• by Step 2 of the algorithm, we replace {PropertyNo, Date} → {StaffNo, Time} with {PropertyNo, Date} → {StaffNo} and {PropertyNo, Date} → {Time}. Then
we have: {{StaffNo} → {StaffName}, {PropertyNo} → {Address}, {PropertyNo, Date} → {StaffNo}, {PropertyNo, Date} → {Time}, {StaffNo, Date} → {CameraID}, {StaffNo, Date, Time} → {PropertyNo}, {Date, Time, CameraID} → {PropertyNo}};
• by Step 3 of the algorithm, we still have the same set of FDs as in the previous step;
• by Step 4 of the algorithm, we calculate the closure of the determinant of a FD in terms of other FDs, if the closure contains the dependent of the FD, then the FD is redundant and can be removed. In doing so, we can only remove {StaffNo, Date, Time} → {PropertyNo} because the closure of {StaffNo, Date, Time} in terms of the other FDs contains PropertyNo.
After the above three steps, we can obtain the minimal cover.
4
(5). Is Inspection in 3NF w.r.t. Σ? If not, determine a lossless and dependency preserving 3NF decomposition. Are the relation schemas you have obtained in the de- composition in BCNF? Justify your answers.
Solution:
Inspection is not in 3NF w.r.t. Σ. This can be verified by testing each FD: X → A defined on Inspection: either X is a superkey or A is a prime attribute. In accor- dance with the results in Exercise (2), it is clear that {PropertyNo} → {Address} and {StaffNo} → {StaffName} are problematic. Using the minimal cover in Exercise (3) and Algorithm 15.6 from the text book, we may decompose Inspection into the following relation schemas.
• Staff={StaffNo, StaffName} with the FD: {StaffNo} → {StaffName};
• Property={PropertyNo, Address} with the FD: {PropertyNo} → {Address};
• Inspection1={PropertyNo, Date, StaffNo, Time} with the FD: {PropertyNo, Date} → {StaffNo, Time};
• Inspection2={StaffNo, Date, CameraID} with the FD: {StaffNo, Date} → {CameraID};
• Inspection3={PropertyNo, Date, Time, CameraID} with the FDs: {PropertyNo,
Date} → {Time} and {Date, Time, CameraID} → {PropertyNo}. The above decomposition into 3NF is lossless and dependency preserving.
The relation schemas Staff, Property, Inspection1 and Inspection2 are in BCNF, but Inspection3 is not due to {PropertyNo, Date} → {Time}.
(6). Does Inspection satisfy BCNF w.r.t. Σ? If not, determine a lossless decomposi- tion for Inspection into BCNF. Does your decomposition preserve all dependencies of Inspection? If not, think about whether these exists a better approach that can nor- malise Inspection into BCNF such that all dependencies in Σ can still be preserved.
Solution:
• Since the determinants of the FDs: {PropertyNo} → {Address}, {StaffNo} → {StaffName} and {StaffNo, Date} → {CameraID} are not superkeys, Inspection doesn’t satisfy BCNF.
• By applying Algorithm 15.5 from the text book, – Let S := {Inspection}.
5
•
•
3 3.1
– SinceInspectionisnotinBCNF,wepicktheFD:{PropertyNo}→{Address} that violates BCNF, and replace Inspection in S by two relation schemas R1={PropertyNo, Date, Time, StaffNo, StaffName, CameraID} with Σ1 ={ fd2, fd3, fd4, fd5, fd6} and R2={PropertyNo, Address} with Σ2 = {fd1}. So we have S:={R1, R2}.
– Now we easily see that R1 is still not in BCNF because the determinant of the FD: {StaffNo} → {StaffName} is not a superkey with respect to Σ1. Replace R1 in S by two relations R11={PropertyNo, Date, Time, StaffNo, CameraID} with Σ11 = {fd3, fd4, fd5, fd6} and R12={StaffNo, StaffName} with Σ12 = {fd2}.
– Now we can still see that R11 is not in BCNF because the determinant of the FD: {StaffNo, Date} → {CameraID} is not a superkey with respect to Σ11. Replace R11 in S by two relations R111={PropertyNo, Date, Time, StaffNo} with Σ111 = {fd3, fd5} and R112={StaffNo, Date, CameraID} with Σ112 = {fd4}.
– Finally, we have S:= {R111, R112, R2, R12}, each of relations in S is in BCNF.
This decomposition is lossless, which is ensured by the algorithm. However fd6 isn’t preserved in the above BCNF decomposition of Inspection because it can- not be inferred from Σ111 ∪ Σ112 ∪ Σ2 ∪ Σ12.
In this case, no BCNF decomposition of Inspection can preserve all functional dependencies (i.e., fd1-fd6).
Functional Dependencies Finding Keys
Consider a relation R = {A, B, C, D} with the following FDs: C → D, AB → C and D → A
(7). List all the candidate keys of R.
Solution:
There are three candidate keys of R (obtained by computing closures of subsets of of R)
• {A,B} is a key because (AB)+ = ABCD, (A)+ = A and (B)+ = B. 6
• {B,C} is a key because (BC)+ = ABCD, (C)+ = ACD and (B)+ = B. • {B,D} is a key because (BD)+ = ABCD, (D)+ = AD and (B)+ = B.
(8). Find all the prime attributes of R. Solution:
All the attributes of R are also prime attributes.
3.2 Determining Implied Functional Dependencies
Consider a relation schema R = {A, B, C, D, E, F } with the following set Σ of functional dependencies:
AB → C, CF → B, BC → AD and D → E.
(9). Does AB → D hold on any relation of R that satisfies Σ? If so, explain why;
otherwise, give a counterexample.
Solution:
Yes, AB → D holds. There are two approaches to show this:
• compute the closure of AB, i.e.,
(AB)+= AB = ABC
= ABCD • by formal proof:
by AB → AB byAB→C byBC→AD
AB → B AB → BC AB → AD AB → D
by reflexivity
by union and the given FD AB → C
by transitivity and the given FD BC → AD decomposition
Remark: Compare the above two approaches and observe that the first approach is usually simpler than the second approach.
(10). Does B → C hold on any relation of R that satisfies Σ? If so, explain why; otherwise, give a counterexample.
7
Solution:
No, B → C does not hold. This can be proven by computing the closure of B in terms
of Σ. Since (B)+ = B and C ∈/ (B)+, B → C does not hold.
A counterexample can be made by adding two tuples into the relation that satisfies all
the given functional dependencies but does not satisfy B → C.
3.3 Computing a Minimal Cover
Consider a relation R = {A, B, C, D}. For each set of FDs given below, identity whether or not the set of FDs is a minimal cover. If not, find a minimal cover for the set of FDs.
(11). {A→B, A→C}.
Solution: it’s a minimal cover.
(12). {A→B,A→CB,B→C}.
Solution: it’s not a minimal cover. A minimal cover should be {A → B, B → C}. (13). {A→B,B→A,B→C}.
Solution: it’s a minimal cover.
Remember to log off before you leave (Click the log-out button on the front panel).
A
B
C
D
E
F
1 2
1 1
1 2
2 2
1 1
1 2
8