大连理工大学算法分析与设计2014 3章-分布式数据库系统的设计2014-12-3课件

1、1徐喜荣分布式数据库系统2012年11月2013年1月徐喜荣（)21 分布式数据库系统设计的目标 在理想情况下，分布式数据库系统的用户可不关心数据的物理分布， 由系统负责处理在不同站点上的分布数据。但是数据实际分布情况会 影响系统的总体性能：访问多个数据对象所需的时间和费用，会因为 这些数据对象是存放在同一站点，还是分布在多个站点有很大差别。 分布式数据库系统中最重要的目标是尽量减少对网络的利用，即尽可能减少站点之间的通信次数和通信量。 因此，分布式数据库系统的数据库设计者必须仔细考虑数据是否分片，片段如何复制，以及数据或片段如何分布，甚至在分布式数据库 管理系统支持高的分布透明性时也要如此。

2、 3 DDBS设计目标目标一：本地性或近地性；目标四：存储能力和费用。目标二：控制数据适当冗余；目标三：工作负荷分布；1 分布式数据库系统设计的目标41 分布式数据库系统设计的目标目标一：分布式数据库的本地性或近地性 分布式数据库设计中的一个主要原则是使数据和应用实现最大程度的本地性。 开发一个分布式数据库的主要目的：通过尽可能地使数据靠近使用该数据的应用进行分配，从而提高处理的本地性或近地性，减少通信。 在一个精心设计的分布式数据库中，90%的数据应当在本地站点找到而只有10%的数据需要在远程站点上进行访问。也即最有效的设计是确保数据对最大数目的应用具有本地性。 设计方法是对每种可供选择的分

3、片方法和片段的分配方法都统计出本地访问和远程访问的次数，然后从其中选择一个最佳的方案。5目标二：控制数据适当冗余 1 分布式数据库系统设计的目标 控制数据的适当冗余是分布式数据库系统设计的又一个目标。 在分布式数据库系统中，为了提高系统的本地性、并发度和可靠性，需要增加数据的副本。 这不仅使应用具有高度的可用性和本地性，而且当数据的任何一个副本不能使用时，可方便地使用在另一站点中的该数据的副本进行恢复，从而提高系统的可靠性。7 数据库的分布会受到各站点的存储能力的影响。在网络中可以有 专门用于存储数据的站点，也可以有完全不支持大量容存储的站点。 一般数据存储的费用与 CPU，I /O及传输的费

4、用相比是不重要的， 但是必须考虑各站点可用存储空间的限制。1 分布式数据库系统设计的目标目标四：存储的能力和费用82 分布式数据库系统设计的内容 分布式数据库系统设计的内容包括：分布式数据库的设计和应用设计。 分布式数据库的设计包括全局模式设计和每个站点的局部数据库设计。其中的关键是数据库的全局模式应如何划分，并映射到合适的站点上。由此产生了分布式数据库设计所特有的两个新问题：数据的分片设计和片段的位置分配设计。 分片设计研究的是全局模式分片的“逻辑准则”，而片段的位置分配设计研究的是处理数据在各站点上的“物理布局” 。 在分布式数据库设计中，为使分片设计和片段的位置分配设计得到的模式能够高效

5、地支持应用，还需要知道应用的确切要求。1.2 分布式数据库的发展重构法 ：一种自顶向下的创建方法。根据系统的实现环境和用户需求， 按照分布式数据库系统的设计思想和方法，采用统一观点，从总体设计 做起，包括各站点上的数据库系统，重新建立一个分布式数据库系统。 按照统一的思想来考虑 分布式数据库系统中的 各种问题，有效地解决 分布式数据库系统数据 一致性、完整性和可靠性。花费的人力、物力会比较多，研制周期也比较长，系统建设的代价会比较大。采用重构法创建的分布式数据库系统，通常是同构异质或同构同质DDBS。大多选择同构型分布式数据库系统。用户1用户2用户n分布式数据库管理系统网络3 分布式数据库系统

6、的设计方法113.1 分布式数据库的发展3 分布式数据库系统的设计方法组合法 ：一种自底向上的创建方法，也称集成法。利用现有的计算机网络和独立存在于各个站点上的现存数据库系统，通过建立一个分布式协调管 理系统，集成为一个统一的分布式数据库系统。 先剖析网络功能；剖析各个站点上原有的数据库系统；解决数据的一致性、完整性和可靠性；若各站点上DBMS不相同，理论和实践难度较大。 采用组合法的分布式数据库系统通常是异构或者同构异质DDBS。用户1用户2用户n分布式协调管理系统DBMS1DBMS2DBMSm 网络12 DDBS设计方法自顶向下方法（重构法）：从头开始设计分布式数据库。设计者理解用户的数据

7、库应用要求，历经概念设计、逻辑设计和物理 设计阶段，并将与计算机系统无关的规格说明逐渐求精成低级的、与 计算机系统有关的规格说明。概念设计和逻辑设计的结果是数据库的 全局模式，包含了数据库的所有数据元素及其使用形式。 专门针对 分布式数据库的一个设计阶段称为分布设计，将全局模式映射成几个 可能交叠的子集模式，每一个子模式表示与一个站点有关的信息子集，然后完成每一单个数据库的设计。混合方法：许多实际情况中，设计者一部分使用自顶向下方法，另一部分使用自底向上方法。自底向上方法（组合法）：通过聚集现存数据库设计分布式数据库。由于需要互联一些现存数据库以形成一个多数据库系统，或者是由于对各站点已独立完

