数据库系统概论第十四章精品文稿.ppt

《数据库系统概论第十四章精品文稿.ppt》由会员分享，可在线阅读，更多相关《数据库系统概论第十四章精品文稿.ppt（62页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

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

2、立处理的能力（称为场地自治），可以执行局部应用（只对本结点数据进行存取的应用），同时每个结点（只对本结点数据进行存取的应用），同时每个结点也能通过网络通讯支持全局应用（指存取两个或两个也能通过网络通讯支持全局应用（指存取两个或两个以上的结点的数据库应用）。以上的结点的数据库应用）。分布式数据库强调场地自治性（局部应用）以及自治场地之分布式数据库强调场地自治性（局部应用）以及自治场地之间的协作性（全局应用）。间的协作性（全局应用）。第3页，本讲稿共62页分布式数据库和分布式数据库系统分布式数据库和分布式数据库系统4分布式数据库具有以下两个特点：分布式数据库具有以下两个特点：分布性分布性分布性有两

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

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

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

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

7、各局部的DBMS可以独立的管理局部的数可以独立的管理局部的数据库，具有自治功能。同时系统又设有集中控制据库，具有自治功能。同时系统又设有集中控制机构，协调各局部机构，协调各局部DBMS的工作，执行全局应用。的工作，执行全局应用。第6页，本讲稿共62页分布式数据库和分布式数据库系统分布式数据库和分布式数据库系统适当增加数据冗余适当增加数据冗余在分布式数据库系统中适当的增加了冗余数据，在分布式数据库系统中适当的增加了冗余数据，在不同的结点存储同一数据的多个副本，其原因在不同的结点存储同一数据的多个副本，其原因是：一提高系统的可靠性、可用性，当某一结点是：一提高系统的可靠性、可用性，当某一结点出现故

8、障时，系统可以对另一结点的相同副本进出现故障时，系统可以对另一结点的相同副本进行操作，不会因为一处故障而造成整个系统的瘫行操作，不会因为一处故障而造成整个系统的瘫痪；二是提高系统性能，系统可以选择用户最近痪；二是提高系统性能，系统可以选择用户最近的数据副本来进行操作，减少通信代价，改善整的数据副本来进行操作，减少通信代价，改善整个系统的性能。个系统的性能。第7页，本讲稿共62页分布式数据库和分布式数据库系统分布式数据库和分布式数据库系统全局的一致性、可串行性和可恢复性全局的一致性、可串行性和可恢复性分布式数据库系统中各局部数据库应满足集中式分布式数据库系统中各局部数据库应满足集中式数据库的一致

9、性、并发事务的可串行性和可恢复数据库的一致性、并发事务的可串行性和可恢复性。除此之外还应保证数据库的全局一致性、全性。除此之外还应保证数据库的全局一致性、全局并发事务的可串行性和系统全局的可恢复性。局并发事务的可串行性和系统全局的可恢复性。这是因为在分布式数据库系统中全局应用要涉及这是因为在分布式数据库系统中全局应用要涉及两个以上结点的数据，全局事务可能由不同结点两个以上结点的数据，全局事务可能由不同结点上的多个操作组成。上的多个操作组成。第8页，本讲稿共62页分布式数据库和分布式数据库系统分布式数据库和分布式数据库系统4分布式数据库系统的目标分布式数据库系统的目标适应部门分布的组织结构，降低

10、费用适应部门分布的组织结构，降低费用使用数据库的单位在组织上常常是分布的，在地使用数据库的单位在组织上常常是分布的，在地理上也是分布的。分布式数据库系统的结构符合理上也是分布的。分布式数据库系统的结构符合上述分布的组织结构，允许各个部门将自己常用上述分布的组织结构，允许各个部门将自己常用的数据存储在本地，降低了通信代价，提高了响的数据存储在本地，降低了通信代价，提高了响应速度。应速度。提高系统的可靠性和可用性提高系统的可靠性和可用性将数据分布于多个结点，并适当增加冗余度，可将数据分布于多个结点，并适当增加冗余度，可以提供更好的可靠性。以提供更好的可靠性。第9页，本讲稿共62页分布式数据库和分布

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

