3NF and Boyce-Codd Normal FormWhat it’s all aboutSlide 3Primitive DomainsBad Database Design - redundancy of factBad Database Design - fact clutterBad Database Design - information lossSlide 8Bad Database Design - dependency lossGood Database DesignSlide 11Functional Dependencies and KeysSlide 13How to Compute Meaning - Armstrong’s inference rulesOverview of NFsNormal Forms - definitionsExample of NormalizationSlide 183NF that is not BCNFSlide 20The theoryExample 1Two possible keysExample 1aBCNF Every determinant is a candidate keyContinued…Rewrite to BCNFExample 1bSlide 29Summary - Example 1Example 2Example 2 cont...Slide 33Slide 34Slide 35Example 2: BCNFProblems BCNF overcomesSplit into two tablesReturning to the ER ModelVideo Library ExampleWhat NF is this?Test for 3NFRewrite for 3NFCheck BCNFSlide 45Slide 46Slide 47Slide 48Slide 49Slide 50Slide 51Slide 52Slide 53Slide 54Slide 55Slide 56Slide 57Slide 58Slide 59Slide 60Slide 61Slide 623NF 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.Primitive DomainsFLT-SCHEDULE flt# weekday airline dtime from atime to DL242 MO WE FR DELTA 10:40 ATL 12:30 BOSSK912 SA SU SAS 12:00 CPH 15:30 JFKAA242 MO FR AA 08:00 CHI 10:10 ATLAttributes must be defined over domains with atomic valuesFLT-SCHEDULE flt# weekday airline dtime from atime to DL242 MO DELTA 10:40 ATL 12:30 BOSSK912 SA SAS 12:00 CPH 15:30 JFKAA242 MO AA 08:00 CHI 10:10 ATLDL242 WE DELTA 10:40 ATL 12:30 BOSDL242 FR DELTA 10:40 ATL 12:30 BOSSK912 SU SAS 12:00 CPH 15:30 JFKAA242 FR AA 08:00 CHI 10:10 ATLBad Database Design- redundancy of factFLIGHTSflt# date airline plane#DL242 10/23/00 Delta k-yo-33297DL242 10/24/00 Delta t-up-73356DL242 10/25/00 Delta o-ge-98722AA121 10/24/00 American p-rw-84663AA121 10/25/00 American q-yg-98237AA411 10/22/00 American h-fe-65748•redundancy: airline name repeated for same flight•inconsistency: when airline name for a flight changes, it must be changed many placesBad Database Design- fact clutter•insertion anomalies: how do we represent that SK912 is flown by Scandinavian without there being a date and a plane assigned?•deletion anomalies: cancelling AA411 on 10/22/00 makes us lose that it is flown by American.•update anomalies: if DL242 is flown by Sabena, we must change it everywhere.FLIGHTSflt# date airline plane#DL242 10/23/00 Delta k-yo-33297DL242 10/24/00 Delta t-up-73356DL242 10/25/00 Delta o-ge-98722AA121 10/24/00 American p-rw-84663AA121 10/25/00 American q-yg-98237AA411 10/22/00 American h-fe-65748Bad Database Design- information lossFLIGHTSflt# date airline plane#DL242 10/23/00 Delta k-yo-33297DL242 10/24/00 Delta t-up-73356DL242 10/25/00 Delta o-ge-98722AA121 10/24/00 American p-rw-84663AA121 10/25/00 American q-yg-98237AA411 10/22/00 American h-fe-65748FLIGHTS-AIRLINEflt# airlineDL242 DeltaAA121 AmericanAA411 AmericanDATE-AIRLINE-PLANEdate airline plane#10/23/00 Delta k-yo-3329710/24/00 Delta t-up-7335610/25/00 Delta o-ge-9872210/24/00 American p-rw-8466310/25/00 American q-yg-9823710/22/00 American h-fe-65748Bad Database Design- information lossFLIGHTSflt# date airline plane#DL242 10/23/00 Delta k-yo-33297DL242 10/24/00 Delta t-up-73356DL242 10/25/00 Delta o-ge-98722AA121 10/24/00 American p-rw-84663AA121 10/25/00 American q-yg-98237AA211 10/22/00 American h-fe-65748AA411 10/24/00 American p-rw-84663AA411 10/25/00 American q-yg-98237AA411 10/22/00 American h-fe-65748DATE-AIRLINE-PLANEdate airline plane#10/23/00 Delta k-yo-3329710/24/00 Delta t-up-7335610/25/00 Delta o-ge-9872210/24/00 American p-rw-8466310/25/00 American q-yg-9823710/22/00 American h-fe-65748FLIGHTS-AIRLINEflt# airlineDL242 DeltaAA121 AmericanAA411 American•information loss: we polluted the database with false facts; we can’t find the true facts.Bad Database Design- dependency lossDATE-AIRLINE-PLANEdate airline plane#10/23/00 Delta k-yo-3329710/24/00 Delta t-up-7335610/25/00 Delta o-ge-9872210/24/00 American p-rw-8466310/25/00 American q-yg-9823710/22/00 American h-fe-65748FLIGHTS-AIRLINEflt# airlineDL242 DeltaAA121 AmericanAA411 American•dependency loss: we lost the fact that (flt#, date) plane#Good Database Design•no redundancy of FACT (!)•no inconsistency•no insertion, deletion or update anomalies•no information loss•no dependency lossFLIGHTS-DATE-PLANEflt# date plane#DL242 10/23/00 k-yo-33297DL242 10/24/00 t-up-73356DL242 10/25/00 o-ge-98722AA121 10/24/00 p-rw-84663AA121 10/25/00 q-yg-98237AA411 10/22/00 h-fe-65748FLIGHTS-AIRLINEflt# airlineDL242 DeltaAA121 AmericanAA411 AmericanLet 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 KeysFLIGHTSflt# date
View Full Document