8、成了数据库的概念说明，所以各站点上数据库规格说明已是现存的。需综合各站点的规格说明，以便得到分布式数据库的全局概念模式。3 分布式数据库系统的设计方法一、集中式数据库设计 包括四个阶段：需求分析、概念设计、逻辑设计、物理设计。需求分析涉及收集用户数据库应用的非结构规格说明，并收集在 设计数据字典中。 概念设计产生全局、综合数据库模式的一种概念规格说明和在此 模式上执行应用的概念规格说明。 逻辑设计将综合概念模式转换成一给定的DBMS类型(关系、网状、 层次或面向对象模型)的数据库模式。 物理设计要遵照所选择的特定DBMS的能力和特征进行，并产生 实现数据库的物理访问结构的定义。3.1 自顶向下

9、设计方法3 分布式数据库系统的设计方法15二、分布式数据库设计增加一个新的阶段：分布设计 分布设计位于逻辑设计与物理设计之间，以一个全局的、与站点无关的模式作为输入，以产生分布式数据库各站点的子模式 ( 局部概念模式 )作为结果输出。 分布设计包括：数据的分片设计和片段的位置分配设计。 分片是指把一个全局对象(实体或关系)细分成若干逻辑片段的过程； 分配是指把各片段映射到一个或多个站点的过程，片段是最合适的数据分配单位。3.1 自顶向下设计方法3 分布式数据库系统的设计方法自底向上设计方法主要问题是构造一个全局模式（超视图）.把分布式数据库中各站点上的数据库模式看成是全局模式的一个 视图，则寻

10、求全局模式的问题可以看作是视图综合问题。概括分层结构支持视图综合。概括分层允许定义两个实体之间的 类型和子类型关联，用于两个视图对同一实体的部分属性相交时。视图综合问题的经典方法就是生成三个实体： 一个实体具有共同属性（超类型），两个实体具有不相交属性（子类型）。在全局视图中，共同属性与子类型相关联，并且对包含非相交 属性的各个视图生成一子类型。视图综合次序问题：一次把一个视图和全局模式进行综合，逐步构造起全局视图。通常最好首先综合最大的或最重要的视图，然后综合小的或者不重要的视图。3.2 自底向上设计方法3 分布式数据库系统的设计方法一、构造全局模式问题分析班机机号日期可用座位出入口座位图延

11、期班机机号日期可用座位机型座位图班机班机1班机2机号日期可用座位座位图出入口延期机型使用概括分层的两个视图的合并3.2 自底向上设计方法3 分布式数据库系统的设计方法识别相似性：综合两个模式的第一步是识别它们的相似性，识别相似性是综合 模式的出发点。从先前存在的数据库中数据的相似性可以推得匹配，相似的值集 表明相交。通过比较属性，可以识别匹配属性域。如果在不同站点上有相似应用，使用各自数据库中的数据副本, 则这两站点的数据库之间有某些相似点。3.2 自底向上设计方法3 分布式数据库系统的设计方法二、识别相似性和识别冲突识别冲突：识别不同模式中相似数据的不同表示或域定义。 通过在全局模式中引入差

