数据库原理教程 课件 杜金莲 第4-7章 关系数据库设计理论-数据库的安全与控制

第4章:关系数据库设计理论

RelationalDatabaseDesign不合理的关系模式带来的问题函数依赖和范式的定义多值依赖及第4范式函数依赖理论关系的规范化§1.不好的关系模式带来的问题FIRST（sno，city，zip，pno，pname,qty）

FIRST（snocityzippnopnameqty）s1c1z1p1nut100s1c1z1p2bolt200s2c2z2p1nut160s2c2z2p3worm320存在问题？1)数据冗余度太大.2）删除异常.3）插入异常.

S(sno，city，zip)s1c1z1s2c2z2

SP(sno，pno，qty)s1p1100s1p2200s2p1160s2p3320

P(pno，pname)p1nutp2boltp3worm§2.函数依赖及范式的定义

FunctionalDependencies§2.1.函数依赖:属性间的依赖关系1.函数依赖:设R(U)是属性集U上的关系模式,X，Y

U。如果对于R(U)的任意一个关系r，以及r的任意两个元组t1，t2，不存在：t1[x]=t2[x]，而t1[Y]

t2[Y]，则称X函数决定Y，或者说Y函数依赖于X。记为：X

Y。

注：1）“X

Y”必须对R（U）的任何一个关系实例都成立。

2）若X

Y，Y

X，则记作X←→Y。若Y不函数依赖X，则记作XY。snocnocnamegrade95121011op8595121012db8695121021op8895121022db7895121014ma90FunctionalDependencies(Cont.)Example1.A=(sno,cno),B=(grade)A

B==(sno,cno)gradeFunctionalDependencies(Cont.)函数依赖是现实世界数据关联的形式之一。Example2.FIRST（sno，city，zip，pno，qty）

snopno?

snozip?

(sno,pno)

qty?

(sno,pno)

zip?zip

city?sno

city?Example3.设一个关系模式需保存如下属性R={SN，SD，MN，CN，G}。其中：SN：学生，SD：系，MN：系负责人，CN：课程，G：成绩。

