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

1、第三章分布式数据库的设计第三章分布式数据库的设计 分布式数据库系统原理与应用内内 容容 简简 介介 解决数据分布的问题解决数据分布的问题如何如何对分布式数据库进行逻辑划分对分布式数据库进行逻辑划分如何对逻辑划分结果进行实际物理分配如何对逻辑划分结果进行实际物理分配n3.1两种设计策略（两种设计策略（ Top-down 和和 Bottom-up ）n3.2分片的定义级作用分片的定义级作用n3.3水平分片水平分片n3.4垂直分片垂直分片n3.5混合分片混合分片n3.6分片的表示方法分片的表示方法n3.7分配设计分配设计分布式数据库系统原理与应用p Top_Down和和 Bottom-UP应用场合应

2、用场合n Top_Down: 适于新设计一个数据库系统。适于新设计一个数据库系统。 （designed from scratch）n Bottom-UP: 已存在许多数据库系统，并将它已存在许多数据库系统，并将它们集成为一个数据库。典型的数据集成的研究。们集成为一个数据库。典型的数据集成的研究。 本课程侧重本课程侧重 top-down 设计中存在的关键技术。设计中存在的关键技术。3.13.1两种设计策略两种设计策略分布式数据库系统原理与应用3.13.1两种设计策略两种设计策略3.1.1 Top-down 设计过程设计过程 基于五步递归实现基于五步递归实现:1. 需求分析（需求分析（Requir

3、ement analysis）2. 概念设计、视图集成、概念设计、视图集成、E-R 表示、转换到关表示、转换到关系模式系模式3. 分布设计、数据分片和分配分布设计、数据分片和分配4. 物理设计物理设计5. 性能调优（性能调优（Tuning）分布式数据库系统原理与应用3.13.1两种设计策略两种设计策略需求分析系统需求说明书调优概念设计外部模式定义全局概念模式视图设计分布设计局部概念模式物理设计局部物理模式3.1.1-Top-down分布式数据库系统原理与应用3.1.2-Bottom-upDatabase 1Database 2Database nTranslator 1Translator 2

4、Translator nInS 1InS 2InS nIntegratorGCS3.13.1两种设计策略两种设计策略分布式数据库系统原理与应用3.2分片的定义及作用分片的定义及作用 例：某集团公司分地理位置分别在不同城市的总公司和下例：某集团公司分地理位置分别在不同城市的总公司和下属两个分公司组成，彼此之间靠网络相连接，业务管理由属两个分公司组成，彼此之间靠网络相连接，业务管理由分布式数据库系统完成。其网络结构图如下所示分布式数据库系统完成。其网络结构图如下所示总公司分公司1分公司2网络假设：人事系统中，有职工关系，定义为：EMP ENO，EName，Salary，DNO。 场地定义：总公司为

5、场地0，职工关系为EMP0分公司1为场地1，职工关系为EMP1分公司2为场地2，职工关系为EMP2EMP=EMP0+EMP1+EMP2为全局数据分布式数据库系统原理与应用3.2分片的定义及作用分片的定义及作用 p数据分布要求数据分布要求 方案方案1：公司总部保留全部数据。：公司总部保留全部数据。 方案方案2：各单位只保留自己的数据。：各单位只保留自己的数据。 方案方案3：公司总部保留全部数据，各分公司只保留自己单位的数据。：公司总部保留全部数据，各分公司只保留自己单位的数据。系统采用以上不同方案，对应需求不同的数据分配方案。如系统采用以上不同方案，对应需求不同的数据分配方案。如:p 上面三种方

6、案中，除方案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分片的定义分片的定义n分片（分片（Fragmentation) ) 对全局数据的划分。对全局数据的划分。n片段片段 划分的结果称为划分的结果称为片段片段 是分布式数据库中数据的存

