分布式數(shù)據(jù)庫(kù)設(shè)計(jì)(共82張PPT)

分布式數(shù)據(jù)庫(kù)設(shè)計(jì)A

FRAMEWORK

FOR

DISTRIBUTEDDATABASE

DESIGN

(概述)THE

DESIGN

OF

DATABASEFRAGMENTATION

(分片設(shè)計(jì))THE

ALLOCATION

OF

FRAGMENTS

(分配設(shè)計(jì))University

of

Shanghai

for

Science

and

TechnologyDistributed

DBMSPage

2.1Level

of

sharing

共享維

不共享，數(shù)據(jù)共享，數(shù)據(jù)+程序共享Access

pattern

behavior訪問(wèn)模式維

靜態(tài)模式，動(dòng)態(tài)

模式(分布式數(shù)據(jù)庫(kù)設(shè)計(jì)與查詢處理)Level

of

knowledge

訪問(wèn)模式知識(shí)維用戶完全已知或部

分已知訪問(wèn)模式分布式系統(tǒng)設(shè)計(jì)的三維Distributed

DBMS

University

of

Shanghai

for

Science

and

Technology

Page

2.2存取模式動(dòng)態(tài)靜態(tài)部分信息數(shù)據(jù)知識(shí)級(jí)別數(shù)據(jù)+程序完整信息共享Dimensions

of

the

ProblemUniversity

of

Shanghai

for

Science

and

TechnologyDistributed

DBMSPage

2.3集中式數(shù)據(jù)庫(kù)設(shè)計(jì)1.

Designing

the

"conceptual

schema"which

describes

the

integrated

database2.

Designing

the

"physical

database,"i.e.,

mapping

the

conceptual

schema

to

storage

areas

and

determining

appropriate

accessmethods.University

of

Shanghai

for

Science

and

TechnologyDistributed

DBMSPage

2.4分布式數(shù)據(jù)庫(kù)設(shè)計(jì)的特殊要求+3.Designing

the

fragmentation.+4.

Designing

the

allocation

of

fragments,i.e.mapped

to

physical

images;

also

the

replication

of

fragments

is

determined.University

of

Shanghai

for

Science

and

TechnologyDistributed

DBMSPage

2.5關(guān)于分片和分配的幾點(diǎn)注意Fragmentation

design

been

partially

analyzed

in

centralized

systemswith

multiple

storage

devices.The

allocation

problem

has

been

studied

as

the

"file

allocation

problem."The

distinction

between

two

problems

is

conceptually

relevantone

deals

with

the

"logical

criteria"

which

motivate

thefragmentation

of

a

global

relationone

deals

with

the

"physical"

placement

of

data

at

the

various

sites.這兩個(gè)問(wèn)題通常是相互關(guān)聯(lián)的，不可能獨(dú)立地解決它們而

能確定最優(yōu)的fragmentaion和allocationUniversity

of

Shanghai

for

Science

and

TechnologyDistributed

DBMSPage

2.6關(guān)于APPLICATION考慮因素：分布式數(shù)據(jù)庫(kù)設(shè)計(jì)包括：分布式數(shù)據(jù)庫(kù)設(shè)計(jì)和相應(yīng)的分布式應(yīng)用設(shè)計(jì)1.

The

site

from

which

the

application

is

issued

(site

of

origin

of

theapplication).2.

The

frequency

of

activation

of

the

application

(i.e.,在單位時(shí)間內(nèi)被激活

的次數(shù));

applications

which

can

be

issued

at

multiple

sites,

we

need

to

know

the

frequency

ofactivation

of

each

application

at

each

site.3.

The

number,

type,

and

the

statistical

distribution

of

accesses

made

byeach

application

to

each

required

data

"object."University

of

Shanghai

for

Science

and

TechnologyDistributed

DBMSPage

2.7設(shè)計(jì)目標(biāo)

(Objectives)Processing

locality數(shù)據(jù)處理的本地性Availability

and

reliability

of

distributed

data

分

布式數(shù)據(jù)的有效性和可靠性冗余控制Workload

