http://www.vacic.org/lib/sql/notes/normal.pdf

1 NormalizationCIS 331: Introduction to Database SystemsVladimir Vacic, Temple University2 Normalization: Reminder Why do we need to normalize? To avoid redundancy (less storage space needed, and data is consistent) To avoid update/delete anomaliesVladimir Vacic, Temple University3 Normalization: ReminderSsn c-id GradeNameAddress123 cs331 Asmith Main123 cs351 Bsmith Main123 cs211 Asmith Main Clearly, Name and Address are redundant(larger relation + you have to update 3 rows to update the Address)Vladimir Vacic, Temple University4 Normalization: Reminder Insertion anomaly:Cannot make a record Jones address because he is not taking any classesSsn c-id Grade Name Address123 cs331 Asmith null null jones ForbesVladimir Vacic, Temple University5 Normalization: Reminder Delete anomaly:Cannot delete Shmoo s enrolment without loosing his address as wellSsn c-id GradeNameAddress123 cs331 Ajones 123 Main124 cs351 Bsmith 124 Broad125 cs211 Ashmoo 42 PennVladimir Vacic, Temple University6 Normal Forms First Normal Form 1NF Second Normal Form 2NF Third Normal Form 3NF Fourth Normal Form 4NF Fifth Normal Form 5NF(so far conveniently named) Boyce-Codd Normal Form BCNFV ladimir Vacic, Temple University7 First Normal Form (1NF) 1NF.

2 All attributes are atomic( no repeating groups )AnneMichaelRumpelstiltskinPeterMaryJohn SmithFirst NameLast NameNot in 1 NFVladimir Vacic, Temple University8 First Normal Form (1NF)AnneMichaelRumpelstiltskinRumpelsti ltskinPeterMaryJohnSmithSmithSmithFirst NameLast NameNormalized to 1 NFVladimir Vacic, Temple University9 First Normal Form (1NF)Not in 1NF195 kgMetatron165 lbUriel201 lbGabriel192 lbRaphael187 lbMichaelWeightNameVladimir Vacic, Temple University10 First Normal Form (1NF)Normalized to 1 NFkg195 Metatronlb165 Uriellb201 Gabriellb192 Raphaellb187 MichaelUnitWeightNameVladimir Vacic, Temple University11 First Normal Form (1NF)P2, P3S3P3S2P1, P3, P4S1 PartSupplierNot in 1 NFVladimir Vacic, Temple University12 First Normal Form (1NF)nullP3 P2S3nullnullP3S2P4P3P1S1 Part3 Part2 Part1 SupplierIs this relation in 1NF?Formally yes, but in essence, NO!Vladimir Vacic, Temple University13 First Normal Form (1NF)P2P3S3S3P3S2P1P3P4S1S1S1 PartSupplierNormalizedto 1NF Vladimir Vacic, Temple University14 Second Normal Form (2NF) 2NF: 1NF and all non-key attributes are fully dependent on the PK ( no partial dependencies )212 Reykjavik Odin Olafson Ericsson in 2 NFVladimir Vacic, Temple University15 Second Normal Form (2NF)ACIS362 HildurCCIS331 IngeBCIS331 SvenACIS331 ErikGradeCourse_IDStudent212 Reykjavik Freya Olafson Ericsson 2NF Vladimir Vacic, Temple University16 Second Normal Form (2NF)AddressGradeCourse_IDStudentVladimi r Vacic, Temple University17 Third Normal Form (3NF)3NF: 2NF and no transitive in 3 NFVladimir Vacic, Temple University18 Third Normal Form (3NF) to 3 NFVladimir Vacic, Temple University19 Third Normal Form (3NF)ValueGradeCourse_IDStudentVladimir Vacic, Temple University20 BCNF: Reminder Informally:Everything depends on the full key, and nothing but the key Formally.

