分布式数据库系统设计课件

1、分布式数据库系统设计分布式数据库系统设计分布式数据库系统设计概述自顶向下设计分布式数据库DATAID-D方法实例研究：飞机订票系统自底向上设计分布式数据库分布式数据库系统设计 第2章分布式数据库系统设计概述分布式数据库系统设计 第2章分布式数据库设计概述1创建方法1.1 组合法 剖析网络功能剖析原有数据库系统解决数据的一致性、完整性和可靠性难度较大 通常是异构或者同构异质DDBS用户1用户2用户n分布式协调管理系统DBMS1DBMS2DBMSm 网络分布式数据库设计概述1创建方法1.1 组合法 剖析网络功分布式数据库设计概述1DDBS创建方法1.1 重构法 根据实现环境和用户需求按照DDBS的

2、设计思想和方法从总体设计做起，包括LDBS,重新建立一个DDBS可有效解决数据一致性、完整性和可靠性问题。 通常是同构异质或同构同质DDBS用户1用户2用户n分布式数据库管理系统 网络分布式数据库设计概述1DDBS创建方法1.1 重构法 根1.2 DDBS设计内容1 分布式数据库设计概述DDBS设计DDB设计应用设计全局模式设计局部数据库设计相关应用需求各个应用的原发站点各个应用在每个站点的激活频率各个应用对要求访问数据对象的访问次数、类型和统计分布分片和分布1.2 DDBS设计内容1 分布式数据库设计概述DDBS设计1.3 DDBS设计目标1 分布式数据库设计概述DDBS设计目标本地性或近地

3、性存储能力和费用尽量减少通信次数和通信量，90/10准则分片和分布方案（本地和远程访问次数）择优控制数据适当冗余冗余增加了可靠性、可用性，提高了效率维护数据一致性开销增加工作负荷分布各站点可以分担整个工作任务本地性降低1.3 DDBS设计目标1 分布式数据库设计概述DDBS本地1.4 DDBS设计方法1 分布式数据库设计概述DDBS设计方法自顶向下方法（重构法）混合方法自底向上方法（组合法）1.4 DDBS设计方法1 分布式数据库设计概述DDBS自顶2.1 步骤和内容2 自顶向下设计DDB需求分析概念设计视图设计分布设计物理设计观察与监视系统需求全局概念模式访问模式外部模式定义局部概念模式物理

4、模式用户输入视图集成用户输入反馈反馈自顶向下设计过程2.1 步骤和内容2 自顶向下设计DDB需求分析概念设计视图假若有全局关系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(垂直分片) 2.2 数据的分片设计2 自顶向下设计DDB 分片原则 假若有全局关系R 被分片为子关系(片段)集合2

