数据库系统概论ppt教程第十四章 分布式数据库系统

《数据库系统概论ppt教程第十四章 分布式数据库系统》由会员分享，可在线阅读，更多相关《数据库系统概论ppt教程第十四章 分布式数据库系统（62页珍藏版）》请在装配图网上搜索。

1、第十四章第十四章分布式数据库系统分布式数据库系统概述概述4分布式数据库系统是数据库技术和网络技术两分布式数据库系统是数据库技术和网络技术两者相互渗透和有机结合的结果者相互渗透和有机结合的结果DB1DB2DB3计算机1计算机2计算机3通讯网络北京重庆上海银行系统分布式数据库和分布式数据库系统分布式数据库和分布式数据库系统4定义定义 分布式数据库是由一组数据组成的，这组数据分布分布式数据库是由一组数据组成的，这组数据分布在计算机网络的不同计算机上，网络中每个结点具在计算机网络的不同计算机上，网络中每个结点具有独立处理的能力（称为场地自治），可以执行局有独立处理的能力（称为场地自治），可以执行局部应

2、用（只对本结点数据进行存取的应用），同时部应用（只对本结点数据进行存取的应用），同时每个结点也能通过网络通讯支持全局应用（指存取每个结点也能通过网络通讯支持全局应用（指存取两个或两个以上的结点的数据库应用）。两个或两个以上的结点的数据库应用）。分布式数据库强调场地自治性（局部应用）以及自分布式数据库强调场地自治性（局部应用）以及自治场地之间的协作性（全局应用）。治场地之间的协作性（全局应用）。分布式数据库和分布式数据库系统分布式数据库和分布式数据库系统4分布式数据库具有以下两个特点：分布式数据库具有以下两个特点： 分布性分布性 分布性有两层含义，一是指数据库中的数据不是分布性有两层含义，一是指

3、数据库中的数据不是都存储在同一结点（更确切的讲，不存储在同一都存储在同一结点（更确切的讲，不存储在同一计算机的存储设备上），而是分布在多个结点上；计算机的存储设备上），而是分布在多个结点上；二是指各结点具有独立的数据库处理能力，能够二是指各结点具有独立的数据库处理能力，能够有效地支持局部应用。有效地支持局部应用。 逻辑整体性逻辑整体性 分布在各结点的数据不是孤立的，而是相互联系分布在各结点的数据不是孤立的，而是相互联系的，是一个逻辑整体，能够支持存取多个结点数的，是一个逻辑整体，能够支持存取多个结点数据的全局应用。据的全局应用。分布式数据库和分布式数据库系统分布式数据库和分布式数据库系统4分布

4、式数据库系统是在集中式数据库系统技术分布式数据库系统是在集中式数据库系统技术的基础上发展起来的，但不是简单地把集中式的基础上发展起来的，但不是简单地把集中式数据库分散的实现，它丰富和发展了集中式数数据库分散的实现，它丰富和发展了集中式数据库的许多概念和技术，具有自己独特的特征据库的许多概念和技术，具有自己独特的特征和性质。具体来说，它具有以下特点：和性质。具体来说，它具有以下特点： 数据独立性数据独立性 数据独立性在分布式数据库系统中具有了更多的含数据独立性在分布式数据库系统中具有了更多的含义，它不仅包括数据的逻辑独立性和物理独立性以义，它不仅包括数据的逻辑独立性和物理独立性以外，还包括数据的

5、分布独立性（也称分布透明性）。外，还包括数据的分布独立性（也称分布透明性）。分布透明性指用户不必关心数据的逻辑分片，不必分布透明性指用户不必关心数据的逻辑分片，不必关心数据物理位置分布的细节，不必关心重复副本关心数据物理位置分布的细节，不必关心重复副本（冗余数据）一致性问题，也不必关心局部结点上（冗余数据）一致性问题，也不必关心局部结点上数据库支持哪种数据模型。数据库支持哪种数据模型。分布式数据库和分布式数据库系分布式数据库和分布式数据库系统统 集中与自治相结合的控制机构集中与自治相结合的控制机构 在分布式数据系统中，数据的共享有两个层次：在分布式数据系统中，数据的共享有两个层次：一是局部共享

6、，即在局部数据库中存储局部结点一是局部共享，即在局部数据库中存储局部结点各用户的共享数据；二是全局共享。即在分布式各用户的共享数据；二是全局共享。即在分布式数据库系统的各个结点也存储供其他结点的用户数据库系统的各个结点也存储供其他结点的用户共享的数据，支持系统的全局应用。因此，相应共享的数据，支持系统的全局应用。因此，相应的控制机构也具有两个层次：集中和自治。分布的控制机构也具有两个层次：集中和自治。分布式数据库系统常常采用集中和自治相结合的控制式数据库系统常常采用集中和自治相结合的控制机构。各局部的机构。各局部的DBMS可以独立的管理局部的数可以独立的管理局部的数据库，具有自治功能。同时系统

