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

1徐喜荣分布式数据库系统2012年11月——2013年1月徐喜荣（xirongxu@)21分布式数据库系统设计的目标

在理想情况下，分布式数据库系统的用户可不关心数据的物理分布，由系统负责处理在不同站点上的分布数据。但是数据实际分布情况会影响系统的总体性能：访问多个数据对象所需的时间和费用，会因为这些数据对象是存放在同一站点，还是分布在多个站点有很大差别。分布式数据库系统中最重要的目标是尽量减少对网络的利用，即尽可能减少站点之间的通信次数和通信量。

因此，分布式数据库系统的数据库设计者必须仔细考虑数据是否分片，片段如何复制，以及数据或片段如何分布，甚至在分布式数据库管理系统支持高的分布透明性时也要如此。3

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

1分布式数据库系统设计的目标控制数据的适当冗余是分布式数据库系统设计的又一个目标。

在分布式数据库系统中，为了提高系统的本地性、并发度和可靠性，需要增加数据的副本。这不仅使应用具有高度的可用性和本地性，而且当数据的任何一个副本不能使用时，可方便地使用在另一站点中的该数据的副本进行恢复，从而提高系统的可靠性。6目标三：工作负荷分布1分布式数据库系统设计的目标分布式计算机系统的一个重要特征是把工作负荷分布在网络中的各个站点上。分布工作负荷的目的是充分利用每个站点的计算机的能力和资源以提高应用执行的并行程度，从而提高系统的性能。7

数据库的分布会受到各站点的存储能力的影响。在网络中可以有专门用于存储数据的站点，也可以有完全不支持大量容存储的站点。一般数据存储的费用与CPU，I/O及传输的费用相比是不重要的，但是必须考虑各站点可用存储空间的限制。1分布式数据库系统设计的目标目标四：存储的能力和费用82分布式数据库系统设计的内容

分布式数据库系统设计的内容包括：分布式数据库的设计和应用设计。分布式数据库的设计包括全局模式设计和每个站点的局部数据库设计。其中的关键是数据库的全局模式应如何划分，并映射到合适的站点上。由此产生了分布式数据库设计所特有的两个新问题：数据的分片设计和片段的位置分配设计。分片设计研究的是全局模式分片的“逻辑准则”，而片段的位置分配设计研究的是处理数据在各站点上的“物理布局”。在分布式数据库设计中，为使分片设计和片段的位置分配设计得到的模式能够高效地支持应用，还需要知道应用的确切要求。92分布式数据库系统设计的内容DDBS设计DDB设计应用设计全局模式设计局部数据库设计各个应用的原发站点各个应用在每个站点激活频率各个应用对要求访问数据对象的访问次数、类型和统计分布数据的分片设计和位置分配设计1.2分布式数据库的发展重构法：一种自顶向下的创建方法。根据系统的实现环境和用户需求，按照分布式数据库系统的设计思想和方法，采用统一观点，从总体设计做起，包括各站点上的数据库系统，重新建立一个分布式数据库系统。按照统一的思想来考虑分布式数据库系统中的各种问题，有效地解决分布式数据库系统数据一致性、完整性和可靠性。花费的人力、物力会比较多，研制周期也比较长，系统建设的代价会比较大。采用重构法创建的分布式数据库系统，通常是同构异质或同构同质DDBS。大多选择同构型分布式数据库系统。用户1用户2用户n分布式数据库管理系统网络3分布式数据库系统的设计方法113.1分布式数据库的发展3分布式数据库系统的设计方法组合法：一种自底向上的创建方法，也称集成法。利用现有的计算机网络和独立存在于各个站点上的现存数据库系统，通过建立一个分布式协调管理系统，集成为一个统一的分布式数据库系统。先剖析网络功能；剖析各个站点上原有的数据库系统；解决数据的一致性、完整性和可靠性；若各站点上DBMS不相同，理论和实践难度较大。

采用组合法的分布式数据库系统通常是异构或者同构异质DDBS。用户1用户2用户n分布式协调管理系统DBMS1DBMS2DBMSm网络12

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

包括四个阶段：需求分析、概念设计、逻辑设计、物理设计。需求分析涉及收集用户数据库应用的非结构规格说明，并收集在

