大连理工大学算法分析与设计20143章_分布式数据库系统的设计2014-12-3

1、第三章分布式数据库系统的设计1徐喜荣徐喜荣20122012年年11 11月月20132013年年1 1月月徐喜荣徐喜荣（)第三章分布式数据库系统的设计21 分布式数据库系统设计的目标 在理想情况下，分布式数据库系统的用户可不关心数据的物理分布，在理想情况下，分布式数据库系统的用户可不关心数据的物理分布， 由系统负责处理在不同站点上的分布数据。但是数据实际分布情况会由系统负责处理在不同站点上的分布数据。但是数据实际分布情况会 影响系统的总体性能：访问多个数据对象所需的时间和费用，会因为影响系统的总体性能：访问多个数据对象所需的时间和费用，会因为 这些数据对象是存放在同一站点，还是分布在多个站点有

2、很大差别。这些数据对象是存放在同一站点，还是分布在多个站点有很大差别。 分布式数据库系统中分布式数据库系统中最重要的目标最重要的目标是是尽量减少对网络的利用尽量减少对网络的利用，即尽，即尽可能减少站点之间的通信次数和通信量。可能减少站点之间的通信次数和通信量。 因此，分布式数据库系统的数据库设计者必须仔细考虑因此，分布式数据库系统的数据库设计者必须仔细考虑数据是否分数据是否分片片，片段如何复制片段如何复制，以及，以及数据或片段如何分布数据或片段如何分布，甚至在分布式数据库，甚至在分布式数据库 管理系统支持高的分布透明性时也要如此。管理系统支持高的分布透明性时也要如此。 第三章分布式数据库系统的

3、设计3 DDBS设计目标设计目标目标一：本地性或近地性；目标一：本地性或近地性；目标四：存储能力和费用。目标四：存储能力和费用。目标二：控制数据适当冗余；目标二：控制数据适当冗余；目标三：工作负荷分布；目标三：工作负荷分布；1 分布式数据库系统设计的目标第三章分布式数据库系统的设计41 分布式数据库系统设计的目标目标一：分布式数据库的本地性或近地性目标一：分布式数据库的本地性或近地性 分布式数据库设计中的一个分布式数据库设计中的一个主要原则主要原则是是使数据和应用实现最大程度使数据和应用实现最大程度的本地性的本地性。 开发一个分布式数据库的开发一个分布式数据库的主要目的主要目的：通过尽可能地使

4、数据靠近使用通过尽可能地使数据靠近使用该数据的应用进行分配该数据的应用进行分配，从而提高处理的本地性或近地性，减少通信。，从而提高处理的本地性或近地性，减少通信。 在一个精心设计的分布式数据库中，在一个精心设计的分布式数据库中，90%的数据的数据应当在本地站点找应当在本地站点找到而只有到而只有10%的数据的数据需要在远程站点上进行访问。也即需要在远程站点上进行访问。也即最有效的设计最有效的设计是确保数据对最大数目的应用具有本地性是确保数据对最大数目的应用具有本地性。 设计方法设计方法是对每种可供选择的分片方法和片段的分配方法都是对每种可供选择的分片方法和片段的分配方法都统计统计出出本地访问本地

5、访问和和远程访问远程访问的的次数次数，然后从其中选择一个，然后从其中选择一个最佳的方案最佳的方案。第三章分布式数据库系统的设计5目标二：控制数据适当冗余目标二：控制数据适当冗余 1 分布式数据库系统设计的目标 控制数据的适当冗余是分布式数据库系统设计的又一个目标。控制数据的适当冗余是分布式数据库系统设计的又一个目标。 在分布式数据库系统中，为了提高系统的本地性、并发度和可靠性，在分布式数据库系统中，为了提高系统的本地性、并发度和可靠性，需要增加数据的副本需要增加数据的副本。 这不仅使应用具有高度的可用性和本地性，而且当数据的任何一个这不仅使应用具有高度的可用性和本地性，而且当数据的任何一个副本

6、不能使用时，可方便地使用在另一站点中的该数据的副本进行恢副本不能使用时，可方便地使用在另一站点中的该数据的副本进行恢复，从而提高系统的可靠性。复，从而提高系统的可靠性。第三章分布式数据库系统的设计6目标三：工作负荷分布目标三：工作负荷分布1 分布式数据库系统设计的目标 分布式计算机系统的一个重要特征是把工作负荷分布在网络中的分布式计算机系统的一个重要特征是把工作负荷分布在网络中的各个站点上。各个站点上。 分布工作负荷的目的是分布工作负荷的目的是充分利用每个站点的计算机的能力和资源充分利用每个站点的计算机的能力和资源以提高应用执行的并行程度以提高应用执行的并行程度，从而提高系统的性能。，从而提高

7、系统的性能。第三章分布式数据库系统的设计7 数据库的分布会受到各站点的存储能力的影响数据库的分布会受到各站点的存储能力的影响。在网络中可以有。在网络中可以有 专门用于存储数据的站点，也可以有完全不支持大量容存储的站点。专门用于存储数据的站点，也可以有完全不支持大量容存储的站点。 一般数据存储的费用与一般数据存储的费用与 CPU，I /O及传输的费用相比是不重要的，及传输的费用相比是不重要的， 但是但是必须考虑各站点可用存储空间的限制必须考虑各站点可用存储空间的限制。1 分布式数据库系统设计的目标目标四：存储的能力和费用目标四：存储的能力和费用第三章分布式数据库系统的设计82 分布式数据库系统设

