为了正常的体验网站,请在浏览器设置里面开启Javascript功能!
首页 > 关系数据模型

关系数据模型

2018-03-21 42页 doc 154KB 77阅读

用户头像

is_731942

暂无简介

举报
关系数据模型关系数据模型 第2章 关系数据模型 1970年,美国IBM公司的E. F. Codd发表了著名论文“A Relational Model of Data for Large Shared Data Banks”中首先提出了关系数据模型。之后他又发表了多篇文章,奠定了关系数据库的理论基础。标志着数据库系统新时代的来临。20世纪80年代以来,计算机厂商推出的数据库管理系统(DBMS)几乎都支持关系模型,非关系系统的产品也都加上了关系接口。关系数据库系统几乎成了当今数据库的代名词。 本章将对关系数据模型作详细的介绍,包括关系的...
关系数据模型
关系数据模型 第2章 关系数据模型 1970年,美国IBM公司的E. F. Codd发表了著名论文“A Relational Model of Data for Large Shared Data Banks”中首先提出了关系数据模型。之后他又发表了多篇文章,奠定了关系数据库的理论基础。标志着数据库系统新时代的来临。20世纪80年代以来,计算机厂商推出的数据库管理系统(DBMS)几乎都支持关系模型,非关系系统的产品也都加上了关系接口。关系数据库系统几乎成了当今数据库的代名词。 本章将对关系数据模型作详细的介绍,包括关系的基本概念与术语、完整性约束、关系的运算、关系表达式的等价变化、关系的查询优化等内容。 2.1 关系数据模型的基本概念 关系数据模型把概念模型中实体以及实体之间的各种联系均用关系来表示。从用户的观点来看,关系模型中数据的逻辑结构是一张二维表,它由行列构成。如图2-1所示的一个员工人事数据表。 2.1.1 关系、元组、属性、域、关系模式 1. 关系 每一个关系用一张二维表来表示,常称为表。每一个关系表都有个区别于其他关系表的名字,称关系名。关系是概念模型中同一类实体以及实体之间联系集合的数据模型表示。如图2-1中的员工人事数据表。 关系模式 员工编号 姓名 年龄 性别 部门号 430425 王天喜 25 男 Deno1 430430 莫玉 27 女 Deno2 元组 关系 430211 肖剑峰 33 男 Deno3 430121 杨琼英 23 女 Deno2 430248 赵继平 41 男 Deno3 属性 图2-1 基本术语 2. 属性 二维表中的每一列即为一个属性,每个属性都有一个显示在每一列首行的属性名。在一个关系表当中不能有两个同名属性。如图2-1中有6列,对应6个属性(员工编号,姓名,年龄,性别,部门号)。关系的属性对应概念模型中实体型以及联系的属性。 3. 域 关系中每个属性的值是有一定变化范围的,如图2-1员工人事数据表,其中属性“员工编号”的变化范围是10位字符;属性“姓名”的变化范围是15位字符;属性“年龄”的变化范围是20-70岁;属性“性别”的变化范围只能是男、女两个值。属性“部门号”的变化范围是所有可能的部门集合。每一个属性所对应的变化范围叫做属性的变域或简称域,它是属性值的集合,关系中所有属性的实际取值必须来自于它对应的域。例如,属性“员工编号”的域是10位字符,因此“员工编号”中出现的所有取值的集合必须是该域上的一个子集。 4. 元组 二维表中的每一行数据总称为一个元组或记录。一个元组对应概念模型中一个实体的所有属性值的总称。如图2-1有5行数据,也就有5个元组。由若干个元组就可构成一个具体的关系,一个关系中不允许有两个完全相同的元组。 5. 分量 一个元组在一个属性域上的取值称为该元组在此属性上的分量。 6. 关系模式 二维表的表头那一行称为关系模式。即一个关系的关系名及其全部属性名的集合。关系模式是概念模型中实体型以及实体型之间联系的数据模型表示。一般表示为: 关系名(属姓名1,属性名2,„„,属性名n) 如图2-1种员工认识数据表中的关系模式为: 员工信息表(员工编号,姓名,年龄,性别,部门号) 关系模式和关系是型与值的联系。关系模式指出了一个关系的结构;而关系则是由满足关系模式结构的元组构成的集合。因此关系模式决定了关系的变化形式,只要关系模式确定了,由它所产生的值——关系也就确定了。关系模式是稳定的、静态的,而关系则是随时间变化的、动态的。但通常在不引起混淆的情况下,两者可都成为关系。 一个具体的关系数据库是一个关系的集合,而关系数据库模式是关系模式的集合。 2.1.2 关键字 在关系数据库中,对每个指定的关系经常需要根据某些属性的值来唯一的操作一个元组,也就是要通过某个或某几个属性来唯一的标识一个元组,我们把这样的属性或属性组称为指定关系的关键字。 1. 超关键字(Super key)。 在一个关系中若通过一个属性集合的取值就能唯一确定每一个元组,即该关系中所有元组在这个属性集合上的分量是不同的。则称该属性集合为该关系的超关键字或则简称为超 键。因此超关键字具有唯一的标识性。值得注意的是超关键字定义并没有对属性集合的数目进行限定,只要求该集合具有唯一的标识性就可以了。超关键字有时也称“超码”。 如图2-1的员工人事数据表中只要包含了“员工编号”的所有属性组合都能唯一的确定该关系中的元组,因此这些属性组合构成的集合都是超关键字,整个关系模式的属性当然也是超关键字。 2. 候选关键字(Candidate key) 如果某一集合是超关键字,但去掉其中任意属性后就不再是超关键字,则称该属性集合为候选关键字。候选关键字不但要求属性集合具有唯一的标识性还要求属性集合的元素数目最少。显然候选关键字是最小的超关键字。候选关键字有时也称“候选码”。 如图2-1 的员工人事数据表中只有“员工编号”是候选关键字(员工可能有相同姓名)。 3. 合成关键字(Composite key) 当某个候选关键字包含多个属性时,称该候选关键字为合成关键字。 如有一个关系,学生选课(学号,课程号,成绩)。由于每一个学生可选修多门课程,每门课程又可被多个学生选修,因此单独的属性“学号”和单独的属性“课程号”都不能唯一的确定该关系的元组。但“学号,课程号”联合起来构成的集合却能唯一的标识每一个元组,并且该属性集合其中的任意一个属性都不能去掉了,所以它是候选关键字。显然该属性集合还是合成关键字。 4. 主关键字(Primary key) 为关系组织物理文件存储时,通常选用一个候选关键字作为插入、删除、检索元组的操作变量。这个被选用的候选关键字称为主关键字,有时也称为“主码”。对任一个关系而言,它的主关键字必定为候选关键字和超关键字。只要主关键字选定就通常不变。因此一个关系的主关键字只有一个,而候选关键字、超关键字可能有很多个。 5. 主属性(Main attribute) 包含在任何一个候选关键字之中的属性称为主属性,不包含在任何一个候选关键字之中的属性称为非主属性。 如关系:员工信息表(员工编号,姓名,年龄,性别,部门号)中主属性是“员工编号”;非主属性是“姓名”、“年龄”、“性别”、“部门号”。 关系:学生选课表(学号,课程号,成绩)中主属性是“学号”、“课程号”;非主属性是“成绩”。 6. 外部关键字(Foreign key) 如果关系R1的某一(些)属性A不是R1的候选关键字,但是在另一关系R2中属性A是候选关键字,则称A是R1的外部关键字。有时也称“外部码” 学生(学号,姓名,性别,年龄,籍贯) 学生选课(学号,课程号,成绩) 图2-2 外部关键字联系图 在图2-2所示的关系模式中,学生选课关系的属性“学号”在自身关系中只是一个主属性不是首选关键字,但在学生关系表中“学号”却是候选关键字。因此“学号”是学生选课关系得外部关键字。 在关系数据模型当中合成关键字和外部关键字提供了一种两个关系联系的桥梁。图2-2中学生选课关系的“学号”就把两个独立的关系表联系在一起了。 2.1.3 关系数据模型的集合论定义 前面介绍的关系数据模型定义和概念都是用自然语言描述的,但关系数据模型是以集合论中的关系(relation)概念发展过来的,它有严格的数学理论基础。下面就从集合论的角度给关系数据模型以严格的定义。 1. 笛卡尔积(Cartesian Product) 定义2.1 设有一个有限集合D、D、D、„„、D,则在D、D、D、„„、D上123n123n的笛卡尔积为: D×D×Dׄ„×D={ (d 、d 、d 、„„、d ) | d?D,i=1,2,3,„„,n } ii 123n123n 其中每一个元素 (d 、d 、d 、„„、d )叫做一个元组 (n-tuple)或简称元组 (Tuple)。123n 元素中的每一个值叫做一个分量 ( Component)。一个元组是组成该元组的各分量的有序集合,而不仅仅是各分量集合。 若D (i=1,2,3,„„,n)为有限集,其基数 (Cardinal Number)为m (i=1,2,3,„„,n),ii 则D×D×Dׄ„×D的基数为: 123n n Mm,,i,i1 笛卡尔积可表示为一个二维表。表中的每行对应一个元组,表中的每列对应一个域。 【例2.1】 设有三个集合如下:A={a1,a2},B={b1,b2},C={c1,c2}则集合A,B,C上的笛卡尔积为 A×B×C={(a1,b1,c1),(a1,b1,c2),(a1,b2,c1),(a1,b2,c2), (a2,b1,c1),(a2,b1,c2),(a2,b2,c1),(a2,b2,c2)} 笛卡尔积形成的二维表如表2-1所示。 表2-1 中集合A有2个元素,集合B有2个元素,集合C有2个元素,则笛卡尔积的基数为2×2×2=8。因此对应的二维表也有8个元素。 2. 关系 ( Relation ) 笛卡尔积D×D×Dׄ„×D的任意一个子集123nA B C 叫做在D、D、D、„„、D上的一个n元关系,简123na1 b1 c1 称关系。每个关系都有一个关系名。必须指出的是:构a1 b1 c2 成笛卡尔积的集合是有序的,形成的元组分量也是有序 a1 b2 c1 的,因此其子集也是有序的。 a1 b2 c2 从上面的定义可以看出,关系是笛卡尔积的子集, 因此可以用二维表来表示。二维表的名字就是关系的名a2 b1 c1 字,二维表的每一列都是一个属性。n元关系就会有na2 b1 c2 个属性。一个关系中每一个属性都有一个名字,且各个a2 b2 c1 属性的属性名都不同,对应参与笛卡尔积运算的每个集 a2 b2 c2 合的名字。一个属性的取值范围D (i=1,2,3,„„,n)称i 为该属性的域 ( Domain)。对应参与笛卡尔积运算的每表2-1 二维表 个集合的值域,所以不同的属性可以有相同的域。二维 表的每一行值对应于一个元组。 在数学中,笛卡尔积形成的二维表的各列是有序的,而在关系数据模型中对属性、元组的次序交换都是无关紧要的。当然,关系的属性、元组按一定的次序存储在数据库中。但这仅仅是物理存储的顺序,而在逻辑上,属性、元组在关系数据模型中都不作规定。 在关系数据模型中,关系可以有三种类型:基本表(或基表)、查询表和视图表。基本表是实际存在的表,它是实际存储数据的逻辑表示。查询表是查询结果对应的表。视图表示由基本表或其他视图表导出的表,是虚表,只有定义,实际不对应存储的数据。 3. 关系模式 在前面关系模式的自然语言定义中已经介绍过,一个关系的关系模式是该关系的关系名及其全部的属性名的集合,一般表示为关系名(属姓名1,属性名2,„„,属性名n)。关系模式和关系是型与值的联系。关系模式指出了一个关系的结构;而关系则是由满足关系模式结构的元组构成的集合。关系模式是稳定的、静态的,而关系则是随时间变化的、动态的。通常在不引起混淆的情况下,两者可都成为关系。 实际上完整的关系模式的数学定义为: R(U、D、dom、F) 其中:R为关系模式名,U为组成该关系的属性名的集合,D为属性组U中属性所来自的域的集合,dom为属性向域映像的集合,F为属性间函数依赖关系的集合。 关系模式通常简写为: R(U)或R(A,A,A,„„,A) 123n 其中:R为关系名,A(i=1,2,3,„„,n)为属性名。域名构成的集合及属性向域映像i 的集合一般为关系模式定义中的属性的类型和长度。 2.1.4 关系数据模型的完整性约束 关系数据模型的基本理论不但对关系模型的结构进行了严格的定义,而且还有一组完整的数据约束规则,它规定了数据模型中的数据必须符合的某种约束条件。在定义关系数据模 型和进行数据操作时都必须保证符合约束。关系模型中共有四类完整性约束:域完整性、实体完整性、参照完整性、用户自定义完整性。其中实体完整性和参照完整性是关系模型必须满足的完整性约束条件,任何关系系统都应该能自动维护。 1. 域完整性 (domain integrity constraint) 关系数据模型规定元组在属性上的分量必须来自于属性的域,这是由于完整性约束指出的。域完整性约束是最简单、最基本的约束。现今的RDBMS,一般都有域完整性约束检查功能。 2. 实体完整性 (entity integrity) 关系数据模型是将概念模型中的实体以及实体之间的联系都用关系这一数据模型来表示。一个基本关系通常只对应一个实体集。由于在实体集合当中的每一个实体都是可以相互区分的,即它们通过实体键唯一标识。因此关系模型当中能唯一标识一个元组的候选关键字就对应了实体集的实体键。这样,候选关键字之中的属性即主属性不能取空值。如果主属性取空值,就说明存在某个不可标识的元组,即存在不可区分的实体,这与现实世界的应用环境相矛盾。在实际的数据存储中我们是用主关键字来唯一标识每一个元组,因此在具体的RDBMS中,实体完整性应变为:任一关系主关键字之中的属性不能为空。 目前大部分RDBMS都支持实体完整性约束,但是只有用户在创建关系模式中说明了主关键字,系统才会自动进行这项检查,否则它是不强制的。 3. 参照完整性 (referential integrity constraint) 现实世界中的事物和概念往往是存在某种联系的,关系数据模型就是通过关系来描述实体和实体之间的联系。这自然就决定了关系和关系之间也不会是孤立的,它们是按照某种规律进行联系的。参照完整性约束就是不同关系之间或同一关系的不同元组必须满足的约束。它要求关系的外部关键字和被引用关系得主关键字之间遵循参照完整性约束:设关系R有1一外部关键字FK,它引用关系R的主关键字PK,则R中任一元组在外部关键字FK上的21 分量必须满足以下两种情况: , 等于R中某一元组在主关键字PK上的分量; 2 , 取空值(FK中的每一个属性的分量都是空值)。 例如:在学生选课关系中,学号只能取学生关系表中实际存在的一个学号;课程号也只能取课程关系表中实际存在的一个课程号。在这个例子当中学号和课程号都不能取空值,因为它们既分别是外部关键字又是该关系的主关键字,所以必须要满足该关系的实体完整性约束。 如图2-1的员工信息表中的属性“部门号”,若它引用部门关系表的主关键字“部门号”,则“部门号”在员工信息表中就是外部关键字。它的取值必须取部门关系表中实际存在的部门号或者去空值。 不仅两个或两个以上的关系间存在参照完整性,同一关系内部属性间也可能存在参照完整性。 【例2.2】 课程关系表(课程号,课程名,学分,先修课课程号),其中,属性“课程号”是主关键字,“先修课课程号”表示开设这门课时必须先要开设的课程编号。显然它应该来自本关系属性“课程号”的取值,如果它去空值则表示当前的这门课程没有先修课。 现在很多DBMS都增加了参照完整性约束的检查功能,可以帮助用户维护参照完整性约束。 4. 用户自定义完整性 (user defined integrity) 以上三类完整性约束都是最基本的,因为关系数据模型普遍遵循。此外,不同的关系数据库系统根据其应用环境的不同,往往还需要一些特殊的约束条件。用户自定义的完整性约束就是对某一具体关系数据库的约束条件,它反映了某一具体应用所涉及的数据必须满足的语义要求。例如年龄不能大于40岁,夫妻的性别不能相同,新创的世界纪录必须好于原纪录,成绩只能在0~100之间等。这些约束条件需要用户自己来定义,故称为用户自定义完整性约束。 关系数据系统应向用户提供定义这类完整性的手段,并能对此类完整性进行检查。 2.2 关系的运算 关系数据模型给出了关系操作的能力,其操作的特点是集合操作方式,即操作的对象和结果都是集合。这种操作的方式称为一次一集合的方式。关系操作可以使用两种定义。一种方式是基于代数的定义,称为关系代数。另一种方法是基于逻辑的定义,称为关系演算。由于使用的变量的不同,关系演算又分为元组关系演算和域关系演算。关系代数、元组关系演算和域关系演算在表达方法上是完全等价的。本书是介绍关系代数和元组关系演算,域关系演算请读者自己参阅其它资料。 在本书的第三章将介绍SQL(Structure Query 运算符 含义 Language)语言。SQL不仅具有丰富的查询功能还具? 并 集 有数据定义和数据控制功能,是集查询、DDL(数据, 差 合 定义语言)、DML(数据操纵语言)、DCL(数据控制符 ? 交 运语言)于一体的关系数据语言。它充分体现了关系数算 × 乘积 据语言的特点和优点,是关系数据库的语言。 ,选择 运专算门? 投影 符 的2.2.1 关系代数 连接 关 系? 除 关系代数由E.F.Codd在一系列文章中率先提出、, 大于 比 最早出现在1970年,到了1972年基本达到了当前的? 大于或等于 较 形式。关系数据库系统中用表的形式存储的信息,关运 , 小于 系代数的运算过程具备了查询关系数据库系统的潜算 ? 小于或等于 符力,因此使用关系代数的形式来查询这种表结构显得 ? 不等于 很自然。关系代数可以被看作是根据查询结果来生成, 等于 新表集合的方法,这些方法称为关系代数运算。关系, 非 逻代数是一种抽象的语言,这意味着无法在一台实际的辑 ,符与 运计算机上执行用关系代数形式化的查询。而关系代数 算 ,或 可以用最简单的形式来表达所有关系数据库查询语言表2-2 关系代数运算符 必须完成的运算的集合,它们能用作评估实际系统查 语言能力的标准或基础。 关系代数运算是通过对关系的运算来表达查询。它的运算对象是关系,运算结果也是关系。关系代数的运算可分为两类: ? 传统的集合运算:并、差、交和乘积。 ? 专门的关系运算,即专门针对关系数据库的运算:投影、选择、连接和除。 关系代数用到的运算符包括四类:集合运算符、专门的关系运算符、逻辑运算符,如表2-2所示。 1. 传统的集合运算 传统的集合运算是二目运算,包括并、交、差、乘积四种运算 ? 并 设关系R和S是同一关系模式下的关系,则R和S的并是由属于R或属于S的元组组成的集合。记作 RSttRtS={ | },,, 如果,和S有重复的元组,则只保留一个。 【例2.3】关系R和S如图2-3(a)、(b)所示,则R和S的并运算如图2-3(c)RS所示。 ? 差 设关系R和S是同一关系模式下的关系,则R和S的差是由属于R但不属于S的元组组成的集合。记作 RSttRtS,,,,,{|} 【例2.4】关系R和S如图2-3(a)、(b)所示,则R和S的差运算如图2-3(d)、RS,所示。 ? 交 设关系R和S是同一关系模式下的关系,则R和S的交是由属于R又属于S的元组组成的集合。记作 RSttRtS,,,,{|} 【例2.5】关系R和S如图2-3(a)、(b)所示,则R和S的交运算如图2-3(e)RS所示。 交和差运算之间存在如下关系: RSRRSSSR,,,,,,()() ? 乘积 设关系R有m个属性、i个元组;关系S有n个属性、j个元组,则关系R和S的乘积是个有(m+n)个属性的元组集合。每个元组的前r个分量来自关系R的一个元组,后s个分量来自S的一个元组,且元组的数目有i×j个。乘积运算又叫广义笛卡尔积。记作 mnmn RStttttRtS,,,,,,,,,{|,} mnm表示乘积运算所得到的新关系的元组由两部分组成的有序结构,由含有关,,tt,t n系R的属性的元组构成、由含有关系S的属性的元组构成,共同组成一个新的元组。 t 这里说明几点: ? 虽然在表示上,我们把关系R的属性放在前面,把关系S的属性放在后面,连接成 一个有序结构的元组,但在实际的关系操作中,属性间的前后交换次序是无关的。 ? 做乘积运算时,可从R的第一个元组开始,一次与S的每一个元组组合,然后,对R的下一个元组进行同样的操作,直至R的最后一个元组也进行完同样的操作为止,即可得到R×S的全部元组。 ? 乘积运算得出的新关系将数据库的多个孤立的关系表联系在一起了。这样就使关系数据库中独立的关系有了沟通的桥梁。 A B C A B C A B C b 2 d a 3 c b 2 d b 3 b b 2 d b 3 b c 2 d e 5 f c 2 d d 3 b d 3 b (b) S a 3 c (a) R e 5 f (c) R?S R.A R.B R.C S.A S.B S.C b 2 d a 3 c b 2 d b 2 d A B C b 2 d e 5 f b 3 b b 3 b a 3 c d 3 b b 3 b b 2 d b 3 b e 5 f (d) R,S c 2 d a 3 c c 2 d b 2 d A B C c 2 d e 5 f b 2 d d 3 b a 3 c d 3 b b 2 d (e) R?S d 3 b e 5 f (f) R×S 图2-3 关系R、S及它们的传统集合 运算 乘积运算在理论上要求参加运算的关系没有同名属性。通常我们在结果关系的属性名前加上<表名>.来区分,这样即使当R和S中有相同的属性名时,也能保证结果关系具有唯一的属性名(为了书写方便,当某个属性名没有同名时,也可以直接使用属性名)。当然,当需要得到一个关系R和其值上的乘积时,表达式R×R是非法的,因为它将导致非唯一的属性名。为此必须引入R的别名,比如说G。从而把关系R作为另一个关系S来使用,这样就能把表达式写为R×G,以便产生需要的唯一的属性名。 【例2.6】关系R和S如图2-3(a)、(b)所示,则R和S的乘积运算如图2-3RS,(f)所示。 2. 专门的关系运算 在关系的运算中,由于关系数据结构的特殊性,在关系代数中除了需要一般的集合运算外,还需要一些专门的关系运算包括:选择、投影、连接和除等。 ? 选择 选择运算是在关系R中选择满足条件F的所有元组组成的一个关系。记作 ,(){|()}RttRFttrue,,,,F 其中,F表示选择条件,它是一个逻辑表达式,取值为“true”或“false”。 逻辑表达式F的基本形式为: XYXY,,,[]1122 θ表示比较运算符,它可以是,、?、,、?、,和?。X,Y等是属性名或简单函数。11 属性名也可以用它在关系中从左到右的序号来代替。Φ表示逻辑运算符,它可以是。,,,、、[ ]表示任选项,即[ ]中的部分可以要也可以不要,„表示上述可以重复下去。 选择运算是单目运算符,即运算的对象仅有一个关系。选择运算不会改变参与运算关系的关系模式,它只是根据给定的条件从所给的关系中找出符合条件的元组。实际上,选择是从行的角度进行的水平运算,是一种将大关系分割为较小关系的工具。 ,()R,()R【例2.7】 设关系R和S如图2-3(a)、(b)所示,计算或[1]''[2]3,,,bAbB,,,''3 的结果如图2-4(a)所示,或的结果如图2-4(b)所示。 ,()S,()S[2]3[3]'',,,cBCc,,,3'' A B C A B C b 2 d b 2 d e 5 f ,()R (a)AbB,,,''3 ,()S(b) BCc,,,3'' 图2-4 选择 ? 投影 投影运算是从一个关系中,选取某些属性(列),并对这些属性重新排列,最后从得出的结果中删除重复的行,从而得到一个新的关系。 设R是n元关系,R在其分量A,A,„,A (m?n;i1,i2,„,im为1到m之间i1i2im 的整数,可不连续)上的投影操作定义为: ,,,,,,,,,{t|tt,t,tt,,t,tt,tn}Ri1,i2,,imi1i2im1i1i2im 即取出所有元组在特定分量A,A,„,A上的值。 i1i2im 投影操作也是单目运算,它是从列的角度进行的垂直分解运算,可以改变关系中列的顺序,与选择一样也是一种分割关系的工具。 【例2.8】设关系R和S如图2-3(a)、(b)所示,计算和的结果如图,()R,()SAC,CB,2-5(a)和(b)所示。 A C C B b d c 3 b b d 2 c d f 5 d b (b),()SCB, (a) ,()RAC, 图2-5 投影 ? 连接 连接是从两个关系的广义笛卡尔积中选取属性间满足一定条件的元组。连接又称θ连接。记作: RStttttRtStAtBRS,,,,,,,,,,,{|,[][]}(),,rsrsrsAB,AB, 其中,A和B分别是R和S上个数相等且可比的属性组(名称可不相同)。AθB作为比较公式F,F的一般形式为F?F?„?F,每个F是形为tAtB[][],的公式。对于连接条件的重要12nirisj 限制是条件表达式中所包含的对应属性必须来自同一个属性域,否则是非法的,即属性得来性必须相同。 若R有m个元组,此运算就是用R的第p个元组的A属性集的各个值与S的B属性集从头至尾依次作θ比较。每当满足这一比较运算时,就把S中该属性值的元组接在R的第p个元组的右边,构成新关系的一个元组。反之,当不满足这一比较运算时就继续作S关系B属性集的下一次比较。这样,当p从1遍历到m时,就得到了新关系的全部元组。新关系的属性集取名方法同乘积运算一样。 【例2.9】设关系R和S如图2-3(a)、(b)所示,计算的结果如图2-6所示。 RSBB, R.A R.B R.C S.A S.B S.C b 2 d a 3 c b 2 d e 5 f b 3 b e 5 f c 2 d a 3 c c 2 d e 5 f d 3 b e 5 f 图2-6 RSBB, 连接运算中有两种最为重要也是最为常用的连接:等值连接和自然连接。 ? 等值连接 当一个连接表达式中所有运算符θ取“=”时的连接就是等值连接,是从两个关系的广义笛卡尔乘积中选取A,B属性集间相等的元组。记作: RStttttRtStAtBRS,,,,,,,,,,,{|,[][]}(),,rsrsrsAB,AB, 若A和B的属性个数为n,A和B中属性相同的个数为k(n?k?0),则等值连接结果将出现k个完全相同的列,即数据冗余,这是它的不足。 RS【例2.10】设关系R和S如图2-3(a)、(b)所示,计算的结果如图2-7所示。 AA, R.A R.B R.C S.A S.B S.C b 2 d b 2 d b 3 b b 2 d RS 图2-7 AA, ? 自然连接 等值连接可能出现数据冗余,而自然连接将去掉重复的列。 自然连接是一种特殊的等值连接,它是两个关系得相同属性上作等值连接,因此,它要求两个关系中进行比较的分量必须是相同的属性组,并且将去掉结果中重复的属性列。 如果R和S有相同的属性组B,Att(R)和Att(S)分别表示R和S的属性集,则自然连接记作: RSRS,,{(())},,AttRAttSBtBtB()((){})[][],, 此处t 表示:。 {|}ttRS,, 自然连接与等值连接的区别是: ? 等值连接相等的属性可以是相同属性,也可以是不同属性;自然连接相等的属性不须是相同的属性。 ? 自然连接必须去掉重复的属性,特指相等比较的属性,而等值连接无此要求。 ? 自然连接一般用于有公共属性的情况。如果两个关系没有公共属性,那么它们的自然连接就退化为广义笛卡尔乘积。如果是两个关系模式完全相同的关系自然连接运算,则变为交运算。 【例2.11】设关系R、S和Q如图2-8(a)、(b)、(c)所示,计算的结果如图RS2-8(d)所示,RQ的结果如图2-7(e)所示。 A B C B C A B a 3 c 2 d b 2 b 2 d 3 b g 6 c 2 d (b)S (c)Q e 5 f g 6 f (a)R A B C A B C 图2-8 自然连接 ? 除 给定关系R(X,Y)和S(Y,Z),其中X,Y,Z为属性或属性集。R中的Y和S中的Y可以有不同的属性名,但必须出自相同的域集。R?S是满足下列条件的最大关系:其中每个元组t与S中的各个元组s组成的新元组必在R中。定义形式为: RSRRSRttRsStsR,,,,,,,,,,,,,,,,()((())){|(),,,}且XXXX 关系的除操作需要说明的是: ? R?S的新关系属性是由属于R但不属于S的所有属性构成的。 ? R?S的任一元组都是R中某元组的一部分。但必须符合下列要求:即任取属于R?S的一个元组t,则t与S的任一元组相连后,结果都为R中的一个元组。 ? RXYSYZRXYS(,)(,)(,)(),,,,Y ? R?S的计算过程如下: i. ; HR,,()X ii. ; WHSR,,,() iii. ; KW,,()X iv. RSHK,,, 【例2.12】设关系R、S和Q如图2-9(a)、(b)、(c)所示,计算R?S的结果如图2-9(d)所示,R?Q的结果如图2-9(e)所示。 A B C B C A B A C a 3 e 2 d a 2 a d a 2 d 3 e g 2 (e)g RQ, g 2 d (b)S (c)Q (d)RS, g 3 e c 6 f 图2-9 除运算 (a)R 【例2.13】设有科研参与关系EP和项目关系P,其中Eno代表员工编号、Pno代表项 目编号,如图2-10(a)和(b)所示,计算EP?P的结果如图2-9(c)所示。 Eno Pno Pno Eno P001 430127 430425 P001 P002 (c)EP?P 430211 P002 P003 430127 P003 (b)P 430211 P001 430127 P001 图 2-10 除运算 根据除运算的定义,该例子的运算结果的实际意义应该是参与了所有项目的员工有哪些。只有员工号为“430127”的员工是参与了所有三个项目的。 可以证明,关系代数操作集是完备的操作集,任何其它关系代数操作都{,,,,},,,, 可以用这五种操作的组合来表示。任何一个DBMS,只要它能完成这五种操作,则它是关系完备的。当然,完备的操作集并不只有这一个。 2.2.2 关系代数运算实例 使用关系代数运算可以对关系数据库进行各种有目的的运算。利用图2-11中所示的学籍管理数据库以及某一时刻的值,根据要求对数据库的各关系进行运算。 Sno Cno grade Sno Sname Sex age place 02001 C01 83 02001 王明 男 21 广东 02001 C02 78 02005 黄小英 女 22 湖北 02001 C03 75 03035 张小倩 女 20 江西 02005 C01 81 03061 李刚 男 21 湖北 02005 C03 66 04009 张珊 女 18 浙江 03035 C01 54 04027 肖文 男 19 福建 03035 C02 89 (a)student关系 03035 C03 68 03035 C04 95 03035 C05 97 03061 C04 52 Cno Cname Credit 03061 C01 84 c01 操作系统 3 04009 C02 91 c02 C语言 4 04009 C03 93 c03 数据结构 3 04027 C02 74 c04 数据库原理 2 04027 C03 73 c05 软件工程 2 (c)study学习 (b)course关系 图2-11 学籍管理数据库 【例2.14】查询所有女生的基本情况。 分析:关系student的属性已包含了查询所需的数据,现要查询女生情况只要对关系表作水平分解的条件运算。 ,,(())student student,''女sex 当投影运算所牵涉的属性是关系的所有属性时,投影的属性可简写成关系的名字。计算结果如图2-12(a)所示。 【例2.15】查询年龄大于20岁的男生基本情况。 分析:本例和例2.14的求解思想一样,应先做关系的水平选择分解运算,再作投影运算。 ,,(())student student,,,''20男sexage 计算结果如图2-12(b)所示。 Sno Sname Sex age place Sno Sname Sex age place 02005 黄小英 女 22 湖北 02001 王明 男 21 广东 03035 张小倩 女 20 江西 03061 李刚 男 21 湖北 04009 张珊 女 18 浙江 (b) 图2-12 查询 (a) 【例2.16】查询张小倩同学所选修的课程号和相应的成绩。 分析:题设中所包含的数据信息有“张小倩”、“课程号”和“成绩”。其中“张小倩”是包含在student关系表中的姓名属性,“课程号”和“成绩”是study关系表中的属性。因此本例中所包含的信息分布在两个不同的关系表中。在study关系表中又存在外键“sno”与student关系表相联系所以可以使用自然连接运算将连个关系表连接在一起形成一个新的关系。然后用选择运算水平分解这个关系得出“张小倩”的所有信息,再用投影运算得出最终需要的列。 ,,(())studentstudy cnograde,,张小倩sname'' 计算结果如图2-13(a)所示。 【例2.17】查询选修了C语言的学生的学号和姓名。 分析:题设中所包含的信息有“C语言”、“学号”和“姓名”。其中“C语言”是course关系表中的课程号属性,“学号”和“姓名”是student关系表中的属性。这两个关系表虽没有直接的外键联系,但他们分别与study关系表有外键联系。因此要进行这样的查询必须将三个关系表都自然连接在一起才能具备题设中的所有信息。 ,,(())studentstudycourse snosname,,语言cnameC'' 计算结果如图2-13(b)所示。 Sno Cno grade Sno Sname 03035 C01 54 02001 王明 03035 C02 89 03035 张小倩 03035 C03 68 04009 张珊 03035 C04 95 04027 肖文 03035 C05 97 (b) (a) 图2-13 查询 【例2.18】查询选修了全部所开课程的学生的学号。 分析:题设中要查询的是选课信息表中选修了全部所开课程的学号,使用除法可以达到 这个目的。但study关系表有三个属性“Sno”、“Cno”、“Grade”,直接用study?course得出的关系模式会包含“Sno”和“Grade”属性而且达不到题设的目的。因此在进行除法运算之前先要对study关系表进行投影操作,使得除运算之后只含有一个属性“sno”。 ,()studycourse, snocno, 计算结果如图2-14(a)所示。 【例2.19】查询所有没选C04号课程的学生的学号。 分析:要达到题设的查询目的,可以先查询出选了C04号课程的学生有哪些,再用总的学生集合减去选了C04号课程的学生集合。 ,,,()(())studentgrade, snosnocno,'C04' 在进行除法运算之前一定要保持被除运算集合只含有两个属性。本例的计算结果如图2-14(b)所示。 Sno Sno 02001 03035 02005 (a) 04009 04027 图2-14 查询 (b) 2.2.3 关系演算 关系演算是利用谓词演算来表达关系操作的一种方法。按谓词变量的不同,关系演算又分为两种:一种是元组关系演算,以元组为变量,简称元组演算;另一种是域关系演算,以域为变过量,简称域演算。本书只介绍元组演算的简单运算,域演算相关知识请参阅其它资料。 元组演算中,元组关系演算表达式的一般形式为。其中,t是元组变量,它表示{|()}tt, 一个定长的元组。为元组演算公式,简称公式,它由原子公式和运算符组成。 ,()t 1. 原子公式的三种形式 ? R(t),其中R是关系名,t是元组变量。R(t)表示:t是关系R的一个元组。 ? t[i]θu[j],其中t和u是元组变量,θ是比较运算符。该原子公式表示:元组t的第i个分量与元组u的第j个分量之间满足θ关系。例如,t[2]>u[3]表示元组t的第2个分量必须大于元组u的第3个分量。 ? t[i] θc或cθt[i],其中t是元组变量,c是一个常量,该原子公式表示:元组t的第i个分量与常量c之间满足θ关系。例如,t[2]>4表示元组t的第2个分量必须大约4。 2. 运算符的优先级 ? 算术比较运算符的优先级最高。 ,,,,? 存在量词和全称量词的优先级次之,而存在量词的优先级又高于全称量词 ? 逻辑运算符优先级最低,并且按、、优先级从高到低。 ,,, ? 若有括号,括号的优先级最高。 3. 公式的定义规则 ? 任何原子公式都是公式。 ? 若φ是公式,则φ也是公式。当φ为真时φ为假。 ,, ? 若、是公式,则、也是公式。只有当、同为真时,,,,,,,,,,,,,,1121211222为真,否则为假。当、至少有一个为真时,为真。 ,,,,,1122 ? 若是公式,则也是公式。当存在一个t使得为真时,为真,否()(),t,()(),t,,,则为假。 ? 若是公式,则也是公式。当所有t都使为真时,为真,否则为()(),t,()(),t,,,假。 ? 所有公式都是从以上五条规则对原子公式进行有限次复合运算求得。 若公式中的一个元组变量前有存在量词或全称量词,则该元组变量称为“约束元组变量”, 否则称为“自由元组变量”。在元组关系演算表达式中,t是唯一的自由元组变量。 {|()}tt, 4. 元组关系演算与关系代数的等价性 在上一节中已经提到,如果一个关系运算体系至少能具有五种基本的关系代数运算功能, 则该关系运算体系是完备的。因此只要五种基本的关系代数运算能等价的用元组演算表达式 表示,则元组关系演算体系也就是完备的。 (1) 并 RStRtSt,,{|()()} (2) 差 RStRtSt,,,,{|()()} (3) 广义笛卡尔积 (1)mmn, RStuvRuSvtu,,,,,,,,{|()()(()()[1][1] ,,,,,,,,,tmumtmvtmnvn[][][1][1][][])} (4) 选择 ,,(){|()}RtRtF,, F ,FF是在元组演算中等价的表示形式。 (5) 投影 ()m ,(){|()(()[1][][][])}RtuRutuitmui,,,,,,,12miiiim,, 5. 元组演算实例 下面通过不同的方式列举几个元组关系演算的示例,请读者仔细阅读示例夹生对元组关系演算的理解。 【例2.20】设有如图2-15所示的关系R、S、Q,计算下面关系元组演算表达式。 RtRttBtCf,,,,,{|()[]3[]}1? RtuStQutBuE,,,,,{|()(()()[][])}2? RtuvSuQvuChtuBtuCtvD,,,,,,,,,,,,{|()()(()()[][1][][2][][3][])}3? 元组关系运算的结果如图2-15所示。 A B C A B C A B C b 6 e b 6 e a 2 f d 5 h d 5 h d 5 h b 4 f b 4 f g 3 f R2 g 8 e b 7 f R S B C D A B C D E 5 h e g 3 f e 7 5 h k k 6 b 7 f R3 RQ 1 图2-15 元组关系演算示例 【例2.21】利用图2-11中所示的学籍管理数据库,进行下列运算。 (1) 所有女学生的学生信息 {[]|()[]''}xstudentstudentxxsex,,女 (2) 男生的学号,年龄 {[,]|()(()[]''[][][][])}xsnoageystudentyysexysnoxsnoyagexage,,,,,,,男 (3) 所有年龄小于22的男生姓名,课程号,成绩 {[,,]|()(()[]''[]22()(()xsnamesnoageystudentyysexyagezstudyz,,,,,,,男 ,,,,,,,,zsnoysnozcnoxcnozgradexgradeysnamexsname[][][][][][])[][])} (4) 所有选修了数据库的学生的学号,姓名 {[,]|()()(()()[][]()(()xsnosnameyzstudentystudyzysnozsnotcourset,,,,,,, ,,,,,,,,tcnozcnotcnamexsnoysnoxsnameysname[][][]''[][][][]))}数据库 2.3 查询优化 查询检索是数据库系统最主要的功能,查询速度的快慢直接影响系统效率。关系模型虽有坚实的理论基础,但其主要的确定就是查询效率较低。若不能解决这个问题则关系模型也很难得到推广。 查询效率不高并非关系模型特有的问题,在所有的非过程或语言当中都存在这个问题。在前面几节介绍的两类关系运算语言都是非过程化语言,用户使用时只需指出他所需要的数据及查询要求,而不必指出通过哪些存取路径来得到这些数据,由DBMS自动安排存取路径。因此,用户使用是方便了,系统的负担却重了。然而这又是数据独立性的表现。可见系统效率和数据独立性、用户使用的便利性和系统实现的便利性都是互相矛盾的。为了解决这些矛盾,必须使系统能自动进行查询优化。 2.3.1 查询优化实例 首先来看下列问题,说明为什么要进行查询优化。 利用图2-11中所示的学籍管理数据库,求选修了C2号课程的学生的姓名。假定学生管理数据库中有1000个学生记录,10000个学生选课记录,其中选修了C2号课程的选课记录为50个。 根据要求,系统可以采用多种等价的关系代数表达式来完成这一查询 Qstudentstudy1(()),,,,snamestudentsnostudycnostudycnoC...'2',,, Qstudentstudy2(()),,,snamestudycnoC.'2', Qstudentstudy3(()),,,snamestudycnoC.'2', 接下来我们分析这三种关系代数表达式就可以由于查询执行的策略不同,查询时间相差很大。 1. 第一种情况 (1) 计算广义笛卡尔积 把student和study的每个元组连接起来。一般的做法是:在内存中尽可能多地装入某一个表(如student表)的若干块元组,留出一块存放另一个表(如study表)的元组。然后把study表中的每一个元组连接,连接后的元组装满一块后就写到中间文件上,再一次读入若干块student元组,读入study元组,重复上述处理过程,直到把student表处理完。 设一个块能装10个student元组,在内存中存放5块student元组和1块study元组,则读取总块数为: 1000 / 10+(1000 / (10*5 ) ) * ( 10000 / 100 ) = 100 + 20 * 100 = 2100 其中读student表100块,读study表20遍,每遍100块。若每秒读写20块,则总计要花105s。 3476连接后的元组数为10 * 10 = 10。设每块能装10个元组,则写出这些块要用10 4/20=5*10s (2) 作选择操作 依次读入连接后的元组,按照选择条件选取满足要求的记录。假定内存处理时间忽略。 4这一步读取中间文件花费的时间需5*10s。满足条件的元组假设仅50个,均可放在内存。 (3) 作投影 把第2步的结果在sname上作投影输出,得到最终结果。因此第一种情况下执行查询 45的总时间=105+2 * 5 * 10?10s。这里,所有内存处理时间均忽略不计。 2. 第二种情况 (1) 计算自然连接 为了执行自然连接,读取student和study表的策略不变,总的读取块数仍为2100块花 4费150s。但自然连接的结果比第一种情况大大减少,为10个。因此写出这些元组时间为410 / 10 / 20 = 50s,仅为第一种情况的千分之一。 (2) 读取中间文件快,执行选择运算,花费时间也为50s。 (3) 把第2步结果投影输出。 第二种情况总的执行时间?105 + 50 + 50 ?205s。 3. 第三种情况 (1) 先对study表作选择运算,只需读一遍study表,存取100块花费时间为5s,因为满足条件的元组仅50个,不必使用中间文件。 (2) 读取student表,把读入的student元组和内存中的study元组作连接,也只需读一遍student表共100块花费时间为5s。 (3) 把连接结果输出。 第三种情况总的执行时间?5 + 5 ?10s。 这个例子充分说明了查询优化的必要性,同时也给出了一些查询优化方法的初步概念。下面给出优化的一般策略。 2.3.2 查询优化准则 查询优化主要是合理安排操作的顺序,使系统效率较高。优化是相对的,变化后的表达式不一定是所有等价表达式中执行时间最少的。但下面这些原则一般都是有效的。 ? 尽可能早的执行选择操作。在查询优化中,这是最基本的一条。选择运算可以水平分割关系,不仅能使中间结果显著变小,而且可使执行时间成数量级的减少。 ? 在一些使用频率较高的属性上,建立索引和分类排序,这样在执行这些属性域上的条件查询时,DBMS就可以利用索引表和分类排序表进行折半查找和二叉排序树查找这可大大提高查询效率。 ? 同一关系上的投影和选择运算同时进行,这样可避免重复扫描关系,从而节省操作时间。 ? 把选择与选择前面的笛卡尔积结合起来成为一个连接运算。而连接运算比同样关系上的笛卡尔积要省很多时间。 ? 把投影运算与其前后的双目运算结合起来进行。以免重复扫描文件。 ? 找出公共子表达式,并将该表达式结果预先计算并加以保留,需要时直接从文件读取,以免重复计算。 2.3.3 关系代数等价变换规则 关系代数是各种数据库查询语言的基础,各种查询语言都能够转换成关系代数表达式。 所以关系代数表达式的优化是查询优化的基本方法。所谓关系代数表达式的等价,是指用相 同的关系代替两个表达式中相应的关系后,取得的结果关系是相同的。 两个关系表达式E1和E2等价时,可表示为:E1?E2。 常用的等价变换规则有: 1. 连接和笛卡尔积的等价交换律 (1) 设E1和E2是两个关系代数表达式,F是连接运算的条件,则: EEEE1221,,, EEEE1221, EEEE1221,FF (2) 设E1、E2和E3是三个关系代数表达式,F1和F2是两个连接运算的限制条件,则: (12)31(23)EEEEEE, (12)31(23)EEEEEE,FFFF1212 (12)31(23)EEEEEE,,,,, 2. 投影的串联等价规则 设E是一个关系代数表达式,A1,A2,„,An是属性名,并且 BiAAAnin,,{1,2,,}(1,2,,) 则: ,,,(())()EE,BBBmAAAnBBBm1,2,,1,2,,1,2,, 3. 选择的串联等价规则 设E是一个关系代数表达式,F1和F2是两个选择条件,则: ,,,(())()EE,FFFF1212, 本规则说明,选择条件可合并成一次处理。 4. 选择和投影的交换规则 设E为一个关系代数表达式,选择条件F只涉及属性A1,A2,„,An,则: ,,,,(())(())EE, FAAAnAAAnF1,2,,1,2,, 若上式中F还涉及不属于A1,A2,„,An的属性集B1,B2,„,Bm,则有: ,,,,,(())((()))EE, AAAnFAAAnFAAAnBBBm1,2,,1,2,,1,2,,,1,2,, 5. 选择和笛卡尔积的交换规则 设E1和E2 是两个关系代数表达式,若条件F只涉及E1的属性,则有 ,,(12)(1)2EEEE,,,FF 若有F=F1?F2,并且F1只涉及E1中的属性,F2只涉及E2中的属性,则 ,,,(12)(1)(2)EEEE,,,FFF12 若F1只涉及E1中的属性,F2却涉及了E1和E2两者的属性,则有 ,,,(12)((1)2)EEEE,,,FFF21 由于选择运算是水平分割关系表,因此提前执行选择运算操作是重要的操作规则。 6. 选择与并交换的规则 设E1和E2有相同的属性名,则 ,,,(12)(1)(2)EEEE,FFF 7. 选择和差交换的规则 设E1和E2有相同的属性名,则 ,,,(12)(1)(2)EEEE,,,FFF 8. 投影与并交换的规则 设E1和E2有相同的属性名,则 ,,,(12)(1)(2)EEEE,AAAnAAAnAAAn1,2,,1,2,,1,2,, 9. 投影与笛卡尔积的交换规则 设E1和E2是两个关系代数表达式,A1,A2,„,An是E1的属性,B1,B2,„, Bn是E2的属性,则 ,,,(12)(1)(2)EEEE,,, AAAnBBBnAAAnBBBn1,2,,,1,2,1,2,,1,2,, 利用上述的等价规则,我们可以将关系代数表达式进行优化,这对于改善查询效率可以 起很好的作用。 2.3.4 关系代数表达式优化的算法 在关系的优化过程中,关系代数的等价变换规则是优化的重要基础。根据优化准则,尽可能早的执行选择操作,多步操作组合一步完成,进行适当的预处理,计算公共子表达式等。 关系查询优化的步骤一般有以下四个: ? 把查询结果转换成内部表示形式,一般是语法树。 ? 选择合适的等价变换规则,把语法树转换成优化形式。 ? 选择底层的操作算法,根据存取路径,数据的存储分布情况等,为语法树中的每个操作选择合适的操作算法。 ? 生成查询执行。由以上三条最后生成了一系列的内部操作。根据这些内部操作要求的执行次序,确定一个执行方案。 利用等价变换规则,实用化后的表达式能遵循优化准则,这就是优化算法的工作。下面给出优化的基本算法。 算法:关系代数表达式的优化。 输入:一个关系代数表达式的语法树。 输出:表达式的优化程序。 优化的基本方法如下: ? 利用关系代数等价变换规则4把形如的式子变换为 ,()EFFFn12,,, ,,,((()))EFFF12 ? 对于每一个选择,使用变化规则4到规则8,尽可能把它移到数的叶端(即尽可能是它提早一点执行)。 ? 对每一个投影,利用变化规则3、5、9,也把它尽可能移到树的叶端。 ? 利用规则3、4、5把选择和投影串接成单个选择、单个投影或一个选择后跟一个投影,使多个选择或投影能同时执行或在一次投影中同时完成。 ? 将上述得到的语法书的内结点分组,每个二目运算(×、?、?、,)结点与其直接祖先被分为一组(这些直接祖先由σ、?表示)。如果它的子结点一直到叶子都是单目运算(σ、?)则把它们并入该组。但当二目运算是笛卡尔积(×),且后面不是能与它结合成等值连接的选择时,这些一直到叶子的单目运算必须单独分为一组。 ? 每一组的计算必须在其后代组计算后,才能进行。根据此限制,生成求表达式的程序。 下面举例说明关系代数表达式优化的方法。 【例2.22】考虑由以下关系组成的图书馆数据库。 BOOKS(TITLE,AUTHOR,PNAME,LC_NO) READERS(NAME, ADDR,CITY,CARD_NO) LOANS(CARD_NO,LC_NO,DATE) 其中各表名和属性的含义如下: BOOKS是书籍关系表:TITLE——书名、AUTHOR——作者姓名、PNAME——作者名、LC_NO——图书编号;READERS是读者关系表:NAME——读者姓名、ADDR——读者街道地址、CITY——读者所在城市;LOANS是借阅关系表:CARD_NO——借书证编号、DATA——书籍借阅日期。 现在需查询“找出2005年元旦以前借出书籍的书名和读者姓名”。显然这个问题可以写成如下的关系代数运算表达式: ,BOOKS.LC_NOLOANS.LC_NOREADERS.CARD_NOLOANS.CARD_NO,,,, BOOKSREADERSLOANS,,,,DATE20050101, ? 生成初始查询树如图2-16所示: π TITLE,NAME BOOKS.LC_NO=LOANS.LC_NO? σ READERS.CARD_NO=LOANS.CARD_NO? DATE<20050101 × BOOKS × READERS LOANS 图2-16 初始查询树 ? 将关系代数表达式中的多条件选择运算分为三个选择元算 ,BOOKSREADERSLOANS,,,,BOOKS.LC_NOLOANS.LC_NO, ,READERSLOANS,,,READERS.CARD_NOLOANS.CARD_NO, ,LOANS,,DATE20050101, π TITLE, NAME BOOKS.LC_NO=LOANS.LC_NO σ READERS.CARD_NO=LOANS.CARD_NO × BOOKS σ DATE<20050101 × READERS σ 图2-17 尽可能提前选择运算后的查询树 把三个选择运算尽可能移近树叶一端后,原来的查询树变成图2-17的形式。 LOANS ? 合并乘积与其后的选择为连接运算,得到图2-18所示形式。 π TITLE, NAME BOOKS.LC_NO=LOANS.LC_NO READERS.CARD_NO=LOANS.CARD_NO BOOKS DATE<20050101 READERS σ LOANS 图2-18 合并乘积与其后的选择 ? 此例中因经选择操作后的LOANS关系于READERS关系的连接结果明显小于LOANS与BOOKS连接的结果,所以仍然按图2-18所示运算次序操作。否则亦可选择图2-19所示运算顺序。 π TITLE, NAME READERS.CARD_NO=LOANS.CARD_NO READERS READERS.LC_NO=LOANS.LC_NO BOOKS σ DATE<20050101 LOANS 图2-19 改变连接顺序 ? 在整个运算过程中BOOKS关系仅用到TITLE和LC_NO两个属性,因此在叶结点BOOKS上增加一个投影运算。同样处理READERS和LOANS两个关系。READERS、LOANS两关系连接后,只有NAME和LC_NO两属性参加后续运算,故增加一个投影运算。最终得到如图2-20的查询树。 π TITLE,NAME BOOKS.LC_NO=LOANS.LC_NO π TITLE,LC_NO π NAME, LOANS.LC_NO READERS.CARD_NO=LOANS.CARD_NO BOOKS π NAME, CARD_NO π LC_NO, CARD_NO READERS σ DATE<20050101 LOANS 图2-20 增加必要的投影 2.4 小结 关系数据模型的数据结构是二维表,基本概念包括:关系、关系模式、属性、域、元组、分量、超关键字、候选关键字和外部关键字等。 关系可以用二维表来表示,但在关系中,元组之间是没有先后次序的,属性之间也没有前后次序。 一个关系的完整模式为:R(U,D,dom,F),其中,R为关系名,U为该关系所有属性名的集合,D为属性组U中的属性所来自的域集合,dom为属性向域映象的集合,F为属性间数据依赖关系的集合。通常关系模式简写为:R(U)。 对关系数据的操作可以用关系代数或关系演算来表达。它们都是实际的关系语言的基础,并且互相是等价的。关系代数是通过对关系的运算来表达查询的。它的运算包括传统的集合运算和专门的关系运算。传统的集合运算有:并、交、差、乘积等。专门的关系运算有:选择、投影、连接和求商。其中:并、差、投影、选择、连接和求商运算构成了一个完备的操作集合,其他的关系代数操作都可用这五种操作的组合来实现。关系演算用谓词表示关系,有两种形式:元组关系演算和域关系演算,它们分别用关系的元组和域作为谓词变量。 关系模型有着十分明显的优点,但它也有着查询效率低等缺点。因此查询优化是关系数据库管理系统实现的一项基本技术。其中的代数优化是指DBMS将用户的查询表达式进行变换,得到与原来查询等价的并且较优的查询表达式,以提高检索效率。查询优化对用户是透明的。 习题2 1. 名词解释下列名词 关系、关系模式、属性、域、元组、超关键字、候选键、主键、外键 2. 为什么关系中的元组没有先后顺序,且不允许有重复元组, 3. 外键值何时允许空,何时不允许空, 4. 笛卡儿积、等值联接、自然联接三者之间有什么区别, 5. 设有关系R和S: R S A B C A B C 3 6 7 3 4 5 2 5 7 7 2 3 7 2 3 4 4 3 SR 计算R?S,R-S,R?S,R×S,π(S),σ(R), R S, 。 3,2B<’5’2<2 6. 设有关系R和S: R S A B B C a b b c c b e a d e b d 计算R ? S,R ? S,σ(R×S) A=C B< C 7. 设关系U和V分别有m个元组和n个元组,给出下列表达式中可能的最小和最大的元 组数量: ?? U?V ? U?V ? UV ? σ(U)×V (F为某个条件) F 8. 假设R和S分别是三元和二元关系,试把表达式π1,5(σ2=4?3=4(R×S))转换成等价的: ?汉语查询句子; ?元组表达式。 9. 有两个关系R (A, B, C)和是S(D, E, F),试把下列关系代数表达式转换成等价的元组表 达式: ?π(R); ?σ(R);? ?(σ(R×S) πAB=’17’RA,FC=D; ×S 10. 设有三个关系: S(SNO,SNAME,AGE,SEX) SC(SNO,CNO,CNAME) C(CNO,CNAME,TEACHER) 试用关系代数表达式表示下列查询语句: ? 检索LIU老师所授课程的课程号和课程名。 ? 检索年龄大于23岁的男学生的学号和姓名。 ? 检索学号为S3学生所学课程的课程名与任课教师名。 ? 检索至少选修LIU老师所授课程中一门课的女学生姓名。 ? 检索WANG同学不学的课程的课程号。 ? 检索至少选修两门课的学生学号。 ? 检索全部学生都选修的课程的课程号与课程名。 ? 检索选修课程包含LIU老师所授全部课程的学生学号。 11. 在教学数据库的关系S、SC、C中,用户有一查询语句:检索女同学选修课程的课程名和任课教师名。 ? 试写出该查询的关系代数表达式。 ? 画出查询表达式的语法树。 ? 使用关系代数优化算法,对语法树进行优化,并画出优化后的语法树。
/
本文档为【关系数据模型】,请使用软件OFFICE或WPS软件打开。作品中的文字与图均可以修改和编辑, 图片更改请在作品中右键图片并更换,文字修改请直接点击文字进行修改,也可以新增和删除文档中的内容。
[版权声明] 本站所有资料为用户分享产生,若发现您的权利被侵害,请联系客服邮件isharekefu@iask.cn,我们尽快处理。 本作品所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用。 网站提供的党政主题相关内容(国旗、国徽、党徽..)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。

历史搜索

    清空历史搜索