7、又设有集中控制据库，具有自治功能。同时系统又设有集中控制机构，协调各局部机构，协调各局部DBMS的工作，执行全局应用。的工作，执行全局应用。分布式数据库和分布式数据库系统分布式数据库和分布式数据库系统 适当增加数据冗余适当增加数据冗余 在分布式数据库系统中适当的增加了冗余数据，在分布式数据库系统中适当的增加了冗余数据，在不同的结点存储同一数据的多个副本，其原因在不同的结点存储同一数据的多个副本，其原因是：一提高系统的可靠性、可用性，当某一结点是：一提高系统的可靠性、可用性，当某一结点出现故障时，系统可以对另一结点的相同副本进出现故障时，系统可以对另一结点的相同副本进行操作，不会因为一处故障而造

8、成整个系统的瘫行操作，不会因为一处故障而造成整个系统的瘫痪；二是提高系统性能，系统可以选择用户最近痪；二是提高系统性能，系统可以选择用户最近的数据副本来进行操作，减少通信代价，改善整的数据副本来进行操作，减少通信代价，改善整个系统的性能。个系统的性能。分布式数据库和分布式数据库系统分布式数据库和分布式数据库系统 全局的一致性、可串行性和可恢复性全局的一致性、可串行性和可恢复性 分布式数据库系统中各局部数据库应满足集中式分布式数据库系统中各局部数据库应满足集中式数据库的一致性、并发事务的可串行性和可恢复数据库的一致性、并发事务的可串行性和可恢复性。除此之外还应保证数据库的全局一致性、全性。除此之

9、外还应保证数据库的全局一致性、全局并发事务的可串行性和系统全局的可恢复性。局并发事务的可串行性和系统全局的可恢复性。这是因为在分布式数据库系统中全局应用要涉及这是因为在分布式数据库系统中全局应用要涉及两个以上结点的数据，全局事务可能由不同结点两个以上结点的数据，全局事务可能由不同结点上的多个操作组成。上的多个操作组成。分布式数据库和分布式数据库系统分布式数据库和分布式数据库系统4分布式数据库系统的目标分布式数据库系统的目标 适应部门分布的组织结构，降低费用适应部门分布的组织结构，降低费用 使用数据库的单位在组织上常常是分布的，在地使用数据库的单位在组织上常常是分布的，在地理上也是分布的。分布式

10、数据库系统的结构符合理上也是分布的。分布式数据库系统的结构符合上述分布的组织结构，允许各个部门将自己常用上述分布的组织结构，允许各个部门将自己常用的数据存储在本地，降低了通信代价，提高了响的数据存储在本地，降低了通信代价，提高了响应速度。应速度。 提高系统的可靠性和可用性提高系统的可靠性和可用性 将数据分布于多个结点，并适当增加冗余度，可将数据分布于多个结点，并适当增加冗余度，可以提供更好的可靠性。以提供更好的可靠性。分布式数据库和分布式数据库系统分布式数据库和分布式数据库系统 充分利用数据库资源，提高现有集中式数据充分利用数据库资源，提高现有集中式数据库的利用率库的利用率 当在一个大企业内部

11、和大部门中已经建成若干个当在一个大企业内部和大部门中已经建成若干个数据库后，为了利用相互的资源，开发全局应用数据库后，为了利用相互的资源，开发全局应用可以在现有各局部数据库的基础上做一定的修改可以在现有各局部数据库的基础上做一定的修改和重构，建立一个分布式数据库系统。和重构，建立一个分布式数据库系统。 逐步扩展处理能力和系统规模逐步扩展处理能力和系统规模 相对于集中式数据库系统，分布式数据库系统能相对于集中式数据库系统，分布式数据库系统能够方便地将一个新结点纳入系统，而不影响现有够方便地将一个新结点纳入系统，而不影响现有系统的结构和系统的正常运行，提供了逐步扩展系统的结构和系统的正常运行，提供

12、了逐步扩展系统能力的较好途径。系统能力的较好途径。分布式数据库的体系结构分布式数据库的体系结构全局全局外模式外模式全局全局外模式外模式全局全局概念模式概念模式分片模式分片模式分布模式分布模式局部局部概念模式概念模式局部局部概念模式概念模式局部局部内模式内模式局部局部内模式内模式局部局部DB局部局部DB全局全局DBMS局部局部DBMS映像1映像2映像3映像4分布式数据库的体系结构分布式数据库的体系结构4全局外模式全局外模式全局应用的用户视图，是全局概念模式的子集。全局应用的用户视图，是全局概念模式的子集。4全局概念模式全局概念模式定义分布式数据库中数据的整体逻辑结构，使得数定义分布式数据库中数据

13、的整体逻辑结构，使得数据如同没有分布一样。据如同没有分布一样。4分片模式分片模式每一个全局关系可以分为若干互不相交的部分，每每一个全局关系可以分为若干互不相交的部分，每一部分称为一个片段。分片模式定义片段以及全局一部分称为一个片段。分片模式定义片段以及全局关系到片段的映像。关系到片段的映像。4分布模式分布模式定义片段的存放结点。定义片段的存放结点。分布式数据库的体系结构分布式数据库的体系结构4分布（网络）透明性分布（网络）透明性 分片透明性分片透明性用户或应用程序只对全局关系进行操作而不必考虑用户或应用程序只对全局关系进行操作而不必考虑关系的分片。如果分片模式改变了，通过调整全局关系的分片。如

