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

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

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

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

4、atabase 2Database n Translator 1Translator 2Translator n InS 1InS 2InS n Integrator GCS 3.13.1两种设计策略两种设计策略 分布式数据库系统原理与应用 3.2分片的定义及作用分片的定义及作用 例：某集团公司分地理位置分别在不同城市的总公司和下例：某集团公司分地理位置分别在不同城市的总公司和下 属两个分公司组成，彼此之间靠网络相连接，业务管理由属两个分公司组成，彼此之间靠网络相连接，业务管理由 分布式数据库系统完成。其网络结构图如下所示分布式数据库系统完成。其网络结构图如下所示 总公司 分公司1 分公司2

5、网络 假设：人事系统中，有职工关系，定义为： EMP ENO，EName，Salary，DNO。 场地定义：总公司为场地0，职工关系为 EMP0 分公司1为场地1，职工关系为EMP1 分公司2为场地2，职工关系为EMP2 EMP=EMP0+EMP1+EMP2为全局数据 分布式数据库系统原理与应用 3.2分片的定义及作用分片的定义及作用 p数据分布要求数据分布要求 方案方案1：公司总部保留全部数据。：公司总部保留全部数据。 方案方案2：各单位只保留自己的数据。：各单位只保留自己的数据。 方案方案3：公司总部保留全部数据，各分公司只保留自己单位的数据。：公司总部保留全部数据，各分公司只保留自己单位

6、的数据。 系统采用以上不同方案，对应需求不同的数据分配方案。如系统采用以上不同方案，对应需求不同的数据分配方案。如: p 上面三种方案中，除方案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分片的定义分片

7、的定义 n分片（分片（Fragmentation) ) 对全局数据的划分。对全局数据的划分。 n片段片段 划分的结果称为划分的结果称为片段片段 是分布式数据库中数据的存储单位。是分布式数据库中数据的存储单位。 n分配（分配（Allocation）：）：对片段的存储场地的指定，称为对片段的存储场地的指定，称为分配分配。 数据复制：数据复制：片段存储在一个以上场地时片段存储在一个以上场地时 数据分割：数据分割：片段只存储在一个场地片段只存储在一个场地 分布式数据库系统原理与应用 3.2分片的定义及作用分片的定义及作用 3.2.2分片的作用分片的作用 n 减少网络传输量。减少网络传输量。如：采用数据

8、复制，可就近访问所需信息。需频如：采用数据复制，可就近访问所需信息。需频 繁访问的信息分片存储在本地场地上。繁访问的信息分片存储在本地场地上。 n 增大事务处理的局部性增大事务处理的局部性。局部场地上所须数据分片分配在各自的局部场地上所须数据分片分配在各自的 场地上，减少数据访问的时间，增强局部事务效率。场地上，减少数据访问的时间，增强局部事务效率。 n 提高数据的可用性和查询效率提高数据的可用性和查询效率。就近访问数据分片或副本，可提就近访问数据分片或副本，可提 高访问效率。同时当某一场地出故障，若存在副本，非故障场地上的高访问效率。同时当某一场地出故障，若存在副本，非故障场地上的 数据副本

9、均是可用的。保证了数据的可用性、数据的完整性和系统的数据副本均是可用的。保证了数据的可用性、数据的完整性和系统的 可靠性。可靠性。 n 使负载均衡。使负载均衡。减少数据访问瓶颈，提高整个系统效率。减少数据访问瓶颈，提高整个系统效率。 分布式数据库系统原理与应用 3.2分片的定义分片的定义及作用 3.2.3分片设计过程分片设计过程 分片过程分片过程是将全局数据进行逻辑划分和实际物理分配的过程。是将全局数据进行逻辑划分和实际物理分配的过程。 o全局数据划分为片段数据全局数据划分为片段数据 片段数据经过分配得到物理数据片段数据经过分配得到物理数据 GDB FDB PDB 分片模式 分配模式 G D

10、B ： 全 局 数 据 库 （Global DB） F D B ： 片 段 数 据 库 （Fragmentation DB） P D B ： 物 理 数 据 库 （Physical DB） 分布式数据库系统原理与应用 3.2分片的定义及作用分片的定义及作用 p 分片模式：分片模式：定义从全局关系到片段模式的映射关系。定义从全局关系到片段模式的映射关系。 p 分配模式：分配模式：定义从片段关系到物理关系的映射关系。定义从片段关系到物理关系的映射关系。 1：N时为复制；时为复制；1：1时为分割时为分割。 R R1 R2 R3 R3 R2 R1 R2 R3 场地1 场地2 场地3 全局关系 片段 副