12、异或在源模型中做一些折中，可以解决冲突。 模式差异包括命名冲突、域差异、定标差异和结构差异。命名冲突：同物异名（EMP,EMPLOYEE）和异物同名。通过在 全局模式中存储名字对应表就能方便地解决。域差异：检测此问题通过比较源数据库或文件并注意不一致性来 进行。概括分层可以用来表示这一问题的解。 定标差异：在具有同一数值的不同视图中可以见到定标差异，如 计量单位不同(天、小时、分钟、秒）。设计中如有可能，应使用 更精确的定标来检索数据，并使用换算公式进行连接或输出。结构差异：同一对象有的用实体描述, 有的用属性描述。视图设计中，一般通过改变一个或两个视图来解决结构差异。3.2 自底向上设计方法

13、3 分布式数据库系统的设计方法处理操作期间的不一致数据策略（5种） 对于设计时不能解决的冲突，需设计可供选择的策略，当执行时检测到不一致性时，以回答有不一致数据的查询。这些策略包括：显示任一不一致值，但不通知用户。这是最直截了当，同时也是最 危险的解决办法。显示所有不一致值，并告诉用户不一致值信息源。在这种情况下， 用户应能评价不一致性的原因。求不一致值的某些组合函数值，并向用户显示此结果。可能使用的 组合函数包括求平均、求最小值、求最大值。使用这种技术是在不 同时间内出现时预期观察值也不同的场合。 显示最新值。这一策略需要更新操作的时间戳。它所依据的假设是 不一致性归因于更新不及时，因此，最

14、新的值也是最可能的值。显示最可靠系统的值。这一策略所依据的假设是，设计者可以评价 分布式数据库中站点的可靠性。3.2 自底向上设计方法3 分布式数据库系统的设计方法分片设计的基本目的：产生一个对全局数据合适的划分方案。使用这种方案得到的片段作为分布式数据库中数据的分配和存储单位时，不但能够减少应用中的操作量，而且能够对于应用具有最大可能的本地性，使绝大多数应用所使用的数据位于该应用的原发站点。在数据分片设计时，是从分配的观点来看，根据具有“相同性质”的元组或属性进行分组，每组就构成一个片段。如果同一个片段的任意两个元素具有“相同性质” (例如访问频率相同)的话，则数据分配时所用的任意一种方法都

15、将把这两个元素放在一起，以这种方式得到的片段将是分布式数据库中数据合适的分配和存储单位。4.1 分片设计的基本目的4 数据分片设计不论哪种分片方法，必须遵守如下规则：假若有全局关系R 被分片为子关系(片段)集合 R = R1, R2, , Rn, 则 R 满足完整性条件： 对任意x R, RiR 必有 xRi ，i=1,2,n可重构条件：R= Ri (水平分片）, R= Ri （垂直分片）不相交条件：Ri Rj =空集, ij, i, j=1,2,n (水平分片)Ri Rj =主键属性, i, j=1,2,n (垂直分片) 4.2 数据分片的基本类型和方法4 数据分片设计例2.1 S(S#,

16、SNAME, AGE, SEX) define fragment S1 as select * from s where sex=M define fragment S2 as select * from s where sex=F 一、基本水平分片 以关系自身的属性性质为基础，执行“选择”操作，将关系分割成若干个不相交的片段。4.3 水平分片4 数据分片设计对全局关系进行水平初级分片需要确定一组不相交的、完整的限定语(选择条件/谓词)。 即表征合适分片的两个性质是： 令 P = p1, p2, , pn 是一简单谓词集合，为保证分片的正确性，则P必须是：完整的：同一分片中的任意两个元组被任一

17、应用以同样概率访问。最小的：集合P中的所有谓词与应用密切相关。限定语具有完整性和最小性不是必要条件, 但是对于简化分配问题 有好处。4.3 水平分片4 数据分片设计例2.2 设全局关系EMP ( E#, NAME, DEPT, JOB, SAL, TEL, ) DEPT=1,2 JOB=P, -P假定应用经常查询的内容是属于部门1且是程序员的职员。 则可能有的水平分段限定：(1) P= DEPT=1 （不是完整的）(2) P= DEPT=1, JOB=P 是正确且合适（完整的、最小的） 这样分片得到的四个片段： DEPT=1, JOB=P, DEPT=1, JOB=-P DEPT=2, JOB

18、=P, DEPT=2, JOB=-P 每一片段中元组被访问的概率是相等的，因此是完整的； 每一限定语都与应用密切相关，因此是最小的； 限定语之间互斥，因此片段之间必不相交。(3) P=DEPT=1, JOB=P, SAL500 （完整的，不是最小的） 因为SAL500与应用无关。4.3 水平分片4 数据分片设计例2.3 设全局关系 SC( S#, C#, GRADE)， S ( S#, SNAME, AGE, SEX ) 要求： 将SC划分为男生各门课成绩和女生的各门成绩。 这不可能从SC本身的属性性质来执行选择，必须从关系S的属性性质 或水平片段来导出。二、导出水平分片 全局关系的导出式水平

19、分片不是以其自身属性性质为基础，而是从另一个关系的属性性质或水平片段推导出来的。确定一方便的导出式水平分片要求确定应用所执行的最重要的结合操作。导出分片可以使片段与片段间“连接”变得更容易。 4.3 水平分片4 数据分片设计按S的属性导出 Define fragment SC1 as （ Define fragment SM as ） Select SC.S#, C#, GRADE From SC, S Where SC.S#=S.S# and SEX=M Define fragment SC2 as （ Define fragment SF as ） Select SC.S#, C#, GR

20、ADE From SC, S Where SC.S#=S.S# and SEX=F如果S已经进行水平分片，分为SM和SF, 分别为男生全体和女生 全体，则按S的水平分片（SM/SF）导出： Define fragment SC1 as Select * From SC Where S# in (Select SF.S# from SM) Define fragment SC2 as Select * From SC Where S# in (Select SM.S# from SF)4.3 水平分片4 数据分片设计全局关系R= Ri , i=1,2,n 如果属性AR, 必有ARi , i=1,

21、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的 一个垂直群集。 垂直分片和垂直群集的目的在于使得许多重要应用可以只访问一个 片段来执行，从而使操作具有本地性。4.4 垂直分片与垂直群集4 数据分片设计全局关系 EMP(Eno#, NAME, SAL, TEL, MAGNUM, DEPT)， 其码为 Eno#。主要应用有: 在Sa 站点查询 NAME, SAL, T

22、EL; 在Sb 站点查询 NAME, MAGNUM, DEPT .采用垂直分片: EMP1 ( Eno#, NAME, SAL, TEL ) EMP2 ( Eno#, MAGNUM, DEPT ) 则NAME属性只属于一个片段，对于上述应用，必须进行连接 操作和非本地访问。采用垂直群集: EMP1 (Eno#, NAME, SAL, TEL) EMP2 (Eno#, NAME, MAGNUM, DEPT) 则对于上述应用不需要执行连接操作且可实现较好的本地性。4.4 垂直分片与垂直群集4 数据分片设计33 数据分布是指分布式数据库中的数据不是存储在一个站点的计算机上，而是根据需要将数据划分成若

23、干逻辑片段，按某种策略把数据分片所得 的逻辑片段分散地存储在各个站点上。 数据分布的策略有：集中式、分割式、复制式、混合式。集中式： 所有数据片段都安排在同一站点上。对数据的控制和管理比较容易，数据的一致性和完整性能得到保证。缺点是该站点负担过重，系统 对该站点的依赖性过多，容易出现瓶颈，系统可靠性较差。5.1 数据分布策略5 数据分布设计34分割式： 所有数据只有一份，被分割成若干个逻辑片段，每个逻辑片段被 指派在某个特定的站点上。可充分利用各个站点上的存储设备， 数据的存储量大。各站点可自治的检索和修改数据，发挥系统的 并发操作能力。当部分站点出现故障时，系统仍能运行，提高了 系统的可靠性

24、。复制式： 全局数据有多个副本，每个站点都有一个完整的数据副本。系统 可靠性高，响应速度快，数据库恢复也较容易。但是要保持各个 站点上数据的同步修改，将要付出高昂的代价。5 数据分布设计5.1 数据分布策略35混合式： 全部数据被分为若干子集，每个子集安置在不同的站点上，但 任一 站点都没有保存全部的数据，并且根据数据的重要性决定 各个子集的副本的多少。 这种分布策略兼顾了分割式和复制式的做法，获得两者优点， 但也包含两者的复杂性。5 数据分布设计5.1 数据分布策略在满足用户需求的前提下, 把设计好的数据片段分配到相应的站点 上存储，尽可能提高系统的效益。片段分配的主要目的在于使应用执行的远

25、程访问次数最少。例子: Emp( Eno#, Name, Location, Salary ) R1 = loc=Sa Emp ; R2 = loc=Sb Emp Querya: select where Location=Sa. Queryb: select where Location=SbSite aSite bR1, R2 存放在哪?5.2 数据片段位置分配的方法5 数据分布设计 根据应用需求确定是非冗余分配还是冗余分配。在非冗余分配中，每个片段恰好映射到一个站点上；在冗余分配中，每个片段映射到一个或多个站点上；设计者决定每一片段复制程度，复制利益随检索与更新间的比值而增加。分配方法非

26、冗余分配设计方法最佳适应法：对每一种分配都进行估算， 然后选择最佳的站点。其他方法冗余分配的设计方法所有得益站点法附加复制法：启发式方法应用需求确定非复制问题的解；确定一组站点分配片段的一个副本。确定非复制问题的解；从最有益处起逐步附加复制的副本，直到附加复制无好处为止。5.2 数据片段位置分配的方法5 数据分布设计 设F为单个片段， 共有m个站点 S1, Sm , 变量X1, , Xm取值如下： 0 如果 片段F 不在 站点Sj上存储 1 如果 片段F 在站点Sj上存储 则总代价为： Total cost = Read Cost + Write Cost + Storage Cost 读代价

27、 写代价 存储代价 确定 Xj 的值, 1 j m, 使总代价最小。Xj =5.2 数据片段位置分配的方法分配的简化模型5 数据分布设计读代价： Read cost = ti MIN Cij i: 读申请源站点； ti: 站点Si 上的读申请激活次数； Cij: 从 Si 读 Sj 站点上的片段F的代价。i=1m.3ici,3ci,1ci,2ti FFF.12j5.2 数据片段位置分配的方法分配的简化模型5 数据分布设计写代价： Write cost = Xj ui Cij i: 写申请源站点 j: 被更新站点 Xj: 0 如果 片段F 不在 站点Sj上存储 1 如果 片段F 在站点Sj上存储

28、 ui: 站点 Si 上更新激活次数 Cij: 从站点 Si 更新 Sj 分段 F 的代价i=1j=1mm.iFFFUpdatesui5 数据分布设计5.2 数据片段位置分配的方法分配的简化模型存储代价：Store Cost = Xi di Xi: 0 如果 片段F 不在 站点Si上存储 1 如果 片段F 在站点Si上存储 di: 站点 Si 存储片段 F 的代价i=1m5 数据分布设计5.2 数据片段位置分配的方法分配的简化模型目标函数：确定 Xj 的值, 1 j m, 使总代价最小。min ti MIN Cij + Xj ui Cij + Xi di ji=1j=1i=1mmm即使最简单的

29、公式也是 NP-完全问题。通常使用方法是尽可能将片段分配在被局部访问位置。5 数据分布设计5.2 数据片段位置分配的方法分配的简化模型为了进行数据片段分配的费用和得益的估算， 假定和得算，假定： i ：表示片段下标； j ：表示站点下标； k ：表示应用下标； Fkj ：表示应用k 在站点j上激活的频率； Rki ：表示应用k被激活一次，对片段i 检索访问的次数； Uki ：表示应用k被激活一次，对片段i 更新访问的次数； Nki= Rki +Uki：表示应用k被激活一次访问片段i的总次数； Fkj* Nki : 表示应用k在站点j上对片段i的访问频度； Fkj* Rki : 表示应用k在站点

30、j上对片段i的检索频度； Fkj* Uki : 表示应用k在站点j上对片段i的更新频度。5 数据分布设计5.3 数据片段分配的费用和得益估算最佳适应法（非冗余分配）： 将片段Ri分配到访问片段Ri次数最多的那个站点上 。 在站点j上 片段Ri 的本地访问次数(对全部应用加和)是： Bij= k Fkj * Nki = k Fkj * (Rki +Uki) (1)估算： max ( Bij ) = Bij 则片段 Ri 就分配在站点 j上。5 数据分布设计5.3 数据片段分配的费用和得益估算水平分片情况j例：设有一个片段Ri, 有两个应用A1,A2 ,可能在三个场地分别设定为 Site, Sit

31、e, Site，并从应用需求分析得到的频度参数为： 应用k=A1： 在j=Site上访问频度 FA1,* NA1,Ri =60, 在j=Site上访问频度 FA1,* NA1,Ri =30, 在j=Site上访问频度 FA1,* NA1,Ri =20, 应用k=A2： 在j=Site上访问频度 FA2,* NA2,Ri =40, 在j=Site上访问频度 FA2,* NA2,Ri =50, 在j=Site上访问频度 FA2,* NA2,Ri =50. 则计算站点j上 片段Ri 的本地访问次数 Bij 如下： 当 j=Site , Bij = k=A1,A2 Fkj * Nki = (60+40

32、)=100, 当 j=Site, Bij = k=A1,A2 Fkj * Nki = (30+50)=80, 当 j=Site, Bij = k=A1,A2 Fkj * Nki = (20+50)=70, 从计算结果可以得到 Bij=100， j 被选定为Site, 也就是说片段Ri 应分配在Site上。5 数据分布设计5.3 数据片段分配的费用和得益估算水平分片情况所有得益站点法（冗余分配方法一）： 将片段Ri的副本分配到所有得益站点 j 上。 所有得益站点：指在这些站点上，所有应用的检索访问费用总比从 任何一个其他站点发出的所有应用对片段 Ri进行更新访问费用要低。初始时使用非冗余分配，确

33、定非冗余问题的解。在每次迭代时，计算因增加一副本使其变成本地检索访问的得益与 为了维护该副本一致性所需要的附加远程修改访问的损失之差值。 这个数字是个较大的正数时，把该片段的副本存储到这个站点。 由此可以确定一组得益站点。 5 数据分布设计5.3 数据片段分配的费用和得益估算水平分片情况所有得益站点法（冗余分配方法一）： 估算增加一个副本使其变成本地检索访问的得益与为了维护该副本一致性所需要的附加远程修改访问的损失之差额值： Bij= kFkj*Rki - c*k jj Fkj*Uki (2)其中： c=更新/检索 为度量更新访问费用与检索访问费用之比的一个常数，因更新有大量控制信息和局部操作

34、，所以代价较高，一般c1. 通过计算，如果Bij* 0，则站点j*是得益站点，应把片段Ri分配在所有场地j*上；如果所有Bij0，把Ri的单一副本放在Bij*为最大的场地上。5 数据分布设计5.3 数据片段分配的费用和得益估算水平分片情况附加复制法（冗余分配方法二）： 首先确定非冗余问题的解，然后从最有益处起逐步附加复制的副本，此过程直到“附加复制”已无明显好处时结束。这种方法就是典型的启发式方法。 由于副本数与可用、可靠不是线性关系，意大利学者S.Ceri 曾发表 文章提出，可以用一函数(Di)来估计存放一个Ri新副本在增加系统的可靠性和可用性方面的得益。 令 Di 表示片段 Ri的冗余度(

35、副本个数), Fi 表示 Ri 在每个站点全部都复制的得益 。Di 与 Fi 之间存在如下关系： 当Di=1, (1)=0；Di=2, (2)=Fi/2； Di=3, (3)=3*Fi/4 等。 5 数据分布设计5.3 数据片段分配的费用和得益估算水平分片情况附加复制法（冗余分配方法二）： 从给出的上述函数出发可以得到求站点j上引入片段Ri 新副本的 得益公式： 用上面公式来评估在站点j上Ri的新副本得益。 采用这种方法随着冗余度的增加得益逐渐减少。 一般，当一个片段只有两三个副本时，系统的得益在增加；但是当副本数再增加时，系统的得益就不再明显增加。5 数据分布设计5.3 数据片段分配的费用和

36、得益估算水平分片情况rs其他站点tRtRRs网络A1A2AsAtA35 数据分布设计5.3 数据片段分配的费用和得益估算垂直分片情况 假设把站点r上的关系R垂直分片成两个片段Rs和Rt, 并将Rs 分配到 s 站点Rt分配到 t 站点，然后将应用分组为 As, At, A1, A2, A3, 并估算 它们的得益情况。估算各个应用分组得益情况如下： 应用组As：自站点s发出只使用Rs, 因而是本地应用，节省了一次 远程访问，得益： BAs = Fks Nki ( k As)应用组At ：自站点t发出, 只使用Rt, 因而是本地应用，节省了一次远程访问，得益： BAt = Fkt Nki ( k

37、At)5 数据分布设计5.3 数据片段分配的费用和得益估算垂直分片情况rs其他站点tRtRRs网络A1A2AsAtA3应用组A1: 由站点r发出, 原先使用Rt或Rs, 现在这些应用需要进行一次额外的远程访问，损失： BA1 = Fkr Nki ( k A1)应用组A2: 由站点r发出, 原先使用R(本地访问), 现在这些 应用需要进行两次额外的远程访问，损失： BA2 = 2 Fkr Nki ( k A2)应用组A3: 由不同于站点r,s,t的站点发出, 它们要访问Rt或Rs这两者的属性, 现在这些应用需一次额外的远程访问，损失： BA3 = Fkj Nki ( k A3, j r,s,t

38、)5 数据分布设计5.3 数据片段分配的费用和得益估算垂直分片情况rs其他站点tRtRRs网络A1A2AsAtA3这种分片和分配的得益为： Bist = BAs + BAt - BA1 - BA2 - BA3 其中： BAs = Fks Nki ( k As) BAt = Fkt Nki ( k At) BA1 = Fkr Nki ( k A1) BA2 = 2 Fkr Nki ( k A2) BA3 = Fkj Nki ( k A3, j r,s,t )这个公式可以用在穷举式“分裂”算法(exhaustive splitting algorithm)中，以确定用试探站点s和t的全部可能组合的

39、方法来把站点i的R分裂 成站点s的Rs和站点t的Rt是否方便。5 数据分布设计5.3 数据片段分配的费用和得益估算垂直分片情况把R分成两个片段Rs和Rt, 分别分配到站点s和站点t, 它们具有重叠的 属性I。因此要求重新考虑应用的分组问题： (1) 应用As含局限于站点s的本地应用，它们或者读取Rs的任何属性， 或者更新不在重叠部分I的Rs的属性。 (2) 应用At类同应用As。 (3) 应用A1含有原先局限于站点r本地的更新应用，它们对I的属性进行 更新，而现在它们需要同时访问Rs和Rt。 (4) 应用A2含有原先局限于站点r本地的查询应用，现在它们需要同时 访问Rs和Rt。 (5) 应用A

40、3含有不在站点r、s或t的应用，它们对I的属性进行更新，而 现在也需要同时访问Rs和Rt。可以使用上面的关于Bist的表示公式来评价这种垂直群集方法的得益。5 数据分布设计5.3 数据片段分配的费用和得益估算垂直群集情况分布式数据库设计阶段需求分析概念设计分布要求分析设计全局逻辑设计分布设计局部逻辑设计局部物理设计位于概念设计阶段之后进行，主要工作：1. 收集用户分布要求信息2. 水平分片的划分谓词3. 每一应用在各站点激活的频率Fkj全局逻辑设计之后进行，主要工作：1. 分布要求和全局逻辑模式作为输入2. 形式为全局数据库模式和逻辑访问表3. 输出为分片模式和分配模式 DATAID-D方法是

41、自顶向下设计分布式数据库的一个典型方法，由意大利米兰工业大学提出，由集中式数据库设计DATAID-1方法论的扩充而得到。 DATAID-1方法有四个阶段：需求分析、概念设计、逻辑设计和物理设计。扩充的DATAID-D对其增加两个阶段：分布要求分析阶段和分布设计阶段。6 DATAID-D方法6.1 DATAID-D方法概述说明：1.设计数据字典；2.全局数据模式；3.全局操作模式；4.简化全局模式；5.逻辑访问表；6.各站点逻辑模式；7.各站点访问表；8.局部逻辑模式（关系或网状）；9.局部物理模式（关系或网状）全局逻辑设计分布设计局部逻辑设计逻辑设计需求分析概念设计分布要求分析局部物理设计18

42、7654329要求频率表划分表极化表6 DATAID-D方法6.1 DATAID-D方法概述分布要求分析用户分布要求全局数据概念模型全局数据操作模式应用频率表实体访问表应用极化表 分布要求分析的目的是收集以后用于推动分布设计所需要的信息。 这一阶段的输入：是用户对分布的要求、全局数据概念模型与全局 数据操作模式。 建立三种类型的表作为这一阶段的输出：应用的频率表、实体的 访问表和数据与应用的极化表(polarization)。6 DATAID-D方法6.2 分布要求分析阶段分布要求分析阶段应用频率表：给出各站点j上每一个应用k激活的次数Fkj（假设所有 应用在所有站点上都能执行；当一个应用在一

43、个站点上从不执行时，相应位置的频率项为零）。实体访问表：可用于模式中各实体的潜在水平分片规则。每条分片规则指明引入水平分片的可能理由，并与在一给定站点访问一给定数据子集的一个或多个应用有关。应用极化表：基于定量分析方法来说明分片如何影响着应用处理的本地性。一个极化表指明由一个站点j发出一个给定应用k访问一个给定片段i 的频率Pkji 。6 DATAID-D方法6.2 分布要求分析阶段分布设计全局数据模式实体逻辑访问表分布要求站点逻辑模式站点逻辑访问表 分布设计的目的是把全局数据模式、实体逻辑访问表和分布要求做为 输入，将数据分配在站点上。 分布设计阶段输出：各站点的逻辑模式和站点逻辑访问表。

44、在以后的局部逻辑设计阶段和在各站点上独立进行的物理设计阶段， 要使用这些逻辑模式和逻辑访问表。6 DATAID-D方法6.3 分布设计阶段DATAID-D的分布设计分成四个阶段：分片设计阶段；非冗余分配阶段；冗余分配阶段；局部模式的重新构造阶段。6 DATAID-D方法6.3 分布设计阶段一、分片设计阶段： 分片设计对实体进行水平分片和垂直分片，以便为以后设计阶段确定可能的分配单位。 要使每一个片段i是一个合适的分配单位，就必须保证由各站点j上执行的各应用k，大约以同一方式 (即相同频率) 访问片段中的实例 (元组)。存在一个阈值条件，超过这一阈值，进一步分片行不通。 分片设计主要包括逻辑判定

45、。进行逻辑判定时，从极化表中选择某些谓词，并用它们定义逻辑片段。6 DATAID-D方法6.3 分布设计阶段二、非冗余分配阶段： 非冗余分配的执行是把各片段i 映射到使用最多的站点j上。根据频率表与极化表，采用“最佳适应法”，可得到从一给定站点j访问一个给定片段i次数的定量测度，从中选出该片段的定位站点。 在该站点发出的所有应用事务k上，求极化值Pkji与该片段所使用的频率Fkj之积的和，可以得到各片段在每一站点上可能的使用频率。有可能识别最频繁访问该片段的站点，将该片段分配到这一站点上。令： Fkj 表示应用k 使用站点j 的频率； Pkji表示应用k 使用站点j 访问片段i 的极化值(即频

46、率)。 于是，全部应用k从站点j访问片段i的次数给出如下： Nij= kFkj*Pkji 因此，片段i被分配到站点j, 使得 Nij= max 所有j Nij 6 DATAID-D方法6.3 分布设计阶段三、冗余分配阶段：冗余分配的执行是使用“贪婪”启发式，可采用“所有得益站点法”或采用“附加复制法”。初始使用非冗余分配，在每次迭代时，计算因增加一个副本使其变成本地检索访问的得益与为维护该副本的一致性所需要的附加远程修改访问的损失之差值。这个数字是个较大的正数时，把该片段的副本存储到这些得益站点上，有理由说明增加冗余度的必要性，否则就不增加。6 DATAID-D方法6.3 分布设计阶段四、局部

47、模式重新构造阶段：局部模式的重新构造是重新构造片段分配站点上的局部模式。这一阶段也负责E-R全局模型中的联系分配。大多数联系是作为对应实体标识符间的结合实现的。DATAID-D方法建议把联系放置在具有最大基数性的实体或片段的站点上，使得必须传送的实体标识符尽可能少。6 DATAID-D方法6.3 分布设计阶段本飞机订票系统维护一个分布在三个站点上的数据库。在美国开业的一家公司，有三个站点即机场1、2、3. 其中：站点1：丹佛机场（代码CO）；站点2：纽约机场（代码NY）；站点3：亚特兰大机场（代码GA）；数据库存储数据内容如下：机场有关规程；班机调度及班机可用情况；旅客订票情况；订票系统共有三

48、个应用：订票应用；登记应用；起飞应用。7 实例研究：飞机订票系统7.1 实例研究简述班机订票从到机场登记旅客到达时间机号日期可用座位起飞时间符号城市进入口座位图延期区域安全规则种类座位号检查行李名字电话权力7 实例研究：飞机订票系统7.1 实例研究简述-飞机订票系统数据库的全局数据模式种类w电话w2 40机场320000班机日期k起飞时间k符号k从可用座位o、w到到达时间k名字w1100000旅客订票 每当一新的旅客想预定一个班机的机票时，订票应用就被激活。1. 实体左下角和右下角的数字表示：示例总数和应用选择的平均示例数。2. 访问数据库中起飞与到达机场;起飞与到达时间;班机日期. k表示关

49、键词。3. 确定班机后建立旅客的一个新的示例及联系“订票”的一个示例，把用户的名字、 电话和种类（对应于票价）的数据写入数据库。 O表示输出，w表示写入。7 实例研究：飞机订票系统7.1 实例研究简述-飞机订票数据库的订票应用全局操作模式1100000旅客120000班机机号k日期k座位图o、w座位号w检查行李w订票登记种类o名字k 凡旅客实际登机时，先执行登记任务，激活登记应用。根据数据库中的旅客名字，班机号，班机日期，查明有关旅客和班机的示例（“k”属性），然后显示检索“种类”信息（“o”）。根据“种类”信息和班机座位图，将一个座位号分配给旅客，并写入座位图和座位号属性，以及旅客的检查行李

50、号（即托运行李的票据号）。7 实例研究：飞机订票系统7.1 实例研究简述-飞机订票数据库的登记应用全局操作模式1 40机场3020000班机30 40机场日期k符号k起飞时间k, o班机号o从到出入口o延期o城市o符号o到达时间k, o从机场起飞时的应用，产生描述即将离开机场的30架班机的起飞信息的报告并显示在TV监视器上。 激活起飞应用。1. 根据数据库中机场符号;当前日期;起飞时间;到达时间, 查明 班机号、 起飞时间、 出入口、 延期、目的地机场符号、目的地城市，然后显示在TV监视器。7 实例研究：飞机订票系统7.1 实例研究简述-飞机订票数据库的起飞应用全局操作模式属性操作a（订票）b

51、（登记）c（起飞）班机号ko日期kkk座位图o/w进入口o延期o可用座位o/w表2.1(1) 实体访问表：班机对每个实体，需估算应用的定量数据，建立起逻辑访问表。表中的列对应于操作，行对应于实体属性，矩阵元素表示在对象上所执行的动作类型 (“o：表示输出”， “w：表示写入”， “k：表示关键词”)。7 实例研究：飞机订票系统7.1 实例研究简述-逻辑访问表:班机属性操作a（订票）b（登记）c（起飞）符号kk/o城市o权力区域安全规则表2.1(2) 实体访问表：机场7 实例研究：飞机订票系统7.1 实例研究简述 -逻辑访问表:机场属性操作a（订票）b（登记）c（起飞）名字wk电话w表2.1(3

52、) 实体访问表：旅客7 实例研究：飞机订票系统7.1 实例研究简述-逻辑访问表:旅客属性操作a（订票）b（登记）c（起飞）起飞时间kk/o表2.1(4) 联系访问表：从7 实例研究：飞机订票系统7.1 实例研究简述-逻辑访问表:从属性操作a（订票）b（登记）c（起飞）到达时间kk/o表2.1(5) 联系访问表：到7 实例研究：飞机订票系统7.1 实例研究简述-逻辑访问表:到属性操作a（订票）b（登记）c（起飞）种类wo表2.1(6) 联系访问表：订票7 实例研究：飞机订票系统7.1 实例研究简述-逻辑访问表:订票属性操作a（订票）b（登记）c（起飞）座位号w检查行李w表2.1(7) 联系访问表

53、：登记7 实例研究：飞机订票系统7.1 实例研究简述-逻辑访问表:登记 应用频率表给出各站点j上每一个应用k激活的次数Fkj。 下面频率表中说明了在站点1：丹佛(CO), 站点2：纽约(NY)和站点3：亚特兰大(GA)上全局操作模式描述的三个应用a,b,c (即应用a：订票、应用b：登记、应用c：起飞)的频率。7 实例研究：飞机订票系统7.2 飞机订票系统中的分布要求分析 基本划分表中给出实体机场和实体旅客的基本划分表。 1. 将机场的区域属性选作为机场实体的划分准则； 2. 将旅客电话号码前三位(区域码)作为旅客实体的划分属性； 3. 谓词选择性表示按照该准则划分各类元组所占的百分数。7 实

54、例研究：飞机订票系统7.2 飞机订票系统中的分布要求分析1. 两种方法导出划分班机实体：应用不同的联系“从”(起飞机场)或“到” (到达机场)和基于已把机场划分成区域来划分班机实体。使用两个不同联系于同一基本划分，产生两种不同导出划分，如下表前两行。2. 下表最后两行给出了导出划分旅客实体的两个方法：依据联系订票和班机，按班机起飞区域或第一订票地点划分。在这种情况下，导出机制分两步，因为它从机场作用到班机，然后从班机作用到旅客。前一种情形，依据他们第一次订票的班机的地点来划分旅客；后一情形中，依据他们各次的订票的班机起飞区域来划分旅客。7 实例研究：飞机订票系统7.2 飞机订票系统中的分布要求

55、分析 导出划分表的注释表说明了七种可能情形：旅客可能预定只离开一个区域(A,B,C)的班机，或离开两个区域(AB,BC,AC)的班机，或离开所有区域(ABC)的班机。由于订票是一种多对多关系，所以需要以上七种情况(考虑往返机票)。 7 实例研究：飞机订票系统7.2 飞机订票系统中的分布要求分析极化表a 订票b 登记c 起飞1丹佛2纽约3亚特123123按区域划分机场P180100P21075100P31080100按出发机场划分航班P17010080P27510080P37010080. 一个极化值表指明由一个站点j发出的一个给定应用k访问一个给定片段i的频率Pkji。下表中的列关系到每一站点

56、上应用的激活信息，表中行关系到划分谓词。极化表中的第一个子矩阵，与订票应用有关联且使用按区域划分机场实体( P1代表区域1, P2代表区域2, P3代表区域3 )。此子矩阵表明，如果选定按区域划分机场，那么在区域1发出的关于订票查询应用有80%的概率是关系到区域1的机场。对第1列中的其他两个位置，假定其余20%访问是均匀分配的各占10%.7 实例研究：飞机订票系统飞机订票系统中的分布设计分四步：对每一个实体选择分片原则；确定非冗余分配；在非冗余分配上引入冗余；在每一站点上重新构造局部模式。7 实例研究：飞机订票系统7.3 飞机订票系统中的分布设计所有实体都有水平分片：机场实体： 基于区域的水平

57、分段： 片段：机场1， 机场2， 机场3班机实体：基于起飞机场的导出水平分段： 片段：班机1，班机2， 班机3旅客实体： 基于旅客预定的所有班机起飞的导出水平分段： 片段：旅客1, 旅客2, 旅客3, 旅客4, 旅客5, 旅客6, 旅客7。一、分片设计 在分片设计中要求对应用做定量分析，可以把应用分成三类：通过划分变得容易的应用，变得更困难的应用和不受影响的应用。7 实例研究：飞机订票系统7.3 飞机订票系统中的分布设计根据分片原则，得出非冗余分配如下：片段机场1，片段班机1，片段旅客1被分配到站点1；片段机场2，片段班机2，片段旅客2被分配到站点2；片段机场3，片段班机3，片段旅客3被分配到

58、站点3； 对于实体旅客的其他片段，根据极化表和频率表来选择使用该片段最多的站点，因此有：片段旅客4，片段旅客6，片段旅客7被分配到站点2；片段旅客5被分配到站点3。二、确定非冗余分配7 实例研究：飞机订票系统7.3 飞机订票系统中的分布设计 由于机场实体和班机实体的与冗余有关的代价超出同一实体所有片段的效益，故不进行冗余分配，即机场实体：不进行冗余分配；班机实体：不进行冗余分配；对于旅客实体片段，引入有限的冗余度：旅客实体： 预定离开两个区域的乘客：旅客4、旅客5、旅客6放到两个站点上；预定离开三个区域的乘客：旅客7放到三个站点上。三、冗余分配7 实例研究：飞机订票系统7.3 飞机订票系统中的

59、分布设计班机1从到订票登记到机场1旅客1u旅客4u旅客5u旅客7BC站点1的局部模式四、局部逻辑模式 自然分配7 实例研究：飞机订票系统7.3 飞机订票系统中的分布设计班机2从到订票登记到机场2旅客2u旅客4u旅客6u旅客7AC站点2的局部模式自然分配7 实例研究：飞机订票系统7.3 飞机订票系统中的分布设计四、局部逻辑模式 班机3从到订票登记到机场3旅客3u旅客5u旅客6u旅客7AB站点3的局部模式自然分配四、局部逻辑模式 7 实例研究：飞机订票系统7.3 飞机订票系统中的分布设计随着社会的发展，人们工作和生活节奏的加快，日常生活中对超市的依赖程度也显著增加。这就促使超市规模的日益扩大，出现

60、了许多大型的连锁超市，为人们的生活提供了极大的便利连锁超市通常由一个总部和多个远程连锁店（门店）组成，并且每个门店分布在不同的地域。通常来说，门店主要负责自身日常业务的处理，如售货、进货、仓储等业务；而总部负责员工管理、业种管理等管理业务以及数据分析和挖掘，以便于进行辅助决策。8 实例研究：连锁超市分布式数据库系统8.1 系统概述连锁超市总部负责产生并管理该连锁超市的整体汇总数据。连锁超市的各个门店之间一般不进行数据交换。有关供应商信息、合同信息、商品信息和销售信息等经营基础数据都是各门店单独管理和使用,门店之间互不相关。每一个远程站点（总部和各门店）分别有一个数据库系统，各自组成一个独立的子