distribution

工作負(fù)荷的合理分布Storage

costs

and

availability存儲(chǔ)能力和費(fèi)用Distributed

DBMS

University

of

Shanghai

for

Science

and

Technology

Page

2.8Processing

localityMaximizeprocessing

locality

corresponds

to

the

simple

principle

ofplacing

data

as

close

as

possible

to

the

applications

which

usethem.Maximizing

processing

locality

(minimizing

remote

references)

canbe

done

by

adding

the

number

of

local

and

remote

referencescorresponding

to

each

candidate

fragmentation

and

fragment,

allocation,

and

selecting

the

best

solution

among

them.The

advantage

of

complete

locality

is

not

only

the

reduction

of

remoteaccesses,

but

also

the

increased

simplicity

in

controlling

the

executionof

theapplication.Distributed

DBMS

University

of

Shanghai

for

Science

and

Technology

Page

2.9Availability

and

reliability

of

distributed

dataA

high

degree

of

availability

for

read-only

applications

isachieved

by

storing

multiple

copies

of

the

same

information;the

system

must

be

able

to

switch

to

an

alternative

copy

when

the

one

that

should

be

accessed

under

normal

conditions

is

not

available.Reliability

is

also

achieved

by

storing

multiple

copies

of

the

same

information

-

possible

to

recover

from

crashes

orfrom

the

physical

destruction

of

one

of

the

copies

by

using

the

other

still

available

copies.Distributed

DBMS

University

of

Shanghai

for

Science

and

Technology

Page

2.10Workload

distributionAn

important

feature

of

distributed

computersystems.To

take

advantage

of

the

different

powers

or

utilizations

of

computers

at

each

site,Maximize

the

degree

of

parallelism

of

execution

of

applications.workload

distribution

might

negatively

affectprocessing

locality

-

to

consider

the

trade-offDistributed

DBMS

University

of

Shanghai

for

Science

and

Technology

Page

2.11Storage

costs

and

availabilityShould

reflect

the

cost

and

availability

of

storage

at

the

different

sites.

It

is

possible

to

have

specialized

sites

in

the

network

for

data

storage,

orconversely

to

have

sites

which

do

not

support

mass

storage

at

all.通常存儲(chǔ)的費(fèi)用并不是非常重要(Compared

to

CPU,I/O,

Transmission

of

network).Distributed

DBMS

University

of

Shanghai

for

Science

and

Technology

Page

2.12設(shè)計(jì)方法Top-Down

Approach自頂向下Bottom-Up

Approach自底向上Distributed

DBMS

University

of

Shanghai

for

Science

and

Technology

Page

2.13Top-down

approach已

有DB..如何分割數(shù)據(jù)及如何分配這些數(shù)據(jù)到不同站點(diǎn)過(guò)程start

by

designing

the

global

schemadesigning

the

fragmentation

of

the

databasethen

by

allocating

the

fragments

to

the

sites,

creating

the

physicalimagesThe

approach

is

completed

by

performing,

at

each

site,

the

"physical

design"

of

the

data

which

are

allocated

to

it.Distributed

DBMS

University

of

Shanghai

for

Science

and

Technology

Page

2.14AccessInformationDistributionDesignObjectivesUser

InputView

IntegrationTop-Down

DesignRequirements

AnalysisConceptual

DesignPhysical

DesignView

DesignUser

InputLCS'sLIS'sGCSES's特點(diǎn)能先看到雛形問(wèn)題：

When

the

distributed

database

is

developed

as

the

aggregation

ofexisting

databases,

it

is

not

easy

to

follow

the

top-down

approach.

The

global

schema

is

often

produced

as

a

compromise

between

existing

data

descriptions.Distributed

DBMSUniversity

of

Shanghai

for

Science

and

Technology

Page

2.16Bottom-up

approachExisting

databases

are

aggregated(還可能是異構(gòu)heterogeneous

或完全自治autonomous),

無(wú)設(shè)計(jì)問(wèn)題(信息集成)!Based

on

the

integration

of

existing

schemata

into

a

single,

global

schema.By

