Download presentation
Presentation is loading. Please wait.
Published byAkseli Saaristo Modified 6年之前
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,可用πAi(R)表示,其中K Ai。
27
垂直分片 例2:职员关系Emp(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:组合关系R(U,Q,S)上的混合分片(M)是一操作,它将关系按照一组属性A1 ,…, An和一组谓词P1 ,…,Pn划分成: R1(U1,Q1,S1),…,Rn(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
Similar presentations