清華大學(xué)數(shù)據(jù)庫原理課件第七章

數(shù)據(jù)庫原理

2003年/秋Chapter7

RelationalDatabaseDesign(c1)

12MainContentsBoyce-CoddNormalFormThirdNormalFormMultivaluedDependenciesFourthNormalFormOverallDatabaseDesignProcess3Boyce-CoddNormalForm

istrivial(i.e.,

)isasuperkeyforRArelationschemaRisinBCNFwithrespecttoasetFoffunctionaldependenciesif

forallfunctionaldependenciesinF+oftheform

,where

Rand

R,

atleastoneofthefollowingholds:4ExampleR=(A,B,C)

F={A

B

BC}

Key={A}RisnotinBCNFDecompositionR1=(A,B),R2=(B,C)R1

andR2inBCNFLossless-joindecompositionDependencypreserving5TestingforBCNFTocheckifanon-trivialdependency

inF+

causesaviolationofBCNF1.compute+(theattributeclosureof)2.verifythatitincludesallattributesofR,thatis,itisasuperkeyofR6SimplifiedTestingforBCNFTocheckifarelationschemaRwithagivensetoffunctionaldependenciesFisinBCNF,itsufficestocheckonly

thedependenciesinthegivenset

FforviolationofBCNF,ratherthancheckingalldependenciesinF+WecanshowthatifnoneofthedependenciesinFcausesaviolationofBCNF,thennoneofthedependenciesinF+willcauseaviolationofBCNFeither7NoTestonaDecompositionofRConsiderR(A,B,C,D),withF={AB,BC}DecomposeRintoR1(A,B)andR2(A,C,D)NeitherofthedependenciesinFcontainonlyattributesfrom(A,C,D)sowemightbemisleadintothinkingR2satisfiesBCNFInfact,dependencyA

CinF+showsR2isnotinBCNFHowever,usingonlyFisincorrectwhentestingarelationinadecompositionofR8BCNFDecompositionAlgorithm result:={R};done:=false;

computeF+;

while(notdone)do

if(thereisaschemaRi

inresultthatisnotinBCNF)

thenbegin

let

beanontrivialfunctionaldependency thatholdsonRisuchthat

Ri

isnotinF+,and

=;

result:=(result–Ri)(Ri–)(,);

end

elsedone:=true;Ri--Ri?9ExampleofBCNFDecompositionR=(branch-name,branch-city,assets,

customer-name,loan-number,amount)

F={branch-name

assetsbranch-city

loan-number

amountbranch-name}

Key={loan-number,customer-name}DecompositionR1=(branch-name,branch-city,assets)R2=(branch-name,customer-name,loan-number,amount)R3=(branch-name,loan-number,amount)R4=(customer-name,loan-number)Finaldecomposition

R1,R3,R410TestingDecompositionwithF+ArelationRiinadecompositionofRTestRiforBCNFwithrespecttotherestrictionofFtoRi(thatis,allFDsinF+thatcontainonlyattributesfromRi)11TestingDecompositionwithFArelationRiinadecompositionofRforeverysetofattributesRi,checkthat+(theattributeclosureof)eitherincludesnoattributeofRi-,orincludesallattributesofRiIftheconditionisviolatedbysomeinF,thedependency

(+-)Ri

canbeshowntoholdonRi,andRiviolatesBCNFWeuseabovedependencytodecomposeRi12BCNFandDP ItisnotalwayspossibletogetaBCNFdecompositionthatisdependencypreserving,’overnormalize’R=(J,K,L)

F={JK

L,L

K}

Twocandidatekeys=JKandJLRisnotinBCNFAnydecompositionofRwillfailtopreserveJK

L13MainContentsBoyce-CoddNormalFormThirdNormalFormMultivaluedDependenciesFourthNormalFormOverallDatabaseDesignProcess14Motivationof3NFTherearesomesituationswhereBCNFisnotdependencypreserving,andEfficientcheckingforFDviolationonupdatesis

importantSolutiondefineaweakernormalform,calledThirdNormalForm(3NF)15ThirdNormalFormArelationschemaRisinthirdnormalformifforall:

inF+

atleastoneofthefollowingholds:

istrivial(i.e.,

)isasuperkeyforREachattributeAin–iscontainedinacandidatekeyforRCanthecandidatekeybereplacedbysuperkey?Shouldeachattributebeinthesamecandidatekey?163NFandBCNFIfarelationisinBCNFitisin3NF(sinceinBCNFoneofthefirsttwoconditionsabovemusthold)ThirdconditionisaminimalrelaxationofBCNFtoensuredependencypreservation17Exampleof3NFR=(J,K,L) Twocandidatekeys,JKandJLRisin3NF

JK

L JKisasuperkey

L

K KiscontainedinacandidatekeyBCNFdecompositionhas(JL)and(LK)

F={JK

L,L

K}TestingforJK

Lrequiresajoin18Redundancyin3NFThereissomeredundancyinthisschemaEquivalenttoexampleinbook:Banker-schema=(branch-name,customer-name, banker-name) banker-namebranch-name branch-namecustomer-namebanker-nameb1 c1 k1b1 c2 k1b1 c1 k219Testingfor3NFTestingfor3NFhasbeenshowntobeNP-hardNeedtocheckonlyFDsinF,neednotcheckallFDsinF+Useattributeclosuretocheck,foreachdependency,ifisasuperkeyIfisnotasuperkey,wehavetoverifyifeachattributeiniscontainedinacandidatekeyofR203NFDecompositionAlgorithm LetFc

beacanonicalcoverforF; i:=0;

foreachfunctionaldependency

inFc

do

ifnoneoftheschemasRj,1j

icontains

thenbegin

i:=i+1;

Ri:=

end //endofifandfor

ifnoneoftheschemasRj,1j

icontainsacandidatekeyforR

thenbegin

i:=i+1;

Ri:=anycandidatekeyforR;

end //endofif

return(R1,R2,...,Ri)

213NFDecompositionAlgorithm(c1)ThepreviousalgorithmensureseachrelationschemaRi

isin3NFdecompositionisdependencypreservingandlossless-jointheresultisnotuniquelydefined22ExampleRelationschema

Banker-info-schema=(branch-name,customer-name,

banker-name,office-number)Thefunctionaldependencies

banker-name

branch-nameoffice-number

customer-namebranch-name

banker-nameThekey

{customer-name,branch-name}23Banker-info-schemato3NFTheforloopinthealgorithmcausesustoincludethefollowingschemasinourdecomposition:

Banker-office-schema= (banker-name,branch-name,office-number)

Banker-schema= (customer-name,branch-name, banker-name)

SinceBanker-schemacontainsacandidatekeyfor

Banker-info-schema,wearedonewiththedecompositionprocess24ComparisonofBCNFand3NFItisalwayspossibletodecomposearelationintorelationsin3NFandthedecompositionislossless,andthedependenciesarepreservedItisalwayspossibletodecomposearelationintorelationsinBCNFandthedecompositionislossless,howerveritmaynotbepossibletopreservedependencies25Examplein3NFJj1j2j3nullLl1l1l1l2Kk1k1k1k2Exampleofproblemsduetoredundancyin3NFR=(J,K,L)

F={JK

L,L

K}J=street,K=city,andL=zip26Problemsin3NF

Aschemathatisin3NFbutnotinBCNFhastheproblemsof

repetitionofinformation(e.g.,therelationshipl1,k1)needtousenullvalues(e.g.,torepresenttherelationshipl2,k2wherethereisnocorrespondingvalueforJ).27TradeoffinDesignGoalforarelationaldatabasedesignis:BCNFLosslessjoinDependencypreservationIfwecannotachievethis,weacceptoneofLackofdependencypreservationRedundancyduetouseof3NF28MainContentsBoyce-CoddNormalFormThirdNormalFormMultivaluedDependencies

FourthNormalFormOverallDatabaseDesignProcess29BeyondBCNFTherearedatabaseschemasinBCNFthatdonotseemtobesufficientlynormalizedConsideradatabase

classes(course,teacher,book)