integration,

the

merging

of

common

datadefinitions

and

the

resolution

of

conflicts

among

different

representations

given

to

the

same

data.University

of

Shanghai

for

Science

and

TechnologyDistributed

DBMSPage

2.17bottom-up

approachHorizontal

fragments

of

a

same

global

relation

must

have

thesame

relation

schema

-

easily

enforced

in

a

top-downdesign,

while

it

is

difficult

to

"discover"

it.

The

integrationprocess

should

attempt

to

modify

the

definitions

of

localrelations,

so

that

they

can

be

regarded

as

horizontal

fragments

of

a

common,

global

relation.Distributed

DBMS

University

of

Shanghai

for

Science

and

Technology

Page

2.18The

selection

of

a

common

database

modelfor

describing

the

global

schema

of

thedatabase.The

translation

of

each

local

schema

into

thecommon

data

model.The

integration

of

the

local

schemata

into

acommon

global

schema.bottom-up

design

requires(異構(gòu)情況下)Distributed

DBMS

University

of

Shanghai

for

Science

and

Technology

Page

2.19DDB

設(shè)計(jì)的兩個(gè)問(wèn)題FragmentaionHorizontal

FragmentationVertical

fragmentationAllocation通常分片設(shè)計(jì)和分配設(shè)計(jì)需要統(tǒng)籌考

慮Distributed

DBMS

University

of

Shanghai

for

Science

and

Technology

Page

2.20Horizontal

FragmentationPrimary

fragmentation

初級(jí)分片Derived

horizontal

fragmentation導(dǎo)出

分片Distributed

DBMS

University

of

Shanghai

for

Science

and

Technology

Page

2.21水平分片原則若

R?F={F?

,F?

,…,Fn},則完整性

對(duì)于每一個(gè)元組t

∈R,3F?

∈F

使得t

∈F不相交性

對(duì)Vt

∈F,-3Fj

使得

t

∈Fj,

i≠j可重構(gòu)性操作是并し(可以忽略，因?yàn)橥暾跃吞N(yùn)含著)R=U{F?

,F?

,..,

Fn}Distributed

DBMS

University

of

Shanghai

for

Science

and

Technology

Page

2.22水平分片一例例子EMP(E#,

NAME,

DEPT,

JOB,

SAL,TEL,..)DEPT={1,2}

JOB={‘P',

‘-P’}假定，應(yīng)用經(jīng)常查詢的內(nèi)容是屬于部門(mén)1且是程序員的職員。

(80/20原則)則可能有的水平分片限定

(Qualification)P={

DEPT=1}P={DEPT=1,JOB=‘P’}P={DEPT=1,JOB=‘P’,SAL>500}Distributed

DBMS

University

of

Shanghai

for

Science

and

Technology

Page

2.23"手工"檢查!e.g.,

F1=Oloc='Sa’E;F?

=Oloc=‘Sb'E生成具有滿足分段原則的predicate謂詞Distributed

DBMS

University

of

Shanghai

for

Science

and

Technology

Page

2.24如何保證分片原則謂詞：用來(lái)執(zhí)行分片選擇操作的條件1.A

simple

predicate

簡(jiǎn)單謂詞：Attribute

=

value

eg.:

DEPT=12.A

minterm

predicate

(

小項(xiàng)謂詞)

y:

給定簡(jiǎn)單謂詞集P={p?,p?

…pn},y=△piepP?*

也既是P?*AP?*A..APn*where(p*=p;or

p?*=NOT

p;)and

y≠false3.A

fragment

is

the

set

of

all

tuples

for

which

a

minterm

predicate

holds.Distributed

DBMS

University

of

Shanghai

for

Science

and

Technology

Page

2.25一些定義謂詞生成過(guò)程找到常用的AP查詢的simple

predicate

(A,θ

Value)

諸如：A<10,A>5,Loc

=Sa,Loc

=Sb生

成

"

小

項(xiàng)

"

謂

詞消除可能出現(xiàn)的無(wú)用謂詞Distributed

DBMS

University

of

Shanghai

for

Science

