Normalization 3NF And BCNF - Computer Science

Normalization3NF and BCNFCS 4750Database Systems[A. Silberschatz, H. F. Korth, S. Sudarshan, Database System Concepts, Ch.7][Ricardo and Urban, Database Illuminated, Ch.6][ on/ ]Fall 2020 – University of Virginia Praphamontripong1

Recap: NormalizationGoals: Reduce redundancy Improve data integrity Queries are logical and efficientDecomposition: Three properties that must satisfied Lossless join decomposition – avoid data corruption No gain/no loss Dependency preserving – improve performance No joins needed to check a dependency Remove duplication – keep size and structure of DB stable Minimize redundant data in a tableFall 2020 – University of Virginia Praphamontripong2

3NF and Decomposition Lossless-join Always dependency preserving Possible to have extra data (there may be redundancy)Questions:Is the relation in 3NF?Is any refinement needed?To calculate 3NF Take Canonical Cover (Fc) Turn (minimal set of) FDs into tablesFall 2020 – University of Virginia Praphamontripong3

Canonical Cover (Fc) A minimal set of functional dependencies that has thesame closure as the original set F Extraneous attributes attribute of FDs that we canremoved without changing the closure of FDs F logically implies all dependencies in Fc Fc logically implies all dependencies in FF and F arelogicallyequivalent No FD in Fc contains an extraneous attributeMinimal basis for a set of FDs: For any set of FDs, there is at least oneminimal basis, which is a set of FDs equivalent to the original (each setimplies the other set), with singleton right sides, no FD that can be eliminatedwhile preserving equivalence, and no attribute in a left side that can beeliminated while preserving equivalenceFall 2020 – University of Virginia Praphamontripong4

Canonical Cover (Fc)Compute the canonical cover of a set of functional dependencies FAlways start with F and use rules to minimizeFc Frepeatapply union rule to replace any dependencies f: X1 à Y1and f: X1 à Y2 with f: X1 à Y1Y2for each functional dependency fiif fi contains an extraneous attribute either in X or in Ythen remove an extraneous attributeuntil Fc does not change any furtherFall 2020 – University of Virginia Praphamontripong5

Example 1: 3NF and FcLet’s do this togetherR(A,B,C,D,E)FDs { A à B, AB à D, B à BDE, C à D, D à D }Compute Fc and convert the relation into 3NFGivenCompute Fc without using reflexivity(1) write all LHSABABCDààààà(2) copy FDs as isABABCDàààààBB DEDDD(3) removereflexivityAà BBà BAB àCàD àDEDDD(4) removeextraneousAà BBàAB àCàattrDEDDA à B and B à D.Thus, remove AB à DFall 2020 – University of Virginia Praphamontripong6

Example 1: 3NF and FcLet’s do this togetherSuper key(from previous page)(4) Removeextraneous attrAà BBàDECàDTurn Fc into tablesABBDECDA relation R(A, B, C, D, E) is converted into 3NF by puttingLHS and RHS of each FD in Fc together in one relation.Dependency preservingR(A, B, C, D, E) becomes R1(A, B) and R2(B, D, E) and R3(C, D)Or write it in another format:Fall 2020 – University of VirginiaAB // BDE // CD Praphamontripong7

Example 2: 3NF and FcLet’s do this togetherR(A,B,C)FDs { A à BC, B à C, A à B, AB à C }Compute Fc and convert the relation into 3NFGiven(1) write all LHSAàBàAB à(2) copy FDs as isAàBàAB àBCCCCombine the givenFDs A à BC andA àBNo reflexivityto remove(3) removeextraneous attrAà BCBàCAB àC(4) removeextraneous attrAà BCBàCConsider AB à C andB à C,A is an extraneous attr,remove A fromAB à C (resulting inB à C)Apply decomposition toA à BC, thus, A à Band A à C.A à C is logicallyequivalent to A à Band B à C (transitivity).Thus, C is anextraneous attr, removeC from A à BCFall 2020 – University of Virginia Praphamontripong8

Example 2: 3NF and FcLet’s do this togetherSuper key(from previous page)(4) Removeextraneous attrAà BBàCTurn Fc into tablesABBCR(A, B, C) becomes R1(A, B) and R2(B, C)Or write it in another format:Fall 2020 – University of VirginiaAB // BC Praphamontripong9

BCNF and Decomposition Lossless-join Guarantee redundancy free May involve dependency across relationsGiven a relation R,for every nontrivial FD X à Y in R, X is a super key For all FDs, “key à everything”Questions:Is the relation in BCNF?Is any refinement needed?Fall 2020 – University of Virginia Praphamontripong10

BCNF and DecompositionTo calculate BCNFCompute F repeat given a relation R (or a decomposed R) and FDs Ffor each functional dependency fi in a relation Rif fi violates X à Ythen decompose R into two relations:one with X U Y as its attributes (i.e., everything f)one with X U (attrs(R) – X – Y) as its attributesuntil no violationFall 2020 – University of Virginia Praphamontripong11

Example: BCNF and F Let’s do this togetherR(A,B,C,D,E)FDs { A à B, AB à D, B à BDE, C à D, D à D }Compute F and convert the relation into BCNFGivenCompute F (1) write all LHS& remainingAàBàAB àCàD àEàFall 2020 – University of Virginia(2) copy FDs as isABABCDEàààààà(3) apply reflexivityBB DEDDDABABCDE Praphamontripongà ABà B DEà AB DàCDàDàE(4) apply transitivityABABCDEà AB DEà B DEà AB DEàCDàDàE12

