Principles and Applications of the Database

Principles and Applications of the Database
数据库原理及应用 Principles and Applications of the Database 第二章关系数据库

第二章关系数据库本章要点关系模型的基本概念关系数据库的重要概念关系数据结构及形式化定义用关系代数表达查询要求
第二章关系数据库本章要点关系模型的基本概念关系数据库的重要概念关系数据结构及形式化定义用关系代数表达查询要求用关系代数表达查询优化及优化的算法和策略用元组关系演算表达查询要求用域关系演算表达查询要求仲恺农业工程学院计算机科学与工程学院

第二章关系数据库本章导读了解：用域关系演算式表达查询要求；关系数据库查询优化的重要性理解：关系模型的基本概念
第二章关系数据库本章导读了解：用域关系演算式表达查询要求；关系数据库查询优化的重要性理解：关系模型的基本概念掌握：关系数据库的重要概念，包括关系模型的数据结构、关系的完整性以及关系操作。用关系代数和元组关系演算表达查询要求。掌握查询处理各个步骤的主要功能。能够把SQL语句转换成查询树，对查询树进行代数优化，转换成优化的查询树。仲恺农业工程学院计算机科学与工程学院

第二章关系数据库重点： 1．关系模型 2．关系数据结构及形式化定义：域、笛卡尔积、元组、关系、侯选码、主码、关系模式、关系数据库
第二章关系数据库重点： 1．关系模型 2．关系数据结构及形式化定义：域、笛卡尔积、元组、关系、侯选码、主码、关系模式、关系数据库 3．关系的完整性：实体完整性、参照完整性、用户定义的完整性仲恺农业工程学院计算机科学与工程学院

第二章关系数据库难点： 1．关系代数：并、差、交、广义笛卡尔积等传统的集合运算；选择、投影、连接、除等专门的关系运算
第二章关系数据库难点： 1．关系代数：并、差、交、广义笛卡尔积等传统的集合运算；选择、投影、连接、除等专门的关系运算 2．关系演算：元组关系演算；域关系演算 3. 查询优化：关系代数的优化算法仲恺农业工程学院计算机科学与工程学院

关系数据库简介提出关系模型的是美国IBM公司的E.F.Codd 1970年提出关系数据模型
E.F.Codd, “A Relational Model of Data for Large Shared Data Banks”, 《Communication of the ACM》, 1970 之后，提出了关系代数和关系演算的概念 1972年提出了关系的第一、第二、第三范式 1974年提出了关系的BC范式仲恺农业工程学院计算机科学与工程学院

第二章关系数据库 2.1 关系 2.2 关系代数 2.3 查询优化 2.4 关系演算* 本章小结仲恺农业工程学院计算机科学与工程学院

2.1 关系 2.1.1 关系定义 2.1.2 码的定义 2.1.3 关系数据库 2.1.4 关系操作 2.1.5 关系完整性约束
2.1 关系关系定义码的定义关系数据库关系操作关系完整性约束仲恺农业工程学院计算机科学与工程学院

2.1.1 关系定义单一的数据结构----关系现实世界的实体以及实体间的各种联系均用关系来表示逻辑结构----二维表
从用户角度，关系模型中数据的逻辑结构是一张二维表建立在集合代数的基础上仲恺农业工程学院计算机科学与工程学院

2.1.1 关系定义 ⒈ 域（Domain） 2. 笛卡尔积 3. 关系仲恺农业工程学院计算机科学与工程学院

⒈ 域（Domain）定义2.1 域是一组具有相同数据类型的值的集合。例如: 姓名：{吴娟，李小丽，王小芬} 性别：{男，女}
专业：{国际贸易，日语，经济管理} 成绩：0-100的整数集合 ……… 仲恺农业工程学院计算机科学与工程学院

定义2.2 给定一组域D1，D2，…，Dn，这些域中可以有相同的。那么D1，D2，…，Dn的笛卡尔积为：
2. 笛卡尔积定义2.2 给定一组域D1，D2，…，Dn，这些域中可以有相同的。那么D1，D2，…，Dn的笛卡尔积为： D1×D2×…×Dn ＝｛（d1，d2，…，dn）｜diDi，i＝1，2，…，n｝所有域的所有取值的一个组合不能重复仲恺农业工程学院计算机科学与工程学院

设有三个域，D1为书名集合，D2为作者集合，D3为出版社集合：
2. 笛卡尔积设有三个域，D1为书名集合，D2为作者集合，D3为出版社集合： D1={基督山伯爵，苏菲的世界，老人与海} D2={大仲马，贾德，海明威} D3={译文出版社，作家出版社 } 仲恺农业工程学院计算机科学与工程学院

笛卡尔积中每一个元素（d1，d2，…，dn）叫作一个n元组（n-tuple）或简称元组(Tuple)
2. 笛卡尔积元组（Tuple）笛卡尔积中每一个元素（d1，d2，…，dn）叫作一个n元组（n-tuple）或简称元组(Tuple) (基督山伯爵，大仲马，译文出版社 )、(基督山伯爵，大仲马，作家出版社 )等都是元组分量（Component）笛卡尔积元素（d1，d2，…，dn）中的每一个值di叫作一个分量基督山伯爵、大仲马、译文出版社、作家出版社等都是分量仲恺农业工程学院计算机科学与工程学院

若Di（i＝1，2，…，n）为有限集，其基数为mi（i＝1，2，…，n），则D1×D2×…×Dn的基数M为：
2. 笛卡尔积基数（Cardinal number）若Di（i＝1，2，…，n）为有限集，其基数为mi（i＝1，2，…，n），则D1×D2×…×Dn的基数M为：其中mi为第i个域基数，n为域的个数笛卡尔积直观意义是诸集合各元素间一切可能的组合，可表示为一个二维表笛卡尔积的表示方法笛卡尔积可表示为一个二维表表中的每行对应一个元组，表中的每列对应一个域仲恺农业工程学院计算机科学与工程学院

表2-1 D1，D2，D3的笛卡尔积书名（D1）作者（D2）出版社（D3）基督山伯爵大仲马译文出版社作家出版社贾德海明威
苏菲的世界老人与海仲恺农业工程学院计算机科学与工程学院

3. 关系定义2.3 D1×D2×…×Dn的子集叫作在域D1，D2，…，Dn上的关系，表示为 R（D1，D2，…，Dn）其中：
n：关系的目或度（Degree）仲恺农业工程学院计算机科学与工程学院

3. 关系 D1，D2，…，Dn的笛卡尔积的某个子集才有实际含义例：表2.1 的笛卡尔积没有实际意义取出有实际意义的元组来构造关系
关系：BAP（书名，作者，出版社）如表2-2所示才为图书、作者及出版社之间的一个正确的关系。仲恺农业工程学院计算机科学与工程学院

表2-2 图书情况对照表书名（D1）作者（D2）出版社（D3）基督山伯爵大仲马译文出版社苏菲的世界贾德作家出版社老人与海
表2-2 图书情况对照表书名（D1）作者（D2）出版社（D3）基督山伯爵大仲马译文出版社苏菲的世界贾德作家出版社老人与海海明威仲恺农业工程学院计算机科学与工程学院

笛卡尔积举例例：M={ 王强，张伟，戈华 }是男性集合 W={ 李丽，刘英 }是女性的集合则 M×W M W 王强刘英戈华
王强李丽刘英张伟戈华 M W 王强刘英戈华李丽 M和W上的夫妻关系 M和W中存在夫妻关系的可能配对并不是笛卡尔积中的每一个子集都是有意义的仲恺农业工程学院计算机科学与工程学院

3. 关系在关系数据模型中，有三类关系：基本关系（基本表或基表）实际存在的表，是实际存储数据的逻辑表示查询表查询结果对应的表
视图表由基本表或其他视图表导出的表，是虚表，不对应实际存储的数据仲恺农业工程学院计算机科学与工程学院

3. 关系基本关系的性质（1）列的同质性（2）异列同域性，即不同的列可出自同一个域其中的每一列称为一个属性
不同的属性要给予不同的属性名（3）列的无序性，即列的顺序可以任意交换（4）元组不重复性，即关系中任意两行（元组）不能相同（5）行的无序性，即行的顺序可以任意交换仲恺农业工程学院计算机科学与工程学院