and

Technology

Page

2.26Global

relation

EMP(EMPNUM,

NAME,

SAL,

TAX,

MGRNUM,

DEPTNUM)Assume:

some

important

APs

require

information

about

employeeswho

are

members

of

department;

other

important

APs

which

require

onlythe

data

of

employees

who

areprogrammers;

these

last

APs

can

be

issued

at

any

site,

and

reference

all

programmers

with

the

same

probability.Assume:

that

there

are

only

two

departments,

1

and

2;

thus,DEPT=1→DEPT≠

2,and

vice

versa.Two

simple

predicates

are

DEPT=1

and

JOB="P"(programmer).

The

minterm

predicates

for

these

two

predicates

areDEPT=1

AND

JOB="P"DEPT=1

AND

JOB≠"P"DEPT≠1

AND

JOB="P"DEPT≠1

AND

JOB

≠"P"Distributed

DBMS

University

of

Shanghai

for

Science

and

Technology

Page

2.27ExampleAll

the

above

simple

predicates

are

relevante.g.

SAL>50

is

not

a

relevant

predicate;Distributed

DBMS

University

of

Shanghai

for

Science

and

Technology

Page

2.28討論LetP={pi,p?,...,pn}

be

a

set

ofsimple

predicates.為了正確有效進(jìn)行分片，則P必須是completeand

minimal1.P

of

predicates

is

complete

if

any

two

tuplesbelonging

to

the

same

fragment

are

referencedwith

the

same

probability

by

any

application.2.P

is

minimal

if

all

its

predicates

are

relevant.Distributed

DBMS

University

of

Shanghai

for

Science

and

Technology

Page

2.29complete

and

minimalP?={DEPT

=1}is

not

complete

-the

applicationsreference

tuples

of

programmers

with

a

greaterprobability

within

each

fragment

produced

by

P?

.P?={DEPT=1,JOB="P"}is

complete

and

minimal.P?={DEPT=1,JOB="P",SAL>50}iscomplete

butnot

minimal,

since

SAL>50

is

not

relevant.Distributed

DBMS

University

of

Shanghai

for

Science

and

Technology

Page

2.30ExampleFragmentation

MethodBasis

Consider

a

predicate

p,

which

partitions

the

tuples

of

R

into

two

parts

which

are

referenced

differently

by

at

leastone

application.

Let

P

={p?}MethodConsider

a

new

simple

predicate

p;

which

partitions

at

least

onefragment

of

P

into

two

parts

which

are

referenced

in

a

different

way

by

at

least

one

application.Set

P—Pup;.

Eliminate

nonrelevant

predicates

from

P.Repeat

this

step

until

the

set

of

the

minterm

fragments

of

P

iscomplete.Distributed

DBMS

University

of

Shanghai

for

Science

and

Technology

Page

2.31Consider:

SAL>50:

if

programmers

have

average

salary

greater

than

50,

itdetermines

two

sets

of

employees

who

are

referenced

differently

by

theapplications.P1={SAL>50}Consider:

DEPT

=1;

thispredicate

is

relevant

and

is

added

to

the

previous

one,

P2={

SAL>50,DEPT=1}.Consider:

JOB="P".

The

predicate

is

relevant,set

P3={SAL>50,DEPT=1,JOB="P"}.then

SAL>

50

is

not

relevant

in

P3,

thus,

the

final

set

P4={DEPT=1,JOB=

"P"},

which

is

complete

and

minimal.Distributed

DBMS

University

of

Shanghai

for

Science

and

Technology

Page

2.32ExampleA

"reasonable"

way1.Concentrating

on

a

few

importantapplications2.Not

distinguishing

fragments

whosefeatures

are

very

similarDistributed

DBMS

University

of

Shanghai

for

Science

and

Technology

Page

2.331.Administrative

applications,

issued

only

at

sites

1

and

3;administrative

applications

about

departments

in

the

northernarea

are

issued

at

site

1;

those

about

departments

in

the

southern

area

are

issued

at

site

3.2.Applications

about

work

conducted

at

each

department;

theycan