已知：现实世界规定如下：a.一个学生只属于一个系；b.一个系只有一名负责人；c.每个学生学过一门课，最多获得一个成绩。F={SN

SD，SD

MN,(SN，CN）

G}FunctionalDependencies(Cont.)FunctionalDependencies(Cont.)Kisacandidatekey(候选码）forRifandonlyifK

R,andforno

K,

RExample4.R=(SN，CN,GRADE）(SN，CN）

GRADESN

GRADECN）

GRADE2.完全函数依赖与部分函数依赖1)完全函数依赖：在R（U）中，如果X

Y，且对X的任何一个真子集X’，都有X’Y，则称Y对X完全函数依赖，记作：XfY.YABY(A,B)YfY2)部份函数依赖：1)的条件下，如果存在X’

Y，则称Y对X部份函数依赖，记作XPY.YYAB(A,B)YpExample5.R=(sno,city,zip,pno,qty）(sno,pno)

qty?（sno，pno）f

qty（sno，pno)zip?snozip?（sno，pno）pzipsnopnozipQty

3.传递函数依赖：在R(U)中,如果X→Y，YX,(Y

X）,Y→Z，则称Z传递函数依赖于X，记为:XtZ.

Example6.R=(sno，city，zip，pno，qty）sno

zipzipcitysnot

citysnozipcity

4.非平凡的函数依赖：若X→Y，且Y

X，则称X→Y是非平凡的函数依赖。Example7.R=（sno，city，zip，pno，qty）(sno,pno)

qty非平凡的函数依赖(sno,pno)

pno

平凡的函数依赖§2.2.范式的定义NormalForm1.范式：指关系数据库中所有关系要满足的属性间依赖的要求。要求不同，范式不同，根据要求从低到高，有六个范式：1NF，2NF，3NF，BCNF，4NF，5NF。2.1NF（1NormalForm)：即关系模式的各属性域必须是“原子”的，则该关系模式是第一范式的.3.2NF：设R是一个关系模式。若R

1NF，且每一个非主属性完全函数依赖于码，则R

2NF。理解：若R2NF，则R中不存在非主属性对码的部份函数依赖!!!Example8.R=（sno，city，zip，pno，qty）KEY=（Sno，pno）∵存在（sno，pno）Pcity，zip∴R

2NFS（sno，city，zip），KEY=（sno）SP（sno，pno，qty），KEY=（sno，pno）S

2NF，SP

2NF。因而，整个关系数据库模式也是2NF的。4.3NF:如果关系模式R是2NF的，且不存在键码X、属性组Y以及非主属性Z（Z

Y），使得X→Y，Y→Z成立，则R∈3NF（Y

X）理解：若R∈3NF，则R中不存在非主属性对码的传递函数依赖!!!Example9.S(sno，city，zip），KEY=（sno）S

2NFS不是3NF

。

sno

zip

cityS(sno,zip），KEY=（sno）ZC(city,zip）Key=(zip)S,ZC均属于是3NF

。Example10.关系模式STJ（S，T，J）其中：S：学号；T：教师；J：课程。规定：a.一个教师教一门课，一门课可以有不止一个教师讲授；b.一个学生选一门课，就确定一位教师。STJ是几范式？STJ∈3NF。问题：如何形式化的确定R的键码？？？如何求解键码？只出现在函数依赖左边的属性，必定是构成键码的属性；只出现在函数依赖右边的属性，必定不是构成键码的属性；不出现在函数依赖中的属性，也必定是构成键码的属性；既出现在左边，也出现在右边的属性则可能是顾全构成键码的属性。例1：给定关系模式R（X,Y,Z,U,V,W），依赖集F={X

Z,XY

Z,Z

UW,ZV

XY,ZU

W,VW

Z}，求：R的所有键码?如何求解键码？答案：R的键码有两个：XV和ZV练习：关系模式R（X,Y,Z,W），F={X

Z,Z

X,Y

XZ,W

XZ}：求R的所有键码?目前来讲最高达到几范式？

5.BCNF：设：R∈1NF,如果对于R的每一个函数依赖X→Y（Y

X）X是超码，则:R∈BCNF。Example11.R=(A,B,C,G,H,I),key1=(AB),key2=(CG)则如果R是BCNF，其允许存在以下依赖：F={AB

G,ABC

H,ABCG

H,ABG

I,CGH,CGA,CGI,CGB}Example11.R=(A,B,C,G,H,I),key1=(AB),key2=(CG)No{AH,BI,GA,HAI,HIA}inF依赖：非主属性部分依赖于码；

主属性部分依赖于不包含它的键码；

主属性依赖于非主属性.

理解：BCNF具有以下性质：a.所有非主属性完全依赖于每个键码。b.所有主属性完全依赖于不包含它的键码。c.没有任何（主/非主）属性完全函数依赖于任一非主属性(组)。在函数依赖范畴内，BCNF达到最高规范化程度!!!Example12.STJ（S，T，J）PPT21F={T→J,（S，J）→T}其中：key=(S,J)orkey=(S,T)STJ∈3NF但STJ不是BCNF？why?存在主属性J部分依赖于不包含它的码（S,T)§3.多值依赖及第4范式

MultivaluedDependenciesand4NF§3.1MultivaluedDependenciesExmaple13.Consideradatabase classes(course,teacher,book)

某学校一门课由多名教师讲授，他们都是使用同一套参考书。一名教师也可以讲多门课。具体数据非规范地表示如下：课程名老师参考书databaseAviHankSudarshanDBConceptsUllmanoperatingsystemsAviJimOSConceptsShawMultivaluedDependencies(Cont.)courseteacherbookdatabasedatabasedatabasedatabasedatabasedatabaseoperatingsystemsoperatingsystemsoperatingsystemsoperatingsystemsAviAviHankHankSudarshanSudarshanAviAviJimJimDBConceptsUllmanDBConceptsUllmanDBConceptsUllmanOSConceptsShawOSConceptsShawClasses(course,teacher,book)MultivaluedDependencies(Cont.)classes(course,teacher,book)的键码?classes∈BCNF但仍然存在信息重复(冗余)插入异常InsertionanomaliesifSaraisanewteacherthatcanteachdatabase,twotuplesneedtobeinserted

(database,Sara,DBConcepts)

(database,Sara,Ullman)why?MultivaluedDependencies(Cont.)MultivaluedDependencies(Cont.)ABCa1a2a3b1b2c1c2X=courseY=bookz1z2zbzczszdZ=teacherMultivaluedDependencies(MVDs)设：R是属性集U上的一个关系模式，X,Y和Z都是U的子集,并且Z=U–X–Y.多值依赖X

Y成立，当且仅当对于关系模式R的任意一个关系r，r在X上的一个值对应唯一一组Y值，且这组Y值与Z的值无关。courseteacherbookdatabasedatabasedatabasedatabasedatabasedatabaseoperatingsystemsoperatingsystemsoperatingsystemsoperatingsystemsAviHank

AviHankSudarshanSudarshanAviAviJimJimDBConceptsUllmanUllmanDBConceptsDBConceptsUllmanOSConceptsShawOSConceptsShawMultivaluedDependencies(MVDs)LetRbearelationschemaandlet

Rand

R.Themultivalueddependency

holdsonRifinanylegalrelationr(R),forallpairsfortuplest1andt2inrsuchthatt1[

]=t2[

],thereexisttuplest3andt4inrsuchthat:

t1[

]=t2[

]=t3[

]=t4

[

]

t3[

]=t1[

]

t3[R–

]=t2[R–

]

t4[

]=t2[

]

t4[R–

]=t1[R–

]MVD(Cont.)Tabularrepresentationof

多值依赖的相关结论TheoryofMVDsFromthedefinitionofmultivalueddependency,wecanderivethefollowingrules:If

,then

Thatis,everyfunctionaldependencyisalsoamultivalueddependency多值依赖具有对称性：若X→→Y，则必有X→→Z（Z=U-X-Y）。若X→→Y，当YX或

Z=U-X-Y=Φ，则称为X→→Y为平凡的多值依赖。否则就是非平凡的MVDscourseteacherdatabasedatabasedatabaseoperatingsystemsoperatingsystemsAviHankSudarshanAviJimcourse

teacheristrivial!!!!平凡的■多值依赖的传递性：若X→→Y，Y→→Z（Z=U-X-Y）则X→→Z。设关系模式R

1NF。如果对于R的每个非平凡多值依赖X

Y，X都是超码，则R

4NF。§3.2FourthNormalForm(4NF)理解：4NF是对属性依赖中的非平凡多值依赖的一种约束!!!!，将每个非平凡的多值依赖左端限制为超码，实际上说明这个多值依赖是函数依赖！ArelationschemaRisin4NFwithrespecttoasetDoffunctionalandmultivalueddependenciesifforallmultivalueddependenciesinD+oftheform

,where

Rand

R,atleastoneofthefollowinghold:

istrivial(i.e.,

or

=R)

isasuperkeyforschemaRIfarelationisin4NFitisinBCNFcourseteacherbookdatabasedatabasedatabasedatabasedatabasedatabaseoperatingsystemsoperatingsystemsoperatingsystemsoperatingsystemsAviAviHankHankSudarshanSudarshanAviAviJimJimDBConceptsUllmanDBConceptsUllmanDBConceptsUllmanOSConceptsShawOSConceptsShawClasses(course,teacher,book)不是4NFcourseteacherdatabasedatabasedatabaseoperatingsystemsoperatingsystemsAviHankSudarshanAviJim(Course，teacher)∈4NFcoursebookdatabasedatabaseoperatingsystemsoperatingsystemsDBConceptsUllmanOSConceptsShaw(course,book)∈4NF范式间关系的小结消去非主属性对码的部分函数依赖消去非主属性对码的传递函数依赖消去主属性对码的部分和传递函数依赖消去非平凡且非函数依赖的多值依赖1NF2NF3NFBCNF4NF§4.函数依赖理论

FunctionalDependencies4.1.函数依赖的逻辑蕴涵设：F是R给定的一组函数依赖集合。若能够用逻辑推理的方法导出其它的函数依赖(如X→Y)，则称F逻辑蕴涵X→Y。记为F

X→YExmaple14.IfF={A

B，B

C},thenwecaninferthatA

CF

A

CF及由F所蕴含的所有的函数据依赖的集合，称为F的闭包.记作：F+.F+

利用

Armstrong’sAxioms可求得:if

,then

(自反reflexivity)if

,then

(增广augmentation)if

,and

,then

(传递transitivity)4.2.函数依赖的闭包FourrulesinferedbyArmstrong’sAxioms:合并：若X→Y，X→Z，则X→YZ分解：若X→YZ，则X→Y,X→Z伪增广：若X→Y，W

Z，有XW→YZ伪传递：由X→Y，WY→Z，有WX→Z.Theserulesaresound

(generateonlyfunctionaldependenciesthatactuallyhold)andcomplete(generateallfunctionaldependenciesthathold).ClosureofaSetofFunctionalDependenciesExample15.R=(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

CGandthentransitivitywithCG

I

CG

HIfromCG

HandCG

I

AG

HFromA

CandCG

H………………..Example16.R（A，B，C），F={A→B，B→C}

A→Ф，AB→Ф，AC→Ф，ABC→Ф，B→Ф，C→ФA→A，AB→A，AC→A，ABC→A，B→B，C→C

A→B，AB→B，AC→B，ABC→B，B→C，F+

=A→C，AB→C，AC→C，ABC→C，B→BC，A→AB，AB→AB，AC→AB，ABC→AB，BC→Ф，A→AC，AB→AC，AC→AC，ABC→AC，BC→B，A→BC，AB→BC，AC→BC，ABC→BC，BC→C，

A→ABC，AB→ABC，AC→ABC，ABC→ABC，BC→BC，ClosureofaSetofFunctionalDependencies4.3.属性的闭包ClosureofAttributeSetsF为属性集U上给定的一组函数依赖,a,

U。则a+F称为属性集a关于函数依赖集F的闭包。a+F={

|a→

是所有由F给定和导出的函数依赖集合}。Example16.R（A，B，C），F={A→B，B→C}A+F={ABC}Algorithmtocomputea+F,theclosureofaunderF:result:=a;

while(changestoresult)do

foreach

inFdo

if

resultthenresult:=result

a+F=resultClosureofAttributeSetsExampleofAttributeSetClosureExample17.R=(A,B,C,G,H,I)F={A

B,A

C, CG

H,CG

I, B

H}(AG)+PROCEDURE:1. result=AGResult=ABCG (A

CandA

B)3. result=ABCGH (CG

HandCG

AGBC)4. result=ABCGHI (CG

IandCG

AGBCH)4.4.属性闭包用途UsesofAttributeClosure属性闭包有以下用途:Testingforcandidatekey:(确定键(候选)码)Testingfunctionaldependencies(确定FD)Tocheckifafunctionaldependencyholds(or,inotherwords,isinF+),justcheckif+.Isasimpleandcheaptest,andveryusefulComputingclosureofF(计算F+)。如何确定属性组AG是键码(IsAGacandidatekey)?DoesAG

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

R?==Is(A)+RDoesG

R?==Is(G)+R（1）确定关系模式的键码Example18.R=(A,B,C,G,H,I)F={A

B,A

C,CG

H,CG

I,B

H}(AG)+=ABCGHI IsAGacandidatekey?A+=ABCHG+=GAGisakeyofR!!!!Example19.R=(C,G,S)F={CS

G},FindallcandidatekeysforR(C)+=C,(G)+=G，(S)+=S

(CG)+=CG,(CS)+=CSG,(SG)+=SGCSRSTOP!CSisakeyofR!!!!（2）判定一个函数依赖是否属于F+？设：R（U，F），属性组X，Y

U。

问：函数依赖X→Y是否被F逻辑蕴涵？

计算:X+。判定:Y

X+?Example20.F={AB,BC}问：ABCF+？

(AB)+F={ABC}，显然有：C

(AB)+FAB

C

F+（3）判定两个函数依赖集是否等价如果F+=G+，就说函数依赖集F和G相互覆盖，或F与G等价，记为F=G。F=G的充分必要条件是F

G+

,

且G

F+判定:F=G？判断F中的每一个依赖是否属于G+判断G中的每一个依赖是否属于F+Example21.F={AB,BC，AB

C

}，G={AB,BC

}F=G？AB

C

∈G+？？？？AB+G=ABCC∈AB+G有F

G+同理有：GF+F=G成立!!4.5正则覆盖CanonicalCoverR的依赖集F中有冗余的依赖存在Eg:A

Cisredundantin:{A

B,B

C,A

C}PartsofafunctionaldependencymayberedundantE.g.onRHS:{A

B,B

C,A

CD}canbesimplifiedto{A

B,B

C,A

D}E.g.onLHS:{A

B,B

C,ABC

D}

canbesimplifiedto{A

B,B

C,AC

D}F的正则覆盖是一个与F等价的极小函数据依赖集Fm，Fm中没有冗余的函数依赖!!!!F中没有“冗余”函数依赖。F中每个函数依赖的右部仅含一个属性。F中每个函数依赖的“左”部都没有“多余”的属性TocomputeacanonicalcoverforF:应用分解规则，使F中每一个函数依赖的右部属性单一化。去掉各函数依赖左部多余的属性。去掉“多余”的函数依赖。ExampleofComputingaCanonicalCoverExmaple22.R=(A,B,C,D)

F={AB

C，BD，D

CA,BA}求Fm?分解右部属性，去除多余依赖：F={AB

C,BD

,DC，D

A，BA}}消去函数依赖左部多余属性：F={ABC,BD,D

C，D

A}令B多余G={A

C,BD,D

C，D

A}F=G？否G={BC，BD,D

C，D

A}令A多余F=G？是Fm={BD,D

C，D

A}Thecanonicalcoveris:{BD,D

C，D

A}Exmaple22（续）.R=(A,B,C,D,E)

F={AB

DE，C

E，D

C,E

A}求Fm?分解:{AB

D,ABE,C

E,D

C,E

A}消去函数依赖左部多余属性：F={AB

D,CE,D

C,E

A},令B多余G={AD,CE,D

C,E

A}F与G是否等价？（不等价）F={AB

D,CE,D

C,E

A},令A多余

G={BD,CE,D

C,E

A}F与G是否等价？（不等价）A，B均不多余！Fm={AB

D,CE,D

C,E

A}§5.关系的规范化Normalization把一个关系模式R分解成若干个不相包含的关系模式{R1,R2…Rn}的操作E.g.R=(branch-name,branch-city,assets,customer-name,loan-number,amount)R1=(branch-name,branch-city,assets)R2=(customer-name,loan-number,branch-name,amount)Allattributesofanoriginalschema(R)mustappearinthedecomposition(R1,R2): R=R1

R2…Rn§5.1模式分解Decomposition§5.2关系投影U1UkExample23:DecompositionofR=(Eno,Es,Eg)into

R1=(Eno,Es)and R2=(Eno,Eg)关系r1关系rk关系rU(u1…un)r1=U1(r)R1EnoEsE013E024E034

R2EnoEgE012600E022200E032200

REnoEsEgE0132600E0242200E03422001.无损连接分解Lossless-joinDecompositionR=R1R2Lossless-joindecomposition.ForallpossiblerelationsronschemaR

r=

R1(r)R2(r)Otherwise,itisLossy-JoinDecomposition(有损分解)

r≠

R1(r)R2(r)ExampleofLossy-JoinDecompositionE.g.R=(A,B,C)→R1=(A,B),R2=(B,C)

A(r)B(r)=AB1422rC35A14

A(r)B22

B(r)B22C35AB11442222C3535E.g.R=(A,B,C):F={A->B,C->B}key=ACR→R1=(A,B),R2=(A,C)

A(r)B(r)=AB1423rC35A14

A(r)B23

B(r)A14C35AB1423C35如果(U1

U2)

(U1-U2)F+,或者：

(U1

U2)

(U2-U1)F+。

定理：设有关系模式R(U，F)，以及R的一个分解ρ={R1(U1，F1)，R2(U2，F2)}。则，分解ρ是具有无损连接性的。如何判断一个模式分解具有无损连接性？例：一个分解具有无损连接性的例子。设：关系模式R（Eno，Es，Eg）。

F={Eno→Es,Es→Eg}现有分解：ρ={R1(Eno，Es)，R2(Es，Eg)},问：该分解具有无损连接性吗？根据定理，分解ρ具备无损连接性。易见，（Es

→Eg）∈

F+R1EnoEsE013E024E035

R2EsEg326004220052200

REnoEsEgE0132600E0242200E0352200反例：

一个分解不具有无损连接性的例子。设：关系模式R（Eno，Es，Eg）。

F={Eno→Es,Es→Eg}现有分解：ρ={R1(Eno，Eg)，R2(Es，Eg)},问：该分解具有无损连接性吗？根据定理，分解ρ不具备无损连接性。易见，（Eg

→Es）

F+,（Eg

→Eno）

F+R2EsEg326004220052200

R1EnoEgE012600E022200E032200

REnoEsEgE0132600E0242200E0352200

R1R2EnoEsR1.EgE0132600E0242200E0252200E0342200E0352200显然子模式自然连接后的结果与原关系不等，所以不具备无损连接性。伪元组当R分解成多个子模式时，如何判定分解是否具有无损连接性？例：

设有关系模式R=（U，F）。其中：

U={A，B，C，D，E}F={A→D,E→D,D→B,BC→D,CD→A}。现有R的一个分解：ρ={R1(A,B)，R2(A,E)，R3(C,E),R4(B,C,D),R5(A,C)

}。问：R的分解是无损连接性的吗？解：（i）初始化：创建5行5列的矩阵，并赋初值ABCDER1a1a2b13b14b15R2a1b22b23b24a5R3b31b32a3b34a5R4b41a2a3a4b45R5a1b52a3b54b55（ii）根据函数依赖集F，反复检查、修改矩阵元，直到F中任何一个函数依赖X→Y，矩阵元取值都不改变。ABCDER1a1a2b13b14b15R2a1b22b23b24a5R3b31b32a3b34a5R4b41a2a3a4b45R5a1b52a3b54b55ABCDER1a1a2b13b14b15R2a1b22b23b24a5R3b31b32a3b34a5R4b41a2a3a4b45R5a1b52a3b54b55F={A→D,E→D,D→B,BC→D,CD→A}。●根据A→D检查、修改矩阵元。●根据E→D检查、修改矩阵元。A→D,E→D,b14b14b14ABCDER1a1a2b13b14b15R2a1b22b23b24a5R3b31b32a3b34a5R4b41a2a3a4b45R5a1b52a3b54b55F={A→D,E→D,D→B,BC→D,CD→A}。A→D,b14b14E→D,b14D→B,a2BC→D,a4CD→Aa1a1a4a4a4a2a2（iii）结论：∵矩阵的第三行元素为a1,a2,a3,a4,a5，它都是由形为ai(i=1,…,m)的元素构成，∴R的分解是无损连接性的。●反复使用函数依赖集，直到矩阵元都不改变。●当某列上的一个bij改为bkj(k＜j)或aj时，应该把同一列、其它行上所有取值为bij的矩阵元都要改成bkj或aj。算法要点：●使用函数依赖集检查、修改矩阵元之后，若矩阵上存在一行，它都是由形为ai(i=1,…,m)的元素构成，则分解是无损连接性的；否则分解不具有无损连接性。

§5.3依赖的投影关系模式R1(U1,F1)关系模R(U,F)关系模式Rk(Uk,Fk)F+=>{F1∪F2∪…

∪Fk}E.g.R（A，B，C），F={A→B，B→C}

R1(U1,F1)，其中U1={B,C}。问：F1=?

R2(U2,F2),U2={A,B}问：此时F2=?Fi的算法：Ri(Ui，Fi)是R分解得到的一个子模式，A是Ui的一个真子集，即A

Ui

对于所有A

Ui，计算A+F和A+F∩Ui根据上面的结果构造FiExample24.R（U，F），U={A，B，C，D}，F={A→B，B→C，C→D，D→A},ρ={R1(A,B,C)，R2(C,D)},求：F在R1、R2上的投影F1、F2

求解过程：U1=ABC，U2=CDForU1,A+,B+,C+,AB+,AC+,BC+

A+=ABCD,A+∩U1=ABC=>A→B,A→CB+=ABCD，B+

∩U1=ABC=>B→A,B→CC+=ABCDC+

∩U1=ABC=>C→A,C→BAB+=ABCDAB+∩

U1=ABC=>AB→CAC+=ABCDAC∩U1=ABC=>AC→BBC+=ABCDBC∩u1=ABC=>BC→AF1={A→B，A→C,B→A,B→C,C→A,C→B,

AB→C,

AC→B,BC→A}F1={A→B,B→C,C→A}用同样的方法计算F2={C→D，D→C}(课堂练习)1.保持依赖的分解Dependencypreservation

(F1

F2…Fn)+=F+

Otherwise,isNotdependencypreserving

.2.判定保持函数依赖性的算法（2）若F

G+，

则ρ是保持函数依赖性的。（1）计算G=∪Fiki=1G

F+!FF1...FkG:F+例:设：R（U，F），U={A，B，C，D}，F={A→B，B→C，C→D，D→A}，ρ={R1(A,B,C)，R2(C,D)}。

问：ρ是否保持函数依赖？

F2={C→D，D→C}。（1）计算：G=F1∪F2

={A→B，B→C，C→A，C→D，D→C}（2）对于D→A∈F,∵D+G={ABCD}∴A

D+G即:D→A∈G+；而对于F中的AB、B→C和C→D，它们显然属于G+。解：得到:F1={A→B，B→C,C→A}

故：ρ对R的分解是保持函数依赖性的。准则：WhenwedecomposearelationschemaRwithasetoffunctionaldependenciesFintoR1,R2,..,RnwewantLossless-joindecomposition:Otherwisedecompositionwouldresultininformationloss.Dependencypreservation:LetFi

bethesetofdependenciesF+thatincludeonlyattributesinRi.§5.4模式分解的准则及相关结论结论：R一定可以无损连接性地分解成若干个BCNF(甚至是4NF）的子模式R一定可以保持函数依赖性地分解成若干个3NF的子模式，但不一定能达到BCNF。R可以既保持函数依赖性，又实现无损连接性地分解形成一些3NF的子模式，但不一定能分解而形成BCNF的子模式。§5.5无损连接分解到BCNF的算法E.g.R=(A,B,C)

F={A

B，B

C}

Key={A}RisnotinBCNFHowtoDecomposeRintoR1andR2?R1

andR2inBCNFLossless-joindecomposition算法：R(U，F)初始,令ρ={R(U，F)}

重复以下步骤，直到ρ的所有关系模式都是BCNF的:找出ρ中不是BCNF的关系模式Ri(Ui，Fi)，其中必有：X→Y∈Fi，而X不含Ri的键码。计算：XFi+，并令：A=XFi+-X把Ri分解成为子模式Ri1和Ri2，其中：Ri1=XFi+，Ri2=Ui–A计算Fi在Ri1和Ri2的投影，以及Ri1和Ri2的键码。Example25：R={C，T，H，R，S，G}F={CS→G,C→T,HR→C,HS→R,TH→R}

KEY={HS}ρ={R}

ρ

=RF={CS→G，C→T

HR→C，HS→RTH→R}KEY=HS(CS)F+={CSGT}R1=CSGTF1={C→T,CS→G}KEY=CS

R2=CHRSF2={CH→R，HR→C,HS→C，HS→R}KEY=HSρ={R1,R2}CS→GR1=CSGTF1={C→T,CS→G}KEY=CS(C)F1+={CT}R11=CT{C→T}KEY=CR12=CGS{CS→G}KEY=CS

R2=CHRSF2={CH→R，HR→C,HS→C，HS→R}KEY=HS(CH)F2+={CHR}R21=CHR{CH→R,HR→C}KEY=CH/HRR22=CHS{HS→C}KEY=HSBCNFBCNFBCNFBCNF注:失去函数依赖TH→Rρ={R11,R12,R21,R22}§5.6保持依赖分解到3NF的算法算法：R(U，F)计算F的正则覆盖Fm。若Fm中仅有一个函数依赖X→Y，且XY=U，则ρ={R（U，Fm）},并结束算法，否则：把U中与Fm的所有函数依赖的左部和右部都无关的属性，从U中分离出去，并使它们构成一个关系模式R0（R0至少是3NF的！）。设Fm剩余的属性构成属性集U0

按照Fm中各函数依赖的左部属性，把Fm划分为F1，…，Fk，使得每个Fi（i=1，2，…，k）的所有函数依赖的左部都相同。根据Fi所包含的属性构造Ui。并由此构造关系模式Ri(Ui,Fi)。于是，可得R的一个分解ρ={R0，R1，…，Rk}，且有：∪ki=1Ui=U0

对于1i,jk(i≠j),若Ui

Uj,则把Ri“合并”到Rj。Example26：R={Eno，En,Es，Eg}F={Eno→EnEsEg，En→Eno,Es→Eg}求Fm={Eno→En，Eno→Es，En→Eno,Es→Eg}所有的属性在Fm中均有!按决定因子划分FmF1={Eno→En，Eno→Es}F2={En→Eno},F3={Es→Eg}R1={Eno,En,Es},R2={En,Eno},R3={Es,Eg}R2R1,F1={Eno→EnEs,En→Eno}最后的模式集合是：R1={Eno,En,Es}和R3={Es,Eg}§5.7无损连接分解到4NF的算法算法：R(U，F)把R保持无损连接性地分解为BCNF。假设分解结果为：ρ={R1，R2，…，Rk}。其中，R1，R2，…，Rk∈BCNF

。若对于ρ的任意一个关系模式Ri，存在：Ri

4NF，则Ri中必存在不是码的非平凡的值依赖X→→Y，于是，对Ri进行分解，使之成为：Ri′=(X，Y)和Ri″=(X，Z)§6.数据库设计的讨论关系模式R可以用以下几种方式提出：通过E-R模型转化一个应用中所有属性构成的一个单独关系(泛关系的设计)一些特殊关系设计的结果E-R模型和规范化精心设计的E-R模型不需要规范化E.g.员工实体集有属性：部门号，和部门地址，FD部门号

部门地址.好的设计会将部门作为一个实体集在关系模式中，非键属性间的函数依赖虽然允许，但非常少。性能与规范化之间的平衡问题降低规范化标准，允许一定量的数据冗余采用物化视图的方法其他设计问题设计中，有一些不能用规范化进行描述一个数据库存储不同年份公司的收入。可以设计以下三种关系模式：Earning(companyid,year,amount)Earning2000,earning2001,earning2002…Company-year(companyid,earning2000,earning2001,earning2002…)以上模式均是BCNF,如何确定好坏？从存储和查询性能上考虑

熟练掌握：函数依赖概念；范式的概念，多值依赖与4NF；函数依赖集闭包概念；函数依赖Armstrong公理系统和推理规则；属性集A关于函数依赖集F的闭包计算；键码的求解，依赖集等价的计算。模式分解的概念，关系投影的无损连接性判断，依赖投影的计算，保持函数依赖分解的概念及判断；具有无损连接性分解到BCNF的算法。保持函数依赖分解到3NF的算法。理解：数据冗余及其影响问题。三、设有关系模式R(U,F)。其中，U={A,B,C,D，E},F={D→E,E→A,BD→C},且已知R的键码是(B,D)。请设计R的一个子模式，它把R无损连接性地分解到BCNF。（写出计算过程）。一、设有关系模式R(U,F)。其中，U={A,B,C,D},F={AB→C,C→D,D→A},求R的所有键码。二、已知两个关系模式R1({A,B,C,E},{A→B,C→E})和R2({A,C,D},{(A,C)→D})。问：在函数依赖范围内，R1和R2分别是第几范式的？四、设有关系模式R(U,F)。其中，U={A,B,C,D，E},F={A→B,B→A,B→C,A→C,C→A,D→E},请设计R的一个子模式ρ，它把R保持函数依赖地分解到3NF（写出计算过程）。1.P47习题3.2.1，3.2.2，3.2.42.P52习题3.3.53.P58习题3.4.54.P70习题3.7.1，3.7.2，3.7.3思考题EndofChapter4第5章:SQLSQL概述查询语句的基本结构BasicStructure数据定义语句数据更新语句SQL:structuredquerylanguage,结构化查询语言§1SQL概述1974年由Boyce和Chamberlin提出SQL。基于关系代数，且做了一些修改。1975-1979IBM在SystemR上实现了SQL语言。1979：Oracle发布了商业版SQL1981-84：出现了其他商业版本，分别来自IBM(DB2),DataGeneral(DG/SQL),RelationalTechnology(INGRES)；1989年，ANSI公布SQL-89。增加了引用完整性(referentialintegrity)；1992年，ANSI公布SQL-92。被数据库管理系统（DBMS）生产商广泛接受；

1987年国际标准化组织（InternationalStandardsOrganization，即ISO）也通过了这一标准。第一个SQL标准是1986年10月由美国国家标准局（AmericanNationalStandardInstitute，简称ANSI）公布，称SQL-86。1997+：成为动态网站(Dynamicwebcontent)的后台支持；SQL/99：Corelevel跟其他8种相应的level，包括递归查询，程序跟流程控制，基本的对象object支持包括oidsSQL/2003：包含了XML相关内容,自动生成列值(columnvalues)；2005-09-30："Dataisthenextgenerationinside.SQListhenewHTML"!TimO'eilly提出了Web2.0理念，称数据将是核心，SQL将成为"新的HTML"；SQL/2006：定义了SQL与XML(包含XQuery)的关联应用；2006：Sun公司将以SQL基础的数据库管理系统嵌入JavaV65.语言简洁，语法简单，易学易用。4.一种语法结构，两种使用方式：语言既是自含式语言，又是嵌入式语言。3.面向集合的操作方法。SQL特点:1.综合统一：集DDL、DML和DCL的功能于一体，语言风格统一。2.高度非过程化。SchemaUsedinExamples§2查询语句的基本结构

(BasicStructure)一个典型的SQL查询具有如下形式：

select

A1,A2,...,An

fromr1,r2,...,rm

where

P1[GroupbyAi[havingP2]][OrderbyAj

ASC|DESC,…..]AisrepresentattributesrisrepresentrelationsP1，P2arepredicate（条件）Select…From…Where等同于下面的关系代数表达式：

A1,A2,...,An(

P(r1xr2x...xrm))SQL查询的结果是包（Bag）.§2.1Select子句(TheselectClause)

select子句后列出需要查询的属性correspondstotheprojectionoperationoftherelationalalgebraE.g.从

loan

中查询银行的名称：

selectbranch-name

fromloan对应的关系代数表达式：

branch-name(loan)TheselectClause(Cont.)Select允许查询结果中出现重复元组.要删除重复元组，可在select后插入关键字：distinct前面的例子，消除重复元组：

selectdistinct

branch-name

fromloan同时SQL用关键字all显式指明不消除重复元组

selectall

branch-name

fromloanTheselectClause(Cont.)Select后用“*”代表所有的属性

select*fromloanSelect子句还可以含有带“+,–,

,/”的算术表达式,运算对象可以是常数或属性.Thequery:

selectloan-number,branch-name,amount

100

fromloan§2.2Where子句(ThewhereClause)Where子句带出的是检索条件correspondstotheselectionpredicateoftherelationalalgebra.

E.g.查找所有在Perryridge支行贷款，且贷款额超过$1200的贷款号.selectloan-number

fromloan

wherebranch-name=‘Perryridge’

and

amount>1200ThewhereClause(Cont.)SQL提供

“between…and”comparisonoperatorE.g.查找贷款额在$90,000and$100,000之间的贷款号：

selectloan-number

fromloan

whereamountbetween90000and100000§2.3From子句(ThefromClause)From后面引出查询所涉及的数据源correspondstotheCartesianproductoperationoftherelationalalgebra.E.g.查询

borrowerxloan的所有信息。

select*

fromborrower,loan要表达两个表的自然连接：比如要查询贷款人及其的所贷款项的所有信息。selectcustomer-name,borrower.loan-number,amountfromborrower,loan

where

borrower.loan-number=loan.loan-number查询在Perryridge支行贷款的客户姓名，贷款编号及贷款额.selectcustomer-name,borrower.loan-number,amount

from

borrower,loan

where

borrower.loan-number=loan.loan-numberandbranch-name=‘Perryridge’§2.4改名运算TheRenameOperationSQL允许对关系和属性改名:

old-nameasnew-nameE.g.查询所有贷过款的客户姓名，贷款编号及贷款额;并将loan-number改名为loan-id.select

customer-name,borrower.loan-numberas

loan-id,amount

from

borrower,loan

where

borrower.loan-number=loan.loan-numberselectdistinctT.branch-name

from

branchasT,branchasS

where

T.assets>S.assetsandS.branch-city=‘Brooklyn’

E.g.查找资产比位于Brooklyn的某一家支行高的支行名。select

customer-name,T.loan-number,S.amount

from

borroweras

T,loanas

S

whereT.loan-number=S.loan-numberbranch§2.5字符串运算StringOperationsSQL提供字符串匹配运算符like.并使用两种字符描述模式：%:匹配任意长度的子串._:匹配长度为1的任意字符.E.g.查询所住街道名中包含“Main”子串的客户的姓名.

selectcustomer-name

from

customer

wherecustomer-street

like‘%Main%’SQL中可用转义字符把%或_变成普通字符，如：Matchthename“Main%” like‘Main\%’escape‘\’SQL支持多种字符串连接运算串接concatenation(using“||”)

转化大小写convertingfromuppertolowercase(andviceversa)获取字符串的长度,抽取子字符串.§2.6排列元组

OrderingtheDisplayofTuples用Orderby子句排列查询结果按字母顺序列出在Perryridge支行有贷款的客户的名字：

selectdistinctcustomer-name

from

borrower,loan

where

borrowerloan-number-loan.loan-numberandbranch-name=‘Perryridge’

orderby

customer-name§2.7集合运算(SetOperations)union,intersect,andexcept

分别对应关系代数中的

E.g.查找在银行中有存款，贷款或二者均有的客户名称。(select

customer-namefromdepositor)

union

(select

customer-namefromborrower)SetOperat