5、.2 数据的职工关系 E (e#, name, loc, sal,) 查询: Qa: select * Qb: select *from E from Ewhere loc=Sa where loc=Sband and .两个站点 : Sa, Sb Qa QbSaSb2.2 数据的分片设计2 自顶向下设计DDB 举例 职工关系 E (e#, name, loc, sal,)两 e# NM Loc Sal E578Sa1000SallySb2500TomSa500Joee# NM Loc Sale# NM Loc Sal58Sa1000TomSa500Joe7Sb2500Sally.F站点Sa站

6、点 Sb2.2 数据的分片设计2 自顶向下设计DDB 举例 e# NM Loc Sal578Sa10基本水平分片 以关系自身的属性性质为基础，执行“选择”操作，将关系分割成若干个不相交的片段。 R = R1, R2 R1 = loc=Sa(E) R2 = loc=Sb(E)2.2 数据的分片设计2 自顶向下设计DDB 基本水平分片 基本水平分片 2.2 数据的分片设计2 自顶向下设计DD若 R = R1, R2, , Rn, 则完整性 对于每一个元组 tR, RiR 使得 tRi 不相交性 对tRi, Rj 使得 tRj, i j可重构性 操作是 (可以忽略, 因为完整性就蕴含着) R = R

7、1, R2, , RnP = p1, p2, , pn是一简单谓词集合，为保证分片的正确性，P必须是：完整的：同一分片中的任意两个元组被应用同样概率访问。最小的：集合P中的所有谓词与应用密切相关。(不同分片中的元组被访问的概率是不同的)具有完整性和最小性不是必要条件, 但是对于简化分配问题有好处2.2 数据的分片设计2 自顶向下设计DDB 基本水平分片 若 R = R1, R2, , Rn, 则2.2 数例子EMP ( E#, NAME, DEPT, JOB, SAL, TEL, ) DEPT=1,2 JOB=P, -P假定，应用经常查询的内容是属于部门1且是程序员的职员。则可能有的水平分段限

8、定 P= DEPT=1 （不是完整的） P=DEPT=1, JOB=P （是完整的、最小的） P=DEPT=1, JOB=P, SAL500 （完整的，不是最小的）2.2 数据的分片设计2 自顶向下设计DDB 基本水平分片 例子2.2 数据的分片设计2 自顶向下设计DDB 基本水平分如何保证分片原则“手工”检查!e.g., R1 = loc=Sa E ; R2 = loc=Sb E生成具有满足分段原则的限定谓词2.2 数据的分片设计2 自顶向下设计DDB 基本水平分片 如何保证分片原则“手工”检查!2.2 数据的分片设计2 自顶设有关系 E (e#,name,Loc,sal,A,), 查询使用

9、的简单谓词（Ai Value）是: A5, Loc = Sa, Loc = Sb下一步: - 生成 “小项” 谓词- 消除无用谓词给定简单谓词集 Pr= p1, p2,. pn , 则“小项”谓词（minterm predicate）形式:p1* p2* pn* 这里 pk* 是 pk 或是 pk2.2 数据的分片设计2 自顶向下设计DDB 谓词生成举例设有关系 E (e#,name,Loc,sal,A,), (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) A

10、5) Loc=SA Loc=SB(6) A5) Loc=SA (Loc=SB)(7) A5) (Loc=SA) Loc=SB(8) A5) (Loc=SA) (Loc=SB)2.2 数据的分片设计2 自顶向下设计DDB小项谓词选择(1) A5 Loc=S (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)

