厦门大学计算机科学系研究生课程 《分布式数据库技术》 分布式数据库技术 专题二 数据分布 专题二 数据分布 林子雨 厦门大学计算机科学系 分布式数据库技术 专题二 数据分布 专题二 数据分布 林子雨 厦门大学计算机科学系 E-mail: ziyulin@xmu.edu.cn 厦门大学计算机科学系 2011年10月

专题二 数据分布 第3章 数据分布 3.1 数据分布概念 3.2 数据划分原则及分片方法 3.3 数据分配原则及方法 第3章 数据分布 3.1 数据分布概念 3.2 数据划分原则及分片方法 3.3 数据分配原则及方法 3.4 数据分布结构模式定义

3.1 数据分布概念 3.1.1. 分布式数据库设计的任务 3.1.2. 数据分布概念 3.1.3 集中式数据库的关系模式及形式化定义 3.1.1. 分布式数据库设计的任务 3.1.2. 数据分布概念 3.1.3 集中式数据库的关系模式及形式化定义 3.1.4. 分布式数据库的模式定义

3.1.1 分布式数据库设计的任务 （1）数据库设计 数据库设计是指：对于一个给定的应用环境，构造最优的数据库模式，建立数据库及其应用系统，使之能够有效地存储数据，满足各种用户的应用需求（信息要求和处理要求）。

3.1.1 分布式数据库设计的任务 （2）分布式数据库设计的任务 分布式数据库设计包含以下任务： 定义全局数据库的概念模式 设计分片 3.1.1 分布式数据库设计的任务 （2）分布式数据库设计的任务 分布式数据库设计包含以下任务： 定义全局数据库的概念模式 设计分片 设计片段的分配 设计物理数据库，将概念模式映射到存储区域，并确定适当的存储方法 在分布式数据库设计过程中，必须考虑分布式数据库应用的需求，包括：应用提交的场地、应用执行的频度、每个应用所存取数据的类型、次数及统计分布等信息 应该明确分布式数据库系统设计的基本策略：从顶向下的设计处理或者从下向上的设计处理

3.1.2 数据分布概念 数据分布的概念 逻辑上将全局概念模式（即全局关系模式），划分成若干逻辑片段（子关系）；再按一定的冗余度将片段分配到各个节点上，这时逻辑片段就成为具体的物理片段。

3.1.3 集中数据库的关系模式及形式化定义 （1）关系 为了讨论分布式数据库的模式定义，首先复习相关知识点。 定义3.1：域是一组具有相同数据类型的值的集合。用{ }表示。 定义3.2：给定一组域D1，D2，…，Dn，这些域中，可以有相同的。其中 D1，D2，…，Dn的笛卡儿积为： D1×D2 × … × Dn = {（ d1, d2 , …, dn）| di∈ Di，i=1, 2, … , n } 其中每一个元素（ d1, d2 , …, dn）叫做一个 n 元组（或元组）， 元素中的每一个值di叫做一个分量 笛卡儿积的基数为|D1|×|D2 |× … × |Dn | 定义3.3： D1×D2 × … × Dn的子集叫做在D1，D2，…，Dn域上的关系，表示为： R（ D1，D2，…，Dn） 其中 ，R表示关系名，n是关系的目（或称为度）。

3.1.3 集中数据库的关系模式及形式化定义 笛卡尔积可表示为一个二维表。表中每行对应一个元组，表中的每列对应一个域。 例1：给出三个域： D1 =导师集合SUPERVISOR=张清玫，刘逸 D2 =专业集合SPECIALITY=计算机专业，信息专业 D3=研究生集合POSTGRADUATE=李勇，刘晨，王敏 则D1 ，D2，D3的笛卡尔积为： D1×D2×D3={（张清玫，计算机专业,李勇），（张清玫，计算机专业，刘晨）， （张清玫，计算机专业，王敏），（张清玫，信息专业，李勇）， （张清玫，信息专业，刘晨），（张清玫，信息专业，王敏）， （刘逸，计算机专业，李勇），（刘逸，计算机专业，刘晨）， （刘逸，计算机专业，王敏），（刘逸，信息专业，李勇）， （刘逸，信息专业，刘晨），（刘逸，信息专业，王敏）} 其中（张清玫，计算机专业，李勇）、（张清玫，计算机专业，刘晨）等都是元组。张清玫、计算机专业、李勇、刘晨等都是分量。

