分布式数据库系统的设计.ppt

徐俊刚（),分布式数据库系统及其应用,2009年2月2009年6月,分布式数据库系统设计概述自顶向下设计分布式数据库DATAID-D方法实例研究：飞机订票系统自底向上设计分布式数据库,分布式数据库系统设计,第2章,分布式数据库设计概述,1,创建方法,组合法,剖析网络功能剖析原有数据库系统解决数据的一致性、完整性和可靠性难度较大 通常是异构或者同构异质DDBS,分布式数据库设计概述,1,重构法,根据实现环境和用户需求按照DDBS的设计思想和方法从总体设计做起，包括LDBS,重新建立一个DDBS可有效解决数据一致性、完整性和可靠性问题。通常是同构异质或同构同质DDBS,DDBS设计,DDB设计,应用设计,全局模式设计,局部数据库设计,相关应用需求,各个应用的原发站点,各个应用在每个站点的激活频率,各个应用对要求访问数据对象的访问次数、类型和统计分布,分片和分布,DDBS设计目标,本地性或近地性,存储能力和费用,尽量减少通信次数和通信量，90/10准则,分片和分布方案（本地和远程访问次数）择优,控制数据适当冗余,冗余增加了可靠性、可用性，提高了效率,维护数据一致性开销增加,工作负荷分布,各站点可以分担整个工作任务,本地性降低,DDBS设计方法,自顶向下方法（重构法）,混合方法,自底向上方法（组合法）,假若有全局关系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=空集,ij,i,j=1,2,n(水平分片)Ri Rj=主键属性,i,j=1,2,n(垂直分片),分片原则,职工关系 E(e#,name,loc,sal,)查询:Qa:select*Qb:select*from E from Ewhere loc=Sa where loc=Sband and.,举例,e#NM Loc Sal E,5,7,8,Sa,1000,Sally,Sb,2500,Tom,Sa,500,Joe,e#NM Loc Sal,e#NM Loc Sal,5,8,Sa,1000,Tom,Sa,500,Joe,7,Sb,2500,Sally,.,.,.,.,F,站点Sa,站点 Sb,举例,基本水平分片 以关系自身的属性性质为基础，执行“选择”操作，将关系分割成若干个不相交的片段。R=R1,R2 R1=loc=Sa(E)R2=loc=Sb(E),基本水平分片,若 R=R1,R2,Rn,则完整性 对于每一个元组 tR,RiR 使得 tRi 不相交性 对tRi,Rj 使得 tRj,i j可重构性 操作是(可以忽略,因为完整性就蕴含着)R=R1,R2,RnP=p1,p2,pn是一简单谓词集合，为保证分片的正确性，P必须是：完整的：同一分片中的任意两个元组被应用同样概率访问。最小的：集合P中的所有谓词与应用密切相关。具有完整性和最小性不是必要条件,但是对于简化分配问题有好处,基本水平分片,例子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,SAL500（完整的，不是最小的）,基本水平分片,如何保证分片原则,“手工”检查!e.g.,R1=loc=Sa E;R2=loc=Sb E生成具有满足分段原则的限定谓词,基本水平分片,设有关系 E(e#,name,Loc,sal,A,),查询使用的简单谓词（Ai Value）是:A5,Loc=Sa,Loc=Sb下一步:-生成“小项”谓词-消除无用谓词给定简单谓词集 Pr=p1,p2,.pn,则“小项”谓词（minterm predicate）形式:p1*p2*pn*这里 pk*是 pk 或是 pk,谓词生成举例,(1)A5 Loc=SA Loc=SB(2)A5 Loc=SA(Loc=SB)(3)A5(Loc=SA)Loc=SB(4)A5(Loc=SA)(Loc=SB)(5)A5)Loc=SA Loc=SB(6)A5)Loc=SA(Loc=SB)(7)A5)(Loc=SA)Loc=SB(8)A5)(Loc=SA)(Loc=SB),小项谓词选择,(9)(A5 Loc=SA Loc=SB(10)(A5 Loc=SA(Loc=SB)(11)(A5(Loc=SA)Loc=SB(12)(A5(Loc=SA)(Loc=SB)(13)(A5)Loc=SA Loc=SB(14)(A5)Loc=SA(Loc=SB)(15)(A5)(Loc=SA)Loc=SB(16)(A5)(Loc=SA)(Loc=SB),小项谓词选择,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,分片结果,注:无用段的消除依赖于应用的语义,e.g.:如果 LOC 可以是 SA,SB,则最终分段集合应该加上R4:5 A 10 Loc SA Loc SB R8:A 5 Loc SA Loc SB R12:A 10 Loc SA Loc SB,小项选择率（minterm selectivity）对某一给定小项谓词用户查询可能选择到的元组数访问频率（Access frequency）用户应用访问数据的频率小项访问频率可以通过用户查询频率获得,分片数量信息,例子 E(#,NM,LOC,SAL,)有查询应用Qa:select*Qb:select*from Efrom E where LOC=Sa where LOC=Sb and and.,如何选择小项谓词举例,(1)Pr=R1=E(2)Pr=LOC=Sa,LOC=Sb R2=loc=Sa E,loc=Sb E(3)Pr=LOC=Sa,LOC=Sb,Sal1000 R3=loc=Sa sal1000 E,loc=Sa sal1000 E,loc=Sb sal1000E,loc=Sb sal1000 E,三种选择,Loc=Sa sal 1000,Loc=Sa sal 1000,Loc=Sb sal 1000,Loc=Sb sal 1000,R1,R3,R2,Qa:Select loc=Sa.,Qb:Select loc=Sb.,图示,Loc=Sa sal 1000,Loc=Sa sal 1000,Loc=Sb sal 1000,Loc=Sb sal 1000,R1,Qa:Select loc=Sa.,Qb:Select loc=Sb.,此处元组有较高的选择概率,此处元组选择概率较低,分段内元组选择概率不等因此 R1 不好.,理由,Loc=Sa sal 1000,Loc=Sa sal 1000,Loc=Sb sal 1000,Loc=Sb sal 1000,R2,Qa:Select loc=Sa.,Qb:Select loc=Sb.,元组选择概率相等,因此 R2好.,R3不好.,理由,导出分片 从另一个关系的属性性质或水平分片推导出来例子 SC(S#,C#,GRADE)S(S#,SNAME,AGE,SEX)要求：将SC划分为男生各门课成绩和女生的各门成绩,导出水平分片,按S的属性导出 Define fragment SC1 as Select SC.S#,C#,GRADE From SC,S Where SC.S#=S.S#and SEX=M Define fragment SC2 as Select SC.S#,C#,GRADE From SC,S Where SC.S#=S.S#and SEX=F按S的水平分片（SF/SM）导出Define fragment SC1 as Select*From SC Where S#in(Select SF.S from SF)Define fragment SC2 as Select*From SC Where S#in(Select SM.S from SM),导出水平分片例子,通过“投影”操作把一个全局关系的属性分成若干组，基本目标是将使用频繁的属性聚集在一起全局关系R=Ri,i=1,2,n如果属性AR,必有ARi,i=1,2,n,而且RiRj=Ap,ij，Ap为R的码或元组标识符，则称Ri,i=1,2,n是关系R的一个垂直分片。如果属性AR,必有ARi,i=1,2,n,而且RiRj=（Ap,A-p),ij，A-p为R的一个或多个非码属性时，称Ri,i=1,2,n是关系R的一个垂直群集。,垂直分片和垂直群集,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),垂直分片/垂直群集例子,E1,E,E2,垂直分片例子,例子:E1(#,NM,LOC)E2(#,SAL)E(#,NM,LOC,SAL)E1(#,NM)E2(#,LOC)E3(#,SAL),?,垂直分片设计,非键属性 A1,A2,An应用 Q1,Q2,.,Qmfreq(Qi)=Qi 的访问频率,属性的亲和关系,R1K,A1,A2,A3 R2K,A4,A5,属性亲和矩阵,行列调整寻找分割点,属性和矩阵,穷举属性亲和矩阵的列排列行与列要同时调整发现好的“分割点”极大化每个分割内的亲合力（affinity）,极小化跨分割的访问,垂直分片算法,水平 基本：R 根据 local属性 导出 根据外键关系垂直R,分片小结,混合分段,R,R1,R2,R11,R12,R21,R22,水平,垂直,分片小结,混合分段的重构,R11,R12,R21,R22,水平,垂直,U,在满足用户需求的前提下,把设计好的数据片段分配到相应的站点上存储例子:E(#,NM,LOC,SAL)R1=loc=Sa E;R2=loc=Sb E Qa:select where loc=Sa.Qb:select where loc=Sb,Site a,Site b,R1,R2 存放在哪?,?,分配方法,非冗余分配设计方法,最佳适应法,其他方法,冗余分配的设计方法,所有得益站点法,附加复制法,应用需求,确定非复制问题的解确定一组站点分配副本,确定非复制问题的解从最有益处增加副本到附加复制无好处为止,什么是段的最好配置/什么是最好的冗余副本数:极小化查询响应时间极大化吞吐量极小化“代价”.约束?有效的存储空间有效的带宽,站点处理能力,保持 90%的响应时间低于 X（如0.5秒）.,单个片段 F 站点 S1,Sm 变量 X1,Xm 0 如果 F 不在 Sj上存储 1 如果 F 在 Sj上存储 Total cost=Read Cost+Write Cost+Storage Cost 确定 Xj 的值,1 j m,使总代价极小,Xj=,读代价,Read cost=ti MIN Cij i:读申请源站点 ti:站点Si上的读申请激活次数 Cij:从 Si读Sj站点分段F的代价,i=1,m,j,写代价,Write cost=Xj ui Cij i:写申请源站点 j:被更新站点 Xj:0 if F not stored at Sj 1 if F stored at Sj ui:站点 Si 上更新激活次数 Cij:从站点 Si 更新 Sj 分段 F 的代价,i=1,j=1,m,m,Updates,ui,存储代价,Store Cost=Xi di Xi:0 if F not stored at Si 1 if F stored at Si di:站点 Si 存储分段 F 的代价,i=1,m,目标函数,min ti MIN Cij+Xj ui Cij+Xi di,j,i=1,j=1,i=1,m,m,m,即使最简单的公式也是 NP-完全问题通常,使用方法尽可能将片段分配在被局部访问位置,“最佳适应”方法（非冗余分配）Bij=k Fkj Nki“所有得益站点”方法（冗余分配）Bij=k Fkj Rki-c k jjFkj 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 jj Fkj*Uki如Bij 0，则站点j是得益站点，放置Ri的一个副本附加复制法Di表示片断Ri的冗余度（副本个数）,Fi表示Ri在所有站点都复制的得益,假设关系R垂直分片R1和R2,R1分配到s站点,R2分配到t站点.应用组As:自站点s发出,只使用Rs,得益 BAs=Fks Nki(k As)应用组Ar:自站点t发出,只使用Rt,得益 BAt=Fkt Nki(k At)应用组A1:由站点r发出,原先使用Rt或Rs(本地),现在要一次远程，损失 BA1=Fkr Nki(k A1)应用组A2:由站点r发出,原先使用R(本地),现在要两次远程，损失 BA2=Fkr Nki(k A2)应用组A3:由不同于站点r,s,t的站点发出,要访问Rt和Rs,损失 BA3=Fkj Nki(k A3,j r,s,t)分配得益 Bist=BAs+BAt-BA1-BA2-BA3,分布式数据库设计阶段需求分析概念设计分布要求设计全局逻辑设计分布设计局部逻辑设计局部物理设计,收集分布信息水平分片谓词每一应用在各站点激活频率概念设计之后进行,收集分布信息分布要求和全局逻辑模式作为输入形式为全局数据库模式和逻辑访问表输出为分片模式和分配模式全局逻辑设计之后进行,说明：1.设计数据字典；2.全局数据模式；3.全局操作模式；4.简化全局模式；5.逻辑访问表；6.各站点逻辑模式；7.各站点访问表；8.局部逻辑模式（关系或Codasyl）；9.局部物理模式（关系或Codasyl）,分布要求分析阶段频率表：各站点上每一应用激活次数（假设所有应用在所有站点上都能执行）划分表：可用于模式中各实体的潜在水平分片规则极化表：指明由一个站点发出的一给定应用访问一给定片段的频率（定量分析方法）,分布设计阶段分片设计非冗余分配冗余分配局部模式的重新构造,分布设计,全局数据模式,逻辑访问表,分布要求,站点逻辑模式,站点逻辑访问表,三个站点站点1：丹佛机场（CO）站点1：纽约机场（NY）站点1：亚特兰大机场（GA）数据库存储内容机场规程班机调度班机可用情况旅客订票情况三个应用订票应用登记应用起飞应用,实体左下角和右下角的数字表示：示例总数和应用选择的平均示例数访问数据库中的起飞与到达机场、起飞与到达时间和班机日期，以k表示这些关键词确定班机后，建立旅客的一个新的示例及联系“订票”的一个示例，把用户的信息（名字、电话写入数据库O表示输出，w表示写入,根据数据库中的旅客名字，班机号，班机日期，查明有关旅客和班机的示例，显示“种类”信息。根据“种类”信息和座位图，将一个座位号分配给旅客，并写入座位图和座位号属性，以及旅客的检查行李号,产生即将离开机场的30架班机的信息显示在TV监视器上。根据数据库中的机场符号，当前日期，起飞时间，到达时间，查明班机号、起飞时间、出入口、延期、目的地机场符号、目的地城市，显示出来。,实体访问表：班机,实体访问表：机场,实体访问表：旅客,联系访问表：从,联系访问表：到,联系访问表：订票,联系访问表：登记,站点1：丹佛（CO）站点2：纽约（NY）站点3：亚特兰大（GA）应用a：订票应用b：登记应用c：起飞,将机场的区域属性选作为机场实体的划分准则将旅客电话号码前三位（区域码）作为旅客实体的划分属性谓词选择性表示按照该准则划分各类元组所占的百分数,两种方法划分班机实体，应用不同的联系“从”或“到”和机场划分区域于同一基本划分，结果不同。根据第一订票地点和班机起飞区域做导出划分机场班机乘客,分四步：对每一实体选择分片原则确定非冗余分配在非冗余分配上引入冗余在每一站点上重新构造局部模式,机场实体：基于区域的水平分段机场1，机场2，机场3班机实体：基于起飞机场的导出水平分段班机1，班机2，班机3旅客实体：基于旅客预定的所有班机起飞的导出水平分段旅客1，旅客2，旅客3，旅客4，旅客5，旅客6，旅客7，,1.分片设计,根据分片原则站点1：机场1，班机1，旅客1站点2：机场2，班机2，旅客2站点3：机场3，班机3，旅客3根据极化表和频率表站点2：旅客4，旅客5，旅客6，旅客7站点3：旅客5,2.确定非冗余分配,冗余超出了同一实体所有片断的效益机场实体：不进行冗余分配班机实体：不进行冗余分配有限冗余旅客实体：预定离开两个区域的乘客：，旅客4，旅客5，旅客6，放到两个站点上预定离开三个区域的乘客：旅客7，放到三个站点上,3.冗余分配,BC,站点1的局部模式,4.局部逻辑模式,自然分配,班机2,从,到,订票,登记,到,机场2,旅客2u旅客4u旅客6u旅客7,AC,站点2的局部模式,4.局部逻辑模式,自然分配,班机3,从,到,订票,登记,到,机场3,旅客3u旅客5u旅客6u旅客7,AB,站点3的局部模式,4.局部逻辑模式,自然分配,将现有的各种不同的数据库模式集成为全局模式.三个问题选择公用数据库模型来描述数据库的全局模式把每个站点上的本地模式翻译成公用数据模型把各站点上的本地数据模式集成为一公用的全局模式,自底向上方法主要问题是构造一个全局模式（超视图）.把各站点上的数据库模式看成是全局模式的一个视图这个问题就可看作是视图综合问题概括分层结构支持视图综合经典方法就是生成三个实体：一个具有共同属性（超类型），两个具有不相交属性（子类型）视图综合次序一次把一个视图和全局模式进行综合，逐步构造起全局视图通常，最好首先综合最大的或最重要的视图，然后跟着综合小的或者不重要的视图,班机,机号,日期,可用座位,出入口,座位图,延期,班机,机号,日期,可用座位,机型,座位图,识别相似性模式命名相似性模式结构相似性不同Site上有相似应用,使用各自DB的数据副本,则这两Site之间有某些相似点.识别冲突命名冲突：同物异名（EMP,EMPLOYEE），异物同名域差异 定标差异：计量单位不同(天、小时、分钟、秒）结构差异：同一对象有的用实体描述,有的用属性描述.处理操作期间不一致的数据策略（5种，p64-65）,系统B概念模式,班机,订票,旅客,标识符,起飞,起飞时间,座位图,可用座位,种类,名字,电话,到达,到达时间,班机,班机B,班机A,飞机符(机号),日期(1,3),可用座位,座位图,出入口,登记,订票,从,到,机场,到达时间,到达机场,起飞时间,起飞机场,起飞时间,到达时间,座位号,检查行李,旅客,种类,名字,电话,综合后建立的全局模式,数据集成,XML Ontology View,Exercise 1 已知有如下两种段分配:A R1在Site1,R2在Site2,R3在Site3.B R1和R2在Site1,R2和R3在Site3.另已知有如下应用(所有应用的频率相同)A1:在Site1上发出,读5个 R1记录,5个 R2记录 A2:在Site3上发出,读5个R3记录,5个R2记录 A3:在Site2上发出,读10个R2记录.问:1.如果以本地应用为主要设计目标,那个分配较优?2.假定A3改为要修改10个R2记录,并仍以本地应用为其设计目标,则那个分配方案较优?,站点1,站点2,站点3,站点3,站点2,站点1,A1R1,A3R2,A2R3,A1R1,R2,A3,A2R2,R3,方案A,方案B,读取,更新,10,10,10,5,5,图2-12 COMPANY关系数据库模式,主码用下划线标出,EMPLOY,DEPARTMENT,DEPT_LOCATION,PROJECT,WORKS_ON,DEPENDENT,Exercise 2,三个站点A,B,C部门1（总部），部门2，部门3在站点B上频繁访问EMPLOYEE,PROJECT中有关工作在部门2的雇员和该部门管辖的项目信息在站点C上频繁访问EMPLOYEE,PROJECT中有关工作在部门3的雇员和该部门管辖的项目信息雇员信息主要是指EMPLOYEE表中的FNAME,ESSN,SALARY,SUPERSSN属性A，B，C站点上频繁访问本站点所在部门的项目工时信息站点A供公司总部使用，经常存取为保险目的而纪录的DEPENDENT信息外，还定期地存取所有雇员和项目的信息,图2-13 站点的片段分配（b）站点B上的对应于部门2的关系片段,图2-13 站点的片段分配（a）站点C上的对应于部门3的关系片段,图2-15 站点A上的对应于部门1（总部）的片断,EMPLOYEE,PROJECT,DEPENDENT,Exercise 3 建立百货连锁店分布式数据库系统:由一个总部和多个远程连锁店组成总部和各个连锁店之间有数据交换，局域网和广域网总部负责产生各类汇总表，如销售汇总表各站点系统相对独立总部统一管理各门店商品的业种和品牌信息，各门店也经常使用这两类信息供应商、合同、商品和销售信息等经营基础数据都由各门店单独管理和使用，门店之间互不相关整个连锁店的职员信息由总部管理，各门店只可以查询本部门的职员信息该连锁店的会员卡实行全国联网消费，会员可以经常异地消费,基本关系模式（初步）,DEPARTMENTEMPLOYEECUSTOMERPRODUCT（p#，YEZHONG，PINPAI，）CONTRACTSALESSUPPLIER,大作业之一（实验）,题目：飞机订票系统集团公司管理系统（习题2.9）连锁店管理系统（习题2.10）自选（鼓励）,大作业之一（实验）,要求：小组：自由组合，23一组，4人一组要我批准时间：期末考试之前完成提交内容：设计报告，代码，开发总结报告设计主要内容：基本关系模式，分片情况，分布情况，系统功能设计开发内容：能够在至少两个站点上实现应用的功能，可以使用远程访问的模式。提交时检查运行情况。,提交任务表格,项目名称项目组组成：组长、组员项目分工情况：设计、开发、总结之一或者其中两类工作每个人信息：姓名、培养单位、E-mail，组长的电话。任务简单描述见Word文件：分布式数据库实验任务书于3月28日之前填好任务书发送到,总 结,分布式数据库的创建方法（重构法/组合法）自顶向下的设计方法数据分片数据分配 DATAID-D方法（分布要求分析和分布设计阶段）实例研究：飞机订票系统 自底向上方法,