分布式数据库系统及其应用 第三章

分布式数据库系统及其应用分布式数据库系统设计的目标分布式数据库系统设计的内容分布式数据库的设计方法数据分片设计数据分布设计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分布式数据库设计方法识别相似性模式命名相似性模式结构相似性不同站点上有相似应用,使用各自DB的数据副本,则这两站点之间有某些相似点.识别冲突命名冲突：同物异名（EMP,EMPLOYEE），异物同名域差异定标差异：计量单位不同(天、小时、分钟、秒）结构差异：同一对象有的用实体描述,有的用属性描述.处理操作期间不一致的数据策略4.1分片设计的基本目的4数据分片设计在自顶向下的数据分布设计中，必须要解决的第一个问题是数据的分片设计。在数据分片设计时，是从分配的观点来看，根据具有“相同性质”的元组（在水平分片的情况下）或属性（在垂直分片的情况下）进行分组，使具有“相同性质（例如访问频率相同）”的元组或属性划分在一个组中，每组就构成一个片段分片设计的基本目的是产生一个对全局数据合适的划分方案，将使用这种方案得到的数据片段作为分布式数据库中数据的分配和存储单位时，不但能够减少应用中的操作量，而且对于应用具有最大可能的本地性但是，不是所有的全局数据都必须进行分片，应考虑到有可能一个全局关系根本不需要分片。假若有全局关系R被分片为子关系(片段)集合

R={R1,R2,…,Rn},则R满足完整性若xR,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.2数据分片的基本类型和方法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........站点Sa站点Sb4.3水平分片4数据分片设计

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

R={R1,R2}R1=loc=Sa(E)R2=loc=Sb(E)4.3

水平分片4数据分片设计若R={R1,R2,…,Rn},则完整性对于每一个元组

tR,RiR使得

tRi

不相交性对tRi,Rj

使得

tRj,ij可重构性操作是∪

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

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

基本水平分片导出分片从另一个关系的属性性质或水平分片推导出来例子

SC(S#,C#,GRADE)S(S#,SNAME,AGE,SEX)要求：将SC划分为男生各门课成绩和女生的各门成绩4.3水平分片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.3水平分片4数据分片设计

导出水平分片例子R和S的若干个片段进行连接，根据连接特性分为：完全连接图任两个片段都有连接分区连接图由多个子图组成，每个子图可以是完全连接图简单连接图由多个子图组成，每个子图只有一条边4.3水平分片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数据分片设计

垂直分片设计在满足用户需求的前提下,把设计好的数据片段分配到相应的站点上存储例子:E(#,NM,LOC,SAL) R1=loc=SaE;R2=loc=SbE

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

R1,R2

存放在哪??5数据分布设计分布的概念集中式所有片段在一个站点分割式片段分在几个站点存放复制式多副本混合式多副本、多站点5.1

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

MINCij

+Xj

ui

C’ij

]

+Xi

di

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

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

Bij=kFkjRki-c

kj’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*kj’≠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.1DATAID-D方法概述6DATAID-D方法收集分布信息水平分片谓词每一应用在各站点激活频率概念设计之后进行收集分布信息分布要求和全局逻辑模式作为输入形式为全局数据库模式和逻辑访问表输出为分片模式和分配模式全局逻辑设计之后进行说明：1.设计数据字典；2.全局数据模式；3.全局操作模式；4.简化全局模式；5.逻辑访问表；6.各站点逻辑模式；7.各站点访问表；8.局部逻辑模式（关系或Codasyl）；9.局部物理模式（关系或Codasyl）全局逻辑设计分布设计局部逻辑设计逻辑设计需求分析概念设计分布要求分析局部物理设计187654329要求频率表划分表极化表6.1DATAID-D方法概述6DATAID-D方法分布要求分析阶段频率表：各站点上每一应用激活次数（假设所有应用在所有站点上都能执行）划分表：可用于模式中各实体的潜在水平分片规则极化表：指明由一个站点发出的一给定应用访问一给定片段的频率（定量分析方法）分布要求分析用户分布要求全局数据概念模型全局数据操作模式应用频率表实体划分表应用极化表6.2分布要求分析阶段6DATAID-D方法分布设计阶段分片设计非冗余分配冗余分配局部模式的重新构造分布设计全局数据模式逻辑访问表分布要求站点逻辑模式站点逻辑访问表6.3分布设计阶段6DATAID-D方法数据分布独立性是指用户或用户程序使用分布式数据库如同使用集中式数据库那样，不必关心全局数据的分布情况，包括全局数据的逻辑分片情况、逻辑片段的站点位置分配情况，以及各站点上数据库的数据模型等在分布式数据库中，分布独立性也称为分布透明性（DistributionTransparency）。分布透明性包括三个层次：分片透明性、位置透明性局部数据模型透明性7.1分布式数据库系统中数据的独立性与分布透明性概述7分布式数据库系统中数据的独立性与分布透明性最高级别透明性：分片透明性全局概念模式以下的任何改变，都不会影响到这个应用程序。若DDBMS具有分片透明性，用户只要知道全局关R就可编写程序中等级别透明性：位置透明性若DDBMS提供位置透明性而不提供分片透明性，用户编写这个应用程序就要知道全局关系的分片情况，但不必知道片段的位置分配细节。最低级别透明性：局部数据模型透明性若DDBMS只提供局部数据模型透明性，不提供位置透明性（当然也不具有分片透明性）时，用户编写应用程序不但要知道全局数据的分片细节，还必须知道片段或其副本存放在哪些站点上7.2分布式数据库简单查询与分布透明性7分布式数据库系统中数据的独立性与分布透明性最高级别透明性：分片透明性全局概念模式以下的任何改变，都不会影响到这个应用程序。若DDBMS具有分片透明性，用户只要知道全局关R就可编写程序中等级别透明性：位置透明性若DDBMS提供位置透明性而不提供分片透明性，用户编写这个应用程序就要知道全局关系的分片情况，但不必知道片段的位置分配细节。最低级别透明性：局部数据模型透明性若DDBMS只提供局部数据模型透明性，不提供位置透明性（当然也不具有分片透明性）时，用户编写应用程序不但要知道全局数据的分片细节，还必须知道片段或其副本存放在哪些站点上无分布透明性7.2分布式数据库简单查询与分布透明性7分布式数据库系统中数据的独立性与分布透明性最高级别透明性：分片透明性由于DDBMS提供分片透明性，所以只需对全局关系进行连接操作即可。中等级别透明性：位置透明性由于DDBMS仅提供位置透明性，因此在编程时需要了解全局关系的分片模式最低级别透明性：局部数据模型透明性如果DDBMS不提供分片透明性和位置透明性，在编程时不但需要了解全局关系的分片模式，还需要了解各片段存放的站点无分布透明性7.3分布式数据库复杂查询与分布透明性7分布式数据库系统中数据的独立性与分布透明性级别1：分片透明性应用程序就如同数据库不是分布的那样来执行更新操作，编程人员不必知道被更新的属性是否是分片模式定义中使用的属性级别2：位置透明性应用程序员必须要知道分片情形，并将给出明确的处理级别3：本地映象透明性应用程序员必须明确处理片段的位置。若为更新应用，还必须考虑片段的复制问题7.4分布式数据库更新应用与分布透明性7分布式数据库系统中数据的独立性与分布透明性三个站点站点1：丹佛机场（CO）站点1：纽约机场（NY）站点1：亚特兰大机场（GA）数据库存储内容机场规程班机调度班机可用情况旅客订票情况三个应用订票应用登记应用起飞应用8.1实例研究概述8实例研究：飞机订票系统8.2数据库的全局数据模式8实例研究：飞机订票系统班机订票从到机场登记旅客到达时间机号日期可用座位起飞时间符号城市进入口座位图延期区域安全规则种类座位号检查行李名字电话权力8.3订票应用全局操作模式8实例研究:飞机订票系统实体左下角和右下角的数字表示：示例总数和应用选择的平均示例数访问数据库中的①起飞与到达机场、②起飞与到达时间和③班机日期，以k表示这些关键词确定班机后，建立旅客的一个新的示例及联系“订票”的一个示例，把用户的信息（名字、电话写入数据库O表示输出，w表示写入种类[w]电话[w]240机场320000班机日期[k]起飞时间[k]符号[k]从可用座位[o、w]到到达时间[k]名字[w]1100000旅客订票8.4登记应用全局操作模式8实例研究:飞机订票系统1100000旅客120000班机机号[k]日期[k]座位图[o、w]座位号[w]检查行李[w]订票登记种类[o]名字[k]根据数据库中的①旅客名字，②班机号，③班机日期，查明有关旅客和班机的示例，显示“种类”信息。根据“种类”信息和座位图，将一个座位号分配给旅客，并写入座位图和座位号属性，以及旅客的检查行李号8.5起飞应用全局操作模式8实例研究:飞机订票系统140机场3020000班机3040机场日期[k]符号[k]起飞时间[k,o]机号[o]从到出入口[o]延期[o]城市[o]符号[o]到达时间[k,o]产生即将离开机场的30架班机的信息显示在TV监视器上。根据数据库中的①机场符号，②当前日期，③起飞时间，④到达时间，查明①班机号、②起飞时间、③出入口、④延期、⑤目的地机场符号、⑥目的地城市，显示出来。8.6实体逻辑访问表8实例研究:飞机订票系统属性操作a（订票）b（登记）c（起飞）机号ko日期kkk座位图o/w进入口o延期o可用座位o/w实体访问表：班机8.6实体逻辑访问表8实例研究:飞机订票系统属性操作a（订票）b（登记）c（起飞）符号kk/o城市o权力区域安全规则实体访问表：机场8.6实体逻辑访问表8实例研究:飞机订票系统属性操作a（订票）b（登记）c（起飞）名字wk电话w实体访问表：旅客8.6实体逻辑访问表8实例研究:飞机订票系统属性操作a（订票）b（登记）c（起飞）起飞时间kk/o联系访问表：从8.6实体逻辑访问表8实例研究:飞机订票系统属性操作a（订票）b（登记）c（起飞）到达时间kk/o联系访问表：到8.6实体逻辑访问表8实例研究:飞机订票系统属性操作a（订票）b（登记）c（起飞）种类wo联系访问表：订票8.6实体逻辑访问表8实例研究:飞机订票系统属性操作a（订票）b（登记）c（起飞）座位号w检查行李w联系访问表：登记8.7分布要求分析8实例研究:飞机订票系统站点1：丹佛（CO）站点2：纽约（NY）站点3：亚特兰大（GA）应用a：订票应用b：登记应用c：起飞8.7分布要求分析8实例研究:飞机订票系统将机场的区域属性选作为机场实体的划分准则将旅客电话号码前三位（区域码）作为旅客实体的划分属性谓词选择性表示