8、计的内容 分布式数据库系统设计的内容包括：分布式数据库系统设计的内容包括：分布式数据库的设计分布式数据库的设计和和应用设计应用设计。 分布式数据库的设计包括分布式数据库的设计包括全局模式设计全局模式设计和和每个站点的局部数据库设计每个站点的局部数据库设计。其中的关键是数据库的全局模式应如何划分，并映射到合适的站点上。由其中的关键是数据库的全局模式应如何划分，并映射到合适的站点上。由此产生了分布式数据库设计所特有的两个新问题：此产生了分布式数据库设计所特有的两个新问题：数据的分片设计数据的分片设计和和片段片段的位置分配设计的位置分配设计。 分片设计研究的是全局模式分片的分片设计研究的是全局模式分

9、片的“逻辑准则逻辑准则”，而片段的位置分配设，而片段的位置分配设计研究的是处理数据在各站点上的计研究的是处理数据在各站点上的“物理布局物理布局” 。 在分布式数据库设计中，为使分片设计和片段的位置分配设计得到的模在分布式数据库设计中，为使分片设计和片段的位置分配设计得到的模式能够高效地支持应用，还式能够高效地支持应用，还需要知道应用的确切要求需要知道应用的确切要求。第三章分布式数据库系统的设计92 分布式数据库系统设计的内容DDBS 设计设计DDB设计设计应用设计应用设计全局模式设计全局模式设计局部数据库设计局部数据库设计各个应用的各个应用的原发站点原发站点各个应用在每个站点各个应用在每个站点

10、激活频率激活频率各个应用对要求访问数据对象各个应用对要求访问数据对象 的的访问次数访问次数、类型类型和和统计分布统计分布数据的分片设计数据的分片设计和位置分配设计和位置分配设计第三章分布式数据库系统的设计1.2 分布式数据库的发展重构法重构法 ：一种：一种自顶向下自顶向下的创建方法。根据系统的实现环境和用户需求，的创建方法。根据系统的实现环境和用户需求， 按照分布式数据库系统的设计思想和方法，采用统一观点，从总体设计按照分布式数据库系统的设计思想和方法，采用统一观点，从总体设计 做起，包括各站点上的数据库系统，重新建立一个分布式数据库系统。做起，包括各站点上的数据库系统，重新建立一个分布式数据

11、库系统。 1.按照统一的思想来考虑按照统一的思想来考虑 分布式数据库系统中的分布式数据库系统中的 各种问题，有效地解决各种问题，有效地解决 分布式数据库系统数据分布式数据库系统数据 一致性、完整性和可靠性。一致性、完整性和可靠性。2.花费的人力、物力会比较花费的人力、物力会比较多，研制周期也比较长，多，研制周期也比较长，系统建设的代价会比较大。系统建设的代价会比较大。采用重构法创建的分布式数据采用重构法创建的分布式数据库系统，通常是同构异质或同库系统，通常是同构异质或同构同质构同质DDBS。大多选择同构。大多选择同构型分布式数据库系统。型分布式数据库系统。用户1用户2用户n分布式数据库管理系统

12、网络3 分布式数据库系统的设计方法第三章分布式数据库系统的设计113.1 分布式数据库的发展3 分布式数据库系统的设计方法组合法组合法 ：一种：一种自底向上自底向上的创建方法，也称的创建方法，也称集成法集成法。利用现有的计算机网络。利用现有的计算机网络和独立存在于各个站点上的现存数据库系统，通过建立一个分布式协调管和独立存在于各个站点上的现存数据库系统，通过建立一个分布式协调管 理系统，集成为一个统一的分布式数据库系统。理系统，集成为一个统一的分布式数据库系统。 1.先剖析网络功能；先剖析网络功能；2.剖析各个站点上原剖析各个站点上原有的数据库系统；有的数据库系统；3.解决数据的一致性、解决数

13、据的一致性、完整性和可靠性；完整性和可靠性；4.若各站点上若各站点上DBMS不相同，理论和实不相同，理论和实践难度较大。践难度较大。 采用组合法的分布式采用组合法的分布式数据库系统数据库系统通常是异构通常是异构或者同构异质或者同构异质DDBS。用户1用户2用户n分布式协调管理系统DBMS1DBMS2DBMSm 网络第三章分布式数据库系统的设计12 DDBS设计方法设计方法自顶向下方法（重构法）：自顶向下方法（重构法）：从头开始设计分布式数据库。从头开始设计分布式数据库。设计者理解用户的数据库应用要求，历经概念设计、逻辑设计和物理设计者理解用户的数据库应用要求，历经概念设计、逻辑设计和物理 设计

14、阶段，并将与计算机系统无关的规格说明逐渐求精成低级的、与设计阶段，并将与计算机系统无关的规格说明逐渐求精成低级的、与 计算机系统有关的规格说明。计算机系统有关的规格说明。概念设计和逻辑设计的结果是数据库的概念设计和逻辑设计的结果是数据库的 全局模式全局模式，包含了数据库的所有数据元素及其使用形式。，包含了数据库的所有数据元素及其使用形式。 专门针对专门针对 分布式数据库的一个设计阶段称为分布式数据库的一个设计阶段称为分布设计分布设计，将全局模式映射成几个将全局模式映射成几个 可能交叠的子集模式可能交叠的子集模式，每一个子模式表示与一个站点有关的信息子集，每一个子模式表示与一个站点有关的信息子集