设计数据字典中。

概念设计产生全局、综合数据库模式的一种概念规格说明和在此

模式上执行应用的概念规格说明。

逻辑设计将综合概念模式转换成一给定的DBMS类型(关系、网状、

层次或面向对象模型)的数据库模式。

物理设计要遵照所选择的特定DBMS的能力和特征进行，并产生

实现数据库的物理访问结构的定义。3.1自顶向下设计方法3分布式数据库系统的设计方法15二、分布式数据库设计增加一个新的阶段：分布设计分布设计位于逻辑设计与物理设计之间，以一个全局的、与站点无关的模式作为输入，以产生分布式数据库各站点的子模式(局部概念模式)作为结果输出。分布设计包括：数据的分片设计和片段的位置分配设计。分片是指把一个全局对象(实体或关系)细分成若干逻辑片段的过程；分配是指把各片段映射到一个或多个站点的过程，片段是最合适的数据分配单位。3.1自顶向下设计方法3分布式数据库系统的设计方法把现有数据库集成起来构成分布式数据库时，可采用自底向上的方法。此方法重点是把将现有的各种不同的数据库模式集成为全局模式。集成就是把公用数据定义合并起来，并解决对同一个数据的不同表示方法之间的冲突。把现有数据库集成为一分布式数据库时，现有数据库很可能使用的是不同的DBMS，这将构成异构系统，从而增加了数据集成的复杂性。此时可以在每对不同的DBMS之间进行一对一的翻译，也可选择一个公用数据模型，然后再把涉及这个DBMS的所有的不同模式都翻译成这种唯一的表示方法。

3.2自底向上设计方法3分布式数据库系统的设计方法自底向上设计方法主要问题是构造一个全局模式（超视图）.把分布式数据库中各站点上的数据库模式看成是全局模式的一个视图，则寻求全局模式的问题可以看作是视图综合问题。概括分层结构支持视图综合。概括分层允许定义两个实体之间的类型和子类型关联，用于两个视图对同一实体的部分属性相交时。视图综合问题的经典方法就是生成三个实体：

一个实体具有共同属性（超类型），两个实体具有不相交属性（子类型）。在全局视图中，共同属性与子类型相关联，并且对包含非相交属性的各个视图生成一子类型。视图综合次序问题：一次把一个视图和全局模式进行综合，逐步构造起全局视图。通常最好首先综合最大的或最重要的视图，然后综合小的或者不重要的视图。3.2自底向上设计方法3分布式数据库系统的设计方法一、构造全局模式问题分析班机机号日期可用座位出入口座位图延期班机机号日期可用座位机型座位图班机班机1班机2机号日期可用座位座位图出入口延期机型使用概括分层的两个视图的合并3.2自底向上设计方法3分布式数据库系统的设计方法识别相似性：综合两个模式的第一步是识别它们的相似性，识别相似性是综合模式的出发点。从先前存在的数据库中数据的相似性可以推得匹配，相似的值集表明相交。通过比较属性，可以识别匹配属性域。如果在不同站点上有相似应用，使用各自数据库中的数据副本,则这两站点的数据库之间有某些相似点。3.2自底向上设计方法3分布式数据库系统的设计方法二、识别相似性和识别冲突识别冲突：识别不同模式中相似数据的不同表示或域定义。通过在全局模式中引入差异或在源模型中做一些折中，可以解决冲突。