suchthat(c,t,b)classesmeansthattisqualifiedtoteachc,andbisarequiredtextbookforc30Thedatabaseissupposedtolistforeachcoursethesetofteachersanyoneofwhichcanbethecourse’sinstructor,andthesetofbooks,allofwhicharerequiredforthecourse(nomatterwhoteachesit)AClassesInstancecourseteacherbookdatabasedatabasedatabasedatabasedatabasedatabaseoperatingsystemsoperatingsystemsoperatingsystemsoperatingsystemsAviAviHankHankSudarshanSudarshanAviAviJimJimDBConceptsUllmanDBConceptsUllmanDBConceptsUllmanOSConceptsShawOSConceptsShawcoursesteachersbooksC-T-B31Sincetherearenotnon-trivialdependencies,(course,teacher,book)istheonlykey,andthereforetherelationisinBCNF

Insertionanomalies(插入異常)ifSaraisanewteacherthatcanteachdatabase,twotuplesneedtobeinserted

(database,Sara,DBConcepts)

(database,Sara,Ullman)ProblemsinClassesTable32Therefore,itisbettertodecomposeclassesinto:courseteacherdatabasedatabasedatabaseoperatingsystemsoperatingsystemsAviHankSudarshanAviJimteachescoursebookdatabasedatabaseoperatingsystemsoperatingsystemsDBConceptsUllmanOSConceptsShawtextDecomposeClassesTable33MVDDefinitionLetRbearelationschemaandletRand

R

Themultivalueddependency（多值依賴）

holdsonRifinanylegalrelationr(R),forallpairsfortuplest1andt2inrsuchthatt1[]=t2[],thereexisttuplest3andt4inrsuchthat:

t1[]=t2[]=t3[]=t4

[]

t3[]=t1[]

t3[R–]=t2[R–]

t4[]=t2[]

t4[R–]=t1[R–]

34Tabularrepresentationof

t1[]=t2[]=t3[]=t4

[]t3[]=t1[]t3[R–]=t2[R–]t4[]=t2[]t4[R–]=t1[R–]35AnotherMVDDefinitionLetRbearelationschemawithasetofattributesthatarepartitionedinto3nonemptysubsets(非空子集)Y,Z,WWesaythatY

Z(Y

multidetermines

Z)

ifandonlyifforallpossiblerelationsr(R) <y1,z1,w1>rand<y1,z2,w2>r then

<y1,z1,w2>rand<y1,z2,w1>rTrivialmultivalueddependency,ifWisemptyNotethatsincethebehaviorofZandWareidenticalitfollowsthatYZifYW36MVDExampleInourexample:

courseteacher

coursebookTheaboveformaldefinitionissupposedtoformalizethenotionthatgivenaparticularvalueofY(course)ithasassociatedwithitasetofvaluesofZ(teacher)andasetofvaluesofW(book),andthesetwosetsareinsomesenseindependentofeachotherNote:IfY

ZthenY

ZIndeedwehave(inpreviousslide)Z1=Z2

R=YZ(R-Y-Z)37UseofMVDWeusemultivalueddependenciesintwoways:TotestrelationstodeterminewhethertheyarelegalunderagivensetoffunctionalandmultivalueddependenciesTospecifyconstraintsonthesetoflegalrelations.

WeshallthusconcernourselvesonlywithrelationsthatsatisfyagivensetofFDsandMVDs

38ConstructionIfarelationrfailstosatisfyagivenmultivalueddependency,wecanconstructarelationsrthatdoessatisfythemultivalueddependencybyaddingtuplestor

ExampleinbookBC-schema

39TheoryofMVDsFromthedefinitionofmultivalueddependency,wecanderivethefollowingrule:If,then Thatis,everyfunctionaldependencyisalsoamultivalueddependency40ClosureD+ofDTheclosure(閉包)D+ofDisthesetofallfunctionalandmultivalueddependencieslogicallyimpliedbyD

WecancomputeD+fromD,usingtheformaldefinitionsofFDsandMVDsWecanmanagewithsuchreasoningforverysimplemultivalueddependencies,whichseemtobemostcommoninpracticeForcomplexdependencies,itisbettertoreasonaboutsetsofdependenciesusingasystemofinferencerules41MainContentsBoyce-CoddNormalFormThirdNormalFormMultivaluedDependenciesFourthNormalFormOverallDatabaseDesignProcess42FourthNormalFormArelationschemaRisin4NFwithrespecttoasetDoffunctionalandmultivalueddependenciesifforallmultivalueddependenciesinD+oftheform