Example: BCNF and F Let’s do this together(from previous page)(4) apply transitivityF ABABCDEà AB DEà B DEà AB DEàCDàDàENot trivial FDs. A, B, C are not super keyTrivial FDs (let’s abbreviate to TR)Based on F , let’s rewrite using the following format to help us calculateR( ABCDE)TRSKX!! ! ! TR TRFall 2020 – University of Virginia Praphamontripong– trivial– super key– neither trivial nor super key– (possibly) need to work on13

Example: BCNF and F Let’s do this togetherR( ABCDE)! ! ! TR TRF ABABCDETo choose which FD to work on, two ways: Choose the first FD, or Choose the longest FD (yield better solution)à AB DEà B DEà AB DEàCDàDàELet’s consider A:A is not a super key, not trivial, thus A à ABDE violates BCNF,break a relation on AFall 2020 – University of Virginia Praphamontripong14

Example: BCNF and F Let’s do this togetherR( ABCDE)! ! ! TR TRF ABABCDEA à ABDETake RHS, make a table: ABDETake LHS, make a table where A is a keyA plus (original – (RHS)) --- thus, ACBreak on AVerify table ABDE ifthere is any violation.ABDEà AB DEà B DEà AB DEàCDàDàEThere are only 2 attrs,this relation is okABCDEACokRestriction: Cannot breakon A 2 times in a rowA is a super key.Still need to work on B.Next: consider B. B is neither trivial nor super key, break on BFall 2020 – University of Virginia Praphamontripong15

Example: Calculate BCNFLet’s do this togetherR( ABDE)X ! TR TRF ABABCDEB à BDETake RHS, make a table: BDETake LHS, make a table where B is a keyB plus (original – (RHS)) --- thus, ABBreak on AVerify that B à BDEdoes not violate BCNF.B is super key.D and E are trivial.Fall 2020 – University of VirginiaokBDEThere are only 2 attrs,this relation is okABCDEABDEBreak on BACABà AB DEà B DEà AB DEàCDàDàEokR(ABCDE) becomesAC // AB // BDEok(notice: results are different 3NF) Praphamontripong16

Wrap-Up Compute F and Fc 3NF and decomposition BCNF and decompositionWhat’s next? SQLFall 2020 – University of Virginia Praphamontripong17

Additional practiceFall 2020 – University of Virginia Praphamontripong18

Practice 1: DecompositionGivenR (A, B, C)FDs { A à B, B à C }Supposed R is decomposed in two different ways :1. R1(A, B), R2(B, C) Does this satisfy lossless-join decomposition?Yes: R1 R2 {B} and B à BC (B is super key of R2) Does this satisfy dependency preserving?Yes: dependencies can be checked without joining tables2. R1(A, B), R2(A, C) Does this satisfy lossless-join decomposition?Yes: R1 R2 {A} and A à AB (A is super key of R1) Does this satisfy dependency preserving?No: cannot check B à C without joining R1 and R2Fall 2020 – University of Virginia Praphamontripong19

Practice 2: 3NF and BCNFGivenR (A, B, C, D, E)FDs { A à C, C à DE, D à B, A à D }Decompose table R using 3NFDecompose table R using BCNFFc:Aà CC à DEDàBF :A à ABCDEBà BC à BCDED à BDEàEAC // BD // CDEAC // BD // CDEFall 2020 – University of Virginia Praphamontripong20

Practice 3: 3NFDoes the Customer order table satisfy 3NF requirements?If not, convert the table into 3NFCustomer orderOrderId12345678910 Fall 2020 – University of VirginiaCustomerIDDate2 10/1/20191 9/25/20193 8/12/20194 10/23/20198 5/11/20196 5/11/20195 7/31/20197 10/17/20196 9/19/20194 10/23/2019 stWestNorthNorth Address11 Sorth Str22 West Str33 East Str22 West Str44 North Str11 Sorth Str33 East Str22 West Str44 North Str44 North Str 21

Practice 3: 3NF - solutionNo. OrderId à Store à Address”Transitive dependency”Customer orderOrderId12345678910 CustomerID2134865764 Fall 2020 – University of 10/23/2019 StoreSouthWestEastWestNorthSouthEastWestNorthNorth PraphamontripongStoreSouthWestEastNorthAddress11 Sorth Str22 West Str33 East Str44 North Str22

Practice 4: BCNFDoes the Student Major Advisor table satisfy BCNF requirements?If not, convert the table into BCNFAssume:(semantic/business rules)Student Major puter SciencePhysicsEngineeringComputer ScienceMathComputer one5someone1computingID, Major à AdvisorAdvisor à MajorFall 2020 – University of Virginia Praphamontripong Each Student may major inseveral subjects. For each Major, a givenStudent has only oneAdvisor. Each Major has severalAdvisors. Each Advisor advises onlyone Major. Each Advisor advisesseveral Students in oneMajor.23

Practice 4: BCNF - solutionNo. Contain non-key attribute(s)PK can be computingID, Major or computingID, AdvisorStudent AdvisorComputingIDht1ydt2ydt2ymd3ymn4emd3yFall 2020 – University of eone5someone1Advisor e5 PraphamontripongMajorComputer SciencePhysicsEngineeringComputer ScienceMath24

(1) write all LHS A à B à AB à (2) copy FDs as is A à BC B à C AB à C (3) remove extraneous attr A à BC B à C AB à C (4) remove extraneous attr A à BC B à C No reflexivity to remove Combine the given FDs A à BC and A à B Consider AB à C