基本軟件與課件通用

Chapter7:RelationalDatabaseDesignChapter7:RelationalDatabaseDesignFeaturesofGoodRelationalDesignAtomicDomainsandFirstNormalFormpositionUsingFunctionalDependenciesFunctionalDependencyTheoryAlgorithmsforFunctionalDependenciespositionUsingMultivaluedDependenciesMoreNormalFormDatabase-DesignProcessModelingTemporalDataTheBankingSchemabranch=(branch_name,branch_city,assets)customer=(customer_id,customer_name,customer_street,customer_city)loan=(loan_number,amount)loan_branch=(loan_number,branch_name)

Loan(loan_number,amount,branch_name)account=(account_number,balance)account_branch=(account_number,branch_name)

Account=(account_number,balance,branch_name)employee=(employee_id.employee_name,telephone_number,start_date)dependent_name=(employee_id,dname)borrower=(customer_id,loan_number)depositor=(customer_id,account_number,access_date)cust_banker=(customer_id,employee_id,type)works_for=(worker_employee_id,manager_employee_id)payment=(loan_number,payment_number,payment_date,payment_amount)savings_account=(account_number,interest_rate)checking_account=(account_number,overdraft_amount)ACombinedSchemaWithoutRepetitionConsidercombiningloan_branchandloanloan_amt_br=(loan_number,amount,branch_name)Norepetition(assuggestedbyexamplebelow)ACombinedSchemaWithRepetitionSupposewecombineborrowerandloantogetbor_loan=(customer_id,loan_number,amount)Resultispossiblerepetitionofinformation(L-100inexamplebelow)ACombinedSchemaWithRepetitioncustomer=(customer_id,customer_name,customer_street,customer_city)account

=(account_number,balance)depositor=(customer_id,account_number,access_date)Howaboutcombiningaboverelations?Account2(customer_id,customer_name,customer_street,customer_city,

account_number,balance,access_date)Pitfallsofthe“bad”relations:Informationrepetition(信息重復)Insertionanomalies(插入異常)Updatedifficulty(更新困難)WhatAboutSmallerSchemas?Supposewehadstartedwithbor_loan.Howwouldweknowtosplitup(pose)itintoborrowerandloan?Writearule“iftherewereaschema(loan_number,amount),thenloan_numberwouldbeacandidatekey”Denoteasafunctionaldependency: loan_numberamountInbor_loan,becauseloan_numberisnotacandidatekey,theamountofaloanmayhavetoberepeated.Thisindicatestheneedtoposebor_loan.Notallpositionsaregood.Supposeweposeemployeeasfollowing:employee=(employee_id.employee_name,telephone_number,start_date)

employee1=(employee_id,employee_name) employee2=(employee_name,telephone_number,start_date)Thenextslideshowshowweloseinformation--wecannotreconstructtheoriginalemployeerelation--andso,thisisalossyposition.ALossyposition(有損分解)WhatAboutSmallerSchemas?Ontheotherhand,followingpositionisOK:employee=(employee_id.employee_name,telephone_number,start_date)

employee1=(employee_id,employee_name) employee2=(employee_id,telephone_number,start_date)positionAllattributesofanoriginalschema(R)mustappearintheposition(R1,R2): R=R1R2Lossless-joinposition.

ForallpossiblerelationsronschemaR r=R1(r)R2(r)ApositionofRintoR1andR2islosslessjoinifandonlyif:R1R2isasuperkeyofR1orR1R2isasuperkeyofR2ExampleofNonLossless-JoinpositionpositionofR=(A,B)R1=(A) ,R2=(B)AB

121A

B12r

A(r)

B(r)

A(r)B(r)AB

1212ExampleofLossless-Joinposition

（無損連接分解）positionofR=(A,B,C)R1=(A,B),R2=(A,C)AB

121A

A

r

A,B(r)

A,C(r)

A(r)B(r)C112211B121C112211AB

