assign5KeyForStudents

pdf

School

Case Western Reserve University *

*We aren’t endorsed by this school

Course

310

Subject

Computer Science

Date

Jan 9, 2024

Type

pdf

Pages

Uploaded by CountWorld12684

Fall 2023 CSDS 341 Introduction to Database Systems Prof. Dianne Foreback Assignment 5 Key – No Points Earned on this assignment 1 of 8 Please submit your assignment in Canvas. 0. To prepare for the final, make certain you can do the practice exercises from the book 7.1, 7.2 7.6, 7.9 the first part of the question, 7.10, 7.13 and make certain that you understand 7.18 transitive dependency and 3 rd Normal Form and in 7.19 partial dependencies. These questions and answers are available from the book site here . Recall, all solutions to practice exercises are here https://www.db-book.com/Practice-Exercises/index-solu.html 1. Given two relations A and B, consider that the primary key of A can functionally determine the primary key of B. Write this as pk(A) → pk(B). Also consider that pk(B) → pk(A). Is this a one-to- one, one-to-many, many-to-one, or many-to-many relationship. Explain. An answer: By definition, since pk(A) determines pk(B) there is only one value for B for each A. And by definition, since pk(B) determines pk(A) there is only one value for A for each B. Thus, this is one-to-one. 2. Consider the relation R(A,B,C,D,E) with the set of functional dependencies F={A → B, B → C, E → B, CD → A} and its decomposition to the relations 𝑅 1 (?, ?, ?), 𝑅 2 (?, ?, ?)𝑎?? 𝑅 3 (?, ?). Is this a lossy or lossless decomposition? Explain. To receive credit for this, you MUST show your work and EXPLAIN why it is lossy/lossless. Recall: determining if a decomposition is lossless/lossy requires the binary operation of natural join and using the closure of the intersection of two relations. We will do a similar problem in class on Wed. Nov 29 th , 2023. Show the relations used for each natural join and closure. An answer: Show something like this: 𝑅 1 ∩ 𝑅 2 = ? ???? ? + = {?????}??𝑖?𝑔 ?? 𝑁?, ?𝑖??? ? + = ? ???𝑦. Show something like this: Try a different permutation. 𝑅 1 ∩ 𝑅 3 = ?? ???? ?? + 𝑔𝑖?? ??? ??𝑖?𝑔 ?? 𝑁?, ?? + = {???}??𝑖?𝑔 ?. Show something like this: Try the third permutation: 𝑅 2 ∩ 𝑅 3 = ????𝑦 ??? ?? ??.

Fall 2023 CSDS 341 Introduction to Database Systems Prof. Dianne Foreback Assignment 5 Key – No Points Earned on this assignment 2 of 8 3. Consider the relation R(A, B, C, D, E, F, G, H) and the set of functional dependencies F = { AD → BCF, A → G, BC → E, D → F, E → H, E → D} . You must give the 3 candidate keys and show your work. Candidate keys are AE, AD and ABC Below is a more detailed explanation with the answer/work/explanation given. a. What are the candidate keys per this relation based on the set of functional dependencies? Your work must be shown by explaining how you logically reduced the closure ???????? + to a smaller proper subset using Armstrong Axioms and Inference rules. Then, you must show the closure of the candidate keys and show no proper subset can be a candidate key. Answer: There are many different ways that the student reduces the initial closure. Make certain that they give an Armstrong Axioms or Inference rule for each reduction. I will give you an example. Armstrong Axioms are: reflexive or trivially, augmentation, transitivity Armstrong Inference Rules are: union, composition, decomposition, pseudo-transitivity My example: ABCDEFGH+ can omit H since E → H. This yields ABCDEFG+ ABCDEFG+ can omit BCF since AD → BCF. This yields ADEG+ ADEG+ can omit G since A → G . This yields ADE+. ADE+ can omit D since E → D. This yields AE+ Check superkey AE to see if it is a candidate Key. AE+ = ABCDEFGH so definitely a super key. A+ = AG and since A+ <> ABCDEFGH it is not a super key or candidate key. E+ = EDH and since E+ <> ABCDEFGH it is not a superkey. Therefore, AE is a candidate key. Since BC → E we have another superkey ABC. We need to check if any subset of ABC is a candidate key. ABC+ = ABCDEFGH (so, we verified it is a superkey). AB+ = ABG and since it is not ABCDEFGH, AB+ is not a candidate key. AC+ = ACG and since it is not ABCDEFGH, AC+ is not a candidate key. BC+ = BCDEH and since it is not ABCDEFGH, BC+ is not a candidate key. Therefore, ABC is a candidate key. Since (AD → BCF and D → F), we can reduce this to (AD → BC and D → F). From our candidate key ABC, we can replace BC with AD due to AD → BC. Thus AD is a super key. AD+=ABCDEFGH, thus verified it is indeed a superkey. Are any subsets of AD a potential superkey? A+ = AG so A is not a superkey D+ = DF so D is not a superkey. Thus AD is a candidate key.

