第3章 分布式数据库系统的设计

分布式数据库系统及其应用分布式数据库系统设计的目标分布式数据库系统设计的内容分布式数据库的设计方法数据分片设计数据分布设计DATAID-D方法分布式数据库系统中数据的独立性与分布透明性实例研究：飞机订票系统分布式数据库系统设计

第3章1分布式数据库设计目标DDBS设计目标本地性或近地性存储能力和费用尽量减少通信次数和通信量，90/10准则分片和分布方案（本地和远程访问次数）择优控制数据适当冗余冗余增加了可靠性、可用性，提高了效率维护数据一致性开销增加工作负荷分布各站点可以分担整个工作任务本地性降低2分布式数据库设计内容DDBS设计DDB设计应用设计全局模式设计局部数据库设计相关应用需求各个应用的原发站点各个应用在每个站点的激活频率各个应用对要求访问数据对象的访问次数、类型和统计分布分片和分布3.1DDBS设计方法3分布式数据库设计方法DDBS设计方法自顶向下方法（重构法）混合方法自底向上方法（组合法）3分布式数据库设计方法DDBS设计方法3.1

组合法剖析网络功能剖析原有数据库系统解决数据的一致性、完整性和可靠性难度较大

通常是异构或者同构异质DDBS用户1用户2用户n分布式协调管理系统DBMS1DBMS2DBMSm

网络3分布式数据库设计方法DDBS设计方法3.1

重构法根据实现环境和用户需求按照DDBS的设计思想和方法从总体设计做起，包括LDBS,重新建立一个DDBS可有效解决数据一致性、完整性和可靠性问题。

通常是同构异质或同构同质DDBS用户1用户2用户n分布式数据库管理系统