15、，然后然后完成每一单个数据库的设计完成每一单个数据库的设计。混合方法混合方法：许多实际情况中，设计者一部分使用自顶向下方法，另许多实际情况中，设计者一部分使用自顶向下方法，另一部分使用自底向上方法。一部分使用自底向上方法。自底向上方法（组合法）：自底向上方法（组合法）：通过聚集现存数据库设计分布式数据库。通过聚集现存数据库设计分布式数据库。由于需要互联一些现存数据库以形成一个多数据库系统，或者是由于由于需要互联一些现存数据库以形成一个多数据库系统，或者是由于对各站点已独立完成了数据库的概念说明，所以对各站点已独立完成了数据库的概念说明，所以各站点上数据库规格各站点上数据库规格说明已是现存的。需

16、综合各站点的规格说明，以便得到分布式数据库说明已是现存的。需综合各站点的规格说明，以便得到分布式数据库的全局概念模式。的全局概念模式。3 分布式数据库系统的设计方法第三章分布式数据库系统的设计133.1 自顶向下设计方法需求分析概念设计视图设计分布设计物理设计观察与监视系统需求全局概念模式访问模式外部模式定义局部概念模式物理模式用户输入视图集成用户输入反馈反馈自顶向下设计过程3 分布式数据库系统的设计方法第三章分布式数据库系统的设计一、集中式数据库设计一、集中式数据库设计 包括四个阶段：需求分析、概念设计、逻辑设计、物理设计。包括四个阶段：需求分析、概念设计、逻辑设计、物理设计。需求分析需求分

17、析涉及收集用户数据库应用的非结构规格说明，并收集在涉及收集用户数据库应用的非结构规格说明，并收集在 设计数据字典中。设计数据字典中。 概念设计概念设计产生全局、综合数据库模式的一种概念规格说明和在此产生全局、综合数据库模式的一种概念规格说明和在此 模式上执行应用的概念规格说明。模式上执行应用的概念规格说明。 逻辑设计逻辑设计将综合概念模式转换成一给定的将综合概念模式转换成一给定的DBMS类型类型(关系、网状、关系、网状、 层次或面向对象模型层次或面向对象模型)的数据库模式。的数据库模式。 物理设计物理设计要遵照所选择的特定要遵照所选择的特定DBMS的能力和特征进行，并产生的能力和特征进行，并产

18、生 实现数据库的物理访问结构的定义。实现数据库的物理访问结构的定义。3.1 自顶向下设计方法3 分布式数据库系统的设计方法第三章分布式数据库系统的设计15二、分布式数据库设计二、分布式数据库设计增加一个新的阶段：增加一个新的阶段：分布设计分布设计 分布设计位于逻辑设计与物理设计之间，以一个分布设计位于逻辑设计与物理设计之间，以一个全局的、与站点全局的、与站点无关的模式作为输入无关的模式作为输入，以产生分布式数据库，以产生分布式数据库各站点的子模式各站点的子模式 ( 局部局部概念模式概念模式 )作为结果输出作为结果输出。 分布设计包括：分布设计包括：数据的分片设计数据的分片设计和和片段的位置分配

19、设计片段的位置分配设计。 分片是指把一个全局对象分片是指把一个全局对象(实体或关系实体或关系)细分成若干逻辑片段的过程；细分成若干逻辑片段的过程； 分配是指把各片段映射到一个或多个站点的过程，片段是最合适的分配是指把各片段映射到一个或多个站点的过程，片段是最合适的数据分配单位。数据分配单位。3.1 自顶向下设计方法3 分布式数据库系统的设计方法第三章分布式数据库系统的设计把现有数据库集成起来构成分布式数据库时，可采用自底向上的方法。把现有数据库集成起来构成分布式数据库时，可采用自底向上的方法。此方法重点是把此方法重点是把将现有的各种不同的数据库模式集成为全局模式将现有的各种不同的数据库模式集成

20、为全局模式。集成就是把集成就是把公用数据定义合并公用数据定义合并起来，并起来，并解决解决对同一个数据的不同表示对同一个数据的不同表示 方方法之间的法之间的冲突冲突。把现有数据库集成为一分布式数据库时，现有数据库很可能使用的是把现有数据库集成为一分布式数据库时，现有数据库很可能使用的是 不不同的同的DBMS，这将构成异构系统，从而增加了数据集成的复杂性。，这将构成异构系统，从而增加了数据集成的复杂性。 此时可以在每对不同的此时可以在每对不同的DBMS之间进行之间进行一对一的翻译一对一的翻译，也可，也可选择一个选择一个 公用数据模型公用数据模型，然后再把涉及这个，然后再把涉及这个DBMS的所有的不

21、同模式都翻译成的所有的不同模式都翻译成 这种唯一的表示方法。这种唯一的表示方法。3.2 自底向上设计方法3 分布式数据库系统的设计方法第三章分布式数据库系统的设计自底向上设计方法主要问题是自底向上设计方法主要问题是构造一个全局模式构造一个全局模式（超视图）（超视图）. 把分布式数据库中各站点上的数据库模式看成是全局模式的一个把分布式数据库中各站点上的数据库模式看成是全局模式的一个 视图，则寻求视图，则寻求全局模式的问题全局模式的问题可以看作可以看作是视图综合问题是视图综合问题。 概括分层结构支持视图综合概括分层结构支持视图综合。概括分层允许定义两个实体之间的。概括分层允许定义两个实体之间的 类

22、型和子类型关联，用于两个视图对同一实体的部分属性相交时。类型和子类型关联，用于两个视图对同一实体的部分属性相交时。视图综合问题的经典方法就是视图综合问题的经典方法就是生成三个实体生成三个实体： 一个实体具有共同属性一个实体具有共同属性（超类型），（超类型），两个实体具有不相交属性两个实体具有不相交属性（子类（子类型）。在全局视图中，共同属性与子类型相关联，并且对包含非相交型）。在全局视图中，共同属性与子类型相关联，并且对包含非相交 属性的各个视图生成一子类型。属性的各个视图生成一子类型。视图综合次序问题：一次把一个视图和全局模式进行综合，逐步构造视图综合次序问题：一次把一个视图和全局模式进行综