14、果分片模式改变了，通过调整全局模式与分片模式之间的映象关系来保持全局模式不模式与分片模式之间的映象关系来保持全局模式不变。变。 位置透明性位置透明性用户或应用程序不必了解片段的存储位置。用户或应用程序不必了解片段的存储位置。 局部数据模型透明性局部数据模型透明性用户或应用程序不必了解局部场地上使用的是哪种用户或应用程序不必了解局部场地上使用的是哪种数据模型。数据模型。分布式数据库的体系结构分布式数据库的体系结构4示例：示例：设有全局关系S，它被划分为两个片段S-A（本科生），S-B（研究生），S-B有两个副本。SS-AS-BS-AS-BS-BSite-1Site-2Site-3全局关系全局关系

15、片段片段物理存储物理存储分布式数据库设计分布式数据库设计4数据在分布式数据库中的存储途径数据在分布式数据库中的存储途径 数据的重复存储数据的重复存储系统在两个或两个以上结点维护关系系统在两个或两个以上结点维护关系R的几个完全的几个完全相同的副本。如果系统的每个结点都存储相同的副本。如果系统的每个结点都存储R的一个的一个副本，则称这种重复存储为完全重复存储。数据重副本，则称这种重复存储为完全重复存储。数据重复存储具有以下几个优点：复存储具有以下几个优点： 可用性强可用性强 如果某个存储如果某个存储R的结点出了故障，系统仍然可以使用其它的结点出了故障，系统仍然可以使用其它结点上的副本继续处理用户查

16、询，使系统正常运行。结点上的副本继续处理用户查询，使系统正常运行。 增强并行性增强并行性 由于由于R的重复存储，可以使更多的用户并行地查询的重复存储，可以使更多的用户并行地查询R。 数据的重复存储也会带来一些问题，如增加了更新数据的重复存储也会带来一些问题，如增加了更新操作的开销，加大了并行控制的难度操作的开销，加大了并行控制的难度分布式数据库设计分布式数据库设计 分片存储分片存储关系被划分为几个片段，各个片段存储在不关系被划分为几个片段，各个片段存储在不同的结点上。将数据分片，使数据存放的单同的结点上。将数据分片，使数据存放的单位不是关系而是片段，这既有利于按照用户位不是关系而是片段，这既有

17、利于按照用户的需求较好地组织数据的分布，也有利于控的需求较好地组织数据的分布，也有利于控制数据的冗余度。分片时必须遵循以下原则：制数据的冗余度。分片时必须遵循以下原则： 完全性：被划分关系中的每个元组必须属于一个片段。完全性：被划分关系中的每个元组必须属于一个片段。 不相交性：同一个关系的片段互不相交。不相交性：同一个关系的片段互不相交。 可重构性：如果可重构性：如果R被划分为片段被划分为片段R1、R2、Rn，则，则R能从能从R1、R2、Rn恢复出来。恢复出来。分布式数据库设计分布式数据库设计 分片方式分片方式 水平分片水平分片 垂直分片垂直分片 导出分片导出分片 混合分片混合分片分布式数据库

18、设计分布式数据库设计 水平分片水平分片将关系将关系r依照一定条件按行分为不相交的若干子依照一定条件按行分为不相交的若干子集集r1，r2，rn，每个子集每个子集ri称为一个水平片段。称为一个水平片段。 一个水平片段可以看成是关系上的一个选择。一个水平片段可以看成是关系上的一个选择。ri = P（i）（r）如如C_S= DNO=D06（S）关系的重构可以通过并运算来实现。关系的重构可以通过并运算来实现。r= r1 r2rn分布式数据库设计分布式数据库设计 垂直分片垂直分片将关系将关系r按列分为若干属性子集按列分为若干属性子集r1，r2，rn，每每个子集个子集ri称为一个垂直片段。称为一个垂直片段。

19、一个垂直片段可以看成是关系上的一个投影。一个垂直片段可以看成是关系上的一个投影。ri =Ri（r）其中其中Ri是是r的一个属性子集。的一个属性子集。 如如P_S = PNO，SAL（P）关系的重构可以通过连接运算来实现。关系的重构可以通过连接运算来实现。r= r1 r2 rn所有分片都包括关系的码所有分片都包括关系的码分布式数据库设计分布式数据库设计 导出分片导出分片 导出水平分片，分片的条件不是关系本身属性条件，导出水平分片，分片的条件不是关系本身属性条件，而是其它关系的属性条件。而是其它关系的属性条件。 如如SC（SNO，CNO，G）按学生系别分片。）按学生系别分片。 混合分片混合分片 关