121C112211FirstNormalForm(范式)DomainisatomicifitselementsareconsideredtobeindivisibleunitsExamplesofnon-atomicdomains:Setofnames,compositeattributesIdentificationnumberslikeCS101thatcanbebrokenupintopartsArelationalschemaRisinfirstnormalformifthedomainsofallattributesofRareatomicNon-atomicvaluescomplicatestorageandencourageredundant(repeated)storageofdataExample:Setofaccountsstoredwitheachcustomer,andsetofownersstoredwitheachaccountWeassumeallrelationsareinfirstnormalform(andrevisitthisinChapter9)FirstNormalForm(Cont’d)Atomicityisactuallyapropertyofhowtheelementsofthedomainareused.Example:StringswouldnormallybeconsideredindivisibleSupposethatstudentsaregivenrollnumberswhicharestringsoftheformCS0012orEE1127Ifthefirsttwocharactersareextractedtofindthedepartment,thedomainofrollnumbersisnotatomic.Doingsoisabadidea:leadstoencodingofinformationinapplicationprogramratherthaninthedatabase.Goal—DeviseaTheoryfortheFollowingDecidewhetheraparticularrelationRisin“good”form.InthecasethatarelationRisnotin“good”form,poseitintoasetofrelations{R1,R2,...,Rn}suchthateachrelationisingoodformthepositionisalossless-joinpositionOurtheoryisbasedon:functionaldependenciesmultivalueddependenciesFunctionalDependenciesConstraintsonthesetoflegalrelations.Requirethatthevalueforacertainsetofattributesdeterminesuniquelythevalueforanothersetofattributes.Afunctionaldependencyisageneralizationofthenotionofakey.FunctionalDependencies(Cont.)LetRbearelationschema

Rand

RThefunctionaldependency

holdson

Rifandonlyifforanylegalrelationsr(R),wheneveranytwotuplest1

andt2ofragreeontheattributes,theyalsoagreeontheattributes.Thatis, t1[]=t2[]t1[

]=t2[

]Example:Considerr(A,B)withthefollowinginstanceofr.Onthisinstance,A

BdoesNOThold,butB

Adoeshold.4153 7FunctionalDependencies(Cont.)KisasuperkeyforrelationschemaRifandonlyifK

RKisacandidatekeyforRifandonlyifK

R,andforno

K,

RFunctionaldependenciesallowustoexpressconstraintsthatcannotbeexpressedusingsuperkeys.Considertheschema:

bor_loan=(customer_id,loan_number,amount).

Weexpectthisfunctionaldependencytohold:

loan_number

amount

butwouldnotexpectthefollowingtohold:

amount

customer_nameFunctionalDependencies(Cont.)AfunctionaldependencyistrivialifitissatisfiedbyallinstancesofarelationExample:customer_name,loan_number

customer_namecustomer_name

customer_nameIngeneral,

istrivialif

UseofFunctionalDependenciesWeusefunctionaldependenciesto:testrelationstoseeiftheyarelegalunderagivensetoffunctionaldependencies.IfarelationrislegalunderasetFoffunctionaldependencies,wesaythatr

satisfiesF.specifyconstraintsonthesetoflegalrelationsWesaythatF

holdson

RifalllegalrelationsonRsatisfythesetoffunctionaldependenciesF.Note:Aspecificinstanceofarelationschemamaysatisfyafunctionaldependencyevenifthefunctionaldependencydoesnotholdonalllegalinstances.Forexample,aspecificinstanceofloanmay,bychance,satisfy

amount

customer_name.ExerciseWriteaSQLassertiontoindicatethatthefunctionaldependencyBCholdsonrelationr(A,B,C).createassertionC1check(notexists(select*fromrasr1,rasr2wherer1.B=r2.Bandr1.C!=r2.C))ClosureofaSetofFunctionalDependenciesGivenasetFoffunctionaldependencies,therearecertainotherfunctionaldependenciesthatarelogicallyimpliedbyF.Forexample:IfA

BandB

C,thenwecaninferthatA

CThesetofallfunctionaldependencieslogicallyimpliedbyFistheclosureofF.WedenotetheclosureofFbyF+.F+isasupersetofF.F={AB,BC},whatisF+?

F+={AB,BC,AC,ABB,ABC,…}7.3.2Boyce-CoddNormalForm

istrivial(i.e.,

)

isasuperkeyforR(每一個非平凡的函數(shù)依賴的左部都是superkey.)ArelationschemaRisinBCNFwithrespecttoasetFoffunctionaldependenciesifforallfunctionaldependenciesinF+oftheform

where

Rand

R,

atleastoneofthefollowingholds:ExampleschemanotinBCNF:

bor_loan=(customer_id,loan_number,amount)becauseloan_number