基本关系的性质(续) （6）分量必须取原子值这是规范条件中最基本的一条表2.3 非范化关系书名（D1）作者（D2）出版社（D3）
表2.3 非范化关系书名（D1）作者（D2）出版社（D3） Press1 Press2 苏菲的世界贾德作家出版社译文出版社老人与海海明威仲恺农业工程学院计算机科学与工程学院

2.1.2 码的定义（1）候选码（Candidate key）
若关系中的某一属性或属性组的值能唯一地标识一个元组，则称该关系中所有满足此要求的属性或属性组为候选码。最简单的情况是，候选码只有一个属性。（2）全码（All-key）最极端的情况：关系模式的所有属性组是这个关系模式的候选码，称为全码（All-key）仲恺农业工程学院计算机科学与工程学院

若一个关系有多个候选码，则选定其中一个为主码（Primary key）
2.1.2 码的定义（3）主码若一个关系有多个候选码，则选定其中一个为主码（Primary key）候选码的诸属性称为主属性（Prime attribute）不包含在任何侯选码中的属性称为非主属性（ Non-Prime attribute）或非码属性（Non-key attribute）仲恺农业工程学院计算机科学与工程学院

STUDENT（借书证号，姓名，专业，性别，出生时间，借书数，照片，办证日期）
主码举例假设有学生关系和借阅关系分别为： STUDENT（借书证号，姓名，专业，性别，出生时间，借书数，照片，办证日期） BORROW（借书证号，ISBN，借书时间，应还时间）仲恺农业工程学院计算机科学与工程学院

假设在同专业中没有同名的学生，那么“姓名与专业”也可以作为一个候选码。
主码举例在关系STUDENT中， “借书证号” 是一个候选码。假设在同专业中没有同名的学生，那么“姓名与专业”也可以作为一个候选码。关系的候选码可以有多个，但同时只能使用一个做为主码，不能同时使用多个候选码。仲恺农业工程学院计算机科学与工程学院

码举例选课(假设学生姓名,课程名都不会有重复) 供应关系候选码：{学号，课程号}; {姓名，课程号} ; {学号，课程名};
成绩课程名课程号姓名学号选课(假设学生姓名,课程名都不会有重复) 供应关系工程号零件号供应商号候选码：{学号，课程号}; {姓名，课程号} ; {学号，课程名}; {姓名，课程名} 主码： {学号，课程号}；主属性：学号; 课程号；姓名;课程名非码属性：成绩；主码:{供应商号,零件号,工程号} 即为全码仲恺农业工程学院计算机科学与工程学院

在BORROW关系中，借书证号是它的外码，其取值依赖于STUDENT关系中的借书证号字段。
2.1.2 码的定义（4）外码若一个关系R2中的一个属性子集S是另一个关系R1的主码所对应的属性组，则称S为R2的外码，并称关系R2为参照关系（Referencing Relation），关系R1为被参照（Referenced Relation）关系或目标关系（Target Relation）。在BORROW关系中，借书证号是它的外码，其取值依赖于STUDENT关系中的借书证号字段。仲恺农业工程学院计算机科学与工程学院

2.1.3 关系数据库关系模式（Relation Schema）是型关系是值关系模式是对关系的描述元组集合的结构属性构成
关系数据库关系模式（Relation Schema）是型关系是值关系模式是对关系的描述元组集合的结构属性构成属性来自的域属性与域之间的映象关系元组语义以及完整性约束条件属性间的数据依赖关系集合仲恺农业工程学院计算机科学与工程学院

2.1.3 关系数据库 R（U，D，DOM，F）定义2.4 关系的描述称为关系模式，可以形式化地表示为：其中：R 关系名
关系数据库定义2.4 关系的描述称为关系模式，可以形式化地表示为： R（U，D，DOM，F）其中：R 关系名 U 组成该关系的属性名集合 D 属性组U中属性所来自的域 DOM 属性向域的映象集合 F 属性间的数据依赖关系集合仲恺农业工程学院计算机科学与工程学院

关系数据库例: 在STUDENT关系模式中，出生日期和办证日期均来自于同一个域——时间域，取不同的属性名，并在模式中定义属性向域的映象，即说明它们分别出自哪个域，如： DOM（出生日期）=DOM（办证日期）=TIME 仲恺农业工程学院计算机科学与工程学院

2.1.3 关系数据库关系模式通常可以简记为 R (U) 或 R (A1，A2，…，An) R: 关系名 A1，A2，…，An : 属性名
关系数据库关系模式通常可以简记为 R (U) 或 R (A1，A2，…，An) R: 关系名 A1，A2，…，An : 属性名注：域名及属性向域的映象常常直接说明为属性的类型、长度仲恺农业工程学院计算机科学与工程学院

关系模式与关系关系模式对关系的描述静态的、稳定的关系关系模式在某一时刻的状态或内容动态的、随时间不断变化的
关系模式和关系往往统称为关系通过上下文加以区别仲恺农业工程学院计算机科学与工程学院

2.1.3 关系数据库关系数据库在一个给定的应用领域中，所有关系的集合构成一个关系数据库关系数据库的型与值仲恺农业工程学院
关系数据库关系数据库在一个给定的应用领域中，所有关系的集合构成一个关系数据库关系数据库的型与值仲恺农业工程学院计算机科学与工程学院

关系数据库的型与值关系数据库的型: 关系数据库模式对关系数据库的描述。关系数据库模式包括若干域的定义在这些域上定义的若干关系模式
关系数据库的值: 关系模式在某一时刻对应的关系的集合，简称为关系数据库仲恺农业工程学院计算机科学与工程学院

2.1.4 关系操作关系操作的特点集合操作方式：操作的对象和结果都是集合，一次一集合的方式常用的关系操作查询：检索
更新：插入、删除、修改等仲恺农业工程学院计算机科学与工程学院

ii．从关系R中检索出满足条件①②的数据。
2.1.4 关系操作（1）数据查询（可分解为三种基本操作） ①一个关系内属性的指定（列的选择）； ②一个关系内元组的指定（行的选择）； ③两个或多个关系的合并。数据执行的算法如下： i．如果查询来自一个关系R，则直接执行ii；如果查询来自两个或者多个关系，则首先执行③（如果是多于两个的关系，可能要多次执行③），直至将两个或多个关系合并成一个关系R； ii．从关系R中检索出满足条件①②的数据。仲恺农业工程学院计算机科学与工程学院

2.1.4 关系操作（2）数据插入。----插入操作（3）数据删除。----先选择后删除（4）数据修改。----先删除后插入
仲恺农业工程学院计算机科学与工程学院

2.1.4 关系操作查询是关系操作中最主要的部分在数据查询中的三种基本操作可以分别通过投影（Project）、选择（Select）和连接（Join）、除（Divide）、并（Union）、交（Intersection）、差（Except）和笛卡尔积等来完成。选择、投影、并、差、笛卡尔积是5种基本操作仲恺农业工程学院计算机科学与工程学院

2.1.4 关系操作关系代数语言用对关系的运算来表达查询要求关系演算语言：用谓词来表达查询要求元组关系演算语言
谓词变元的基本对象是元组变量代表：APLHA, QUEL 域关系演算语言谓词变元的基本对象是域变量代表：QBE 仲恺农业工程学院计算机科学与工程学院

2.1.4 关系操作具有关系代数和关系演算双重特点的语言代表：SQL（Structured Query Language）

2.1.5 关系完整性约束假设有学生选课数据库：学生（学号，姓名，性别，专业号，年龄，班长）课程（课程号，课程名，学分）
关系完整性约束假设有学生选课数据库：学生（学号，姓名，性别，专业号，年龄，班长）课程（课程号，课程名，学分）选修（学号，课程号，成绩）专业（专业号，专业名，申办时间）仲恺农业工程学院计算机科学与工程学院