3 For every FD a bin F+ a bis trivial (ais a superset of b) or ais a superkey (or both)Vladimir Vacic, Temple University21 Normal forms: BCNF vs. 3NF If a relation is in BCNF, it is always in 3NF (but not the converse) In practice, aim for BCNFIf that s impossible, we accept 3NF; but we insist on lossless join and dependency preservationVladimir Vacic, Temple University22 Normal forms: BCNF vs. 3NF Let s consider the classic example:STC (Student, Teacher, Course)Teacher CourseStudent, Course TeacherIs it in BCNF?StudentTeacherCourseVladimir Vacic, Temple University23 Normal forms: BCNF vs. 3 NFSTC (Student, Teacher, Course)Teacher Course Student, Course Teacher1) (Teacher, Course) (Student, Course)(BCNF? Y+Y- Lossless? No- Dep. No)2) (Teacher, Course) (Student, Teacher) (BCNF? Y+Y - Lossless? Yes - Dep. No)Vladimir Vacic, Temple University24 Normal forms: BCNF vs. 3 NFSTC (Student, Teacher, Course)Teacher Course Student, Course Teacherin this case it is impossible to have both BCNF and dependency preservationSo we have to use the (weaker) Vacic, Temple University25 Normal forms: BCNF vs.

4 3 NFSTC (Student, Teacher, Course)Teacher Course Student, Course TeacherSCTI nformally, 3NF forgives the red arrow Vladimir Vacic, Temple University26 Normalization: Examples342P4 Paris10 KohlS7(null)P3 London12 SpiritosoS2125P4 Paris10 JonesS1500P1 Paris10 JonesS1257P3 Paris10 JonesS1 QtyPartCityStatus_CityNameSupplier Start by determining functional dependencies!Vladimir Vacic, Temple University27 Normalization: ExampleFDs Supplier Name Supplier City Status_City Supplier Status_City (Supplier, Part) QtyPartial Dependencies (Supplier, Part) Name (Supplier, Part) City (Supplier, Part) Status_CityVladimir Vacic, Temple University28 Normalization: ExampleParis10 KohlS7 London12 SpiritosoS2 Paris10 JonesS1 CityStatus_CityNameSupplier342P4S7(null) P3S2125P4S1257P3S1500P1S1 QtyPartSupplierVladimir Vacic, Temple University29 Normalization: Example We took care of the partial dependencies, but what about transitive dependencies?Paris10 KohlS7 London12 SpiritosoS2 Paris10 JonesS1 CityStatus_CityNameSupplierVladimir Vacic, Temple University30 Normalization: ExampleParisKohlS7 LondonSpiritS2 ParisJonesS1 CityNameSupplier342P4S7(null)P3S2125P4S1 257P3S1500P1S1 QtyPartSupplier12 London10 ParisStatus_CityCityVladimir Vacic, Temple University31 Normalization: Examples Silberschatz et al.

5 : (lossless-join decomposition)hint: use the theorem! A decomposition is a lossless-join decomposition if the joining attribute is a superkey in at least one of the new relations (lossless-join decomposition) (dependency-preserving decomposition)Vladimir Vacic, Temple University32 Normalization: Final Thoughts There are higher normal forms (4NF, 5NF), but we will not talk about them In practice, normalized means in BCNF or 3NF Luckily, in practice, ER diagrams lead to normalized tables (but do not rely on luck)Vladimir Vacic, Temple University33 Normalization: Overview Why do we normalize? To avoid redundancy (less storage space needed, and data is consistent) To avoid update/delete anomalies A good decomposition should: be a lossless join decomposition (you can recover original tables with a join) preserve dependencies (FD s should not span two tables)Vladimir Vacic, Temple University34 Normalization: Overview Boyce-Codd Normal Form (BCNF): Everything should depend on the key, the wholekey, and nothing butthe key (so help me Codd joke attributed to Date ) 1NF (all attributes are atomic) 2NF (no partial dependencies) 3NF (no transitive dependencies)