be

issued

at

any

department,

but

they

reference

tuples

of

the

departments

which

are

closer

to

their

site

of

origin

with

higher

probability

than

the

tuples

of

other

departments.DEPT

(DEPTNUM,NAME,AREA,MGRNUM)

importantapplications:Distributed

DBMS

University

of

Shanghai

for

Science

and

Technology

Page

2.34P1:DEPTNUM<10P2:10<DEPTNUM<20P3:DEPTNUM

>20P4:AREA

="North"P5:AREA

="South"Distributed

DBMS

University

of

Shanghai

for

Science

and

Technology

Page

2.35Set

of

predicates:Y1:DEPTNUM<10Y2:

DEPTNUM<10Y3:10<DEPTNUM<20Y4:10<DEPTNUM<20Y5:

DEPTNUM>10Y6:

DEPTNUM>10AREA="North"AREA="South“AREA="North"

AREA="South"AREA

="North"AREA="South"andandandandandandDistributed

DBMS

University

of

Shanghai

for

Science

and

Technology

Page

2.36可能的謂詞限定Reduce,

eg.AREA="North"implies

that

DEPNUM>20y1:DEPTNUM≤10y2:(10<DEPTNUM≤20)AND

(AREA

="North")y3:(10<DEPTNUM≤20)AND

(AREA

=

"South")y4:DEPTNUM>20Distributed

DBMS

University

of

Shanghai

for

Science

and

Technology

Page

2.37Derived

Horizontal

Fragmentation導(dǎo)出分片DHF:

從另一個(gè)關(guān)系的屬性性質(zhì)或水平分片

推導(dǎo)出來(lái)采

用DHF

可以使分片之間的join操作更加容易Distributed

DBMS

University

of

Shanghai

for

Science

and

Technology

Page

2.38DHF

分片exampleeg:SC(S#,C#,GRADE)S(S#,SNAME.

AGE,

SEX)分段設(shè)計(jì)Define

fragment

SC1

asSelect

SC.S#,C#,GRADE

From

SC,SWhere

SC.S#=S.S#

and

SEX=‘M'Define

fragment

SC2

asSelect

SC.S#,C#,GRADE

From

SC,SWhere

SC.S#=S.S#

and

SEX=‘F'Distributed

DBMS

University

of

Shanghai

for

Science

and

Technology

Page

2.39distributed

joinjoin

graphsTotalSimplepartitioned分布式數(shù)據(jù)庫(kù)中的join

連接操作Distributed

DBMS

University

of

Shanghai

for

Science

and

Technology

Page

2.40圓圈：數(shù)據(jù)分片無(wú)向邊：兩個(gè)分片之間有相同

屬性值的元組存在Distributed

DBMS

University

of

Shanghai

for

Science

and

Technology

Page

2.41連接圖定義R

SJoin

graphA

join

graph

is

total

when

it

contains

all

possible

edgesbetween

fragments

of

R

and

S;完全連接圖定義Distributed

DBMS

University

of

Shanghai

for

Science

and

Technology

Page

2.42R

STotal

Join

graphA

reduced

join

graph

is

partitioned

if

the

graph

is

composedof

two

or

moresubgraphs

without

edges

between

themDistributed

DBMS

University

of

Shanghai

for

Science

and

Technology

Page

2.43部分連接圖定義Partitioned

Join

graphR

SA

reduced

join

graph

R

Sis

simple

if

it

ispartitioned

and

eachsubgraph

has

justone

edgeDistributed

DBMS

University

of

Shanghai

for

Science

and

Technology

Page

2.44簡(jiǎn)單連接圖定義Simple

Join

graphSUPPLY

(SNUM,PNUM,

DEPTNUM,

QUAN)

SUPPLY

is

always

used

together

with

another

relationSome

applications

require

information

about

supplies

of

given

suppliers-join

SUPPLY

and

SUPPLIER

on

the

SNUM

attribute.

The

other

applications

require

information

about

supplies

at

a

given

department-join

SUPPLY

and

DEPT

on

the

DEPTNUMattribute.Distributed

