分布式数据库系统的设计

1分布式数据库系统的设计及RMI简介姚易简婕王伟2课本知识目录2.1分布式数据库系统设计概述2.5自底向上设计分布式数据库2.2自顶向下设计分布式数据库2.3DATAID-D方法2.4实例研究：飞机订票系统32.1分布式数据库系统设计概述1分布式数据库系统定义2分布式数据库设计的目标3分布式数据库系统设计的内容4分布式数据库系统的创建方法5分布式数据库设计的方法42.1.1分布式数据库系统定义分布式数据库系统中的数据是物理分布在用计算机网络连接起来的各个站点上；每一个站点是一个集中式数据库系统，都有自治处理的能力，完成本站点的局部应用；而每个站点上的数据并不是互不相关的，它们构成一个逻辑整体，统一在分布数据库管理下，共同参与并完成全局应用，并且分布式数据库系统中的这种“分布”对用户来说是透明的，也就是说，本地与远程结合的“接缝”是被隐蔽的，用户几乎感觉不到远程与本地结合的接缝的存在，即“一个分布式系统应该看起来完全像一个非分布系统”。52.1.2分布式系统设计的目标1分布式数据库的本地性或近地性尽可能减少站点之间的通信次数和通信量2控制数据的适当冗余考虑到本地性，并发性，可靠性，一致性，开销等3工作负荷分布充分利用每个站点计算机的能力和资源提高性能4存储的能力和费用62.1.3分布式数据库系统设计的内容相类似于集中式数据库设计：数据库+应用数据库设计：全局模式设计+局部模式设计关键点：全局模式如何划分并映射到站点新设计问题：数据的分片、片段的位置分配需求增加：各个应用的发出点/各个应用在每个站点被激活的频率/各个应用对访问对象的每个数据对象的访问次数，类型和统计分析72.1.4分布式数据库系统的创建方法组合法：自底向上的创建方法82.1.4分布式数据库系统的创建方法重构法：自顶向下的创建方法92.1.5分布式数据库设计的方法自顶向下方法：从头开始设计自底向上方法：聚集现存数据库然而！许多情况下，设计者都是一部分使用自顶向下方法，另一部分使用自底向上方法GOON：分别详述这些方法102.2自底向上设计分布式数据库1构造全局模式的设计问题2构造全局模式的解决方法3自底向上综合的一个示例112.2.1构造全局模式的设计问题在异构分布式数据库设计中特别重要：1选择公有数据库模型来描述数据库的全局模式2把每个站点上的本地模式翻译成公有的数据模型3把各站点上本地数据模式集成一个公有的全局模式122.2.2构造全局模式的解决方法1识别相似性2识别冲突：命名冲突/域差异/定标差异/结构差异3处理操作期间的不一致性4经典解法是生成三个实体：一个具有共同属性另两个具有非相交属性132.2.3自底向上综合的一个示例问题：假设已存在两个飞机订票系统A和B，可供查询各自班机的可用情况。二者有不同的概念模型。现需要将这两个系统合为一个分布式数据库系统，以便从两个公司的任一办公室能查询班机的可用情况。结果：综合后建立起来的全局模式中，有一个概括分层被用来表示两个子类型班机A和班机B。值得注意的是，对两个局部模式，应以不同的方法翻译一个需要有关班机从一给定机场起飞的信息的查询。142.2.3自底向上综合的一个示例152.2.3自底向上综合的一个示例162.2.3自底向上综合的一个示例172.3自顶向下设计分布式数据库1自顶向下设计分布式数据库的步骤和内容2数据的分片设计3数据库片段的位置分配设计182.3.1步骤和内容集中式：需求分析概念设计逻辑设计物理设计分布设计：位于逻辑设计与物理设计之间，以一个全局的与站点无关的模式作为输入，以产生分布式数据库各站点的子模式为结果输出，包括数据的分片设计和片段的位置分配设计分片：把一全局对象（实体或关系）细分成若干逻辑片段的过程分配：把各片段映射到一个或多个站点的过程，片段是最合适的数据分配单位192.3.2数据的分片设计基本目标：产生一个对全局数据合适的划分方案。这种方案得到的片段作为分布式数据库中数据的分配和存储单位，不但能够减少应用中的操作量，而且能够对于应用具有最大可能的本地性，即使得各片段位于其使用最多的站点，或者说，使用绝大多数应用所使用的数据位于该应用的原发始点。当分片的好处太小，不足以补偿分片造成的开销时，不必要分片20分片方法：水平分片垂直分片混合分片遵守规则：完整性可重构不相交水平分片：对全局关系执行“选择”操作，可以具体分为初始分片和导出分片两种垂直分片：对全局关系执行“投影”操作，组之间必须只在某个键属性上重叠，而垂直群集的组在其他属性上也可以重叠2.3.2数据的分片设计21数据片段位置分配的方法1非冗余分配：估算每种分配后选择最佳冗余分配：2所有得益站点法：非复制问题的解+若干唯一复本3附加复制法：非复制问题的解+从最有益处起逐步附加复本，直至无明显好处2.3.3数据库片段的位置分配设计22数据片段分配的费用和得益估算假定i表示片段的下标j表示站点的下标k表示应用的下标Fkj表示应用k在站点j上被激活的频率Rki表示应用k被激活一次，对片段i进行检索访问的次数Uki表示应用k被激活一次，对片段i进行更新访问的次数Nki=Rki+Uki表示应用k被激活一次，访问片段i的总次数2.3.3数据库片段的位置分配设计23水平分片情况1非冗余分配：将片段分配到访问次数最多的站点2.3.3数据库片段的位置分配设计2所有得益站点：本站点的应用的检索访问费用总比任何一个其他站点发出的应用对该片段进行更新访问的费用要低3附加复制法：Dj表示片段Ri冗余度；Fi表示Ri在每个站点都复制的得益242.3.3数据库片段的位置分配设计垂直分片情况假定把站点r上的关系R垂直分成两个片段Rs和Rt，并将Rs和Rt分别分配在站点S和t,然后将应用分组并估算它们的利益情况252.3.3数据库片段的位置分配设计垂直分片情况1应用组As:自站点s发出，它们只使用Rs,因而是本地应用，得益2应用组At:自站点t发出，它们只使用Rt,因而是本地应用，得益3应用组A1:自r发出，原使用Rt或Rs,现在需要一次额外的远程访问，损失：4应用组A2:自r发出，原来使用R，现在需要两次额外的远程访问，损失：5应用组A3:与r,s,t不同，访问Rs和Rt,现需一次额外的远程访问，损失：262.3.3数据库片段的位置分配设计垂直群集情况与垂直分片的情况类似，只是要注意检索及更新要同时涉及到Rs和Rt了GOON：详述自顶向下法中的一个具体方法：DATAID-D方法以飞机订票系统为例讲述分布式数据库系统设计272.4DATAID-D方法2.4.1DATAID-D方法概述2.4.2分布要求分析阶段2.4.3分布设计阶段282.4.1DATAID-D方法概述１．是自顶向下设计分布式数据库的一个典型方法，由意大利米兰工业大学提出２．作为集中式数据库设计DATAID-1方法论的扩充而构造的３．集中式数据库设计的四个阶段需求分析，概念设计，逻辑设计和物理设计４．增加两个阶段：分布要求分析阶段和分布设计阶段29DATAID-D方法的分布式数据库设计步骤30主要设计步骤简要概述１．需求分析需求分析简单地说就是分析用户的要求２．概念设计将需求分析得到的用户需求抽象为信息结构即概念结构设计，如画Ｅ-Ｒ图３．逻辑设计将E-R图转换为相应的数据模型相符合的逻辑结构，如关系模型31主要设计步骤简要概述４．物理设计确定数据库的物理结构；对物理结构进行评价５．分布要求分析收集关于分布的信息，如水平分片的划分谓词每一应用在各站点激活的频率等６．分布设计产生全局数据的分片模式和片段的位置分配模式，分配模式描述了分配在各站点上的数据情况322.4.2分布要求分析阶段目的：收集以后用于推动分布设计所需要的信息输入：用户对分布的要求和全局数据概念模型与操作模式输出：应用的频率表，实体的划分表和数据与应用的极化表33三种类型的表1.频率表给出各站点上每一应用激活次数．这里假设所有应用在所有站点上都有可能执行2.划分表指明可使用于模式中各实体的潜在水平分片规则．3.极化表基于定量分析方法来说明分片如何影响着应用处理的本地性．一个极化值表指明由一给定站点发出的一给定应用访问一给定片段的概率342.4.3分布设计阶段目标：从全局数据模式，逻辑访问表和分布要求出发，将数据分配在站点上．输出：各站点的逻辑模式和逻辑访问表．包括四个阶段：分片设计，非冗余分配，冗余分配和局部模式的重新构造．35分片设计分片设计对实体进行水平分片和垂直分片，以便为以后设计阶段确定可能的分配单位．要使每一片段是一个合适的分配单位，就必须保证由各站点上执行的各应用，大约以同一方式（即相同频率）访问在片段中的事例（元组）．分片设计主要包括逻辑判定，进行逻辑判定时，从极化表中选择某些谓词，并用它们定义逻辑片段．36目标：是把各片段映射到使用该片段最多的站点上．问题：如何识别最频繁访问该片段的站点？方法：根据频率表与极化表，采用“最佳适应法”，令Fij应用i使用站点j的频率；Pijk应用i使用站点j时片段k的极化值于是从站点j访问片段k的次数给出如下：因此，片段k被分配到站点j`，使得非冗余分配37冗余分配冗余分配的执行是使用“贪婪”启发式，可以采用上面已经阐述过的“所有得益站点法”或采用“附加复制法”．就是初起使用非冗余分配，在每次迭代时，计算因增加一副本使其变成本地的检索访问的得益与为维护该副本一致性所需要的附加远程修改访问的损失之差值．这个数字是个较大的正数时，把该片段的副本存储到得益站点，否则就不增加．38局部模式重新构造局部模式的重新构造是重新构造片段分配站点上的局部模式，这一阶段也负责ER全局模型中的联系分配．大多数联系是作为对应实体标识符间的结合实现的，DATAID-D方法建议把联系放置在具有最大基数性的实体或片段的站点上，使得必须传送的实体标识符尽可能少．392.5实例研究：飞机订票系统2.5.1实例研究概述2.5.2飞机订票系统中的分布要求分析2.5.3飞机订票系统中的分布设计402.5.1实例研究概述这是在飞机订票系统中应用DATAID-D方法进行分布式数据库设计的例子．问题：我们要研究的订票系统维护一个分布在三个站点（即机场1、2、3）上的数据库，为使这个系统更形象，考虑在美国开业的一家公司。其中：1=丹佛，代码为CO，位于美国的西部；2=纽约，代码为NY，在北部；3=亚特兰大，代码为GA，在南部。数据库存储有关机场规程、班机调度、班机可用情况和旅客订票等数据。41飞机订票数据库的全局数据模式42飞机订票数据库的全局操作模式43订票应用[图2.7(a)]每当一新的旅客想预定一班机的机票时，该应用就被激活。在这种情况下，访问数据库中的起飞与到达的机场，起飞与到达时间和班机日期。这些属性在图中标以k，表明它们被用作访问数据的关键词。箭头表明经由两个关系“从”与“到”访问从机场实体到班机实体的进行情况。实体左下角和右下角中的数字分别表示示例总数和由应用选择的平均示例数。一旦确定了班机，就建立旅客实体的一个新的示例及联系订票的一个示例；关于旅客名字、电话和种类（对应于票价）的数据被写入数据库。注意：可用座位属性先读后写（“o，w”;o表示输出，w表示写入）。问题：示例总数和由应用选择的平均示例总数有何异同？解答：以班机实体为例，图中的数字2000，表示的是班机示例的总的样本空间数，假设在该样本中，a应用发生的次数为n1，b应用发生的次数为n2，c应用发生的次数为n3，那么就有如下等式：2000=3n1+n2+30n3其中：3，1，30分别为应用a，b，c选择的平均示例数44登记应用[图2.7(b)]凡旅客实际登机时，先执行登记任务。根据旅客名字和班机号与日期，查明有关旅客和班机的示例（”k“属性），然后，显示检索种类信息（”o“），并根据这一信息和班机座位图，将一座位号分配给旅客，写入座位图和座位号属性，以及旅客的检查行李号（即托运行李的票据号）。45起飞应用[图2.7(c)]从机场起飞时的应用，产生描述即将离开该机场的30架班机的起飞信息的报告并显示在TV监视器上。机场符号和当前日期与时间用于标识所涉