「 数据库原理 」查询优化（关系代数表达式优化）
关系代数表达式是进行数据库查询前的理论部分，在简单的查询中一般不会想到这个，直接上sql语句就行。但是一旦涉及大范围或者超多表查询，关系代数表达式能够组织逻辑并且基于关系代数表达式的优化，能够很大程度上优化最后的查询语句，从而提高查询效率。当然先写出sql语句，在对sql语句进行优化实际上一样的。查询优化的目标：选择有效的策略求给定关系表达式的值使查询代价最小（实际上只能是较小）优化的部分：并不是所有的部分都可以进行优化的，而我们知道在关系代数的运算中最消耗时间的两个操作：笛卡尔积 和 连接运算优化策略：代数优化即有选择和连接操作时，先做选择操作，这样参加连接的元组就可以大大减少，这是代数优化.
物理优化选择操作算法有**全表扫描**和**索引扫描**2种方法，&font color=&red&&索引扫描方法较优&/font&
对于AB表的连接，利用A表上的索引，&font color=&red&&采用index join代价也较小&/font&
代数优化策略:主要说一下代数优化：通过对关系代数表达式的等价变换来提高查询效率 代数等价概念：关系代数表达式的等价：指用相同的关系代替两个表达式中相应的关系所得到的结果是相同的两个关系表达式E1和E2是等价的，可记为E1≡E2关系代数等价变换规则：连接、笛卡尔积交换律
E1 x E2 ≡ E2 x E1
E1 ? E2 ≡ E2 ? E1
E1 ? E2 &sub&F&/sub&≡ E2 ? E1 &sub&F&/sub&
2. 连接、笛卡尔积结合律投影的串接定律选择的串接定律选择与投影的交换律选择与笛卡尔积交换律选择与并的交换选择与差运算的交换投影与笛卡尔积的交换投影与并的交换表达式转换的启发式规则：尽可能早地执行选择操作尽可能早地执行投影操作避免直接做笛卡儿积，把笛卡儿积操作之前和之后的一连串选择和投影合并起来一起做关系代数表达式的启发式优化算法：利用规则4进行选择条件分解对每一个选择，利用规则4-8尽量把它移到树的叶端对每一个投影，利用规则3，9，10，5中的一般形式尽可能把它移到树的叶端利用规则3-5把选择和投影的串接合并成单个选择、单个投影或一个选择后跟一个投影把上述得到的语法树的内结点分组生成一个程序，每组结点的计算是程序中的一步示例：设有三个关系 A（a1,a2,a3,…）、B（b1,b2,b3, … ）、C（a1,b1,c1,c2, … ）有一个查询请求如下：SELECT
A.a1 FROM A，B，C WHERE
A. a1 =C. a1 AND B. b1 =C. b1 AND f(c1)优化如下：1. 将查询语言转换成语法树2. 选择条件分解（规则4）
3. 选择操作下移
4. 投影操作下移
5. 选择和投影的串接合并（规则5）
6. 内结点分组内结点分组算法：内结点分组其实比较简单从一个笛卡尔积（也就是 X ）出发，往上（父节点）全部囊括进去，直到遇见另一个笛卡尔积（x）从一个笛卡尔积出发，找子节点，当发现子节点连着一个笛卡尔积（x）时，这条线上的所有的选择和投影均去掉（属于下面连接的笛卡尔积，因为规则1说明了，从一个笛卡尔积往上的父节点全部囊括除非遇到了另一个笛卡尔积）3.从一个笛卡尔积出发，当发现某条线上的子节点一直连接到叶子节点，那么这条线的连接和投影操作均属于该笛卡尔积的内结点分组。可以参照步骤6中的图经过优化后的查询操作，比起一开始的语句，已经优化的太多了。
文章版权：
本文链接：
转载请注明文章原始出处 !
扫描二维码,在手机阅读！
添加新评论更多相关文档设A={a,b,c,d},A上的等价关系,R={&a,b&&b,a&&c,d&&d,c}并IA,求出A中个元素的等价类_百度知道
设A={a,b,c,d},A上的等价关系,R={&a,b&&b,a&&c,d&&d,c}并IA,求出A中个元素的等价类
我有更好的答案
答:元素a和b具有相同等价类，元素c和d具有相同等价类
[a]=[b]={a,b}
[c]=[c]={c,d}
为您推荐：
其他类似问题
等价关系的相关知识
换一换
回答问题，赢新手礼包
个人、企业类
违法有害信息,请在下方选择后提交
色情、暴力
我们会通过消息、邮箱等方式尽快将举报结果通知您。离散数学中设R是集合A上的等价关系，则R所具有的关系的三个特性是？
对于任意的a∈A，因为R是等价关系，所以aRa，由S的定义可知(a,a∈S。所以S非空且有自反性。
如果a,∈S，那么存在c∈A，使得aRc，cR。因为R是等价关系，有对称性，所以Rc，cRa，由S的定义可知,a∈S。所以S有对称性。
如果a,,,c∈S，那么存在d∈A，使得aRd，dR。存在e∈A，使得Re，eRc。因为R是等价关系，有传递性，所以由dR，Re，eRc可知dRc。由aRd，dRc以及S的定义可知a,c∈S，所以S有传递性。
所以，S是等价关系。
答: 垂直于同一条直线的两个平面互相平行这句话是对的。常被用来判定两个平面平行。证明过程在：人教版高中第二册（下）（2004年9月第一版）的第30页，例一。
答: 学习要学好，有三个重要因素：一是兴趣，二是技巧，三是毅力。
先培养孩子对数学的兴趣，比如在孩子解出难题的时候给予表扬，告诉孩子你真聪明、可以把数学学好等，树立孩...
答: 简而言之,概率论是属于随机数学的范畴,即研究随机现象的一门自然科学。
答: 中国人的数学理应比外国人好！ 这是我的个人观点，这在于中国人对数字的发音是单音，因此，对数字的记忆较为简单，提高了学习数学的效率！
而科学的发展，往往受制于社会...
大家还关注
Copyright &
Corporation, All Rights Reserved
确定举报此问题
举报原因(必选)：
广告或垃圾信息
激进时政或意识形态话题
不雅词句或人身攻击
侵犯他人隐私
其它违法和不良信息
报告，这不是个问题
报告原因(必选)：
这不是个问题
这个问题分类似乎错了
这个不是我熟悉的地区
相关问答：123456789101112131415赞助商链接
当前位置： >>
第2章 关系数据模型 数据库原理及应用讲义
第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 中的员工人事数据表。关系模式 员工编号 430 关系 121 430248 姓名 王天喜 莫玉 肖剑峰 杨琼英 赵继平 年龄 25 27 33 23 41 性别 男 女 男 女 男 部门号 Deno1 Deno2 Deno3 Deno2 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 1 、D 2 、D 3 、……、D n ，则在D 1 、D 2 、D 3 、……、D n 上的笛卡尔积为： D 1 ×D 2 ×D 3 ×……×D n ={ (d 1 、d 2 、d 3 、……、d n ) | d i ∈D i ,i=1,2,3,……,n } 其中每一个元素 (d 1 、d 2 、d 3 、……、d n ) 叫做一个元组 (n-tuple)或简称元组 (Tuple)。 元素中的每一个值叫做一个分量 ( Component)。一个元组是组成该元组的各分量的有序集 合，而不仅仅是各分量集合。 若D i (i=1,2,3,……,n)为有限集，其基数 (Cardinal Number)为m i (i=1,2,3,……,n)， 则D 1 ×D 2 ×D 3 ×……×D n 的基数为：M = ∏ mii =1n笛卡尔积可表示为一个二维表。表中的每行对应一个元组，表中的每列对应一个域。 【例 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 1 ×D 2 ×D 3 ×……×D n 的任意一个子集 A B C 叫做在D 1 、D 2 、D 3 、……、D n 上的一个n元关系，简称 a1 b1 c1 关系。每个关系都有一个关系名。必须指出的是：构成 a1 b1 c2 笛卡尔积的集合是有序的，形成的元组分量也是有序 a1 b2 c1 的，因此其子集也是有序的。 a1 b2 c2 从上面的定义可以看出，关系是笛卡尔积的子集， 因此可以用二维表来表示。二维表的名字就是关系的名 a2 b1 c1 字，二维表的每一列都是一个属性。n元关系就会有n个 a2 b1 c2 属性。一个关系中每一个属性都有一个名字，且各个属 a2 b2 c1 性的属性名都不同，对应参与笛卡尔积运算的每个集合 a2 b2 c2 的名字。一个属性的取值范围D i (i=1,2,3,……,n)称为 该属性的域 ( Domain)。对应参与笛卡尔积运算的每个 表 2-1 二维表 集合的值域，所以不同的属性可以有相同的域。二维表 的每一行值对应于一个元组。 在数学中，笛卡尔积形成的二维表的各列是有序的，而在关系数据模型中对属性、元组 的次序交换都是无关紧要的。当然，关系的属性、元组按一定的次序存储在数据库中。但这 仅仅是物理存储的顺序，而在逻辑上，属性、元组在关系数据模型中都不作规定。 在关系数据模型中，关系可以有三种类型：基本表（或基表） 、查询表和视图表。基本 表是实际存在的表，它是实际存储数据的逻辑表示。查询表是查询结果对应的表。视图表示 由基本表或其他视图表导出的表，是虚表，只有定义，实际不对应存储的数据。 3. 关系模式 在前面关系模式的自然语言定义中已经介绍过， 一个关系的关系模式是该关系的关系名 及其全部的属性名的集合，一般表示为关系名（属姓名 1，属性名 2，……，属性名 n） 。关 系模式和关系是型与值的联系。 关系模式指出了一个关系的结构； 而关系则是由满足关系模 式结构的元组构成的集合。 关系模式是稳定的、 静态的， 而关系则是随时间变化的、 动态的。 通常在不引起混淆的情况下，两者可都成为关系。 实际上完整的关系模式的数学定义为： R（U、D、dom、F） 其中：R 为关系模式名，U 为组成该关系的属性名的集合，D 为属性组 U 中属性所来 自的域的集合，dom 为属性向域映像的集合，F 为属性间函数依赖关系的集合。 关系模式通常简写为： R（U）或R（A 1 ，A 2 ，A 3 ，……，A n ） 其中：R为关系名，A i （i=1,2,3,……,n）为属性名。域名构成的集合及属性向域映像 的集合一般为关系模式定义中的属性的类型和长度。2.1.4 关系数据模型的完整性约束关系数据模型的基本理论不但对关系模型的结构进行了严格的定义， 而且还有一组完整 的数据约束规则， 它规定了数据模型中的数据必须符合的某种约束条件。 在定义关系数据模型和进行数据操作时都必须保证符合约束。关系模型中共有四类完整性约束：域完整性、实 体完整性、参照完整性、用户自定义完整性。其中实体完整性和参照完整性是关系模型必须 满足的完整性约束条件，任何关系系统都应该能自动维护。 1. 域完整性 （domain integrity constraint） 关系数据模型规定元组在属性上的分量必须来自于属性的域， 这是由于完整性约束指出 的。域完整性约束是最简单、最基本的约束。现今的 RDBMS，一般都有域完整性约束检查 功能。 2. 实体完整性 （entity integrity） 关系数据模型是将概念模型中的实体以及实体之间的联系都用关系这一数据模型来表 示。 一个基本关系通常只对应一个实体集。 由于在实体集合当中的每一个实体都是可以相互 区分的， 即它们通过实体键唯一标识。 因此关系模型当中能唯一标识一个元组的候选关键字 就对应了实体集的实体键。这样，候选关键字之中的属性即主属性不能取空值。如果主属性 取空值，就说明存在某个不可标识的元组，即存在不可区分的实体，这与现实世界的应用环 境相矛盾。在实际的数据存储中我们是用主关键字来唯一标识每一个元组，因此在具体的 RDBMS 中，实体完整性应变为：任一关系主关键字之中的属性不能为空。 目前大部分 RDBMS 都支持实体完整性约束， 但是只有用户在创建关系模式中说明了主 关键字，系统才会自动进行这项检查，否则它是不强制的。 3. 参照完整性 （referential integrity constraint） 现实世界中的事物和概念往往是存在某种联系的， 关系数据模型就是通过关系来描述实 体和实体之间的联系。 这自然就决定了关系和关系之间也不会是孤立的， 它们是按照某种规 律进行联系的。参照完整性约束就是不同关系之间或同一关系的不同元组必须满足的约束。 它要求关系的外部关键字和被引用关系得主关键字之间遵循参照完整性约束：设关系R 1 有 一外部关键字FK，它引用关系R 2 的主关键字PK，则R 1 中任一元组在外部关键字FK上的分 量必须满足以下两种情况： ? 等于R 2 中某一元组在主关键字PK上的分量； ? 取空值（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 的元组组 成的集合。记作R U S ={ t | t ∈ R ∨ t ∈ S}如果Ｒ和 S 有重复的元组，则只保留一个。 【例 2.3】关系 R 和 S 如图 2-3（a）（b）所示，则 R 和 S 的并运算 R U S 如图 2-3（c） 、 所示。 ⑵ 差 设关系 R 和 S 是同一关系模式下的关系，则 R 和 S 的差是由属于 R 但不属于 S 的元组 组成的集合。记作R ? S = {t | t ∈ R ∧ t ? S}【例 2.4】关系 R 和 S 如图 2-3（a）（b）所示，则 R 和 S 的差运算 R ? S 如图 2-3（d） 、 、 所示。 ⑶ 交 设关系 R 和 S 是同一关系模式下的关系，则 R 和 S 的交是由属于 R 又属于 S 的元组组 成的集合。记作R I S = {t | t ∈ R ∧ t ∈ S }【例 2.5】关系 R 和 S 如图 2-3（a）（b）所示，则 R 和 S 的交运算 R I S 如图 2-3（e） 、 所示。 交和差运算之间存在如下关系：R I S = R ? ( R ? S ) = S ? ( S ? R)⑷ 乘积 设关系 R 有 m 个属性、i 个元组；关系 S 有 n 个属性、j 个元组，则关系 R 和 S 的乘积 是个有(m+n)个属性的元组集合。每个元组的前 r 个分量来自关系 R 的一个元组，后 s 个分 量来自 S 的一个元组，且元组的数目有 i×j 个。乘积运算又叫广义笛卡尔积。记作R × S = {t | t =& t m , t n & ∧t m ∈ R ∧ t n ∈ S } & t m , t n & 表示乘积运算所得到的新关系的元组由两部分组成的有序结构， t m 由含有关系 R 的属性的元组构成、 t 由含有关系 S 的属性的元组构成，共同组成一个新的元组。 这里说明几点： ① 虽然在表示上，我们把关系 R 的属性放在前面，把关系 S 的属性放在后面，连接成n一个有序结构的元组，但在实际的关系操作中，属性间的前后交换次序是无关的。 ② 做乘积运算时，可从 R 的第一个元组开始，一次与 S 的每一个元组组合，然后，对 R 的下一个元组进行同样的操作，直至 R 的最后一个元组也进行完同样的操作为止，即可 得到 R×S 的全部元组。 ③ 乘积运算得出的新关系将数据库的多个孤立的关系表联系在一起了。这样就使关系 数据库中独立的关系有了沟通的桥梁。A A b b c d B 2 3 2 3 (a) R C d b d b A a b e B 3 2 5 (b) S C c d f b b c d a e B 2 3 2 3 3 5 C d b d b c f(c) R∪S R.A b b b b b b c c c d d d R.B 2 2 2 3 3 3 2 2 2 3 3 3 R.C d d d b b b d d d b b b (f) R×S S.A a b e a b e a b e a b e S.B 3 2 5 3 2 5 3 2 5 3 2 5 S.C c d f c d f c d f c d f 图 2-3 关系 R、 及它们的传统集合 S A b B 2 C d A b d B 3 3 C b b(d) R－S(e) R∩S乘积运算在理论上要求参加运算的关系没有同名属性。 通常我们在结果关系的属性名前 加上&表名&.来区分，这样即使当 R 和 S 中有相同的属性名时，也能保证结果关系具有唯一 的属性名（为了书写方便，当某个属性名没有同名时，也可以直接使用属性名） 。当然，当 需要得到一个关系 R 和其值上的乘积时，表达式 R×R 是非法的，因为它将导致非唯一的属 性名。为此必须引入 R 的别名，比如说 G。从而把关系 R 作为另一个关系 S 来使用，这样就 能把表达式写为 R×G，以便产生需要的唯一的属性名。 【例 2.6】关系 R 和 S 如图 2-3（a）（b）所示，则 R 和 S 的乘积运算 R × S 如图 2-3 、 （f）所示。 2. 专门的关系运算 在关系的运算中， 由于关系数据结构的特殊性， 在关系代数中除了需要一般的集合运算 外，还需要一些专门的关系运算包括：选择、投影、连接和除等。 ⑴ 选择选择运算是在关系 R 中选择满足条件 F 的所有元组组成的一个关系。记作σ F ( R) = {t | t ∈ R ∧ F (t ) = true}其中，F 表示选择条件，它是一个逻辑表达式，取值为“true”或“false” 。 逻辑表达式 F 的基本形式为： X 1θ Y1[φ X 2θ Y2 ]L θ表示比较运算符，它可以是＞、≥、＜、≤、＝和≠。X 1 ,Y 1 等是属性名或简单函数。 ∧ ∨ 属性名也可以用它在关系中从左到右的序号来代替。Φ表示逻辑运算符，它可以是 ?、 、 。 [ ]表示任选项，即[ ]中的部分可以要也可以不要，…表示上述格式可以重复下去。 即运算的对象仅有一个关系。 选择运算不会改变参与运算关系 选择运算是单目运算符， 的关系模式，它只是根据给定的条件从所给的关系中找出符合条件的元组。实际上，选择是 从行的角度进行的水平运算，是一种将大关系分割为较小关系的工具。 【例 2.7】设关系 R 和 S 如图 2-3 a） b） （ 、 所示， （ 计算 σ A=' b ' ∧ B&3 ( R ) 或 σ [1]=' b ' ∧[2]&3 ( R ) 的结果如图 2-4（a）所示， σ B &3∨ C ≠ ' c ' ( S ) 或 σ [2]&3∨[3]≠ ' c ' ( S ) 的结果如图 2-4（b）所示。A b B 2 C d A b e B 2 5 C d f（a） σ A=' b ' ∧ B &3 ( R )图 2-4 选择（b） σ B &3∨ C ≠ ' c ' ( S )⑵ 投影 投影运算是从一个关系中，选取某些属性（列） ，并对这些属性重新排列，最后从得出 的结果中删除重复的行，从而得到一个新的关系。 设R是n元关系，R在其分量A i1 ，A i2 ，…，A im (m≤n；i1，i2，…，im为 1 到m之间的 整数，可不连续)上的投影操作定义为：π i1,i2,L ,im = {t | t =& t i1 , t i2 ,L t im & ∧ & t1 ,L , t i1 , t i2 L t im ,L tn &∈ R}即取出所有元组在特定分量A i1 ，A i2 ，…，A im 上的值。 投影操作也是单目运算， 它是从列的角度进行的垂直分解运算， 可以改变关系中列的顺 序，与选择一样也是一种分割关系的工具。 【例 2.8】设关系 R 和 S 如图 2-3（a）（b）所示，计算 π A,C ( R ) 和 π C ,B ( S ) 的结果如图 、 2-5（a）和（b）所示。A b b c d C d b d b C c d f B 3 2 5（a） π A,C ( R )（b） π C ,B ( S ) 图 2-5 投影⑶ 连接 连接是从两个关系的广义笛卡尔积中选取属性间满足一定条件的元组。连接又称θ连接。 记作：R && S = {t | t =& tr , ts & ∧tr ∈ R ∧ ts ∈ S ∧ tr [ A]θ ts [ B]} = σ Aθ B ( R × S )Aθ B其中，A和B分别是R和S上个数相等且可比的属性组（名称可不相同） 。AθB作为比较公式F， F的一般形式为F 1 ∧F 2 ∧…∧F n ,每个F i 是形为 tr [ Ai ]θ ts [ B j ] 的公式。对于连接条件的重要限制 是条件表达式中所包含的对应属性必须来自同一个属性域，否则是非法的，即属性得来性必须 相同。 若 R 有 m 个元组，此运算就是用 R 的第 p 个元组的 A 属性集的各个值与 S 的 B 属性集从头 至尾依次作θ比较。每当满足这一比较运算时，就把 S 中该属性值的元组接在 R 的第 p 个元组 的右边，构成新关系的一个元组。反之，当不满足这一比较运算时就继续作 S 关系 B 属性集的 下一次比较。这样，当 p 从 1 遍历到 m 时，就得到了新关系的全部元组。新关系的属性集取名 方法同乘积运算一样。 【例 2.9】设关系 R 和 S 如图 2-3（a）（b）所示，计算 R && S 的结果如图 2-6 所示。 、B& BR.A b b b c c dR.B 2 2 3 2 2 3R.C d d b d d bS.A a e e a e eS.B 3 5 5 3 5 5S.C c f f c f f图 2-6 R && SB& B连接运算中有两种最为重要也是最为常用的连接：等值连接和自然连接。 ① 等值连接 当一个连接表达式中所有运算符θ取“=”时的连接就是等值连接，是从两个关系的广 义笛卡尔乘积中选取 A，B 属性集间相等的元组。记作：R && S = {t | t =& tr , ts & ∧tr ∈ R ∧ ts ∈ S ∧ tr [ A]θ ts [ B]} = σ A= B ( R × S )A= B若 A 和 B 的属性个数为 n，A 和 B 中属性相同的个数为 k（n≥k≥0） ，则等值连接结果 将出现 k 个完全相同的列，即数据冗余，这是它的不足。 【例 2.10】设关系 R 和 S 如图 2-3（a）（b）所示，计算 R 、 R.A b b R.B 2 3 R.C d b 图 2-7 S.A b b S.B 2 2&& SA= A的结果如图 2-7 所示。S.C d dR&& SA= A② 自然连接 等值连接可能出现数据冗余，而自然连接将去掉重复的列。 自然连接是一种特殊的等值连接，它是两个关系得相同属性上作等值连接，因此，它要 求两个关系中进行比较的分量必须是相同的属性组，并且将去掉结果中重复的属性列。 如果 R 和 S 有相同的属性组 B，Att（R）和 Att（S）分别表示 R 和 S 的属性集，则自 然连接记作：R & & S = {π A tt ( R ) U ( A tt ( S ) ?{ B }) (σ t [ B ]= t [ B ] ( R × S ))}此处 t 表示： {t | t ∈ R × S } 。 自然连接与等值连接的区别是： ① 等值连接相等的属性可以是相同属性，也可以是不同属性；自然连接相等的属性不 须是相同的属性。 ② 自然连接必须去掉重复的属性，特指相等比较的属性，而等值连接无此要求。 ③ 自然连接一般用于有公共属性的情况。如果两个关系没有公共属性，那么它们的自 然连接就退化为广义笛卡尔乘积。 如果是两个关系模式完全相同的关系自然连接运算， 则变 为交运算。 【例 2.11】设关系 R、S 和 Q 如图 2-8（a）（b）（c）所示，计算 R && S 的结果如图 、 、 2-8（d）所示， R && Q 的结果如图 2-7（e）所示。A a b c e gB 3 2 2 5 6 （a）RC c d d f fB 2 3 （b）SC d bA b g （c）QB 2 6图 2-8 自然连接 ⑷ 除 给定关系 R（X，Y）和 S（Y，Z） ，其中 X，Y，Z 为属性或属性集。R 中的 Y 和 S 中 的 Y 可以有不同的属性名，但必须出自相同的域集。R÷S 是满足下列条件的最大关系：其 中每个元组 t 与 S 中的各个元组 s 组成的新元组&t,s&必在 R 中。定义形式为：R ÷ S = π X ( R ) ? π X ((π X ( R ) × S ) ? R ) = {t | t ∈ π X ( R ), 且?s ∈ S , & t , s &∈ R}关系的除操作需要说明的是： ① R÷S 的新关系属性是由属于 R 但不属于 S 的所有属性构成的。 ② R÷S 的任一元组都是 R 中某元组的一部分。 但必须符合下列要求： 即任取属于 R÷S 的一个元组 t，则 t 与 S 的任一元组相连后，结果都为 R 中的一个元组。 ③ R ( X , Y ) ÷ S (Y , Z ) ≡ R ( X , Y ) ÷ π Y ( S ) ④ R÷S 的计算过程如下： i. ii. iii.H = π X ( R) ；W = (H × S ) ? R ；K = π X (W ) ；R÷S = H ?K iv. 【例 2.12】设关系 R、S 和 Q 如图 2-9（a）（b）（c）所示，计算 R÷S 的结果如图 2-9 、 、 （d）所示，R÷Q 的结果如图 2-9（e）所示。A a a g g c B 3 2 2 3 6 C e d d e f 图 2-9 除运算 B 2 3 C d e A a g B 2 2A a g （d） R ÷ SC d （e） R ÷ Q（b）S（c）Q（a）R【例 2.13】设有科研参与关系 EP 和项目关系 P，其中 Eno 代表员工编号、Pno 代表项 目编号，如图 2-10（a）和（b）所示，计算 EP÷P 的结果如图 2-9（c）所示。Eno 211 211 Pno P001 P002 P003 P001 Pno P001 P002 P003 Eno 430127（c）EP÷P（b）P图 2-10 除运算根据除运算的定义，该例子的运算结果的实际意义应该是参与了所有项目的员工有哪 些。只有员工号为“430127”的员工是参与了所有三个项目的。 可以证明，关系代数操作集 {U, ?, π , σ , ×} 是完备的操作集，任何其它关系代数操作都 可以用这五种操作的组合来表示。任何一个 DBMS，只要它能完成这五种操作，则它是关 系完备的。当然，完备的操作集并不只有这一个。2.2.2 关系代数运算实例使用关系代数运算可以对关系数据库进行各种有目的的运算。利用图 2-11 中所示的学 籍管理数据库以及某一时刻的值，根据要求对数据库的各关系进行运算。Sno
Sname 王明 黄小英 张小倩 李刚 张珊 肖文Sex 男 女 女 男 女 男age 21 22 20 21 18 19place 广东 湖北 江西 湖北 浙江 福建Sno
Cno C01 C02 C03 C01 C03 C01 C02 C03 C04 C05 C04 C01 C02 C03 C02 C03grade 83 78 75 81 66 54 89 68 95 97 52 84 91 93 74 73（a）student 关系Cno c01 c02 c03 c04 c05Cname 操作系统 C 语言 数据结构 数据库原理 软件工程Credit 3 4 3 2 2 图 2-11 学籍管理数据库（b）course 关系 【例 2.14】查询所有女生的基本情况。（c）study 学习分析：关系 student 的属性已包含了查询所需的数据，现要查询女生情况只要对关系表 作水平分解的条件运算。π student (σ sex = '女 ' ( student ))当投影运算所牵涉的属性是关系的所有属性时， 投影的属性可简写成关系的名字。 计算 结果如图 2-12（a）所示。 【例 2.15】查询年龄大于 20 岁的男生基本情况。 分析：本例和例 2.14 的求解思想一样，应先做关系的水平选择分解运算，再作投影运算。π student (σ sex = ' 男 ' ∧ age & 20 ( student ))计算结果如图 2-12（b）所示。Sno
04009 Sname 黄小英 张小倩 张珊 Sex 女 女 女 age 22 20 18 place 湖北 江西 浙江 图 2-12 查询 Sno
Sname 王明 李刚 Sex 男 男 age 21 21 place 广东 湖北（b）（a）【例 2.16】查询张小倩同学所选修的课程号和相应的成绩。 分析：题设中所包含的数据信息有“张小倩”“课程号”和“成绩” 、 。其中“张小倩”是 包含在 student 关系表中的姓名属性， “课程号”和“成绩”是 study 关系表中的属性。因此本 例中所包含的信息分布在两个不同的关系表中。 study 关系表中又存在外键 在 “sno” student 与 关系表相联系所以可以使用自然连接运算将连个关系表连接在一起形成一个新的关系。然后 用选择运算水平分解这个关系得出“张小倩”的所有信息，再用投影运算得出最终需要的列。π cno , grade (σ sname = '张小倩 ' ( student & & study ))计算结果如图 2-13（a）所示。 【例 2.17】查询选修了 C 语言的学生的学号和姓名。 分析：题设中所包含的信息有“C 语言”“学号”和“姓名” 、 。其中“C 语言”是 course 关系表中的课程号属性， “学号”和“姓名”是 student 关系表中的属性。这两个关系表虽没 有直接的外键联系，但他们分别与 study 关系表有外键联系。因此要进行这样的查询必须将三 个关系表都自然连接在一起才能具备题设中的所有信息。π sno , sname (σ cname = ' C 语言 ' ( student & & study & & course ))计算结果如图 2-13（b）所示。Sno
03035 Cno C01 C02 C03 C04 C05 grade 54 89 68 95 97 图 2-13 查询 Sno
Sname 王明 张小倩 张珊 肖文（b）（a）【例 2.18】查询选修了全部所开课程的学生的学号。 分析：题设中要查询的是选课信息表中选修了全部所开课程的学号，使用除法可以达到这个目的。但 study 关系表有三个属性“Sno”“Cno”“Grade” 、 、 ，直接用 study÷course 得出 的关系模式会包含“Sno”和“Grade”属性而且达不到题设的目的。因此在进行除法运算之 前先要对 study 关系表进行投影操作，使得除运算之后只含有一个属性“sno” 。π sno ,cno ( study ) ÷ course计算结果如图 2-14（a）所示。 【例 2.19】查询所有没选 C04 号课程的学生的学号。 分析：要达到题设的查询目的，可以先查询出选了 C04 号课程的学生有哪些，再用总的 学生集合减去选了 C04 号课程的学生集合。π sno ( student ) ? π sno (σ cno = 'C04 ' ( grade ))在进行除法运算之前一定要保持被除运算集合只含有两个属性。本例的计算结果如图 2-14（b）所示。Sno 03035 Sno
图 2-14 查询（a）（b）2.2.3 关系演算关系演算是利用谓词演算来表达关系操作的一种方法。按谓词变量的不同，关系演算又分 为两种：一种是元组关系演算，以元组为变量，简称元组演算；另一种是域关系演算，以域为 变过量，简称域演算。本书只介绍元组演算的简单运算，域演算相关知识请参阅其它资料。 元组演算中，元组关系演算表达式的一般形式为{t | ? (t )} 。其中，t 是元组变量，它表示 一个定长的元组。 ? (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. 公式的定义规则 ⑴ 任何原子公式都是公式。 ⑵ 若 φ 是公式，则 ? φ 也是公式。当 φ 为真时 ? φ 为假。 ⑶ 若 ?1 、? 2 是公式， ?1 ∧ ? 2 、?1 ∨ ? 2 也是公式。 则 只有当 ?1 、? 2 同为真时，?1 ∧ ? 2 为真，否则为假。当 ?1 、 ? 2 至少有一个为真时， ?1 ∨ ? 2 为真。 ⑷ 若 ? 是公式，则 (?t )(? ) 也是公式。当存在一个 t 使得 ? 为真时， (?t )(? ) 为真，否 则为假。 ⑸ 若 ? 是公式，则 (?t )(? ) 也是公式。当所有 t 都使 ? 为真时， (?t )(? ) 为真，否则为 假。 ⑹ 所有公式都是从以上五条规则对原子公式进行有限次复合运算求得。 若公式中的一个元组变量前有存在量词或全称量词，则该元组变量称为“约束元组变量” ， 否则称为“自由元组变量” 。在元组关系演算表达式{t | ? (t )} 中，t 是唯一的自由元组变量。4. 元组关系演算与关系代数的等价性 在上一节中已经提到， 如果一个关系运算体系至少能具有五种基本的关系代数运算功能， 则该关系运算体系是完备的。因此只要五种基本的关系代数运算能等价的用元组演算表达式 表示，则元组关系演算体系也就是完备的。 (1) 并R U S = {t | R(t ) ∨ S (t )}(2) 差R ? S = {t | R (t ) ∧ ?S (t )}(3) 广义笛卡尔积R × S = {t ( m +1) | (?u m )(?v n )( R(u ) ∧ S (v) ∧ t[1] = u[1] ∧ L∧t[m] = u[m] ∧ t[m + 1] = v[1] ∧ L ∧ t[m + n] = v[n])}(4) 选择σ F ( R) = {t | R(t ) ∧ F ′}F ′ 是 F 在元组演算中等价的表示形式。(5) 投影π i ,i12 ,Lim( R ) = {t ( m ) | ( ? u )( R ( u ) ∧ t [1] = u [ ii ] ∧ L ∧ t [ m ] = u [ im ])}5. 元组演算实例 下面通过不同的方式列举几个元组关系演算的示例，请读者仔细阅读示例夹生对元组关系 演算的理解。 【例 2.20】设有如图 2-15 所示的关系 R、S、Q，计算下面关系元组演算表达式。 ⑴ ⑵ ⑶R1 = {t | R(t ) ∧ t[ B] ≥ 3 ∧ t[C ] = f } R2 = {t | (?u )( S (t ) ∧ Q(u ) ∧ t[ B] ≤ u[ E ])} R3 = {t | (?u )(?v)( S (u ) ∧ Q(v) ∧ u[C ] = h ∧ t[1] = u[ B] ∧ t[2] = u[C ] ∧ t[3] = v[ D])}元组关系运算的结果如图 2-15 所示。A a d g b A g b B 2 5 3 7 C f h f f C f f A b d b g D e k B 6 5 4 8 C e h f e B E 7 6 5 5 A b d b B 6 5 C e h fR2C h h4RB 3 7SD e kR1Q图 2-15 元组关系演算示例R3【例 2.21】利用图 2-11 中所示的学籍管理数据库，进行下列运算。 (1) 所有女学生的学生信息{x[ student ] | student ( x) ∧ x[ sex] = '女 '}(2) 男生的学号，年龄{x[ sno, age] | (?y )( student ( y ) ∧ y[ sex] = '男'∧ y[ sno] = x[ sno] ∧ y[age] = x[ age])}(3) 所有年龄小于 22 的男生姓名，课程号，成绩{x[ sname, sno, age] | (?y )( student ( y ) ∧ y[ sex] = ' 男 '∧ y[age] & 22 ∧ (?z )( study ( z )∧ z[ sno] = y[ sno] ∧ z[cno] = x[cno] ∧ z[ grade] = x[ grade]) ∧ y[ sname] = x[ sname])}(4) 所有选修了数据库的学生的学号，姓名{x[ sno, sname] | (?y )(?z )( student ( y ) ∧ study ( z ) ∧ y[ sno] = z[ sno] ∧ (?t )(course(t )∧t[cno] = z[cno] ∧ t[cname] = ' 数据库 '∧ x[ sno] = y[ sno] ∧ x[ sname] = y[ sname]))}2.3 查询优化查询检索是数据库系统最主要的功能， 查询速度的快慢直接影响系统效率。 关系模型虽 有坚实的理论基础， 但其主要的确定就是查询效率较低。 若不能解决这个问题则关系模型也 很难得到推广。 查询效率不高并非关系模型特有的问题，在所有的非过程或语言当中都存在这个问题。 在前面几节介绍的两类关系运算语言都是非过程化语言， 用户使用时只需指出他所需要的数 据及查询要求，而不必指出通过哪些存取路径来得到这些数据，由 DBMS 自动安排存取路 径。因此，用户使用是方便了，系统的负担却重了。然而这又是数据独立性的表现。可见系 统效率和数据独立性、 用户使用的便利性和系统实现的便利性都是互相矛盾的。 为了解决这 些矛盾，必须使系统能自动进行查询优化。2.3.1 查询优化实例首先来看下列问题，说明为什么要进行查询优化。 利用图 2-11 中所示的学籍管理数据库， 求选修了 C2 号课程的学生的姓名。 假定学生管 理数据库中有 1000 个学生记录，10000 个学生选课记录，其中选修了 C2 号课程的选课记录 为 50 个。 根据要求，系统可以采用多种等价的关系代数表达式来完成这一查询Q1 = π sname (σ student .sno = study.cno ∧ study.cno ='C 2' ( student × study )) Q 2 = π sname (σ study.cno ='C 2' ( student && study )) Q3 = π sname ( student && σ study .cno ='C 2' ( study ))接下来我们分析这三种关系代数表达式就可以由于查询执行的策略不同， 查询时间相差 很大。 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。 连接后的元组数为 103 * 104 = 107。设每块能装 10 个元组，则写出这些块要用 106 /20=5*104s （2） 作选择操作 依次读入连接后的元组，按照选择条件选取满足要求的记录。假定内存处理时间忽略。 这一步读取中间文件花费的时间需 5*104s。满足条件的元组假设仅 50 个，均可放在内存。（3） 作投影 把第 2 步的结果在sname上作投影输出，得到最终结果。因此第一种情况下执行查询的 4 总时间=105+2 * 5 * 10 ≈105s。这里，所有内存处理时间均忽略不计。 2. 第二种情况 （1） 计算自然连接 为了执行自然连接，读取student和study表的策略不变，总的读取块数仍为 2100 块花费 150s。但自然连接的结果比第一种情况大大减少，为 104个。因此写出这些元组时间为 104 / 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 是连接运算的条件，则：E1× E 2 ≡ E 2 × E1 E1 && E 2 ≡ E 2 && E1 E1 && E 2 ≡ E 2 && E1F F(2) 设 E1、E2 和 E3 是三个关系代数表达式，F1 和 F2 是两个连接运算的限制条件，则：( E1 && E 2) && E 3 ≡ E1 && ( E 2 && E 3) ( E1&& E 2) && E 3 ≡ E1&& ( E 2 && E 3)F1 F2 F1 F2( E1 × E 2) × E 3 ≡ E1 × ( E 2 × E 3)2. 投影的串联等价规则 设 E 是一个关系代数表达式，A1，A2，…，An 是属性名，并且Bi ∈ { A1, A2,L , An}(i = 1, 2,L , n)则： π B1, B 2, L, Bm(π A1, A 2, L , An ( E )) ≡ π B1, B 2, L , Bm ( E )3. 选择的串联等价规则 设 E 是一个关系代数表达式，F1 和 F2 是两个选择条件，则：σ F 1 (σ F 2 ( E )) ≡ σ F 1∧ F 2 ( E )本规则说明，选择条件可合并成一次处理。 4. 选择和投影的交换规则 设 E 为一个关系代数表达式，选择条件 F 只涉及属性 A1，A2，…，An，则：σ F (π A1, A2,L , An ( E )) ≡ π A1, A2,L , An (σ F ( E ))若上式中 F 还涉及不属于 A1，A2,…，An 的属性集 B1，B2，…，Bm，则有：π A1, A2,L , An (σ F ( E )) ≡ π A1, A2,L , An (σ F (π A1, A2,L , An,B1,B 2,L ,Bm ( E )))5. 选择和笛卡尔积的交换规则 设 E1 和 E2 是两个关系代数表达式，若条件 F 只涉及 E1 的属性，则有σ F ( E1× E 2) ≡ σ F ( E1) × E 2若有 F=F1∧F2，并且 F1 只涉及 E1 中的属性，F2 只涉及 E2 中的属性，则σ F ( E1 × E 2) ≡ σ F 1 ( E1) × σ F 2 ( E 2)若 F1 只涉及 E1 中的属性，F2 却涉及了 E1 和 E2 两者的属性，则有σ F ( E1 × E 2) ≡ σ F 2 (σ F 1 ( E1) × E 2)由于选择运算是水平分割关系表，因此提前执行选择运算操作是重要的操作规则。 6. 选择与并交换的规则 设 E1 和 E2 有相同的属性名，则σ F ( E1 U E 2) ≡ σ F ( E1) Uσ F ( E 2)7. 选择和差交换的规则 设 E1 和 E2 有相同的属性名，则σ F ( E1 ? E 2) ≡ σ F ( E1) ? σ F ( E 2)8. 投影与并交换的规则 设 E1 和 E2 有相同的属性名，则π A1, A2,L , An ( E1 U E 2) ≡ π A1, A2,L , An ( E1) Uπ A1, A2,L , An ( E 2)9. 投影与笛卡尔积的交换规则 设 E1 和 E2 是两个关系代数表达式，A1，A2，…，An 是 E1 的属性，B1，B2，…， Bn 是 E2 的属性，则π A1, A2,L , An, B1, B 2,L Bn ( E1 × E 2) ≡ π A1, A2,L , An ( E1) × π B1, B 2,L , Bn ( E 2)利用上述的等价规则， 我们可以将关系代数表达式进行优化， 这对于改善查询效率可以 起很好的作用。2.3.4 关系代数表达式优化的算法在关系的优化过程中，关系代数的等价变换规则是优化的重要基础。根据优化准则，尽 可能早的执行选择操作， 多步操作组合一步完成， 进行适当的预处理， 计算公共子表达式等。 关系查询优化的步骤一般有以下四个： ⑴ 把查询结果转换成内部表示形式，一般是语法树。 ⑵ 选择合适的等价变换规则，把语法树转换成优化形式。 ⑶ 选择底层的操作算法，根据存取路径，数据的存储分布情况等，为语法树中的每个 操作选择合适的操作算法。 ⑷ 生成查询执行方案。由以上三条最后生成了一系列的内部操作。根据这些内部操作 要求的执行次序，确定一个执行方案。 利用等价变换规则，实用化后的表达式能遵循优化准则，这就是优化算法的工作。下面 给出优化的基本算法。 算法：关系代数表达式的优化。 输入：一个关系代数表达式的语法树。 输出：表达式的优化程序。 优化的基本方法如下： ⑴ 利用关系代数等价变换规则 4 把形如 σ F 1∧ F 2∧L ∧ Fn ( E ) 的式子变换为σ F 1 (σ F 2 (L σ F ( E )L ))⑵ 对于每一个选择，使用变化规则 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 _ NO=LOANS.LC _ NO∧ READERS.CARD _ NO=LOANS.CARD _ NO ∧DATE & ( BOOKS × READERS × LOANS )π TITLE，NAMEBOOKS.LC_NO=LOANS.LC_NO∧⑴ 生成初始查询树如图 2-16 所示：σ × BOOKS READERS图 2-16READERS.CARD_NO=LOANS.CARD_NO∧ DATE&× LOANS初始查询树⑵ 将关系代数表达式中的多条件选择运算分为三个选择元算σ BOOKS.LC _ NO = LOANS.LC _ NO ( BOOKS × READERS × LOANS )σ READERS.CARD _ NO = LOANS.CARD _ NO ( READERS × LOANS )σ DATE& ( LOANS)π TITLE, NAMEBOOKS.LC_NO=LOANS.LC_NO σ× BOOKSσ READERS.CARD_NO=LOANS.CARD_NO ×READERSσ DATE& LOANS图 2-17尽可能提前选择运算后的查询树把三个选择运算尽可能移近树叶一端后，原来的查询树变成图 2-17 的形式。⑶ 合并乘积与其后的选择为连接运算，得到图 2-18 所示形式。π TITLE, NAMEBOOKS.LC_NO=LOANS.LC_NO&&&&READERS.CARD_NO=LOANS.CARD_NOBOOKSREADERSσDATE&LOANS图 2-18 合并乘积与其后的选择⑷ 此例中因经选择操作后的 LOANS 关系于 READERS 关系的连接结果明显小于 LOANS 与 BOOKS 连接的结果，所以仍然按图 2-18 所示运算次序操作。否则亦可选择图 2-19 所示运算顺序。π TITLE, NAME&&READERS.LC_NO=LOANS.LC_NOREADERS.CARD_NO=LOANS.CARD_NO&&σREADERSDATE&BOOKSLOANS图 2-19 改变连接顺序⑸ 在整个运算过程中 BOOKS 关系仅用到 TITLE 和 LC_NO 两个属性，因此在叶结点 BOOKS 上增加一个投影运算。 同样处理 READERS 和 LOANS 两个关系。 READERS、 LOANS 两关系连接后，只有 NAME 和 LC_NO 两属性参加后续运算，故增加一个投影运算。最终 得到如图 2-20 的查询树。π TITLE，NAMEBOOKS.LC_NO=LOANS.LC_NO&&πNAME, LOANS.LC_NOπ TITLE，LC_NO BOOKS&&READERS.CARD_NO=LOANS.CARD_NOπ NAME, CARD_NO π LC_NO, CARD_NO READERS σ DATE&LOANS 图 2-20 增加必要的投影2.4 小结关系数据模型的数据结构是二维表，基本概念包括：关系、关系模式、属性、域、元组、 分量、超关键字、候选关键字和外部关键字等。 关系可以用二维表来表示，但在关系中，元组之间是没有先后次序的，属性之间也没有 前后次序。 一个关系的完整模式为：R（U，D，dom，F） ，其中，R 为关系名，U 为该关系所有属 性名的集合，D 为属性组 U 中的属性所来自的域集合，dom 为属性向域映象的集合，F 为属 性间数据依赖关系的集合。通常关系模式简写为：R（U） 。 对关系数据的操作可以用关系代数或关系演算来表达。它们都是实际的关系语言的基 础，并且互相是等价的。关系代数是通过对关系的运算来表达查询的。它的运算包括传统的 集合运算和专门的关系运算。传统的集合运算有：并、交、差、乘积等。专门的关系运算有： 选择、投影、连接和求商。其中：并、差、投影、选择、连接和求商运算构成了一个完备的 操作集合， 其他的关系代数操作都可用这五种操作的组合来实现。 关系演算用谓词表示关系， 有两种形式：元组关系演算和域关系演算，它们分别用关系的元组和域作为谓词变量。 关系模型有着十分明显的优点， 但它也有着查询效率低等缺点。 因此查询优化是关系数 据库管理系统实现的一项基本技术。其中的代数优化是指 DBMS 将用户的查询表达式进行 变换，得到与原来查询等价的并且较优的查询表达式，以提高检索效率。查询优化对用户是 透明的。习题21. 名词解释下列名词 关系、关系模式、属性、域、元组、超关键字、候选键、主键、外键 2. 为什么关系中的元组没有先后顺序，且不允许有重复元组？ 3. 外键值何时允许空？何时不允许空？ 4. 笛卡儿积、等值联接、自然联接三者之间有什么区别？ 5. 设有关系 R 和 S： R S A B C A B C 3 2 7 4 6 5 2 4 7 7 3 3 S。 3 7 4 2 5 3计算R∪S，R-S，R∩S，R×S，π3,2（S）,σB&’5’(R), R 2&2 S, R 6. 设有关系 R 和 S： A a c d R B b b e B b e b S C c a d? 计算 R ? S，R B& C S，σA=C (R×S)7. 设关系 U 和 V 分别有 m 个元组和 n 个元组，给出下列表达式中可能的最小和最大的元 组数量： ⑷ σ F (U)×V （F为某个条件） ⑴ U∩V ⑵ U∪V ⑶ U?V 8. 假设 R 和 S 分别是三元和二元关系， 试把表达式π1,5(σ2=4∨3=4(R×S))转换成等价的: ⑴汉语查询句子; ⑵元组表达式。 9. 有两个关系 R (A, B, C)和是 S（D, E, F）,试把下列关系代数表达式转换成等价的元组表 达式: ⑴πA(R)； ⑵σB=’17’(R)；⑶ R×S； ⑷πA,F(σC=D(R×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 中，用户有一查询语句：检索女同学选修课程的课程名 和任课教师名。 ① 试写出该查询的关系代数表达式。 ② 画出查询表达式的语法树。 ③ 使用关系代数优化算法，对语法树进行优化，并画出优化后的语法树。
更多搜索：
赞助商链接
All rights reserved Powered by
文档资料库内容来自网络，如有侵犯请联系客服。}