20、系按某种方式分片后，得到的片段再按另一种方式关系按某种方式分片后，得到的片段再按另一种方式继续分片。继续分片。 如如SC（SNO，CNO，G）按学生系别分片，再对每个）按学生系别分片，再对每个片段按成绩片段按成绩（及格，不及格）分片。及格，不及格）分片。分布式数据库设计分布式数据库设计 组合存储组合存储这种方法是重复存储和分片存储相结合的方这种方法是重复存储和分片存储相结合的方法。关系被划分为几个片段，系统为每个片法。关系被划分为几个片段，系统为每个片段维护几个副本，每个副本存放于不同的结段维护几个副本，每个副本存放于不同的结点上。点上。分布式数据库设计分布式数据库设计4命名和局部自治性命名和

21、局部自治性 每个数据项（关系、副本、片段）必须有唯每个数据项（关系、副本、片段）必须有唯一的名字，在分布式数据库系统中必须保证一的名字，在分布式数据库系统中必须保证在不同的结点上不会用同一个名字来代表不在不同的结点上不会用同一个名字来代表不同的数据项。同的数据项。 途径途径1：名字服务器：名字服务器 所有名字都在名字服务器中注册，每个名字对应所有名字都在名字服务器中注册，每个名字对应一个数据项。一个数据项。 缺陷：名字服务器成为名字解析的瓶颈；其故障缺陷：名字服务器成为名字解析的瓶颈；其故障将影响整个系统的运行；局部自治性降低。将影响整个系统的运行；局部自治性降低。分布式数据库设计分布式数据库

22、设计 途径途径2：将结点标识作为前缀加到该结点：将结点标识作为前缀加到该结点数据项的名字前面。使用这一方法，能够数据项的名字前面。使用这一方法，能够保证名字的唯一性，不须中央控制，局部保证名字的唯一性，不须中央控制，局部自治性提高；但不能保证网络透明性。自治性提高；但不能保证网络透明性。分布式数据库管理系统概述分布式数据库管理系统概述4D-DBMS由四个部分组成：由四个部分组成： LDBMS，局部场地上的，局部场地上的DBMS，主要功能，主要功能是建立和管理局部数据库，提供场地自治能是建立和管理局部数据库，提供场地自治能力，执行局部应用以及全局查询的子查询。力，执行局部应用以及全局查询的子查询

23、。 GDBMS，全局数据库管理系统，主要功能，全局数据库管理系统，主要功能是提供分布透明性，协调全局事务的执行，是提供分布透明性，协调全局事务的执行，协调各局部协调各局部DBMS以完成全局应用，保证数以完成全局应用，保证数据库的全局一致性，执行并发控制，实现更据库的全局一致性，执行并发控制，实现更新同步，提供全局恢复等功能。新同步，提供全局恢复等功能。分布式数据库管理系统概述分布式数据库管理系统概述 全局数据字典，存放全局概念模式、分片模全局数据字典，存放全局概念模式、分片模式、分布模式等的定义，以及各模式之间的式、分布模式等的定义，以及各模式之间的映像定义，存放有关用户存取权限的定义、映像定

24、义，存放有关用户存取权限的定义、完整性约束的定义等。完整性约束的定义等。 通信管理，在分布式数据库各场地之间传送通信管理，在分布式数据库各场地之间传送消息和数据，完成通信功能。消息和数据，完成通信功能。分布式数据库管理系统概述分布式数据库管理系统概述4D-DBMSD-DBMS的分类的分类按全局控制发生分类按全局控制发生分类 全局控制集中的全局控制集中的DDBMSDDBMS全局数据库器和全局数据字典集中于某一结全局数据库器和全局数据字典集中于某一结点，其优点是控制简单，容易实现更新一致点，其优点是控制简单，容易实现更新一致性，但该结点容易成为系统的瓶颈，系统也性，但该结点容易成为系统的瓶颈，系统

25、也较脆弱。较脆弱。分布式数据库管理系统概述分布式数据库管理系统概述 全局控制分散的全局控制分散的DDBMSDDBMS全局数据库器和全局数据字典分散在网络上全局数据库器和全局数据字典分散在网络上的每一个结点上，每个结点都能完成全局事的每一个结点上，每个结点都能完成全局事务的协调和局部数据库事务的控制功能。每务的协调和局部数据库事务的控制功能。每个结点既是全局事务的参与者，也是全局事个结点既是全局事务的参与者，也是全局事务的协调者。其优点是结点独立，自治性强，务的协调者。其优点是结点独立，自治性强，但全局控制的协调机制和一致性维护都比较但全局控制的协调机制和一致性维护都比较困难。困难。 全局控制部

26、分分散的全局控制部分分散的DDBMSDDBMS介于上述两者之间，根据应用的需要将全局介于上述两者之间，根据应用的需要将全局数据库管理器和全局数据字典分散在某些结数据库管理器和全局数据字典分散在某些结点上。点上。分布式数据库管理系统概述分布式数据库管理系统概述按局部按局部DBMSDBMS的类型分类的类型分类 同构型同构型DDBMSDDBMS每个结点的局部数据库具有相同的每个结点的局部数据库具有相同的DBMSDBMS。 异构型异构型DDBMSDDBMS各结点的局部数据库具有不同的各结点的局部数据库具有不同的DBMSDBMS分布式查询处理分布式查询处理4在分布式数据库系统中，数据分布在网在分布式数据

