3 10 11 Normal Forms CISC437 637 Lecture 9 Ben Cartere e Copyright Ben Cartere e 1 Normal Forms Normal forms help determine whether a relaGon is subject to logical inconsistencies and anomalies There is a series of normal forms of increasing strictness and lower chance of inconsistency First normal form 1NF Third normal form 3NF Boyce Codd normal form BCNF Fourth Rh sixth normal forms 4NF 5NF 6NF Copyright Ben Cartere e 2 1 3 10 11 First Normal Form 1NF is the simplest normal form A relaGon is in 1NF if all of its elds contain only atomic values No lists or sets Our de niGon of a relaGon implies 1NF holds by default By enforcing domain constraints we guarantee every relaGon is in 1NF Copyright Ben Cartere e 3 Redundancy Revisited We touched on redundancy in the context of database design decisions Redundancy is an extremely important consideraGon in those decisions Redundant storage can be a problem The real problem is maintaining the data during inserts updates deletes Anything that modi es redundant data has to be sure to modify every copy of that data or inconsistencies can be introduced Redundancy can be quite subtle hard to detect It doesn t strictly mean duplicate informaGon Copyright Ben Cartere e 4 2 3 10 11 Does This RelaGon Instance Contain Redundancy Copyright Ben Cartere e 5 FuncGonal Dependencies A func onal dependency is a type of integrity constraint related to relaGon keys Field s X func onally determine eld s Y if for every possible instance r of relaGon R for any two tuples t1 t2 in r if X t1 X t2 then Y t1 Y t2 We write X Y to indicate funcGonal dependency FuncGonal dependencies are statements about all possible relaGon instances If K is a candidate key K R Copyright Ben Cartere e 6 3 3 10 11 RelaGon DecomposiGon When an FD of the form B CD is idenG ed replace relaGon ABCD with relaGons AB and BCD QuesGons Is the decomposiGon necessary Will the decomposiGon create new problems Answers Normal forms of schema can help determine Problems might include inability to retrieve data lossy join loss of power to enforce constraints worse DBMS performance due to more joins Copyright Ben Cartere e 7 FDs and Normal Forms Higher order normal forms 3NF and higher are related to redundancy FuncGonal dependencies describe redundancy Thus funcGonal dependencies will be used to determine which form a relaGon is in To do this we will need to a way to check all funcGonal dependencies in a relaGon Copyright Ben Cartere e 8 4 3 10 11 Reasoning About FDs Two FDs may imply that a third FD holds Simple example A B and B C A C The closure of a set F of FDs denoted F is the set of all FDs implied by the set F GeneraGng the closure is an algorithmic process of repeated applicaGon of rules For sets of elds X Y Z in schema R Re exivity if X Y then X Y Augmenta on if X Y then XZ YZ for any Z Transi vity if X Y and Y Z then X Z Copyright Ben Cartere e 9 Reasoning About FDs Two more useful rules Union if X Y and X Z then X YZ Decomposi on if X YZ then X Y and X Z Example closure Schema Contracts contracGd supplierid projecGd depGd parGd qty value FDs from enterprise requirements C CSJDPQV le ers map to elds in order Project purchases a given part using a single contract JP C A department purchases at most one part from a suppler SD P Copyright Ben Cartere e 10 5 3 10 11 Boyce Codd Normal Form A relaGon R with funcGonal dependencies F is in BCNF if for all X A in F A X a trivial FD or X is a superkey i e X contains a key Or R is in BCNF if the only non trivial FDs are key constraints No dependency in R that can be predicted using FDs alone Copyright Ben Cartere e 11 TesGng for BCNF CompuGng F is exponenGal in number of a ributes If we just want to check if a given FD X Y is in the closure there is an e cient algorithm Compute a4ribute closure of X denoted X wrt F X is the set of all elds A such that X A is in F Check if Y is in X If it is then X Y is in F Copyright Ben Cartere e 12 6 3 10 11 TesGng for BCNF Given a nontrivial dependency X A compute a ribute closure X and verify that it includes all a ributes of R If so X is a superkey and the FD does not violate BCNF Otherwise the FD does violate BCNF Use the above process to check each FD in F It no FD in F violates BCNF then no FD in F violates BCNF either Copyright Ben Cartere e 13 Decomposing into BCNF If R is a relaGon with FDs F and X Y in F violates BCNF then decompose R into R Y and XY Do this iteraGvely unGl all relaGons are in BCNF The order this is done could result in di erent sets of relaGons but all will be in BCNF no ma er what Copyright Ben Cartere e 14 7 3 10 11 RelaGon DecomposiGons In general a relaGon R with a ributes A1 A2 An is decomposed by replacing R with two or more new relaGons such that Each new relaGon schema contains a subset of a ributes of R and no other a ributes Every a ribute of R is an a ribute of at least one of the new relaGons Copyright Ben Cartere e 15 Possible Problems with DecomposiGons Four main problems could arise Queries become more expensive more joins required means more potenGal cross products Original data may be unrecoverable Checking dependencies may require joining decomposed relaGons Loss of power to model constraints These issues must always be considered against the possibility of anomalies due to redundancy Copyright Ben Cartere e 16 8 3 10 11 Lossless DecomposiGons DecomposiGon of R to R1 R2 is lossless join with respect to a set of FDs F if for every instance r that saGs es F R1 r R2 r r Note that r R1 r R2 r is always true As long as all decomposiGons are lossless original data will always be recoverable Copyright Ben Cartere e 17 Lossless DecomposiGons De ne lossless join in terms of a closure F of a set of FDs F DecomposiGon of R into R1 R2 is lossless join w r t F if and only if F contains R1 R2 R1 or R1 R2 R2 A decomposiGon of R into UV and R V is lossless join if U V is a FD on R Therefore BCNF decomps are always lossless join Copyright Ben Cartere e 18 9 3 10 11 Dependency Preserving DecomposiGon If R decomposes into R1 R2 R3 and FDs on those three relaGons are enforced then FDs …