amountholdsonbor_loanbutloan_numberis notasuperkeyposingaSchemaintoBCNFSupposewehaveaschemaRandanon-trivialdependencycausesaviolationofBCNF. WeposeRinto:(U)(R-(-))Inourexample,=loan_number=amountandbor_loanisreplacedby(U)=(loan_number,amount)(R-(-))=(customer_id,loan_number)ExerciseFortherelationschemaR(A,B,C,D)withthefunctionaldependenciessetF={AB,BCD},Listallcandidatekeysoftherelation.posetherelationintoacollectionofBCNFrelations.Thepositionmustbelossless-join.Answer:candidatekeys:AR1=(B,C,D),R2=(A,B).Thepositionislossless-join,becauseR1R2=(B),andBisacandidatekeyofR1.AnotherAnswer:candidatekeys:AR1=(A,B),R2=(A,C,D).

ABDCBCNFandDependencyPreservationConstraints,includingfunctionaldependencies,arecostlytocheckinpracticeunlesstheypertaintoonlyonerelationIfitissufficienttotestonlythosedependenciesoneachindividualrelationofapositioninordertoensurethatallfunctionaldependencieshold,thenthatpositionisdependencypreserving.

（如果檢驗各單個關系上的函數(shù)依賴，就能確保所有的函數(shù)依賴成立，那么這樣的分解就是依賴保持的）（或者，原來關系R上的每一個函數(shù)依賴，都可以在分解后的單個的關系上得到檢驗，或者推導后來。）BecauseitisnotalwayspossibletoachievebothBCNFanddependencypreservation,weconsideraweakernormalform,knownasthirdnormalform.ExerciseFortherelationschemaR(A,B,C,D,E)withthefunctionaldependenciessetF={AB,BCD,ED},Listallcandidatekeysoftherelation.posetherelationintoacollectionofBCNFrelations.Thepositionmustbelossless-join.Whetherthepositionof(b)isdependencypreservingornot?Answer:candidatekeys:AER1(E,D),R2(B,C),R3(A,B),R4(A,E)Abovepositionisnotdependencypreserving,becauseBDcannotbeinferredbyallfunctionaldependenciesholdsonR1,R2,R3,andR4.ABDCEThirdNormalFormArelationschemaRisinthirdnormalform(3NF)ifforall:

inF+

atleastoneofthefollowingholds:

istrivial(i.e.,

)

isasuperkeyforREachattributeAin

–

iscontainedinacandidatekeyforR.

(NOTE:eachattributemaybeinadifferentcandidatekey)IfarelationisinBCNFitisin3NF(sinceinBCNFoneofthefirsttwoconditionsabovemusthold).ThirdconditionisaminimalrelaxationofBCNFtoensuredependencypreservation.GoalsofNormalizationLetRbearelationschemewithasetFoffunctionaldependencies.DecidewhetherarelationschemeRisin“good”form.InthecasethatarelationschemeRisnotin“good”form,poseitintoasetofrelationscheme{R1,R2,...,Rn}suchthateachrelationschemeisingoodformthepositionisalossless-joinpositionPreferably,thepositionshouldbedependencypreserving.HowgoodisBCNF?TherearedatabaseschemasinBCNFthatdonotseemtobesufficientlynormalizedConsideradatabase

classes(course,teacher,book)

suchthat(c,t,b)

classesmeansthattisqualifiedtoteachc,andbisarequiredtextbookforcThedatabaseissupposedtolistforeachcoursethesetofteachersanyoneofwhichcanbethecourse’sinstructor,andthesetofbooks,allofwhicharerequiredforthecourse(nomatterwhoteachesit).Therearenonon-trivialfunctionaldependenciesandthereforetherelationisinBCNFInsertionanomalies–i.e.,ifMarilynisanewteacherthatcanteachdatabase,twotuplesneedtobeinserted (database,Marilyn,DBConcepts)

(database,Marilyn,Ullman)courseteacherbookdatabasedatabasedatabasedatabasedatabasedatabaseoperatingsystemsoperatingsystemsoperatingsystemsoperatingsystemsAviAviHankHankSudarshanSudarshanAviAviPetePeteDBConceptsUllmanDBConceptsUllmanDBConceptsUllmanOSConceptsStallingsOSConceptsStallingsclassesHowgoodisBCNF?(Cont.)Therefore,itisbettertoposeclassesinto:courseteacherdatabasedatabasedatabaseoperatingsystemsoperatingsystemsAviHankSudarshanAviJimteachescoursebookdatabasedatabaseoperatingsystemsoperatingsystemsDBConceptsUllmanOSConceptsShawtextThissuggeststheneedforhighernormalforms,suchasFourthNormalForm(4NF),whichweshallseelater.HowgoodisBCNF?(Cont.)Functional-DependencyTheoryFunctional-DependencyTheoryWenowconsidertheformaltheorythattellsuswhichfunctionaldependenciesareimpliedlogicallybyagivensetoffunctionaldependencies.WethendevelopalgorithmstogeneratelosslesspositionsintoBCNFand3NFWethendevelopalgorithmstotestifapositionisdependency-preservingFunctionalDependencies(Cont.)LetRbearelationschema