23、合，逐步构造起全局视图。通常最好起全局视图。通常最好首先综合最大的或最重要的视图首先综合最大的或最重要的视图，然后综合小，然后综合小的或者不重要的视图。的或者不重要的视图。3.2 自底向上设计方法3 分布式数据库系统的设计方法一、构造全局模式问题分析一、构造全局模式问题分析第三章分布式数据库系统的设计班机机号日期可用座位出入口座位图延期班机机号日期可用座位机型座位图班机班机1班机2机号日期可用座位座位图出入口延期机型使用概括分层的两个视图的合并3.2 自底向上设计方法3 分布式数据库系统的设计方法第三章分布式数据库系统的设计识别相似性：识别相似性： 综合两个模式的第一步是识别它们的相似性，综合

24、两个模式的第一步是识别它们的相似性，识别相似性是综合识别相似性是综合 模模式的出发点。式的出发点。 从先前存在的数据库中从先前存在的数据库中数据的相似性数据的相似性可以推得匹配，可以推得匹配，相似的值集相似的值集 表表明相交明相交。 通过比较属性，可以通过比较属性，可以识别匹配属性域识别匹配属性域。 如果在不同站点上有如果在不同站点上有相似应用相似应用，使用各自数据库中的数据副本，使用各自数据库中的数据副本, 则则这两站点的数据库之间有某些相似点。这两站点的数据库之间有某些相似点。3.2 自底向上设计方法3 分布式数据库系统的设计方法二、识别相似性和识别冲突二、识别相似性和识别冲突第三章分布式

25、数据库系统的设计 识别冲突：识别冲突：识别不同模式中相似数据的不同表示或域定义识别不同模式中相似数据的不同表示或域定义。 通过在全局模式中引入通过在全局模式中引入差异差异或在源模型中做一些折中，可以解决冲突。或在源模型中做一些折中，可以解决冲突。 模式差异模式差异包括包括命名冲突命名冲突、域差异域差异、定标差异定标差异和和结构差异结构差异。命名冲突命名冲突：同物异名（：同物异名（EMP,EMPLOYEE）和异物同名。通过在）和异物同名。通过在 全局模式中存储名字对应表就能方便地解决。全局模式中存储名字对应表就能方便地解决。域差异域差异：检测此问题通过比较源数据库或文件并注意不一致性来：检测此问

