復(fù)試-數(shù)據(jù)庫(kù)期末復(fù)習(xí)

2014/6/22Database

Principles&

Programming2ContentsIntroduction

to

E-R

ConceptsFurther

Details

of

E-R

DiagramsAdditional

E-R

ConceptsCase

StudyNormalization:

PreliminariesFunctional

DependenciesLossless

positionsNormal

Forms2014/6/22Database

Principles&

Programming3Review

of

E-R

Model

(1)E-R

ModelEntityAttributeIdentifier,

Descriptor,

Composite

Attribute,Multi-Valued

AttributeRelationshipCard(E,

R)

=

(x,

y)single-valued/multi-valued

participationmandatory/optional

participationOne-to-One,

Many-to-Many,

Many-to-OneExamples

of

E-R

diagrams

(1)Examples

of

E-R

diagrams

(2)2014/6/22Database

Principles&

Programming6Review

of

E-R

Model

(2)Transform

E-R

Model

to

RelationsRule

1:

EntityRule

2:

Multi-valued

AttributeRule

3:

N-N

RelationshipsRule

4.

N-1

RelationshipsRule

5:

1-1

Relationships:

Optional

on

onesideRule

6:

1-1

Relationships:

Mandatory

on

bothsides2014/6/22Database

Principles&

Programming7Rule

3:

N-N

RelationshipsEmployees(eid,

straddr,

city,

……)Projects(prid,

proj_name,

due_date)EmployeesProjectspercentworks_on(eid,

prid,

percent)(1,

N)

works_on

(0,

N)2014/6/22Database

Principles&

Programming8Rule

4.

N-1

RelationshipsInstructors(insid,

lname,

……)Course_sections(secid,

insid,

course,

…)insidsecid2014/6/22Database

Principles&

Programming9Rule

5:

1-1

Relationships:

Optional

on

one

side(ssn,

name,

birthdate)DrivingLicense(DLno,

validdate,

class,

ssn)DrivingLicensehaving(0,1)(1,1)ssn

DLnonamebirthdatevaliddate

class2014/6/22Database

Principles&

Programming10Rule

6:

1-1

Relationships:

Mandatory

on

both

sidesStudent(ssn,

name,

scid,

department,

class)(1,1)StudentCardStudent

having(1,1)ssn

scidnamedepartment

class2014/6/22Database

Principles&

Programming11Review

of

E-R

Model

(3)Cardinality

of

Attributes

(x,

y)eidemp_address(1,1)Employees(0,1)hobbies(1,N)(1,1)staddress(1,1)city(1,1)state(1,1)zipcode2014/6/22Database

Principles&

Programming12Review

of

E-R

Model

(4)Weak

EntitiesOrdersLine_itemsProductshas

itemfor_prod(1,

N)(1,

1)ordnolineno2014/6/22Database

Principles&

Programming13Review

of

E-R

Model

(5)Generalization

HierarchiessConsultantsEmployeesManagersNon_managersvendornoaddressempidexpensenounion_noReview

of Functional

DependencyFunctional

Dependency

(FD,函數(shù)依賴)Def.

of

FDArmstrong’s

Axioms(Armstrong公理)Minimal

Cover

(最小覆蓋)Closure

of

a

Set

of

FDs

(函數(shù)依賴集的閉包)FD

Set

Cover

(函數(shù)依賴集的覆蓋)Equivalenceof

two

sets

of

FDS

(函數(shù)依賴集的等價(jià))Algorithm

6.6.13：最小覆蓋計(jì)算算法Closure

of

a

Set

of

Attributes

(屬性集的閉包)Algorithm

6.6.12：屬性集閉包計(jì)算算法ABA

does

not

functionallydetermine

B.

Somevalues

of

A

correspondto

more

than

one

valueof

B.Figure

6.18 Graphical

Depiction

of

Functional

DependencyABA

functionallydetermines

B.

Eachvalue

of

A

correspondsto

only

one

value

of

B.A

→BA

→B→

B→

AX1

Y1X2

Y2X3

Y3X4

Y4AB（一對(duì)一）B

→

AX1

Y1X2

Y2X3

Y3（一對(duì)多）A

BY4(none)X1

Y1X2

Y2X3