12、地将一个新结点纳入系统，而不影响现有够方便地将一个新结点纳入系统，而不影响现有系统的结构和系统的正常运行，提供了逐步扩展系统的结构和系统的正常运行，提供了逐步扩展系统能力的较好途径。系统能力的较好途径。第10页，本讲稿共62页分布式数据库的体系结构分布式数据库的体系结构全局全局外模式外模式全局全局外模式外模式全局全局概念模式概念模式分片模式分片模式分布模式分布模式局部局部概念模式概念模式局部局部概念模式概念模式局部局部内模式内模式局部局部内模式内模式局部局部DB局部局部DB全局全局DBMS局部局部DBMS映像1映像2映像3映像4第11页，本讲稿共62页分布式数据库的体系结构分布式数据库的体系结

13、构4全局外模式全局外模式全局应用的用户视图，是全局概念模式的子集。全局应用的用户视图，是全局概念模式的子集。4全局概念模式全局概念模式定义分布式数据库中数据的整体逻辑结构，使得数据如同定义分布式数据库中数据的整体逻辑结构，使得数据如同没有分布一样。没有分布一样。4分片模式分片模式每一个全局关系可以分为若干互不相交的部分，每一部分每一个全局关系可以分为若干互不相交的部分，每一部分称为一个片段。分片模式定义片段以及全局关系到片段的称为一个片段。分片模式定义片段以及全局关系到片段的映像。映像。4分布模式分布模式定义片段的存放结点。定义片段的存放结点。第12页，本讲稿共62页分布式数据库的体系结构分布

14、式数据库的体系结构4分布（网络）透明性分布（网络）透明性分片透明性分片透明性用户或应用程序只对全局关系进行操作而不必考虑关系的分用户或应用程序只对全局关系进行操作而不必考虑关系的分片。如果分片模式改变了，通过调整全局模式与分片模式之片。如果分片模式改变了，通过调整全局模式与分片模式之间的映象关系来保持全局模式不变。间的映象关系来保持全局模式不变。位置透明性位置透明性用户或应用程序不必了解片段的存储位置。用户或应用程序不必了解片段的存储位置。局部数据模型透明性局部数据模型透明性用户或应用程序不必了解局部场地上使用的是哪种数据用户或应用程序不必了解局部场地上使用的是哪种数据模型。模型。第13页，本

15、讲稿共62页分布式数据库的体系结构分布式数据库的体系结构4示例：示例：设有全局关系S，它被划分为两个片段S-A（本科生），S-B（研究生），S-B有两个副本。SS-AS-BS-AS-BS-BSite-1Site-2Site-3全局关系全局关系片段片段物理存储物理存储第14页，本讲稿共62页分布式数据库设计分布式数据库设计4数据在分布式数据库中的存储途径数据在分布式数据库中的存储途径数据的重复存储数据的重复存储系统在两个或两个以上结点维护关系系统在两个或两个以上结点维护关系R的几个完全相同的副的几个完全相同的副本。如果系统的每个结点都存储本。如果系统的每个结点都存储R的一个副本，则称这的一个副本

16、，则称这种重复存储为完全重复存储。数据重复存储具有以下几种重复存储为完全重复存储。数据重复存储具有以下几个优点：个优点：可用性强可用性强 如果某个存储如果某个存储R的结点出了故障，系统仍然可以使用其它结点上的副本继的结点出了故障，系统仍然可以使用其它结点上的副本继续处理用户查询，使系统正常运行。续处理用户查询，使系统正常运行。增强并行性增强并行性 由于由于R的重复存储，可以使更多的用户并行地查询的重复存储，可以使更多的用户并行地查询R。数据的重复存储也会带来一些问题，如增加了更新操作的开销，数据的重复存储也会带来一些问题，如增加了更新操作的开销，加大了并行控制的难度加大了并行控制的难度第15页

17、，本讲稿共62页分布式数据库设计分布式数据库设计分片存储分片存储关系被划分为几个片段，各个片段存储在不关系被划分为几个片段，各个片段存储在不同的结点上。将数据分片，使数据存放的单同的结点上。将数据分片，使数据存放的单位不是关系而是片段，这既有利于按照用户位不是关系而是片段，这既有利于按照用户的需求较好地组织数据的分布，也有利于控的需求较好地组织数据的分布，也有利于控制数据的冗余度。分片时必须遵循以下原则：制数据的冗余度。分片时必须遵循以下原则：完全性：被划分关系中的每个元组必须属于一完全性：被划分关系中的每个元组必须属于一个片段。个片段。不相交性：同一个关系的片段互不相交。不相交性：同一个关系

