CS计算机代考程序代写 algorithm Exercise 3 – Solution

Exercise 3 – Solution
Q1.

No, AB+ = {A,B,C},a proper subset of {A,B,C,D,E}

Yes, ABD+ = {A,B,C,D,E}

Q2.

Let us use the following shorthand notation:

C = CourseNo, SN = SecNo, OD = OfferingDept, CH = CreditHours, CL = CourseLevel,

I = InstructorSSN, S = Semester, Y = Year, D = Days_Hours, RM = RoomNo,

NS = NoOfStudents

Hence, R = {C, SN, OD, CH, CL, I, S, Y, D, RM, NS}, and the following functional

dependencies hold:

{C} -> {OD, CH, CL}

{C, SN, S, Y} -> {D, RM, NS, I}

{RM, D, S, Y} -> {I, C, SN}

First, we can calculate the closures for each left hand side of a functional dependency,

since these sets of attributes are the candidates to be keys:

(1) {C}+ = {C, OD, CH, CL}

(2) Since {C, SN, S, Y} -> {D, RM, NS, I}, and {C}+ = {C, OD, CH, CL}, we get:

{C, SN, S, Y}+ = {C, SN, S, Y, D, RM, NS, I, OD, CH, CL} = R

(3) Since {RM, D, S, Y} -> {I, C, SN}, we know that {RM, D, S, Y}+ contains {RM, D, S,

Y, I, C, SN}. But {C}+ contains {OD, CH, CL} so these are also contained in {RM, D, S,

Y}+ since C is already there. Finally, since {C, SN, S, Y} are now all in {RM, D, S, Y}+

and {C, SN, S, Y}+ contains {NS} (from (2) above), we get:

{RM, D, S, Y}+ = {RM, D, S, Y, I, C, SN, OD, CH, CL, NS} = R

Hence, both K1 = {C, SN, S, Y} and K2 = {RM, D, S, Y} are (candidate) keys of R.

Q3.

(a)The key for this relation is Book_title,Authorname. This relation is in 1NF and not in 2NF as no

attributes are FFD on the key. It is also not in 3NF.

(b)

3NF decomposition:

Book0(Book_title, Authorname)

Book1-1(Book_title, Publisher, Book_type)

Book1-2(Book_type, Listprice)

Book2(Authorname, Author_affil)

Q4.

(a)

– {M} IS NOT a candidate key since it does not functionally determine attributes Y or P.

– {M, Y} IS a candidate key since it functionally determines the remaining attributes P, MP,

and C.

– {M, C} IS NOT a candidate key since it does not functionally determine attributes Y or P.

(b)

REFRIG is not in 2NF, due to the partial dependency {M, Y} -> MP (since {M} -> MP

holds). Therefore REFRIG is neither in 3NF nor in BCNF.

Alternatively: BCNF can be directly tested by using all of the given dependencies and

finding out if the left hand side of each is a superkey (or if the right hand side is a prime

attribute). In the two fields in REFRIG: M -> MP and MP -> C. Since neither M nor MP is a

superkey, we can conclude that REFRIG is is neither in 3NF nor in BCNF.

(c) Yes. Please follow the algorithm provided in the lecture notes.

Q5.

1) List the candidate keys for 𝑅.

EH/ABH/BDH/CDH

2) Determine the highest normal form of 𝑅 with respect to 𝐹.

1NF. Non-prime attribute 𝐺 is functionally determined by 𝐷.

3) Is the decomposition {𝐴𝐵𝐶𝐷, 𝐷𝐸𝐺𝐻} (with the same FD set 𝐹) of 𝑅 lossless-join?

No.

Decomposition A B C D E G H

𝑅1(𝐴, 𝐵, 𝐶, 𝐷) a a a a b b b

𝑅2(𝐷, 𝐸, 𝐺, 𝐻) b b b a a a a

Decomposition A B C D E G H

𝑅1(𝐴, 𝐵, 𝐶, 𝐷) a a a a b a b

𝑅2(𝐷, 𝐸, 𝐺, 𝐻) a b b a a a a

4) Find a minimal cover 𝐹𝑚 for 𝐹.

𝐹𝑚 = {𝐴𝐵 → 𝐶, 𝐷 → 𝐴, 𝐷 → 𝐺, 𝐸 → 𝐵, 𝐴𝐵 → 𝐷, 𝐸 → 𝐴, 𝐶𝐷 → 𝐸}

5) Decompose into a set of 3NF relations if it is not in 3NF. Make sure your decomposition is

dependency-preserving and lossless-join.

For 𝐹𝑚 = {𝐴𝐵 → 𝐶, 𝐷 → 𝐴, 𝐷 → 𝐺, 𝐸 → 𝐵, 𝐴𝐵 → 𝐷, 𝐸 → 𝐴, 𝐶𝐷 → 𝐸} :

From 𝐴𝐵 → 𝐶, 𝐴𝐵 → 𝐷, derive 𝑅1{𝐴, 𝐵, 𝐶, 𝐷}

From 𝐷 → 𝐴, 𝐷 → 𝐺, derive 𝑅2{𝐴, 𝐷, 𝐺}

From 𝐸 → 𝐵, 𝐸 → 𝐴, derive 𝑅3{𝐴, 𝐵, 𝐸}

From 𝐶𝐷 → 𝐸, derive 𝑅4{𝐶, 𝐷, 𝐸}

None of the relation schemas contains a key of 𝑅, add one relation schema 𝑅5{𝐸, 𝐻}

6) Decompose it into a collection of BCNF relations if it is not in BCNF. Make sure your

decomposition is lossless-join.