3.1.3 集中数据库的关系模式及形式化定义 该笛卡尔积的基数为2×2×3=12，也就是说，D1×D2×D3一共有2×2×3=12个元组。这12个元组可列成一张二维表，如下： D1，D2，D3的笛卡尔积 SUPERVISOR SPECIALITY POSTGRADUATE 张清玫 刘逸 计算机专业 信息专业 李勇 刘晨 王敏

3.1.3 集中数据库的关系模式及形式化定义 定义3.3说明： 若关系中的某一属性组的值能唯一地标识一个元组，则称该属性组为侯选码。 若一个关系有多个侯选码，则选定其中一个为主码（Primary Key）。主码的诸属性称为主属性（Prime attribute）。 不包含在任何侯选码中的属性称为非码属性（Non-key attribute）。 在最简单的情况下，侯选码只包含一个属性；在最极端的情况下，关系模式的所有属性组是这个关系模式的侯选码；上述称为全码（All-key）。 关系是一个二维表，表的每行对应一个元组，表的每一列对应一个域。

3.1.3 集中数据库的关系模式及形式化定义 （2）关系模式 （3）关系数据库 定义3.4：关系的描述称为关系模式。它可以形式化地表示为： R（U，D，dom，F） 其中：R 为关系名， U 为组成该关系的属性名集合， D 为属性组U中属性所来自的域， dom 为属性向域的映象的集合， F 为属性间数据的依赖关系集合。 （3）关系数据库 定义3.5：在一个给定的应用领域中，所有实体及实体之间联系的关系 的集合构成一个关系数据库。

3.1.4 分布式数据库的模式定义 3.1.4.1 全局关系模式及关系 3.1.4.2 DDB中的三种关系 3.1.4 分布式数据库的模式定义 3.1.4.1 全局关系模式及关系 3.1.4.2 DDB中的三种关系 3.1.4.3 DDB中的三种数据库 3.1.4.4 分片模式（FS）定义 3.1.4.5 分配模式（AS）定义 3.1.4.6 关系的分布结构 S 3.1.4.7 组合关系

3.1.4.1 全局关系模式及关系 关系和关系模式有以下关系： 3.1.4.1 全局关系模式及关系 全局关系模式是一个多元组，表示为：R（U，D，dom，I，F，Q，S），其中： R是关系名； U是组成R的有限属性集； D是U中属性的值域； dom是属性列到域的所有映射的集合； I 是一组完整性约束条件； Q是关系所满足的限定条件（谓词）； F是属性间的一组数据依赖； S是关系的分布结构。 一个关系r是相应于全局关系模式R（U，D，dom，I，F，Q，S）按分布结构S组织起来的从属性集U到值域D上所有满足Q的映射的集合。其中，每个元素称为元组；每个关系有主键 。 关系和关系模式有以下关系： 关系模式描述关系的结构及语义约束，对于全局关系模式，同时还具有按一定谓词条件Q划分成子关系（局部关系）模式和子关系物理存储模式的约束 关系是关系模式在某一时刻的“当前值” 全局关系被划分以后，按分布结构组成子关系，以呈现现实世界某一时刻的状态。所有关系的当前值就是关系数据库 为了把问题集中于数据分布，可以把全局关系模式简化成R（U，Q，S）