18、的片段互不相交。可重构性：如果可重构性：如果R被划分为片段被划分为片段R1、R2、Rn，则则R能从能从R1、R2、Rn恢复出来。恢复出来。第16页，本讲稿共62页分布式数据库设计分布式数据库设计分片方式分片方式水平分片水平分片垂直分片垂直分片导出分片导出分片混合分片混合分片第17页，本讲稿共62页分布式数据库设计分布式数据库设计水平分片水平分片将关系将关系r依照一定条件按行分为不相交的若干子依照一定条件按行分为不相交的若干子集集r1，r2，rn，每个子集每个子集ri称为一个水平片段。称为一个水平片段。一个水平片段可以看成是关系上的一个选择。一个水平片段可以看成是关系上的一个选择。ri=P（i）

19、（r）如如C_S=DNO=D08（S）关系的重构可以通过并运算来实现。关系的重构可以通过并运算来实现。r=r1 r2rn第18页，本讲稿共62页分布式数据库设计分布式数据库设计垂直分片垂直分片将关系将关系r按列分为若干属性子集按列分为若干属性子集r1，r2，rn，每每个子集个子集ri称为一个垂直片段。称为一个垂直片段。一个垂直片段可以看成是关系上的一个投影。一个垂直片段可以看成是关系上的一个投影。ri=Ri（r）其中其中Ri是是r的一个属性子集。的一个属性子集。如如P_S=PNO，SAL（P）关系的重构可以通过连接运算来实现。关系的重构可以通过连接运算来实现。r=r1 r2 rn所有分片都包括

20、关系的键所有分片都包括关系的键第19页，本讲稿共62页分布式数据库设计分布式数据库设计导出分片导出分片导出水平分片，分片的条件不是关系本身属性条件，导出水平分片，分片的条件不是关系本身属性条件，而是其它关系的属性条件。而是其它关系的属性条件。如如SC（SNO，CNO，G）按学生系别分片。）按学生系别分片。混合分片混合分片关系按某种方式分片后，得到的片段再按另一种方式关系按某种方式分片后，得到的片段再按另一种方式继续分片。继续分片。如如SC（SNO，CNO，G）按学生系别分片，再对每个）按学生系别分片，再对每个片段按成绩片段按成绩（及格，不及格）分片。及格，不及格）分片。第20页，本讲稿共62页

21、分布式数据库设计分布式数据库设计组合存储组合存储这种方法是重复存储和分片存储相结合的方这种方法是重复存储和分片存储相结合的方法。关系被划分为几个片段，系统为每个片法。关系被划分为几个片段，系统为每个片段维护几个副本，每个副本存放于不同的结段维护几个副本，每个副本存放于不同的结点上。点上。第21页，本讲稿共62页分布式数据库设计分布式数据库设计4命名和局部自治性命名和局部自治性每个数据项（关系、副本、片段）必须有唯每个数据项（关系、副本、片段）必须有唯一的名字，在分布式数据库系统中必须保证一的名字，在分布式数据库系统中必须保证在不同的结点上不会用同一个名字来代表不在不同的结点上不会用同一个名字来

22、代表不同的数据项。同的数据项。途径途径1：名字服务器：名字服务器所有名字都在名字服务器中注册，每个名字对应所有名字都在名字服务器中注册，每个名字对应一个数据项。一个数据项。缺陷：名字服务器成为名字解析的瓶颈；其故障缺陷：名字服务器成为名字解析的瓶颈；其故障将影响整个系统的运行；局部自治性降低。将影响整个系统的运行；局部自治性降低。第22页，本讲稿共62页分布式数据库设计分布式数据库设计途径途径2：将结点标识作为前缀加到该结点数：将结点标识作为前缀加到该结点数据项的名字前面。使用这一方法，能够保据项的名字前面。使用这一方法，能够保证名字的唯一性，不须中央控制，局部自证名字的唯一性，不须中央控制，