7、储单位。是分布式数据库中数据的存储单位。n分配（分配（Allocation）：）：对片段的存储场地的指定，称为对片段的存储场地的指定，称为分配分配。 数据复制：数据复制：片段存储在一个以上场地时片段存储在一个以上场地时 数据分割：数据分割：片段只存储在一个场地片段只存储在一个场地分布式数据库系统原理与应用3.2分片的定义及作用分片的定义及作用 3.2.2分片的作用分片的作用n 减少网络传输量。减少网络传输量。如：采用数据复制，可就近访问所需信息。需频如：采用数据复制，可就近访问所需信息。需频繁访问的信息分片存储在本地场地上。繁访问的信息分片存储在本地场地上。n 增大事务处理的局部性增大事务处理

8、的局部性。局部场地上所须数据分片分配在各自的局部场地上所须数据分片分配在各自的场地上，减少数据访问的时间，增强局部事务效率。场地上，减少数据访问的时间，增强局部事务效率。n 提高数据的可用性和查询效率提高数据的可用性和查询效率。就近访问数据分片或副本，可提就近访问数据分片或副本，可提高访问效率。同时当某一场地出故障，若存在副本，非故障场地上的高访问效率。同时当某一场地出故障，若存在副本，非故障场地上的数据副本均是可用的。保证了数据的可用性、数据的完整性和系统的数据副本均是可用的。保证了数据的可用性、数据的完整性和系统的可靠性。可靠性。n 使负载均衡。使负载均衡。减少数据访问瓶颈，提高整个系统效

9、率。减少数据访问瓶颈，提高整个系统效率。分布式数据库系统原理与应用3.2分片的定义分片的定义及作用3.2.3分片设计过程分片设计过程分片过程分片过程是将全局数据进行逻辑划分和实际物理分配的过程。是将全局数据进行逻辑划分和实际物理分配的过程。全局数据划分为片段数据全局数据划分为片段数据片段数据经过分配得到物理数据片段数据经过分配得到物理数据GDBFDBPDB分片模式分配模式G D B ： 全 局 数 据 库（Global DB）F D B ： 片 段 数 据 库（Fragmentation DB）P D B ： 物 理 数 据 库（Physical DB）分布式数据库系统原理与应用3.2分片的定

10、义及作用分片的定义及作用 p 分片模式：分片模式：定义从全局关系到片段模式的映射关系。定义从全局关系到片段模式的映射关系。p 分配模式：分配模式：定义从片段关系到物理关系的映射关系。定义从片段关系到物理关系的映射关系。1：N时为复制；时为复制；1：1时为分割时为分割。RR1R2R3R3R2R1R2R3场地1场地2场地3全局关系片段 副本分布式数据库系统原理与应用3.2分片的定义及作用分片的定义及作用 3.2.3分片设计过程分片设计过程 GDB=FDBi 表示全局数据库是划分的多个片段数据库的集合。表示全局数据库是划分的多个片段数据库的集合。 nF(GDB)=FDB F()：表示表示分片模式分片

11、模式映射函数；能从全局数据库得到片段数据库映射函数；能从全局数据库得到片段数据库nF-1(FDB)=GDB F-1()表示分片模式的反映射函数；能从片段数据库得到全局数据表示分片模式的反映射函数；能从片段数据库得到全局数据nP(FDB)=PDB n P-1(PDB)=FDB P()：表示分配模式映射函数，能从片段数据库经得到物理数据库：表示分配模式映射函数，能从片段数据库经得到物理数据库 P-1()表示分配模式的反映射函数。能从物理数据库表示分配模式的反映射函数。能从物理数据库得到得到片段数据库片段数据库。分布式数据库系统原理与应用3.2分片的定义及作用分片的定义及作用 3.2.4分片的原则分

12、片的原则n 完备性完备性：所有全局数据：所有全局数据必须映射到某个片段上。必须映射到某个片段上。n 可重构性：可重构性：所有片段必须可以重新构成全局数据。所有片段必须可以重新构成全局数据。n 不相交性：不相交性：划分的各片段所包含的数据不允许相同。划分的各片段所包含的数据不允许相同。分布式数据库系统原理与应用3.2分片的定义及作用分片的定义及作用3.2.4分片的原则分片的原则n完备性完备性如果全局关系R划分的片段为R1,R2,Rn，则对于R中任意数据项d（dR），一定存在dRi（1in）。n可重构性可重构性如果全局关系R划分的片段为R1,R2,Rn，则存在关系运算，使得R=R1R2Rn。n不相