Rand

RThefunctionaldependency

holdson

Rifandonlyifforanylegalrelationsr(R),wheneveranytwotuplest1

andt2ofragreeontheattributes,theyalsoagreeontheattributes.Thatis, t1[]=t2[]t1[

]=t2[

]Example:Considerr(A,B)withthefollowinginstanceofr.Onthisinstance,A

BdoesNOThold,butB

Adoeshold.4153 7ClosureofaSetofFunctionalDependenciesGivenasetFoffunctionaldependencies,therearecertainotherfunctionaldependenciesthatarelogicallyimpliedbyF.Forexample:IfA

BandB

C,thenwecaninferthatA

CThesetofallfunctionaldependencieslogicallyimpliedbyFistheclosureofF.WedenotetheclosureofFbyF+.Wecanfindallof

F+

byapplyingArmstrong’sAxioms:if

,then

(reflexivity,自反律)if

,then

(augmentation，增強律)if

,and

,then

(transitivity，傳遞律)Theserulesaresound

(正確的）generateonlyfunctionaldependenciesthatactuallyhold)andcomplete（完備的）(generateallfunctionaldependenciesthathold).ExampleR=(A,B,C,G,H,I)

F={A

B

A

C

CG

H

CG

I

B

H}somemembersofF+A

HbytransitivityfromA

BandB

HAG

IbyaugmentingA

CwithG,togetAG

CG

andthentransitivitywithCG

ICG

HIbyaugmentingCG

ItoinferCG

CGI,andaugmentingofCG

Htoinfer

CGI

HI,

andthentransitivity☆ProcedureforComputingF+TocomputetheclosureofasetoffunctionaldependenciesF:

F+=F

repeat

foreachfunctionaldependencyfinF+

applyreflexivityandaugmentationrulesonf

addtheresultingfunctionaldependenciestoF+

foreachpairoffunctionaldependenciesf1andf2inF+

if

f1andf2canbecombinedusingtransitivity

thenaddtheresultingfunctionaldependencytoF+

untilF+doesnotchangeanyfurtherNOTE:WeshallseeanalternativeprocedureforthistasklaterClosureofFunctionalDependencies(Cont.)WecanfurthersimplifymanualcomputationofF+byusingthefollowingadditionalrules.Ifholdsandholds,thenholds(union,合并律)Ifholds,thenholdsandholds(position,分解律)Ifholdsandholds,thenholds(pseudotransitivity,偽傳遞律)TheaboverulescanbeinferredfromArmstrong’saxioms.EX

<=>

(右部的重復屬性可以去掉)

=>

(左部屬性越少越強)

<

=

(右部屬性越多越強)ClosureofAttributeSetsGivenasetofattributesa,definetheclosure

ofa

under

F(denotedbya+)asthesetofattributesthatarefunctionallydeterminedbyaunderFAlgorithmtocomputea+,theclosureofaunderF

result:=a;

while(changestoresult)do

foreach

inFdo

begin

if

resultthenresult:=result

endExampleofAttributeSetClosureR=(A,B,C,G,H,I)F={A

B

A

C

CG

H

CG

I

B

H}(AG)+1. result=AG2. result=ABCG (A

CandA

B)3. result=ABCGH (CG

HandCG

AGBC)4. result=ABCGHI (CG

IandCG

AGBCH)IsAGacandidatekey?IsAGasuperkey?IsanysubsetofAGasuperkey?UsesofAttributeClosureThereareseveralusesoftheattributeclosurealgorithm:Testingforsuperkey:Totestifisasuperkey,wecompute+,andcheckif+

containsallattributesofR.TestingfunctionaldependenciesTocheckifafunctionaldependencyholds(or,inotherwords,isinF+),justcheckif+.Thatis,wecompute+

byusingattributeclosure,andthencheckifitcontains.Isasimpleandcheaptest,andveryusefulComputingclosureofFForeachR,wefindtheclosure+,andforeachS

+,weoutputafunctionaldependencyS.UsesofAttributeClosureComputingclosureofF:R(A,B),F={AB}computing:

