Question 1
Because any super set of AB or BD are superkeys, so AB ABC ABD ABCD ABD CBD are all superkeys, there are 6 superkeys.
Question 2
2.1
The keys are AD, BCD, BED.
This is because the closure of AD, BCD, BED is the set of all attributes of R. Moreover, if removing any one attribute from AD, BCD, BED, the closure of the left attributes, does not contain all attributes of R.
Step: I first observe that D doesn’t appear in the right at any dependency, so the key must contain D. Then find AD’s closure contain all attributes, it is a key, no need to look for superset of AD, now look others to find BCD and BED.
2.2
The closure of CD is CDE, it doesn’t contain B, so Σ |=CD → B doesn’t hold. The following relation satisfies all the given functional dependencies but does not satisfy CD -> B.
A B C D E
4 3 1 2 5
5 4 1 2 5
2.3
Yes, A → E is redundant, because from A → C, C → E, we can infer A → E.
Question 3
（1）Yes, the decomposition is dependency-preserving. AB → C , AC → B is preserved in relation ABC,
BD → E is preserved in relation BCDE. From FD set {AB → C , AC → B, BD → E}, we can compute the closure of ACD is ABCDE, so ACD → E, thus the decomposition is dependency-preserving.
(2) The decomposition is not lossless. The intersection of ABC and BCDE is BC, the closure of BC is BC, so none of BC -> ABC and BC -> BCDE hold, thus it is not lossless.
The following relation conforms to all the FDs.
A B C D E
1 2 3 4 5
2 2 3 3 5
It decomposes into the following two relations.
A B C
1 2 3
2 2 3
B C D E
2 3 4 5
2 3 3 5
Join them, we can get the following relation, there are two additional rows apart from original two rows, so it is not lossless decomposition.
A B C D E
1 2 3 4 5
1 2 3 3 5
2 3 3 4 5
2 2 3 3 5
Question 4
4.1
No, it is not a good design.
Problem1: data duplication. For example, suppose a employer has 1000 candidates, then we need to store the employer information in 1000 rows in the table under this schema.
Problem2: If we need to change one employer information, we need to change every row that contains this employer information.
4.2
Let S := {Job_Application}
Step 1
The determinant of fd4 is not the super key. Decompose Job_Application into two relations:
R1 = {Employer_Name, Employer_Address, Number_of_Employees}
Σ1={ fd4}
R2 = {Candidate_Name, Candidate_DoB, Candidate_Email, Candidate_EducationLevel Job_No, Job_Position, Job_Type, Job_Salary, Job_Location, Closing_Date, Employer_Name, Application_Date, Application_Documents}
Σ2 ={ fd1, fd2, fd3, fd6}
we have S:={R1, R2}.
Step 2
Now R2 still not in BCNF, because the determinant of the fd6 is not a
superkey with respect to Σ2. Decompose the R2 into two relations:
R21 = {Candidate_Name, Candidate_DoB, Candidate_Email, Job_No, Application_Date, Application_Documents}
Σ21 = {fd6}
R22 = {Candidate_Name, Candidate_DoB, Candidate_Email, Candidate_EducationLevel Job_No, Job_Position, Job_Type, Job_Salary, Job_Location, Closing_Date, Employer_Name}
Σ22 = {fd1, fd2, fd3}.
we have S:={R1, R21, R22}.
Step 3
Now, R22 still not in BCNF, because the determinant of the fd1 is not a superkey with respect to Σ22. Replace R22 in S by two relations :
R221 = {Candidate_Email, Candidate_Name, Candidate_DoB, Candidate_EducationLevel} with
Σ221 = {fd1, fd2}
R222 = {Candidate_Email, Job_No, Job_Position, Job_Type, Job_Salary, Job_Location, Closing_Date, Employer_Name}
Σ222 = {fd3}
we have S:={R1, R21, R221, R222}.
Step 4
Now, R222 still not in BCNF, because the determinant of the fd3 is not a superkey with respect to Σ222. Replace R222 in S by two relations :
R2221 = {Job_No} → {Job_Position, Employer_Name,Job Type,Job_Salary,Closing_Date}
Σ2221 = {fd3}
R2222 = {Candidate_Email, Job_No, Job_Location }
Σ2222 = {}
Step 5
Finaly, we have S:={R1, R21, R221, R2221, R2222}, each relation is in BCNF. Σ1= {fd4} , Σ21 = {fd6}, Σ221 = {fd1, fd2}, Σ2221 = {fd3}, Σ2222 = {}.
This decomposition is lossless, which is ensured by the algorithm.
Σ1∪ Σ21 ∪ Σ221 ∪ Σ2221∪ Σ2222 = {fd1, fd2, fd3, fd4, f6}， and because we can’t infer from
{fd1, fd2, fd3, fd4, f6} to fd5, so this decomposition can preserve all functional dependencies except for FD5.
4.3
Job_Application 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. (FD5) {Employer_Address} → {Job_Location} is problematic, because {Employer_Address} is not super key and Job_Location is not primary attribute.
First, Compute minimal cover. in FD1, attribute Candidate_EducationLevel is redundant, remove it. In FD6, left
side attributes Candidate_Name and Candidate_DoB are redundant, remove them. After these modifications:
FD1 = {Candidate_Name, Candidate_DoB} → {Candidate_Email},
FD6 = {Candidate_Email, Job_No} →{Application_Date, Application_Documents}
The others are the same. Now it is the minimal cover, one candidate key is {Candidate_Email, Job_No, Employer_Name}.
Now for each FD X→Y, create a relation with schema XY. So
R1 = {Candidate_Name, Candidate_DoB, Candidate_Email} with {FD1}
R2 = {Candidate_Email, Candidate_Name, Candidate_DoB, Candidate_EducationLevel} with {FD1, FD2}
R3 = {Job_No, Job_Position, Employer_Name,Job Type,Job_Salary,Closing_Date}; with {FD3}
R4 = {Employer_Name, Employer_Address, Number_of_Employees}; with {FD4}
R5 = {Employer_Address, Job_Location}; with {FD5}
R6 = {Candidate_Email, Job_No, Application_Date, Application_Documents} with {FD6}
Because R1 is a subset of R2, so remove it. Because none of the schemas created so far contains a key, so add add a relation schema containing a key. One candidate key is {Candidate_Email, Job_No, Employer_Name}.
So R7 = {Candidate_Email, Job_No, Employer_Name}.
Now the decomposition finished.
S = {R2, R3, R4, R5, R6, R7}.
The above decomposition into 3NF is lossless and dependency preserving.
4.4
Yes, we should consider 3NF instead of BCNF. Because 3NF can preserve all function dependencies.