26、题通过比较源数据库或文件并注意不一致性来 进行。概括分层可以用来表示这一问题的解。进行。概括分层可以用来表示这一问题的解。 定标差异定标差异：在具有同一数值的不同视图中可以见到定标差异，如：在具有同一数值的不同视图中可以见到定标差异，如 计量单位不同计量单位不同(天、小时、分钟、秒）。设计中如有可能，应使用天、小时、分钟、秒）。设计中如有可能，应使用 更更精确的定标来检索数据，并使用换算公式进行连接或输出。精确的定标来检索数据，并使用换算公式进行连接或输出。结构差异结构差异：同一对象有的用实体描述：同一对象有的用实体描述, 有的用属性描述。视图设计有的用属性描述。视图设计中，一般通过改变一个或

27、两个视图来解决结构差异。中，一般通过改变一个或两个视图来解决结构差异。3.2 自底向上设计方法3 分布式数据库系统的设计方法第三章分布式数据库系统的设计处理操作期间的不一致数据策略（处理操作期间的不一致数据策略（5种）种） 对于设计时不能解决的冲突，需设计可供选择的策略，当执行时检测到对于设计时不能解决的冲突，需设计可供选择的策略，当执行时检测到不一致性时，以回答有不一致数据的查询。这些策略包括：不一致性时，以回答有不一致数据的查询。这些策略包括： 显示任一不一致值，但不通知用户显示任一不一致值，但不通知用户。这是最直截了当，同时也是最。这是最直截了当，同时也是最 危险的解决办法。危险的解决办

28、法。 显示所有不一致值，并告诉用户不一致值信息源显示所有不一致值，并告诉用户不一致值信息源。在这种情况下，。在这种情况下， 用户应能评价不一致性的原因。用户应能评价不一致性的原因。 求不一致值的某些组合函数值，并向用户显示此结果求不一致值的某些组合函数值，并向用户显示此结果。可能使用的。可能使用的 组合函数包括求平均、求最小值、求最大值。使用这种技术是在不组合函数包括求平均、求最小值、求最大值。使用这种技术是在不 同时间内出现时预期观察值也不同的场合。同时间内出现时预期观察值也不同的场合。 显示最新值显示最新值。这一策略需要更新操作的时间戳。它所依据的假设是这一策略需要更新操作的时间戳。它所依

29、据的假设是 不一致性归因于更新不及时，因此，最新的值也是最可能的值。不一致性归因于更新不及时，因此，最新的值也是最可能的值。 显示最可靠系统的值显示最可靠系统的值。这一策略所依据的假设是，设计者可以评价这一策略所依据的假设是，设计者可以评价 分布式数据库中站点的可靠性。分布式数据库中站点的可靠性。3.2 自底向上设计方法3 分布式数据库系统的设计方法第三章分布式数据库系统的设计分片设计的基本目的分片设计的基本目的：产生一个对：产生一个对全局数据合适的划分方案。全局数据合适的划分方案。使用使用这种方案得到的这种方案得到的片段作为分布式数据库中数据的分配和存储单位片段作为分布式数据库中数据的分配和

30、存储单位时，时，不但能够减少应用中的操作量，而且能够对于不但能够减少应用中的操作量，而且能够对于应用具有最大可能的应用具有最大可能的本地性本地性，使绝大多数，使绝大多数应用应用所使用的所使用的数据位于数据位于该应用的该应用的原发站点。原发站点。在数据分片设计时，是从分配的观点来看，在数据分片设计时，是从分配的观点来看，根据具有根据具有“相同性质相同性质”的元组或属性进行分组的元组或属性进行分组，每组就构成一个片段。，每组就构成一个片段。如果同一个片段的任意两个元素具有如果同一个片段的任意两个元素具有“相同性质相同性质” (例如访问频率例如访问频率相同相同)的话，则数据分配时所用的任意一种方法都

31、将把这两个元素的话，则数据分配时所用的任意一种方法都将把这两个元素放在一起，以这种方式得到的片段将是分布式数据库中放在一起，以这种方式得到的片段将是分布式数据库中数据合适的数据合适的分配和存储单位。分配和存储单位。4.1 分片设计的基本目的4 数据分片设计第三章分布式数据库系统的设计有两种基本的数据分片方法：有两种基本的数据分片方法：水平分片水平分片方法和方法和垂直分片垂直分片方法。方法。 水平分片水平分片是对全局关系执行是对全局关系执行“选择选择”操作，把具有相同性质的元组操作，把具有相同性质的元组 进行分组，构成若干个不相交的子集。进行分组，构成若干个不相交的子集。 水平分片的方法可归为水

32、平分片的方法可归为基本水平分片基本水平分片和和导出水平分片导出水平分片两类。两类。 垂直分片垂直分片是通过是通过“投影投影”操作把它的属性分成若干组。根据应用以操作把它的属性分成若干组。根据应用以“同样方式同样方式”(具有相同的使用频率具有相同的使用频率)访问的属性来进行分组。访问的属性来进行分组。 垂直分片的方法可归为垂直分片的方法可归为基本垂直分片基本垂直分片和和垂直群集垂直群集两类。基本垂直分两类。基本垂直分片只在某个键属性上重叠，其他属性不可重叠；垂直群集的组在其他片只在某个键属性上重叠，其他属性不可重叠；垂直群集的组在其他属性上也可以重叠。属性上也可以重叠。 通过交替水平分片与垂直分

33、片，可以产生通过交替水平分片与垂直分片，可以产生混合分片。混合分片。4.2 数据分片的基本类型和方法4 数据分片设计第三章分布式数据库系统的设计不论哪种分片方法，必须不论哪种分片方法，必须遵守如下规则遵守如下规则：假若有全局关系假若有全局关系R 被分片为子关系被分片为子关系(片段片段)集合集合 R = R1, R2, , Rn, 则则 R 满足满足 完整性条件完整性条件： 对任意对任意x R, Ri R 必有必有 x Ri ，i=1,2,n 可重构条件可重构条件：R= Ri (水平分片）水平分片）, R= Ri （垂直分片）（垂直分片） 不相交条件不相交条件：Ri Rj =空集空集, ij,

34、i, j=1,2,n (水平分片水平分片)Ri Rj =主键属性主键属性, i, j=1,2,n (垂直分片垂直分片) 4.2 数据分片的基本类型和方法4 数据分片设计第三章分布式数据库系统的设计例例2.1 S(S#, SNAME, AGE, SEX) define fragment S1 as select * from s where sex=M define fragment S2 as select * from s where sex=F 一、基本水平分片一、基本水平分片 以关系自身的属性性质为基础，执行以关系自身的属性性质为基础，执行“选择选择”操作，将关系分割成若干操作，将关系分

35、割成若干个不相交的片段。个不相交的片段。4.3 水平分片4 数据分片设计第三章分布式数据库系统的设计限定语：限定语：把初级分片对片段的定义中，执行选择操作的把初级分片对片段的定义中，执行选择操作的条件条件(或称或称谓词谓词)叫做限定语叫做限定语(qualification)。 例如：例如： sex=M 和和sex=F-是限定语是限定语水平分片正确性原则的三个条件可以这样实现：水平分片正确性原则的三个条件可以这样实现： 若若 R = R1, R2, , Rn, 则则 完整性条件：完整性条件：各片段定义中的各片段定义中的限定语集合必须是完整限定语集合必须是完整的，即至少的，即至少是它们允许值的集合

36、。是它们允许值的集合。 可重构条件：可重构条件：如果如果限定语集合限定语集合是完整的，则通过并操作总能重构是完整的，则通过并操作总能重构全局关系。全局关系。 不相交条件：不相交条件：如果如果限定语之间是互斥限定语之间是互斥的，它们的片段必不相交。的，它们的片段必不相交。4.3 水平分片4 数据分片设计第三章分布式数据库系统的设计对对全局关系进行水平初级分片需要全局关系进行水平初级分片需要确定一组不相交的、完整的限定语确定一组不相交的、完整的限定语(选择条件选择条件/谓词谓词)。 即表征合适分片的两个性质是：即表征合适分片的两个性质是： 令令 P = p1, p2, , pn 是一简单谓词集合，

37、为保证分片的正确性，则是一简单谓词集合，为保证分片的正确性，则P必须是：必须是：完整的完整的：同一分片同一分片中的中的任意两个元组任意两个元组被被任一应用任一应用以以同样概率同样概率访问。访问。最小的最小的：集合：集合P中的中的所有谓词所有谓词与与应用应用密切相关。密切相关。限定语具有完整性和最小性不是必要条件限定语具有完整性和最小性不是必要条件, 但是对于简化分配问题但是对于简化分配问题 有有好处。好处。4.3 水平分片4 数据分片设计第三章分布式数据库系统的设计例例2.2 设全局关系设全局关系EMP ( E#, NAME, DEPT, JOB, SAL, TEL, ) DEPT=1,2 J

38、OB=P, -P假定假定应用应用经常经常查询查询的内容是属于的内容是属于部门部门1且是且是程序员的职员程序员的职员。 则可能有的水平分段限定：则可能有的水平分段限定：(1) P= DEPT=1 （不是完整的）（不是完整的）(2) P= DEPT=1, JOB=P 是正确且合适（是正确且合适（完整的、最小的完整的、最小的） 这样分片得到的四个片段：这样分片得到的四个片段： DEPT=1, JOB=P, DEPT=1, JOB=-P DEPT=2, JOB=P, DEPT=2, JOB=-P 每一片段中元组被访问的概率是相等的，因此是每一片段中元组被访问的概率是相等的，因此是完整的完整的； 每一限

39、定语都与应用密切相关，因此是每一限定语都与应用密切相关，因此是最小的最小的； 限定语之间互斥，因此片段之间限定语之间互斥，因此片段之间必不相交必不相交。(3) P=DEPT=1, JOB=P, SAL500 （完整的，不是最小的）（完整的，不是最小的） 因为因为SAL500与应用无关。与应用无关。4.3 水平分片4 数据分片设计第三章分布式数据库系统的设计例例2.3 设全局关系设全局关系 SC( S#, C#, GRADE)， S ( S#, SNAME, AGE, SEX ) 要求：要求： 将将SC划分为划分为男生男生各门课各门课成绩成绩和和女生女生的各门的各门成绩成绩。 这不可能从这不可能

40、从SC本身的属性性质来执行选择，必须从关系本身的属性性质来执行选择，必须从关系S的属性性质的属性性质 或或水平片段来导出。水平片段来导出。二、导出水平分片二、导出水平分片 全局关系的导出式水平分片不是以其自身属性性质为基础，而是全局关系的导出式水平分片不是以其自身属性性质为基础，而是从另从另一个关系的属性性质一个关系的属性性质或或水平片段水平片段推导出来的。确定一方便的导出式水平推导出来的。确定一方便的导出式水平分片要求确定应用所执行的最重要的结合操作。导出分片可以使片段与分片要求确定应用所执行的最重要的结合操作。导出分片可以使片段与片段间片段间“连接连接”变得更容易。变得更容易。 4.3 水

41、平分片4 数据分片设计第三章分布式数据库系统的设计按按S的属性导出的属性导出 Define fragment SC1 as （ Define fragment SM as ） Select SC.S#, C#, GRADE From SC, S Where SC.S#=S.S# and SEX=M Define fragment SC2 as （ Define fragment SF as ） Select SC.S#, C#, GRADE From SC, S Where SC.S#=S.S# and SEX=F如果如果S已经进行水平分片，分为已经进行水平分片，分为SM和和SF, 分别为男生

42、全体和女生分别为男生全体和女生 全体，则按全体，则按S的水平分片（的水平分片（SM/SF）导出：）导出： Define fragment SC1 as Select * From SC Where S# in (Select SF.S# from SM) Define fragment SC2 as Select * From SC Where S# in (Select SM.S# from SF)4.3 水平分片4 数据分片设计第三章分布式数据库系统的设计全局关系全局关系R= Ri , i=1,2,n 如果属性如果属性AR, 必有必有ARi , i=1,2,n , 而且而且RiRj=Ap,

43、 ij，Ap为为R的码的码，则称，则称 Ri | i=1,2,n是关系是关系R的一个的一个垂直分片。垂直分片。如果属性如果属性AR, 必有必有ARi, i=1,2,n, 而且而且 RiRj=(Ap, A-p), ij， A-p为为R的一个或多个非码属性的一个或多个非码属性时，称时，称 Ri | i=1,2,n , 是关系是关系R的的 一个一个垂直群集。垂直群集。 垂直分片垂直分片和和垂直群集的目的垂直群集的目的在于使得许多在于使得许多重要应用可以只访问一个重要应用可以只访问一个 片段片段来执行，从而使来执行，从而使操作具有本地性操作具有本地性。4.4 垂直分片与垂直群集4 数据分片设计第三章分

44、布式数据库系统的设计全局关系全局关系 EMP(Eno#, NAME, SAL, TEL, MAGNUM, DEPT)， 其码为其码为 Eno#。主要应用有。主要应用有: 在在Sa 站点查询站点查询 NAME, SAL, TEL; 在在Sb 站点查询站点查询 NAME, MAGNUM, DEPT . 采用采用垂直分片垂直分片: EMP1 ( Eno#, NAME, SAL, TEL ) EMP2 ( Eno#, MAGNUM, DEPT ) 则则NAME属性只属于一个片段，对于上述应用，必须进行连接属性只属于一个片段，对于上述应用，必须进行连接 操作和非本地访问。操作和非本地访问。 采用采用垂直

45、群集垂直群集: EMP1 (Eno#, NAME, SAL, TEL) EMP2 (Eno#, NAME, MAGNUM, DEPT) 则对于上述应用不需要执行连接操作且可实现较好的本地性。则对于上述应用不需要执行连接操作且可实现较好的本地性。4.4 垂直分片与垂直群集4 数据分片设计第三章分布式数据库系统的设计33 数据分布是指分布式数据库中的数据不是存储在一个站点的计算机上，数据分布是指分布式数据库中的数据不是存储在一个站点的计算机上，而是根据需要将数据划分成若干逻辑片段，按而是根据需要将数据划分成若干逻辑片段，按某种策略某种策略把数据分片所得把数据分片所得 的的逻辑片段逻辑片段分散地分散

46、地存储存储在在各个站点各个站点上。上。 数据分布的策略有：集中式、分割式、复制式、混合式。数据分布的策略有：集中式、分割式、复制式、混合式。 集中式集中式： 所有数据片段都安排在所有数据片段都安排在同一站点同一站点上。对数据的控制和管理比较容易，上。对数据的控制和管理比较容易，数据的一致性和完整性能得到保证。缺点是该站点负担过重，系统数据的一致性和完整性能得到保证。缺点是该站点负担过重，系统 对该站点的依赖性过多，对该站点的依赖性过多，容易出现瓶颈容易出现瓶颈，系统可靠性较差。，系统可靠性较差。5.1 数据分布策略5 数据分布设计第三章分布式数据库系统的设计34 分割式分割式： 所有数据只有一

47、份，被分割成若干个逻辑片段，所有数据只有一份，被分割成若干个逻辑片段，每个逻辑片段被每个逻辑片段被 指派在某个特定的站点上指派在某个特定的站点上。可充分利用各个站点上的存储设备，。可充分利用各个站点上的存储设备， 数据的存储量大。各站点可自治的检索和修改数据，发挥系统的数据的存储量大。各站点可自治的检索和修改数据，发挥系统的 并发操作能力。当部分站点出现故障时，系统仍能运行，提高了并发操作能力。当部分站点出现故障时，系统仍能运行，提高了 系统的可靠性。系统的可靠性。 复制式复制式： 全局数据有多个副本，全局数据有多个副本，每个站点都有一个完整的数据副本每个站点都有一个完整的数据副本。系统。系统

48、 可靠性高，响应速度快，数据库恢复也较容易。但是要可靠性高，响应速度快，数据库恢复也较容易。但是要保持各个保持各个 站点上数据的同步修改站点上数据的同步修改，将要付出，将要付出高昂的代价高昂的代价。5 数据分布设计5.1 数据分布策略第三章分布式数据库系统的设计35 混合式混合式： 全部数据被分为若干子集，每个子集安置在不同的站点上，但全部数据被分为若干子集，每个子集安置在不同的站点上，但 任一任一 站点都没有保存全部的数据站点都没有保存全部的数据，并且，并且根据数据的重要性决定根据数据的重要性决定 各个子集的副本的多少各个子集的副本的多少。 这种分布策略这种分布策略兼顾了分割式和复制式兼顾了

49、分割式和复制式的做法，获得两者优点，的做法，获得两者优点， 但也包含两者的复杂性。但也包含两者的复杂性。5 数据分布设计5.1 数据分布策略第三章分布式数据库系统的设计在满足用户需求的前提下在满足用户需求的前提下, 把设计好的数据片段分配到相应的站点把设计好的数据片段分配到相应的站点 上存储，尽可能提高系统的效益。上存储，尽可能提高系统的效益。片段分配的片段分配的主要目的主要目的在于使应用执行的在于使应用执行的远程访问次数最少远程访问次数最少。例子例子: Emp( Eno#, Name, Location, Salary ) R1 = loc=Sa Emp ; R2 = loc=Sb Emp

50、Querya: select where Location=Sa. Queryb: select where Location=SbSite aSite bR1, R2 存放在哪?5.2 数据片段位置分配的方法5 数据分布设计第三章分布式数据库系统的设计 根据根据应用需求应用需求确定是非冗余分配还是冗余分配。在非冗余分配中，每个确定是非冗余分配还是冗余分配。在非冗余分配中，每个片段恰好映射到一个站点上；在冗余分配中，每个片段映射到一个或多个片段恰好映射到一个站点上；在冗余分配中，每个片段映射到一个或多个站点上；设计者决定每一片段复制程度，复制利益随站点上；设计者决定每一片段复制程度，复制利益随

51、检索与更新间的比值检索与更新间的比值而增加。而增加。分配方法分配方法非冗余分配设计方法非冗余分配设计方法最佳适应法：对每一种分配都进行估算，最佳适应法：对每一种分配都进行估算， 然后选择最佳的站点。然后选择最佳的站点。其他方法其他方法冗余分配的设计方法冗余分配的设计方法所有得益站点法所有得益站点法附加复制法：附加复制法：启发式方法启发式方法应用需求应用需求确定非复制问题的解；确定非复制问题的解；确定一组站点分配片段确定一组站点分配片段的一个副本。的一个副本。确定非复制问题的解；确定非复制问题的解；从最有益处起逐步附加从最有益处起逐步附加复制的副本，直到附加复制的副本，直到附加复制无好处为止。复

52、制无好处为止。5.2 数据片段位置分配的方法5 数据分布设计第三章分布式数据库系统的设计 设设F为单个片段为单个片段， 共有共有m个站点个站点 S1, Sm , 变量变量X1, , Xm取值如下：取值如下： 0 如果如果 片段片段F 不在不在 站点站点Sj上存储上存储 1 如果如果 片段片段F 在站点在站点Sj上存储上存储 则总代价为：则总代价为： Total cost = Read Cost + Write Cost + Storage Cost 读代价读代价 写代价写代价 存储代价存储代价 确定确定 Xj 的值的值, 1 j m, 使使总代价最小总代价最小。Xj =5.2 数据片段位置分配

53、的方法分配的简化模型5 数据分布设计第三章分布式数据库系统的设计读代价读代价： Read cost = ti MIN Cij i: 读申请源站点；读申请源站点； ti: 站点站点Si 上的读申请上的读申请激活次数激活次数； Cij: 从从 Si 读读 Sj 站点上的片段站点上的片段F的代价。的代价。i=1m.3ici,3ci,1ci,2ti FFF.12j5.2 数据片段位置分配的方法分配的简化模型5 数据分布设计第三章分布式数据库系统的设计写代价：写代价： Write cost = Xj ui Cij i: 写申请源站点写申请源站点 j: 被被更新更新站点站点 Xj: 0 如果如果 片段片段

54、F 不在不在 站点站点Sj上存储上存储 1 如果如果 片段片段F 在站点在站点Sj上存储上存储 ui: 站点站点 Si 上上更新更新激活次数激活次数 Cij: 从站点从站点 Si 更新更新 Sj 分段分段 F 的代价的代价i=1 j=1mm.iFFFUpdatesui5 数据分布设计5.2 数据片段位置分配的方法分配的简化模型第三章分布式数据库系统的设计存储代价：存储代价：Store Cost = Xi di Xi: 0 如果如果 片段片段F 不在不在 站点站点Si上存储上存储 1 如果如果 片段片段F 在站点在站点Si上存储上存储 di: 站点站点 Si 存储存储片段片段 F 的代价的代价i

55、=1m5 数据分布设计5.2 数据片段位置分配的方法分配的简化模型第三章分布式数据库系统的设计目标函数：确定目标函数：确定 Xj 的值的值, 1 j m, 使总代价最小。使总代价最小。min ti MIN Cij + Xj ui Cij + Xi di ji=1j=1i=1mmm即使最简单的公式也是即使最简单的公式也是 NP-完全问题完全问题。通常使用方法是尽可能将片段分配在被局部访问位置。通常使用方法是尽可能将片段分配在被局部访问位置。5 数据分布设计5.2 数据片段位置分配的方法分配的简化模型第三章分布式数据库系统的设计为了进行数据片段分配的费用和得益的估算，为了进行数据片段分配的费用和得

56、益的估算， 假定假定和得算，假定：和得算，假定： i ：表示：表示片段片段下标；下标； j ：表示：表示站点站点下标；下标； k ：表示：表示应用应用下标；下标； Fkj ：表示：表示应用应用k 在在站点站点j上激活的上激活的频率频率； Rki ：表示：表示应用应用k被激活一次，对被激活一次，对片段片段i 检索检索访问的访问的次数次数； Uki ：表示：表示应用应用k被激活一次，对被激活一次，对片段片段i 更新更新访问的访问的次数次数； Nki= Rki +Uki：表示：表示应用应用k被激活一次访问被激活一次访问片段片段i的的总次数总次数； Fkj* Nki : 表示表示应用应用k在站点在站点

57、j上对上对片段片段i的的访问频度访问频度； Fkj* Rki : 表示表示应用应用k在站点在站点j上对上对片段片段i的的检索频度检索频度； Fkj* Uki : 表示表示应用应用k在站点在站点j上对上对片段片段i的的更新频度更新频度。5 数据分布设计5.3 数据片段分配的费用和得益估算第三章分布式数据库系统的设计最佳适应法（非冗余分配）最佳适应法（非冗余分配）： 将片段将片段Ri分配到分配到访问片段访问片段Ri次数最多次数最多的那个站点上的那个站点上 。 在站点在站点j上上 片段片段Ri 的的本地访问次数本地访问次数(对全部应用加和对全部应用加和)是：是： Bij= k Fkj * Nki =

58、 k Fkj * (Rki +Uki) (1)估算：估算： max ( Bij ) = Bij 则片段则片段 Ri 就分配在站点就分配在站点 j上。上。5 数据分布设计5.3 数据片段分配的费用和得益估算水平分片情况j第三章分布式数据库系统的设计例：设有一个例：设有一个片段片段Ri, 有有两个应用两个应用A1,A2 ,可能在可能在三个场地三个场地分别设定为分别设定为 Site, Site, Site，并从应用需求分析得到的频度参数为，并从应用需求分析得到的频度参数为： 应用应用k=A1： 在在j=Site上访问频度上访问频度 FA1,* NA1,Ri =60, 在在j=Site上访问频度上访问

59、频度 FA1,* NA1,Ri =30, 在在j=Site上访问频度上访问频度 FA1,* NA1,Ri =20, 应用应用k=A2： 在在j=Site上访问频度上访问频度 FA2,* NA2,Ri =40, 在在j=Site上访问频度上访问频度 FA2,* NA2,Ri =50, 在在j=Site上访问频度上访问频度 FA2,* NA2,Ri =50. 则计算站点站点j上上 片段片段Ri 的的本地访问次数本地访问次数 Bij 如下如下： 当当 j=Site , Bij = k=A1,A2 Fkj * Nki = (60+40)=100, 当当 j=Site, Bij = k=A1,A2 Fk

60、j * Nki = (30+50)=80, 当当 j=Site, Bij = k=A1,A2 Fkj * Nki = (20+50)=70, 从计算结果可以得到从计算结果可以得到 Bij=100， j 被选定为被选定为Site, 也就是说片段也就是说片段Ri 应分配在应分配在Site上。上。5 数据分布设计5.3 数据片段分配的费用和得益估算水平分片情况第三章分布式数据库系统的设计 所有得益站点法（冗余分配方法一）所有得益站点法（冗余分配方法一）： 将片段将片段Ri的副本分配到的副本分配到所有得益站点所有得益站点 j 上。上。 所有得益站点所有得益站点：指在这些站点上，所有应用的：指在这些站点