数据库原理与系统ch7 Relational Database Design Normalization课件

Chapter7:RelationalDatabaseDesignChapter7:RelationalDatabas1Chapter7:RelationalDatabaseDesignFeaturesofGoodRelationalDesignAtomicDomainsandFirstNormalFormDecompositionUsingFunctionalDependenciesFunctionalDependencyTheoryAlgorithmsforFunctionalDependenciesDecompositionUsingMultivaluedDependenciesMoreNormalFormDatabase-DesignProcessModelingTemporalDataChapter7:RelationalDatabas2TheBankingSchemabranch=(branch_name,branch_city,assets)customer=(customer_id,customer_name,customer_street,customer_city)loan=(loan_number,amount)account=(account_number,balance)employee=(employee_id.employee_name,telephone_number,start_date)dependent_name=(employee_id,dname)account_branch=(account_number,branch_name)loan_branch=(loan_number,branch_name)borrower=(customer_id,loan_number)depositor=(customer_id,account_number)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)TheBankingSchemabranch=(br3CombineSchemas?Supposewecombineborrowerandloantogetbor_loan=(customer_id,loan_number,amount)Resultispossiblerepetitionofinformation(L-100inexamplebelow)CombineSchemas?Supposewecom4ACombinedSchemaWithoutRepetitionConsidercombiningloan_branchandloanloan_amt_br=(loan_number,amount,branch_name)Norepetition(assuggestedbyexamplebelow)ACombinedSchemaWithoutRepe5WhatAboutSmallerSchemas?Supposewehadstartedwithbor_loan.Howwouldweknowtosplitup(decompose)itintoborrowerandloan?Writearule“iftherewereaschema(loan_number,amount),thenloan_numberwouldbeacandidatekey”Denoteasafunctionaldependency: loan_number

amountInbor_loan,becauseloan_numberisnotacandidatekey,theamountofaloanmayhavetoberepeated.Thisindicatestheneedtodecomposebor_loan.Notalldecompositionsaregood.Supposewedecomposeemployeeinto

employee1=(employee_id,employee_name)

employee2=(employee_name,telephone_number,start_date)Thenextslideshowshowweloseinformation--wecannotreconstructtheoriginalemployeerelation--andso,thisisalossydecomposition.WhatAboutSmallerSchemas?Sup6ALossyDecompositionALossyDecomposition7FirstNormalFormDomainisatomicifitselementsareconsideredtobeindivisibleunitsExamplesofnon-atomicdomains:Setofnames,compositeattributesIdentificationnumberslikeCS101thatcanbebrokenupintopartsArelationalschemaRisinfirstnormalformifthedomainsofallattributesofRareatomicNon-atomicvaluescomplicatestorageandencourageredundant(repeated)storageofdataExample:Setofaccountsstoredwitheachcustomer,andsetofownersstoredwitheachaccountWeassumeallrelationsareinfirstnormalform(andrevisitthisinChapter9)FirstNormalFormDomainisato8FirstNormalForm(Cont’d)Atomicityisactuallyapropertyofhowtheelementsofthedomainareused.Example:StringswouldnormallybeconsideredindivisibleSupposethatstudentsaregivenrollnumberswhicharestringsoftheformCS0012orEE1127Ifthefirsttwocharactersareextractedtofindthedepartment,thedomainofrollnumbersisnotatomic.Doingsoisabadidea:leadstoencodingofinformationinapplicationprogramratherthaninthedatabase.FirstNormalForm(Cont’d)Atom9Goal—DeviseaTheoryfortheFollowingDecidewhetheraparticularrelationRisin“good”form.InthecasethatarelationRisnotin“good”form,decomposeitintoasetofrelations{R1,R2,...,Rn}suchthateachrelationisingoodformthedecompositionisalossless-joindecompositionOurtheoryisbasedon:functionaldependenciesmultivalueddependenciesGoal—DeviseaTheoryforthe10FunctionalDependenciesConstraintsonthesetoflegalrelations.Requirethatthevalueforacertainsetofattributesdeterminesuniquelythevalueforanothersetofattributes.Afunctionaldependencyisageneralizationofthenotionofakey.FunctionalDependenciesConstra11FunctionalDependencies(Cont.)LetRbearelationschema

RandRThefunctionaldependency

holdson

Rifandonlyifforanylegalrelationsr(R),wheneveranytwotuplest1

andt2ofragreeontheattributes,theyalsoagreeontheattributes.Thatis, t1[]=t2[]t1[]=t2[]Example:Considerr(A,B)withthefollowinginstanceofr.Onthisinstance,A

BdoesNOThold,butB

Adoeshold.4153 7FunctionalDependencies(Cont.12FunctionalDependencies(Cont.)KisasuperkeyforrelationschemaRifandonlyifK

RKisacandidatekeyforRifandonlyifK

R,andfornoK,

RFunctionaldependenciesallowustoexpressconstraintsthatcannotbeexpressedusingsuperkeys.Considertheschema:

bor_loan=(customer_id,loan_number,amount).

Weexpectthisfunctionaldependencytohold:

loan_number

amount

butwouldnotexpectthefollowingtohold:

amount

customer_nameFunctionalDependencies(Cont.13UseofFunctionalDependenciesWeusefunctionaldependenciesto:testrelationstoseeiftheyarelegalunderagivensetoffunctionaldependencies.IfarelationrislegalunderasetFoffunctionaldependencies,wesaythatr

satisfiesF.specifyconstraintsonthesetoflegalrelationsWesaythatF

holdson

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

amount

customer_name.UseofFunctionalDependencies14FunctionalDependencies(Cont.)AfunctionaldependencyistrivialifitissatisfiedbyallinstancesofarelationExample:customer_name,loan_number

customer_namecustomer_name

customer_nameIngeneral,

istrivialif

FunctionalDependencies(Cont.15ClosureofaSetofFunctionalDependenciesGivenasetFoffunctionaldependencies,therearecertainotherfunctionaldependenciesthatarelogicallyimpliedbyF.Forexample:IfA

BandB

C,thenwecaninferthatA

CThesetofallfunctionaldependencieslogicallyimpliedbyFistheclosureofF.WedenotetheclosureofFbyF+.F+isasupersetofF.ClosureofaSetofFunctional16Boyce-CoddNormalForm

istrivial(i.e.,

)isasuperkeyforRArelationschemaRisinBCNFwithrespecttoasetFoffunctionaldependenciesifforallfunctionaldependenciesinF+oftheform

where

Rand

R,

atleastoneofthefollowingholds:ExampleschemanotinBCNF:

bor_loan=(customer_id,loan_number,amount)becauseloan_number

amountholdsonbor_loanbutloan_numberis notasuperkeyBoyce-CoddNormalForm17DecomposingaSchemaintoBCNFSupposewehaveaschemaRandanon-trivialdependency

causesaviolationofBCNF. WedecomposeRinto:(U

)(R-(-))Inourexample,=loan_number=amountandbor_loanisreplacedby(U

)=(loan_number,amount)(R-(-))=(customer_id,loan_number)DecomposingaSchemaintoBCNF18BCNFandDependencyPreservationConstraints,includingfunctionaldependencies,arecostlytocheckinpracticeunlesstheypertaintoonlyonerelationIfitissufficienttotestonlythosedependenciesoneachindividualrelationofadecompositioninordertoensurethatallfunctionaldependencieshold,thenthatdecompositionisdependencypreserving.BecauseitisnotalwayspossibletoachievebothBCNFanddependencypreservation,weconsideraweakernormalform,knownasthirdnormalform.BCNFandDependencyPreservati19ThirdNormalFormArelationschemaRisinthirdnormalform(3NF)ifforall:

inF+

atleastoneofthefollowingholds:

istrivial(i.e.,

)isasuperkeyforREachattributeAin–iscontainedinacandidatekeyforR.

(NOTE:eachattributemaybeinadifferentcandidatekey)IfarelationisinBCNFitisin3NF(sinceinBCNFoneofthefirsttwoconditionsabovemusthold).ThirdconditionisaminimalrelaxationofBCNFtoensuredependencypreservation(willseewhylater).ThirdNormalFormArelationsc20GoalsofNormalizationLetRbearelationschemewithasetFoffunctionaldependencies.DecidewhetherarelationschemeRisin“good”form.InthecasethatarelationschemeRisnotin“good”form,decomposeitintoasetofrelationscheme{R1,R2,...,Rn}suchthateachrelationschemeisingoodformthedecompositionisalossless-joindecompositionPreferably,thedecompositionshouldbedependencypreserving.GoalsofNormalizationLetRbe21HowgoodisBCNF?TherearedatabaseschemasinBCNFthatdonotseemtobesufficientlynormalizedConsideradatabase

classes(course,teacher,book)

suchthat(c,t,b)classesmeansthattisqualifiedtoteachc,andbisarequiredtextbookforcThedatabaseissupposedtolistforeachcoursethesetofteachersanyoneofwhichcanbethecourse’sinstructor,andthesetofbooks,allofwhicharerequiredforthecourse(nomatterwhoteachesit).HowgoodisBCNF?Therearedat22Therearenonon-trivialfunctionaldependenciesandthereforetherelationisinBCNFInsertionanomalies–i.e.,ifMarilynisanewteacherthatcanteachdatabase,twotuplesneedtobeinserted (database,Marilyn,DBConcepts)

(database,Marilyn,Ullman)courseteacherbookdatabasedatabasedatabasedatabasedatabasedatabaseoperatingsystemsoperatingsystemsoperatingsystemsoperatingsystemsAviAviHankHankSudarshanSudarshanAviAviPetePeteDBConceptsUllmanDBConceptsUllmanDBConceptsUllmanOSConceptsStallingsOSConceptsStallingsclassesHowgoodisBCNF?(Cont.)Therearenonon-trivialfunct23Therefore,itisbettertodecomposeclassesinto:courseteacherdatabasedatabasedatabaseoperatingsystemsoperatingsystemsAviHankSudarshanAviJimteachescoursebookdatabasedatabaseoperatingsystemsoperatingsystemsDBConceptsUllmanOSConceptsShawtextThissuggeststheneedforhighernormalforms,suchasFourthNormalForm(4NF),whichweshallseelater.HowgoodisBCNF?(Cont.)Therefore,itisbettertodec24Functional-DependencyTheoryWenowconsidertheformaltheorythattellsuswhichfunctionaldependenciesareimpliedlogicallybyagivensetoffunctionaldependencies.WethendevelopalgorithmstogeneratelosslessdecompositionsintoBCNFand3NFWethendevelopalgorithmstotestifadecompositionisdependency-preservingFunctional-DependencyTheoryWe25ClosureofaSetofFunctionalDependenciesGivenasetFsetoffunctionaldependencies,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).ClosureofaSetofFunctional26ExampleR=(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

ItoinferCGCGI,andaugmentingofCG

Htoinfer

CGI

HI,

andthentransitivityExampleR=(A,B,C,G,H,I)

27ProcedureforComputingF+TocomputetheclosureofasetoffunctionaldependenciesF:

F+=F

repeat

foreachfunctionaldependencyfinF+

applyreflexivityandaugmentationrulesonf

addtheresultingfunctionaldependenciestoF+

foreachpairoffunctionaldependenciesf1andf2inF+

if

f1andf2canbecombinedusingtransitivity

thenaddtheresultingfunctionaldependencytoF+

untilF+doesnotchangeanyfurtherNOTE:WeshallseeanalternativeprocedureforthistasklaterProcedureforComputingF+Toc28ClosureofFunctionalDependencies(Cont.)WecanfurthersimplifymanualcomputationofF+byusingthefollowingadditionalrules.If

holdsand

holds,then

holds(union)If

holds,then

holdsand

holds(decomposition)If

holdsand

holds,then

holds(pseudotransitivity)TheaboverulescanbeinferredfromArmstrong’saxioms.ClosureofFunctionalDependen29ClosureofAttributeSetsGivenasetofattributesa,definetheclosure

ofa

under

F(denotedbya+)asthesetofattributesthatarefunctionallydeterminedbyaunderFAlgorithmtocomputea+,theclosureofaunderF

result:=a;

while(changestoresult)do

foreach

inFdo

begin

if

resultthenresult:=result

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

B

A

C

CG

H

CG

I

B

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

CandAB)3. result=ABCGH (CG

HandCGAGBC)4. result=ABCGHI (CG

IandCGAGBCH)IsAGacandidatekey?IsAGasuperkey?DoesAG

R?==Is(AG)+RIsanysubsetofAGasuperkey?DoesA

R?==Is(A)+RDoesG

R?==Is(G)+RExampleofAttributeSetClosu31UsesofAttributeClosureThereareseveralusesoftheattributeclosurealgorithm:Testingforsuperkey:Totestifisasuperkey,wecompute+,andcheckif+

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

byusingattributeclosure,andthencheckifitcontains.Isasimpleandcheaptest,andveryusefulComputingclosureofFForeachR,wefindtheclosure+,andforeachS+,weoutputafunctionaldependencyS.UsesofAttributeClosureThere32CanonicalCoverSetsoffunctionaldependenciesmayhaveredundantdependenciesthatcanbeinferredfromtheothersForexample:ACisredundantin:{A

B,B

C}PartsofafunctionaldependencymayberedundantE.g.:onRHS:{A

B,B

C,A

CD}canbesimplifiedto

{A

B,B

C,A

D}E.g.:onLHS:{A

B,B

C,AC

D}canbesimplifiedto

{A

B,B

C,A

D}Intuitively,acanonicalcoverofFisa“minimal”setoffunctionaldependenciesequivalenttoF,havingnoredundantdependenciesorredundantpartsofdependenciesCanonicalCoverSetsoffunctio33ExtraneousAttributesConsiderasetFoffunctionaldependenciesandthefunctionaldependency

inF.AttributeAisextraneousinifA

andFlogicallyimplies(F–{

}){(–A)

}.AttributeAisextraneousinifA

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

CcanbeinferredevenafterdeletingCExtraneousAttributesConsider34TestingifanAttributeisExtraneousConsiderasetFoffunctionaldependenciesandthefunctionaldependency

inF.TotestifattributeAisextraneous

in

compute({}–A)+usingthedependenciesinF

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

TotestifattributeA

isextraneousin

compute+usingonlythedependenciesin

F’=(F–{

}){

(

–A)},checkthat+containsA;ifitdoes,Aisextraneousin

TestingifanAttributeisExt35CanonicalCoverAcanonicalcover

forFisasetofdependenciesFcsuchthatFlogicallyimpliesalldependenciesinFc,andFc

logicallyimpliesalldependenciesinF,andNofunctionaldependencyinFc

containsanextraneousattribute,andEachleftsideoffunctionaldependencyinFc

isunique.TocomputeacanonicalcoverforF:

repeat

UsetheunionruletoreplaceanydependenciesinF

1

1and1

2with1

1

2

Findafunctionaldependency

withan

extraneousattributeeitherinorin

Ifanextraneousattributeisfound,deleteitfrom

untilFdoesnotchangeNote:Unionrulemaybecomeapplicableaftersomeextraneousattributeshavebeendeleted,soithastobere-appliedCanonicalCoverAcanonicalcov36ComputingaCanonicalCoverR=(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

BandBC.CanuseattributeclosureofAinmorecomplexcasesThecanonicalcoveris: A

B

B

CComputingaCanonicalCoverR=37Lossless-joinDecompositionForthecaseofR=(R1,R2),werequirethatforallpossiblerelationsronschemaR

r=R1

(r)R2

(r)AdecompositionofRintoR1andR2islosslessjoinifandonlyifatleastoneofthefollowingdependenciesisinF+:R1

R2

R1R1

R2

R2Lossless-joinDecompositionFor38ExampleR=(A,B,C)

F={A

B,B

C)CanbedecomposedintwodifferentwaysR1=(A,B),R2=(B,C)Lossless-joindecomposition:

R1R2={B}

andB

BCDependencypreservingR1=(A,B),R2=(A,C)Lossless-joindecomposition:

R1R2={A}

andAABNotdependencypreserving

(cannotcheckB

CwithoutcomputingR1

R2)ExampleR=(A,B,C)

F={A39DependencyPreservation

LetFi

bethesetofdependenciesF+thatincludeonlyattributesinRi.Adecompositionisdependencypreserving,if(F1

F2…Fn)+=F+Ifitisnot,thencheckingupdatesforviolationoffunctionaldependenciesmayrequirecomputingjoins,whichisexpensive.DependencyPreservationLetFi40TestingforDependencyPreservationTocheckifadependencyispreservedinadecompositionofRintoR1,R2,…,Rnweapplythefollowingtest(withattributeclosuredonewithrespecttoF)result=

while(changestoresult)do

foreach

Ri

inthedecomposition

t=(resultRi)+Ri

result=resulttIfresultcontainsallattributesin,thenthefunctionaldependency

ispreserved.WeapplythetestonalldependenciesinFtocheckifadecompositionisdependencypreservingThisproceduretakespolynomialtime,insteadoftheexponentialtimerequiredtocomputeF+

and

(F1

F2…Fn)+

TestingforDependencyPreserv41ExampleR=(A,B,C)

F={A

B

BC}

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

andR2inBCNFLossless-joindecompositionDependencypreservingExampleR=(A,B,C)

F={A42TestingforBCNFTocheckifanon-trivialdependency

causesaviolationofBCNF1.compute+(theattributeclosureof),and2.verifythatitincludesallattributesofR,thatis,itisasuperkeyofR.Simplifiedtest:TocheckifarelationschemaRisinBCNF,itsufficestocheckonlythedependenciesinthegivensetFforviolationofBCNF,ratherthancheckingalldependenciesinF+.IfnoneofthedependenciesinFcausesaviolationofBCNF,thennoneofthedependenciesinF+willcauseaviolationofBCNFeither.However,usingonlyFisincorrectwhentestingarelationinadecompositionofRConsiderR=(A,B,C,D,E),withF={AB,BCD}DecomposeRintoR1=

(A,B)andR2=

(A,C,D,E)NeitherofthedependenciesinFcontainonlyattributesfrom

(A,C,D,E)sowemightbemisleadintothinkingR2satisfiesBCNF.Infact,dependencyAC

DinF+showsR2isnotinBCNF.TestingforBCNFTocheckifa43TestingDecompositionforBCNFTocheckifarelationRiinadecompositionofRisinBCNF,EithertestRiforBCNFwithrespecttotherestrictionofFtoRi(thatis,allFDsinF+thatcontainonlyattributesfromRi)orusetheoriginalsetofdependenciesFthatholdonR,butwiththefollowingtest:foreverysetofattributesRi,checkthat+(theattributeclosureof)eitherincludesnoattributeofRi-,orincludesallattributesofRi.IftheconditionisviolatedbysomeinF,thedependency

(+-)Ri

canbeshowntoholdonRi,andRiviolatesBCNF.WeuseabovedependencytodecomposeRiTestingDecompositionforBCNF44BCNFDecompositionAlgorithm

result:={R};

done:=false;

computeF+;

while(notdone)do

if(thereisaschemaRi

inresultthatisnotinBCNF)

thenbegin

let

beanontrivialfunctionaldependencythatholdsonRi

suchthat

Ri

isnotinF+,

and

=;

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

end

elsedone:=true;Note:eachRi

isinBCNF,anddecompositionislossless-join.BCNFDecompositionAlgorithm r45ExampleofBCNFDecompositionR=(A,B,C)

F={A

B

BC}

Key={A}RisnotinBCNF(BCbutBisnotsuperkey)DecompositionR1=(B,C)R2=(A,B)ExampleofBCNFDecompositionR46ExampleofBCNFDecompositionOriginalrelationRand

functionaldependencyFR=

(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,R4ExampleofBCNFDecompositionO47BCNFandDependencyPreservationR=(J,K,L)

F={JK

L

L

K}

Twocandidatekeys=JKandJLRisnotinBCNFAnydecompositionofRwillfailtopreserve

JK

LThisimpliesthattestingforJK

LrequiresajoinItisnotalwayspossibletogetaBCNFdecompositionthatisdependencypreservingBCNFandDependencyPreservati48ThirdNormalForm:MotivationTherearesomesituationswhereBCNFisnotdependencypreserving,andefficientcheckingforFDviolationonupdatesisimportantSolution:defineaweakernormalform,calledThirdNormalForm(3NF)Allowssomeredundancy(withresultantproblems;wewillseeexampleslater)Butfunctionaldependenciescanbecheckedonindividualrelationswithoutcomputingajoin.Thereisalwaysalossless-join,dependency-preservingdecompositioninto3NF.ThirdNormalForm:MotivationT493NFExampleRelationR:R=(J,K,L)

F={JK

L,L

K}Twocandidatekeys:JKandJLRisin3NF

JK

L JKisasuperkey

L

K Kiscontainedinacandidatekey3NFExampleRelationR:50Redundancyin3NFJj1j2j3nullLl1l1l1l2Kk1k1k1k2repetitionofinformation(e.g.,therelationshipl1,k1)needtousenullvalues(e.g.,torepresenttherelationship

l2,k2wherethereisnocorrespondingvalueforJ).ThereissomeredundancyinthisschemaExampleofproblemsduetoredundancyin3NFR=(J,K,L)

F={JK

L,L

K}Redundancyin3NFJj1Ll1Kk1The51Testingfor3NFOptimization:NeedtocheckonlyFDsinF,neednotcheckallFDsinF+.Useattributeclosuretocheckforeachdependency,ifisasuperkey.Ifisnotasuperkey,wehavetoverifyifeachattributeiniscontainedinacandidatekeyofRthistestisrathermoreexpensive,sinceitinvolvefindingcandidatekeystestingfor3NFhasbeenshowntobeNP-hardInterestingly,decompositionintothirdnormalform(describedshortly)canbedoneinpolynomialtimeTestingfor3NFOptimization:N523NFDecompositionAlgorithm

LetFc

beacanonicalcoverforF;

i:=0;

foreachfunctionaldependency

inFc

do

ifnoneoft