关系运算和关系表达式的优化问题.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第3章 关系运算,关系数据库系统是当今普遍应用的数据库系统。本章主要介绍关系数据模型的基本概念，关系运算和关系表达式的优化问题，其中关系运算本课程的重点内容之一。,关系运算是关系数据模型的理论基础。,3.1 关系数据模型,3.1.1 关系数据模型的定义,用二维表格表示实体集，键表示实体间联系的数据模型称为关系模型。,在关系模型中，数据是以二维表的形式存在的，这个,二维表,就叫做,关系,。,关系理论,是以,集合代数,理论为基础的，因此，我们可以用集合代数给出二维表的“关系”定义。,为了从集合论的角度给出关系的定义，我们先引入,域,和,笛卡尔积,的概念。,定义3.1 域（,Domain）,域是一组具有相同数据类型的值的集合，又称为,值域,。（用,D,表示）,例如整数、实数、字符串的集合。,域中所包含的值的个数称为域的,基数,（用,m,表示）。,关系中用域表示属性的取值范围。例如：,D1=,汪宏伟，钱红,m1=2,D2=,数据结构，离散数学，计算机原理,m2=3,其中，,D1，D2,为域名，分别表示教师名域和课程名域。,域名无排列次序，如,D1=,汪宏伟，钱红=钱红，汪宏伟,3.2 笛卡尔积(,Cartesian Product),给定一组域,D1，D2，,Dn,（,它们可以包含相同的元素，即可以完全不同，也可以部分或全部相同）。,D1，D2，,Dn,的笛卡尔积为,D1D2,Dn,=（d1，d2，,dn,）|,di,Di,，i=1，2，n。,由定义可以看出，笛卡尔积也是一个,集合,。其中：,1.元素中的每一个,di,叫做一个分量(,Component)，,来自相应的域（,di,Di,）,2.,每一个元素（,d1，d2，d3，,dn,）,叫做一个,元组,（,Tuple,）。,但元组不是,di,的集合，元组的每个分量（,di,）,是按序排列的。如：,（1，2，3）（2，3，1）（1，3，2）；,而集合中的元素是没有排序次序的，如（1，2，3）=（2，3，1）=（1，3，2）。,3.若,Di,（i=1，2，n）,为有限集，,Di,中的集合元素个数称为,Di,的,基数,，用,mi（i=1，2，n）,表示，则笛卡尔积,D1D2,Dn,的基数,M（,即元素（,d1,d2,dn,）,的个数）为所有域的基数的累乘之积，即,M=,例如：上述表示教师关系中姓名、性别两个域的笛卡尔积为：,D1D2=（,汪宏伟，数据结构），（汪宏伟，离散数学），（汪宏伟，计算机原理），（钱红，数据结构），（钱红，离散数学），（钱红，计算机原理）,它表示教师名和课程名的所有可能的组合。,汪宏伟、钱红、数据结构等都是分量,（,汪宏伟，数据结构），（钱红，离散数学）等是元组,其基数,M=m1m2=2*3=6,元组的个数为63.3 关系（,Relation）,笛卡尔积,D1D2,Dn,的任一子集称为定义在域,D1，D2，,Dn,上的,n,元,关系,（,Relation），,可用,R（D1，D2,Dn,）,表示,用集合论的观点来定义关系,：关系是一个元数为,k（k1）,的元组集合。即这个关系中有若干个元组，每个元组有,k,个属性值。把关系看成是一个集合，集合中的元素是元组。更直观的理解，可将关系看成是一张二维表格。,如上例,D1D2,笛卡尔积的子集可以构成教师本学期任课关系,T1，,如下表,：,姓名,课程,汪宏伟,数据结构,钱红,离散数学,(1)二维表的表头那一行称为,关系模式,（,Relational Scheme）。,每一张表称为该关系模式的一个具体关系或简称为关系（,Relation）。,它表示的是一个实体集合。,（2）二维表的各行称为关系的,元组,（,Tuple,），,可用来表示实体集中的一个实体。元组的个数称为基数（,Cordinality,）。,（3）二维表中的每一列称为关系的,属性,（,Attributes），,给每一列起一个名称即属性 名，表中的属性名不能相同。列中的元素为该属性的值，称作,分量,。,（4）每个属性(列)所对应的变化范围叫属性的 变域或简称,域,（,Domain），,它是一个值的集 合，关系中所有属性的实际值均来自于它所对应的域。同列具有相同的域，不同的列可有相 同的域例如:职工编号和年龄都为整数域。,（5）表中任意两行（元组）不能相同。能惟一标识表中不同行的属性或属性组称为,主键,。,关系的性质,尽管,关系,与,二维表格,、传统的,数据文件,是非常类似的，但它们之间又有重要的区别。,严格地说，,关系,是种规范化了的,二维表,，为了使相应的数据操作简化，在关系模型中，对关系作了种种,限制,，关系具有如下特性：,1.,关系中不允许出现相同的元组。,因为数学上集合中没有相同的元素，而关系是元组的集合，所以作为集合元素的元组应该是唯一的。,2.,关系中元组的顺序（即行序）是无关 紧要的，在一个关系中可以任意交换两行的次序。,因为集合中的元素是无序的，所以作为集合元素的元组也是无序的。根据关系的这个性质，可以改变元组的顺序使其具有某种排序，然后按照顺序查询数据，可以提高查询速度。,3.,关系中属性的顺序是无关紧要的，即列的顺序可以任意交换。,交换时，应连同属性名一起交换，否则将得到不同的关系。,4,.,同一属性名下的各个属性值必须来自同一个域，是同一类型的数据。,5.,关系中各个属性必须有不同的名字，不同的属性可 来自同一个域，即它们的分量可以取自同一个域。,例如，有如下表中关系，职业与兼职是两个不同的属性，但它们取自同一个域职业教师，工人，辅导员。,姓名,职业,兼职,张强,教师,辅导员,王丽,工人,教师,刘宁,教师,辅导员,6.,关系中每一分量必须是不可分的数据项,，或者说所有属性值都是原子的，即是一个确定的值，而不是值的集合。属性值可以为空值，表示“未知”或“不可使用”，即不可“表中有表”。,例如，在表2.8中，籍贯含有省、市县两项，出现了“表中有表”的现象，则为非规范化关系，而把籍贯分成省、市县两列，将其规范化，如表2.9所示。,姓名,籍贯,姓名,省,市县,省,市县,张强,吉林,长春,张强,吉林,长春,王丽,山西,大同,王丽,山西,大同,表2.8 表2.9,3.1.2 关键码和表之间的联系,在关系数据库中，关键码（简称键）是关系模型的一个重要概念。通常键由一个或几个属性组成，有如下几种键：,（1）,超键,：在一个关系中，能惟一标识元组的属性或属性集称为关系的超键。,（2）,候选键,：如果一个属性集能惟一标识元组，且又不含有多余的属性，那么这个属性集称为关系的候选键。,（3）,主键,：若一个关系中有多个候选键，则选其中的一个为关系的主键。每个关系必需选择一个主关系键，选定以后，不能随意改变。每个关系必定有且仅有一个主关系键，因为关系的元组无重复，至少关系的所有属性的组合可作为主关系键，通常用较小的属性组合作为主关系键。,包含在任何一个候选键中的属性称为主属性（,Primary Attribute），,不包含在任何键中的属性称为非主属性（,Nonprilnary,Attribute）,或非键属性（,Nonkey,Attnbute,）。,在最简单的情况下，一个候选码只包含一个属性，如学生关系中的“学号”，教师关系中的“教师号”。,在最极端的情况下，所有属性的组合是关系的候选码，这时称为,全码,（,all-key）,下面是一个全码的例子：,假设有教师授课关系,TCS，,分别有三个属性教师（,T）、,课程（,C）,和学生（,S）。,一个教师可以讲授多门课程，一门课程可以为多个教师讲授，同样一个学生可以选听多门课程，一门课程可以为多个学生选听。,在这种情况下，,T，C，S,三者之间是多对多关系，(,T,C,S),三个属性的组合是关系,TCS,的候选码，称为,全码,，,T,C,S,都是主属性。,表3.,l,是一张职工表（是一张二维表格，也是一个关系）,表3.1 职工表（实体集）,-,职工编号 姓名 部门 性别 年龄 身份证号码,-,21,3,程晓清 销售部 男 30 310110720306408,21,6,刘红英 财务部 女 32 310110700508506,218,李小刚 管理部 男 28 310110740609507,215 蒋 民 采购部 男 41 310,l l06l 0808406,214,王国洋 销售部 男 39 310110630909407,-,例如：表3.1的关系中，设属性集,K（,职工编号，部门），虽然,K,能惟一标识职工，但,K,只能是关系的超键，还不能作候选键使用。因为,K,中“部门”是一个多余属性，只有“职工编号”能惟一标识职工。因而“职工编号”是一个候选键。还有“身份证号”也可以是一个候选键。另外，如果规定“不允许有同名同姓的职工”，那么“姓名”也可以是一个候选键。关系的候选键可以有多个，但不能同时使用，只能使用一个，譬如使用“职工编号”来标识职工，那么“职工编号”就是主键了。,（4）,外键,：若一个关系,R,中包含有另一个关系,S,的主键所对应的属性组,F，,则称,F,为,R,的外键。并称关系,R,为,参照关系,，关系,S,为,依赖关系（被参照关系,）。,例如，职工关系和部门关系分别为：,职工（,职工编号,，姓名，,部门编号,，性别，年龄 ，身份证号码）,部门（,部门编号,，部门名称，部门经理）,职工关系的主键为职工编号，部门关系的主键为部门编号，在职工关系中，部门编号是它的外键。更确切地说，部门编号是部门表的主键，将它作为外键放在职工表中，实现两个表之间的联系。在关系数据库中，表与表之间的联系就是通过公共属性实现的。这个公共属性是一个表的主键和另一个表的外键，这是关系数据库的特点。,3.1.3 关系模式、关系子模式和存储模式,关系模型基本上遵循数据库的三级体系结构。在关系模型中，概念模式是关系模式的集合，外模式是关系子模式的集合，内模式是存储模式的集合。,1关系模式,关系模式是对关系的描述，它包括模式名，组成该关系的诸属性名、值域名和模式的主键。具体的关系称为实例。,例3.1图3.1是一个教学模型的实体联系图。实体类型“学生”的属性,SNO、SNAME、AGE、SEX、SDEPT,分别表示学生的学号、姓名、年龄、性别和学生所在系；实体类型“课程”的属性,CNO、CNAME、CDEPT、TNAME,分别表示课程号、课程名、课程所属系和任课教师。学生用,S,表示，课程用,C,表示。,S,和,C,之间有,M：N,的联系（一个学生可选多门课程，一门课程可以被多个学生选修），联系类型,SC,的属性成绩用,GRADE,表示。图3.1表示的实体联系图（,ER,图）转换成关系模式集如图3.2所示。,ER,图向关系模型的转换技术将在第7章中详细介绍。表3.2是这个关系模式的实例。,又如图31中表示的学生关系的基本情况，相应的关系模式为：,S（SNO,SNAME,AGE,SEX,SDEPT）,这个关系模式描述了学生的数据结构，它是,图3.1中学生关系（表格）的关系模式。,关系模式是用数据定义语言（,DDL）,定义的。关系模式的定义包括：模式名、属性名、值域名以及模式的主键。由于不涉及到物理存储方面的描述，因此关系模式仅仅是对数据本身的特征的描述。,2关系子模式,有时，用户使用的数据不直接来自关系模式中的数据，而是从若干关系模式中抽取满足一定条件的数据。这种结构可用关系子模式实现。关系子模式是用户所需数据的结构的描述，其中包括这些数据来自哪些模式和应满足哪些条件。,例3.2用户需要用到成绩子模式,G（SNO，SNAME，CNO，GRADE）。,子模式,G,对应的数据来源于表,S,和表,SC，,构造时应满足它们的,SNO,值相等。子模式,G,的构造过程如图3.3所示.,子模式定义语言还可以定义用户对数据进行操作的权限，例如是否允许读、修改等。由于关系子模式来源于多个关系模式，因此是否允许对子模式的数据进行插人和修改就不一定了。,3存储模式,存储模式描述了关系是如何在物理存储设备上存储的。关系存储时的基本组织方式是文件。由于关系模式有键，因此存储一个关系可以用散列方法或索引方法实现。如果关系中元组数目较少(100以内)，那么也可以用堆文件方式实现。此外，还可以对任意的属性集建立辅助索引。,(补充：关系数据库）,关系数据库,是“一组随时间变化，具有各种度的规范化关系的集合”。,因为关系是由,关系头,和,关系体,组成的，所以关系数据库也可以看作是一组关系头和关系体的集合。,由此可见，关系数据库也有,型,和,值,的概念，其型就是关系数据库模式，相对固定；其值就是关系数据库内容，代表现实世界中的实体，而实体是随着时间不断变化的，所以其值在不同的时刻会有所变化。,3.1.4 关系模型的完整性规则,关系模型的完整性规则是对数据的约束。关系模型提供了三类完整性规则：实体完整性规则、参照完整性规则、用户定义的完整性规则。其中实体完整性规则和参照完整性规则是关系模型必须满足的完整性的约束条件，称为关系完整性规则。,1实体完整性规则,在图3.4中给出导师表和研究生表，其中导师表的主键是导师编号，研究生表的主,键是学号，这两个主键的值在表中是惟一的和确定的，才能有效地标识每一个导师和研究生。主键不能取空值（,NULL），,空值不是0，也不是空字符串，是没有值，是不确定的值，所以空值无法标识表中的一行。为了保证每一个实体有惟一的标识符，主键不能取空值。,实体完整性规则：关系中元组的主键值不能为空。,例如，图3.4所示研究生表的主键是学号，不包含空的数据项；导师表的主键是导师编号，也不包含空的数据项，所以，这两个表都满足实体完整性规则。,2参照完整性规则,在关系数据库中，关系与关系之间的联系是通过,公共属性,实现的。这个公共属性是一个表的主键和另一个表的外键。,外键必须是另一个表的主键的有效值，或者是一个“空值”,。例如，图3.4中研究生表与导师表之间的联系是通过导师编号实现的，导师编号是导师表的主键、研究生表的外键。研究生表中的导师编号必须是导师表中导师编号的有效值，或者“空值”，否则，就是非法的数据。从图34所示的研究生表中，我们看到学号为“98110”的研究生没有固定的导师，所以他的导师编号为“空值”；而学号为“98110”的研究生的导师编号为“318”，由于导师表中不存在导师编号“318”，所以这个值是非法的。,参照完整性规则的形式定义如下：,如果属性集,K,是关系模式,R1,的主键,也是关系模式,R2,的外键，那么在,R2,的关系中,K,的取值只允许两种可能，或者为空值，或者等于,R1,关系中某个主键值。,这条规则在使用时，有三点需注意：,(1)外键和相应的主键可以不同名，只要定义在相同值域上即可。,(2),R1,和,R2,也可以是同一个关系模式，表示了同一个关系中不同元组之间的联系。例如表示课程之间先修联系的模式,R（CNO，CNAME,PCNO）,其属性表示课程号、课程名,先修课程的课程号,R,的主键是,CNO，,而,PCNO,就是一个外键，表示,PCNO,值一定要在关系中存在（某个,CNO,值）。,（3外键值是否允许空，应视具体问题而定。在模式中，若外键是该模式主键中的成分时，则外键值不允许空，否则允许空。,在上述形式定义中,R1,称为“参照关系”模式，,R2,称为“依赖关系”模式。在软件开发工具,PowerBuilder,中，分别称为主表和副表；在,Visual FoxPro,系统中，分别称为父表和子表.,上述两类完整性规则是关系模型必须满足的规则，应该由系统自动支持。,3用户定义的完整性规则,这是针对某一具体数据的约束条件，由应用环境决定。它反映某一具体应用所涉及的数据必须满足的语义要求。系统应提供定义和检验这类完整性的机制，以便用统一的系统方法处理它们，不再由应用程序承担这项工作。例如学生成绩应该大于或等于零，职工的工龄应小于年龄，人的身高不能超过3米，等等。,3.1.5 关系模型的形式定义,关系模型有三个组成部分：数据结构，数据操作，完整性规则。,（1）数据库中全部数据及其相互联系都被组织成关系（即二维表格）的形式。关系模型基本的数据结构是关系。,（2）关系模型提供一组完备的高级关系运算，以支持对数据库的各种操作。关系运算分为关系代数和关系演算两类。,（3）关系模型的三类完整性规则。,3.2 关系代数,3.2.1 关系查询语言和关系运算,关系模型与其他模型相比，最有特色的是它的,数据库语言,。,这种语言灵活方便、表达能力和功能都很强。,目前关系数据库所使用的语言一般都具有,定义,、,查询,、,更新,和,控制,一体化的特点，而,查询,是最主要的部分。（关系数据库的数据操纵语言（,DML）,的语句分成查询语句和更新语句两大类。查询语句用于描述用户的各类检索要求；更新语句用于描述用户的插入、修改和删除等操作。）,所以说，关系数据库的核心部分是,查询,，故又称为,查询语言,，而查询的条件要使用,关系运算表达式,来表示。,因此，关系运算是设计关系数据语言的基础。,按表达查询的方法不同（理论基础的不同），关系运算可分为,关系代数,和,关系演算,两大类。,关系代数语言：查询操作是以集合操作为基础的运算。,关系演算语言：查询操作是以谓词演算为基础的运算。,关系查询语言,是一种比,PASCAL、C,等程序设计语言更高级的语言。,PASCAL、C,一类语言属于过程性（,Pocedural,）,语言，在编程时必须给出获得结果的操作步骤，即指出“干什么”及“怎么干”。而关系查询语言属于非过程（,Nonprocedural）,语言，编程时只需指出需要什么信息，不必给出具体的操作步骤，即只要指出“干什么”，不必指出“怎么干”。,3.2.2 关系代数,关系代数是以集合代数为基础发展起来的，它是以关系为运算对象的一组高级运算的集合。(即每个运算都以一个或多个关系作为它的运算对象，并生成另外一个关系作为该运算的结果。）,由于关系定义为元数相同的元组集合，因此把关系看成集合，集合代数中的操作（并、差、交、笛卡儿积）就可以引人到关系运算中来。还有一些操作是针对关系数据库环境专门设计的，比如对关系进行垂直分割（投影）、水平分割（选择）、关系的结合（联接）等。,关系代数的,运算对象,是,关系,，,运算结果,也是,关系,，关系代数用到的运算符主要包括四类：,集合运算符,：（并），-（差），（交），,X（,广义笛卡尔积）；,专门的关系运算符,：,(,选择)，（投影），（连接），（自然连接），（除）；,算术比较运算符,：（大于），（大于等于），（小于），（小于等于），=（等于），（不等于）；,逻辑运算符,：（与）,（或）,（非）,关系代数有五个基本的操作。,1并（,Union）,设关系,R,和关系,S,具有相同的元数,n(,即两个关系都有,n,个属性)，且相应的属性取自同一个城，则关系,R,和关系,S,的并由属于,R,或属于,S,的元组组成。其结果仍为,n,元的关系。记为,RS。,形式定义如下：,RSt|tR tS,，t,是元组变量，,R,和,S,的元数相同。,两个关系的并运算是将两个关系中的所有元组构成一个新关系。并运算要求两个关系属性的性质必须一致且并运算的结果要消除重复的元组。,对于关系数据库，,记录的插入和添加可通过并运算实现。,例33有库存和进货两个表（见表33），要将两个表合并为一个表，可利用并运算实现。,2差（,Difference）,设关系,R,和关系,S,具有相同的元数,n，,且,相应的属性取自同一个域，则关系,R,和,S,的,差由属于,R,而不属于,S,的所有元组组成。其,结果仍为,n,元的关系，记为,RS，,形式定,义如下：,R-S t|tR t,S,t,是,元组变量，,R,和,S,的元数相同,通过差运算，可实现关系数据库记录的删除。,例34有考生成绩合格者名单和身体不合格者名单两个关系，按录取条件将从成绩合格且身体健康的考生中产生录取名单关系。这个任务可以用差运算来完成（见表34）。,3笛卡儿积（,Cartesian Product）,设关系,R,和关系,S,的元数分别为,r,和,s。,定义,R,和,S,的笛卡儿积,Rx S,是一个（rs）,元的元组集合，每个元组的前,r,个分量（属性值）来自,R,的一个元组，后,s,个分量是,S,的一个元组，记为,RXS，,形式定义如下：,RS t|t=|,t,r,R,t,s,S,这里,t,r,，,t,s,中,r,s,为上标，分别表示有,r,个分量和,s,个分量。若,R,有,n,个元组,S,有,m,个元组，则,RxS,有,nxm,个元组。,例351 在学生和必修课程两个关系上，产生选修关系：要求每个学生必须选修所有必修课程。这个选修关系可以用两个关系的笛卡儿积运算来实现（见表35）。,例351 在学生和必修课程两个关系上，产生选修关系：要求每个学生必须选修所有必修课程。这个选修关系可以用两个关系的笛卡儿积运算来实现（见表35）。,4投影（,Projection）,这个操作是对一个关系进行垂直分割，消去某些列，并重新安排列的顺序，再删去重复元组。,设关系,R,是,k,元关系,R,在其分量,Ai1,，Aim（mk，i1，,im,为1到,k,之间的整数）上的投影用,i,1,i,2,im,表示，它是从,R,中选择若干属性列组成的一个,m,元组的集合，形式定义如下：,i,1,i,2,im,(,R,),t,t,=,R,例 36已知职工表如前面表 3.1所示，对职工表进行投影操作。,（1）列出所有职工的职工编号、姓名、部门，关系代数表示为：,职工编号、姓名、部门,(职工),（2）列出职工表中的所有部门，关系代数表示为：,部门,(职工)注意：由于投影的结果消除了重复元组，所以，结果只有4个元组。,5.选择（,Selection）,这个操作是根据某些条件对关系做水平分割，即选择符合条件的元组。条件用命题公式,F,表示,F,中的运算对象是常量（用引号括起来）或元组分量（属性名或列的序号），运算符有算术比较运算符（，4,(SCXL)。,（,e）,为,SC,CL,的值。,F,GRADEG,31,31,31,2=1,32,（注：在（,d）,图中，少了一个元组（,S5,C2,91,79,B）,3.自然联接（,Natural Join）,自然联接是一种特殊的等值连接，它要求两个关系中进行比较的分量必须是相同的属性组，并且要在结果中把重要的属性去掉。两个关系的自然联接用,R,S,表示，具体计算过程如下,(1)计算,RXS。,(2),设,R,和,S,的公共属性是,A,1,A,K,挑选,RXS,中满足,R.A,1,=S.A,1,R.,A,k,=S.,A,k,那些元组。,(3)去掉,S.A,1,S.,A,k,这些列（保留,R.A,1,R.,A,k,),因此,R,S,可用下式定义：,R,S,i1,im,(,R.A,1,=S.A,1,R.,A,k,=S.,A,k,(,R,s,),例3.10表3.11（,c）,表示关系,C,和,SC,和自然联接，这里,R,S,sno,sc.,cno,GRADECNAME,CDEPT,TNAME,(,SC,.,cno,=c.,cno,(SC,C),自然联接是构造新关系的有效方法，是关系代数中常用的一种运算，,在关系数据库理论中起着重要作用。利用投影、选择和自然联接操作可以任意地分解和构造关系。,等值连接与自然连接的区别,：,1.,等值连接中不要求相等属性值的属性名相同，而自然连接要求相等属性值的属性名必须相同，即两关系只有在同名属性才能进行自然连接。,2.等值连接不将重复属性去掉，而自然连接去掉重复属性，也可以说，自然连接是去掉重复列的等值连接。,除法（,division）,设关系,R,和,S,的元数分别为,r,和,s（,设,rs0），,那么,RS是一个（,r-s）,元的元组的集合。（,RS）,是满足下列条件的最大关系：其中每个元组,t,与,S,中每个元组,u,组成的新元组,必在关系,R,中。,RS1，2，r-s（R）-1，2，r-s（1，2，r-s（R）S）-R）,R,能被,S,除的充分必要条件是：,R,中的属性包含,S,中的所有属性；,R,中有一些属性不出现在,S,中。,求商运算示例,324,关系代数表达式及其应用实例,在关系代数运算中，把由五种基本操作经过有限次复合的式子称为关系代数表达式。这种表达式的运算结果仍是一个关系，我们可以用关系代数表达式表示各种数据查询操作。查询语句的关系代数表达式的一般形式是：,上面的式子表示：首先取得查询涉及到的关系，再执行笛卡尔积或自然联接操作得到一张中间表格，然后对该中间表格执行水平分割（选择操作）和垂直分割（投影操作），见下面例子3.12的（2）（5）。当查询涉及到否定或全部、包含值时，上述形式就不能表达了就要用到差操作或除法操作见下面例3.12的（6）一（8）。,例3.12 见书本49-50页,补充例子设教学数据库,EDUCATION,中有三个关系：,学生关系,S（SNO，SNAME，AGE，SEX，SDEPT）,学习关系,SC（SNO，CNO，GRADE）,课程关系,C（CNO，CNAME，CDEPT，TNAME）,试用关系代数表达式表示每个查询语句。,(1)检索计算机系全体学生的学号、姓名和性别。,(2),检索学习课程号为,C2,的学生学号与姓名。,（3）检索选修课程名为“数据结构”的学生学号与姓名。,（4）检索选修课程号为,C2,或,C4,的学生学号。,（5）,检索至少选修课程号为,C2,和,C4,的学生学号。,（6）,检索不学,C2,课的学生姓名与年龄。,（7）检索学习全部课程的学生姓名。,（8）检索所学课程包含计算机系开设的全部课程的学生学号。,(1)检索计算机系全体学生的学号、姓名和性别。,SNO，SNAME，SEX,(,SDEPT=,计算机,(,S),该式表示先对关系,S,执行选择操作，然后执行投影操作。表达式中也可以不写属性名，而写属性的序号,：,12，4,(,5=,计算机,(,S),(2),检索学习课程号为,C2,的学生学号与姓名。,sno,，,sname,(,cno,=c2,(,s,sc),这个查询涉及到关系,S,和,SC，,因此先要对这两个关系执行自然联接操作，然后再对其执行选择和投影操作,。,（3）检索选修课程名为“数据结构”的学生学号与姓名,。,SNO，SNAME,(,cname,=,数据结构,(,S,sc,c,),（4）检索选修课程号为,C2,或,C4,的学生学号。,sno,(,cno,=c2,cno,=c4,(,sc),（5）,检索至少选修课程号为,C2,和,C4,的学生学号,。,SNO,(,1=4,2=,c2,5=,c4S,c,sc,),这里(,S,c,sc,),表示关系,sc,自身相乘的笛卡尔积操作。这里的,是对关系(,S,c,sc,),进行选择操作，其中的条件,（,1=4,2=,c2,5=,c4）,表示同一个学生，既选修了,c2,课程又选修了,c4,课程。,（6）,检索不学,C2,课的学生姓名与年龄。,SNAME,AGE,(,s,)-,SNAME,AGE,(,cno,=c,2,(,S,sc,),这里要用到集合差操作。先求出全体学生的姓名和年龄再求出学了,C2,课的学生姓名和年龄，最后执行两个集合的差操作。,（7）检索学习全部课程的学生姓名。,编写这个查询语句的关系代数表达式的过程如下：学生选课情况用操作,SNO，CNO,（SC）,表示;全部课程用操作,CNO,（C）,表示;学了全部课程的学生学号用除法操作表示,操作结果是学号,SNO,集:(,SNO，CNO,（SC）,CNO,（C）);,从,SNO,求学生姓名,SNAME,可以用自然连接和投影操作组合而成:,SNAME,（S,(,SNO，CNO,（SC）,CNO,（C）),（8）检索所学课程包含计算机系开设的全部课程的学生学号。,学生选课情况用操作,SNO，CNO,（SC）,表示,;,计算机系开设的全部课程用操作,CNO,(,CDEPT=,计算机,(,C),),表示;所学课程包含计算机系开设的全部课程的学生学号,可以用除法操作表示:,SNO，CNO,(SC),CNO,(,CDEPT=,计算机,(,C),重要内容分析（一）,（1）一般规则,对于只涉及到选择、投影、联接的查询可用下列表达式表示：,（,（RS）,或者,（,（RS）,对于否定的操作，一般要用差操作表示，例如“检索不学,C2,课的学生姓名”。,对于检索具有“全部”特征的操作，一般要用除法操作表示，例如“,检索学习全部课程的学生姓名”。,重要内容分析（二）,（2）“检索不学,C2,课的学生姓名”，决不能用下式表示：,SNAME，AGE,（,CNOC2,（S,SC）,一定要用“差”的形式：,SNAME，AGE,（S）,SNAME，AGE,（,CNO=C2,（S,SC）,（3检索学习全部课程的学生学号”，要用,SNO，CNO,（SC）,CNO,（C）,表示，,而不能写成,SNO,（SC,CNO,（C）,形式。这是因为一个学生学的课程的成绩可能是不一样的。,3.4 查询优化,3.4.1 关系代数表达式的优化问题,在关系代数表达式中需要指出若干关系的操作步骤。那么，系统应该以什么样的操作 顺序，才能做到既省时间，又省空间，而且效率也比较高呢？这个问题称为查询优化问题。,在关系代数运算中，笛卡儿积和联接运算是最费时间的。若关系,R,有,m,个元组，关系,S,有,n,个元组，那么,RxS,就有,mxn,个元组。当关系很大时,R,和,S,本身就要占较大的外存空间，由于内存的容量是有限的，只能把,R,和,S,的一部分元组读进内存，如何有效地执行笛卡儿积操作，花费较少的时间和空间，就有一个查询优化的策略问题。,例 323设关系,R,和,S,都是二元关系，属性名分别为,A，B,和,C，D。,设有一个查询可用关系代数表达式表示：,E1=,A,(,B=C,D=99,（R,S）),也可以把选择条件,D99,移到笛卡儿积中的关系,S,前面：,E2,=,A,(,B=C,（,R,D=99,（,S）,还可以把选择条件,BC,与笛卡儿积结合成等值联接形式：,E3,=,A,(,R,D=99,（,S）,这三个关系代数表达式是等价的，但执行的效率大不一样。显然，求,E1，E2，E3,的大部分时间是花在联接操作上的。,B=C,对于,E1，,先做笛卡儿积，要把,R,的每个元组与,S,的每个元组联接起来。在外存储器中，每个关系以文件形式存储。设关系,R,和,S,的元组个数都是10000，每个物理存储块可存放5个元组，那么关系,R,有2000块，,S,也有2000块。而内存只给这个操作100块的内存空间。此时执行笛卡儿积操作较好的方法是先让,R,的第一组99块数据装人内存，然后关系,S,逐块转入内存去做元组的联接；再把关系,R,的第二组99块数据装人内存，然后关系,S,逐块转入内存去做元组的联接,这样关系,R,每块只进内存一次，装入块数是2000；而关系,S,的每块需要进内存（200099）次，装人内存的块数是（200099）*2000，因而执行,R X S,的总装入块数是：,2000（200099）*200042400（块）,若每秒装入内存20块，则需要约35分钟。这里还没有考虑联接后产生的元组写人外存的时间。,对于,E2,和,E3，,由于先做选择，设,S,中,D99,的元组只有几个，因此关系的每块只需进内存一次。则关系,R,和,S,的总装人块数为4000，约3分钟，相当于求,E1,花费时间的110。,如果对关系,R,和,S,在属性,B、C、D,上建立索引，那么花费时间还要少得多。,这种差别的原因是计算,E1,时,S,的每个元组进内存多次，而计算,E2,和,E3,时S,的每个元组只进内存一次。在计算,E3,时把笛卡儿积和选择操作合并成等值联接操作。,从此例可以看出，如何安排选择、投影和联接的顺序是个很重要的问题。,关系代数表达式的等价变换规则,(1),联接和笛卡尔积的交换律,联接和笛卡尔积的结合律,投影的级联,选择的级联,选择和投影操作的交换,选择对笛卡尔积的分配律,选择对并的分配律,关系代数表达式的等价变换规则,(2),选择对集合差的分配律,选择对自然联接的分配律,投影对笛卡尔积的分配律,投影对并的分配律,选择与联接操作的结合,并和交的交换律,并和交的结合律,返回,3.4.3 优化的一般策略,这里介绍的优化策略与关系的存储技术无关，主要是如何安排操作的顺序。但经过优 化后的表达式不一定是所有等价表达式中执行时间最少的。此处不讨论执行时间最少的“最优问题”，只是介绍优化的,一般技术,。主要有以下一些策略：,（1）在关系代数表达式中尽可能早地执行选择操作。,（2）把笛卡儿积和其后的选择操作合并成,F,联接运算。,（3）同时计算一连串的选择和投影操作，以免分开运算造成多次扫描文件，从而能节省操作时间。,（4）如果在一个表达式中多次出现某个子表达式，那么应该将该子表达式预先计算出结果保存起来，以免重复计算,（5）适当地对关系文件进行预处理。（6）在计算表达式前应先估计一下怎么计算合算。,关系代数表达式的优化算法,算法3.1 关系代数表达式的优化算法。,输入：一个关系代数表达式的语法树,输出：计算表达式的一个优化序列,例3.24,见书本62页,返回,小结,（1）基本概念,关系模型，关键码（主键和外键），关系的定义和性质，三类完整性规则，过程性语言与非过程性语言。,（2）关系代数,五个基本操作，四个组合操作,（3）关系代数表达式的优化,关系代数表达式的等价及等价转换规则，优化算法。,重点:教材中,P49,的例3.12（关系代数表达式的应用实例）,