《數(shù)據(jù)庫系統(tǒng)》教學(xué)課件

數(shù)據(jù)庫系統(tǒng)教學(xué)課件,數(shù)據(jù)庫系統(tǒng),數(shù)據(jù)庫,系統(tǒng),教學(xué),課件 Schema Refinement and Normal FormsJianlin FengSchool of SoftwareSUN YAT-SEN UNIVERSITYcourtesy of Joe Hellerstein for some slidesReview:Database DesignnRequirements Analysisq user needs;what must database do?nConceptual Designq high level description(often done with ER model)nLogical Designq translate ER into DBMS data modelnSchema Refinement q consistency,normalizationnPhysical Design-indexes,disk layoutnSecurity Design-who accesses whatThe Evils of RedundancynRedundancy is at the root of several problems associated with relational schemas:qredundant storage,insert/delete/update anomaliesnIntegrity constraints,in particular functional dependencies,can be used to identify schemas with such problems and to suggest refinements.nMain refinement technique:decomposition qreplacing ABCD with,say,AB and BCD,or ACD and ABD.nDecomposition should be used judiciously:qIs there reason to decompose a relation?qWhat problems(if any)does the decomposition cause?Functional Dependencies(FDs)nA functional dependency X Y holds over relation schema R if,for every allowable instance r of R:t1 r,t2 r,pX(t1)=pX(t2)implies pY(t1)=pY(t2)(where t1 and t2 are tuples;X and Y are sets of attributes)nIn other words:X Y means Given any two tuples in r,if the X values are the same,then the Y values must also be the same.(but not vice versa)nCan read“”as“determines”Functional Dependencies(Contd.)nAn FD is a statement about all allowable relations.qMust be identified based on semantics of application.qGiven some instance r1 of R,we can check if r1 violates some FD f,but we cannot determine if f holds over R.nQuestion:How related to keys?qif“K all attributes of R”then K is a superkey for R(does not require K to be minimal.)nFDs are a generalization of keys.Example:Constraints on Entity SetnConsider relation obtained from Hourly_Emps:Hourly_Emps(ssn,name,lot,rating,wage_per_hr,hrs_per_wk)nWe sometimes denote a relation schema by listing the attributes:e.g.,SNLRWHnSometimes,we refer to the set of all attributes of a relation by using the relation name.e.g.,“Hourly_Emps”for SNLRWHWhat are some FDs on Hourly_Emps?ssn is the key:S SNLRWH rating determines wage_per_hr:R Wlot determines lot:L L (“trivial”dependnency)Problems Due to R WnUpdate anomaly:Can we modify W in only the 1st tuple of SNLRWH?nInsertion anomaly:What if we want to insert an employee and dont know the hourly wage for his or her rating?(or we get it wrong?)nDeletion anomaly:If we delete all employees with rating 5,we lose the information about the wage for rating 5!Hourly_EmpsDetecting RedundancyHourly_EmpsQ:Why was R W problematic,but S W not?Decomposing a RelationnRedundancy can be removed by“chopping”the relation into pieces.nFDs are used to drive this process.R W is causing the problems,so decompose SNLRWH into what relations?Hourly_Emps2WagesRefining an ER Diagram by FD:Attributes Can Easily Be Associated with the“Wrong”Entitity Set in ER Design.n1st diagram becomes:Workers(S,N,L,D,Si)Departments(D,M,B)qLots associated with workers.nSuppose all workers in a dept are assigned the same lot:D LnRedundancy;fixed by decomposition:Workers2(S,N,D,Si)Dept_Lots(D,L)Departments(D,M,B)nCan fine-tune this:Workers2(S,N,D,Si)Departments(D,M,B,L)lotdnamebudgetdidsincenameWorks_InDepartmentsEmployeesssnlotdnamebudgetdidsincenameWorks_InDepartmentsEmployeesssnBefore:After:Reasoning About FDsnGiven some FDs,we can usually infer additional FDs:title studio,star implies title studio and title star title studio and title star implies title studio,startitle studio,studio star implies title starBut,title,star studio does NOT necessarily imply that title studio or that star studionAn FD f is implied by a set of FDs F if f holds whenever all FDs in F hold.nF+=closure of F is the set of all FDs that are implied by F.(includes“trivial dependencies”)Rules of InferencenArmstrongs Axioms(X,Y,Z are sets of attributes):qReflexivity:If X Y,then X Y qAugmentation:If X Y,then XZ YZ for any ZqTransitivity:If X Y and Y Z,then X ZnThese are sound and complete inference rules for FDs!qi.e.,using AA you can compute all the FDs in F+and only these FDs.nSome additional rules(that follow from AA):qUnion:If X Y and X Z,then X YZqDecomposition:If X YZ,then X Y and X ZExamplenContracts(cid,sid,jid,did,pid,qty,value),and:qC is the key:C CSJDPQVqP(roject)purchases a given part using a single contract:JP CqD(ept)purchases at most 1 part from a supplier:SD PnProblem:Prove that SDJ is a key for ContractsqJP C,C CSJDPQV imply JP CSJDPQV(by transitivity)(shows that JP is a key)qSD P implies SDJ JP(by augmentation)qSDJ JP,JP CSJDPQV imply SDJ CSJDPQV(by transitivity)thus SDJ is a key.Attribute ClosurenTypically,we just want to check if a given FD X Y is in the closure of a set of FDs F.An efficient check:qCompute attribute closure of X(denoted X+)w.r.t.F.X+=Set of all attributes A such that X A is in F+nX+:=XnRepeat until no change:if there is an FD U V in F such that U is in X+,then add V to X+qCheck if Y is in X+nThe approach can also be used to find the keys of a relation.qIf all attributes of R are in the closure of X,then X is a superkey for R.Attribute Closure(example)nR=A,B,C,D,EnF=B CD,D E,B A,E C,AD B nIs B E in F+?B+=BB+=BCDB+=BCDAB+=BCDAE Yes!and B is a key for R too!n Is D a key for R?D+=DD+=DED+=DEC Nope!Is AD a key for R?AD+=ADAD+=ABD and B is a key,so Yes!Is AD a candidate key for R?A+=A A not a key,nor is D so Yes!Is ADE a candidate key for R?No!AD is a key,so ADE is a superkey,but not a candidate key.Normal FormsnHow to do schema refinement?qWe use normal forms as guidance.nIf a relation is in a normal form(BCNF,3NF etc.):qwe know that certain problems are avoided/minimized.qhelps decide whether decomposing a relation is useful.Normal Forms vs.Functional DependenciesnRole of FDs in detecting redundancy:qConsider a relation R with 3 attributes,ABC.nNo(non-trivial)FDs hold:There is no redundancy here.nGiven A B:If A is not a key,then several tuples could have the same A value,and if so,theyll all have the same B value!nThe normal forms based on FDs are:qFirst Normal Form(1NF),2NF,3NF,and Boyce-Codd Normal Form(BCNF)qThese forms have increasingly restrictive requirements:n1NF 2NF(of historical interest)3NF BCNF1st Normal Formn1st Normal Form all attributes are atomicqGiven a relation R in 1NF,for a tuple t of R,ts every attribute can contain only atomic values,qi.e.,attribute values are not lists or sets.nWe can imagine there exists FDs in the following manner:qAttribute A some unique value in As domain.Boyce-Codd Normal Form (BCNF)nRelation R with FDs F is in BCNF if for all X A in F+qA X (called a trivial FD),orqX is a superkey for R.nIntuitively,R is in BCNF if the only non-trivial FDs over R are key constraints.Boyce-Codd Normal Form (Contd.)nIf R in BCNF,then every field of every tuple records information that cannot be inferred using FDs alone.qSay we know FD X A holds for this example relation:Can you guess the value of the missing attribute?Yes,so relation is not in BCNFDecomposition of a Relation SchemenIf a relation is not in a desired normal form,it can be decomposed into multiple relations that each are in that normal form.nSuppose that relation R contains attributes A1.An.A decomposition of R consists of replacing R by two or more relations such that:qEach new relation scheme contains a subset of the attributes of R,qand every attribute of R appears as an attribute of at least one of the new relations.Example(same as before)nSNLRWH has FDs S SNLRWH and R WnQ:Is this relation in BCNF?Hourly_EmpsNo,The second FD causes a violation;W values repeatedly associated with R values.Decomposing a RelationnEasiest fix is to create a relation RW to store these associations,and to remove W from the main schema:Decompositions should be used only when needed.Q:potential problems of decomposition?Q:Are both of these relations are now in BCNF?Hourly_Emps2WagesProblems with DecompositionsnThere are three potential problems to consider:1)May be impossible to reconstruct the original relation!(Lossiness)nFortunately,not in the SNLRWH example.2)Dependency checking may require JOINs.nFortunately,not in the SNLRWH example.3)Some queries become more expensive.ne.g.,How much does Guldu earn?Tradeoff:Must consider these issues vs.redundancy.Lossless Decomposition(example)=Lossy Decomposition(example)A B;C B=Lossless Join DecompositionsnDecomposition of R into X and Y is lossless-join w.r.t.a set of FDs F if,for every instance r that satisfies F:(r)(r)=rnIt is always true that r (r)(r)qIn general,the other direction does not hold!If it does,the decomposition is lossless-join.nDefinition extended to decomposition into 3 or more relations in a straightforward way.nIt is essential that all decompositions used to deal with redundancy be lossless!(Avoids Problem#1)Simple Test on Lossless DecompositionnThe decomposition of R into X and Y is lossless w.r.t.F iff the closure of F contains:X Y X,orX Y YnIn the example:decomposing ABC into AB and BC is lossy,because intersection(i.e.,“B”)is not a key of either resulting relation.nUseful result:If W Z holds over R and W Z is empty,then decomposition of R into R-Z and WZ is loss-less.Lossless Decomposition(example)A B;C BBut,now we cant check A B without doing a join!=Dependency Preserving DecompositionnIntuitively,a dependency preserving decomposition allows us to enforce all FDs by examining a single relation instance on each insertion or modification of a tuple.q(Avoids Problem#2 on our list.)nProjection of set of FDs F:qIf R is decomposed into X and Y,qthe projection of F on X (denoted FX)is the set of FDs U V in F+such that all of the attributes U,V are in X.(same holds for Y of course)Dependency Preserving Decompositions(Contd.)nDecomposition of R into X and Y is dependency preserving if (FX FY)+=F+.nImportant to consider F+in this definition:qABC,A B,B C,C A,decomposed into AB and BC.qIs this dependency preserving?Is C A preserved?nnote:F+contains F A C,B A,C B,sonFAB contains A B and B A;FBC contains B C and C B.So,(FAB FBC)+contains C ADecomposition into BCNFnConsider relation R with FDs F.If X Y violates BCNF,decompose R into R-Y and XY(guaranteed to be loss-less).qRepeated application of this idea will give us a collection of relations that are in BCNF;qlossless join decomposition,and guaranteed to terminate.qe.g.,CSJDPQV,key C,JP C,SD P,J Sq contractid,supplierid,projectid,deptid,partid,qty,valueqTo deal with SD P,decompose into SDP,CSJDQV.qTo deal with J S,decompose CSJDQV into JS and CJDQVqSo we end up with:SDP,JS,and CJDQVDecomposition of CSJDPQV intoSDP,JS,and CJDQVWhat if we do the decomposition by using the dependency JS first?BCNF and Dependency PreservationnIn general,there may not be a dependency preserving decomposition into BCNF.qdecomposition of CSJDPQV into SDP,JS and CJDQV is not dependency preserving (w.r.t.the FDs JP C,SD P and J S).qi.e.,the dependency JP C can not be enforced without a join.However,it is a lossless join decomposition.nIn this case,adding JPC to the collection of relations gives us a dependency preserving decomposition.qbut JPC tuples are stored only for checking the FD.(Redundancy!)Third Normal Form (3NF)nRelation R with FDs F is in 3NF if,for all X A in F+qA X (called a trivial FD),orqX is a superkey of R,orqA is part of some candidate key(not superkey!)for R.nMinimality of a key is crucial in third condition above!nIf R is in BCNF,obviously in 3NF.nIf R is in 3NF,some redundancy is possible.It is a compromise,used when no“good”decomposition for BCNF,or for performance considerations.qLossless-join,dependency-preserving decomposition of R into a collection of 3NF relations always possible.3NF Violated by XA:Case 1nX is a proper subset of some key K qSuch XA is sometimes called a partial dependency.nWe store(X,A)pairs redundantly.E.g.,Reserves has attributes SBDC,(C is for credit card number),the only key is SBD,and we have the FD S C.Then we store the credit card number for a sailor as many times as there are reservations for that sailor.3NF Violated by XA:Case 2nX is not a proper subset of any key.qSuch XA is sometimes called a transitive dependency.qBecause it means there is a chain of FDs K X A.The problem:we cannot associate an X value with a K value,unless we also associate an A value with an X value.Example:SNLRWH has FDs S SNLRWH and R WRedundancy in 3NFnThe problems associated with partial and transitive dependences can persist in 3NF ifqThere is a non-trivial FD XA,qand X is not a superkey,qbut A is part of a key.Why 3NF?nThe motivation for 3NF is rather technical.qLossless-join,dependency preserving decomposition does not always exist for BCNF.qWe can ensure every relation schema can be decomposed into a collection of 3NF relationsnusing only lossless-join,dependency preserving decompositions.Decomposition into 3NFnThe algorithm for lossless join decomposition into BCNF can be used to obtain a lossless join decomposition into 3NF qbut does not ensure dependency preservation.nTo ensure dependency preservation,one idea:qIf X Y is not preserved,add relation XY.Problem is that XY may violate 3NF!e.g.,consider the addition of JPC to preserve JP C.What if we also have J C?nRefinement:Instead of the given set of FDs F,use a minimal cover for F.Minimal Cover for a Set of FDsnMinimal cover G for a set of FDs F:qF+is equal to G+.qEach FD in G is of the form XA,where A is a single attribute.qIf we modify G by deleting an FD or by deleting attributes from an FD in G,the closure changes.nIntuitively,every FD in G is needed,and as small as possible in order to get the same closure as F.A General Algorithm for Calculating Minimal CoverE.g.,Assume F=A B,ABCD E,EF GH,ACDF EG,its minimal cover is:qA B,ACD E,EF G and EF HDependency-Preserving Decomposition into 3NFnLet R be a relation with a set of F of FDs that is a minimal cover,and let R1,R2,Rn be a lossless-join decomposition of R.nSuppose that each Ri is in 3NF,and let Fi denote the projection of F onto the attributes of Ri.nDo the following:qIndentify the set N of FDs in F that are not preserved.qFor each FD XA in N,create a relation schema XA and add it to the decomposition of R.nEach XA is in 3NF.Proof:XA is in 3NF nSince XA is in the minimal cover F,qFor any proper subset Y of X,YA does not hold.qTherefore,X is a key for XA.nFor any other FD PQ that holds over XAqQ must belong to X.Summary of Schema RefinementnBCNF:each field contains information that cannot be inferred using only FDs.qensuring BCNF is a good heuristic.nNot in BCNF?Try decomposing into BCNF relations.qMust consider whether all FDs are preserved!nLossless-join,dependency preserving decomposition into BCNF impossible?Consider 3NF.qSame if BCNF decomp is unsuitable for typical queriesqDecompositions should be carried out and/or re-examined while keeping performance requirements in mind.