13、交性不相交性如果全局关系R水平划分的片段为R1,R2,Rn，则任意两个不同的片段的交集为空，即RiRj=（ij, 1in, 1jn）。分布式数据库系统原理与应用3.2分片的定义及作用分片的定义及作用 3.2.5分片的种类分片的种类n水平分片水平分片：按元组进行划分，由分片条件决定。：按元组进行划分，由分片条件决定。n垂直分片垂直分片：按关系属性划分，除关键字外，同一：按关系属性划分，除关键字外，同一关系的某一属性不允许出现在一个关系的多个分关系的某一属性不允许出现在一个关系的多个分片中。片中。n混合分片混合分片：即包括水平分片也包括垂直分片。：即包括水平分片也包括垂直分片。属性或元组关系根据需

14、要进行相应的分片分布式数据库系统原理与应用3.2分片的定义及作用分片的定义及作用3.2.6分布透明性分布透明性n透明性：透明性：指对用户和高层系统隐蔽具体实现细节。指对用户和高层系统隐蔽具体实现细节。n分布透明性指分片透明性、分配透明性和局部映射透分布透明性指分片透明性、分配透明性和局部映射透明性。明性。n分片透明性分片透明性：指用户不必考虑数据属于哪个片段。：指用户不必考虑数据属于哪个片段。n分配透明性分配透明性：指用户不必考虑各个片段的存储场地。：指用户不必考虑各个片段的存储场地。n局部映射透明性局部映射透明性：用户不必考虑数据的局部存储形式。：用户不必考虑数据的局部存储形式。分布式数据库

15、系统原理与应用3.33.3水平分片水平分片 3.3.1 水平分片的定义水平分片的定义水平分片水平分片 是将关系的是将关系的元组集元组集划分成若干不相交的划分成若干不相交的子集子集。分片分片属性属性 用来用来划分元组的属性划分元组的属性 分片条件分片条件 用来划分元组的条件用来划分元组的条件n定义定义设有一个关系设有一个关系R，R1，R2，Rn为为R的子关系的集合，如果的子关系的集合，如果R1，R2，Rn满足以下条件，则称其为关系满足以下条件，则称其为关系R的水平分片，的水平分片，Ri称为称为R的一个水的一个水平片段。平片段。 （1）R1，R2，Rn与与R具有相同的关系模式具有相同的关系模式 （

16、2）R1R2Rn=R （3）RiRj = （ij，1in）分布式数据库系统原理与应用3.33.3水平分片水平分片按下面分片条件进行分段：按下面分片条件进行分段： E1：满足（：满足（Dno=201）的所有分组；）的所有分组； E2：满足（：满足（Dno=202）的所有分组；）的所有分组； E3：满足（：满足（Dno201 AND Dno202 ）的所有分组。的所有分组。 p例如：设有雇员关系例如：设有雇员关系 EMPENO, ENAME, SALARY, DNOENOENAMESALARYDNO001张三1500201002李四1400202003王五800203基本水平分片基本水平分片 划分

17、关系元组的划分关系元组的属性属性，属于这个关系，属于这个关系本身本身分布式数据库系统原理与应用3.33.3水平分片水平分片 将关系将关系EMP分成了三个子关系分成了三个子关系E1:部门编号部门编号Dno=201的元组的元组E2:部门编号部门编号Dno=202的元组的元组E3:部门编号部门编号Dno201 AND Dno202分片属性分片属性：部门编号：部门编号Dno分片条件分片条件： Dno=201 Dno=202 Dno201 AND Dno202003 王五1200203002 李四1400202001 张三 1500201ENOENAMESALARYDNO001张三1500201002李