Y3B（多對(duì)多）AReview

of

Armstrong’s

AxiomsArmstrong’s

AxiomsRule

1(自反規(guī)則):

If

YX，then

X→YRule

2(傳遞規(guī)則):If

X→Y

and

Y→Z

，then

X→ZRule

3(增廣規(guī)則):IfX→Y,then

XZ→YZSome

Implications

of

Armstrong’sRule

4(合并規(guī)則):If

X→Y

and

X→Z，then

X→YZRule

5(分解規(guī)則):If

X→YZ，then

X→Y

and

X→ZRule

6(偽傳遞規(guī)則):If

X→Y，and

WY→Z，then

XW→ZRule

7(聚積規(guī)則):If

X→YZ

and

Z→W，then

X→YZWReview

of

Minimal

CoverClosure

of

a

Set

of

FDs(函數(shù)依賴集F的閉包)F+

=

{

X→A

|

F╞

X→A

}FD

Set

Cover(函數(shù)依賴集的覆蓋)F

covers

G

iff G

F+Equivalence

of

two

sets

of

FDS(函數(shù)依賴集的等價(jià))F

covers

G

and

G

covers

FReview

of Functional

DependencyClosure

of

a

Set

of

Attributes

(屬性集的閉包)Algorithm

6.6.12：屬性集閉包計(jì)算算法Minimal

Cover

(最小覆蓋)Algorithm

6.6.13：最小覆蓋計(jì)算算法Review

of

Closure

of

a

Set

of

AttributesDef.

6.6.11:

X+

=

{

A

|

X

→

A

∈

F+

}Falgorithm

6.6.12X+

:=X;repeatoldX+

:=

X+;for

each

functional

dependency

YZ

in

F

doif

Y

X+

then

X+

:=

X+

Z;until

(

oldX+

=

X+

)Algorithm

6.6.13：Minimal

Coverstep

1:

From

the

set

F

of

FDs,

we

createanequivalent

set

H

of

FDs,

with

only

single

attributeson

the

right

side.step

2:

From

the

set

H

of

FDs,

successivelyremove

individual

FDs

that

are

inessential

in

H.step

3:

From

the

set

H

of

FDs,

successivelyreplace

individual

FDs

with

FDs

that

have

asmaller

number

of

attributes

on

the

left-hand

side,as

long

as

the

resu oes

not

change

H+.step

4:

From

the

remaining

set

of

FDs,

gather

allFDs

with

equal

left-hand

sides

and

use

the

unionrule

to

create

an

equivalent

set

of

FDs

M

where

allleft-hand

sides

are

unique.Review

of

NormalizationThe

process

of

normalizationpositions

of

table

THead(T)

=

Head(T1)

Head(T2)

......

Head(Tk)Lossless

position(無損分解)T

T1

T2

...

TkTheorem

6.7.3

&

6.7.4：無損分解的判定定理Lossy

position(有損分解)T

T1

T2

...

TkContent

of

nextDef.6.8.3

FDP

(依賴保持性)Superkey

&

KeyAlgorithm

to

Find

Candidate

KeyPRIME

ATTRIBUTE(主屬性)NON-PRIME

ATTRIBUTE(非主屬性)Normal

Forms:2NF,

3NF,

BCNFAlgorithm

6.8.8246.8 Normal

Formsgorithm

to

Find

Candidate

KeyGiven

a

table

T

with

a

set

F

of

FDs++set

K

:=

Head(T)

;for

each

attribute

A

in

K{compute

(K

–

A)F

;if

(K

–

A)F

contains

all

the

attributes

in

T,

then{set

K

:=

K

–

{

A

}

;}}2014/6/22 Database

Principles

&

ProgrammingBCNF和3NF定義的對(duì)比BCNFfor

any

FD

XA

in

F+

that

lies

in

T

(allattributes

of

X

and

A

in

T),

A

is

a

singleattribute

not

in

X,

then

X

must

be

asuperkey

for

T3NFfor

any

FD

XA

implied

by

F

that

lies

in

T,if

A

is

a

single

non-prime

attribute

not

in

X,then

X

must

be

a

superkey

for

T.3NF和2NF定義的對(duì)比3NFfor

any

XA

implied

by

F

t