,where

Rand

R,atleastoneofthefollowinghold:

istrivial(i.e.,

or

=R)isasuperkeyforschemaRIfarelationisin4NFitisinBCNF43RestrictionofMVDsTherestrictionofDtoRiisthesetDiconsistingofAllfunctionaldependenciesinD+thatincludeonlyattributesofRiAllmultivalueddependenciesoftheform

(

Ri)where

Riand

isinD+

444NFDecompositionAlgorithmresult:={R};

done:=false;

computeD+;

LetDidenotetherestrictionofD+toRiwhile(notdone)

if(thereisaschemaRiinresultthatisnotin4NF)then

begin letbeanontrivialmultivalueddependency thatholdsonRisuchthatRiisnotinDi,and ;

result:=(result-Ri)(Ri

-)(,);

end

elsedone:=true;45DecompositionExampleR=(A,B,C,G,H,I) F={A

B,B

HI, CG

H}Risnotin4NFsinceA

BandAisnotasuperkeyforRDecomposition a)R1=(A,B) (R1isin4NF) b)R2=(A,C,G,H,I) (R2isnotin4NF) c)R3=(C,G,H) (R3isin4NF) d)R4=(A,C,G,I) (R4isnotin4NF)46DecompositionExample(c1) SinceA

BandB

HI,A

HI,A

I e)R5=(A,I) (R5isin4NF) f)R6=(A,C,G) (R6isin4NF)47MainContentsBoyce-CoddNormalFormThirdNormalFormMultivaluedDependenciesFourthNormalFormOverallDatabaseDesignProcess48OverallDatabaseDesignProcessWehaveassumedschemaRisgivenRcouldhavebeengeneratedwhenconvertingE-RdiagramtoasetoftablesRcouldhavebeenasinglerelationcontainingallattributesthatareofinterest(calleduniversalrelation泛關(guān)系)NormalizationbreaksRintosmallerrelations.Rcouldhavebeentheresultofsomeadhocdesignofrelations,whichwethentest/converttonormalform49ERModelandNormalizationWhenanE-Rdiagramiscarefullydesigned,identifyingallentitiescorrectly,thetablesgeneratedfromtheE-RdiagramshouldnotneedfurthernormalizationHowever,inareal(imperfect)designtherecanbeFDsfromnon-keyattributesofanentitytootherattributesoftheentity50ERModelandNormalization(c1)Exampleemployeeentitywithattributesdepartment-numberanddepartment-address,andanFDdepartment-numberdepartment-addressGooddesignwouldhavemadedepartmentanentityFDsfromnon-keyattributesofarelationshipsetpossible,butraremostrelationshipsarebinary51UniversalRelationDanglingtuplesTuplesthat“disappear”incomputingajoinLetr1(R1),r2(R2),….,rn(Rn)beasetofrelationsAtupleroftherelationriisadanglingtupleifrisnotintherelation: Ri(r1

r2…rn)Therelationr1

r2…rniscalledauniversalrelation

sinceitinvolvesalltheattributesinthe“universe”definedbyR1R2…Rn

52DanglingTuplesIfdanglingtuplesareallowedinthedatabase,insteadofdecomposingauniversalrelation,wemayprefertosynthesizeacollectionofnormalformschemasfromagivensetofattributesDanglingtuplesmayoccurinpracticaldatabaseapplicationsTheyrepresentincompleteinformation53ExampleforDanglingTuplesWemaywanttobreakupinformationaboutloansinto:(branch-name,loan-number)(loan-number,amount)(loan-number,customer-name)Universalrelationwouldrequirenullvalues,andhavedanglingtuples54UniversalRelationApproachAparticulardecompositiondefinesarestrictedformofincompleteinformationthatisacceptableinourdatabaseAbovedecompositionrequiresatleastone(至少一個(gè))ofcustomer-name,branch-nameoramountinordertoenteraloannumberwithoutusingnullvaluesRulesoutstoringofcustomer-name,amountwithoutanappropriateloan-number(sinceitisakey,itcan'tbenulleither!)55U