Fall 2023 CSDS 341 Introduction to Database Systems Prof. Dianne Foreback Assignment 5 Key – No Points Earned on this assignment 3 of 8 b. From your answer in part a, what are the prime attributes? Answer: ABCDE are the prime attributes 4. Consider the relation R(A, B, C, D, E, F, G, H) and the set of functional dependencies F = { AD → BCF, A → G, BC → E, D → F, E → H}. Notice, this is the same relation from above but the set of functional dependencies in this example is missing the functional dependency E → D from above. Students, I am providing a high level answers typed but you must also show your work. Some of the work is shown at the end of this problem that is handwritten. After these high level answers, I provide you with my handwritten notes for solving parts 4c – 4i (my full work may not be shown, but you should show yours please, especially if given on a test). a. What are the candidate keys? Again, show your work as done for part 3a. Answer: Again, many ways to show. Mine follows. ABCDEFGH+ since E → H omit H and get ABCDEFG (trivially/reflexive) ABCDEFG since BC → E omit E and get ABCDFG (trivially/reflexive) ABCDFG since A → G omit G and get ABCDF ( trivially/reflexive) ABCDF since AD → BCF omit BCG and get AD (trivially/reflexive) No further reductions possible. Verify AD is a superkey by taking its closure:AD+ = ABCDEFGH so yes a super key Are any subsets of AD a superkey. If no then AD is a candidate key. A+ = AG so A not a superkey D+ = DF so D not a superkey. Thus, AD is a candidate key. b. This relation is not in 2 nd Normal Form (2NF). Why? Explain by giving the rule(s) that are broken and how the rule(s) with example(s) are broken via this relation and F. Answer: This is not in 2NF since AD is a candidate key and the only one so it is also the primary key. Since A → G and D → F we have two partial dependencies, thus not in 2NF. c. Decompose this relation to 2NF (but not 3NF). Show your work and include the necessary closures and the new set of functional dependencies that are derived for each decomposition. You will be using the new set of functional dependencies later in this problem for a couple more questions. Answer: (I provide more info on my handwritten notes) R1(A, G) R2(D, F) R3(A,D, B, C, E, H) F1={A → G} F2={D → F} F3={AD → BC, BC → E, E → H}

Your preview ends here

Eager to read complete document? Join bartleby learn and gain access to the full version

Access to all documents
Unlimited textbook solutions
24/7 expert homework help

Fall 2023 CSDS 341 Introduction to Database Systems Prof. Dianne Foreback Assignment 5 Key – No Points Earned on this assignment 4 of 8 d. After applying the rule(s) to normalize from 1NF to 2NF, why is the decomposition not in 3NF? Explain by giving the rule(s) that are not satisfied with the example(s) from your decomposition. Answer: Because of the transitive dependencies in R3, BC → E and E → H I provide more info on my handwritten notes) e. Give the decomposition from 2NF to 3NF. Again, show your work and provide the necessary closures and the new set of functional dependencies that are derived for each decomposition. Answer: R31(A D B C) R32(B C E ) R33(E H) F31{AD → BC} F32{BC → E} F33{E → H} f. Is the decomposition from part e also in BCNF? Explain why/why not. Answer: “It is in BCNF because there are no non -prime attributes that determine a prime attribute” g. Draw the Relational Schema from part f underlining the primary keys and drawing the arrow to represent foreign key constraints. Answer: see my hand written h. Consider that we placed the functional dependency E → D back into the set of functional dependencies F and assume that you arrived at the decomposition from part e. Will this decomposition be in BCNF? Explain why/why not. You do not have to go through the steps for decomposition with this functional dependency E → D in the set of functional dependencies, just think about this and explain the rule that this violates. Answer: Adding E → D back into the set of functional dependencies and considering R2(BCE) we could have a non-prime attribute E determining a prime attribute D. This violates BCNF. More detail to explain this to the students. The reason this occurs is that by adding E → D back into the set of functional dependencies, we end up with problem 3. There are multiple candidate keys and multiple ways to decompose the relation to its normal forms. i. Is the decomposition from part e (2NF to 3NF) a dependency preserving decomposition? Show your work and explain why/why not. You will need to take union of the set of derived functional dependencies from your decomposition, call this set G, and show that G covers F. Show your work for credit.

Fall 2023 CSDS 341 Introduction to Database Systems Prof. Dianne Foreback Assignment 5 Key – No Points Earned on this assignment 5 of 8 The new set of functional dependencies is G. G = F1 U F2 U F31 U F32 U F33 = {A → G, D → F, AD → BC, BC → E, E → H} Recall F = { AD → BCF, A → G, BC → E, D → F, E → H}. The student must show for each functional dependency in F, that the determinants closure using G yields the dependent from F. That is, for each functional dependency in F, the closure of left side of the functional dependency using G gives the right side. Answer. AD → BCF since AD+ using G gives ADGFBCEH so this includes BCF. We are good. A → G directly in G BC → E directly in G D → F directly in G E → H directly in G Students, notice, this one is relatively simple to show since many of the functional dependencies are directly in G. If they are not, find the closure such as done with AD → BCF.

Fall 2023 CSDS 341 Introduction to Database Systems Prof. Dianne Foreback Assignment 5 Key – No Points Earned on this assignment 6 of 8 生

Your preview ends here

Eager to read complete document? Join bartleby learn and gain access to the full version

Access to all documents
Unlimited textbook solutions
24/7 expert homework help

Fall 2023 CSDS 341 Introduction to Database Systems Prof. Dianne Foreback Assignment 5 Key – No Points Earned on this assignment 7 of 8

Fall 2023 CSDS 341 Introduction to Database Systems Prof. Dianne Foreback Assignment 5 Key – No Points Earned on this assignment 8 of 8

assign5KeyForStudents

Related Documents