网络3.2自顶向下设计DDB步骤和内容3分布式数据库设计方法需求分析概念设计视图设计分布设计物理设计观察与监视系统需求全局概念模式访问模式外部模式定义局部概念模式物理模式用户输入视图集成用户输入反馈反馈自顶向下设计过程将现有的各种不同的数据库模式集成为全局模式.三个问题选择公用数据库模型来描述数据库的全局模式把每个站点上的本地模式翻译成公用数据模型把各站点上的本地数据模式集成为一公用的全局模式3.3自底向上设计方法3分布式数据库设计方法自底向上设计方法要解决的问题自底向上方法主要问题是构造一个全局模式（超视图）.把各站点上的数据库模式看成是全局模式的一个视图这个问题就可看作是视图综合问题概括分层结构支持视图综合经典方法就是生成三个实体：一个具有共同属性（超类型），两个具有不相交属性（子类型）视图综合次序一次把一个视图和全局模式进行综合，逐步构造起全局视图通常，最好首先综合最大的或最重要的视图，然后跟着综合小的或者不重要的视图3.3自底向上设计方法3分布式数据库设计方法构造全局模式问题和解决方法班机机号日期可用座位出入口座位图延期班机机号日期可用座位机型座位图班机班机1班机2机号日期可用座位座位图出入口延期机型3.3自底向上设计方法3分布式数据库设计方法3.3自底向上设计方法3分布式数据库设计方法识别相似性模式命名相似性模式结构相似性不同Site上有相似应用,使用各自DB的数据副本,则这两Site之间有某些相似点.识别冲突命名冲突：同物异名（EMP,EMPLOYEE），异物同名域差异定标差异：计量单位不同(天、小时、分钟、秒）结构差异：同一对象有的用实体描述,有的用属性描述.处理操作期间不一致的数据策略（5种，p64-65）4.1分片设计的基本目的4数据分片设计在自顶向下的数据分布设计中，必须要解决的第一个问题是数据的分片设计。在数据分片设计时，是从分配的观点来看，根据具有“相同性质”的元组（在水平分片的情况下）或属性（在垂直分片的情况下）进行分组，使具有“相同性质（例如访问频率相同）”的元组或属性划分在一个组中，每组就构成一个片段分片设计的基本目的是产生一个对全局数据合适的划分方案，将使用这种方案得到的数据片段作为分布式数据库中数据的分配和存储单位时，不但能够减少应用中的操作量，而且对于应用具有最大可能的本地性但是，不是所有的全局数据都必须进行分片，应考虑到有可能一个全局关系根本不需要分片。假若有全局关系R被分片为子关系(片段)集合

R={R1,R2,…,Rn},则R满足完整性?x

R,RiR必有

xRi

，i=1,2,…,n可重构性存在函数g使得R=g(R1,R2,…,Rn)即，R=∪Ri(水平分片）,R=∞

Ri

（垂直分片）不相交性Ri

∩

Rj

=空集,i≠j,i,j=1,2,…,n(水平分片)Ri

∩

Rj

=主键属性,i,j=1,2,…,n(垂直分片)4.3数据分片的基本类型和方法4数据分片设计

分片原则

分片方法水平分片

垂直分片职工关系E(e#,name,loc,sal,…)

查询:

Qa:select* Qb:select* fromE fromE whereloc=Sa whereloc=Sb and… and...两个站点:Sa,SbQa

QbSaSb4.3数据分片的基本类型和方法4数据分片设计

举例 e#NMLocSal E578Sa1000SallySb2500TomSa500Joee#NMLocSale#NMLocSal58Sa1000TomSa500Joe7Sb2500Sally........F站点Sa站点Sb4.3数据分片的基本类型和方法4数据分片设计

举例基本水平分片以关系自身的属性性质为基础，执行“选择”操作，将关系分割成若干个不相交的片段。

R={R1,R2}R1=

loc=Sa(E)R2=

loc=Sb(E)4.4

数据的分片设计4数据分片设计

基本水平分片若R={R1,R2,…,Rn},则完整性对于每一个元组

t

R,RiR使得

tRi

不相交性对

tRi,Rj

使得

tRj,ij可重构性操作是∪

(可以忽略,因为完整性就蕴含着)R=

∪{R1,R2,…,Rn}P={p1,p2,…,pn}是一简单谓词集合，为保证分片的正确性，P必须是：完整的：同一分片中的任意两个元组被应用同样概率访问。最小的：集合P中的所有谓词与应用密切相关。具有完整性和最小性不是必要条件,但是对于简化分配问题有好处4.4

数据的分片设计4数据分片设计

基本水平分片例子EMP(E#,NAME,DEPT,JOB,SAL,TEL,…)DEPT={1,2}JOB={‘P’,‘-P’}假定，应用经常查询的内容是属于部门1且是程序员的职员。则可能有的水平分段限定

P={DEPT=1}（不是完整的）

P={DEPT=1,JOB=‘P’}（是完整的、最小的）

P={DEPT=1,JOB=‘P’,SAL>500}（完整的，不是最小的）4.4

数据的分片设计4数据分片设计

基本水平分片如何保证分片原则“手工”检查! e.g.,R1=

loc=‘Sa’E;R2=

loc=‘Sb’E生成具有满足分段原则的限定谓词4.4

数据的分片设计4数据分片设计

基本水平分片设有关系E(e#,name,Loc,sal,A,…),查询使用的简单谓词（Ai

Value）是:A<10,A>5,Loc=Sa,Loc=Sb下一步: -生成“小项”谓词

-消除无用谓词给定简单谓词集Pr={p1,p2,..pn},则“小项”谓词（mintermpredicate）形式:

p1*

p2*…pn*

这里pk*是pk

或是¬pk4.4

数据的分片设计4数据分片设计

谓词生成举例(1)A<10

A>5

Loc=SA

Loc=SB(2)

A<10

A>5

Loc=SA

¬(Loc=SB)(3)

A<10

A>5

¬(Loc=SA)

Loc=SB(4)A<10

A>5

¬(Loc=SA)

¬(Loc=SB)(5)A<10

¬(A>5)

Loc=SA

Loc=SB(6)

A<10

¬(A>5)

Loc=SA

¬(Loc=SB)(7)

A<10

¬(A>5)

¬(Loc=SA)

Loc=SB(8)A<10

¬(A>5)

¬(Loc=SA)

¬(Loc=SB)4.4

数据的分片设计4数据分片设计小项谓词选择(9)¬(A<10)

A>5

Loc=SA

Loc=SB(10)¬(A<10)

A>5

Loc=SA

¬(Loc=SB)(11)¬(A<10)

A>5

¬(Loc=SA)

Loc=SB(12)¬(A<10)

A>5

¬(Loc=SA)

¬(Loc=SB)(13)¬(A<10)

¬(A>5)

Loc=SA

Loc=SB(14)¬(A<10)

¬(A>5)

Loc=SA

¬(Loc=SB)(15)¬(A<10)

¬(A>5)

¬(Loc=SA)

Loc=SB(16)¬(A<10)

¬(A>5)

¬(Loc=SA)

¬(Loc=SB)4.4

数据的分片设计4数据分片设计小项谓词选择R2: 5<A<10

Loc=SA

R3: 5<A<10

Loc=SB

R6: A

5

Loc=SA

R7: A

5

Loc=SB

R10: A

10

Loc=SA

R11: A

10

Loc=SB

分片结果4.4数据的分片设计4数据分片设计注:无用段的消除依赖于应用的语义e.g.:

如果LOC可以是

SA,SB,则最终分段集合应该加上R4: 5<A<10

LocSA

LocSB

R8: A

5

LocSA

LocSB

R12: A

10

LocSA

LocSB4.4

数据的分片设计4数据分片设计小项选择率（mintermselectivity）

对某一给定小项谓词用户查询可能选择到的元组数访问频率（Accessfrequency）用户应用访问数据的频率小项访问频率可以通过用户查询频率获得4.4

数据的分片设计4数据分片设计分片数量信息例子

E(#,NM,LOC,SAL,…)

有查询应用

Qa:select* Qb:select* fromE fromE whereLOC=Sa whereLOC=Sb and… and...4.4

数据的分片设计4数据分片设计如何选择小项谓词举例(1)Pr={}R1={E}(2)Pr={LOC=Sa,LOC=Sb} R2={

loc=SaE,loc=SbE}(3)Pr={LOC=Sa,LOC=Sb,Sal<1000} R3={

loc=Sa

sal<1000E,loc=Sa

sal1000E,

loc=Sb

sal<1000E,loc=Sb

sal1000E}三种选择4数据分片设计4数据分片设计Loc=Sa

sal<1000Loc=Sa

sal

1000Loc=Sb

sal<1000Loc=Sb

sal

1000R1R3R2Qa:Select…loc=Sa...Qb:Select…loc=Sb...R2是好的…(R1,R3不好

)4.4

数据的分片设计4数据分片设计图示Loc=Sa

sal<1000Loc=Sa

sal

1000Loc=Sb

sal<1000Loc=Sb

sal

1000R1Qa:Select…loc=Sa...Qb:Select…loc=Sb...此处元组有较高的选择概率此处元组选择概率较低分段内元组选择概率不等因此R1不好...4.4

数据的分片设计4数据分片设计理由Loc=Sa

sal<1000Loc=Sa

sal

1000Loc=Sb

sal<1000Loc=Sb

sal

1000R2Qa:Select…loc=Sa...Qb:Select…loc=Sb...元组选择概率相等因此R2好...R3不好

...理由4.4

数据的分片设计4数据分片设计导出分片从另一个关系的属性性质或水平分片推导出来例子

SC(S#,C#,GRADE)S(S#,SNAME,AGE,SEX)要求：将SC划分为男生各门课成绩和女生的各门成绩4.4

数据的分片设计4数据分片设计

导出水平分片按S的属性导出

DefinefragmentSC1asSelectSC.S#,C#,GRADEFromSC,SWhereSC.S#=S.S#andSEX=‘M’DefinefragmentSC2asSelectSC.S#,C#,GRADEFromSC,SWhereSC.S#=S.S#andSEX=‘F’按S的水平分片（SF/SM）导出DefinefragmentSC1asSelect*FromSCWhereS#in(SelectSF.SfromSF)DefinefragmentSC2asSelect*FromSCWhereS#in(SelectSM.SfromSM)

4.4

数据的分片设计4数据分片设计

导出水平分片例子通过“投影”操作把一个全局关系的属性分成若干组，基本目标是将使用频繁的属性聚集在一起全局关系R={Ri},i=1,2,…,n如果属性A∈R,必有A∈Ri,i=1,2,…,n,而且Ri∩Rj=Ap,i≠j，Ap为R的码或元组标识符，则称{Ri},i=1,2,…,n}是关系R的一个垂直分片。如果属性A∈R,必有A∈Ri,i=1,2,…,n,而且Ri∩Rj=（Ap,A-p),i≠j，A-p为R的一个或多个非码属性时，称{Ri},i=1,2,…,n}是关系R的一个垂直群集。4.4

数据的分片设计4数据分片设计

垂直分片和垂直群集EMP(E#,NAME,SAL,TEL,MAGNUM,DEPT)假定Key:E#主要应用:Sa站点查询NAME,SAL,TEL;Sb站点查询NAME,MAGNUM,DEPT垂直分片:EMP1(E#,NAME,SAL,TEL)EMP2(E#,MAGNUM,DEPT)垂直群集:EMP1(E#,NAME,SAL,TEL)EMP2(E#,NAME,MAGNUM,DEPT)4.4

数据的分片设计4数据分片设计

垂直分片/垂直群集例子4.4

数据的分片设计4数据分片设计E1EE2

垂直分片例子

例子: E1(#,NM,LOC) E2(#,SAL)E(#,NM,LOC,SAL) E1(#,NM) E2(#,LOC) E3(#,SAL)?4.4

数据的分片设计4数据分片设计

垂直分片设计非键属性A1,A2,…,An应用Q1,Q2,….,Qmfreq(Qi)=Qi

的访问频率4.4

数据的分片设计4数据分片设计

属性的亲和关系7578021A47975400A540974845A3024810050A201455096A1

A5A4A3A2A1R1[K,A1,A2,A3]R2[K,A4,A5]4.4

数据的分片设计4数据分片设计

属性亲和矩阵0787521A497044845A34757900A5482010050A245105096A1

A3A4A5A2A1行列调整寻找分割点4.4数据的分片设计4数据分片设计

属性和矩阵穷举属性亲和矩阵的列排列行与列要同时调整发现好的“分割点”极大化每个分割内的亲合力（affinity）,极小化跨分割的访问4.4数据的分片设计4数据分片设计垂直分片算法水平 基本：

R 根据local属性

导出

根据外键关系垂直

R4.4

数据的分片设计4数据分片设计分片小结混合分段RR1R2R11R12R21R22水平垂直4.4

数据的分片设计4数据分片设计分片小结混合分段的重构R11R12R21R22水平垂直U4.4

数据的分片设计4数据分片设计分片小结在满足用户需求的前提下,把设计好的数据片段分配到相应的站点上存储例子:E(#,NM,LOC,SAL)

R1=

loc=SaE;R2=

loc=SbE

Qa:select…whereloc=Sa... Qb:select…whereloc=Sb…SiteaSiteb

R1,R2

存放在哪??5.1

数据分布概念5数据分布设计分布的概念集中式分割式复制式混合式5.2

数据的分布策略5数据分布设计分配的策略5.3数据片段位置分配的方法5数据分布设计分配方法分配方法非冗余分配设计方法最佳适应法其他方法冗余分配的设计方法所有得益站点法附加复制法应用需求确定非复制问题的解确定一组站点分配副本确定非复制问题的解从最有益处增加副本到附加复制无好处为止什么是段的最好配置/什么是最好的冗余副本数:极小化查询响应时间极大化吞吐量极小化“代价”...约束?有效的存储空间有效的带宽,站点处理能力,…保持90%的响应时间低于X（如0.5秒）...5.4数据片段分配的费用和得益估算5数据的分配设计优化问题

单个片段F站点S1,…Sm

变量X1,…,Xm0如果F不在Sj上存储

1如果F在Sj上存储

Totalcost=ReadCost+WriteCost+ StorageCost

确定Xj的值,1jm,使总代价极小Xj=分配的简化模型读代价

Readcost=[tiMINCij]i: 读申请源站点

ti: 站点Si上的读申请激活次数

Cij:从Si读Sj站点分段F的代价

i=1m分配的简化模型...3ici,3ci,1ci,2ti

FFF.12j写代价

Writecost=

XjuiC’iji:写申请源站点

j:被更新站点

Xj:0ifFnotstoredatSj 1ifFstoredatSjui:站点Si上更新激活次数

C’ij:从站点Si更新Sj分段F的代价i=1j=1mm分配的简化模型....iFFFUpdatesui存储代价

StoreCost=

Xidi

Xi: 0ifFnotstoredatSi

1ifFstoredatSidi:

站点Si存储分段F的代价i=1m分配的简化模型目标函数min

[tiMINCij

+

XjuiC’ij]

+

Xidi

ji=1j=1i=1mmm分配的简化模型即使最简单的公式也是NP-完全问题通常,使用方法尽可能将片段分配在被局部访问位置“最佳适应”方法（非冗余分配）

Bij=

kFkjNki“所有得益站点”方法（冗余分配）

Bij=

kFkjRki-c

k

j’jFkj’Uki

i片段下标j站点下标

k应用下标Fkj应用k在站点j上激活的频率

Rki应用k被激活一次,对片段i读的次数

Uki应用k被激活一次,对片段i写的次数

Nki应用k被激活一次,对片段i读写的总次数分配方法最佳适应法将片断Ri分配到访问Ri次数最多的那个站点上Bij=

kFkj*Nki

所有得益站点法将片断Ri的副本分配到所有得益站点j上Bij=

kFkj*Rki-c*k

j’≠jFkj’*Uki如Bij＞0，则站点j是得益站点，放置Ri的一个副本附加复制法Di表示片断Ri的冗余度（副本个数）,Fi表示Ri在所有站点都复制的得益

水平分片情况假设关系R垂直分片R1和R2,R1分配到s站点,R2分配到t站点.应用组As:自站点s发出,只使用Rs,得益

BAs=FksNki(kAs)应用组Ar:自站点t发出,只使用Rt,得益

BAt=FktNki(kAt)应用组A1:由站点r发出,原先使用Rt或Rs(本地),现在要一次远程，损失

BA1=FkrNki(kA1)应用组A2:由站点r发出,原先使用R(本地),现在要两次远程，损失

BA2=FkrNki(kA2)应用组A3:由不同于站点r,s,t的站点发出,要访问Rt和Rs,损失

BA3=FkjNki(kA3,j≠r,s,t)分配得益

Bist=BAs+BAt-BA1-BA2-BA3垂直分片情况垂直分片情况rs其他站点tRtRRs网络A1A2AsAtA3分布式数据库设计阶段需求分析概念设计分布要求设计全局逻辑设计分布设计局部逻辑设计局部物理设计6.1与集中式数据库的异同6DATAID-D方法收集分布信息水平分片谓词每一应用在各站点激活频率概念设计之后进行收集分布信息分布要求和全局逻辑模式作为输入形式为全局数据库模式和逻辑访问表输出为分片模式和分配模式全局逻辑设计之后进行说明：1.设计数据字典；2.全局数据模式；3.全局操作模式；4.简化全局模式；5.逻辑访问表；6.各站点逻辑模式；7.各站点访问表；8.局部逻辑模式（关系或Codasyl）；9.局部物理模式（关系或Codasyl）全局逻辑设计分布设计局部逻辑设计逻辑设计需求分析概念设计分布要求分析局部物理设计187654329要求频率表划分表极化表6.2设计步骤6DATAID-D方法分布要求分析阶段频率表：各站点上每一应用激活次数（假设所有应用在所有站点上都能执行）划分表：可用于模式中各实体的潜在水平分片规则极化表：指明由一个站点发出的一给定应用访问一给定片段的频率（定量分析方法）分布要求分析用户分布要求全局数据概念模型全局数据操作模式应用频率表实体划分表应用极化表6.3分布要求分析阶段6DATAID-D方法分布设计阶段分片设计非冗余分配冗余分配局部模式的重新构造分布设计全局数据模式逻辑访问表分布要求站点逻辑模式站点逻辑访问表6.4分布设计阶段6DATAID-D方法数据分布独立性是指用户或用户程序使用分布式数据库如同使用集中式数据库那样，不必关心全局数据的分布情况，包括全局数据的逻辑分片情况、逻辑片段的站点位置分配情况，以及各站点上数据库的数据模型等在分布式数据库中，分布独立性也称为分布透明性（DistributionTransparency）。分布透明性包括三个层次：分片透明性、位置透明性局部数据模型透明性7.1分布式数据库系统中数据的独立性与分布透明性概述7分布式数据库系统中数据的独立性与分布透明性最高级别透明性：分片透明性全局概念模式以下的任何改变，都不会影响到这个应用程序。若DDBMS具有分片透明性，用户只要知道全局关R就可编写程序中等级别透明性：位置透明性若DDBMS提供位置透明性而不提供分片透明性，用户编写这个应用程序就要知道全局关系的分片情况，但不必知道片段的位置分配细节。最低级别透明性：局部数据模型透明性若DDBMS只提供局部数据模型透明性，不提供位置透明性（当然也不具有分片透明性）时，用户编写应用程序不但要知道全局数据的分片细节，还必须知道片段或其副本存放在哪些站点上7.2分布式数据库简单查询与分布透明性7分布式数据库系统中数据的独立性与分布透明性最高级别透明性：分片透明性全局概念模式以下的任何改变，都不会影响到这个应用程序。若DDBMS具有分片透明性，用户只要知道全局关R就可编写程序中等级别透明性：位置透明性若DDBMS提供位置透明性而不提供分片透明性，用户编写这个应用程序就要知道全局关系的分片情况，但不必知道片段的位置分配细节。最低级别透明性：局部数据模型透明性若DDBMS只提供局部数据模型透明性，不提供位置透明性（当然也不具有分片透明性）时，用户编写应用程序不但要知道全局数据的分片细节，还必须知道片段或其副本存放在哪些站点上无分布透明性7.2