CMSC424 Database Design Instructor Amol Deshpande amol cs umd edu Today Project Relational Database Design Goal We want a mechanism for Deciding whether a relation R is in a good form Has no redundancy etc If R is not in good form decompose it into a set of relations R1 R2 Rn such that Each relation is in good form The decomposition is a lossless join decomposition Dependencies are preserved optional All dependencies can be checked within a single relation Approach We will encode and list all our knowledge about the schema somehow Functional dependencies FDs SSN name SSN implies length If two tuples have the same SSN they must have the same name movietitle length Not true But movietitle movieYear length True We will define a set of rules that the schema must follow to be considered good Normal forms 1NF 2NF 3NF BCNF 4NF Rules specify constraints on the schemas and FDs Functional Dependencies Let R be a relation schema R and R The functional dependency holds on R iff for any legal relations r R whenever two tuples t1 and t2 of r have same values for they have same values for t1 t2 t1 t2 1 1 3 A 4 5 7 B On this instance A B does NOT hold but B A does hold Today Mechanisms and definitions to work with FDs Closures candidate keys canonical covers etc Armstrong axioms Decompositions Loss less decompositions Dependency preserving decompositions BCNF How to achieve a BCNF schema BCNF may not preserve dependencies 3NF Solves the above problem BCNF allows for redundancy 4NF Solves the above problem 1 Closure Given a set of functional dependencies F its closure F is all FDs that are implied by FDs in F e g If A B and B C then clearly A C Armstrong s Axioms We can find F by applying Armstrong s Axioms if then reflexivity if then augmentation if and then transitivity These rules are sound generate only functional dependencies that actually hold and complete generate all functional dependencies that hold Additional rules If and then union If then and decomposition If and then pseudotransitivity The above rules can be inferred from Armstrong s axioms Example R A B C G H I F A B A C CG H CG I B H Some members of F A H by transitivity from A B and B H AG I by augmenting A C with G to get AG CG and then transitivity with CG I CG HI by augmenting CG I to infer CG CGI and augmenting of CG H to infer CGI HI and then transitivity 2 Closure of an attribute set Given a set of attributes A and a set of FDs F closure of A under F is the set of all attributes implied by A In other words the largest B such that A B Redefining super keys The closure of a super key is the entire relation schema Redefining candidate keys 1 It is a super key 2 No subset of it is a super key Computing the closure for A Simple algorithm 1 Start with B A 2 Go over all functional dependencies in F 3 If B then Add to B 4 Repeat till B changes Example R A B C G H I F A B A C CG H CG I B H AG 1 result AG 2 result ABCG 3 result ABCGH 4 result ABCGHI A C and A B CG H and CG AGBC CG I and CG AGBCH Is AG a candidate key 1 It is a super key 2 A BC G G YES Uses of attribute set closures Determining superkeys and candidate keys Determining if A B is a valid FD Check if A contains B Can be used to compute F 3 Extraneous Attributes Consider F and a functional dependency A B Extraneous Are there any attributes in A or B that can be safely removed Without changing the constraints implied by F Example Given F A C AB CD C is extraneous in AB CD since AB C can be inferred even after deleting C 4 Canonical Cover A canonical cover for F is a set of dependencies Fc such that F logically implies all dependencies in Fc and Fc logically implies all dependencies in F and No functional dependency in Fc contains an extraneous attribute and Each left side of functional dependency in Fc is unique In some vague sense it is a minimal version of F Read up algorithms to compute Fc Today Mechanisms and definitions to work with FDs Closures candidate keys canonical covers etc Armstrong axioms Decompositions Loss less decompositions Dependency preserving decompositions BCNF How to achieve a BCNF schema BCNF may not preserve dependencies 3NF Solves the above problem BCNF allows for redundancy 4NF Solves the above problem Loss less Decompositions Definition A decomposition of R into R1 R2 is called lossless if for all legal instance of r R r R1 r R2 r In other words projecting on R1 and R2 and joining back results in the relation you started with Rule A decomposition of R into R1 R2 is lossless iff R1 R2 R1 in F or R1 R2 R2 Dependency preserving Decompositions Is it easy to check if the dependencies in F hold Okay as long as the dependencies can be checked in the same table Consider R A B C and F A B B C 1 Decompose into R1 A B and R2 A C Lossless Yes But makes it hard to check for B C The data is in multiple tables 2 On the other hand R1 A B and R2 B C is both lossless and dependency preserving Really What about A C If we can check A B and B C A C is implied Dependency preserving Decompositions Definition Consider decomposition of R into R1 Rn Let Fi be the set of dependencies F that include only attributes in Ri The decomposition is dependency preserving if F1 F2 Fn F Today Mechanisms and definitions to work with FDs Closures candidate keys canonical covers etc Armstrong axioms Decompositions Loss less decompositions Dependency preserving decompositions BCNF How to achieve a BCNF schema BCNF may not preserve dependencies 3NF Solves the above problem BCNF allows for redundancy 4NF Solves the above problem BCNF Given a relation schema R and a set of functional dependencies F if every FD A B is either 1 Trivial 2 A is a superkey of R Then R is in BCNF Boyce Codd Normal Form Why is BCNF good BCNF What if the schema is not in BCNF Decompose split the schema into two pieces Careful you want the decomposition to be lossless Achieving BCNF Schemas For all dependencies A B in F check if A is a superkey By using attribute closure If not then Choose a dependency in F that breaks the BCNF rules say A B Create R1 A B Create R2 A R B A Note that R1 R2 A and A AB R1 so this is lossless decomposition Repeat for R1 and R2 By defining F1 to be all …
View Full Document
Unlocking...