A+=ABB+=B(AB)+=ABF+={AA,AB,AAB,BB,ABA,ABB,ABAB}UsesofAttributeClosureComputingclosureofF:R(A,B,C),F={AB,BC}computing:

A+=ABC,B+=BC,C+=C(AB)+=ABC,(AC)+=ABC,(BC)+=BC,(ABC)+=ABCF

{AABC,BBC,CC,ABABC,ACABC,BCBC,ABCABC}

{AA,AB,AC,AAB,AAC,ABC,AABCBB,BC,BBC,CC,

ABA,ABB,ABC,ABAB,ABAC,ABBC,ABABC,ACA,ACB,ACC,ACAB,ACAC,ACBC,ACABC,BCB,BCC,BCBC,

ABCA,ABCB,ABCC,ABCAB,ABCAC,ABCBC,ABCABC}

=F+CanonicalCover（正則覆蓋）SetsoffunctionaldependenciesmayhaveredundantdependenciesthatcanbeinferredfromtheothersForexample:A

C

isredundantin:{A

B,B

C,AC}PartsofafunctionaldependencymayberedundantE.g.:onRHS:{A

B,B

C,A

CD}canbesimplifiedto

{A

B,B

C,A

D}

.A

CD,CDD=>AD.AB,BC=>AC,AD=>ACDE.g.:onLHS:{A

B,B

C,AC

D}canbesimplifiedto

{A

B,B

C,A

D}.AB,BC=>AC=>AAC,ACD=>AD.AD=>ACCD,CDD=>ACDIntuitively,acanonicalcoverofFisa“minimal”setoffunctionaldependenciesequivalenttoF,havingnoredundantdependenciesorredundantpartsofdependencies☆ExtraneousAttributes（無關屬性）ConsiderasetFoffunctionaldependenciesandthefunctionaldependency

inF.AttributeAisextraneousin

ifA

andFlogicallyimplies(F–{

}){(–A)

}.AttributeAisextraneousin

ifA

andthesetoffunctionaldependencies

(F–{

}){

(

–A)}logicallyimpliesF.Note:implicationintheoppositedirectionistrivialineachofthecasesabove,sincea“stronger”functionaldependencyalwaysimpliesaweakeroneExample:GivenF={A

C,AB

C}BisextraneousinAB

Cbecause{A

C,AB

C}logicallyimpliesA

C(I.e.theresultofdroppingBfromAB

C).Example:GivenF={A

C,AB

CD}CisextraneousinAB

CDsinceAB

CcanbeinferredevenafterdeletingC☆TestingifanAttributeisExtraneousConsiderasetFoffunctionaldependenciesandthefunctionaldependency

inF.TotestifattributeA

isextraneous

in

compute({}–A)+usingthedependenciesinF

checkthat({}–A)+contains;ifitdoes,Aisextraneousin

TotestifattributeA

isextraneousin

compute

+usingonlythedependenciesin

F’=(F–{

}){

(

–A)},checkthat

+containsA;ifitdoes,Aisextraneousin

CanonicalCover（正則覆蓋/最簡覆蓋）AcanonicalcoverforFisasetofdependenciesFcsuchthatFlogicallyimpliesalldependenciesinFc,andFclogicallyimpliesalldependenciesinF,andNofunctionaldependencyinFccontainsanextraneousattribute,andEachleftsideoffunctionaldependencyinFcisunique.☆TocomputeacanonicalcoverforF:

repeat

UsetheunionruletoreplaceanydependenciesinF

11and12with112

Findafunctionaldependencywithan

extraneousattributeeitherinorin

Ifanextraneousattributeisfound,deleteitfrom

untilFdoesnotchangeNote:Unionrulemayeapplicableaftersomeextraneousattributeshavebeendeleted,soithastobere-appliedComputingaCanonicalCoverR=(A,B,C)

F={A

BC

B

C

A

B

AB

C}CombineA

BCandA

BintoA

BCSetisnow{A

BC,B

C,AB

C}AisextraneousinAB

CCheckiftheresultofdeletingAfromAB

CisimpliedbytheotherdependenciesYes:infact,B

Cisalreadypresent!Setisnow{A

BC,B

C}CisextraneousinA

BC

CheckifA

CislogicallyimpliedbyA

BandtheotherdependenciesYes:usingtransitivityonA

BandB

C.CanuseattributeclosureofAinmorecomplexcasesThecanonicalcoveris: A

B

