第三章分布式数据库的设计

第三章分布式数据库的设计内容简介在系统设计中，最基本问题就是分布式数据库的分布问题，即如何对分布式数据库进行逻辑划分和实际物理分配。数据的逻辑划分称数据分片。本章主要针对数据分布进行介绍，以关系数据库为例来说明。§3.1两种设计策略（Top-down和Bottom-up）§3.2分片的定义§3.3水平分片§3.4水平分片的设计§3.5垂直分片的设计§3.6分片的表示方法§3.7分配设计Top_Down和Bottom-UP应用场合Top_Down:适于新设计一个数据库系统。（designedfromscratch）Bottom-UP:已存在许多数据库系统，并将它们集成为一个数据库。典型的数据集成的研究。本课程侧重top-down设计中存在的关键技术。§3.1两种设计策略3.1两种设计策略Top-down设计过程基于五步递归实现:1.需求分析（Requirementanalysis）2.概念设计、视图集成、E-R表示、转换到关系模式3.分布设计、数据分片和分配4.物理设计5.性能调优（Tuning）3.1两种设计策略-Top-down源于多数据库应用Database1Database2Databasen…Translator1Translator2Translatorn…InS1InS2InSn…IntegratorGCS§3.1两种设计策略-Bottom-up§3.2分片的定义例：某集团公司分地理位置分别在不同城市的总公司和下属两个分公司组成，彼此之间靠网络相连接，业务管理由分布式数据库系统完成。其网络结构图如下所示：总公司分公司1分公司2网络假设：人事系统中，有职工关系，定义为：EMP{ENO，EName，Salary，DNO}。场地定义：总公司为场地0，职工关系为EMP0分公司1为场地1，职工关系为EMP1分公司2为场地2，职工关系为EMP2EMP=EMP0+EMP1+EMP2为全局数据§3.2分片的定义数据分布要求：方案1：公司总部保留全部数据。方案2：各单位只保留自己的数据。方案3：公司总部保留全部数据，各分公司只保留自己单位的数据。系统采用以上不同方案，对应需求不同的数据分配方案。如：方案1：方案2：方案3：总部（EMP）分公司1（无）分公司2（无）总部（EMP0）分公司1（EMP1）分公司2（EMP2）总部（EMP）分公司1（EMP1）分公司2（EMP2）场地0场地1场地2上面三种方案中，除方案1外，均须进行分片定义。方案3中，分公司的数据信息除本场地存储外，总部场地也存储一份相同信息，存在在不同场地上互称副本。§3.2分片的定义定义片段（Fragment）：是分布式数据库中数据的存储单位。分片（Fragmentation)：对全局数据的划分。片段:划分的结果称为片段。分配（Allocation）：对片段的存储场地的指定，称为分配。当片段存储在一个以上场地时，称为数据复制（Replication）。如果每个片段只存储在一个场地，称为数据分割（Partition）存储。§3.2分片的定义分片的作用减少网络传输量。如：采用数据复制，可就近访问所需信息。需频繁访问的信息分片存储在本地场地上。增大事务处理的局部性。局部场地上所须数据分片分配在各自的场地上，减少数据访问的时间，增强局部事务效率。提高数据的可用性和查询效率。就近访问数据分片或副本，可提高访问效率。同时当某一场地出故障，若存在副本，非故障场地上的数据副本均是可用的。保证了数据的可用性、数据的完整性和系统的可靠性。使负载均衡。减少数据访问瓶颈，提高整个系统效率。§3.2分片的定义分片设计过程分片过程是将全局数据进行逻辑划分和实际物理分配的过程。全局数据由分片模式定义分成各个片段数据，各个片段数据由分配模式定义存储在各场地上。分片过程如图3.1所示。GDBFDBPDB分片模式分配模式GDB：全局数据库（GlobalDB）FDB：片段数据库（FragmentationDB）PDB：物理数据库（PhysicalDB）§3.2分片的定义分片模式：定义从全局模式到片段模式的映射关系。分配模式：定义从片段模式到物理模式的映射关系。1：N时为复制；1：1时为分割。RR1R2R3R3R2R1R2R3场地1场地2场地3全局关系片段副本§3.2分片的定义分片设计过程说明：GDB=∑FDBi表示全局数据库是划分的多个片段数据库的集合。F(GDB)=FDB〈≡〉F-1(FDB)=GDBF()：表示分片模式映射函数，F-1()表示分片模式的反映射函数。即全局数据库经分片模式映射函数得到全局数据的各个片段，相反，所有片段经分片模式反映射函数得到全局数据。P(FDB)=PDB〈≡〉P-1(PDB)=FDBP()：表示分配模式映射函数，P-1()表示分配模式的反映射函数。即片段数据库经分配模式映射函数得到物理数据库，相反，物理数据库经分配模式反映射函数得到片段数据库。§3.2分片的定义分片的原则在构成分布式数据库系统时，设计者必须考虑数据如何分布在各个场地上，即全局数据如何进行逻辑划分和物理分配问题。哪些数据须分布存放、哪些数据不须分布存放、哪些数据需要复制等，对系统进行全盘考虑，使系统性能最优。但无论如何进行分片，必须遵循下面原则：•完备性：所有全局数据必须映射到某个片段上。•可重构性：所有片段必须可以重新构成全局数据。•不相交性：划分的各片段所包含的数据不允许相同。§3.2分片的定义分片的正确性描述§3.2分片的定义分片的种类分布式系统按系统实际需求对全局数据进行分片和物理分配。分片的种类有三种。水平分片：按元组进行划分，由分片条件决定。垂直分片：按关系属性划分，除关键字外，同一关系的某一属性不允许出现在一个关系的多个分片中。混合分片：即包括水平分片也包括垂直分片。§3.2分片的定义分布透明性透明性：指对用户和高层系统隐蔽具体实现细节。分布透明性指分片透明性、分配透明性和局部映射透明性。分片透明性：指用户不必考虑数据属于哪个片段。分配透明性：指用户不必考虑各个片段的存储场地。局部映射透明性：用户不必考虑数据的局部存储形式。§3.3水平分片的设计水平分片的定义水平分片是将关系的元组集划分成若干不相交的子集。每个水平片段由关系中的某个属性上的条件来定义，该属性称为分片属性，该条件称为分片条件。定义设有一个关系R，{R1，R2，…，Rn}为R的子关系的集合，如果{R1，R2，…，Rn}满足以下条件，则称其为关系R的水平分片，Ri称为R的一个水平片段。（1）R1，R2，…，Rn与R具有相同的关系模式（2）R1∪R2∪…∪Rn=R（3）Ri∩Rj=Φ（i≠j，1≤i≤n）§3.3水平分片的设计按下面分片条件进行分段：E1：满足（Dno=201）的所有分组；E2：满足（Dno=202）的所有分组；E3：满足（Dno〈〉201ANDDno〈〉202）的所有分组。例3.1：§3.3水平分片的设计例3.1从上面的分片可知，将关系EMP分成了三个子关系，部门编号Dno等于201的元组（E1）、部门编号Dno等于202的元组（E2）和其他元组（E3）。分片属性：部门编号Dno分片条件：E1：Dno=201E2：Dno=202E3：Dno〈〉201ANDDno〈〉202003王五1200203002李四1400202001张三1500201§3.3水平分片的设计例3.1根据水平分片定义，满足：•E1,E2,E3和EMP关系模式相同；•E1∪E2∪E3=EMP•E1∩E2=Φ，E1∩E3=Φ，E2∩E3=Φ因此，E1、E2和E3是EMP的水平分片。§3.3水平分片的设计水平分片的表示水平分片实际上是关系的选择操作，因此，用选择操作σ表示，选择条件为分片谓词q，则R的片段可表示为：σq(R)。例3.2：E1=σDno=201（EMP）SQL：SELECT*FROMEMPWHEREDNO=201E2=σDno=202（EMP）SQL：SELECT*FROMEMPWHEREDNO=202E3=σDno〈〉201ANDDno〈〉202（EMP）SQL：SELECT*FROMEMPWHEREDno〈〉201ANDDno〈〉202§3.3水平分片的设计正确性判断分片必须遵循完备性、可重构性和不相交性三个原则。通过验证满足这三个特性判断分片的正确性。例如：上例的验证过程：•完备性证明:((Dno=201)∪(Dno=202)∪(Dno201∩Dno202)=T)证明：(Dno=201)∪(Dno=202)∪(Dno201∩Dno202)=((Dno=201)∪(Dno=202))∪(¬((Dno=201∪Dno=202))=T满足完备性。§3.3水平分片的设计-正确性判断可重构性证明(E1∪E2∪E3=EMP)证明：E1∪E2∪E3=σDno=201(EMP)∪σDno=202(EMP)∪σDno201ANDDno202(EMP)=σDno=201∪Dno=202∪Dno201ANDDno202(EMP)=σT(EMP)=EMP满足可重构性。§3.3水平分片的设计-正确性判断不相交性证明(E1∩E2=Φ，E1∩E3=Φ，E2∩E3=Φ)证明：E1∩E2=σDno=201∩Dno=202（EMP）=σF（EMP）=Φ同理：E1∩E3=Φ，E2∩E3=Φ满足不相交性。根据上面三原则证明可知：该水平分片的设计是正确的。§3.3水平分片的设计水平分片的影响因素水平分片是基于谓词条件划分关系。分片需求信息：来源于应用信息和数据库信息，应用信息：包括定性信息和定量的信息。数据库信息：主要指全局模式中模式间的关联关系（用于导出水平分片）—定性信息（Qualitative）:查询中的谓词。分为：简单谓词(simplepredicate):小项谓词(Mintermpredicate)：简单谓词的连接。—定量信息（Quantitativeinformation）小项选择（Mintermselectivity）–sel(mi)：基于小项谓词mi的查询返回的元组个数。访问频率（Accessfrequency）–acc(mi)：用户基于小项谓词mi查询访问数据的频率。§3.3水平分片的设计应用信息应用信息：包括定性信息和定量的信息。—定性信息（Qualitative）:查询中的谓词。分为：简单谓词(simplepredicate):小项谓词(Mintermpredicate)：简单谓词的连接。应用信息举例—简单谓词（Simplepredicates）TITLE=“Elect.Eng.”TITLE=“Syst.Anal.”TITLE=“Mech.Eng.”TITLE=“Programmer”SAL30000,SAL30000小项谓词（Mintermpredicates）TITLE=“Elect.Eng.”SAL30000TITLE=“Elect.Eng.”SAL30000(TITLE=“Programmer”)SAL30000(TITLE=“Programmer”)SAL30000…等等，但有些是无意意义的。—定量信息（Quantitativeinformation）小项选择（Mintermselectivity）–sel(mi)基于小项谓词mi的查询返回的元组个数。访问频率（Accessfrequency）–acc(mi)用户基于小项谓词mi查询访问数据的频率。§3.3水平分片的设计§3.4基本的水平分片基本水平分片(Primaryhorizontalfragmentation)定义：基本水平分片针对一个关系，基于选择操作定义的。描述如下：基本水平分片步骤：-第一步：找到具有完备性和最小性的简单谓词集合。-第二步：派生小项谓词集合—Mintermpredicatesareexponentialonthenumberofsimplepredicates.-第三步：确定有意义的小项谓词集，去除无意义的小项谓词。(),1jjFiijwRR