2.1.5 关系完整性约束实体完整性和参照完整性：关系模型必须满足的完整性约束条件称为关系的两个不变性，应该由关系系统自动支持
关系完整性约束实体完整性和参照完整性：关系模型必须满足的完整性约束条件称为关系的两个不变性，应该由关系系统自动支持用户定义的完整性：应用领域需要遵循的约束条件，体现了具体领域中的语义约束仲恺农业工程学院计算机科学与工程学院

现实世界的三个问题如何保证一个数据（实体）是可识别的？实体完整性如何由一个数据找到另一个数据？参照完整性
如何保证一个数据的取值合理？用户定义的完整性仲恺农业工程学院计算机科学与工程学院

1、实体完整性规则2.1 实体完整性规则（Entity Integrity）若属性A是基本关系R的主属性，则属性A具有唯一性且不能取空值
例：学生（学号，姓名，性别，专业号，年龄，班长），其中：学号：唯一不能取空值仲恺农业工程学院计算机科学与工程学院

2、参照完整性-关系间的引用在关系模型中实体及实体间的联系都是用关系来描述的，因此可能存在着关系与关系间的引用。
例1 专业实体、学生实体之间的联系学生实体及其内部的领导联系　学生（学号，姓名，性别，专业号，年龄，班长）专业（专业号，专业名，申办时间）（1：n）（1：n）主码外码外码主码仲恺农业工程学院计算机科学与工程学院

学生（学号，姓名，性别，专业号，年龄，班长）专业（专业号，专业名）
关系间的引用（续）学生（学号，姓名，性别，专业号，年龄，班长）专业（专业号，专业名）仲恺农业工程学院计算机科学与工程学院

2、参照完整性规则2.2 参照完整性规则若属性（或属性组）F是基本关系R的外码，它与基本关系S的主码Ks相对应（基本关系R和S不一定是不同的关系），则对于R中每个元组在F上的值必须为：或者取空值（F的每个属性值均为空值）或者等于S中某个元组的主码值仲恺农业工程学院计算机科学与工程学院

参照完整性（续）【例2】学生、课程和学生与课程之间的多对多的联系（选课）可以表示为：学生（学号，姓名，性别，专业号，年龄，班长）
课程（课程号，课程名，学分）选修（学号，课程号，成绩）选课关系中每个元组的“学号”和“课程号”可能的取值： (1) 分别为学生和课程关系的主属性，不能取空值 (2) 只能取相应被参照关系中已经存在的主码值仲恺农业工程学院计算机科学与工程学院

参照完整性(续) 学生表选课表课程表仲恺农业工程学院计算机科学与工程学院

参照完整性【例3】学生、图书和学生与图书之间的多对多的联系（借阅）可以表示为：
STUDENT（借书证号，姓名，专业，性别，出生时间，借书数，照片，办证日期） BOOK（ISBN，书名，作者，出版社，价格，复本书，库存量） BORROW（借书证号，ISBN，借书时间，应还时间）仲恺农业工程学院计算机科学与工程学院

参照完整性(续) BORROW关系中每个元组的“借书证号”和“ISBN”可能的取值：
（1）分别为STUDENT和BOOK关系的主属性，不能取空值（2）只能取相应被参照关系中已经存在的主码值仲恺农业工程学院计算机科学与工程学院

参照完整性(续) STUDENT表 BOOK表 … … BORROW表借书证号姓名办证日期 080101 吕亭亭 2008-06
080102 张玉玲 080105 汪东升 ┇ ISBN 书名 … 库存量 X 版主答疑-Delphi高级编程技巧 5 C++程序设计语言（特别版） 1 数据库系统概论 2 ┇ BORROW表借书证号 ISBN 借书时间应还时间 080101 080102 X ┇ 仲恺农业工程学院计算机科学与工程学院

参照完整性规则(续) 【例4】课程COURSE（课程号，课程名，先行课，学分） “先行课”属性值可以取两类值：
（1）空值，表示该课程没有先行课（2）非空值，该值必须是本关系表中确实存在的课程号仲恺农业工程学院计算机科学与工程学院

3、用户定义的完整性针对某一具体关系数据库的约束条件，反映某一具体应用所涉及的数据必须满足的语义要求
关系模型应提供定义和检验这类完整性的机制，以便用统一的系统的方法处理它们，而不要由应用程序承担这一功能仲恺农业工程学院计算机科学与工程学院

用户定义的完整性(续) 例: 学生成绩需取值[0,100]或[0,150] 姓名不能取空值职工的工龄应小于法定的退休年龄
人的身高不能超过3米仲恺农业工程学院计算机科学与工程学院

关系的完整性约束总结：实体完整性参照完整性用户自定义的完整性仲恺农业工程学院计算机科学与工程学院

2.2 关系代数关系代数运算的三个要素运算对象：关系运算结果：关系运算符：四类仲恺农业工程学院计算机科学与工程学院

四类运算符 1、集合运算符将关系看成元组的集合运算是从关系的“水平”方向即行的角度来进行 2、专门的关系运算符不仅涉及行而且涉及列
3、算术比较符辅助专门的关系运算符进行操作 4、逻辑运算符仲恺农业工程学院计算机科学与工程学院

（1）传统的集合运算符，包括并（∪）、差（—）、交（∩）、笛卡尔积（×）；
2.2 关系代数（1）传统的集合运算符，包括并（∪）、差（—）、交（∩）、笛卡尔积（×）；（2）专门的关系运算符，包括选择（）、投影（Π）、连接（∞）和除（÷）运算；（3）算术比较运算符，包括大于（＞）、大于等于（≥）、小于（＜）、小于等于（≤）、等于（＝）、不等于（≠）；（4）逻辑运算符，包括与（∧）、或（∨）、非（）。仲恺农业工程学院计算机科学与工程学院

2.2 关系代数 2.2.1 传统的集合运算 2.2.2 专门的关系运算 2.2.3 关系代数综合举例仲恺农业工程学院
关系代数综合举例仲恺农业工程学院计算机科学与工程学院

2.2.1 传统的集合运算并交差笛卡尔积仲恺农业工程学院计算机科学与工程学院

2.2.1 传统的集合运算 R和S（相容的）具有相同的目n（即两个关系都有n个属性）相应的属性取自同一个域书法社S 运动队R 姓名系
性别赵铭数学男陈艺外语女孙森茂教育王捷姓名系性别王捷数学男张彦物理陈艺外语女仲恺农业工程学院计算机科学与工程学院

仍为n目关系，由属于R或属于S的元组组成 R∪S = { t|t  R∨t S } 其中t为元组变量
1. 并运算（Union） R∪S 仍为n目关系，由属于R或属于S的元组组成 R∪S = { t|t  R∨t S } 其中t为元组变量 RUS 仲恺农业工程学院计算机科学与工程学院

并操作 R∪S 运动队R 书法社S 姓名系性别王捷数学男张彦物理陈艺外语女姓名系性别赵铭数学男陈艺外语
孙森茂教育王捷姓名系性别王捷数学男张彦物理陈艺外语女赵铭参加了运动队或参加了书法社的学生：仲恺农业工程学院计算机科学与工程学院

并(续) 仲恺农业工程学院计算机科学与工程学院

仍为n目关系，由属于R而不属于S的所有元组组成
2. 差运算（Difference） R - S 仍为n目关系，由属于R而不属于S的所有元组组成 R -S = { t|tR∧tS } R-S 仲恺农业工程学院计算机科学与工程学院

差(续) 仲恺农业工程学院计算机科学与工程学院

差操作 R-S 书法社S 运动队R 姓名系性别王捷数学男张彦物理陈艺外语女姓名系性别赵铭数学男陈艺外语
孙森茂教育王捷参加了运动队而没有参加书法社的同学姓名系性别张彦物理男仲恺农业工程学院计算机科学与工程学院

