CMSC424: Database DesignToday…GoalApproachFunctional DependenciesToday…1. ClosureArmstrong’s AxiomsAdditional rulesExample2. Closure of an attribute setComputing the closure for ASlide 13Uses of attribute set closures3. Extraneous Attributes4. Canonical CoverSlide 17Loss-less DecompositionsDependency-preserving DecompositionsSlide 20Slide 21BCNFSlide 23Achieving BCNF SchemasExample 1Example 2-1Example 2-2Example 3Slide 29BCNF may not preserve dependenciesSlide 31Slide 323NFSlide 343NF and redundancyDecomposing into 3NFSlide 37BCNF and redundancyMulti-valued DependenciesSlide 404NFComparing the normal formsDatabase design processDBMS at a glanceSlide 45CMSC424: Database DesignInstructor: Amol Deshpande [email protected]…ProjectRelational Database DesignGoalWe 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 decompositionDependencies are preserved (optional)All dependencies can be checked within a single relationApproachWe 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 FDsFunctional DependenciesLet R be a relation schema R and RThe 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 [ ] On this instance, A B does NOT hold, but B A does hold.1 41 53 7A BToday…Mechanisms and definitions to work with FDsClosures, candidate keys, canonical covers etc…Armstrong axiomsDecompositionsLoss-less decompositions, Dependency-preserving decompositionsBCNFHow to achieve a BCNF schemaBCNF may not preserve dependencies3NF: Solves the above problemBCNF allows for redundancy4NF: Solves the above problem1. 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 CArmstrong’s AxiomsWe 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 rulesIf and , then (union)If , then and (decomposition)If and , then (pseudotransitivity)The above rules can be inferred from Armstrong’s axioms.ExampleR = (A, B, C, G, H, I)F = { A B A CCG HCG I B H}Some members of F+A H •by transitivity from A B and B HAG 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 transitivity2. Closure of an attribute setGiven a set of attributes A and a set of FDs F, closure of A under F is the set of all attributes implied by AIn other words, the largest B such that:A BRedefining super keys:The closure of a super key is the entire relation schemaRedefining candidate keys:1. It is a super key 2. No subset of it is a super keyComputing the closure for ASimple algorithm1. Start with B = A.2. Go over all functional dependencies, , in F+3. If B, thenAdd to B4. Repeat till B changesExampleR = (A, B, C, G, H, I)F = { A B A CCG HCG I B H}(AG) + ? 1. result = AG2. result = ABCG (A C and A B)3. result = ABCGH (CG H and CG AGBC)4. result = ABCGHI (CG I and CG AGBCHIs (AG) a candidate key ? 1. It is a super key. 2. (A+) = BC, (G+) = G. YES.Uses of attribute set closuresDetermining superkeys and candidate keysDetermining if A B is a valid FDCheck if A+ contains BCan be used to compute F+3. Extraneous AttributesConsider 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 FExample: Given F = {A C, AB CD}C is extraneous in AB CD since AB C can be inferred even after deleting C4. Canonical CoverA 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, andNo functional dependency in Fc contains an extraneous attribute, andEach left side of functional dependency in Fc is uniqueIn some (vague) sense, it is a minimal version of FRead up algorithms to compute FcToday…Mechanisms and definitions to work with FDsClosures, candidate keys, canonical covers etc…Armstrong axiomsDecompositionsLoss-less decompositions, Dependency-preserving decompositionsBCNFHow to achieve a BCNF schemaBCNF may not preserve dependencies3NF: Solves the above problemBCNF allows for redundancy4NF: Solves the above problemLoss-less DecompositionsDefinition: 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 withRule: A decomposition of R into (R1, R2) is lossless, iff: R1 ∩ R2 R1 or R1 ∩ R2 R2 in F+.Dependency-preserving DecompositionsIs 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 CThe 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
View Full Document