DBMS

University

of

Shanghai

for

Science

and

Technology

Page

2.45General

example

(continued)DEPT

is

horizontally

fragmented

according

to

values

taken

by

the

attribute

DEPTNUMSUPPLIER

is

horizontally

fragmented

according

to

values

taken

by

the

attribute

SNUM.There

are

two

possible

derived

fragmentationsSUPPLYone

through

the

semi-join

with

SUPPLIER

on

SNUMone

through

the

semi-join

with

DEPT

on

DEPTNUMboth

of

them

are

correct.The

selection

between

these

alternatives

should

take

intoaccount

which

one

of

the

two

corresponding

joins

is

more

used

by

applications.Distributed

DBMS

University

of

Shanghai

for

Science

and

Technology

Page

2.46Vertical

FragmentationVertical

FragmentationVertical

Clusteringobjective:將某個(gè)AP

頻繁使用的屬性聚

集在一起，當(dāng)有多個(gè)APs

有時(shí)候需要權(quán)

衡利弊。Distributed

DBMS

University

of

Shanghai

for

Science

and

Technology

Page

2.47Vertical

Fragmentation為一全局關(guān)系R

進(jìn)行分片是不容易的，因?yàn)殡S著R

的

屬性數(shù)目增加，可能的分片數(shù)目也大幅度增加

(the

number

of

possible

clusters

is

even

larger.)兩種啟發(fā)式方法(heuristic

approaches)The

split

approach

in

which

global

relations

are

progressively

splitinto

fragments分裂法The

grouping

approach

in

which

attributes

are

progressively

aggregated

to

constitute

fragments成組法Distributed

DBMS

University

of

Shanghai

for

Science

and

Technology

Page

2.48EMP(EMPNUM,NAME,

SAL,TAX,MGRNUM,DEPTNUM)APP1

、Administrative

applications,

concentrated

at

site

3,

requiring

NAME,

SAL,

and

TAX

of

employees.APP2

、Applications

about

work

conducted

at

each

department,requiring

NAME,

MGRNUM,

and

DEPTNUM

of

employees;

these

applications

are

issued

at

all

sites,

and

reference

tuples

of

employees

in

the

same

group

of

departments

with

80

percent

probability.Distributed

DBMS

University

of

Shanghai

for

Science

and

Technology

Page

2.49General

example

(continued)EMPI(EMPNUM,NAME,TAX,

SAL)EMP2(EMPNUM,

NAME,

MGRNUM,DEPTNUM)Distributed

DBMS

University

of

Shanghai

for

Science

and

Technology

Page

2.50結(jié)果the

simplest

ways:1.

Applying

horizontal

fragmentation

to

vertical

fragments2.Applying

vertical

fragmentation

to

horizontal

fragmentsDistributed

DBMS

University

of

Shanghai

for

Science

and

Technology

Page

2.51Mixed

Fragmentationnonredundant

allocation(

easier)The

simplest

method

is

a

"best-fit"

(最佳適應(yīng)

)

approach;

a

measure

is

associated

with

eachpossible

allocation,

and

the

site

with

the

best

measure

is

selected.redundant

allocationReplication

introduces

further

complexity,例如復(fù)

制程度，如何檢索和更新等Distributed

DBMS

University

of

Shanghai

for

Science

and

Technology

Page

2.52THE

ALLOCATION

OF

FRAGMENTS討論在進(jìn)行redundant

allocation冗余分配時(shí)，通常先求nonredundant

allocation非冗余分配的解，在此基礎(chǔ)上再求

redundant

allocation冗余分配的解The

"additional

replication"

method

is

a

typical

heuristicapproach;

with

this

method,

it

is

possible

to

take

intoaccount

that

the

increase

in

the

degree

of

redundancy

isDistributed

DBMS

University

of

Shanghai

for

Science

and

Technology

Page

2.53progressively

less

beneficial.Two

methods

(for

reduntant

allocation):1.

Determine

the

set

of

all

sites

where

the

benefit

of

allocatingone

copy

of

the

fragment

is

higher

than

the

cost,