3. 交运算（Intersection） R∩S 仍为n目关系，由既属于R又属于S的元组组成 R∩S = { t|t  R∧t S }
R∩S = R –(R-S） R∩S 仲恺农业工程学院计算机科学与工程学院

交 (续) 仲恺农业工程学院计算机科学与工程学院

交的操作 R∩S 运动队R 书法社S 姓名系性别王捷数学男张彦物理陈艺外语女姓名系性别赵铭数学男陈艺外语
孙森茂教育王捷姓名系性别王捷数学男陈艺外语女既参加了运动队又参加了书法社的学生仲恺农业工程学院计算机科学与工程学院

4. 笛卡尔积（Cartesian Product）
严格地讲应该是广义的笛卡尔积（Extended Cartesian Product） R: r目关系，k1个元组 S: s目关系，k2个元组 R×S 列：（r+s）列元组的集合元组的前r列是关系R的一个元组后s列是关系S的一个元组行：k1×k2个元组 R×S = {tr ts |tr R ∧ tsS } 仲恺农业工程学院计算机科学与工程学院

笛卡尔积R XS 书法社S 运动队R 姓名系性别赵铭数学男陈艺外语女孙森茂教育王捷姓名系性别王捷数学男
张彦物理陈艺外语女仲恺农业工程学院计算机科学与工程学院

RXS的笛卡尔积是十二个元组的表姓名系性别王捷数学男赵铭陈艺外语女孙森茂教育张彦物理仲恺农业工程学院
计算机科学与工程学院

笛卡尔积(续) 仲恺农业工程学院计算机科学与工程学院

2.2.2 专门的关系运算选择投影连接除仲恺农业工程学院计算机科学与工程学院

假设有图书管理数据库，该数据库包括有学生表STUDENT、图书表BOOK和借阅表BORROW STUDENT表
2.2.2 专门的关系运算假设有图书管理数据库，该数据库包括有学生表STUDENT、图书表BOOK和借阅表BORROW STUDENT表借书证号姓名专业名性别借书数出生年份办证日期 080101 吕亭亭计算机女 3 080102 张玉玲 1 080105 汪东升网络工程男 2 080208 陈艺电子 080210 张彦 080511 孙森茂外语 ┇ 仲恺农业工程学院计算机科学与工程学院

2.2.2 专门的关系运算 BOOK表 ISBN 书名作者出版社价格复本数库存量 730200899X
版主答疑-Delphi高级编程技巧岳庆生机械工业出版社 49.0 7 5 X 大学英语词汇记忆点津与考点要览马德高牛津大学出版社(港) 16.0 20 15 英语网上文摘董素华科学出版社 5.0 3 C++程序设计语言（特别版） Special Stroustrup 人民交通出版社 55.67 8 1 计算机网络谢希仁电子工业出版社 39.0 4 数据库系统概论王珊高等教育出版社 33.8 2 ┇ 仲恺农业工程学院计算机科学与工程学院

2.2.2 专门的关系运算 BORROW表借书证号 ISBN 借书时间应还时间 080101 7040100959 2008-09-01
080102 X 080105 X 080208 080511 ┇ 仲恺农业工程学院计算机科学与工程学院

2.2.2 专门的关系运算先引入2个记号（1） R，tR，t[Ai] 设关系模式为R(A1，A2，…，An) 它的一个关系设为R
tR表示t是R的一个元组 t[Ai]则表示元组t中相应于属性Ai的一个分量仲恺农业工程学院计算机科学与工程学院

2.2.2 专门的关系运算（2） A，t[A]， A 若A={Ai1，Ai2，…，Aik}，其中Ai1，Ai2，…，Aik是A1，A2，…，An中的一部分，则A称为属性列或属性组。 A则表示{A1，A2，…，An}中去掉{Ai1，Ai2，…，Aik}后剩余的属性组。 t[A]=(t[Ai1]，t[Ai2]，…，t[Aik])表示元组t在属性列A上诸分量的集合。仲恺农业工程学院计算机科学与工程学院

1. 选择（Selection） 1) 选择又称为限制（Restriction） 2) 选择运算符的含义在关系R中选择满足给定条件的诸元组
σF(R) = {t|tR∧F(t)= ‘true'} F：选择条件，是一个逻辑表达式，基本形式为： X1θY1 仲恺农业工程学院计算机科学与工程学院

选择（续） 3) 选择运算是从关系R中选取使逻辑表达式F为真的元组，是从行的角度进行的运算 σ 仲恺农业工程学院计算机科学与工程学院

选择运算σ 姓名系性别赵铭中文男李凤宇外语女王磐石宋胜马骏数学陈艺孙森茂教育王捷外语系的学生姓名系

STUDENT表借书证号姓名专业名性别借书数 080101 吕亭亭计算机女 3 1988-01 2008-06 080102
出生年份办证日期 080101 吕亭亭计算机女 3 080102 张玉玲 1 080105 汪东升网络工程男 2 080208 陈艺电子 080210 张彦 080511 孙森茂外语 ┇ 仲恺农业工程学院计算机科学与工程学院

选择（续）【例2-3】从学生关系中查询电子专业的全体学生情况。 专业名=“电子” (STUDENT)
结果：借书证号姓名专业名性别借书数出生年份办证日期 080208 陈艺电子女 2 080210 张彦男 ┇ 仲恺农业工程学院计算机科学与工程学院

BOOK表 ISBN 书名作者出版社价格复本数库存量 730200899X 版主答疑-Delphi高级编程技巧岳庆生
机械工业出版社 49.0 7 5 X 大学英语词汇记忆点津与考点要览马德高牛津大学出版社(港) 16.0 20 15 英语网上文摘董素华科学出版社 5.0 3 C++程序设计语言（特别版） Special Stroustrup 人民交通出版社 55.67 8 1 计算机网络谢希仁电子工业出版社 39.0 4 数据库系统概论王珊高等教育出版社 33.8 2 ┇ 仲恺农业工程学院计算机科学与工程学院

【例2-4】从图书关系中选择价格在40元及其以下且库存量超过两本的图书信息。 价格<=40∧库存量>2 (BOOK)
选择（续）【例2-4】从图书关系中选择价格在40元及其以下且库存量超过两本的图书信息。 价格<=40∧库存量>2 (BOOK) ISBN 书名作者出版社价格数复本数库存量 X 大学英语词汇记忆点津与考点要览马德高牛津大学出版社(港) 16.0 20 15 英语网上文摘董素华科学出版社 5.0 3 ┇ 仲恺农业工程学院计算机科学与工程学院

投影（续） 1）投影运算符的含义从R中选择出若干属性列组成新的关系 πA(R) = { t[A] | t R } A：R中的属性列

投影（续） 2）投影操作主要是从列的角度进行运算但投影之后不仅取消了原关系中的某些列，而且还可能取消某些元组（避免重复行） π

STUDENT表借书证号姓名专业名性别借书数 080101 吕亭亭计算机女 3 1988-01 2008-06 080102
出生年份办证日期 080101 吕亭亭计算机女 3 080102 张玉玲 1 080105 汪东升网络工程男 2 080208 陈艺电子 080210 张彦 080511 孙森茂外语 ┇ 仲恺农业工程学院计算机科学与工程学院

【例2-5】查询已办理借书证的学生的姓名、专业名和出生年份。 Π姓名，专业名，出生年份(STUDENT) 或 Π2，3，6(STUDENT)
投影（续）【例2-5】查询已办理借书证的学生的姓名、专业名和出生年份。 Π姓名，专业名，出生年份(STUDENT) 或 Π2，3，6(STUDENT) 姓名专业名出生年份吕亭亭计算机张玉玲汪东升网络工程陈艺电子张彦孙森茂外语 ┇ 仲恺农业工程学院计算机科学与工程学院

投影（续）【例2-6】查询学校有哪些专业。 Π 专业名 (STUDENT) 结果：专业名计算机网络工程电子外语 ┇
电子外语 ┇ 仲恺农业工程学院计算机科学与工程学院

3. 连接（Join）先引入1个符号 tr ts R为n目关系，S为m目关系。 tr R，tsS， tr ts称为元组的连接或者连串。
tr ts是一个n + m列的元组，前n个分量为R中的一个n元组，后m个分量为S中的一个m元组。仲恺农业工程学院计算机科学与工程学院