23、局部自治性提高；但不能保证网络透明性。治性提高；但不能保证网络透明性。第23页，本讲稿共62页分布式数据库管理系统概述分布式数据库管理系统概述4D-DBMS由四个部分组成：由四个部分组成：LDBMS，局部场地上的，局部场地上的DBMS，主要功能，主要功能是建立和管理局部数据库，提供场地自治能是建立和管理局部数据库，提供场地自治能力，执行局部应用以及全局查询的子查询。力，执行局部应用以及全局查询的子查询。GDBMS，全局数据库管理系统，主要功能，全局数据库管理系统，主要功能是提供分布透明性，协调全局事务的执行，是提供分布透明性，协调全局事务的执行，协调各局部协调各局部DBMS以完成全局应用，保证

24、数以完成全局应用，保证数据库的全局一致性，执行并发控制，实现更据库的全局一致性，执行并发控制，实现更新同步，提供全局恢复等功能。新同步，提供全局恢复等功能。第24页，本讲稿共62页分布式数据库管理系统概述分布式数据库管理系统概述全局数据字典，存放全局概念模式、分片模全局数据字典，存放全局概念模式、分片模式、分布模式等的定义，以及各模式之间的式、分布模式等的定义，以及各模式之间的映像定义，存放有关用户存取权限的定义、映像定义，存放有关用户存取权限的定义、完整性约束的定义等。完整性约束的定义等。通信管理，在分布式数据库各场地之间传送通信管理，在分布式数据库各场地之间传送消息和数据，完成通信功能。消

25、息和数据，完成通信功能。第25页，本讲稿共62页分布式数据库管理系统概述分布式数据库管理系统概述4D-DBMSD-DBMS的分类的分类按全局控制发生分类按全局控制发生分类全局控制集中的全局控制集中的DDBMSDDBMS全局数据库器和全局数据字典集中于某一结点，其全局数据库器和全局数据字典集中于某一结点，其优点是控制简单，容易实现更新一致性，但该结点优点是控制简单，容易实现更新一致性，但该结点容易成为系统的瓶颈，系统也较脆弱。容易成为系统的瓶颈，系统也较脆弱。第26页，本讲稿共62页分布式数据库管理系统概述分布式数据库管理系统概述全局控制分散的全局控制分散的DDBMSDDBMS全局数据库器和全局

26、数据字典分散在网络上的每一全局数据库器和全局数据字典分散在网络上的每一个结点上，每个结点都能完成全局事务的协调和局个结点上，每个结点都能完成全局事务的协调和局部数据库事务的控制功能。每个结点既是全局事务部数据库事务的控制功能。每个结点既是全局事务的参与者，也是全局事务的协调者。其优点是结点的参与者，也是全局事务的协调者。其优点是结点独立，自治性强，但全局控制的协调机制和一致性独立，自治性强，但全局控制的协调机制和一致性维护都比较困难。维护都比较困难。全局控制部分分散的全局控制部分分散的DDBMSDDBMS介于上述两者之间，根据应用的需要将全局数据库管介于上述两者之间，根据应用的需要将全局数据库

27、管理器和全局数据字典分散在某些结点上。理器和全局数据字典分散在某些结点上。第27页，本讲稿共62页分布式数据库管理系统概述分布式数据库管理系统概述按局部按局部DBMSDBMS的类型分类的类型分类同构型同构型DDBMSDDBMS每个结点的局部数据库具有相同的每个结点的局部数据库具有相同的DBMSDBMS。异构型异构型DDBMSDDBMS各结点的局部数据库具有不同的各结点的局部数据库具有不同的DBMSDBMS第28页，本讲稿共62页分布式查询处理分布式查询处理4在分布式数据库系统中，数据分布在网在分布式数据库系统中，数据分布在网络上的多个结点之中，其查询需要由多络上的多个结点之中，其查询需要由多个

28、结点利用网络协作完成。在集中式数个结点利用网络协作完成。在集中式数据库中，查询优化的目标是产生最小磁据库中，查询优化的目标是产生最小磁盘盘I/O数，在分布式数据库中还要考虑网数，在分布式数据库中还要考虑网络的传输时间和各结点的并发执行。因络的传输时间和各结点的并发执行。因此，分布式查询处理较集中式数据库复此，分布式查询处理较集中式数据库复杂。杂。第29页，本讲稿共62页分布式查询处理分布式查询处理4在分布式数据库系统中，查询可分为三在分布式数据库系统中，查询可分为三类：局部查询，远程查询，全局查询。类：局部查询，远程查询，全局查询。局部查询和远程查询只涉及单个结点的局部查询和远程查询只涉及单个

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

