分布式数据库系统概述课件全套整套电子教案电子讲义.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,分布式数据库系统及其应用,分布式数据库系统的起源和发展,分布式数据库系统的定义和分类,分布式数据库系统的体系结构,分布式数据库系统与客户机/服务器模式,分布式数据库管理系统,其他非集中式数据库系统,分布式数据库目录系统的主要内容和逻辑结构,分布式数据库系统的主要技术,分布式数据库系统的主要应用,分布式数据库系统的优点和存在的技术问题,分布式数据库系统概述,第,1,章,1.1,分布式数据库的起源,1 分布式数据库的起源和发展,计算机平台环境的改变,卫星通信,蜂窝通信,局域网,广域网,Intranet,Internet,信息系统应用需求,地域上分散、管理集中的企业越来越多,既要求实现本地数据管理，就要求存取异地的数据,既要有各部门的局部控制和分散管理；又要有整个组织的全局控制和高层次的协同管理,1.2,分布式数据库的发展,1 分布式数据库的起源和发展,分布式数据库发展阶段,20世纪70年代末期产生,20世纪80年代成长阶段,20世纪90年代商品化应用阶段,21世纪大规模应用阶段,分布式数据库系统的12条规则,本地自治性,不依赖于中心节点,可连续操作性,位置独立性,数据分片独立性,数据复制独立性,分布式查询处理,分布式事务处理,硬件独立性,操作系统独立性,网络独立性,数据库管理系统独立性,2.1,分布式数据库的定义和特点,2 分布式数据库系统的定义和分类,分布式数据库定义：物理上分散而逻辑上集中的系统，它使用计算机网络将地理位置分散而管理和控制又需要不同程度集中的多个逻辑单位（通常是集中式数据库系统）连接起来，共同组成一个统一的数据库系统。分布式数据库系统可以看成是计算机网络和数据库系统的有机结合。,分布式数据库系统的特点,物理分布性：数据不是存放在一个站点上,逻辑整体性：是与分散式数据库系统的区别,站点自治性：是与多处理机系统的区别,数据分布透明性,集中与自治相结合,存在适当的数据冗余度,事务管理的分布性,2.1,分布式数据库的定义和特点,2 分布式数据库系统的定义和分类,DB1,DB2,DB3,全局用户1,局部用户1,全局用户2,局部用户2,全局用户3,局部用户3,网络,DDBMS DBMS1,DDBMS DBMS2,DDBMS DBMS3,分布式数据库系统示意图,2.2,分布式数据库的分类,2 分布式数据库系统的定义和分类,按局部DBMS的数据模型分类,同构型DDBS,同构同质型,同构异质型,异构型DDBS,按DDBS的全局控制类型分类,全局控制集中型DDBS：全局控制机制和全局数据词典位于中心站点,全局控制分散型DDBS：全局控制机制和全局数据词典分散在网络的各个站点上。,全局控制可变型DDBS：也称主从型DDBS。分成两组站点，一组包含全局控制机制和全局控制词典，另外一组不包含。,3.1,分布式数据库系统的体系结构,3 分布式数据库系统的体系结构,分布式数据库系统的体系结构,GDBMS,LDBMS,LDD,全局用户,局部用户,网络,CM,LDB,GDD GDB,全局用户,GDD GDB,局部用户,GDBMS,LDBMS,LDD,CM,LDB,GDBMS,LDBMS,CM,全局用户,GDD GDB,局部用户,LDD LDB,3.2 基于三层模式的分布式数据库系统体系结构,3 分布式数据库系统的体系结构,全局外模式,全局概念模式,分片模式,分配模式,局部概念模式,局部内模式,DB,局部概念模式,局部内模式,DB,全局外模式,全局外模式,全局,DBMS,局部,DBMS,分布式数据库特有的,集中式数据库也有的,映象1,映象3,映象2,映象4,全局外模式,全局概念模式,分片模式,分配模式,局部概念模式,局部内模式,DB,局部概念模式,局部内模式,DB,全局外模式,全局外模式,全局,DBMS,局部,DBMS,分布式数据库特有的,集中式数据库也有的,映象1,映象3,映象2,映象4,3.3 基于组件模式的分布式数据库系统体系结构,3 分布式数据库系统的体系结构,基于客户机服务器模式的系统可以看作是真正意义上的分布式系统的一某些站点是客户机站点，而另一些站点是服务器站点；,所有的数据都驻留在服务器站点；,所有的应用都在客户机站点运行；,应用请求是通过客户机请求和服务器响应的协作方式来完成的；,一般不提供完全的位置透明性，即“存在接缝”。,4.1,客户机/服务器模式的含义,4 分布式数据库系统与客户机/服务器模式,4.2 集中式客户机/服务器系统,4 分布式数据库系统与客户机/服务器模式,4.3 多客户机/单服务器系统,4 分布式数据库系统与客户机/服务器模式,4.4 多客户机/多服务器系统,4 分布式数据库系统与客户机/服务器模式,4.5 服务器-服务器系统,4 分布式数据库系统与客户机/服务器模式,4.6 对等客户机/服务器系统,4 分布式数据库系统与客户机/服务器模式,分布式数据库系统是在集中式数据库系统基础上发展起来的，但不是简单地把集中式数据库系统分散地实现，,负责负责实现分布式数据库的建立、查询、更新、复制和维护等功能，同时还包括提供分布透明性，查询优化、协调全局事务的执行，协调各局部DBMS共同完成全局应用，保证数据库的全局一致性，执行并发控制，实现更新同步和全局恢复等功能。它,除此之外，还具有自己的性质和特征。,数据跟踪,分布式查询处理,分布式事务管理,复制数据的管理,安全性,分布式目录管理,5.1 分布式数据库管理系统的功能,5 分布式数据库系统的管理系统,5.2 分布式数据库管理系统的结构,5 分布式数据库系统的管理系统,用户查询,查询分析,优化算法,查询处理模块,调度处理模块,CM,LDBMS,DB,可靠性,处理模块,完整性,处理模块,系统,DD,网络,分布策略,需要的数据,实际的数据,数据定位,错误,对网络的监视信息,局部处理命令,数据,P2P模型是一种新型的体系结构模型，面向大范围的多数据资源节点的松散耦合。,每个对等计算机地位相同，可直接互连实现各种资源的共享，不需要依赖集中式服务器支持。,典型的P2P系统主要有以下三种结构：纯粹分布式P2P系统结构、集中目录P2P系统结构以及混合式P2P系统结构,P2P系统的主要特点有：,每个节点均可贡献数据，系统资源具有丰富性、多样性；,可直接访问数据源中的数据资源，即时得到最新鲜的数据，不同于集中的数据资源库，如数据仓库等；,采用自组织原则，具有健壮性；,每个节点可随时加入和退出，系统具有分散性、可扩展性；,通常以Web上的资源为节点，系统部署简单，不需要复杂的框架部署实现。,6.1 对等数据库系统,6,其他非集中式数据库系统,6.1 对等数据库系统,6,其他非集中式数据库系统,（a）纯粹分布式P2P系统结构（b）集中目录分布式P2P系统结构,（c）混合式分布式P2P系统结构,(a),(b),(c),多数据库系统（Multi-Database Systems，MDBS）是多个已存在的、自治的、异构的数据库系统的联合。,参与构成多数据库系统的数据库系统称为局部或成员数据库系统(Local Database System，LDBS)。多,数据库系统是在己经存在的数据库系统之上为用户提供一个统一的存取数据的环境。,6.2 多数据库系统,6,其他非集中式数据库系统,6.2 多数据库系统的逻辑结构,6,其他非集中式数据库系统,全局用户,多数据库系统,局部数据库系统,1,局部数据库系统,2,局部用户,局部用户,DB,1,DB,2,6.2 多数据库系统的组件结构,6,其他非集中式数据库系统,用户,多数据库用户接口,查询分析器,查询处理器,存储管理器,恢复管理器,全局执行监控器,查询分析器,查询处理器,存储管理器,恢复管理器,全局执行监控器,DBMS,DBMS,数据库,数据库,分布式数据库的目录系统（Catalog System）是存放与分布式数据库系统有关的对象和各种控制信息的场所。,主要功能包括：,7.1 分布式数据库目录系统的主要内容,7,分布式数据库目录系统的主要内容和逻辑结构,全局模式描述,分片模式描述,分布模式描述,局部名映射,存取方法描述,数据库的统计信息,一致性错误,状态信息,数据表述,数据命令,系统描述,分布式数据库目录系统可与分布式数据库系统协同工作，将用户对数据的高级查询转化为相应存储对象的低级操作，而且满足数据独立性要求。,验证用户对数据的访问权限，保证合法用户能正确而有效地访问数据库中的数据。,主要功能包括：,设计应用,翻译应用,优化处理,运行监督,系统维护,7.2 分布式数据库目录系统的主要用途,7,分布式数据库目录系统的主要内容和逻辑结构,分布式数据库目录系统的组织方式通常有以下三种:,独立式,利用操作系统提供的文件管理功能来建立和维护目录信息，这时目录系统具有独立的数据定义、装入、查询、修改和报告生成功能。,分离式,利用DBMS建立和维护目录信息，但它的用户界面与功能均独立于DBMS。,嵌入式,DBMS与目录系统一体化，即目录系统作为DBMS的子集而存在，在分布式数据库系统中通常采用这种方法。,7.3 分布式数据库目录系统的组织方式,7,分布式数据库目录系统的主要内容和逻辑结构,分布式数据库目录系统的组织方式通常有以下三种:,独立式,利用操作系统提供的文件管理功能来建立和维护目录信息，这时目录系统具有独立的数据定义、装入、查询、修改和报告生成功能。,分离式,利用DBMS建立和维护目录信息，但它的用户界面与功能均独立于DBMS。,嵌入式,DBMS与目录系统一体化，即目录系统作为DBMS的子集而存在，在分布式数据库系统中通常采用这种方法。,7.3 分布式数据库目录系统的组织方式,7,分布式数据库目录系统的主要内容和逻辑结构,7.4 分布式数据库目录系统的逻辑结构,7,分布式数据库目录系统的主要内容和逻辑结构,全局外模式,目录,全局概念模式,目录,局部外模式,目录,局部概念模式,目录,内模式,目录,局部数据库,网络目录,分布式数据库目录由目录系统进行管理。,目录系统在网络操作系统和分布式数据库管理系统的支持下实现对数据目录进行自动管理，并保持其在动态变化过程中数据目录的一致性和有效性。,目录系统有以下功能模块组成：,目录定义：描述目录信息的逻辑结构和模式表示。,目录装入：负责目录信息的装入与存储。,目录查询：负责解释用户对目录信息的查询请求，处理各种查询要求。,目录更新：用于更新目录信息。,目录维护：用于在不破坏目录模式定义的前提下，对目录信息进行分类、归并、重构与链接。,报告生成：将目录信息以文本格式输出。,7.5 分布式数据库目录系统的目录结构,7,分布式数据库目录系统的主要内容和逻辑结构,集中式目录：全局系统目录采用集中式存放方式,全复制式目录：在每个站点上都存放一个完整的全局目录，但目录的更新必须传播到每一个站点。,局部式目录：每个站点只为存放在本站点的数据保留一份目录（局部目录），系统的整体目录是所有这些不相交的局部目录的集合。,混合式目录：混合式目录是上述三种方式的混合使用，是折中的目录分布方案，包括：,集中式目录与局部式目录相混合。,全复制式目录与局部式目录相混合。,7.6 分布式数据库目录系统的分布方式,7,分布式数据库目录系统的主要内容和逻辑结构,分布式数据库设计方法主要有两种：,自顶向下方法,自底向上方法,前者从头开始设计分布式数据库，而后者则通过集成现有数据库来设计分布式数据库。,8.1 分布式数据库设计,8,分布式数据库目录系统的主要技术,分布式环境下影响查询效率的因素有很多,除了集中式查询下的CPU和I/O代价外，数据在网络站点之间的传输、数据的冗余和分布都会对查询的效率产生很大的影响。,分布式查询优化的准则是使通信费用最低和响应时间最短，即以最小的总代价、在最短的响应时间内获得需要的数据。最基本的查询优化方法是基于关系代数等价变换的查询优化方法。,此外，考虑局部代价和传输代价的不同情况，还有多种查询优化方法：,基于半连接算法的查询优化处理方法,基于直接连接算法的查询优化处理方法,分布式INGRES算法,R*算法和SDD-1算法等,8.2 分布式查询和优化,8,分布式数据库目录系统的主要技术,分布式DBMS系统中的分布式事务管理程序必须即保证本地事务的ACID特性又保证分布式事务的ACID特性,事务管理程序的本地事务管理程序负责保证本地事务的ACID特性，而分布式事务的ACID特性则由两阶段提交协议来保证。,当发生故障时，要使得分布式数据库恢复到一个正确的、一致的状态。恢复的基本原理是数据冗余，即利用冗余存储在别处的信息和数据，部分或全部重建数据库。,8.3 分布式事务管理和恢复,8,分布式数据库目录系统的主要技术,分布式数据库中的并发控制是以集中式数据库中的并发控制技术为基础的，主要解决多个分布式事务对数据并发执行的正确性。,分布式数据库系统并发控制的主要内容包括：,分布式数据库系统并发控制的封锁技术,分布式数据库系统中的死锁处理,分布式数据库系统并发控制的时标技术,分布式数据库系统并发控制的多版本技术,分布式数据库系统并发控制的乐观方法等,8.4 分布式并发控制,8,分布式数据库目录系统的主要技术,分布式数据库的可靠性是指分布式数据库在一个给定的时间间隔内不产生任何失败的概率。,它强调分布式数据库的正确性，要求分布式数据库在符合某种要求情况下正确地运行。一,个可靠性高的系统要求故障少、容易修复或者修复得快。,分布式数据库失败的主要原因有错误的设计、不稳定或临界的组件、不稳定的外部环境和操作者的过失等。,分布式数据库的可靠性协议可以保证在分布式数据库上执行的分布式事务的原子性和持久性。,8.5 分布式数据库的可靠性,8,分布式数据库目录系统的主要技术,分布式数据库面临的安全问题主要有：,单站点故障、,网络故障、,各类管理制度的不完善、,人为攻击（黑客攻击）、,内部人员泄露密码数据、,程序内嵌的不安全因素等引起的安全问题等。,分布式数据库的安全性的的内容主要包括：保证数据库安全的措施主要有建立安全数据模型、设定有效的访问控制机制、建立多级安全数据库、数据加密等。,8.6 分布式数据库的安全性,8,分布式数据库目录系统的主要技术,移动分布式数据库系统,连锁超市分布式数据库系统,火车订票分布式数据库系统,GSP药品管理分布式数据库系统,银行管理分布式数据库系统,9,分布式数据库系统的主要应用,良好的可靠性和可用性,提高系统效率，降低通信费用,较大的灵活性和可伸缩性,经济性和保护投资,适应组织的分布式管理和控制,数据分布具有透明性和站点具有较好的自治性,10.1 分布式数据库系统的优点,10,分布式数据库系统的优点和存在的技术问题,最重要的问题是通信网络速度问题,如何控制数据的分片、分布与冗余度,如何实现异构数据库的互联,如何优化分布式数据库的查询处理,如何更好地实现分布式数据库的更新处理,如何实现分布式数据库的并发控制机制,如何实现分布式数据库的恢复控制机制,如何实现目录管理,10.2 分布式数据库系统中存在的技术问题,10,分布式数据库系统,的优点和存在的技术问题,总 结,结,分布式数据库系统概论,分布式数据库系统的定义与分类,分布式数据库系统的体系结构,分布式数据库系统与客户机/服务器模式,分布式数据库管理系统,其他非集中数据库系统,分布式数据库目录系统的主要内容和逻辑结构,分布式数据库系统的主要技术,分布式数据库系统的主要应用,分布式数据库系统的优点和存在的技术问题,分布式数据库系统及其应用,数据库技术回顾,计算机网络技术回顾,基础知识回顾,第,2,章,数据库系统知识回顾,数据库,(DB:DataBase),长期储存在计算机内的有组织的、可共享的相关数据的集合。,数据库管理系统,(DBMS:DataBase Management System),DBMS是介于用户与操作系统之间的一层数据管理软件。为,用户或应用程序提供访问DB的方法，包括DB的建立、查询、,更新及各种数据控制。DBMS基于某种数据模型。,数据库系统,(DBS:DataBase System),数据库系统（DBS）通常是指带有数据库的计算机应用系统。,包括数据库、相应的硬件、软件和各类人员。,数据库技术,硬件,操,作,系,统,D,B,M,S,应,用,软,件,应,用,程,序,包,数据库系统软硬件层次关系,数据库技术是研究数据库的,结构、存储、设计、管理和,使用的一门软件学科；是一,门综合性较强的学科。,1,基本概念,1.1,1,数据库系统知识回顾,数据库系统的模式结构,1.2,视图抽象外模式,概念抽象概念模式,物理抽象内模式,概念模式,内模式,现实世界,视图抽象,概念抽象,物理抽象,外模式,视图2,视图1,视图3,数据库系统知识回顾,关系数据模型(Data Model),1,1.3,数据结构,数据操作,完整性约束,用于描述系统的静态特性；是所研究的对象类型（Object type）,的集合，包括：数据的类型、内容和性质的对象（事物）；数据之间,联系的对象（联系）。,数据模型的三要素,1.数据结构：,是一组完整性规则（条件）的集合。给出数据及其联系所具有,的制约、依赖和存储规则，用于限定数据库的状态和状态变化，保,证数据库中的数据的正确、有效、完全和相容。,3.完整性约束（Integrity Constraint）：,用于描述系统的动态特性，是对数据库中的各种对象的实例（值）,允许执行的操作的集合。主要有查询和更新（插入、删除、修改）两,类操作。,2.数据操作（Data Manipulation）：,1.,数据库系统知识回顾,实体联系模型,1.4,一对一的联系，记为,11,一对多的联系，记为,1n,多对多的联系，记为,mn,实体联系类型,实体内部联系,实体之间的联系,同一实体型的实体之间的联系,不同实体型的实体之间的联系,1.,数据库系统知识回顾,SQL语言,1.5,SQL是结构化查询语言（Structured Query Language）的英文缩写，它起源于,IBM,公司San Jose研究中心为其关系,数据库,管理系统System R开发的一种查询语言SQUARE语言。,SQL语言之所以成为国际标准，被广大用户接收和使用，是因为它是一个综合的、功能强大的、简单易学的语言。它主要有以下几个特点：,综合统一,高度非过程化,面向集合的操作方式,灵活的使用方式,语言简洁，易学易用，功能强大,1.,数据库系统知识回顾,SQL语言,基本组成,1.5.1,数据定义语言,操作对象,操作方式,SQL语句,模式,创建,CREATE SCHEMA,AUTHORIZATION,;,删除,DROP SCHEMA,CASCADE,|,RESTRICT,;,基本表,创建,CREATE TABLE,(,列级完整性约束条件,);,删除,DROP TABLE,CASCADE,|,RESTRICT,;,修改,ALTER TABLE,ADD COLUMN,完整性约束,MODIFY COLUMN,DROP COLUMN,CASCADE,|,RESTRICT,;,视图,创建,CREATE VIEW,(,),AS,WITH CHECK OPTION,;,删除,DROP VIEW,CASCADE,;,索引,创建,CREATE UNIQUECLUSTER INDEX,ON,(,);,删除,DROP,INDEX,;,1.,数据库系统知识回顾,SQL语言,基本组成,1.5.1,数据定义语言（续）,域,创建,CREATE DOMAIN,AS,DEFAULT,CHECK,;,删除,DROP DOMAIN,;,存储过程,创建,CREATE PROCEDURE,.,AS,SQL语句;,修改,ALTER PROCEDURE,.,AS,SQL语句;,删除,DROP PROCEDURE,;,触发器,创建,CREATE TRIGGER,owner.,ON,owner.表名,WITH ENCRYPTION,FOR,|,AFTER,|,INSTEAD OF,INSERT,|,UPDATE,|,DELETE,AS,IF UPDATE(列名)AND,|,ORUPDATE(列名),SQL语句;,修改,ALTER TRIGGER,owner.,ON,owner.表名,WITH ENCRYPTION,FOR,|,AFTER,|,INSTEAD OF,INSERT,|,UPDATE,|,DELETE,AS,IF UPDATE(列名)AND,|,ORUPDATE(列名),SQL语句;,删除,DROP TRIGGER,;,1.,数据库系统知识回顾,SQL语言,基本组成,1.5.2,2.数据操作语言,操作对象,操作方式,SQL语句,基本表,查询,SELECT,ALL,|,DISTINCT,FROM,WHERE,GROUP BY,HAVING,ORDER BY,ASC,|,DESC,;,插入,INSERT INTO,(,),VALUES,(,);,更新,UPDATE,SET,=,=,WHERE,;,删除,DELETE,FROM,WHERE,；,1.,数据库系统知识回顾,SQL语言,基本组成,1.5.2,2.数据操作语言（续）,视图,查询,SELECT,ALL,|,DISTINCT,FROM,WHERE,GROUP BY,HAVING,ORDER BY,ASC,|,DESC,;,插入,INSERT INTO,(,),VALUES,(,);,更新,UPDATE,SET,=,=,WHERE,;,删除,DELETE,FROM,WHERE,;,1.,数据库系统知识回顾,SQL语言,基本组成,1.5.2,3.数据控制语言,操作对象,操作方式,SQL语句,权限,授权,GRANT,.,ON,TO,.,WITH OPTION,;,收权,REVOKE,.,ON,FROM,.;,1.,数据库系统知识回顾,关系代数与关系数据库的查询优化,1.6.1,关系代数语言是非过程化的语言，即：存取数据不必给出路径，存取多个记录不必借助于循环或递归来实现。,关系代数操作符主要有传统的集合操作符、专门的关系操作符、比较操作符和逻辑操作符四大类，如下图所示,传统的集合操作符：,，,，,，,专门的关系操作符：,，,，,，,，,，,，,比较操作符：,，,，,，,，,，,逻辑操作符：,，,，,传统的集合运算,1.6.2,关系代数,并运算,差运算,交运算,广义笛卡尔积,c,b,a,a,g,b,d,b,c,f,a,d,RS,f,a,d,RS,d,b,c,c,b,a,R-S,d,b,c,f,a,d,c,b,a,C,B,A,f,a,d,a,g,b,F,E,D,R,S,C,B,A,f,a,d,c,b,a,c,b,a,d,b,c,d,b,c,f,a,d,F,E,D,f,a,d,f,a,d,a,g,b,a,g,b,f,a,d,a,g,b,R x S,数据库系统知识回顾,1,选择运算是从关系中选取使公式为真的元组。这是从行的角度进行的运算。,在关系R中选择满足给定条件的元组，记做：,F,(,R,),=r|r,R,F(r)=,真,F,是一个公式，表示形式为由逻辑运算符（,),连接各算术表达式组成,。,算术表达式的基本形式为,：,X,Y.,=,=,.,X,Y是属性名或常量或简单函数。,例1 求计算机科学系CS的学生,SD=CS,(,S,),学号 学生姓名 所属系名 学生年龄,S#SN SD SA,S1 A CS 20,S2 B CS 21,S3 C MA 19,S4 D CI 19,S5 E MA 20,S6 F CS 22,(a),(S),(S),S#SN SD SA,S1 A CS 20,S2 B CS 21,S6 F CS 22,SD=CS,(,S,),选择运算,投影运算,这是从列的角度进行的运算,。,例2,SN,SD,(,S,),即求得学生关系S在学生姓名和所在系这两个属性上的投影结果。,SN,SD,(,S,),学号 学生姓名 所属系名 学生年龄,S#SN SD SA,S1 A CS 20,S2 B CS 21,S3 C MA 19,S4 D CI 19,S5 E MA 20,S6 F CS 22,(a),(S),SN SD,A CS,B CS,C MA,D CI,E MA,F CS,关系R上的投影是从R中选择若干属性组A组成新的关系。记做：,A,(,R,),=rA|r,R,投影之后不仅取消了某些列,，,还可能取消某些元组。,SA,(,S,),SA,20,21,19,连接运算是从两个关系的笛卡尔积中选取属性间满足一定条件的元组。,记做：,R S,.,其中，F是条件表达式，它涉及到对两个关系中的属性的比较。,如果F仅仅是一个相等条件，即等值连接。,连接运算,F,例3 设关系R、S如下图：,2,b5,2,b3,10,b3,7,b2,3,b1,E,B,S,12,b4,a2,8,b3,a2,6,b2,a1,5,b1,a1,C,B,A,R,R S,C,=,.,X,Y是属性名或常量或简单函数。,例1 求计算机科学系CS的学生,SD=CS,(,S,),学号 学生姓名 所属系名 学生年龄,S#SN SD SA,S1 A CS 20,S2 B CS 21,S3 C MA 19,S4 D CI 19,S5 E MA 20,S6 F CS 22,(a),(S),(S),S#SN SD SA,S1 A CS 20,S2 B CS 21,S6 F CS 22,SD=CS,(,S,),选择运算,投影运算,这是从列的角度进行的运算,。,例2,SN,SD,(,S,),即求得学生关系S在学生姓名和所在系这两个属性上的投影结果。,SN,SD,(,S,),学号 学生姓名 所属系名 学生年龄,S#SN SD SA,S1 A CS 20,S2 B CS 21,S3 C MA 19,S4 D CI 19,S5 E MA 20,S6 F CS 22,(a),(S),SN SD,A CS,B CS,C MA,D CI,E MA,F CS,关系R上的投影是从R中选择若干属性组A组成新的关系。记做：,A,(,R,),=rA|r,R,投影之后不仅取消了某些列,，,还可能取消某些元组。,SA,(,S,),SA,20,21,19,连接运算是从两个关系的笛卡尔积中选取属性间满足一定条件的元组。,记做：,R S,.,其中，F是条件表达式，它涉及到对两个关系中的属性的比较。,如果F仅仅是一个相等条件，即等值连接。,连接运算,F,例3 设关系R、S如下图：,2,b5,2,b3,10,b3,7,b2,3,b1,E,B,S,12,b4,a2,8,b3,a2,6,b2,a1,5,b1,a1,C,B,A,R,R S,C,=,.,X,Y是属性名或常量或简单函数。,例1 求计算机科学系CS的学生,SD=CS,(,S,),学号 学生姓名 所属系名 学生年龄,S#SN SD SA,S1 A CS 20,S2 B CS 21,S3 C MA 19,S4 D CI 19,S5 E MA 20,S6 F CS 22,(a),(S),(S),S#SN SD SA,S1 A CS 20,S2 B CS 21,S6 F CS 22,SD=CS,(,S,),选择运算,投影运算,这是从列的角度进行的运算,。,例2,SN,SD,(,S,),即求得学生关系S在学生姓名和所在系这两个属性上的投影结果。,SN,SD,(,S,),学号 学生姓名 所属系名 学生年龄,S#SN SD SA,S1 A CS 20,S2 B CS 21,S3 C MA 19,S4 D CI 19,S5 E MA 20,S6 F CS 22,(a),(S),SN SD,A CS,B CS,C MA,D CI,E MA,F CS,关系R上的投影是从R中选择若干属性组A组成新的关系。记做：,A,(,R,),=rA|r,R,投影之后不仅取消了某些列,，,还可能取消某些元组。,SA,(,S,),SA,20,21,19,连接运算是从两个关系的笛卡尔积中选取属性间满足一定条件的元组。,记做：,R S,.,其中，F是条件表达式，它涉及到对两个关系中的属性的比较。,如果F仅仅是一个相等条件，即等值连接。,连接运算,F,例3 设关系R、S如下图：,2,b5,2,b3,10,b3,7,b2,3,b1,E,B,S,12,b4,a2,8,b3,a2,6,b2,a1,5,b1,a1,C,B,A,R,R S,C500 （完整的，不是最小的）,4.4,数据的分片设计,4,数据分片设计,基本水平分片,如何保证分片原则,“手工”检查!,e.g.,R,1,=,loc=Sa,E;R,2,=,loc=Sb,E,生成具有满足分段原则的限定谓词,4.4,数据的分片设计,4,数据分片设计,基本水平分片,设有关系 E(e#,name,Loc,sal,A,),查询使用的简单谓词（A,i,Value）,是:,A5,Loc=Sa,Loc=Sb,下一步:-生成“小项”谓词,-消除无用谓词,给定简单谓词集 Pr=p,1,p,2,.p,n,则“小项”谓词（minterm predicate）形式:,p,1,*,p,2,*,p,n,*,这里 p,k,*是 p,k,或是 p,k,4.4,数据的分片设计,4,数据分片设计,谓词生成举例,(1)A5,Loc=S,A,Loc=S,B,(2),A5,Loc=S,A,(Loc=S,B,),(3),A5,(Loc=S,A,),Loc=S,B,(4),A5,(Loc=S,A,),(Loc=S,B,),(5),A5),Loc=S,A,Loc=S,B,(6),A5),Loc=S,A,(Loc=S,B,),(7),A5),(Loc=S,A,),Loc=S,B,(8),A5),(Loc=S,A,),(Loc=S,B,),4.4,数据的分片设计,4,数据分片设计,小项谓词选择,(9),(,A5,Loc=S,A,Loc=S,B,(10),(,A5,Loc=S,A,(Loc=S,B,),(11),(,A5,(Loc=S,A,),Loc=S,B,(12)(,A5,(Loc=S,A,),(Loc=S,B,),(13)(,A5),Loc=S,A,Loc=S,B,(14)(,A5),Loc=S,A,(Loc=S,B,),(15)(,A5),(Loc=S,A,),Loc=S,B,(16)(,A5),(Loc=S,A,),(Loc=S,B,),4.4,数据的分片设计,4,数据分片设计,小项谓词选择,R2:,5 A 10,Loc=S,A,R3:,5 A 10,Loc=S,B,R6:,A,5,Loc=S,A,R7:,A,5,Loc=S,B,R10:,A,10,Loc=S,A,R11:,A,10,Loc=S,B,分片结果,4.4 数据的分片设计,4,数据分片设计,注:无用段的消除依赖于应用的语义,e.g.:,如果 LOC 可以是,SA,SB,则最终分段集合应该加上,R4:,5 A 10,Loc S,A,Loc S,B,R8:,A,5,Loc S,A,Loc S,B,R12:,A,10,Loc S,A,Loc S,B,4.4,数据的分片设计,4,数据分片设计,小项选择率（minterm selectivity）,对某一给定小项谓词用户查询可能选择到的元组数,访问频率（Access frequency）,用户应用访问数据的频率,小项访问频率可以通过用户查询频率获得,4.4,数据的分片设计,4,数据分片设计,分片数量信息,例子,E(#,NM,LOC,SAL,),有查询应用,Qa:select*Qb:select*,from Efrom E,where LOC=Sa where LOC=Sb,and and.,4.4,数据的分片设计,4,数据分片设计,如何选择小项谓词举例,(1)Pr=R1=E,(2)Pr=LOC=Sa,LOC=S,b,R2=,loc=Sa,E,loc=S,b,E,(3)Pr=LOC=Sa,LOC=Sb,Sal1000,R,3=,loc=Sa,sal1000,E,loc=Sa,sal1000,E,loc=Sb,sal1000,E,loc=Sb,sal1000,E,三种选择,4,数据分片设计,4,数据分片设计,Loc=Sa,sal 1000,Loc=Sa,sal,1000,Loc=Sb,sal 1000,Loc=Sb,sal,1000,R,1,R,3,R,2,Q,a,:Select loc=S,a,.,Q,b,:Select loc=S,b,.,R,2,是好的,(,R,1,R,3不好,),4.4,数据的分片设计,4,数据分片设计,图示,Loc=Sa,sal 1000,Loc=Sa,sal,1000,Loc=Sb,sal 1000,Loc=Sb,sal,1000,R,1,Q,a,:Select loc=S,a,.,Q,b,:Select loc=S,b,.,此处元组有较,高的选择概率,此处元组选,择概率较低,分段内元组选择概率不等,因此,R,1 不好,.,4.4,数据的分片设计,4,数据分片设计,理由,Loc=Sa,sal 1000,Loc=Sa,sal,1000,Loc=Sb,sal,=,。,例1 求计算机科学系CS的学生,SD=CS,(,S,),学号 学生姓名 所属系名 学生年龄,S#SN SD SA,S1 A CS 20,S2 B CS 21,S3 C MA 19,S4 D CI 19,S5 E MA 20,S6 F CS 22,(a),(S),(S),S#SN SD SA,S1 A CS 20,S2 B CS 21,S6 F CS 22,SD=CS,(,S,),选择运算,在关系R中选择满足给定条件的元组，记做：,F,(,R,),=t|t,R,F(t)=,真,例2 求计算机科学系CS，年龄不超过21岁的学生。,SD=CS,SA21,(,S,),(S),S#SN SD SA,S1 A CS 20,S2 B CS 21,选择运算,(S),S#SN SD SA,S1 A CS 20,S2 B CS 21,S6 F CS 22,SD=CS,(,S,),学号 学生姓名 所属系名 学生年龄,S#SN SD SA,S1 A CS 20,S2 B CS 21,S3 C MA 19,S4 D CI 19,S5 E MA 20,S6 F CS 22,(S),投影运算,这是从列的角度进行的运算,。,例,3,SN,SD,(,S,),即求得学生关系S在学生姓名和所在系这两个属性上的投影结果。,SN,SD,(,S,),学号 学生姓名 所属系名 学生年龄,S#SN SD SA,S1 A CS 20,S2 B CS 21,S3 C MA 19,S4 D CI 19,S5 E MA 20,S6 F CS 22,(a),(S),关系R上的投影是从R中选择若干属性列组成新的关系。记做：,A,(,R,),=tA|t,R,投影之后不仅取消了某些列,，,还可能取消某些元组。,SA,(,S,),SA,