连接(续) 连接也称为θ连接，从两个关系的笛卡尔积中选取属性间满足一定条件的元组（A和B：分别为R和S上度数相等且可比的属性组）
R S = { | tr  R∧ts S∧tr[A]θts[B] } 1）等值连接：当θ取“＝”时为等值连接 R S = { | tr R∧ts S∧tr[A] = ts[B] } 等值连接的具体计算过程如下： ① 计算R×S； ②找出R×S中满足R中属性组A的值与S中的属性组B的值相等的那些元组。 AθB tr ts A=B tr ts 仲恺农业工程学院计算机科学与工程学院

R S = { | tr R∧ts S∧tr[B] = ts[B] }
连接(续) 2）自然连接： R S = { | tr R∧ts S∧tr[B] = ts[B] } 两个关系中进行比较的分量必须是相同的属性组，在结果中把重复的属性列去掉自然连接的计算过程如下： ① 计算R×S； ② 设R和S的公共属性是B，则找出R×S中满足R中属性B的值与S中的属性B的值相等的那些元组； ③ 去掉重复的属性列，如可去掉S中的B列保留R中B列。 tr ts 仲恺农业工程学院计算机科学与工程学院

连接(续) 3）一般的连接操作是从行的角度进行运算。自然连接还需要取消重复列，所以是同时从行和列的角度进行运算。 AθB R S

等值连接姓名课程号王捷高等数学立体几何模糊数学张彦普通物理陈艺听力姓名系性别王捷数学男张彦物理陈艺
外语女 S R 姓名系性别课程号王捷数学男高等数学立体几何模糊数学张彦物理普通物理陈艺外语女听力仲恺农业工程学院计算机科学与工程学院

自然连接自然连接：客户1 客户2 姓名工作单位工资王帆赵群高誉于励西四小学方正公司新港码头华东师大 1200
6000 4000 1500 姓名住址王帆高誉于励张扬北京西四天津上海南京自然连接：姓名住址工作单位工资王帆高誉于励北京西四天津上海西四小学新港码头华东师大 1200 4000 1500 笛卡尔积：16个元组（姓名，住址，姓名，工作单位，工资）连接：三个元组仲恺农业工程学院计算机科学与工程学院

连接(续) 【例2-7】关系R和关系S 如下所示： B C D b 1 5 3 b 2 8 7 b 3 10 b 4 9 2 b3 S

连接(续) 一般连接的结果如下： A RB RC SB SC D a1 b1 5 b 2 8 7 b 3 10 a 1 6 a 2 B3
一般连接的结果如下： R RC<SD S R RC<SD S A RB RC SB SC D a1 b1 5 b 2 8 7 b 3 10 a 1 6 a 2 B3 仲恺农业工程学院计算机科学与工程学院

连接(续) 等值连接的结果如下： A RB RC SB SC D a1 b1 5 b 1 3 a 1 b 2 6 8 7 a 2 b3
等值连接的结果如下： RB=SB R S RB=SB R S A RB RC SB SC D a1 b1 5 b 1 3 a 1 b 2 6 8 7 a 2 b3 b 3 10 2 b 4 12 9 仲恺农业工程学院计算机科学与工程学院

连接(续) 自然连接 R S的结果如下： A B C D a1 b1 5 3 a 2 b3 8 2 仲恺农业工程学院计算机科学与工程学院

自然连接一定是等值连接，但等值连接不一定是自然连接；
等值连接和自然连接的比较自然连接一定是等值连接，但等值连接不一定是自然连接；等值连接要求有值相等的属性列，但不一定具有相同的属性名，而自然连接要求相等属性值的属性名必须相同；等值连接不做投影运算，而自然连接要把重复的属性列去掉。仲恺农业工程学院计算机科学与工程学院

在作自然连接时，如果把舍弃的元组也保存在结果关系中，而在其他属性上填空值(Null)，这种连接就叫做外连接（OUTER JOIN）。
连接(续) 外连接在作自然连接时，如果把舍弃的元组也保存在结果关系中，而在其他属性上填空值(Null)，这种连接就叫做外连接（OUTER JOIN）。左外连接如果只把左边关系R中要舍弃的元组保留就叫做左外连接(LEFT OUTER JOIN或LEFT JOIN) 右外连接如果只把右边关系S中要舍弃的元组保留就叫做右外连接(RIGHT OUTER JOIN或RIGHT JOIN)。仲恺农业工程学院计算机科学与工程学院

外连接表1 表2 姓名住址王帆高誉于励张扬北京西四天津上海南京姓名工作单位工资王帆赵群高誉于励西四小学
方正公司新港码头华东师大 1200 6000 4000 1500 仲恺农业工程学院计算机科学与工程学院

外连接全外连接：姓名住址工作单位工资王帆高誉于励张扬赵群北京西四天津上海南京 NULL 西四小学新港码头
华东师大方正公司 1200 4000 1500 6000 仲恺农业工程学院计算机科学与工程学院

外连接左外连接：右外连接：姓名住址工作单位工资王帆高誉于励张扬北京西四天津上海南京西四小学新港码头华东师大
NULL 1200 4000 1500 右外连接：姓名住址工作单位工资王帆高誉于励赵群北京西四天津上海 NULL 西四小学新港码头华东师大方正公司 1200 4000 1500 6000 仲恺农业工程学院计算机科学与工程学院

4. 除（Division）首先看一下象集Zx的概念：给定一个关系R（X，Z），X和Z为属性组。
当t[X]=x时，x在R中的象集（Images Set）为： Zx={t[Z]|t R，t[X]=x} 它表示R中属性组X上值为x的诸元组在Z上分量的集合。仲恺农业工程学院计算机科学与工程学院

象集 x1在R中的象集 Zx1 ={Z1，Z2，Z3}， x2在R中的象集 Zx2 ={Z2，Z3}， x3在R中的象集
象集举例仲恺农业工程学院计算机科学与工程学院

4. 除（Division）给定关系R (X，Y) 和S (Y，Z)，其中X，Y，Z为属性组。
R中的Y与S中的Y可以有不同的属性名，但必须出自相同的域集。 R与S的除运算得到一个新的关系P(X)，为： R÷S = {tr [X] | tr  R∧πY (S)  Yx } Yx：x在R中的象集，x = tr[X] 含义： P是R中满足下列条件的元组在 X 属性列上的投影：元组在X上分量值x的象集Yx包含S在Y上投影的集合。仲恺农业工程学院计算机科学与工程学院

除(续) 除操作是同时从行和列角度进行运算 ÷ R S 仲恺农业工程学院计算机科学与工程学院

除(续) 【例2-8】试找出修读了全部课程的学生的学号。对这个问题可用除法解决，即S_C÷C
分析过程：对于关系S_C，Sno可以取三个值{S1，S2，S3}，其中 S1的象集为 { c1，c2}；S2的象集为 { c1，c2 ，c3}；S3的象集为 { c2} C在Cno上的投影为{ c1，c2，c3}，只有S2的象集包含了C在Cno属性组上的投影，所以R÷S ={S2} C所有课程 S_C学生选修课程 Cno C1 C2 C3 Sno Cno S1 C1 C2 S2 C3 S3 S_C÷C Sno S2 仲恺农业工程学院计算机科学与工程学院

除(续) 【例2-9】设关系R、S分别为下图的(a)和(b)，R÷S的结果为图(c) 分析：在关系R中，A可以取三个值{a1，a2，a3}
a1的象集为 {(b1，5)，(b2，6)，(b3，12)}； a2的象集为 {(b1，5)，(b3，12)}； a3的象集为 {(b3，12)} S在(B，C)上的投影为{(b1，5)，(b2，6)，(b3，12)} 只有a1的象集包含了S在(B，C)属性组上的投影，所以R÷S ={a1}。（a）R （b）S A B C a1 b1 5 a 1 b 2 6 a 2 b3 12 b 3 a 3 B C D b 1 5 3 b 2 6 7 b3 12 2 A a1 （c）R÷S 仲恺农业工程学院计算机科学与工程学院