30、模式上的查询转换为数据定位的目的是把用户定义在全局概念模式上的查询转换为定义在局部概念模式上的查询。由于它定义在片段上，也称定义在局部概念模式上的查询。由于它定义在片段上，也称为片段查询。设查询为片段查询。设查询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。第二步，进一步加。第二步，进

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

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

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

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

35、传传(S)SP第40页，本讲稿共62页分布式查询处理分布式查询处理在B站选出红色零件（10个），把结果传送到A站，在A站完成查询。传送时间T=1+10100/104=1.1sS,SPP传传(P)第41页，本讲稿共62页分布式查询处理分布式查询处理4半连接运算半连接运算定义定义半连接半连接R S=R（R S）=ABa1b1a2b1a2b3a2b4a3b3BCb1c1b2c2b5c1b5c2b6c4b7c2b8c3ABa1b1a2b1第42页，本讲稿共62页分布式查询处理分布式查询处理半连接作用半连接作用找出找出R中能够与中能够与S中元组相连接的元组来，中元组相连接的元组来，类似于在连接之前先做选

36、择和投影。类似于在连接之前先做选择和投影。R S=（R S）SR S=（S R）R半连接的非对称性半连接的非对称性R S （S R）第43页，本讲稿共62页分布式查询处理分布式查询处理半连接在分布式数据库中的应用半连接在分布式数据库中的应用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送回

