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.2 码的定义 2.1.3 关系数据库 2.1.4 关系操作 2.1.5 关系完整性约束 仲恺农业工程学院 计算机科学与工程学院

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.1 关系定义 2.1.2 码的定义 2.1.3 关系数据库 2.1.4 关系操作 2.1.5 关系完整性约束 2.1 关系 2.1.1 关系定义 2.1.2 码的定义 2.1.3 关系数据库 2.1.4 关系操作 2.1.5 关系完整性约束 仲恺农业工程学院 计算机科学与工程学院

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

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

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

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

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

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

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

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

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

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

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

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 张玉玲 2008-07 080105 汪东升 ┇ ISBN 书名 … 库存量 730200899X 版主答疑-Delphi高级编程技巧 5 7040100959 C++程序设计语言（特别版） 1 7040195835 数据库系统概论 2 ┇ BORROW表 借书证号 ISBN 借书时间 应还时间 080101 7040100959 2008-09-01 2008-12-01 7040195835 080102 730200899X 2008-08-25 2008-11-25 ┇ 仲恺农业工程学院 计算机科学与工程学院

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

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

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

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

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

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.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.2.1 传统的集合运算 2.2.2 专门的关系运算 2.2.3 关系代数综合举例 仲恺农业工程学院 2.2.3 关系代数综合举例 仲恺农业工程学院 计算机科学与工程学院

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

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

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

2.2.2 专门的关系运算 BORROW表 借书证号 ISBN 借书时间 应还时间 080101 7040100959 2008-09-01 2008-12-01 7040195835 7115101620 080102 730200899X 2008-08-25 2008-11-25 080105 781067224X 2008-09-10 2008-12-10 080208 2008-10-09 2009-01-09 2008-09-28 2008-11-28 080511 7800048381 2008-10-23 2009-01-23 ┇ 仲恺农业工程学院 计算机科学与工程学院

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 1988-01 2008-06 080102 张玉玲 1 1989-05 2008-07 080105 汪东升 网络工程 男 2 1988-06 080208 陈艺 电子 1987-10 2008-09 080210 张彦 1988-09 080511 孙森茂 外语 1986-05 2008-10 ┇ 仲恺农业工程学院 计算机科学与工程学院

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

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

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

投影（续） 1）投影运算符的含义 从R中选择出若干属性列组成新的关系 πA(R) = { t[A] | t R } A：R中的属性列   仲恺农业工程学院 计算机科学与工程学院

投影（续） 2）投影操作主要是从列的角度进行运算 但投影之后不仅取消了原关系中的某些列，而且还可能取消某些元组（避免重复行） π 仲恺农业工程学院 计算机科学与工程学院

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

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

投影（续） 【例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÷ R22 R11÷ R23 R# R1 R2 R3 R# R1 R3 R# R1 仲恺农业工程学院 计算机科学与工程学院

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

2.2.3 关系代数综合举例 假设某学生选课管理系统中，有三个关系，分别为Student，SC，Course： 2.2.3 关系代数综合举例 假设某学生选课管理系统中，有三个关系，分别为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.1 关系 2.2 关系代数 2.3 查询优化 2.4 关系演算* 本章小结 仲恺农业工程学院 计算机科学与工程学院

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是连接运算的条件，则有 E1 E2≡E2 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，则有 (E1 E2) E3≡E1 (E2 E3) (E1 E2) E3≡E1 (E2 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）≡E1 E2 σF1（E1 E2）≡E1 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 张玉玲 2008-07 080105 汪东升 ┇ ISBN 书名 … 库存量 730200899X 版主答疑-Delphi高级编程技巧 5 7040100959 C++程序设计语言（特别版） 1 7040195835 数据库系统概论 2 ┇ BORROW表 借书证号 ISBN 借书时间 应还时间 080101 7040100959 2008-09-01 2008-12-01 7040195835 080102 730200899X 2008-08-25 2008-11-25 ┇ 仲恺农业工程学院 计算机科学与工程学院

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

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

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

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

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

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

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

{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.出生时间>‘1989-01-01’ 仲恺农业工程学院 计算机科学与工程学院

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

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

{t1，t2，…，tk | P( t1，t2，…，tk)} 其中t1、t2、 …、tk分别是元组变量t的各个分量的域变量，P是域演算公式。 2.4.2 域关系演算语言 {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. 实际上是显示 查询条件 可使用比较运算符＞，≥，＜，≤，＝和≠ 其中＝可以省略 仲恺农业工程学院 计算机科学与工程学院

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

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

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

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

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