27、库系统中，数据分布在网络上的多个结点之中，其查询需要由多络上的多个结点之中，其查询需要由多个结点利用网络协作完成。在集中式数个结点利用网络协作完成。在集中式数据库中，查询优化的目标是产生最小磁据库中，查询优化的目标是产生最小磁盘盘I/O数，在分布式数据库中还要考虑网数，在分布式数据库中还要考虑网络的传输时间和各结点的并发执行。因络的传输时间和各结点的并发执行。因此，分布式查询处理较集中式数据库复此，分布式查询处理较集中式数据库复杂。杂。分布式查询处理分布式查询处理4在分布式数据库系统中，查询可分为三在分布式数据库系统中，查询可分为三类：局部查询，远程查询，全局查询。类：局部查询，远程查询，全局

28、查询。局部查询和远程查询只涉及单个结点的局部查询和远程查询只涉及单个结点的数据（本地的或远程的），可以采用集数据（本地的或远程的），可以采用集中式数据库的处理技术；二全局查询涉中式数据库的处理技术；二全局查询涉及到多个结点的数据，因此相对复杂的及到多个结点的数据，因此相对复杂的多。多。分布式查询处理分布式查询处理4分布式查询处理的过程包括：分布式查询处理的过程包括： 查询变换查询变换 将用户查询转换为析取范式或合取范式，并将用户查询转换为析取范式或合取范式，并进行语义分析，检查查询的正确性等工作。进行语义分析，检查查询的正确性等工作。分布式查询处理分布式查询处理 数据定位数据定位 数据定位的目

29、的是把用户定义在全局概念模式上的数据定位的目的是把用户定义在全局概念模式上的查询转换为定义在局部概念模式上的查询。由于它查询转换为定义在局部概念模式上的查询。由于它定义在片段上，也称为片段查询。设查询定义在片段上，也称为片段查询。设查询Q中包含中包含关系关系R1、R2、Rn，而且对于，而且对于1in，Ri已经被已经被划分为划分为m个片段个片段Ri1、Ri2、Rim， Ri=F(Ri1、Ri2、Rim)。Q Q的数据定位包括两步。第一步，的数据定位包括两步。第一步，对于对于1in，用用Ri=F(Ri1、Ri2、Rim)代替代替Q中的中的Ri ，得到一个等价的片段查询，得到一个等价的片段查询FQ。

30、第二步，进一。第二步，进一步加工步加工FQ，产生一个与，产生一个与FQ等价并且效率更高的片等价并且效率更高的片段查询。段查询。分布式查询处理分布式查询处理 全局查询优化全局查询优化 无论是集中式数据库还是分布式数据库其查无论是集中式数据库还是分布式数据库其查询策略的选择都是以执行查询的预期代价为询策略的选择都是以执行查询的预期代价为依据的。在集中式数据库中，查询执行的开依据的。在集中式数据库中，查询执行的开销主要是：销主要是：I/O+CPU代价。而在分布式数据代价。而在分布式数据库中查询执行的开销为：库中查询执行的开销为：I/O+CPU代价代价+通通信代价。因此在全局查询优化时需要选择执信代价

31、。因此在全局查询优化时需要选择执行操作的顺序，降低网络通信的开销。行操作的顺序，降低网络通信的开销。分布式查询处理分布式查询处理 局部查询优化局部查询优化 局部查询优化的目的是为每个局部查询选择局部查询优化的目的是为每个局部查询选择优化的执行计划，其方法与集中式数据库的优化的执行计划，其方法与集中式数据库的查询优化策略和方法相同。查询优化策略和方法相同。分布式查询处理分布式查询处理假定每条元组100bit大小4求供应红色零件的、北京的供应商号码select S.S# from S, P, SPwhere S.CITY = 北京 and S.S# = SP.S#and SP.P# = P.P#