11、 (A5) (Loc=SA) (Loc=SB)2.2 数据的分片设计2 自顶向下设计DDB小项谓词选择 (9) (A5 LoR2: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 分片结果2.2 数据的分片设计2 自顶向下设计DDBR2:5 A 10 Loc=SA 分注:无用段的消除依赖于应用的语义e.g.: 如果 LOC 可以是 SA, SB, 则最终分段集合应该加上R4:5 A 10 Loc SA Loc SB R8:A 5 Loc SA Loc SB R12

12、:A 10 Loc SA Loc SB2.2 数据的分片设计2 自顶向下设计DDB注:无用段的消除依赖于应用的语义e.g.: 如果 LOC 可小项选择率（minterm selectivity） 对某一给定小项谓词用户查询可能选择到的元组数访问频率（Access frequency）用户应用访问数据的频率小项访问频率可以通过用户查询频率获得2.2 数据的分片设计2 自顶向下设计DDB分片数量信息小项选择率（minterm selectivity） 对某例子 E(#, NM, LOC, SAL,) 有查询应用Qa: select *Qb: select * from Efrom E where

13、LOC=Sa where LOC=Sb and and .2.2 数据的分片设计2 自顶向下设计DDB如何选择小项谓词举例例子 2.2 数据的分片设计2 自顶向下设计DDB如何选择(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 三种选择2.2 数据的分片设计2 自顶向下设计DDB(1) Pr = R1 =

14、E 三种选择Loc=Sa sal 1000Loc=Sa sal 1000Loc=Sb sal 1000Loc=Sb sal 1000R1R3R2Qa: Select loc = Sa .Qb: Select loc = Sb .R2 是好的( R1 , R3不好 ) 2.2 数据的分片设计2 自顶向下设计DDB图示Loc=Sa Loc=Sa Loc=Sb Loc=SbLoc=Sa sal 1000Loc=Sa sal 1000Loc=Sb sal 1000Loc=Sb sal 1000R1Qa: Select loc = Sa .Qb: Select loc = Sb .此处元组有较高的选择概

15、率此处元组选择概率较低分段内元组选择概率不等因此 R1 不好.2.2 数据的分片设计2 自顶向下设计DDB理由Loc=Sa Loc=Sa Loc=Sb Loc=SbLoc=Sa sal 1000Loc=Sa sal 1000Loc=Sb sal 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. 如果以本地

16、应用为主要设计目标, 那个分配较优? 2. 假定A3改为要修改10个R2记录, 并仍以本地应用为其设计目标, 则那个分配方案较优?Exercise 1站点1站点2站点3站点3站点2站点1A1R1A3R2A2R3A1R1, R2A3A2R2, R3方案A方案B读取更新10101055站点1站点2站点3站点3站点2站点1A1A3A2A1A3A2 图2-12 COMPANY关系数据库模式, 主码用下划线标出 EMPLOYFNAMEMINIT LNAMEESSNBDATEADDRESSSEXSALARYSUPERSSNDNODEPARTMENTDNAMEDNOMGRSSNMGRSTARTDATEDEP

17、T_LOCATIONDNODLOCATIONPROJECTPNAMEPNOPLOCATIONDNO WORKS_ONESSNPNOHOURSDEPENDENTESSNDEPENDENT_NAMESEXBDATERELATIONSHIPExercise 2 图2-12 COMPAN三个站点A,B,C部门1（总部），部门2，部门3在站点B上频繁访问EMPLOYEE,PROJECT中有关工作在部门2的雇员和该部门管辖的项目信息在站点C上频繁访问EMPLOYEE,PROJECT中有关工作在部门3的雇员和该部门管辖的项目信息雇员信息主要是指EMPLOYEE表中的FNAME,ESSN,SALARY,SUP

18、ERSSN属性A，B，C站点上频繁访问本站点所在部门的项目工时信息站点A供公司总部使用，经常存取为保险目的而纪录的DEPENDENT信息外，还定期地存取所有雇员和项目的信息三个站点A,B,CFNAMEMINIT LNAME ESSN SALARYSUPERSSN DNOAlicia J Zelaya 999887777 25000 987654321 2Jennifer S Wallace 987654321 43000 888665555 2Ahmad V Jabbar 987987987 25000 987654321 2EMPD2DEP2DNAMEDNOMGRSSNMGRSTARTDAT

19、EAdministr 2987654321 2003-01-01DEP2_LOCSDNODLOCATION 2StatlondDEP2_WORKSON ESSNPNOHOURS333445555 10 10.0999887777 30 30.0999887777 10 10.0987987987 10 35.0987987987 30 5.0987654321 30 20.0987654321 30 15.0DEP2_PROJECTPNAMEPNOPLOCATIONDNOComputer 10 Startlond 2Newbenef 30 Startlond 2图2-13 站点的片段分配（b）

20、站点B上的对应于部门2的关系片段FNAMEMINIT LNAME ESSN SFNAMEMINIT LNAME SSN SALARYSUPERSSN DNOJohn B Smith 123456789 30000 333445555 3Franklin T Wong 333445555 40000 888665555 3Ramesh K Narayan 666884444 38000 333445555 3Joyce A English 453453453 25000 333445555 3EMPD3DEP3DNAMEDNOMGRSSNMGRSTARTDATEResearch 33334455

21、55 2003-05-22DEP3_LOCSDNODLOCATION 3Bellaire 3Sugarlnd 3HoustonDEP3_WORKSON ESSNPNOHOURS123456789 1 32.5123456789 2 7.5666884444 3 40.0453453453 1 20.0453453453 2 20.0333445555 2 10.0333445555 3 10.0 DEP3_PROJECTPNAMEPNOPLOCATIONDNOProduct X 1 Bellaire 3Product Y 2 ugarlnd 3Product Z 3 Houston 3图2-13 站点的片段分配（a）站点C上的对应于部门3的关系片段FNAMEMINIT LNAME SSN SA 图2-15 站点A上的对应于部门1（总部）的片断 EMPLOYEEPROJECTPNAMEPNUMERPLOCATIONDNUMDEPENDENTESSNDEPENDENT_NAMESEXBDATERELATIONSHIPFNAMEMINIT LNAME SSN SALARYSUPERSSN DNOAlicia J Zelaya 999887777 25000 987654321 2Jenn