3.1.4.2 DDB中的三种关系 全局关系：当一个关系R（U，Q，S）称为全局关系（GR），是指在分布式数据库系统中对用户是可见的，实际上是由若干子关系的逻辑片段和物理片段按分布结构S组成，具有Q=TRUE，S≠Ø的特点，且GR是虚拟的。 逻辑片段：当一个关系R（U，Q，S）称为逻辑片段，是指这个关系在DDB中是实际存在的关系，不需要由其它关系组成，因而它是基本关系，即是构成DDB的实体。它是全局关系在某个场地上的子关系的逻辑成分，所以逻辑片段可简称为GR的逻辑关系，而全局关系与逻辑关系间有一定的映射，用分片模式定义，它们之间的映射性质为 1：n 。 物理片段：当一个关系R（U，Q，S）称为物理片段，是指这个关系是在某一场地上的逻辑片段，即是在某场地上的基本关系，其特点是S=Ø。|物理片段由分配模式定义。逻辑片段映射为某个场地上的物理片段，亦可称为某个场地的副本，或直接称物理关系，其映射有 1：1 和 1：n性质（因而一个逻辑关系可以对应一个物理关系，也可对应多个物理关系）。 结论： 一个全局关系由分片操作（分片模式定义）分解成多个逻辑关系；一个逻辑关系在几个场地上放置副本（分配模式定义）就产生几个物理关系。这些分片信息和分配信息构成了全局关系的分布结构S。

3.1.4.2 DDB中的三种关系 问题：DDB三种关系分别属于哪一层？ 集 中 式 三 层 摸 结 构 图 分 布 式 四 层 摸 结 构

3.1.4.3 DDB中的三种数据库 全局（虚拟）数据库：由所有全局关系组成的数据库称为全局（或虚拟）数据库GDB。 逻辑数据库：由所有逻辑片段（基本关系）组成的数据库称为逻辑数据库LgDB。 物理数据库：由所有物理关系组成的数据库称为物理数据库PDB。 三种数据库之间的关系可表示如下： 分片模式 分配模式 GDB LgDB PDB 当用户查询或更新操作分布式数据库时，只是对虚拟的全局数据库操作，它并不实际存在，而是由若干“片段”组成的（由若干片段的并行操作和自然联接操作实现的），这些片段映射为一个“物理关系”存在于物理数据库中。 三种数据库是通过分片模式定义和分配模式定义联系起来的。

3.1.4.4 分片模式（FS）定义 分片模式FS定义为一组操作，它将GDB中每个GR分解成LgDB中的片段，即： FS（GDB）= LgDB 这种操作还应具有可逆性，这是分布式数据库系统的基本要求： FS-1（LgDB）＝GDB

3.1.4.5 分配模式（AS）定义 分配模式定义为一组操作，它将LgDB中每个逻辑关系映射到PDB中的一组物理关系上，即： 分配模式的逆操作含义是，从PDB中选择出适当的物理关系作为逻辑关系，从而构成LgDB，即有： AS-1（PDB）=LgDB。

3.1.4.6 关系的分布结构S 关系R（U，Q，S）的分布结构S是有关R被划分和分配的信息的集合 如果R是物理关系，那么它无需划分和分配，因此S=Ø 如果R是逻辑关系，那么它还需分配场地，因此S记载R的分配信息 如果R是全局关系，那么S记载了R如何分解成逻辑关系和物理关系

3.1.4.7 组合关系 在全局关系与逻辑关系之间，事实上还存在若干关系，我们可称它为中间关系。只是起过渡作用。用组合关系表示。 3.1.4.7 组合关系 在全局关系与逻辑关系之间，事实上还存在若干关系，我们可称它为中间关系。只是起过渡作用。用组合关系表示。 组合关系R（U，Q，S）是由若干逻辑关系和物理关系按分布结构S组成的关系。它可以是全局关系，或者也可以是中间关系。基本特点为S≠Ø。

3.2 数据划分原则及分片方法 3.2.1 分片操作原则 3.2.2 分片操作 3.2.3 分片操作的正确性