11、本 分布式数据库系统原理与应用 3.2分片的定义及作用分片的定义及作用 3.2.3分片设计过程分片设计过程 GDB=FDBi 表示全局数据库是划分的多个片段数据库的集合。表示全局数据库是划分的多个片段数据库的集合。 nF(GDB)=FDB F()：表示分片模式映射函数；能从全局数据库得到片段数据库表示分片模式映射函数；能从全局数据库得到片段数据库 nF-1(FDB)=GDB F-1()表示分片模式的反映射函数；能从片段数据库得到全局数据表示分片模式的反映射函数；能从片段数据库得到全局数据 nP(FDB)=PDB n P-1(PDB)=FDB P()：表示分配模式映射函数，能从片段数据库经得到物

12、理数据库：表示分配模式映射函数，能从片段数据库经得到物理数据库 P-1()表示分配模式的反映射函数。能从物理数据库得到片段数据库表示分配模式的反映射函数。能从物理数据库得到片段数据库。 分布式数据库系统原理与应用 3.2分片的定义及作用分片的定义及作用 3.2.4分片的原则分片的原则 n 完备性：所有全局数据完备性：所有全局数据必须映射到某个片段上。必须映射到某个片段上。 n 可重构性：可重构性：所有片段必须可以重新构成全局数据。所有片段必须可以重新构成全局数据。 n 不相交性：不相交性：划分的各片段所包含的数据不允许相同。划分的各片段所包含的数据不允许相同。 分布式数据库系统原理与应用 3.

13、2分片的定义及作用分片的定义及作用 3.2.4分片的原则分片的原则 n完备性完备性 如果全局关系R划分的片段为R1,R2,Rn，则对于R中 任意数据项d（dR），一定存在dRi（1in）。 n可重构性可重构性 如果全局关系R划分的片段为R1,R2,Rn，则存在关 系运算，使得R=R1R2Rn。 n不相交性不相交性 如果全局关系R水平划分的片段为R1,R2,Rn，则任 意两个不同的片段的交集为空，即RiRj=（ij, 1in, 1jn）。 分布式数据库系统原理与应用 3.2分片的定义及作用分片的定义及作用 3.2.5分片的种类分片的种类 n水平分片水平分片：按元组进行划分，由分片条件决定。：按元

14、组进行划分，由分片条件决定。 n垂直分片垂直分片：按关系属性划分，除关键字外，同一：按关系属性划分，除关键字外，同一 关系的某一属性不允许出现在一个关系的多个分关系的某一属性不允许出现在一个关系的多个分 片中。片中。 n混合分片混合分片：即包括水平分片也包括垂直分片。：即包括水平分片也包括垂直分片。 属性或元组关系 根据需要进行相应的分片 分布式数据库系统原理与应用 3.2分片的定义及作用分片的定义及作用 3.2.6分布透明性分布透明性 n透明性：透明性：指对用户和高层系统隐蔽具体实现细节。指对用户和高层系统隐蔽具体实现细节。 n分布透明性指分片透明性、分配透明性和局部映射透分布透明性指分片透

15、明性、分配透明性和局部映射透 明性。明性。 n分片透明性分片透明性：指用户不必考虑数据属于哪个片段。：指用户不必考虑数据属于哪个片段。 n分配透明性分配透明性：指用户不必考虑各个片段的存储场地。：指用户不必考虑各个片段的存储场地。 n局部映射透明性局部映射透明性：用户不必考虑数据的局部存储形式。：用户不必考虑数据的局部存储形式。 分布式数据库系统原理与应用 3.33.3水平分片水平分片 3.3.1 水平分片的定义水平分片的定义 水平分片水平分片 是将关系的是将关系的元组集元组集划分成若干不相交的划分成若干不相交的子集子集。 分片属性分片属性 用来划分元组的属性用来划分元组的属性 分片条件分片条