18、四1400202003王五800203E1：E2：E3：分布式数据库系统原理与应用3.33.3水平分片水平分片 水平分片正确性判定水平分片正确性判定根据水平分片定义，满足：根据水平分片定义，满足：nE1,E2,E3和和EMP关系模式相同；关系模式相同；nE1E2E3=EMPnE1E2=，E1E3=，E2E3=因此，因此，E1、E2和和E3是是EMP的水平分片。的水平分片。 分布式数据库系统原理与应用3.33.3水平分片水平分片导出水平分片导出水平分片 一个关系的分片不是基于关系本身的属性，而是根一个关系的分片不是基于关系本身的属性，而是根据另一个与其有关联性质的关系的属性来划分。据另一个与其有

19、关联性质的关系的属性来划分。n 例如：例如：关系关系WORKSENO，PRJNO，HOURS关系关系EMPENO，ENAME，SALARY，DNO将将WORKS按按DNO进行水平分片，分片条件同进行水平分片，分片条件同EMP的水平分的水平分片条件，得到的导出水平分片为片条件，得到的导出水平分片为W1、W2和和W3。n 分布式数据库系统原理与应用3.33.3水平分片水平分片p 导出水平分片计算如下：导出水平分片计算如下：令：令：W=WORKS EMP W： ENO，PRJNO，HOURS ，ENAME，SALARY，DNO 根据根据DNO对对W进行水平分片进行水平分片如：如：W1=DNO=201