3.2.1 分片操作原则 （1）数据划分的基本思路：首先按DDB外部特征划分数据，然后根据DDB的内部特征，提出应遵守的基本原则以检验数据划分的正确性。 所谓“外部特征”是指构成DDB的属性群集特性，包括属性值集和数据项集等。 例1：某公司数据库中有部门关系Dept，便于管理可按部门性质或部门所在地将部门关系Dept划分成若干片段（如部门号DNO，或部门所在地区AREA的属性值集划分）。这是一种按属性值集的划分。 例2：而上述数据库中有职员关系Emp，通常可按业务管理性质将Emp的属性组合值集划分（如财务部门对税收TAX、工资SAL等属性项有兴趣，行政部门对Emp承担工作业务的属性项有兴趣等）。这是按数据项集划分。 内部特征是指DDB的组成性质。 （2）基本原则：当对DDB划分后，仍应保持DDB原有的特质，所以划分后的各逻辑关系之间应遵守下列原则： 完整性原则、重构性原则、不相交原则

3.2.2 分片操作 3.2.2.1 水平分片 3.2.2.2 垂直分片 3.2.2.3 混合分片 3.2.2.4 诱导分片 3.2.2.1 水平分片 3.2.2.2 垂直分片 3.2.2.3 混合分片 3.2.2.4 诱导分片 3.2.2.5 四种分片操作的统一表示

3.2.2.1 水平分片 水平分片是将关系按行横向以某些条件划分成元组的子集，（即：满足条件的记录的集合）每个子集含有一定的逻辑意义，称逻辑片段。 定义1：组合关系R（U，Q，S）上的水平分片（H）是一操作，它将R按照一组给定的谓词 P1，P2，…，Pn，划分成一组关系模式： R1（U1，Q1，S1），…，Rn（Un，Qn，Sn） 满足：1）U1＝U2＝…＝Un＝U； 2）K1＝K2＝…＝Kn＝K； 3）Qi＝Q Pi； 4）Si ≠Ø 其中：i，j∈{l，…，n}，Pi Pj=Ø， Pi=True，记为： R（H）<P> = { R1，…，Rn } 式中P={P1，…，Pn}。 由定义可得出：水平分片实际上是关系的选择操作。即属性=“值”的具体条件的子关系Ri，因此片段可用σq(R)表示。

3.2.2.1 水平分片 例1：供应商全局关系Supplier（SNO，SNAME，SCITY）按供应商所在地SCITY 属性值划分。假设只有两个城市London和Paris，则按上述定义，其水平分片为： Supplier1＝σscity＝‘London’（Supplier） Supplier2＝σscity＝‘Paris’（Supplier）

3.2.2.2 垂直分片 垂直分片是将关系按列纵向以属性组划分成若干片段。在垂直分片时，为了保证片段的重构性，应将“键属性”属于各个片段中（放松的不相交性）。 定义2：组合关系R（U，Q，S）上垂直分片（V）是一操作，它将R按照一组给定的属性A1，…，An划分成一组关系模式： R1（U1，Q1，S1），…，Rn（Un，Qn，Sn） 满足：1）K1=K2=…=Kn=K； 2）Ui=Ai； 3）Q1=Q2=…Qn=Q； 4）πk1（R1）=πk2（R2）=…=πkn（Rn）= πk（R）； 5）Si≠Ø 其中：i，j∈{ 1，…，n }， Ai U, Ai∩Aj =K，∪Ai =U 记为：R（V）<A>= { R1，…，Rn} 式中A= { A1，…，An } 由定义可得出，关系的垂直分片实际上是对指定属性集上的投影操作。所以，R关系的垂直分片片段是R的部分属性组合子关系Ri，可用πＡi(R)表示，其中K Ai。

3.2.2.2 垂直分片 例２：职员关系Ｅmp（ENO,ENAME,SAL,TAX,MGRSSN,DNO）划分成两个子关系：一个包括财务信息，对SAL,TAX属性感兴趣；一个包括工作信息，对ENO,ENAME,MGRSSN,DNO属性感兴趣。为了保证划分后重构，可将ENO作为公共属性分别包括在二个片段中。这样Emp可划分： Emp1=πENO,SAL,TAX（Emp） Emp2=πENO,ENAME,MGRSSN,DNO（Emp）