B

CBACLossless-joinpositionForthecaseofR=(R1,R2),werequirethatforallpossiblerelationsronschemaR r=R1(r)R2(r)ApositionofRintoR1andR2islosslessjoinifandonlyifatleastoneofthefollowingdependenciesisinF+:R1R2R1R1R2R2ExampleR=(A,B,C)

F={AB,BC)CanbeposedintwodifferentwaysR1=(A,B),R2=(B,C)Lossless-joinposition: R1R2={B}andBBCDependencypreservingR1=(A,B),R2=(A,C)Lossless-joinposition: R1R2={A}andAABNotdependencypreserving

(cannotcheckBCwithoutcomputingR1R2)DependencyPreservationLetFibethesetofdependenciesofF+thatincludeonlyattributesinRi.Apositionisdependencypreserving,if(F1F2…Fn)+=F+Ifitisnot,thencheckingupdatesforviolationoffunctionaldependenciesmayrequirecomputingjoins,whichisexpensive.☆TestingforDependencyPreservationTocheckifadependencyispreservedinapositionofRintoR1,R2,…,Rnweapplythefollowingtest(withattributeclosuredonewithrespecttoF)result=

while(changestoresult)do

foreachRiintheposition

t=(resultRi)+Ri

result=resulttIfresultcontainsallattributesin,thenthefunctionaldependency

ispreserved.WeapplythetestonalldependenciesinFtocheckifapositionisdependencypreservingThisproceduretakespolynomialtime,insteadoftheexponentialtimerequiredtocomputeF+and(F1F2…Fn)+ExampleR=(A,B,C)

F={AB

BC}

Key={A}RisnotinBCNFpositionR1=(A,B),R2=(B,C)R1andR2inBCNFLossless-joinpositionDependencypreserving☆TestingforBCNFTocheckifanon-trivialdependencycausesaviolationofBCNF1.compute+(theattributeclosureof),and2.verifythatitincludesallattributesofR,thatis,itisasuperkeyofR.Simplifiedtest:TocheckifarelationschemaRisinBCNF,itsufficestocheckonlythedependenciesinthegivensetFforviolationofBCNF,ratherthancheckingalldependenciesinF+.IfnoneofthedependenciesinFcausesaviolationofBCNF,thennoneofthedependenciesinF+willcauseaviolationofBCNFeither.However,usingonlyFisincorrectwhentestingarelationinapositionofRConsiderR=(A,B,C,D,E),withF={AB,BCD}poseRintoR1=(A,B)andR2=(A,C,D,E)NeitherofthedependenciesinFcontainonlyattributesfrom

(A,C,D,E)sowemightbemisleadintothinkingR2satisfiesBCNF.Infact,dependencyACDinF+showsR2isnotinBCNF.☆TestingpositionforBCNFTocheckifarelationRiinapositionofRisinBCNF,EithertestRiforBCNFwithrespecttotherestrictionofFtoRi(thatis,allFDsinF+thatcontainonlyattributesfromRi)orusetheoriginalsetofdependenciesFthatholdonR,butwiththefollowingtest:foreverysetofattributesRi,checkthat+(theattributeclosureof)eitherincludesnoattributeofRi-,orincludesallattributesofRi.IftheconditionisviolatedbysomeinF,thedependency

(+-)Ri

canbeshowntoholdonRi,andRiviolatesBCNF.WeuseabovedependencytoposeRiExerciseFunctionaldependencyholdsonR(,,)pleaseprovethatisequivalentwith.

Duplicatedattributescanberemovedfromrightsideofafunctionaldependency.

Prove:

,

==>

(reflexivity)

==>

==>

(Augmentation)BCNFpositionAlgorithm

(machineversion) result:={R};

done:=false;

computeF+;

while(notdone)do

if(thereisaschemaRiinresultthatisnotinBCNF)

thenbegin

letbeanontrivialfunctionaldependencythatholdsonRi

suchthatRiisnotinF+,

and=;

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

end

elsedone:=true;Note:eachRiisinBCNF,andpositionislossless-join.BCNFpositionAlgorithm result:={R};

done:=false;

while(notdone)do

if(thereisaschemaRiinresultthatisnotinBCNF)

thenbegin

letbeanontrivialfunctionaldependencythatholdsonRi

suchthatisnotakeyofRi

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

//poseRiinto(,)and(Ri–) end

elsedone:=true;Note:eachRiisinBCNF,andpositionislossless-join.ExampleofBCNFposition