37、结点送回结点S1。在在S1结点完成结点完成R与与S的连接操作，的连接操作，R S=R S第44页，本讲稿共62页分布式查询处理分布式查询处理4通讯代价模型通讯代价模型TC（X）=C0+X*C1其中其中X为数据传输量。为数据传输量。C0为两结点初始化一次传输所花费的开销。为两结点初始化一次传输所花费的开销。C1为传输率，即单位数据传输所花费的时间。为传输率，即单位数据传输所花费的时间。采用半连接的通讯代价：采用半连接的通讯代价：CSJ=2C0+(size(R)*card(R)+size(S)*card(S)*C1不采用半连接的通讯代价：不采用半连接的通讯代价：CJN=C0+size(S)*car

38、d(S)*C1当当S中参与连接的元组足够少时采用半连接策略是有利的。中参与连接的元组足够少时采用半连接策略是有利的。第45页，本讲稿共62页分布式数据库系统的事务处理分布式数据库系统的事务处理4分布式事务分布式事务数据的分布导致事务具有了分布性。一个数据的分布导致事务具有了分布性。一个全局事务的执行被划分为在许多结点上子全局事务的执行被划分为在许多结点上子事务的执行。系统不但要保证每个子事务事务的执行。系统不但要保证每个子事务的原子性，还要保证全局事务的原子性。的原子性，还要保证全局事务的原子性。这不是哪一个局部这不是哪一个局部DBMS能够完成的，而能够完成的，而是需要在结点间进行协调。是需要

39、在结点间进行协调。第46页，本讲稿共62页分布式数据库系统的事务处理分布式数据库系统的事务处理示例：银行在两个帐户之间转帐。示例：银行在两个帐户之间转帐。对集中式数据库，单个事务对集中式数据库，单个事务T：A：=A-100，B：=B+100对于分布式数据库，假定对于分布式数据库，假定A在在S1,S2各有一副本，各有一副本，B在在S3,S4各有一副本，用户请求在各有一副本，用户请求在S5发出，则分布事务发出，则分布事务T由由T1,T2,T3,T4,T5构成：构成：T1,T2：A：=A-100 T3,T4：B：=B+100T5：结果返回给用户结果返回给用户第47页，本讲稿共62页分布式数据库系统的

40、事务处理分布式数据库系统的事务处理4分布式事务处理器分布式事务处理器事务管理器事务管理器TM：管理那些访问存储在一个局部结点中：管理那些访问存储在一个局部结点中的数据的事务。事务可以是局部事务，也可以是全局的数据的事务。事务可以是局部事务，也可以是全局事务的一部分。事务的一部分。事务协调器事务协调器TC：协调该结点上发起的各事务（局部的或全局：协调该结点上发起的各事务（局部的或全局的）的执行。的）的执行。TC1TM1TCnTMn第48页，本讲稿共62页分布式数据库系统的事务处理分布式数据库系统的事务处理事务管理器功能事务管理器功能维护一个用于恢复的日志。维护一个用于恢复的日志。参与适当的并发控

41、制模式，以协调在该结点上执行的事务的并参与适当的并发控制模式，以协调在该结点上执行的事务的并发执行发执行。事务协调器功能事务协调器功能启动事务的执行。启动事务的执行。将事务分解为若干子事务，并将子事务分派到适当的结将事务分解为若干子事务，并将子事务分派到适当的结点上去执行。点上去执行。协调事务的终止，保证事务在所有的结点上都提交或都中止。协调事务的终止，保证事务在所有的结点上都提交或都中止。一个全局事务的各个子事务要么全部执行，要么全部中止。一个全局事务的各个子事务要么全部执行，要么全部中止。第49页，本讲稿共62页分布式数据库系统的事务处理分布式数据库系统的事务处理4事务两阶段提交协议事务两

42、阶段提交协议假定事务假定事务T在结点在结点Si发起，发起，阶段阶段1：事务协调器事务协调器TCi向日志中加入一条记录向日志中加入一条记录，并强制该日，并强制该日志写入稳定存储器中。志写入稳定存储器中。TCi将消息将消息发送到执行发送到执行T的所有结点上。的所有结点上。当某结点接受到上述消息时，该结点的当某结点接受到上述消息时，该结点的TM回答确定是否提交回答确定是否提交T中属中属于它的那部分，若否，则于它的那部分，若否，则TM将记录将记录加入到日志中，并向加入到日志中，并向TCi发送消息发送消息。若是，则。若是，则TM将记录将记录加入到日志加入到日志中，并将日志强制写入稳定存储器中，并向中，并

43、将日志强制写入稳定存储器中，并向TCi发送消息发送消息。第50页，本讲稿共62页分布式数据库系统的事务处理分布式数据库系统的事务处理阶段阶段2：当当TCi收到所有结点对收到所有结点对消息的回答时，或等消息的回答时，或等待响应的时间已过，待响应的时间已过，TCi决定事务决定事务T是提交还是中止。是提交还是中止。如果如果TCi 收到的都是收到的都是消息，事务就可以提交，否消息，事务就可以提交，否则事务必须被中止。根据结果的不同向日志中写入则事务必须被中止。根据结果的不同向日志中写入 或者或者，并强制将日志写入稳定存储器中。，并强制将日志写入稳定存储器中。向所有参与的结点发送消息向所有参与的结点发送

44、消息或或。结点收到此消息后，就把该消息记入日志中。（向结点收到此消息后，就把该消息记入日志中。（向TCi发发送消息送消息；TCi收到该消息后，将记录收到该消息后，将记录加入到日志中）。加入到日志中）。第51页，本讲稿共62页分布式并发控制技术分布式并发控制技术4分布式锁技术分布式锁技术若分布式数据库中没有重复存储的数据，可若分布式数据库中没有重复存储的数据，可以采用如下的分布式锁技术：每个结点保留以采用如下的分布式锁技术：每个结点保留一个局部锁管理器，处理对存储在本地的数一个局部锁管理器，处理对存储在本地的数据加锁和释放锁的请求。当事务据加锁和释放锁的请求。当事务T希望对结希望对结点点Si上的

45、数据项上的数据项Q加锁时，加锁时，T简单的向结点上简单的向结点上的锁管理器发出一个加锁请求。分布式锁技的锁管理器发出一个加锁请求。分布式锁技术具有实现简单的特点，它处理一个加锁请术具有实现简单的特点，它处理一个加锁请求需要两次通信，处理释放锁请求需要一次求需要两次通信，处理释放锁请求需要一次通信。但其死锁处理较为复杂。通信。但其死锁处理较为复杂。第52页，本讲稿共62页分布式并发控制技术分布式并发控制技术4集中式锁技术集中式锁技术集中式锁技术仅有一个锁管理器，这个锁管理器位于唯集中式锁技术仅有一个锁管理器，这个锁管理器位于唯一一个结点（如一一个结点（如Si）上。所有的加锁和释放锁的请求都）上。

46、所有的加锁和释放锁的请求都在该结点上处理。集中式锁技术具有以下优点：在该结点上处理。集中式锁技术具有以下优点：实现简单实现简单 加锁请求需要两次通信，释放锁请求需要一次通信。加锁请求需要两次通信，释放锁请求需要一次通信。死锁处理简单死锁处理简单 可按照集中式数据库的方法进行处理可按照集中式数据库的方法进行处理集中式锁技术具有以下缺点：集中式锁技术具有以下缺点：瓶颈问题瓶颈问题 Si是一个锁管理瓶颈是一个锁管理瓶颈脆弱性脆弱性 如果如果Si出现故障，系统无法正常运行。出现故障，系统无法正常运行。第53页，本讲稿共62页分布式并发控制技术分布式并发控制技术4混合锁技术混合锁技术混合锁技术是集中式和

47、分布式锁技术的折中。混合锁技术是集中式和分布式锁技术的折中。这种技术设置多个锁管理器，每个锁管理器这种技术设置多个锁管理器，每个锁管理器管理一组数据的加锁和释放锁的请求。每个管理一组数据的加锁和释放锁的请求。每个锁管理器位于不同的结点上。锁管理器位于不同的结点上。第54页，本讲稿共62页分布式并发控制技术分布式并发控制技术4以多为主的锁协议以多为主的锁协议系统在每个结点上有一个锁管理器。在任何系统在每个结点上有一个锁管理器。在任何结点结点Si上的锁管理器管理存储在上的锁管理器管理存储在Si上的所有上的所有数据项副本的加锁和释放锁的请求。当事务数据项副本的加锁和释放锁的请求。当事务T请求对数据项

48、请求对数据项Q加锁时，如果加锁时，如果n个结点存储个结点存储Q的副本，则的副本，则T要向要向n/2以上的存储以上的存储Q副本的副本的结点发出加锁请求。结点发出加锁请求。第55页，本讲稿共62页分布式并发控制技术分布式并发控制技术4区分锁类型的锁协议区分锁类型的锁协议每个结点上有一个锁管理器。每个锁管理器每个结点上有一个锁管理器。每个锁管理器管理所在结点上存储的数据的加锁和释放锁管理所在结点上存储的数据的加锁和释放锁的请求。共享锁和互斥锁采用不同的方式进的请求。共享锁和互斥锁采用不同的方式进行处理。当事务行处理。当事务T需要在数据项加共享锁时，需要在数据项加共享锁时，T直接向一个存储该数据项副本

49、的结点的锁直接向一个存储该数据项副本的结点的锁管理器发出加锁请求。当事务管理器发出加锁请求。当事务T需要在数据需要在数据项上加互斥锁时，项上加互斥锁时，T要向所有包含该数据项要向所有包含该数据项副本的结点的锁管理器发出加锁请求。副本的结点的锁管理器发出加锁请求。第56页，本讲稿共62页分布式并发控制技术分布式并发控制技术4主副本锁协议主副本锁协议在数据项在数据项Q具有多个副本的情况下，选择一具有多个副本的情况下，选择一个节点上的副本作为数据主副本，此节点称个节点上的副本作为数据主副本，此节点称为该数据项为该数据项Q的主节点。的主节点。当有事务请求对数据项当有事务请求对数据项Q的封锁时，它仅需的

50、封锁时，它仅需要向要向Q的主节点发出一个加锁请求。的主节点发出一个加锁请求。优点：简单优点：简单缺点：对主节点依赖大，如果主节点不可用，缺点：对主节点依赖大，如果主节点不可用，则数据项的其他副本也不可用。则数据项的其他副本也不可用。第57页，本讲稿共62页分布式死锁处理技术分布式死锁处理技术T1T2T5T3结点1T4T2T3结点2T1T4T2T3全局等待图T5第58页，本讲稿共62页分布式死锁处理技术分布式死锁处理技术4集中式方法集中式方法 在集中式方法中，全局等待图（局部等待图的并集）被保在集中式方法中，全局等待图（局部等待图的并集）被保存在一个称为死锁检测器的特殊结点上。全局等待图在下存在