3.2.2.3 混合分片 混合分片是水平分片和垂直分片的内部混合。 定义3：组合关系Ｒ（U，Q，Ｓ）上的混合分片（M）是一操作，它将关系按照一组属性A1 ,…, An和一组谓词P1 ,…,Pn划分成： Ｒ1(U1,Q1,S1)，…，Ｒn(Un,Qn,Sn,) 满足：1）Ui= Ai 2）K1=K2=…=Kn=K; 3）Qi=Q∧Pi; 4）Si≠Ø。 其中：i，j∈{l，…，n}，Ai U，Ai∩Aj =K，∪Ai =U，Pi Pj=Ø， Pj=True，记为： R (M)<AP> = { R1, …,Rn } 式中AP= { <Ai,Pi> | i=1,…,n } 。 上述定义说明混合分片是水平分片和垂直分片的混合操作，即对关系的选择和投影。当要重构混合分片的各片段，可按相应次序做合并（UNION）操作和联接（JOIN）操作。

3.2.2.3 混合分片 例3：将例2的Emp划分成Emp1,Emp2后，对Emp2可按部门号DNO=1、DNO=3分在一个片段，而DNO=2在另一片段，则Emp可划分为： Emp1=πENO，SAL，TAX（Emp） Emp2=σDNO=“D1”or DNO=“D3” (πENO,ENAME,MGRSSN,DNO Emp) Emp3=σDNO=“D2”(πENO,ENAME,MGRSSN,DNO Emp)

3.2.2.4 诱导分片 一个关系的分片不是基于关系本身的属性，而是根据另一个与其有关联性质的关系的属性来划分。这种划分是只基于水平分片的诱导 定义4：组合关系R（U,Q,S），按另一个组合关系T （T是已经水平分片成T1（U1，Q1，S1）,…，Tn（Un,Qn, Sn） ）在公共属性A上的诱导分片（DH）是一操作，它将R划分为： R1（ ） ,…, Rn（ ） 满足： 1） 2） 3） 4） 5）S’i≠Ø 记为：R（DH）<T>= { R1，…，Rn } 式中：T= { T1，…，Tn } 诱导分片是一种相关分片操作，它是一种半联接操作 诱导分片实例

3.2.2.4 诱导分片 关于半联接操作 关系代数操作中的联接（JOIN）操作包括θ-联接和自然联接 半联接操作是关系代数操作中联接（JOIN）操作的一种缩减：关系R和S的半联接记为R∝S，其结果关系是R和S自然联接（Natural JOIN）后在R的属性上的投影，可用下述表达式表示： R∝S=πR（R∞S）（实例） 计算R∝S的另一种等价的方法是：将S中与R有相同属性名的属性集投影出来，然后与R完成自然联接 半联接操作是一种不对称操作，即R∝S≠S∝R 在分布式数据库的查询优化中，常常用半联接操作实现联接操作的操作数（关系）的缩减（归约）

3.2.2.4 诱导分片 自然联接的结果是在 R 和 S 中的在它们的公共属性名字上相等的所有元组的组合。例如下面是表格“雇员”和“部门”和它们的自然联接: 图 自然联接实例

3.2.2.4 诱导分片 θ-联接（等值联接是它的特例） 如果我们要组合来自两个关系的元组，而组合条件不是简单的共享属性上的相等，则有一种更一般形式的联接算子才方便，这就是 θ-联接(或 theta-联接)。θ 是在集合 {<, ≤, =, >, ≥} 中的二元关系。θ的结果由在 R 和 S 中满足关系θ 的元素的所有组合构成。只有 S 和 R 的表头是不相交的，即不包含公共属性的情况下，θ-联接的结果才是有定义的。 实例：考虑分别列出车模和船模的价格的表“车”和“船”。假设一个顾客要购买一个车模和一个船模，但不想为船花费比车更多的钱。在关系上的θ-联接 CarPrice ≥ BoatPrice 生成所有可能选项的一个表。 图 θ-联接实例

3.2.2.4 诱导分片 半联接的结果只是在 S 中有在公共属性名字上相等的元组的所有 R 中的元组。 实例：“雇员”和“部门”和它们的半联接的表: R∝S=πR（R∞S） R S Manager Harriet Charies 半联接结果 图 半联接实例 自然联接结果