除(续) 求 R11÷R21 R11÷ R22 R11÷ R23 例： R11 R21 R22 R23
B# R1 B1 B2 B3 B4 R2 R3 B# B1 B2 B# B1 B2 B3 B# B1 在关系R11中，R#各个值的象集分别为： R1 { (B1), (B2), (B3), (B4) } R2 { (B1), (B3), (B4) } R3 { (B1),(B2) } 求 R11÷R21 R11÷ R R11÷ R23 R# R1 R2 R3 R# R1 R3 R# R1 仲恺农业工程学院计算机科学与工程学院

2.2.3 关系代数综合举例假设某学生选课管理系统中，有三个关系，分别为Student，SC，Course：
关系代数综合举例假设某学生选课管理系统中，有三个关系，分别为Student，SC，Course： Student（Sno，Sname，Sex， Class，Sage，Profession） SC（Sno，Cno，Grade） Course（Cno，Cname，Period，Credit，Cpno）其中Cpno指先修课程。仲恺农业工程学院计算机科学与工程学院

系代数综合举例 Student SC Course 吕婷婷女 19 计算机张玉玲 21 汪东升男 20 网络陈艺电子 06001
Sno Sname Sex Class Sage Profession 06001 吕婷婷女计算机061 19 计算机 06002 张玉玲 21 06023 汪东升男网络062 20 网络 06011 陈艺电子061 电子 Sno Cno Grade 06001 2 93 5 92 06002 87 7 85 8 95 11 79 06023 86 06011 97 Course Cno Cname Period Credit Cpno 2 C语言 54 3 5 数据结构 72 7 操作系统 8 网络原理 11 数据库原理仲恺农业工程学院计算机科学与工程学院

综合举例(续) 【例2-10】查询选修了2号课程且成绩超过（包括）90分的所有学生的姓名。
πSname（σCno=‘2’∧grade≥ 90（student SC））【例2-11】查询年龄为20岁的学生所选修的课程名。 πCname（σSage=20（student SC Course））【例2-12】查询选修了全部课程的学生号码和姓名。（πSno，Cno（SC）÷πCno（Course）） πSno，Sname（Student）仲恺农业工程学院计算机科学与工程学院

综合举例(续) [例2-13] 查询至少选修了一门其直接先行课为5号课程的学生姓名
[例2-13] 查询至少选修了一门其直接先行课为5号课程的学生姓名 πSname(σCpno='5'(Course SC Student)) 或 πSname(σCpno='5'(Course) SC πSno，name(Student)) πSname (πSno (σCpno='5' (Course) SC) πSno，Sname (Student)) 仲恺农业工程学院计算机科学与工程学院

关系代数小结关系代数运算关系代数运算并、差、交、笛卡尔积、投影、选择、连接、除基本运算并、差、笛卡尔积、投影、选择交、连接、除
关系代数运算关系代数运算并、差、交、笛卡尔积、投影、选择、连接、除基本运算并、差、笛卡尔积、投影、选择交、连接、除可以用5种基本运算来表达仲恺农业工程学院计算机科学与工程学院

关系代数小结(续) 关系代数表达式关系代数运算经有限次复合后形成的式子典型关系代数语言
ISBL（Information System Base Language）由IBM United Kingdom研究中心研制用于PRTV（Peterlee Relational Test Vehicle）实验系统仲恺农业工程学院计算机科学与工程学院

2.3 查询优化 2.3.1 查询优化的组织 2.3.2 查询优化的策略和算法仲恺农业工程学院计算机科学与工程学院

2.3.1 查询优化的组织 1. 关系代数表达式的优化问题通过例2-13可以得知，选择不同的关系代数运算顺序，就会得到不同的查询效率，因此，需要变换规则对关系代数表达式进行等价变换，从而将同一查询请求转换为效率更高的关系代数表达式。仲恺农业工程学院计算机科学与工程学院

关系代数表达式的等价：指用相同的关系代替两个表达式中相应的关系所得到的结果是相同的
2.3.1 查询优化的组织 2.关系代数表达式的等价变换规则关系代数表达式的等价：指用相同的关系代替两个表达式中相应的关系所得到的结果是相同的代数优化策略：通过对关系代数表达式的等价变换来提高查询效率两个关系表达式E1和E2是等价的，可记为E1≡E2 仲恺农业工程学院计算机科学与工程学院

设E1和E2是关系代数表达式，F是连接运算的条件，则有
关系代数表达式等价变换规则（续）常用的等价变换规则：（1）连接、笛卡尔积交换律设E1和E2是关系代数表达式，F是连接运算的条件，则有 E E2≡E E1 E1 × E2≡E2 × E1 仲恺农业工程学院计算机科学与工程学院

设E1，E2，E3是关系代数表达式，F1和F2是连接运算的条件, F1 只涉及E1，E2，F2只涉及E2，E3，则有
关系代数表达式等价变换规则（续）常用的等价变换规则：（2）连接、笛卡尔积的结合律设E1，E2，E3是关系代数表达式，F1和F2是连接运算的条件, F1 只涉及E1，E2，F2只涉及E2，E3，则有 (E E2) E3≡E (E E3) (E1 E2) E3≡E1 (E E3) (E1 × E2) × E3≡E1 × (E2 × E3) 仲恺农业工程学院计算机科学与工程学院

关系代数表达式等价变换规则（续）（3）投影的串接定律 ( (E))≡ (E)
这里，E是关系代数表达式，Ai(i=1，2，…，n)，Bj(j=1，2，…，m)是属性名且{A1，A2，…，An}构成{B1，B2，…，Bm}的子集。仲恺农业工程学院计算机科学与工程学院

这里，E是关系代数表达式，F1、F2是选择条件。选择的串接律说明选择条件可以合并。这样一次就可检查全部条件。
关系代数表达式等价变换规则（续）（4）选择的串接定律 ( (E))≡ (E) 这里，E是关系代数表达式，F1、F2是选择条件。选择的串接律说明选择条件可以合并。这样一次就可检查全部条件。仲恺农业工程学院计算机科学与工程学院

若F中有不属于A1，…，An的属性B1，…，Bm则有更一般的规则：
关系代数表达式等价变换规则（续）（5）选择与投影操作的交换律 (σF(E))≡ σF ( (E)) 选择条件F只涉及属性A1，…，An。若F中有不属于A1，…，An的属性B1，…，Bm则有更一般的规则： (σF(E))≡ (σF( (E))) 仲恺农业工程学院计算机科学与工程学院

如果F=F1∧F2，并且F1只涉及E1中的属性，F2只涉及E2中的属性，则由上面的等价变换规则1，4，6可推出：
关系代数表达式等价变换规则（续）（6）选择对笛卡尔积的交换律如果F中涉及的属性都是E1中的属性，则 (E1×E2)≡ (E1)×E2 如果F=F1∧F2，并且F1只涉及E1中的属性，F2只涉及E2中的属性，则由上面的等价变换规则1，4，6可推出： (E1×E2)≡ (E1)× (E2) 若F1只涉及E1中的属性，F2涉及E1和E2两者的属性，则仍有 (E1×E2)≡ ( (E1)×E2) 它使部分选择在笛卡尔积前先做。仲恺农业工程学院计算机科学与工程学院

关系代数表达式等价变换规则（续）（7）选择对并的分配律设E=E1∪E2，E1，E2有相同的属性名，则
σF(E1∪E2)≡σF(E1)∪σF(E2) （8）选择对差运算的分配律若E1与E2有相同的属性名，则 σF(E1-E2)≡σF(E1)-σF(E2) （9）选择对自然连接的分配律 σF(E1 E2)≡σF(E1) σF(E2) F只涉及E1与E2的公共属性仲恺农业工程学院计算机科学与工程学院

设E1和E2是两个关系表达式，L1是E1的属性集，L2是E2的属性集，则
关系代数表达式等价变换规则（续）（10）投影对笛卡尔积的分配律设E1和E2是两个关系表达式，L1是E1的属性集，L2是E2的属性集，则 ΠL1∪L2 （E1×E2）≡ΠL1（E1）×ΠL2（E2）（11）投影对并的分配律设E1与E2具有相同的属性名或者二者的属性有对应性，L为二者的共同属性，则 ΠL（E1∪E2）≡ΠL（E1）∪ΠL（E2）仲恺农业工程学院计算机科学与工程学院

