(2)2007 Fall CS157A Midterm 3 Study GuideProf. Sin-Min LeeNov. 27, Tuesday The exam will be comprehensive. Test material will be drawn from the text book, lecture, assignments and any supplementary material provided in class.You should review the following: - all the lecture notes - all the assigned readings 1.Know the basis of the mathematical relation and the properties of a relation. 2.Know the characteristics of superkey, candidate key, primary key, and foreign key. 3.Know the rules of relational integrity and referential integrity. 4.Be able to recognize and read relational algebra statements with the primary operators. 5.Be able to recognized simple relational calculus statements (like the ones used in class) andunderstand the difference between the algebra and SQLs. Know the significance of theselanguages with respect to communicating with a DBMS and maintaining independence. 6.Understand the use of foreign key in implementing a relationship. 7. Review closure of attributes and closure algorithm. 8.1NF,2 NF,3 NF and BCNF. Understand "Fully Dependent" and "Transitive Dependency" 9. 4NFTry to work on the following problems:(1)(2)(3) 3.Try to express the above querries in SQL.(5) Consider relation R with attributes ABCD:a) Is R in BCNF with functional dependencies AB→C, AB→D? Why, or why not?Key is AB (AB+=ABCD). For both f.d. left side is key, therefore R is in BCNF.b) Is R in BCNF with functional dependencies A→B, A→C, A→D, D→C? Why, or why not? A is a key. A→B, A→C, A→D doesn't violate BCNF (left side is key). D→C violatesBCNF rule (D is not a key). Therefore, R is not in BCNF. For D→C, the right side (C) isnot part of a key, therefore also violates 3NF rule. So, R is not even in 3NF.c) Is R in 3NF with functional dependencies A→BCD, D→A? Why, or why not?A and D are keys.So, both f.d. do not violate BCNF rule. Therefore, R is in 3NF as well.d) Is R in 3NF with functional dependencies A→BC, A→D, D→B? Why, or why not?A is the key. A→BC, A→D do not violate (left side is a key), D→B violates 3NF, since Dis not a key, B is not part of a key. So, R is not in 3NF.e) For (a) and (b), if any one of those cases is not in BCNF, decompose ABCD into BCNFrelations.(b) is not BCNF, so we decompose. Since A→B, A→C, A→D are OK, but D→Cviolates BCNF, we decompose R using lossless join decomposition rule (X→A violates,R is decomposed into XA and R-A relations) into R1=CD and R2=ABD. R1 is in BCNFsince only D→C applies and D is a key. R2 is in BCNF since only A→B, A→D applyand A is the key (A+=ABD).6.Consider a relation R(A,B,C). Suppose R contains the following four tuples: A B C 1 2 3 1 2 4 5 2 3 5 2 6(a) List all completely nontrivial functional dependencies that hold on this instance of R. - (b) List all nontrivial multivalued dependencies that hold on this instance of R.(7) Use Armstrong's axioms to prove the union rule: A - B and A - C imply A- BC (8) Assume the schema R (A,B,C,D, E, F) and functional dependencies FD1.A- BD, FD2. B - C, FD3. E -F.1. Is there a candidate key for R? What?2. Find A+: 3.Which of the following functional dependencies are implied by the above?Prove one of them.a. A - B: b. B - A c. A - C: (9)(10) CITY TRAFFIC FINE DATA BASE (1)Assume that the police officer will not usually come in contact with the offender.(2)that the amount of fine is not printed on the ticket (which would be strange). (3)There is only one registered owner (name) possible per auto.(4) The ticket numbers are printed on the tickets and are unique. Name Auto license Transgression Fine Date Ticket# Smith, C MVX 322 Parking 15.00 03/12/86 1023 Wesley RVX 287 Red light 50.00 04/15/85 233 Smith, C MVX 322 Parking 15.00 03/12/86 397 Smith, C TGY 832 Parking 15.00 03/12/86 1025 Smith, C TGY 832 Spitting 15.00 03/12/86 1028Simmons, R SKINNY Backing-in 65.00 12/25/85 328 Simmons, R SKINNY Spitting 15.00 03/12/86 1125Decide whether this table is in 3 NF ?11. Given the relation Book(Book_title, Authorname, Book_type, Listprice, Author_affil, Publisher) and the FDs Book_title --> Publisher, Book_type Book_type --> Listprice Authorname --> Author_affil(a) Find the key of this database.(b) Decide whether it is in 3NF?12. Armstrong’s Axioms are stated as:F1 (Reflexivity): X - XF2 (Augmentation): X - Y implies XZ - YF3 (Transitivity): X - Y and Y - Z imply X - ZProve (Pseudotransitivity) : X - Y and YZ - W imply XZ - W using only F1, F2 and F3.. 13. Consider the relation schema R = (A, B, C, D, E) and the set of functional dependencies: 1.AD - BE 2.CD - E 3.B -AE 4.AE-C 5.C - D a)List all of the candidate keys for R. There are four: B, AC, AD, and AE. (Hint: to generate,calculate closures of single attributes, thengroups of two that do notcontain a key, then groups of three, etc.) b) The attribute set ABCDE is not a candidate key of R. Why not? Lots of reasons, for example since B is a key, anything containing B cannot be a candidate key (it canbe a super key, but this is not the question). 14.15. We have the relation R (ABCD) with FDs AB--C, C-D, D-A. Explain why this relation is not inBCNF, but is in 3NF16. Armstrong’s Axioms are stated as:F1 (Reflexivity): X - XF2 (Augmentation): X - Y implies XZ - YF3 (Transitivity): X - Y and Y - Z imply X - ZProve (Pseudotransitivity) : X - Y and YZ - W imply XZ - W using only F1, F2 and F3.17. (a) Is the following relation in 3 NF? R(A, B, C, D, E, F, G, H) AàB, C, D, EDàEFàG, H (b)Decompose R into relations that are in at least 4 NF.18. Given the following functional dependencies of R(A B C D E)FD1 A-BDFD2 BC-EFD3 D-AEDecide whether the decomposition R1(A B D), R2(BCE), R3(A C D) is lossless?19. Decide whether the following relational schema R(A B C D) is BCNF?FD1. A-B DFD2. B - CFD3. C - A20. Decide whether A->>CD in this table A B C D 1 1 0 2 2 1 2 1 1 3 2 1 1 4 0 2 1 4 2 1 2 3 2 2 2 4 1
View Full Document