3.2.2.4 诱导分片 例4：设供应关系Supply(SNO,PNO,QTY)，它的划分要求按供应商所在地SCITY属性值划分。 分析：虽然SCITY不是Supply关系的属性，但Supply是Supplier与另一个零件关系Part的关联（这种关联描述了供应商供应零件的细节）。Supply与Supplier和Part分别通过SNO和PNO建立联系，就Supply与Supplier而言，SNO是它们的公共的属性，充当Supply的外键（foreign key）。所以，Supply的划分可以通过公共属性SNO实现，在SCITY属性值上完成水平诱导划分。这时，SCITY属性称为Supply的诱导属性。

3.2.2.4 诱导分片 前例已有：Supplier1=σSCITY=’London’Supplier Supplier2=σSCITY=’Paris’Supplier 通过半联接操作实现对Supply的划分，则 Supply1=Supply ∝ Supplier1 Supply2=Supply ∝ Supplier2 根据半联接表达式，则上式分别为： Supply1=πSNO,PNO,QTY(Supply∞(σSCITY=‘London’Supplier)) Supply2=πSNO,PNO,QTY(Supply∞(σSCITY=‘Paris’Supplier)) 从式中可看出：Supply诱导水平分片的谓词有两部分，一部分是它与关联关系的公共属性；另一部分是它应满足的关于诱导属性的谓词。可表示为： Q1：Supply.SNO=Supplier. SNO and SCITY=‘London’ Q2：Supply.SNO=Supplier.SNO and SCITY=‘Paris’ [注：R∝S=πR（R∞S）]

3.2.2.4 诱导分片

3.2.2.5 四种分片操作的统一表示 四种分片操作可以用一个统一的形式描述： R（Oj），<C>={R1，…，Rn} 其中，Oj∈{ H,V,M,DH }, C= { C1,…，Cn }。 当Oj=DH时，Ci表示关系； 当Oj≠DH时，Ci={<Ai,Pi>|如果Oj=H,则Ai=U；如果Oj=V，则Pi=True}。 操作的作用是将组合关系R（U,Q,S）按操作Oj分解成一组满足条件的片段（子关系）：R1（U1,Q1,S1），…，Rn(Un,Qn,Sn)，其中， 当Oj ≠ DH时， Ui=Ai，Ki=K, Qi=Q∧Pi ，Si ≠ Ø，i=1，…，n； 当Oj=DH时，Ui=U, Ki=K, Qi=Ci， Si ≠ Ø，i=1，…，n。

3.2.3 分片操作的正确性 四种分片操作均是建立在关系代数基础上的。一个关系经过选择操作分成若干子关系，子关系间遵守三个内部特征原则。 一个关系经过投影操作划分成若干子关系，它们共享关系的主键属性，且相交属性只允许是主键。这种划分后的内部特征的检查如下： 完整性检查：垂直分片定义中已定义了子关系属性项，并是关系的属性项（∪Ai=U），即不会出现游离的属性项； 重构性检查：将子关系做自然联接则还原成关系； 不相交性检查：对于垂直分片是允许在键属性上相交。 一个关系的混合分片的检查，实际上是重复上述两种分片的检查。两个关系间的诱导分片的检查，主要是对半联接作的检查，半联接操作是一种基于关系基本操作的导出操作（选择、投影、联接的复合操作）。

3.2.3 分片操作的正确性 例1：检查Supplier被水平划分成Supplier1和Supplier2两个子关系的分片正确性。 完整性检查：选择操作包括了所有 SCITY值，即不出现游离的元组项； 重构性检查：将两个子关系做并操作还原为原来的Suppler关系； 不相交性检查：选择操作的两个谓词为： Q1：SCITY=‘London’， Q2：SCITY=‘Paris’， 它们之间是互斥的，所以片段中不存在相同的元组项

3.3 数据分配原则及方法 3.3.1 数据分配的一般准则 3.3.2 分配操作定义 3.3.3 分配操作方法

