DATA BASE MANAGE SYS
DATA BASE MANAGE SYS COP 5725
Popular in Course
Popular in Computer Programming
Hans Farrell PhD
verified elite notetaker
This 9 page Class Notes was uploaded by Hans Farrell PhD on Friday September 18, 2015. The Class Notes belongs to COP 5725 at University of Florida taught by Markus Schneider in Fall. Since its upload, it has received 20 views. For similar materials see /class/206689/cop-5725-university-of-florida in Computer Programming at University of Florida.
Reviews for DATA BASE MANAGE SYS
Report this Material
What is Karma?
Karma is the currency of StudySoup.
Date Created: 09/18/15
What you should have learned after this lecture El what 3NF and BCNF are 75 Third Normal Form Definition El A relation schema R with associated FDs F is in third normal form 3NF if and only if it is in 2NF and for each FD A gt B e F at least one of the following conditions holds B g A ie the FD A gt B is trivial A is superkey of R B is part of some candidate key of R These conditions exclude nontrivial FDs between nonkey attributes That is transitive dependencies of the type A gt B and B gt C where A is candidate key B is no candidate key and C contains at least one nonkey attribute is forbidden The last condition is rather unintuitive but helps to ensure that every schema has a dependencypreserving decomposition into 3NF Example El relation lecturew title persid room El Relation is not in 3NF because the FD persid gt room exists and persid is not a key and room is not part of a candidate key El Possible anomalies Information about a professor and hisher room are not available without assign ment of a lecture update anomaly Change of the room number of a professor requires a change for each course with the same professor deletion anomaly If a professor does not hold a class any more all information about the professor and hisher room is removed from the database El solution Splitting of the schema lecture into the two schemas lecture title persid and Profpersid room El conclusion The 3NF eliminates the dependencies from nonkey attributes 3NF synthesis algorithm El goal decomposition of a relation schema R with the FDs F into relation schemas R1 Rn so that the following three criteria are fulfilled R1 Rn is a lossless decomposition of R The decomposition preserves the FDs The schemas R1 Rn each fulfil the 3NF synthesis algorithm for computing the decomposition on the basis of F step 1 determine a canonical cover FC for F ie left reduction of the FDs right reduction of the remaining FDs removal of FDs of the form A gt Q union rule for identical left sides step 2 for each FD A gt B 6 FC create a relation schema RA A u B assign the FDs FA C gt D e FC Cu DgRAtoRA step 3 If all schemas RA created in step 2 do not contain a candidate key of the original schema R additionally create a relation with the schema RK K and FK where K is a candidate key of R step 4 Eliminate schemas RA that are contained in another schema RAJ The result is not uniquely defined since a set of FDs can have more than one canon ical cover In some cases the result of the algorithm depends on the order in which it considers the dependencies in F0 Example for decomposition algorithm El relation schema ProfAddrpersid name rank room city street zipcode areacode state government El assumptions A city denotes the residence of a pro fessor Government is the party of the presi dent persId zip City names are unique Within a state code The zipcode does not change within a street ll Cities and streets lie completely in the W sin le states area 9 A professor has exactly one office that L he does not share government El persid and room are candidate keys of the relation ProfAddr The relation is not in 3NF since eg the FD city state gt areacode violates the 3NF CI step 1 computation of a canonical cover precomputed FD 1 persid gt name rank room city street state FD 2 room gt persid FD 3 city street state gt zipcode FD 4 city state gt areacode FD 5 state gt government FD 6 zipcode gt city state step 2 from FD 1 we obtain persid name rank room city street state FD 1 and FD 2 are assigned from FD 2 we obtain room persid FD 2 is assigned from FD 3 we obtain city street state zipcode FD 3 and FD 6 are assigned from FD 4 we obtain city state areacode FD 4 is assigned from FD 5 we obtain state government FD 5 is assigned from FD 6 we obtain zipcode city state FD 6 is assigned El step 3 Both room and persid are candidate keys of the original schema ProfAddr and are contained in a schema RA El step 4 room persid g persid name rank room city street state zipcode city state g city street state zipcode El We obtain gersid name rank room city street state FD 1 FD 2 city street state zipcode FD 3 FD 6 city state areacode FD 4 state government FD 5 76 Boyce Codd Normal Form CI CI A relation schema R with FDs F is in BoyceCodd normal form BCNF if and only if it is in 3NF and for each FD A gt B e F at least one of the following conditions holds B g A ie the FD A gt B is trivial A is superkey of R conclusion The BCNF eliminates dependencies among attributes that are part of a candidate key example Carlndexmanufacturer manufacturerid modelid consider FDs FD1 modelid manufacturer gt manufacturerid FD2 manufacturerid gt manufacturer example is in 3NF but not in BCNF CI The following anomalies can arise Insertion of the same manufacturer with different manufacturer ids and different model ids is possible 11relationship between manufacturer and manufacturerid is connected to modelid El properties of a schema in BCNF A relation schema R with associated FDs F can be decomposed into relation sche mas R1 Rn so that holds The decomposition is lossless The schemas R 1 g i g n are all in BCNF But We cannot always find a BCNF decomposition which is also dependencypre serving This case is seldom in practice El procedure decomposition of a schema from 3NF to BCNF Check if this decomposition is dependencypreserving If this is the case take this schema Otherwise use the original schema in 3NF example Producermanufacturerid manufacturer CarlndexNewmanufacturer modelid decomposition maintains FD2 but loses FD1 lossless join decomposition since Carlndex Producer lgtltl CarlndexNew