设E1和E2是关系代数表达式，根据F连接的定义，下式成立： σF （E1×E2）≡E1 E2 σF1（E1 E2）≡E1 E2
关系代数表达式等价变换规则（续）（12）选择与连接操作的结合律设E1和E2是关系代数表达式，根据F连接的定义，下式成立： σF （E1×E2）≡E E2 σF1（E1 E2）≡E E2 （13）并和交的交换律 E1∪E2≡E2∪E1 E1∩E2≡E1∩E2 （14）并和交的结合律（E1∪E2）∪E3≡E1∪（E2∪E3）（E1∩E2）∩E3≡E1∩（E2∩E3） F F2 F1∧F2 仲恺农业工程学院计算机科学与工程学院

2.3 查询优化 2.3.1 查询优化的组织 2.3.2 查询优化的策略和算法仲恺农业工程学院计算机科学与工程学院

（1）在关系代数表达式中尽可能早地执行选择操作；
2.3.2 查询优化的策略和算法 1.优化策略三条启发式规则：（1）在关系代数表达式中尽可能早地执行选择操作；（2）在关系代数表达式中尽可能早地执行投影操作；（3）合并笛卡尔积和其后的选择操作，使之成为一个连接运算，连接特别是等值连接运算要比同样关系上的笛卡尔积省很多时间。仲恺农业工程学院计算机科学与工程学院

遵循三条启发式规则，应用2.3.1的等价变换公式来优化关系表达式的算法。算法：关系表达式的优化输入：一个关系表达式的语法树
2.3.2 查询优化的策略和算法遵循三条启发式规则，应用2.3.1的等价变换公式来优化关系表达式的算法。算法：关系表达式的优化输入：一个关系表达式的语法树输出：优化序列方法： (1) 利用等价变换规则4把形如σF1∧F2∧…∧Fn(E)变换为σF1(σF2(…(σFn(E))…))。 (2) 对每一个选择，利用等价变换规则4～9尽可能把它移到树的叶端，即尽可能早地执行选择操作。仲恺农业工程学院计算机科学与工程学院

(3) 对每一个投影利用等价变换规则3，10，11， 5中的一般形式尽可能把它移向树的叶端。
关系代数语法树的启发式优化（续） (3) 对每一个投影利用等价变换规则3，10，11， 5中的一般形式尽可能把它移向树的叶端。注意：等价变换规则3使一些投影消失规则5把一个投影分裂为两个，其中一个有可能被移向树的叶端如果一个投影是针对被投影表达式的全部属性，则可消去该投影操作 (4) 利用等价变换规则3～5把选择和投影的串接合并成单个选择、单个投影或一个选择后跟一个投影。使多个选择或投影能同时执行，或在一次扫描中全部完成。仲恺农业工程学院计算机科学与工程学院