3.3.1 数据分配的一般准则 集中型评估 分割型评估 全复制型评估 混合型评估 上述三种的综合设置，考虑更新/检索比 分配 4 种类型：集中型、分割型、全复制型、混合型 评估 4 个因素：存储代价、可靠性、检索代价、更新代价 评估分析 集中型评估 分割型评估 全复制型评估 混合型评估 上述三种的综合设置，考虑更新/检索比 - 没有片段间 的通讯； - 存储代价没有额外开销； - 可靠性差； - 检索代价猛增； - 没有同步更新的开销。 存储代价没有增加 可靠性比集中型好 没有通讯代价问题 不存在副本同步更新 可靠性好 存储代价剧增 - 检索代价随更新同步机制而变化（分析集中式更新同步技术和全局锁技术的检索代价与更新复杂性） 数据分配一般准则： 处理局部性 数据的可用性和可靠性 工作负载分布的均匀性

3.3.2 分配操作定义 定义1： 对于逻辑片段R（U，Q，S）的分配操作（AO），是将R分配到一组场地r1，…，rn上，使得每个ri上有一个相应的物理关系 Rri（Uri，Qri，Sri），满足： Uri=U； Qri=Q； Sri=Ø。 记为： R(AO)〈r〉= { Rr1, Rr2…Rrn}， {r=r1, …, rn }

3.3.3 分配操作方法 总体思路和参考方法： 利用大量的性能测试和“应用”优化。即：分别根据需求，使用以下三种方法求出收益值，分析最佳分配。 方法1：非冗余分配“最佳”法 方法2：冗余分配“选择所有收益场地法” 方法3：冗余分配“添加副本”法

3.4 数据分布结构模式定义 3.4.1 概述 3.4.2 用分解树理论讨论分布结构的定义 3.4.3 数据分布模式定义

3.4 用分解树理论讨论分布结构的定义 3.4.1 概述 全局关系模式： R（U，D，dom，I，F，Q，S） 或简化成： R（U，Q，S）， 其中，S是关系的分布结构 ，是有关R被划分和分配的信息的集合。 如果R是全局关系，那么S记载了R如何分解成逻辑关系和物理关系； 如果R是逻辑关系，那么它还需分配场地，因此S记载R的分配信息； 如果R是物理关系，那么它无需划分和分配，因此S=Ø； 本节讨论如下要点： 如何将分片和分配的信息在一个分布结构S中进行描述 表示“数据分布的模式定义”的语句格式，即以语句格式表现数据分布的实际操作

3.4 数据分布结构模式定义 3.4.2 用分解树理论讨论分布结构的定义 3.4.2.1 分布结构的粗定义 3.4.2 用分解树理论讨论分布结构的定义 3.4.2.1 分布结构的粗定义 3.4.2.2 关于独立分片的分解树定义 3.4.2.3 包含相关分片的分解树定义 3.4.2.4 包含分配操作的分解树定义

3.4.2.1 分布结构的粗定义 定义1：一个分布结构是一个有向图G=（V，E，L），其中： 1） V是节点集：每个节点由关系模式和在相应关系上的操作所组成，用Ri(Ui,Qi,Si)(Oj)表示； 2） E是边集：如果有任意分片操作R（Oj）<C>={R1,…，Rn}，则有从节点R（U,Q,S）（Oj）到R1（U1,Q1,S1）(O1),…，Rn（Un,Qn,Sn）(On)的n条有向边[R（R,Q,S）（Oj），Ri（Ui,Qi,Si）(Oi)],每条边上有符号Ci，i=1,2,…，n。 3） L是符号集：它由所有边上的Ci所组成。 如果一个分布结构是一棵树，就称它为分解树。

3.4.2.1 分布结构的粗定义 图 分解树结构

3.4.2.2 关于独立分片的分解树定义 定理1：在分解树中对任一符号为Ci=<Ai,Pi>的有向边 [R（U,Q,S）(O)，R’（U’,Q’,S’）(O’)] ,都有： Q’=QΛPi，U’=Ai，K’=K 。 定理2：在分解树中，设任意两节点R0(U0,Q0,S0)(O0)到Rf(Uf,Qf,Sf)(Of)间的所有边上的符号为 ,有： 1） 2） 3） 4） 为根节点的子树.

