第2讲分布式数据库的设计-水平分片

第三章分布式数据库的设计分布式数据库系统原理与应用内容简介解决数据分布的问题①如何对分布式数据库进行逻辑划分②如何对逻辑划分结果进行实际物理分配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两种设计策略3.1.1Top-down设计过程基于五步递归实现:1.需求分析（Requirementanalysis）2.概念设计、视图集成、E-R表示、转换到关系模式3.分布设计、数据分片和分配4.物理设计5.性能调优（Tuning）分布式数据库系统原理与应用3.1两种设计策略需求分析系统需求说明书调优概念设计外部模式定义全局概念模式视图设计分布设计局部概念模式物理设计局部物理模式3.1.1-Top-down分布式数据库系统原理与应用3.1.2-Bottom-upDatabase1Database2Databasen…Translator1Translator2Translatorn…InS1InS2InSn…IntegratorGCS3.1两种设计策略分布式数据库系统原理与应用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外，均须进行分片定义。方案3中，分公司的数据信息除本场地存储外，总部场地也存储一份相同信息，存在在不同场地上互称副本。总部（EMP）分公司1（无）分公司2（无）总部（EMP0）分公司1（EMP1）分公司2（EMP2）总部（EMP）分公司1（EMP1）分公司2（EMP2）场地0场地1场地2方案1方案2方案3分布式数据库系统原理与应用3.2分片的定义及作用3.2.1分片的定义分片（Fragmentation)对全局数据的划分。片段划分的结果称为片段是分布式数据库中数据的存储单位。分配（Allocation）：对片段的存储场地的指定，称为分配。数据复制：片段存储在一个以上场地时数据分割：片段只存储在一个场地分布式数据库系统原理与应用3.2分片的定义及作用3.2.2分片的作用减少网络传输量。如：采用数据复制，可就近访问所需信息。需频繁访问的信息分片存储在本地场地上。增大事务处理的局部性。局部场地上所须数据分片分配在各自的场地上，减少数据访问的时间，增强局部事务效率。提高数据的可用性和查询效率。就近访问数据分片或副本，可提高访问效率。同时当某一场地出故障，若存在副本，非故障场地上的数据副本均是可用的。保证了数据的可用性、数据的完整性和系统的可靠性。使负载均衡。减少数据访问瓶颈，提高整个系统效率。分布式数据库系统原理与应用3.2分片的定义及作用3.2.3分片设计过程分片过程是将全局数据进行逻辑划分和实际物理分配的过程。①全局数据划分为片段数据②片段数据经过分配得到物理数据GDBFDBPDB分片模式分配模式GDB：全局数据库（GlobalDB）FDB：片段数据库（FragmentationDB）PDB：物理数据库（PhysicalDB）分布式数据库系统原理与应用3.2分片的定义及作用分片模式：定义从全局关系到片段模式的映射关系。分配模式：定义从片段关系到物理关系的映射关系。1：N时为复制；1：1时为分割。RR1R2R3R3R2R1R2R3场地1场地2场地3全局关系片段副本分布式数据库系统原理与应用3.2分片的定义及作用3.2.3分片设计过程GDB=∑FDBi表示全局数据库是划分的多个片段数据库的集合。F(GDB)=FDBF()：表示分片模式映射函数；能从全局数据库得到片段数据库F-1(FDB)=GDBF-1()表示分片模式的反映射函数；能从片段数据库得到全局数据P(FDB)=PDBP-1(PDB)=FDBP()：表示分配模式映射函数，能从片段数据库经得到物理数据库P-1()表示分配模式的反映射函数。能从物理数据库得到片段数据库。分布式数据库系统原理与应用3.2分片的定义及作用3.2.4分片的原则完备性：所有全局数据必须映射到某个片段上。可重构性：所有片段必须可以重新构成全局数据。不相交性：划分的各片段所包含的数据不允许相同。分布式数据库系统原理与应用3.2分片的定义及作用3.2.4分片的原则完备性如果全局关系R划分的片段为R1,R2,…,Rn，则对于R中任意数据项d（dR），一定存在dRi（1in）。可重构性如果全局关系R划分的片段为R1,R2,…,Rn，则存在关系运算，使得R=R1R2…Rn。不相交性如果全局关系R水平划分的片段为R1,R2,…,Rn，则任意两个不同的片段的交集为空，即RiRj=（ij,1in,1jn）。分布式数据库系统原理与应用3.2分片的定义及作用3.2.5分片的种类水平分片：按元组进行划分，由分片条件决定。垂直分片：按关系属性划分，除关键字外，同一关系的某一属性不允许出现在一个关系的多个分片中。混合分片：即包括水平分片也包括垂直分片。属性或元组关系根据需要进行相应的分片分布式数据库系统原理与应用3.2分片的定义及作用3.2.6分布透明性透明性：指对用户和高层系统隐蔽具体实现细节。分布透明性指分片透明性、分配透明性和局部映射透明性。分片透明性：指用户不必考虑数据属于哪个片段。分配透明性：指用户不必考虑各个片段的存储场地。局部映射透明性：用户不必考虑数据的局部存储形式。分布式数据库系统原理与应用3.3水平分片3.3.1水平分片的定义水平分片是将关系的元组集划分成若干不相交的子集。分片属性用来划分元组的属性分片条件用来划分元组的条件定义设有一个关系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）的所有分组。例如：设有雇员关系EMP{ENO,ENAME,SALARY,DNO}ENOENAMESALARYDNO001张三1500201002李四1400202003王五800203基本水平分片划分关系元组的属性，属于这个关系本身分布式数据库系统原理与应用3.3水平分片将关系EMP分成了三个子关系E1:部门编号Dno=201的元组E2:部门编号Dno=202的元组E3:部门编号Dno201ANDDno202分片属性：部门编号Dno分片条件：Dno=201Dno=202Dno201ANDDno202003王五1200203002李四1400202001张三1500201ENOENAMESALARYDNO001张三1500201002李四1400202003王五800203E1：E2：E3：分布式数据库系统原理与应用3.3水平分片水平分片正确性判定根据水平分片定义，满足：E1,E2,E3和EMP关系模式相同；E1∪E2∪E3=EMPE1∩E2=Φ，E1∩E3=Φ，E2∩E3=Φ因此，E1、E2和E3是EMP的水平分片。分布式数据库系统原理与应用3.3水平分片导出水平分片一个关系的分片不是基于关系本身的属性，而是根据另一个与其有关联性质的关系的属性来划分。例如：关系WORKS{ENO，PRJNO，HOURS}关系EMP{ENO，ENAME，SALARY，DNO}将WORKS按DNO进行水平分片，分片条件同EMP的水平分片条件，得到的导出水平分片为W1、W2和W3。分布式数据库系统原理与应用3.3水平分片导出水平分片计算如下：①令：W′=WORKSEMPW′：{ENO，PRJNO，HOURS，ENAME，SALARY，DNO}②根据DNO对W′进行水平分片如：W1=σDNO=201（W′）=σDNO=201（WORKSEMP）=WORKSσDNO=201（EMP）=WORKSE1③只保留WORKS的属性W1=attr（WORKS)W1）=attr（WORKS）(WORKSE1）=WORKSE1称为半连接。同理：W2=WORKSE2W3=WORKSE3通过上述三步骤得出按关系EMP的DNO属性对WORKS进行水平划分，得出WORKS的导出水平分片W1、W2和W3。分布式数据库系统原理与应用3.3水平分片3.3.2水平分片的操作水平分片实际上是关系的选择操作，因此，用选择操作σ表示，选择条件为分片谓词q，则R的片段可表示为：σq(R)。例：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水平分片3.3.3水平分片设计1.水平分片设计依据基本水平分片①应用需求因素：包括定性信息和定量的信息导出水平分片①应用需求因素：包括定性信息和定量的信息。②数据库信息：主要指全局模式中模式间的关联关系定性信息（Qualitative）:查询中的谓词。简单谓词(simplepredicate):小项谓词(Mintermpredicate)：简单谓词的连接。定量信息（Quantitativeinformation）小项选择度（Mintermselectivity）–sel(mi)：基于小项谓词mi的查询返回的元组个数。访问频率（Accessfrequency）–acc(mi)：用户基于小项谓词mi查询访问数据的频率。分布式数据库系统原理与应用3.3水平分片3.3.3水平分片设计1.水平分片设计依据应用信息定性信息（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(T