模式差异包括命名冲突、域差异、定标差异和结构差异。命名冲突：同物异名（EMP,EMPLOYEE）和异物同名。通过在全局模式中存储名字对应表就能方便地解决。域差异：检测此问题通过比较源数据库或文件并注意不一致性来进行。概括分层可以用来表示这一问题的解。定标差异：在具有同一数值的不同视图中可以见到定标差异，如计量单位不同(天、小时、分钟、秒）。设计中如有可能，应使用更精确的定标来检索数据，并使用换算公式进行连接或输出。结构差异：同一对象有的用实体描述,有的用属性描述。视图设计中，一般通过改变一个或两个视图来解决结构差异。3.2自底向上设计方法3分布式数据库系统的设计方法处理操作期间的不一致数据策略（5种）对于设计时不能解决的冲突，需设计可供选择的策略，当执行时检测到不一致性时，以回答有不一致数据的查询。这些策略包括：显示任一不一致值，但不通知用户。这是最直截了当，同时也是最危险的解决办法。显示所有不一致值，并告诉用户不一致值信息源。在这种情况下，用户应能评价不一致性的原因。求不一致值的某些组合函数值，并向用户显示此结果。可能使用的组合函数包括求平均、求最小值、求最大值。使用这种技术是在不同时间内出现时预期观察值也不同的场合。显示最新值。这一策略需要更新操作的时间戳。它所依据的假设是不一致性归因于更新不及时，因此，最新的值也是最可能的值。显示最可靠系统的值。这一策略所依据的假设是，设计者可以评价分布式数据库中站点的可靠性。3.2自底向上设计方法3分布式数据库系统的设计方法分片设计的基本目的：产生一个对全局数据合适的划分方案。使用这种方案得到的片段作为分布式数据库中数据的分配和存储单位时，不但能够减少应用中的操作量，而且能够对于应用具有最大可能的本地性，使绝大多数应用所使用的数据位于该应用的原发站点。在数据分片设计时，是从分配的观点来看，根据具有“相同性质”的元组或属性进行分组，每组就构成一个片段。如果同一个片段的任意两个元素具有“相同性质”(例如访问频率相同)的话，则数据分配时所用的任意一种方法都将把这两个元素放在一起，以这种方式得到的片段将是分布式数据库中数据合适的分配和存储单位。4.1分片设计的基本目的4数据分片设计有两种基本的数据分片方法：水平分片方法和垂直分片方法。

水平分片是对全局关系执行“选择”操作，把具有相同性质的元组进行分组，构成若干个不相交的子集。水平分片的方法可归为基本水平分片和导出水平分片两类。

垂直分片是通过“投影”操作把它的属性分成若干组。根据应用以“同样方式”(具有相同的使用频率)访问的属性来进行分组。垂直分片的方法可归为基本垂直分片和垂直群集两类。基本垂直分片只在某个键属性上重叠，其他属性不可重叠；垂直群集的组在其他属性上也可以重叠。通过交替水平分片与垂直分片，可以产生混合分片。4.2数据分片的基本类型和方法4数据分片设计不论哪种分片方法，必须遵守如下规则：假若有全局关系R被分片为子关系(片段)集合

R={R1,R2,…,Rn},则R满足完整性条件：对任意x

R,RiR必有xRi

，i=1,2,…,n可重构条件：R=∪Ri(水平分片）,

R=∞

Ri

（垂直分片）不相交条件：Ri

∩Rj=空集,i≠j,i,j=1,2,…,n

(水平分片)Ri

∩Rj=主键属性,i,j=1,2,…,n(垂直分片)4.2数据分片的基本类型和方法4数据分片设计例2.1S(S#,SNAME,AGE,SEX)definefragmentS1asselect*fromswheresex=‘M’definefragmentS2asselect*fromswheresex=‘F’一、基本水平分片

以关系自身的属性性质为基础，执行“选择”操作，将关系分割成若干个不相交的片段。4.3水平分片4数据分片设计限定语：把初级分片对片段的定义中，执行选择操作的条件(或称谓词)叫做限定语(qualification)。例如：sex=‘M’和sex=‘F’----是限定语水平分片正确性原则的三个条件可以这样实现：若R={R1,R2,…,Rn},则完整性条件：各片段定义中的限定语集合必须是完整的，即至少是它们允许值的集合。可重构条件：如果限定语集合是完整的，则通过并操作总能重构全局关系。不相交条件：如果限定语之间是互斥的，它们的片段必不相交。4.3水平分片4数据分片设计对全局关系进行水平初级分片需要确定一组不相交的、完整的限定语(选择条件/谓词)。即表征合适分片的两个性质是：令P={p1,p2,…,pn}是一简单谓词集合，为保证分片的正确性，则P必须是：完整的：同一分片中的任意两个元组被任一应用以同样概率访问。最小的：集合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=‘P’},{DEPT=2,JOB=‘-P’}

每一片段中元组被访问的概率是相等的，因此是完整的；每一限定语都与应用密切相关，因此是最小的；限定语之间互斥，因此片段之间必不相交。(3)P={DEPT=1,JOB=‘P’,SAL>500}（完整的，不是最小的）因为SAL>500与应用无关。4.3水平分片4数据分片设计例2.3设全局关系

SC(S#,C#,GRADE)，S(S#,SNAME,AGE,SEX)

要求：将SC划分为男生各门课成绩和女生的各门成绩。这不可能从SC本身的属性性质来执行选择，必须从关系S的属性性质或水平片段来导出。二、导出水平分片全局关系的导出式水平分片不是以其自身属性性质为基础，而是从另一个关系的属性性质或水平片段推导出来的。确定一方便的导出式水平分片要求确定应用所执行的最重要的结合操作。导出分片可以使片段与片段间“连接”变得更容易。4.3水平分片4数据分片设计按S的属性导出

DefinefragmentSC1

as（DefinefragmentSM

as）

SelectSC.S#,C#,GRADEFromSC,SWhereSC.S#=S.S#andSEX=‘M’DefinefragmentSC2

as（DefinefragmentSF

as）

SelectSC.S#,C#,GRADEFromSC,SWhereSC.S#=S.S#andSEX=‘F’如果S已经进行水平分片，分为SM和SF,分别为男生全体和女生全体，则按S的水平分片（SM/SF）导出：

DefinefragmentSC1asSelect*FromSCWhereS#in(SelectSF.S#fromSM)DefinefragmentSC2asSelect*FromSCWhereS#in(SelectSM.S#fromSF)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(Eno#,NAME,SAL,TEL,MAGNUM,DEPT)，其码为Eno#。主要应用有:

在Sa站点查询

NAME,SAL,TEL;

在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数据分布是指分布式数据库中的数据不是存储在一个站点的计算机上，而是根据需要将数据划分成若干逻辑片段，按某种策略把数据分片所得的逻辑片段分散地存储在各个站点上。数据分布的策略有：集中式、分割式、复制式、混合式。集中式：

所有数据片段都安排在同一站点上。对数据的控制和管理比较容易，数据的一致性和完整性能得到保证。缺点是该站点负担过重，系统对该站点的依赖性过多，容易出现瓶颈，系统可靠性较差。5.1数据分布策略5数据分布设计34分割式：所有数据只有一份，被分割成若干个逻辑片段，每个逻辑片段被指派在某个特定的站点上。可充分利用各个站点上的存储设备，数据的存储量大。各站点可自治的检索和修改数据，发挥系统的并发操作能力。当部分站点出现故障时，系统仍能运行，提高了系统的可靠性。复制式：全局数据有多个副本，每个站点都有一个完整的数据副本。系统可靠性高，响应速度快，数据库恢复也较容易。但是要保持各个站点上数据的同步修改，将要付出高昂的代价。5数据分布设计5.1数据分布策略35混合式：全部数据被分为若干子集，每个子集安置在不同的站点上，但任一站点都没有保存全部的数据，并且根据数据的重要性决定各个子集的副本的多少。

这种分布策略兼顾了分割式和复制式的做法，获得两者优点，但也包含两者的复杂性。5数据分布设计5.1数据分布策略在满足用户需求的前提下,把设计好的数据片段分配到相应的站点上存储，尽可能提高系统的效益。片段分配的主要目的在于使应用执行的远程访问次数最少。例子:Emp(Eno#,Name,Location,Salary)

R1=

loc=SaEmp;R2=

loc=SbEmp

Querya:select…whereLocation=Sa... Queryb:select…whereLocation=Sb…SiteaSitebR1,R2存放在哪??5.2数据片段位置分配的方法5数据分布设计根据应用需求确定是非冗余分配还是冗余分配。在非冗余分配中，每个片段恰好映射到一个站点上；在冗余分配中，每个片段映射到一个或多个站点上；设计者决定每一片段复制程度，复制利益随检索与更新间的比值而增加。分配方法非冗余分配设计方法最佳适应法：对每一种分配都进行估算，然后选择最佳的站点。其他方法冗余分配的设计方法所有得益站点法附加复制法：启发式方法应用需求确定非复制问题的解；确定一组站点分配片段的一个副本。确定非复制问题的解；从最有益处起逐步附加复制的副本，直到附加复制无好处为止。5.2数据片段位置分配的方法5数据分布设计

设F为单个片段，共有m个站点S1,…Sm,变量X1,…,Xm取值如下：

0如果片段F不在站点Sj上存储

1如果片段F在站点Sj上存储则总代价为：

Totalcost=ReadCost+WriteCost+StorageCost

读代价写代价存储代价

确定Xj

的值,1jm,使总代价最小。Xj=5.2数据片段位置分配的方法—分配的简化模型5数据分布设计读代价：

Readcost=

[

tiMINCij

]

i:

读申请源站点；

ti:站点Si上的读申请激活次数；

Cij:

从Si读Sj站点上的片段F的代价。

i=1m...3ici,3ci,1ci,2ti

FFF.12j5.2数据片段位置分配的方法—分配的简化模型5数据分布设计写代价：

Writecost=

XjuiC’iji:写申请源站点

j:被更新站点

Xj:

0如果片段F不在站点Sj上存储 1如果片段F在站点Sj上存储ui:站点Si

上更新激活次数

C’ij:从站点Si更新

Sj

分段F的代价i=1j=1mm....iFFFUpdatesui5数据分布设计5.2数据片段位置分配的方法—分配的简化模型存储代价：

StoreCost=

Xidi

Xi: 0如果片段F不在站点Si上存储

1如果片段F在站点Si上存储di: 站点Si

存储片段F的代价i=1m5数据分布设计5.2数据片段位置分配的方法—分配的简化模型目标函数：确定Xj

的值,1jm,使总代价最小。min

[ti

MINCij

+

Xj

ui

C’ij

]

+

Xidi

ji=1j=1i=1mmm即使最简单的公式也是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在站点j上对片段i的检索频度；

Fkj*Uki:表示应用k在站点j上对片段i的更新频度。5数据分布设计5.3数据片段分配的费用和得益估算最佳适应法（非冗余分配）：

将片段Ri分配到访问片段Ri次数最多的那个站点上。在站点j上片段Ri

的本地访问次数(对全部应用加和)是：

Bij=

kFkj*

Nki

=

kFkj*(Rki+Uki)

(1)估算：max(Bij)=Bij’则片段Ri就分配在站点j’上。5数据分布设计5.3数据片段分配的费用和得益估算—水平分片情况j例：设有一个片段Ri,有两个应用A1,A2

,可能在三个场地分别设定为

Site<1>,Site<2>,Site<3>，并从应用需求分析得到的频度参数为：

应用k=A1：在j=Site<1>上访问频度FA1,<1>*NA1,Ri=60,

在j=Site<2>上访问频度FA1,<2>*NA1,Ri=30,

在j=Site<3>上访问频度FA1,<3>*NA1,Ri=20,

应用k=A2：在j=Site<1>上访问频度FA2,<1>*NA2,Ri=40,

在j=Site<2>上访问频度FA2,<2>*NA2,Ri=50,

在j=Site<3>上访问频度FA2,<3>*NA2,Ri=50.

则计算站点j上片段Ri

的本地访问次数Bij

如下：

当j=Site<1>,

Bij=

k=A1,A2

Fkj*Nki=(60+40)=100,

当j=Site<2>,

Bij=

k=A1,A2

Fkj*Nki=(30+50)=80,

当j=Site<3>,

Bij=

k=A1,A2Fkj*Nki=(20+50)=70,

从计算结果可以得到Bij’=100，j’被选定为Site<1>,也就是说片段Ri

应分配在Site<1>上。5数据分布设计5.3数据片段分配的费用和得益估算—水平分片情况所有得益站点法（冗余分配方法一）：将片段Ri的副本分配到所有得益站点j上。

所有得益站点：指在这些站点上，所有应用的检索访问费用总比从任何一个其他站点发出的所有应用对片段Ri进行更新访问费用要低。初始时使用非冗余分配，确定非冗余问题的解。在每次迭代时，计算因增加一副本使其变成本地检索访问的得益与为了维护该副本一致性所需要的附加远程修改访问的损失之差值。这个数字是个较大的正数时，把该片段的副本存储到这个站点。由此可以确定一组得益站点。

5数据分布设计5.3数据片段分配的费用和得益估算—水平分片情况所有得益站点法（冗余分配方法一）：

估算增加一个副本使其变成本地检索访问的得益与为了维护该副本一致性所需要的附加远程修改访问的损失之差额值：

Bij=

kFkj*Rki

-c*k

j’≠j

Fkj’*Uki(2)其中：

c=更新/检索为度量更新访问费用与检索访问费用之比的一个常数，因更新有大量控制信息和局部操作，所以代价较高，一般c≥1.

通过计算，如果Bij*＞0，则站点j*是得益站点，应把片段Ri分配在所有场地j*上；如果所有Bij<0，把Ri的单一副本放在Bij*为最大的场地上。5数据分布设计5.3数据片段分配的费用和得益估算—水平分片情况附加复制法（冗余分配方法二）：首先确定非冗余问题的解，然后从最有益处起逐步附加复制的副本，此过程直到“附加复制”已无明显好处时结束。这种方法就是典型的启发式方法。由于副本数与可用、可靠不是线性关系，意大利学者S.Ceri曾发表文章提出，可以用一函数β(Di)来估计存放一个Ri新副本在增加系统的可靠性和可用性方面的得益。令Di表示片段Ri的冗余度(副本个数),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数据片段分配的费用和得益估算—水平分片情况rs其他站点tRtRRs网络A1A2AsAtA35数据分布设计5.3数据片段分配的费用和得益估算—垂直分片情况假设把站点r上的关系R垂直分片成两个片段Rs和Rt,并将Rs分配到s站点Rt分配到t站点，然后将应用分组为As,

At,

A1,

A2,

A3,并估算它们的得益情况。估算各个应用分组得益情况如下：

应用组As：自站点s发出只使用Rs,因而是本地应用，节省了一次远程访问，得益：

BAs=

FksNki(kAs)应用组At：自站点t发出,只使用Rt,因而是本地应用，节省了一次远程访问，得益：

BAt=

FktNki(kAt)5数据分布设计5.3数据片段分配的费用和得益估算—垂直分片情况rs其他站点tRtRRs网络A1A2AsAtA3应用组A1:

由站点r发出,原先使用Rt或Rs,现在这些应用需要进行一次额外的远程访问，损失：

BA1=

FkrNki(kA1)应用组A2:由站点r发出,原先使用R(本地访问),现在这些应用需要进行两次额外的远程访问，损失：

BA2=

2FkrNki(kA2)应用组A3:由不同于站点r,s,t的站点发出,它们要访问Rt或Rs这两者的属性,现在这些应用需一次额外的远程访问，损失：

BA3=

FkjNki(kA3,

j≠r,s,t)5数据分布设计5.3数据片段分配的费用和得益估算—垂直分片情况rs其他站点tRtRRs网络A1A2AsAtA3这种分片和分配的得益为：

Bist=BAs+BAt-BA1-BA2-BA3

其中：BAs=FksNki(kAs)BAt=FktNki(kAt)BA1=FkrNki(kA1)BA2=2FkrNki(kA2)

BA3=FkjNki(kA3,j≠r,s,t)这个公式可以用在穷举式“分裂”算法(exhaustive‘splitting’algorithm)中，以确定用试探站点s和t的全部可能组合的方法来把站点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)应用A3含有不在站点r、s或t的应用，它们对I的属性进行更新，而现在也需要同时访问Rs和Rt。可以使用上面的关于Bist的表示公式来评价这种垂直群集方法的得益。5数据分布设计5.3数据片段分配的费用和得益估算—垂直群集情况分布式数据库设计阶段需求分析概念设计分布要求分析设计全局逻辑设计分布设计局部逻辑设计局部物理设计位于概念设计阶段之后进行，主要工作：1.收集用户分布要求信息2.水平分片的划分谓词3.每一应用在各站点激活的频率Fkj全局逻辑设计之后进行，主要工作：1.分布要求和全局逻辑模式作为输入2.形式为全局数据库模式和逻辑访问表3.输出为分片模式和分配模式DATAID-D方法是自顶向下设计分布式数据库的一个典型方法，由意大利米兰工业大学提出，由集中式数据库设计DATAID-1方法论的扩充而得到。

DATAID-1方法有四个阶段：需求分析、概念设计、逻辑设计和物理设计。扩充的DATAID-D对其增加两个阶段：分布要求分析阶段和分布设计阶段。6DATAID-D方法6.1DATAID-D方法概述说明：1.设计数据字典；2.全局数据模式；3.全局操作模式；4.简化全局模式；5.逻辑访问表；6.各站点逻辑模式；7.各站点访问表；8.局部逻辑模式（关系或网状）；9.局部物理模式（关系或网状）全局逻辑设计分布设计局部逻辑设计逻辑设计需求分析概念设计分布要求分析局部物理设计187654329要求频率表划分表极化表6DATAID-D方法6.1DATAID-D方法概述分布要求分析用户分布要求全局数据概念模型全局数据操作模式应用频率表实体访问表应用极化表

分布要求分析的目的是收集以后用于推动分布设计所需要的信息。这一阶段的输入：是用户对分布的要求、全局数据概念模型与全局数据操作模式。建立三种类型的表作为这一阶段的输出：应用的频率表、实体的访问表和数据与应用的极化表(polarization)。6DATAID-D方法6.2分布要求分析阶段分布要求分析阶段应用频率表：给出各站点j上每一个应用k激活的次数Fkj（假设所有应用在所有站点上都能执行；当一个应用在一个站点上从不执行时，相应位置的频率项为零）。实体访问表：可用于模式中各实体的潜在水平分片规则。每条分片规则指明引入水平分片的可能理由，并与在一给定站点访问一给定数据子集的一个或多个应用有关。应用极化表：基于定量分析方法来说明分片如何影响着应用处理的本地性。一个极化表指明由一个站点j发出一个给定应用k访问一个给定片段i

的频率Pkji。6DATAID-D方法6.2分布要求分析阶段分布设计全局数据模式实体逻辑访问表分布要求站点逻辑模式站点逻辑访问表分布设计的目的是把全局数据模式、实体逻辑访问表和分布要求做为输入，将数据分配在站点上。分布设计阶段输出：各站点的逻辑模式和站点逻辑访问表。在以后的局部逻辑设计阶段和在各站点上独立进行的物理设计阶段，要使用这些逻辑模式和逻辑访问表。6DATAID-D方法6.3分布设计阶段DATAID-D的分布设计分成四个阶段：分片设计阶段；非冗余分配阶段；冗余分配阶段；局部模式的重新构造阶段。6DATAID-D方法6.3分布设计阶段一、分片设计阶段：分片设计对实体进行水平分片和垂直分片，以便为以后设计阶段确定可能的分配单位。要使每一个片段i是一个合适的分配单位，就必须保证由各站点j上执行的各应用k，大约以同一方式(即相同频率)访问片段中的实例(元组)。存在一个阈值条件，超过这一阈值，进一步分片行不通。分片设计主要包括逻辑判定。进行逻辑判定时，从极化表中选择某些谓词，并用它们定义逻辑片段。6DATAID-D方法6.3分布设计阶段二、非冗余分配阶段：非冗余分配的执行是把各片段i映射到使用最多的站点j上。根据频率表与极化表，采用“最佳适应法”，可得到从一给定站点j访问一个给定片段i次数的定量测度，从中选出该片段的定位站点。在该站点发出的所有应用事务k上，求极化值Pkji与该片段所使用的频率Fkj之积的和，可以得到各片段在每一站点上可能的使用频率。有可能识别最频繁访问该片段的站点，将该片段分配到这一站点上。令：Fkj表示应用k使用站点j的频率；

Pkji表示应用k使用站点j访问片段i的极化值(即频率)。于是，全部应用k从站点j访问片段i的次数给出如下：

Nij=

kFkj*Pkji

因此，片段i被分配到站点j’,使得Nij’=max所有jNij

6DATAID-D方法6.3分布设计阶段三、冗余分配阶段：冗余分配的执行是使用“贪婪”启发式，可采用“所有得益站点法”或采用“附加复制法”。初始使用非冗余分配，在每次迭代时，计算因增加一个副本使其变成本地检索访问的得益与为维护该副本的一致性所需要的附加远程修改访问的损失之差值。这个数字是个较大的正数时，把该片段的副本存储到这些得益站点上，有理由说明增加冗余度的必要性，否则就不增加。6DATAID-D方法6.3分布设计阶段四、局部模式重新构造阶段：局部模式的重新构造是重新构造片段分配站点上的局部模式。这一阶段也负责E-R全局模型中的联系分配。大多数联系是作为对应实体标识符间的结合实现的。DATAID-D方法建议把联系放置在具有最大基数性的实体或片段的站点上，使得必须传送的实体标识符尽可能少。6DATAID-D方法6.3分布设计阶段本飞机订票系统维护一个分布在三个站点上的数据库。在美国开业的一家公司，有三个站点即机场1、2、3.其中：站点1：丹佛机场（代码CO）；站点2：纽约机场（代码NY）；站点3：亚特兰大机场（代码GA）；数据库存储数据内容如下：机场有关规程；班机调度及班机可用情况；旅客订票情况；订票系统共有三个应用：订票应用；登记应用；起飞应用。7实例研究：飞机订票系统7.1实例研究简述班机订票从到机场登记旅客到达时间机号日期可用座位起飞时间符号城市进入口座位图延期区域安全规则种类座位号检查行李名字电话权力7实例研究：飞机订票系统7.1实例研究简述-飞机订票系统数据库的全局数据模式种类[w]电话[w]240机场320000班机日期[k]起飞时间[k]符号[k]从可用座位[o、w]到到达时间[k]名字[w]1100000旅客订票

每当一新的旅客想预定一个班机的机票时，订票应用就被激活。1.实体左下角和右下角的数字表示：示例总数和应用选择的平均示例数。2.访问数据库中①起飞与到达机场;②起飞与到达时间;③班机日期.

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

40机场日期[k]符号[k]起飞时间[k,o]班机号[o]从到出入口[o]延期[o]城市[o]符号[o]到达时间[k,o]从机场起飞时的应用，产生描述即将离开机场的30架班机的起飞信息的报告并显示在TV监视器上。激活起飞应用。1.根据数据库中①机场符号;②当前日期;③起飞时间;④到达时间,

查明①班机号、②起飞时间、③出入口、④延期、⑤目的地机场符号、⑥目的地城市，然后显示在TV监视器。7实例研究：飞机订票系统7.1实例研究简述-飞机订票数据库的起飞应用全局操作模式属性操作a（订票）b（登记）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)实体访问表：旅客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)联系访问表：登记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实例研究：飞机订票系统7.2飞机订票系统中的分布要求分析1.两种方法导出划分班机实体：应用不同的联系“从”(起飞机场)或“到”(到达机场)和基于已把机场划分成区域来划分班机实体。使用两个不同联系于同一基本划分，产生两种不同导出划分，如下表前两行。2.下表最后两行给出了导出划分旅客实体的两个方法：依据联系订票和班机，按班机起飞区域或第一订票地点划分。在这种情况下，导出机制分两步，因为它从机场作用到班机，然后从班机作用到旅客。前一种情形，依据他们第一次订票的班机的地点来划分旅客；后一情形中，依据他们各次的订票的班机起飞区域来划分旅客。7实例研究：飞机订票系统7.2飞机订票系统中的分布要求分析

导出划分表的注释表说明了七种可能情形：旅客可能预定只离开一个区域(A,B,C)的班机，或离开两个区域(AB,BC,AC)的班机，或离开所有区域(ABC)的班机。由于订票是一种多对多关系，所以需要以上七种情况(考虑往返机票)。7实例研究：飞机订票系统7.2飞机订票系统中的分布要求分析极化表a订票b登记c起飞1丹佛2纽约3亚特123123按区域划分机场P180×100P21075×100P31080×100按出发机场划分航班P17010080P27510080P37010080...……………………

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