3.4.2.2 关于独立分片的分解树定义 定义2： 分解树是一棵树T=（V，E），其中： 1）V是节点集：每个节点结构为Ri (Ui,Qi,Si)(Oj)，Qi是一谓词，Oj表示操作集{H，V，M}，对于根节点，有Qi=True，Si=T; 2）E是边集：对于任一独立分片操作，R（Oj）<C>={R1，…，Rn}，其中，C={C1，…，Cn}，Ci=<Ai,Pi>,（i=1,…,n）。则在分解树中，有节点R（U,Q,S）(Oj)到Ri(Ui,Qi,Si)( )的边，其中，i=1,…,n，且Ui=Ai，Ki=K， Qi=Q∧Pi 。 这个定义就是非常重要的独立分片的分解树定义

3.4.2.3 包含相关分片的分解树定义 定义3： 分解树是一棵树 ，其中： 1）V是节点集：每个节点结构为 是一谓词或是关系名， 表示操作集 根节点 2）E是边集：对于任一分片操作 如果， ，在分解树中有从节点 到Ri(Ui,Qi,Si)(Oj’ )的， 且Ui=Ai，Ki=K，Qi=Q∧Pi； 如果 ，那么 一定是关系名，这时 ，在分解树T中有从节点 到节点 的几条边， 且对每个 ，有

3.4.2.4 包含分配操作的分解树定义 定义4： 分解树是一棵树 ，其中： 1）V是节点集：每个节点结构为 其中， 是一谓词或是关系名或场地名， 表示操作集 对于根节点，有 2）E是边集：对于任一分片操作 如果Oj∈{H,V,M}，则有 ，在分解树中有从节点 到Ri(Ui,Qi,Si)(Oj’ )的边， 且Ui=Ai，Ki=K，Qi=Q∧Pi； Si=以Ri(Ui,Qi,Si)(Oj’ )为根的子树， 如果Oj∈{DH,空}，那么 在分解树T中有从节点 到节点 的边， 且对每个 ，有 （注：“空”时， Qi 表示场地名）

3.4 数据分布模式定义 3.4.3 数据分布模式定义 DDB的数据分布在四层模式中属全局概念层的描述，它是分布式数据库的整体抽象，也是分布式数据库与集中式数据库抽象的最特殊的一点。这里讨论描述全局概念层中关于数据分布的模式定义语句，而四层模式中其它三层的模式定义与集中式数据库类似。 在全局概念层中，有全局概念模式、分片模式、分配模式三种模式。所以，对全局层模式定义语句应包括这三方面的描述，语句的词法和语法视设计的风格而定。本课程采用武汉大学数据库研究组研制的WDDBS的L-SQL*语言。

3.4 数据分布模式定义 例6 有例2的职员关系Emp，将它按例3所示混合分片划分Emp时，用L-SQL*语句如下书写： Create Table Emp (ENO n 4 ENAME c 12 SAL n 5 TAX n 4 MGRSSN n 8 DNO n 2) Key ENO Fragment aa=Emp (ENO,ENAME,MGRSSN,DNO) Emp1=Emp (ENO, SAL, TAX) Emp2=aa (DNO=”1” or DNO=”3”) Emp3=aa (DNO=”2”) Site Empl(1,2) Emp2(1) Emp3(2)；

3.4 数据分布模式定义 例7 给出例1和例4的分片及分配模式定义语句 例7 给出例1和例4的分片及分配模式定义语句 Create talbe Supplier (SNO n 4 SNAME c 12 SCITY c 10) Key SNO Fragment Supplier1=Supplier(SCITY=’London’) Supplier2=Supplier(SCITY=’Paris’) Site Supplier1 (1) Supplier2(2,3)； Create Table Supply (SNO n 4 PNO n 4 QTY n 5) Key SNO　PNO Fragment Supply1=Supply SJ［SNO=SNO］Supplier.Supplier1 Supply2=Supply SJ［SNO=SNO］Supplier.Supplier2 Site Supply1(1,3) Supply2(2,3)；

Department of Computer Science, Xiamen University, Oct, 2011