3NF and Boyce-Codd Normal FormSlide 2Slide 3Slide 4Slide 5Slide 6Slide 7What it’s all aboutSlide 9Slide 10Slide 11Slide 12Slide 13How to Compute Meaning - Armstrong’s inference rulesOverview of NFsNormal Forms - definitionsSlide 17Slide 18Slide 19Slide 203NF that is not BCNFSlide 22The theoryExample 1Two possible keysExample 1aBCNF Every determinant is a candidate keyContinued…Rewrite to BCNFExample 1bSlide 31Summary - Example 1Example 2Example 2 cont...Slide 35Slide 36Slide 37Example 2: BCNFProblems BCNF overcomesSplit into two tablesReturning to the ER ModelVideo Library ExampleWhat NF is this?Test for 3NFRewrite for 3NFCheck BCNFSlide 47Slide 483NF and Boyce-Codd Normal FormProf. Sin-Min LeeDepartment of Computer ScienceSan Jose State UniversityWhat it’s all about•Given a relation, R, and a set of functional dependencies, F, on R. •Assume that R is not in a desirable form for enforcing F.•Decompose relation R into relations, R1,..., Rk, with associated functional dependencies, F1,..., Fk, such that R1,..., Rk are in a more desirable form, 3NF or BCNF.•While decomposing R, make sure to preserve the dependencies, and make sure not to lose information.Let X and Y be sets of attributes in R•Y is functionally dependent on X in R iff for each x R.X there is precisely one y R.Y•Y is fully functional dependent on X in R if Y is functional dependent on X and Y is not functional dependent on any proper subset of X•We use keys to enforce functional dependencies in relations:X YX YFunctional Dependencies and KeysHow to Compute Meaning- Armstrong’s inference rulesRules of the computation:–reflexivity: if YX, then X Y–Augmentation: if X Y, then WX WY–Transitivity: if XY and YZ, then XZDerived rules:–Union: if XY and XZ, the XYZ–Decomposition: if XYZ, then X Y and XZ–Pseudotransitivity: if XY and WYZ, then XW ZArmstrong’s Axioms:–sound–completeOverview of NFsNF21NF2NF3NFBCNFNormal Forms- definitions•NF: non-first normal form•1NF: R is in 1NF. iff all domain values are atomic2•2NF: R is in 2. NF. iff R is in 1NF and every nonkey attribute is fully dependent on the key•3NF: R is in 3NF iff R is 2NF and every nonkey attribute is non-transitively dependent on the key•BCNF: R is in BCNF iff every determinant is a candidate key•Determinant: an attribute on which some other attribute is fully functionally dependent.3NF that is not BCNFABCCandidate keys: {A,B} and {A,C} Determinants: {A,B} and {C}A decomposition:Lossless, but not dependency preserving!A B CRC BR1A CR2•When a relation has more than one candidate key, anomalies may result even though the relation is in 3NF.•3NF does not deal satisfactorily with the case of a relation with overlapping candidate keys–i.e. composite candidate keys with at least one attribute in common.•BCNF is based on the concept of a determinant.–A determinant is any attribute (simple or composite) on which some other attribute is fully functionally dependent.•A relation is in BCNF is, and only if, every determinant is a candidate key.The theory•Consider the following relation and determinants.Example 1. Given R(a,b,c,d)a,c -> b,da,d -> b•To be in BCNF, all valid determinants must be a candidate key. In the relation R, a,c->b,d is the determinate used, so the first determinate is fine.•Example 2. If {a, b} is not a key, a,d->b suggests that a,d can be the primary key, which would determine b. However this would not determine c. This is not a candidate key, and thus R is not in BCNF.Example 1Patient NoPatient Name Appointment Id Time Doctor1 John 0 09:00 Zorro2 Kerr 0 09:00 Killer3 Adam 1 10:00 Zorro4 Robert 0 13:00 Killer5 Zane 1 14:00 ZorroTwo possible keys•DB(Patno,PatName,appNo,time,doctor)•Determinants:–Patno -> PatName–Patno,appNo -> Time,doctor–Time -> appNo•Two options for 1NF primary key selection:– DB(Patno,PatName,appNo,time,doctor) (example 1a)– DB(Patno,PatName,appNo,time,doctor) (example 1b)Example 1a•DB(Patno,PatName,appNo,time,doctor) •No repeating groups, so in 1NF•2NF – eliminate partial key dependencies:–DB(Patno,appNo,time,doctor)–R1(Patno,PatName) •3NF – no transient dependences so in 3NF•Now try BCNF.BCNF Every determinant is a candidate keyDB(Patno,appNo,time,doctor)R1(Patno,PatName) •Is determinant a candidate key?–Patno -> PatNamePatno is present in DB, but not PatName, so irrelevant.Continued…DB(Patno,appNo,time,doctor)R1(Patno,PatName) –Patno,appNo -> Time,doctorAll LHS and RHS present so relevant. Is this a candidate key? Patno,appNo IS the key, so this is a candidate key. –Time -> appNoTime is present, and so is appNo, so relevant. Is this a candidate key? If it was then we could rewrite DB as: DB(Patno,appNo,time,doctor)This will not work, so not BCNF.Rewrite to BCNF•DB(Patno,appNo,time,doctor)R1(Patno,PatName) •BCNF: rewrite to DB(Patno,time,doctor) R1(Patno,PatName) R2(time,appNo)•time is enough to work out the appointment number of a patient. Now BCNF is satisfied, and the final relations shown are in BCNFExample 1b•DB(Patno,PatName,appNo,time,doctor) •No repeating groups, so in 1NF•2NF – eliminate partial key dependencies:–DB(Patno,time,doctor)–R1(Patno,PatName) –R2(time,appNo)•3NF – no transient dependences so in 3NF•Now try BCNF.BCNF Every determinant is a candidate keyDB(Patno,time,doctor)R1(Patno,PatName) R2(time,appNo)•Is determinant a candidate key?–Patno -> PatNamePatno is present in DB, but not PatName, irrelevant.–Patno,appNo -> Time,doctorNot all LHS present so not relevant–Time -> appNoTime is present, but not appNo, so not relevant. –Relations are in BCNF.Summary - Example 1This example has demonstrated three things:•BCNF is stronger than 3NF, relations that are in 3NF are not necessarily inBCNF•BCNF is needed in certain situations to obtain full understanding of the data model•there are several routes to take to arrive at the same set of relations in BCNF.–Unfortunately there are no rules as to which route will be the easiest one to take.Example 2Grade_report(StudNo,StudName,(Major,Adviser,(CourseNo,Ctitle,InstrucName,InstructLocn,Grade)))•Functional dependencies–StudNo -> StudName–CourseNo -> Ctitle,InstrucName–InstrucName -> InstrucLocn–StudNo,CourseNo,Major -> Grade–StudNo,Major -> Advisor–Advisor -> MajorExample 2
View Full Document
Unlocking...