20、（W）=DNO=201（WORKS EMP ）= WORKS DNO=201（EMP）= WORKS E1只保留只保留WORKS的属性的属性W1= attr（WORKS) W1）= attr（WORKS） (WORKS E1）= WORKS E1 称为半连接。称为半连接。 同理：同理：W2= WORKS E2 W3= WORKS E3通过上述三步骤得出按关系通过上述三步骤得出按关系EMP的的DNO属性对属性对WORKS进行水平划分，进行水平划分，得出得出WORKS的导出水平分片的导出水平分片W1、W2和和W3。分布式数据库系统原理与应用3.33.3水平分片水平分片3.3.2 水平分片的操作水平

21、分片的操作水平分片实际上是关系的选择操作，因此，用选择操作水平分片实际上是关系的选择操作，因此，用选择操作表示，选表示，选择条件为分片谓词择条件为分片谓词q，则，则R的片段可表示为的片段可表示为 ： q(R)。例例：E1= Dno=201（EMP） SQL：SELECT * FROM EMP WHERE DNO=201E2= Dno=202（EMP） SQL：SELECT * FROM EMP WHERE DNO=202E3= Dno201 AND Dno202（EMP） SQL：SELECT * FROM EMP WHERE Dno201 AND Dno202 分布式数据库系统原理与应用3.

22、33.3水平分片水平分片3.3.3水平分片设计水平分片设计 1.水平分片设计依据水平分片设计依据n基本水平分片基本水平分片应用应用需求因素：包括定性信息和定量的信息需求因素：包括定性信息和定量的信息n导出水平分片导出水平分片应用需求因素：包括应用需求因素：包括定性信息定性信息和和定量的信息定量的信息。 数据库信息：数据库信息：主要指全局模式中模式间的关联关系主要指全局模式中模式间的关联关系 定性信息定性信息（Qualitative）: 查询中的谓词。查询中的谓词。简单谓词简单谓词(simple predicate):小项谓词小项谓词(Minterm predicate)：简单谓词的连接。简单谓

23、词的连接。 定量信息定量信息（Quantitative information）小项选择度（小项选择度（Minterm selectivity） sel(mi)：基于小项谓词：基于小项谓词mi 的查询返的查询返回的元组个数。回的元组个数。 访问频率（访问频率（ Access frequency ） acc(mi)：用户基于小项谓词：用户基于小项谓词mi查询访问查询访问数据的频率。数据的频率。分布式数据库系统原理与应用3.33.3水平分片水平分片 3.3.3水平分片设计水平分片设计 1.水平分片设计依据水平分片设计依据n应用应用信息信息 定性信息定性信息（Qualitative）: 查询中的谓词

24、。分为：查询中的谓词。分为： 简单谓词简单谓词(simple predicate):只包含一个操作符号的查询谓词，称为简单谓词。小项谓词小项谓词(Minterm predicate)：由多个简单谓词组成的查询谓词称为小项谓词。简单谓词简单谓词（Simple predicates）TITLE = “Elect. Eng.” TITLE = “Syst. Anal.”TITLE = “Mech. Eng.” TITLE = “Programmer”SAL 30000, SAL 30000小项谓词（小项谓词（Minterm predicates）TITLE=“Elect. Eng.” SAL 300

25、00TITLE=“Elect. Eng.” SAL30000 (TITLE=“Programmer”) SAL 30000 (TITLE=“Programmer”) SAL30000 等等，但有些是无意意义的。等等，但有些是无意意义的。分布式数据库系统原理与应用3.33.3水平分片水平分片 3.3.3水平分片设计水平分片设计 1.水平分片设计依据水平分片设计依据n应用应用信息信息n定量信息定量信息（Quantitative information）p 小项选择度（小项选择度（Minterm selectivity） sel(mi)指指关系关系R中满足小项谓词中满足小项谓词mi的元组（的元组（

26、mi (R)）的数量。）的数量。p 访问频率（访问频率（ Access frequency ） acc(mi)指在一定时间段内对应小项谓词指在一定时间段内对应小项谓词mi的查询的查询qi被执行的次数，被执行的次数， 记为记为acc(mi)。 应用需求:总公司管理title5的雇员信息 定性信息定性信息 总 公 司 管 理 查 询 结 果 为 5 条 记 录 的 信 息 定量信息定量信息分布式数据库系统原理与应用3.33.3水平分片水平分片n定义定义 最小性最小性：如果简单谓词集中所有简单谓词都是相关（：如果简单谓词集中所有简单谓词都是相关（relevant）的，）的，则该简单谓词集具有最小性。

27、则该简单谓词集具有最小性。n定义定义 相关性（相关性（relevance）：令：令mi mj是两个小项谓词，是两个小项谓词，f1, f2分别是基分别是基于于mi, mj两个小项谓词定义的片段（不包括两个小项谓词定义的片段（不包括mi包含包含pi而而 mj包含包含 pi的情的情况），则况），则pi是相关的，当且仅当是相关的，当且仅当acc(mi)/card(fi) acc(mj)/card(fj)。 说明：一个应用或者访问说明：一个应用或者访问f1或者访问或者访问 f2。或者说，一个简单谓词确定一个片。或者说，一个简单谓词确定一个片段，即一个简单谓词同一个片段相关段，即一个简单谓词同一个片段相关

28、(relevance)。3.3.3水平分片水平分片设计设计n水平分片水平分片设计准则设计准则n定义定义完备性完备性简单谓词集合简单谓词集合Pr是完备的，当且仅当：是完备的，当且仅当：任何应用程序任何应用程序访问基于访问基于Pr分片的分片的任任何片段何片段的机率均等。的机率均等。分布式数据库系统原理与应用3.3水平分片水平分片n 最小性最小性：Pr =LOC=“Montreal”, LOC=“New York”, LOC=“Paris”,BUDGET200000,BUDGET200000 满足最小性Pr =LOC=“Montreal”, LOC=“New York”, LOC=“Paris”,B

29、UDGET200000 不满足最小性3.3.3水平分片设计水平分片设计1.水平分片设计准则水平分片设计准则n完备性完备性 PROJ(PNO,PNAME,BUDGET,LOC)Pr = LOC = “Montreal”, LOC = “New York”, LOC = “Paris”（1）如果有且只有一个应用按照location访问PROJ Pr 满足完备性。（2）若存在一个应用按照BUDGET 200000访问PROJ Pr 是不完备的。 Pr = LOC = “Montreal”, LOC = “New York”,LOC = “Paris”, BUDGET 20 不满足最小性不满足最小性 满足完备性满足完备性分布式数据库系统原理与应用3.3水