(5) 把上述得到的语法树的内节点分组。每一双目运算(×，，∪，-)和它所有的直接祖先为一组(这些直接祖先是(σ，π运算)。
关系代数语法树的启发式优化（续） (5) 把上述得到的语法树的内节点分组。每一双目运算(×，，∪，-)和它所有的直接祖先为一组(这些直接祖先是(σ，π运算)。如果它的子孙结点直到叶子都是一元运算符，则也将其并入该组；但如果二元运算是笛卡尔积，而且后面不是与它组合成等值连接的选择时，则不能将选择和这个二元运算组成同一组。仲恺农业工程学院计算机科学与工程学院

（6）生成一个程序，每一组结点的计算是程序中的一步，各步的顺序是任意的，只要保证任何一组不会在它的子孙组前面计算。
关系代数语法树的启发式优化（续）（6）生成一个程序，每一组结点的计算是程序中的一步，各步的顺序是任意的，只要保证任何一组不会在它的子孙组前面计算。仲恺农业工程学院计算机科学与工程学院

三个表 STUDENT表 BOOK表 … … BORROW表借书证号姓名办证日期 080101 吕亭亭 2008-06 080102
张玉玲 080105 汪东升 ┇ ISBN 书名 … 库存量 X 版主答疑-Delphi高级编程技巧 5 C++程序设计语言（特别版） 1 数据库系统概论 2 ┇ BORROW表借书证号 ISBN 借书时间应还时间 080101 080102 X ┇ 仲恺农业工程学院计算机科学与工程学院

【例2-14】在所给出的图书管理数据库关系模式中，求2008年10月1日前借出的图书的书名以及借书学生的姓名，以督促逾期不还的学生尽快还书。
关系代数语法树的启发式优化（续）【例2-14】在所给出的图书管理数据库关系模式中，求2008年10月1日前借出的图书的书名以及借书学生的姓名，以督促逾期不还的学生尽快还书。先写出其关系代数表达式： Π书名，姓名（σ借书时间<' '（STUDENT BOOK BORROW）仲恺农业工程学院计算机科学与工程学院

原始查询语法树仲恺农业工程学院计算机科学与工程学院

步骤1：由规则（4），即选择的串接定律，把相与的选择条件分解为两个独立的选择条件。
关系代数语法树的启发式优化（续）步骤1：由规则（4），即选择的串接定律，把相与的选择条件分解为两个独立的选择条件。 σSTUDENT.借书证号= BORROW.借书证号∧BOOK.ISBN= BORROW. ISBN ≡σSTUDENT.借书证号= BORROW.借书证号和σBOOK.ISBN= BORROW. ISBN 步骤2：使用规则（4）~（8），将三个选择操作尽可能的向叶端靠拢。根据规则（6）可将选择条件σSTUDENT.借书证号= BORROW.借书证号移动到下面的笛卡尔积的上方，再根据规则（5）可以把借书时间<‘ ’移动到BORROW的上方，从而得到中间的语法树。仲恺农业工程学院计算机科学与工程学院

中间的语法树仲恺农业工程学院计算机科学与工程学院

关系代数语法树的启发式优化（续）步骤3：根据规则（5）（选择和投影的交换律），则有
Π书名，姓名（σBOOK.ISBN= BORROW. ISBN（…） ≡ Π书名，姓名（σBOOK.ISBN= BORROW. ISBN（ Π书名，姓名，BOOK.ISBN， BORROW. ISBN （…））再把投影Π书名，姓名，BOOK.ISBN， BORROW. ISBN分解为两个独立的部分Π书名，BOOK.ISBN与 Π姓名，BORROW. ISBN，再利用规则（10）（投影对笛卡尔积的分配律）分别对相关的部分作投影，则有 Π书名，姓名（σBOOK.ISBN= BORROW. ISBN（Π书名，BOOK.ISBN（BOOK）×Π姓名，BORROW. ISBN （σSTUDENT.借书证号= BORROW.借书证号（STUDENT×σ借书时间<' '（BORROW）））））仲恺农业工程学院计算机科学与工程学院

关系代数语法树的启发式优化（续）步骤3：同理，利用规则（5），（10），再将σSTUDENT.借书证号= BORROW.借书证号进行分解并与相关的部分结合，则有： Π姓名，BORROW . ISBN（σSTUDENT.借书证号= BORROW.借书证号（STUDENT×σ借书时间<' '（BORROW）））≡ Π姓名，BORROW. ISBN（σSTUDENT.借书证号= BORROW.借书证号（Π姓名，STUDENT.借书证号（STUDENT）×（ΠBORROW.借书证号，BORROW. ISBN（σ借书时间<' '（BORROW）））））在本步骤中，添加相应的投影运算是为了在做笛卡尔积之前，把每个关系无关的属性完全删除。仲恺农业工程学院计算机科学与工程学院

优化语法树步骤4：根据步骤3中所分析画出相应的优化语法树如下图所示。仲恺农业工程学院计算机科学与工程学院

关系代数语法树的启发式优化（续）步骤4（续）：优化的查询表达式为：
Π书名，姓名（σBOOK.ISBN= BORROW. ISBN（Π书名，BOOK.ISBN（BOOK）×Π姓名，BORROW. ISBN（σSTUDENT.借书证号= BORROW.借书证号（Π姓名，STUDENT.借书证号（STUDENT）×（ΠBORROW.借书证号，BORROW. ISBN（σ借书时间<' '（BORROW）））））））按照习惯，更趋向于将符合要求的笛卡尔积写成自然连接的形式，则该查询的优化表达式为： Π书名，姓名（Π书名，BOOK.ISBN（BOOK） Π姓名，BORROW. ISBN（Π姓名，STUDENT.借书证号（STUDENT）（ΠBORROW.借书证号，BORROW. ISBN（σ借书时间<' '（BORROW）））））仲恺农业工程学院计算机科学与工程学院

2.4 关系演算关系演算以数理逻辑中的谓词演算为基础按谓词变元不同进行分类 1.元组关系演算：以元组变量作为谓词变元的基本对象
2.4 关系演算关系演算以数理逻辑中的谓词演算为基础按谓词变元不同进行分类 1.元组关系演算：以元组变量作为谓词变元的基本对象元组关系演算语言ALPHA 2.域关系演算：以域变量作为谓词变元的基本对象域关系演算语言QBE 仲恺农业工程学院计算机科学与工程学院

2.4 关系演算 2.4.1 元组关系演算语言ALPHA 2.4.2 域关系演算语言QBE 2.4.3 关系运算的等价性仲恺农业工程学院
2.4 关系演算元组关系演算语言ALPHA 域关系演算语言QBE 关系运算的等价性仲恺农业工程学院计算机科学与工程学院

{t | R(t)}为元组演算表达式，其中t是元组变量 R(t)为元组关系演算公式，简称公式。
2.4.1 元组关系演算在元组关系演算系统中， {t | R(t)}为元组演算表达式，其中t是元组变量 R(t)为元组关系演算公式，简称公式。仲恺农业工程学院计算机科学与工程学院

2.4.1 元组关系演算设r目关系R和s目关系S的谓词分别为R（u）和S（v），则：（1）并： R∪S={t | R(t)∨S(t)}
（3）笛卡尔积：R×S={t(r+s)|(u(r))( v(s))(R(u)∧S(v)∧t[1]=u[1]∧…∧t[r]=u[r]∧t[r+1]=v[1]∧…∧t[r+s]=v[s]) } （4）选择： σF (R)={ t | R(t)∧F＇} 其中F＇是条件表达式F在谓词演算中的表示形式。（5）投影： Π(R)={t(k)|(u)(R(u)t[1]=u[i1]…t[k]=u[ik])} 其中t(k)表示元组t有k个分量，而t[i]表示元组t的第i个分量，u[j]表示元组u的第j个分量。仲恺农业工程学院计算机科学与工程学院

【例2-15】设有关系模式STUDENT（借书证号，姓名，专业，性别，出生时间，借书数，照片，办证日期），试用元组关系演算来表达下述查询。
2.4.1 元组关系演算【例2-15】设有关系模式STUDENT（借书证号，姓名，专业，性别，出生时间，借书数，照片，办证日期），试用元组关系演算来表达下述查询。（1）列出计算机专业的所有学生： S计算机=｛t | STUDENT（t）∧t[3]= '计算机'｝（2）列出所有1980年以前出生的学生： S出生年月=｛t |STUDENT（t）∧t[5]<1980｝仲恺农业工程学院计算机科学与工程学院

ALPHA语言由E.F.Codd提出 INGRES所用的QUEL语言是参照ALPHA语言研制的语句检索语句更新语句 GET
PUT，HOLD，UPDATE，DELETE，DROP 仲恺农业工程学院计算机科学与工程学院

ALPHA语言操作格式语句格式：操作语句工作空间名（表达式）：操作条件工作空间：通常用W表示表达式：指定语句的操作对象格式：
语句格式：操作语句　工作空间名（表达式）：操作条件工作空间：通常用W表示表达式：指定语句的操作对象格式：关系名| 关系名. 属性名| 元组变量. 属性名| 集函数 [，… ] 操作条件：将操作结果限定在满足条件的元组中格式：逻辑表达式（还可加上排序要求及定额）仲恺农业工程学院计算机科学与工程学院

ALPHA语言---举例【例2-16】查询所有学生的数据。 GET W（STUDENT）【例2-17】查询所有清华大学出版社的图书信息。
GET W（BOOK）：BOOK.出版社=‘清华大学出版社‘ 【例2-18】查询所有1989年以后出生的学生借书证号、姓名和专业。 GET W（STUDENT.借书证号，STUDENT.姓名，STUDENT.专业）：STUDENT.出生时间>‘ ’ 仲恺农业工程学院计算机科学与工程学院

ALPHA语言---举例【例2-19】取出计算机专业最后一个办理借书证的学生的借书证号和姓名。
GET W（1）（STUDENT.借书证号，STUDENT.姓名）： STUDENT.专业='计算机' DOWN STUDENT.办证日期仲恺农业工程学院计算机科学与工程学院

{t1，t2，…，tk | P( t1，t2，…，tk)} 其中t1、t2、 …、tk分别是元组变量t的各个分量的域变量，P是域演算公式。
域关系演算语言 {t1，t2，…，tk | P( t1，t2，…，tk)} 其中t1、t2、 …、tk分别是元组变量t的各个分量的域变量，P是域演算公式。仲恺农业工程学院计算机科学与工程学院

2.4.2 域关系演算语言QBE 一种典型的域关系演算语言由M.M.Zloof提出以元组变量的分量即域变量作为谓词变元的基本对象
QBE：Query By Example 以表格的形式进行操作通过例子来表示查询，使用查询查询顺序自由仲恺农业工程学院计算机科学与工程学院

QBE操作框架关系名属性名操作命令元组属性值或查询条件或操作命令仲恺农业工程学院计算机科学与工程学院

操作步骤以简单查询为例说明：【例2-20】在图书管理系统中，从学生表中查询出所有计算机专业的学生的姓名。操作步骤为：
（1）用户提出要求；（2）屏幕显示空白表格；仲恺农业工程学院计算机科学与工程学院

简单查询（续）（3）用户在最左边一栏输入要查询的关系名Student；（4）系统显示该关系的属性名 Student STUDENT
借书证号姓名专业性别出生时间借书数照片办证日期仲恺农业工程学院计算机科学与工程学院

简单查询（续）（5）用户在上面构造查询要求陈艺是示例元素，即域变量（6）屏幕显示查询结果 STUDENT 借书证号姓名专业性别
出生时间数照片办证日期 P.陈艺计算机 STUDENT 借书证号姓名专业性别出生时间借书数照片办证日期吕亭亭张玉玲计算机仲恺农业工程学院计算机科学与工程学院

构造查询的几个要素示例元素即域变量一定要加下划线示例元素是这个域中可能的一个值，它不必是查询结果中的元素
示例元素即域变量一定要加下划线示例元素是这个域中可能的一个值，它不必是查询结果中的元素打印操作符P. 实际上是显示查询条件可使用比较运算符＞，≥，＜，≤，＝和≠ 其中＝可以省略仲恺农业工程学院计算机科学与工程学院

关系运算的等价性关系代数、安全的元组关系运算、安全的域关系演算在关系的表达和操作能力上是等价的，它们之间可以相互转换。三个重要结论：（1）若E是一个由五种基本关系代数运算经过有限次组合而成的关系代数表达式，则必定存在与之等价的安全的元组演算表达式。（2）对于每一个安全的元组关系演算表达式，都存在与之等价的安全的域关系演算表达式。（3）对于每个安全的域关系演算表达式，都存在与之等价的关系代数表达式。仲恺农业工程学院计算机科学与工程学院

本章小结 1．关系 2. 关系代数 3. 查询优化 4. 关系演算仲恺农业工程学院计算机科学与工程学院

下课了。。。追求仲恺农业工程学院计算机科学与工程学院

Principles and Applications of the Database

Similar presentations

Presentation on theme: "Principles and Applications of the Database"— Presentation transcript:

Similar presentations

About project

反馈

请登录

Auth with social network:

Principles and Applications of the Database

Similar presentations

Presentation on theme: "Principles and Applications of the Database"— Presentation transcript:

Similar presentations

About project

反馈