厦门大学计算机科学系研究生课程 《分布式数据库技术》 分布式数据库技术 专题二 数据分布 专题二 数据分布 林子雨 厦门大学计算机科学系

Presentation on theme: "厦门大学计算机科学系研究生课程 《分布式数据库技术》 分布式数据库技术 专题二 数据分布 专题二 数据分布 林子雨 厦门大学计算机科学系"— Presentation transcript:

1 厦门大学计算机科学系研究生课程 《分布式数据库技术》 分布式数据库技术 专题二 数据分布 专题二 数据分布 林子雨 厦门大学计算机科学系
分布式数据库技术 专题二 数据分布 专题二 数据分布 林子雨 厦门大学计算机科学系 厦门大学计算机科学系 年10月

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

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

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

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

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

7 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是关系的目（或称为度）。

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

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

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

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

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

13 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）

14 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。

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

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

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

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

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

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

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

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

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

24 水平分片 水平分片是将关系按行横向以某些条件划分成元组的子集，（即：满足条件的记录的集合）每个子集含有一定的逻辑意义，称逻辑片段。 定义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)表示。

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

26 垂直分片 垂直分片是将关系按列纵向以属性组划分成若干片段。在垂直分片时，为了保证片段的重构性，应将“键属性”属于各个片段中（放松的不相交性）。 定义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； ）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。

27 垂直分片 例２：职员关系Ｅ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）

28 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）操作。

29 混合分片 例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)

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

31 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 在分布式数据库的查询优化中，常常用半联接操作实现联接操作的操作数（关系）的缩减（归约）

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

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

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

35 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的诱导属性。

36 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）]

37 诱导分片

38 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。

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

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

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

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

43 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 }

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

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

46 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中进行描述 表示“数据分布的模式定义”的语句格式，即以语句格式表现数据分布的实际操作

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

48 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所组成。 如果一个分布结构是一棵树，就称它为分解树。

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

50 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） 为根节点的子树.

51 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 。 这个定义就是非常重要的独立分片的分解树定义

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

53 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 表示场地名）

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

55 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)；

56 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)；

57 Department of Computer Science, Xiamen University, Oct, 2011