16、件 用来划分元组的条件用来划分元组的条件 n定义定义 设有一个关系设有一个关系R，R1，R2，Rn为为R的子关系的集合，如果的子关系的集合，如果R1， R2，Rn满足以下条件，则称其为关系满足以下条件，则称其为关系R的水平分片，的水平分片，Ri称为称为R的一个水的一个水 平片段。平片段。 （1）R1，R2，Rn与与R具有相同的关系模式具有相同的关系模式 （2）R1R2Rn=R （3）RiRj = （ij，1in） 分布式数据库系统原理与应用 3.33.3水平分片水平分片 按下面分片条件进行分段：按下面分片条件进行分段： E1：满足（：满足（Dno=201）的所有分组；）的所有分组； E2：满足

17、（：满足（Dno=202）的所有分组；）的所有分组； E3：满足（：满足（Dno201 AND Dno202 ） 的所有分组。的所有分组。 p例如：设有雇员关系例如：设有雇员关系 EMPENO, ENAME, SALARY, DNO ENOENAMESALARYDNO 001张三1500201 002李四1400202 003王五800203 基本水平分片基本水平分片 划分关系元组的划分关系元组的属性属性，属于这个关系，属于这个关系本身本身 分布式数据库系统原理与应用 3.33.3水平分片水平分片 将关系将关系EMP分成了三个子关系分成了三个子关系 E1:部门编号部门编号Dno=201的元组的

18、元组 E2:部门编号部门编号Dno=202的元组的元组 E3:部门编号部门编号Dno201 AND Dno202 分片属性分片属性：部门编号：部门编号Dno 分片条件分片条件： Dno=201 Dno=202 Dno201 AND Dno202 003 王五1200203 002 李四1400202 001 张三 1500201 ENOENAMESALARYDNO 001张三1500201 002李四1400202 003王五800203 E1： E2： E3： 分布式数据库系统原理与应用 3.33.3水平分片水平分片 水平分片正确性判定水平分片正确性判定 根据水平分片定义，满足：根据水平分片

19、定义，满足： nE1,E2,E3和和EMP关系模式相同；关系模式相同； nE1E2E3=EMP nE1E2=，E1E3=，E2E3= 因此，因此，E1、E2和和E3是是EMP的水平分片。的水平分片。 分布式数据库系统原理与应用 3.33.3水平分片水平分片 导出水平分片导出水平分片 一个关系的分片不是基于关系本身的属性，而是根一个关系的分片不是基于关系本身的属性，而是根 据另一个与其有关联性质的关系的属性来划分。据另一个与其有关联性质的关系的属性来划分。 n 例如：例如： 关系关系WORKSENO，PRJNO，HOURS 关系关系EMPENO，ENAME，SALARY，DNO 将将WORKS按

20、按DNO进行水平分片，分片条件同进行水平分片，分片条件同EMP的水平分的水平分 片条件，得到的导出水平分片为片条件，得到的导出水平分片为W1、W2和和W3。 n 分布式数据库系统原理与应用 3.33.3水平分片水平分片 p 导出水平分片计算如下：导出水平分片计算如下： o令：令：W=WORKS EMP W： ENO，PRJNO，HOURS ，ENAME，SALARY，DNO n根据根据DNO对对W进行水平分片进行水平分片 如：如：W1=DNO=201（W） =DNO=201（WORKS EMP ） = WORKS DNO=201（EMP） = WORKS E1 n只保留只保留WORKS的属性的

21、属性 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 水平分片的操作水平分片的操作 水平分片实际上是关系的选择操作，因此，用选择操作水平分片实际上是关系的选择操作，因此，用

22、选择操作表示，选表示，选 择条件为分片谓词择条件为分片谓词q，则，则R的片段可表示为的片段可表示为 ： q(R)。 例例： E1= Dno=201（EMP） SQL：SELECT * FROM EMP WHERE DNO=201 E2= Dno=202（EMP） SQL：SELECT * FROM EMP WHERE DNO=202 E3= Dno201 AND Dno202（EMP） SQL：SELECT * FROM EMP WHERE Dno201 AND Dno 202 分布式数据库系统原理与应用 3.33.3水平分片水平分片 3.3.3水平分片设计水平分片设计 1.水平分片设计依据水

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

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

25、imple 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 30000 TITLE=“Elect.

26、 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的元组（的元组（ mi (R)）的数

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

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

29、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”,BUDGET

30、200000 不满足最小性 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水平分片水