32、and P.COLOR = 红色Site-ASite-BS(S#,CITY)104个元组个元组SP(S#,P#)106个元组个元组P(P#,COLOR)105个元组个元组网络网络传输速度传输速度104bps传输延迟传输延迟1s分布式查询处理分布式查询处理 传送时间T=总传输延迟+总数据量/传输速度 1.把关系P从B站传送到A站，在A站进行查询传送时间T=1+105 100 /104=103sS, SPP传传P分布式查询处理分布式查询处理 2.把关系S，SP从A站传送到B站，在B站进行查询传送时间T=2+(104+106)100/104104sS, SPP传传S,SP分布式查询处理分布式查询处理

33、在A站连接S与SP，选出城市为北京的元组（假定有105个），然后对其中每个元组的P#，询问B站，看其是否为红色。传送时间T=2 105sS, SPP问问答答分布式查询处理分布式查询处理在B站选出红色零件（假定有10个），然后对每个元组询问A站，看北京的供应商是否供应此零件。传送时间T=2 10=20s问问S, SPP答答分布式查询处理分布式查询处理5.在A站选出北京的供应商（105个），传送到B站，在B站完成查询。传送时间T=1+ 105100/104=103sS, SPP传传 (S) SP分布式查询处理分布式查询处理在B站选出红色零件（10个），把结果传送到A站，在A站完成查询。传送时间T=

34、1+ 10100/104=1.1sS, SPP传传 (P)分布式查询处理分布式查询处理4半连接运算半连接运算 定义定义半连接半连接R S=R（R S）=ABa1b1a2b1a2b3a2b4a3b3BCb1c1b2c2b5c1b5c2b6c4b7c2b8c3ABa1b1a2b1分布式查询处理分布式查询处理 半连接作用半连接作用找出找出R中能够与中能够与S中元组相连接的元组来，中元组相连接的元组来，类似于在连接之前先做选择和投影。类似于在连接之前先做选择和投影。R S = （R S） SR S = （S R） R 半连接的非对称性半连接的非对称性R S （S R）分布式查询处理分布式查询处理 半连

35、接在分布式数据库中的应用半连接在分布式数据库中的应用R与与S位于不同结点位于不同结点S1，S2上，其属性组分别为上，其属性组分别为R1，R2，要在，要在S1结点求结点求R和和S的连接结果。的连接结果。在在S1结点对结点对R做投影，将做投影，将R缩减为缩减为R，R=R1 R2（R）将将R 送往结点送往结点S2。在在S2结点完成结点完成S与与R的半连接操作，将的半连接操作，将S缩减为缩减为S，S = S R将将S送回结点送回结点S1 。在在S1结点完成结点完成R与与S的连接操作，的连接操作，R S = R S分布式查询处理分布式查询处理4通讯代价模型通讯代价模型TC（X）= C0+X*C1其中其中

36、X为数据传输量。为数据传输量。C0为两结点初始化一次传输所花费的开销。为两结点初始化一次传输所花费的开销。C1为传输率，即单位数据传输所花费的时间。为传输率，即单位数据传输所花费的时间。 采用半连接的通讯代价：采用半连接的通讯代价：CSJ=2C0+(size(R)*card(R)+size(S)*card(S)*C1不采用半连接的通讯代价：不采用半连接的通讯代价：CJN=C0+size(S)*card(S) *C1当当S中参与连接的元组足够少时采用半连接策略是有利的。中参与连接的元组足够少时采用半连接策略是有利的。分布式数据库系统的事务处理分布式数据库系统的事务处理4分布式事务分布式事务 数据

37、的分布导致事务具有了分布性。数据的分布导致事务具有了分布性。一个全局事务的执行被划分为在许多一个全局事务的执行被划分为在许多结点上子事务的执行。系统不但要保结点上子事务的执行。系统不但要保证每个子事务的原子性，还要保证全证每个子事务的原子性，还要保证全局事务的原子性。这不是哪一个局部局事务的原子性。这不是哪一个局部DBMS能够完成的，而是需要在结点能够完成的，而是需要在结点间进行协调。间进行协调。分布式数据库系统的事务处理分布式数据库系统的事务处理 示例：银行在两个帐户之间转帐。示例：银行在两个帐户之间转帐。对集中式数据库，单个事务对集中式数据库，单个事务T：A：=A - 100，B：=B+1

38、00对于分布式数据库，假定对于分布式数据库，假定A在在S1,S2各有一副本，各有一副本，B在在S3,S4各有一副本，用户请求在各有一副本，用户请求在S5发出，则分发出，则分布事务布事务T由由T1,T2,T3,T4,T5构成：构成：T1, T2： A：=A - 100 T3, T4 ：B：=B + 100T5 ： 结果返回给用户结果返回给用户分布式数据库系统的事务处理分布式数据库系统的事务处理4分布式事务处理器分布式事务处理器 事务管理器事务管理器TM：管理那些访问存储在一个局部结点：管理那些访问存储在一个局部结点中的数据的事务。事务可以是局部事务，也可以是中的数据的事务。事务可以是局部事务，也

39、可以是全局事务的一部分。全局事务的一部分。 事务协调器事务协调器TC：协调该结点上发起的各事务（局部：协调该结点上发起的各事务（局部的或全局的）的执行。的或全局的）的执行。TC1TM1TCnTMn分布式数据库系统的事务处理分布式数据库系统的事务处理 事务管理器功能事务管理器功能 维护一个用于恢复的日志。维护一个用于恢复的日志。 参与适当的并发控制模式，以协调在该结点上执行的参与适当的并发控制模式，以协调在该结点上执行的事务的并发执行事务的并发执行。 事务协调器功能事务协调器功能 启动事务的执行。启动事务的执行。 将事务分解为若干子事务，并将子事务分派到适当的将事务分解为若干子事务，并将子事务分

40、派到适当的结点上去执行。结点上去执行。 协调事务的终止，保证事务在所有的结点上都提交或协调事务的终止，保证事务在所有的结点上都提交或都中止都中止。 一个全局事务的各个子事务要么全部执行，要么全部中一个全局事务的各个子事务要么全部执行，要么全部中止。止。分布式数据库系统的事务处理分布式数据库系统的事务处理4事务两阶段提交协议事务两阶段提交协议假定事务假定事务T在结点在结点Si发起，发起， 阶段阶段1： 事务协调器事务协调器TCi向日志中加入一条记录向日志中加入一条记录，并强，并强制该日志写入稳定存储器中。制该日志写入稳定存储器中。 TCi将消息将消息发送到执行发送到执行T的所有结点上。的所有结点

41、上。 当某结点接受到上述消息时，该结点的当某结点接受到上述消息时，该结点的TM回答确定是否回答确定是否提交提交T中属于它的那部分，若否，则中属于它的那部分，若否，则TM将记录将记录加加入到日志中，并向入到日志中，并向TCi发送消息发送消息。若是，则。若是，则TM将记录将记录加入到日志中，并将日志强制写入稳定加入到日志中，并将日志强制写入稳定存储器中，并向存储器中，并向TCi发送消息发送消息。分布式数据库系统的事务处理分布式数据库系统的事务处理 阶段阶段2： 当当TCi收到所有结点对收到所有结点对消息的回答时，或消息的回答时，或等待响应的时间已过，等待响应的时间已过，TCi决定事务决定事务T是提

42、交还是中是提交还是中止。止。 如果如果TCi 收到的都是收到的都是消息，事务就可以提消息，事务就可以提交，否则事务必须被中止。根据结果的不同向日志交，否则事务必须被中止。根据结果的不同向日志中写入中写入 或者或者，并强制将日志写，并强制将日志写入稳定存储器中。入稳定存储器中。 向所有参与的结点发送向所有参与的结点发送消息消息或或。 结点收到此消息后，就把该消息记入日志中。（向结点收到此消息后，就把该消息记入日志中。（向TCi发送消息发送消息； TCi收到该消息后，收到该消息后，将记录将记录加入到日志中）加入到日志中）。分布式并发控制技术分布式并发控制技术4分布式锁技术分布式锁技术 若分布式数据

43、库中没有重复存储的数据，可若分布式数据库中没有重复存储的数据，可以采用如下的分布式锁技术：每个结点保留以采用如下的分布式锁技术：每个结点保留一个局部锁管理器，处理对存储在本地的数一个局部锁管理器，处理对存储在本地的数据加锁和释放锁的请求。当事务据加锁和释放锁的请求。当事务T希望对结希望对结点点Si上的数据项上的数据项Q加锁时，加锁时，T简单的向结点简单的向结点上的锁管理器发出一个加锁请求。分布式锁上的锁管理器发出一个加锁请求。分布式锁技术具有实现简单的特点，它处理一个加锁技术具有实现简单的特点，它处理一个加锁请求需要两次通信，处理释放锁请求需要一请求需要两次通信，处理释放锁请求需要一次通信。但

44、其死锁处理较为复杂。次通信。但其死锁处理较为复杂。分布式并发控制技术分布式并发控制技术4集中式锁技术集中式锁技术 集中式锁技术仅有一个锁管理器，这个锁管理器位集中式锁技术仅有一个锁管理器，这个锁管理器位于唯一一个结点（如于唯一一个结点（如Si）上。所有的加锁和释放锁）上。所有的加锁和释放锁的请求都在该结点上处理。集中式锁技术具有以下的请求都在该结点上处理。集中式锁技术具有以下优点：优点： 实现简单实现简单 加锁请求需要两次通信，释放锁请求需要一次通加锁请求需要两次通信，释放锁请求需要一次通信。信。 死锁处理简单死锁处理简单 可按照集中式数据库的方法进行处理可按照集中式数据库的方法进行处理 集中

45、式锁技术具有以下缺点：集中式锁技术具有以下缺点： 瓶颈问题瓶颈问题 Si是一个锁管理瓶颈是一个锁管理瓶颈 脆弱性脆弱性 如果如果Si出现故障，系统无法正常运行。出现故障，系统无法正常运行。分布式并发控制技术分布式并发控制技术4混合锁技术混合锁技术 混合锁技术是集中式和分布式锁技术的折中。混合锁技术是集中式和分布式锁技术的折中。这种技术设置多个锁管理器，每个锁管理器这种技术设置多个锁管理器，每个锁管理器管理一组数据的加锁和释放锁的请求。每个管理一组数据的加锁和释放锁的请求。每个锁管理器位于不同的结点上。锁管理器位于不同的结点上。分布式并发控制技术分布式并发控制技术4以多为主的锁协议以多为主的锁协

46、议 系统在每个结点上有一个锁管理器。在任何系统在每个结点上有一个锁管理器。在任何结点结点Si上的锁管理器管理存储在上的锁管理器管理存储在Si上的所有上的所有数据项副本的加锁和释放锁的请求。当事务数据项副本的加锁和释放锁的请求。当事务T请求对数据项请求对数据项Q加锁时，如果加锁时，如果n个结点存储个结点存储Q的副本，则的副本，则T要向要向n/2以上的存储以上的存储Q副本的副本的结点发出加锁请求。结点发出加锁请求。分布式并发控制技术分布式并发控制技术4区分锁类型的锁协议区分锁类型的锁协议 每个结点上有一个锁管理器。每个锁管理器每个结点上有一个锁管理器。每个锁管理器管理所在结点上存储的数据的加锁和释

47、放锁管理所在结点上存储的数据的加锁和释放锁的请求。共享锁和互斥锁采用不同的方式进的请求。共享锁和互斥锁采用不同的方式进行处理。当事务行处理。当事务T需要在数据项加共享锁时，需要在数据项加共享锁时，T直接向一个存储该数据项副本的结点的锁直接向一个存储该数据项副本的结点的锁管理器发出加锁请求。当事务管理器发出加锁请求。当事务T需要在数据需要在数据项上加互斥锁时，项上加互斥锁时，T要向所有包含该数据项要向所有包含该数据项副本的结点的锁管理器发出加锁请求。副本的结点的锁管理器发出加锁请求。分布式并发控制技术分布式并发控制技术4主副本锁协议主副本锁协议 在数据项在数据项Q具有多个副本的情况下，选择一具有

48、多个副本的情况下，选择一个节点上的副本作为数据主副本，此节点称个节点上的副本作为数据主副本，此节点称为该数据项为该数据项Q的主节点。的主节点。 当有事务请求对数据项当有事务请求对数据项Q的封锁时，它仅需的封锁时，它仅需要向要向Q的主节点发出一个加锁请求。的主节点发出一个加锁请求。 优点：简单优点：简单 缺点：对主节点依赖大，如果主节点不可用，缺点：对主节点依赖大，如果主节点不可用，则数据项的其他副本也不可用。则数据项的其他副本也不可用。分布式死锁处理技术分布式死锁处理技术T1T2T5T3结点1T4T2T3结点2T1T4T2T3全局等待图T5分布式死锁处理技术分布式死锁处理技术4集中式方法集中式

49、方法 在集中式方法中，全局等待图（局部等待图的并集）在集中式方法中，全局等待图（局部等待图的并集）被保存在一个称为死锁检测器的特殊结点上。全局被保存在一个称为死锁检测器的特殊结点上。全局等待图在下列事件发生时被构造或更新：等待图在下列事件发生时被构造或更新： 某个局部等待图被加入一条新边或删除一条边。某个局部等待图被加入一条新边或删除一条边。 局部等待图发生了较大改变。局部等待图发生了较大改变。 协调器需要触发死锁检测算法。协调器需要触发死锁检测算法。 当死锁检测器被触发时，协调器检查它的全局等待当死锁检测器被触发时，协调器检查它的全局等待图。如果发现一个环，就选择要放弃的事务解决死图。如果发

50、现一个环，就选择要放弃的事务解决死锁。协调器需通知所有结点放弃的是哪个事务，使锁。协调器需通知所有结点放弃的是哪个事务，使其他结点也放弃该事务。其他结点也放弃该事务。分布式死锁处理技术分布式死锁处理技术4分布式方法分布式方法 在分布式方法中，所有结点对于死锁检测具在分布式方法中，所有结点对于死锁检测具有相同的职责。每个结点都根据系统的动态有相同的职责。每个结点都根据系统的动态行为构造一个全局等待图的子等待图。子等行为构造一个全局等待图的子等待图。子等待图必须满足：如果有死锁存在，则至少一待图必须满足：如果有死锁存在，则至少一个子等待图中出现环。局部等待图中增加了个子等待图中出现环。局部等待图中

51、增加了一个结点一个结点Tex，用以表示外结点与本结点发，用以表示外结点与本结点发生等待关系的子事务。如果局部等待图中含生等待关系的子事务。如果局部等待图中含有一个不包含有一个不包含Tex的环，表明系统处于死锁的环，表明系统处于死锁状态。如果存在一个包含状态。如果存在一个包含Tex的环，需要通的环，需要通过分布式死锁检测算法确定是否出现死锁。过分布式死锁检测算法确定是否出现死锁。分布式死锁处理技术分布式死锁处理技术 如果结点如果结点Si的局部等待图中有一个包含的局部等待图中有一个包含Tex的的环：环： Tex Tk1 Tk2 Tkn Tex，说，说明明Si上的事务上的事务Tkn正在等待其他结点（如正在等待其他结点（如Sj）上的数据项。则结点上的数据项。则结点Si向向Sj发送含有这个环发送含有这个环的死锁检测信息。结点的死锁检测信息。结点Sj根据这一信息修改根据这一信息修改自己的局部等待图，搜索是否存在一个不含自己的局部等待图，搜索是否存在一个不含有有Tex的环，若有则发生死锁。如果存在一的环，若有则发生死锁。如果存在一个含有个含有Tex的环，则继续上述过程，直到确的环，则继续上述过程，直到确定是否存在死锁。定是否存在死锁。分布式死锁处理技术分布式死锁处理技术T1T2T5T3Tex结点1TexT4T2T3结点2TexT4T2T3结点2