关系模型和关系运算理论.ppt

1 第2章关系模型和关系运算理论 2 本章重要概念 1 1 基本概念关系模型 关键码 主键和外键 关系的定义和性质 三类完整性规则 过程性语言与非过程性语言 2 关系代数五个基本操作 四个组合操作 七个扩充操作 3 本章重要概念 2 3 关系演算元组关系演算和域关系演算的原子公式 公式的定义 关系演算的安全性和等价性 4 关系代数表达式的优化关系代数表达式的等价及等价转换规则 启化式优化算法 5 关系逻辑谓词 原子 规则和查询 规则的安全性 用规则模拟关系代数表达式 4 本章概要 本章先介绍关系模型的基本概念 然后介绍关系运算的三种理论 关系代数 关系演算和关系逻辑 5 关系模型和关系运算理论 2 1关系模型的基本概念2 2关系代数2 3关系演算2 4关系代数表达式的优化2 5关系逻辑2 6小结 6 2 1关系模型的基本概念 2 1 1基本术语2 1 2关系的定义和性质2 1 3关系模型的三类完整性规则2 1 4关系模型的三级体系结构2 1 5关系模型的形式定义和优点2 1 6关系查询语言和关系运算 返回 7 2 1 1基本术语 1 定义2 1用二维表格表示实体集 用关键码表示实体之间联系的数据模型称为关系模型 RelationalModel 图2 1学生登记表 8 2 1 1基本术语 2 在关系模型中 字段称为属性 字段值称为属性值 记录类型称为关系模式 在图2 1中 关系模式名是R 记录称为元组 tuple 元组的集合称为关系 relation 或实例 instance 一般用大写字母A B C 表示单个属性 用大写字母 X Y Z表示属性集 用小写字母表示属性值 有时也习惯称呼关系为表或表格 元组为行 row 属性为列 column 关系中属性个数称为 元数 arity 元组个数为 基数 cardinality 9 2 1 1基本术语 3 关系元数为5 基数为4 10 2 1 1基本术语 4 关键码 key 简称键 由一个或多个属性组成 在实际使用中 有下列几种键 1 超键 SuperKey 2 候选键 CandidateKey 3 主键 PrimaryKey 在图2 1中 工号 姓名 是模式的一个超键 但不是候选键 而 工号 是候选键 在实际使用中 如果选择 工号 作为删除或查找元组的标志 那么称 工号 是主键 4 外键 ForeignKey 返回 11 2 1 2关系的定义和性质 定义2 2关系是一个属性数目相同的元组的集合 在关系模型中 对关系作了下列规范性限制 1 关系中每一个属性值都是不可分解的 2 关系中不允许出现重复元组 即不允许出现相同的元组 3 由于关系是一个集合 因此不考虑元组间的顺序 即没有行序 4 元组中的属性在理论上也是无序的 但使用时按习惯考虑列的顺序 返回 12 2 1 3关系模型的完整性规则 1 实体完整性规则 entityintegrityrule 要求关系中元组在组成主键的属性上不能有空值 如果出现空值 那么主键值就起不了惟一标识元组的作用 13 2 1 3关系模型的完整性规则 2 参照完整性规则 referenceintegrityrule 定义2 3参照完整性规则的形式定义如下 如果属性集K是关系模式R1的主键 K也是关系模式R2的外键 那么在R2的关系中 K的取值只允许两种可能 或者为空值 或者等于R1关系中某个主键值 这条规则的实质是 不允许引用不存在的实体 在上述形式定义中 关系模式R1的关系称为 参照关系 关系模式R2的关系称为 依赖关系 主表 和 副表 父表 和 子表 14 2 1 3关系模型的完整性规则 3 这条规则在具体使用时 有三点变通 外键和相应的主键可以不同名 只要定义在相同值域上即可 R1和R2也可以是同一个关系模式 此时表示了同一个关系中不同元组之间的联系 外键值是否允许空 应视具体问题而定 15 2 1 3关系模型的完整性规则 4 例下面各种情况说明了参照完整性规则在关系中如何实现的 在关系数据库中有下列两个关系模式 S S SNAME AGE SEX SC S C SCORE 这里带线者为主键 带线者为外键 据规则要求关系SC中的S 值应该在关系S中出现 如果关系SC中有一个元组 S7 C4 80 而学号S7却在关系S中找不到 那么我们就认为在关系SC中引用了一个不存在的学生实体 这就违反了参照完整性规则 另外 在关系SC中S 不仅是外键 也是主键的一部分 因此这里S 值不允许空 16 2 1 3关系模型的完整性规则 5 设工厂数据库中有两个关系模式 DEPT D DNAME EMP E ENAME SALARY D 车间模式DEPT的属性为车间编号 车间名 职工模式EMP的属性为工号 姓名 工资 所在车间的编号 每个模式的主键与外键已标出 在EMP中 由于D 不在主键中 因此D 值允许空 17 2 1 3关系模型的完整性规则 6 设课程之间有先修 后继连系 模式如下 R C CNAME PC 其属性表示课程号 课程名 先修课的课程号 如果规定 每门课程的直接先修课只有一门 那么模式R的主键是C 外键是PC 这里参照完整性在一个模式中实现 即每门课程的直接先修课必须在关系中出现 18 2 1 3关系模型的完整性规则 7 例2 1TEACHER T TNAME TITLE COURSE C CNAME T STUDENT S SNAME AGE SEX SC S C SCORE 图2 3关系模型的数据结构图 DSD 19 2 1 3关系模型的完整性规则 8 用户定义的完整性规则在建立关系模式时 对属性定义了数据类型 即使这样可能还满足不了用户的需求 此时 用户可以针对具体的数据约束 设置完整性规则 由系统来检验实施 以使用统一的方法处理它们 不再由应用程序承担这项工作 例如学生的年龄定义为两位整数 范围还太大 我们可以写如下规则把年龄限制在15 30岁之间 CHECK AGEBETWEEN15AND30 返回 20 2 1 4关系模型的三层体系结构 关系模式 在关系模型中 记录类型称为关系模式 而关系模式的集合就是数据库的概念模式 在系统实现时 关系模式和属性的命名一般都用英文单词 TEACHER T TNAME TITLE COURSE C CNAME T STUDENT S SNAME AGE SEX SC S C SCORE 21 2 1 4关系模型的三层体系结构 子模式 1 子模式是用户所用到的那部分数据的描述 除此之外 还应指出数据与关系模式中相应数据的连系 例如 用户需要用到子模式G 图2 3 成绩子模式G S SNAME C SCORE 22 2 1 4关系模型的三层体系结构 子模式 2 80 23 2 1 4关系模型的三层体系结构 存储模式 1 图2 6关系STUDENT和SC的环结构 在有些DBMS中 关系存储是作为文件看待的 每个元组就是一个记录 由于关系模式有键 因此存储一个关系可用散列方法或索引方法实现 如果关系的元组数目较少 100个以内 那么也可以用 堆文件 方式实现 即没有特定的次序 此外 还可对任意的属性集建立辅助索引 24 2 1 4关系模型的三层体系结构 存储模式 2 图2 7两个关系存储在一起 25 2 1 5关系模型的形式定义 关系模型有三个重要组成部分 数据结构 数据操纵 数据完整性规则 1 数据结构 数据库中全部数据及其相互连系都被组织成 关系 二维表格 的形式 关系模型基本的数据结构是关系 2 数据操纵 关系模型提供一组完备的高级关系运算 以支持对数据库的各种操作 关系运算分成关系代数 关系演算和关系逻辑等三类 3 数据完整性规则 数据库中数据必须满足实体完整性 参照完整性和用户定义的完整性等三类完整性规则 26 2 1 5关系模型的优点 与其它数据模型相比 关系模型突出的优点如下 1 关系模型提供单一的数据结构形式 具有高度的简明性和精确性 2 关系模型的逻辑结构和相应的操作完全独立于数据存储方式 具有高度的数据独立性 3 关系模型使数据库的研究建立在比较坚实的数学基础上 4 关系数据库语言与一阶谓词逻辑的固有内在连系 为以关系数据库为基础的推理系统和知识库系统的研究提供了方便 27 2 1 6关系查询语言和关系运算 关系数据库的数据操纵语言 DML 的语句分成查询语句和更新语句两大类 查询语句用于描述用户的各种检索要求 更新语句用于描述用户进行插入 删除 修改等操作 关于查询的理论称为 关系运算理论 关系查询语言根据其理论基础的不同分成三类 1 关系代数语言 2 关系演算语言 3 关系逻辑语言 28 2 2关系代数 2 2 1关系代数的五个基本操作2 2 2关系代数的四个组合操作2 2 3关系代数运算的应用实例2 2 4关系代数的七个扩充操作 返回 29 2 2 1关系代数的五个基本操作 1 并 Union 设关系R和S具有相同的关系模式 R和S的并是由属于R或属于S的元组构成的集合 记为R S 形式定义如下 R S t t R t S t是元组变量 R和S的元数相同 差 Difference 设关系R和S具有相同的关系模式 R和S的差是由属于R但不属于S的元组构成的集合 记为R S 形式定义如下 R S t t R t S R和S的元数相同 30 2 2 1关系代数的五个基本操作 2 笛卡尔积 CartesianProduct 形式定义如下 R S t t tr R ts S 此处tr ts中r s为上标 若R有m个元组 S有n个元组 则R S有m n个元组 31 2 2 1关系代数的五个基本操作 3 投影 Projection 对关系进行垂直分割 形式定义如下 i1 im R t t ti1 tim t1 tk R 例如 3 1 R 表示新关系中第1列为R的第3列 新关系的第2列为R的第1列 如果R的每列标上属性名 那么操作符 的下标处也可以用属性名表示 例如 关系R A B C 那么 C A R 与 3 1 R 是等价的 32 2 2 1关系代数的五个基本操作 4 选择 Selection 据条件对关系做水平分割 形式定义如下 F R t t R F t true 例如 2 3 R 表示从R中挑选第2个分量值大于3的元组所构成的关系 书写时 为了与属性序号区别起见 常量用引号括起来 而属性序号或属性名不要用引号括起来 33 2 2 1关系代数的五个基本操作 例 例2 2有两个关系R和S 34 2 2 1关系代数的五个基本操作 例 a b c d e R SR SR S C A R B 4 R 35 2 2 2关系代数的四个组合操作 1 交 intersection 关系R和S的交是由属于R又属于S的元组构成的集合 记为R S 这里要求R和S定义在相同的关系模式上 形式定义如下 R S t t R t S R和S的元数相同 由于R S R R S 或R S S S R 因此交操作不是一个独立的操作 在表2 3中 R S的结果是只有一个元组 4 5 6 36 2 2 2关系代数的四个组合操作 2 连接 join 连接 RS t t tr R ts S tri tsj 定义等价于下式 RS i r j R S 该式表示连接是在关系R和S的笛卡儿积中挑选第i个分量和第 r j 个分量满足 操作的元组 37 2 2 2关系代数的四个组合操作 3 38 2 2 2关系代数的四个组合操作 4 自然连接 naturaljoin 关系R和S的自然连接操作计算过程如下 RS 去掉S中的公共属性 公共属性上值相等 R S a 关系R b 关系S c RS RS A R B R C D R B S B R C S C R S 39 2 2 2关系代数的四个组合操作 5 除法 division 设关系R和S的元数分别为r和s 设r s 0 那么R S是一个 r s 元的元组的集合 R S 是满足下列条件的最大关系 其中每个元组t与S中每个元组u组成的新元组必在关系R中 R S 1 2 r s R 1 2 r s 1 2 r s R S R 40 表2 7除法操作的例子 41 象集Z 给定一个关系R X Z X和Z为属性组 当t X x时 x在R中的象集 ImagesSet 为 Zx t Z t R t X x 它表示R中属性组X上值为x的诸元组在Z上分量的集合 42 除 Division 给定关系R X Y 和S Y Z 其中X Y Z为属性组 R中的Y与S中的Y可以有不同的属性名 但必须出自相同的域集 R与S的除运算得到一个新的关系P X P是R中满足下列条件的元组在X属性列上的投影 元组在X上分量值x的象集Yx包含S在Y上投影的集合 R S tr X tr R Y S Yx Yx x在R中的象集 x tr X 43 除 续 R S 44 除法举例 在关系R中 A可以取四个值 a1 a2 a3 a4 a1的象集为 b1 c2 b2 c3 b2 c1 a2的象集为 b3 c7 b2 c3 a3的象集为 b4 c6 a4的象集为 b6 c6 S在 B C 上的投影为 b1 c2 b2 c1 b2 c3 只有a1的象集包含了S在 B C 属性组上的投影所以R S a1 45 2 2 3关系代数运算的应用实例 在关系代数运算中 把由五个基本操作经过有限次复合的式子称为关系代数表达式 这种表达式的运算结果仍是一个关系 我们可以用关系代数表达式表示各种数据查询操作 例2 6设教学数据库中有四个关系 教师关系T T TNAME TITLE 课程关系C C CNAME T 学生关系S S SNAME AGE SEX 选课关系SC S C SCORE 46 S S SNAME AGE SEX SC S C SCORE 检索学习课程号为C2课程的学生学号与成绩 S SCORE C C2 SC 表达式中也可以不写属性名 而写上属性的序号 1 3 2 C2 SC 检索学习课程号为C2的学生学号与姓名 S SNAME C C2 SSC 由于这个查询涉及到两个关系S与SC 因此先要对这两个关系进行自然连接操作 然后再执行选择和投影操作 47 T T TNAME TITLE S S SNAME AGE SEX C C CNAME T SC S C SCORE 检索至少选修LIU老师所授课程中一门课程的学生学号与姓名 S SNAME TNAME LIU SSCCT 检索选修课程号为C2或C4的学生学号 S C C2 C C4 SC 检索至少选修课程号为C2和C4的学生学号 1 1 4 2 C2 5 C4 SC SC 这里 SC SC 表示关系SC自身相乘的笛卡尔积操作 48 S S SNAME AGE SEX SC S C SCORE 检索不学C2课的学生姓名与年龄 SNAME AGE S SNAME AGE C C2 SSC 这里要用到集合差操作 先求出全体学生的姓名和年龄 再求出学了C2课的学生的姓名和年龄 最后执行两个集合的差操作 SNAME AGE C C2 SSC 49 S S SNAME AGE SEX SC S C SCORE C C CNAME TEACHER 检索学习全部课程的学生姓名 编写这个查询语句的关系代数表达式过程如下 学生选课情况可用操作 S C SC 表示 全部课程可用操作 C C 表示 学了全部课程的学生学号可用除法操作表示 操作结果是学号S 集 S C SC C C 从S 求学生姓名SNAME 可以用自然联接和投影操作组合而成 SNAME S S C SC C C 50 SC S C SCORE 检索所学课程包含学生S3所学课程的学生学号 学生选课情况可用操作 S C SC 表示 学生S3所学课程可用操作 C S S3 SC 表示 所学课程包含学生S3所学课程的学生学号 可以用除法操作求得 S C SC C S S3 SC 51 2 2 3关系代数运算的应用实例 查询语句的关系代数表达式的一般形式是 R S 或者 RS 但是当查询涉及到否定或全部值时 上述形式就不能表达了 就要用到差操作或除法操作 在例2 6中的 说明了这点 52 2 2 4七个扩充操作 1 改名广义投影赋值外连接 outerjoin 外部并 outerunion 半连接 semijoin 聚集操作 53 2 2 4七个扩充操作 2 1 改名 可改变关系的命名和属性的命名 例2 7 设关系R A B 和S B C D 则R S的属性应写成A R B S B C D 使用改名操作后 R S可写成R S X C D S 则其属性为A B X C D 更为清晰 设关系R A B 和S C D 则R和S在B C上自然连接要写成 A B D RS 或 A B D B C R S 使用改名操作后 可写成R S B D S 形式 B C 54 2 2 4七个扩充操作 3 2 广义投影 允许在投影列表中使用算术函数来对投影进行扩展 其形式是 F1 F2 Fn R 这里R是任意的关系模式 F1 F2 Fn是涉及R模式中常量和属性的算术表达式 例2 8在选课关系SC S C SCORE 中 课程号为C4的成绩应增加5 则可用下式表示 S C SCORE 1 05 C C4 SC 55 2 2 4七个扩充操作 4 3 赋值 通过给临时变量赋值 可以把关系代数表达式分开书写 以便把复杂的表达式化整为零 成为简单的表达式 赋值运算符是 类似于计算机语言中的赋值运算符 例2 9关系R和S的除法操作 可用下面的一串操作表示出来 TEMP1 1 2 r s R TEMP2 TEMP1 S RTEMP3 1 2 r s TEMP2 R S TEMP1 TEMP3 56 2 2 4七个扩充操作 5 4 外连接 OuterJoin 如果R和S做自然连接时 把原该舍弃的元组也保留在新关系中 同时在这些元组新增加的属性上填上空值 null 这种操作称为 外连接 操作 用符号RS表示 如果R和S做自然连接时 只把R中原该舍弃的元组放到新关系中 那么这种操作称为 左外连接 操作 用符号RS表示 如果R和S做自然连接时 只把S中原该舍弃的元组放到新关系中 那么这种操作称为 右外连接 操作 用符号RS表示 57 2 2 4七个扩充操作 6 58 2 2 4七个扩充操作 7 5 外部并 OuterUnion 前面定义两个关系的并操作时 要求R和S具有相同的关系模式 如果R和S的关系模式不同 构成的新关系的属性由R和S的所有属性组成 公共属性只取一次 新关系的元组由属于R或属于S的元组构成 同时元组在新增加的属性上填上空值 那么这种操作称为 外部并 操作 59 2 2 4七个扩充操作 8 a 关系R b 关系S c R和S的外部并 60 2 2 4七个扩充操作 9 6 半连接 semijoin RS R RS 或RS R R S S 显然 半连接的交换律是不成立的 即RS SR 半连接操作主要用于分布式数据库中 61 2 2 4七个扩充操作 10 RS R RS 62 2 2 4七个扩充操作 11 7 聚集操作 聚集操作是指输入一个值的集合 然后根据该值集合得到一个单一的值作为结果 聚集函数有max min avg sum和count等 例2 14在S S SNAME AGE SEX 中 求男同学的平均年龄 可以用式子avgage sex M S 表示 求年龄为18岁的人数可用式子countS age 18 S 表示 63 关系代数习题 1 设有如下关系 学生 学号 姓名 性别 专业 出生日期 教师 教师编号 姓名 所在部门 职称 授课 教师编号 学号 课程编号 课程名称 教材 学分 成绩 1 查找学习 数据库原理 课程且成绩不及格的学生学号和任课教师编号 2 查找学习 英语 课程的 计算机应用 专业学生的学号 姓名和成绩 2 设有如下关系 S S SNAME AGE SEX 学生 学号 姓名 年龄 性别 C C CNAME TEACHER 课程 课程号 课程名 任课教师 SC S C GRADE 成绩 学号 课程号 成绩 查询 教师 程军 所授课程的课程号和课程名 李强 同学不学课程的课程号 至少选修了课程号为k1和k5的学生学号 选修课程包含学号为2的学生所修课程的学生学号 64 2 3关系演算 把数理逻辑的谓词演算引入到关系运算中 就可得到以关系演算为基础的运算 关系演算又可分为元组关系演算和域关系演算 前者以元组为变量 后者以属性 域 为变量 2 3 1元组关系演算2 3 2域关系演算2 3 3关系运算的安全约束和等价性 65 2 3 1元组关系演算 1 在元组关系演算 TupleRelationalCalculus 中 元组关系演算表达式简称为元组表达式 其一般形式为 t P t 其中 t是元组变量 表示一个元数固定的元组 P是公式 在数理逻辑中也称为谓词 也就是计算机语言中的条件表达式 t P t 表示满足公式P的所有元组t的集合 66 2 3 1元组关系演算 2 在元组表达式中 公式由原子公式组成 定义2 4原子公式 Atoms 有下列三种形式 R s s i u j s i a或a u j 在定义关系演算操作时 要用到 自由 Free 和 约束 Bound 变量概念 在一个公式中 如果元组变量未用存在量词 或全称量词 符号定义 那么称为自由元组变量 否则称为约束元组变量 67 2 3 1元组关系演算 3 定义2 5公式 Formulas 的递归定义如下 每个原子是一个公式 其中的元组变量是自由变量 如果P1和P2是公式 那么 P1 P1 P2 P1 P2和P1 P2也都是公式 如果P1是公式 那么 s P1 和 s P1 也都是公式 公式中各种运算符的优先级从高到低依次为 和 和 在公式外还可以加括号 以改变上述优先顺序 公式只能由上述四种形式构成 除此之外构成的都不是公式 68 2 3 1元组关系演算 4 例2 15图2 16的 a b 是关系R和S c g 分别是下面五个元组表达式的值 图2 20元组关系演算的例子 R1 t S t t 1 2 R2 t R t S t R3 t u S t R u t 3 u 1 R5 t u v R u S v u 1 v 2 t 1 u 2 t 2 v 3 t 3 u 1 69 2 3 1元组关系演算 5 在元组关系演算的公式中 有下列三个等价的转换规则 P1 P2等价于 P1 P2 P1 P2等价于 P1 P2 s P1 s 等价于 s P1 s s P1 s 等价于 s P1 s P1 P2等价于 P1 P2 70 2 3 1元组关系演算 6 关系代数表达式到元组表达式的转换例2 16R S可用 t R t S t 表示 R S可用 t R t S t 表示 R S可用 t u v R u S V t 1 u 1 t 2 u 2 t 3 u 3 t 4 v 1 t 5 v 2 t 6 v 3 表示 设投影操作是 2 3 R 那么元组表达式可写成 t u R u t l u 2 t 2 u 3 F R 可用 t R t F 表示 F 是F的等价表示形式 譬如 2 d R 可写成 t R t t 2 d 71 例2 17设关系R和S都是二元关系 1 4 2 3 R S R S t u v R u S v t 1 u 1 t 2 u 2 t 3 v 1 t 4 v 2 2 3 R S 在上述表达式的公式中加上 t 2 t 3 即可 1 4 2 3 R S w t u v R u S v t 1 u 1 t 2 u 2 t 3 v 1 t 4 v 2 t 2 t 3 w 1 t 1 w 2 t 4 再对上式化简 去掉元组变量t 可得下式 w u v R u S v u 2 v 1 w 1 u 1 w 2 v 2 72 例2 18对于例2 6中查询语句的关系代数表达式形式也可以用元组表达式形式表示 检索学习课程号为C2的学生学号与成绩 S GRADE C C2 SC t u SC u u 2 C2 t l u 1 t 2 u 3 检索学习课程号为C2的学生学号与姓名 S SNAME C C2 SSC t u v S u SC v v 2 C2 u l v 1 t l u 1 t 2 u 2 73 例2 18对于例2 6中查询语句的关系代数表达式形式也可以用元组表达式形式表示 检索至少选修LIU老师所授课程中一门课程的学生学号与姓名 S SNAME CNAME MATHS SSCCT t u v w x S u SC v C w T x u l v 1 v 2 w 1 w 3 x 1 x 2 LIU t l u 1 t 2 u 2 检索选修课程号为C2或C4的学生学号 S C C2 C C4 SC t u SC u u 2 C2 u 2 C4 t l u 1 74 例2 18对于例2 6中查询语句的关系代数表达式形式也可以用元组表达式形式表示 检索至少选修课程号为C2和C4的学生学号 1 1 4 2 C2 5 C4 SC SC t u v SC u SC v u 2 C2 v 2 C4 u l v 1 t l u 1 检索不学C2课的学生姓名与年龄 SNAME AGE S SNAME AGE C C2 SSC t u v S u SC v u l v 1 v 2 C2 t 1 u 2 t 2 u 3 75 例2 18对于例2 6中查询语句的关系代数表达式形式也可以用元组表达式形式表示 检索学习全部课程的学生姓名 SNAME S S C SC C C t u v w S u C v SC w u l w 1 v 1 w 2 t 1 u 2 检索所学课程包含学号S3所学课程的学生 S C SC C S S3 SC t u SC u v SC v v 1 S3 w SC w w 1 u 1 w 2 v 2 t l u 1 76 2 3 2域关系演算 1 原子公式有两种形式 R x1 xk x y 公式中也可使用 和 等逻辑运算符 x 和 x 但变量x是域变量 不是元组变量 自由域变量 约束域变量等概念和元组演算中一样 域演算表达式是形为 t1 tk P t1 tk 的表达式 其中P t1 tk 是关于自由域变量t1 tk的公式 77 2 3 2域关系演算 2 例2 19图2 17的 a b c 是三个关系R S W d e f 分别表示下面三个域表达式的值 a 关系R b 关系S c 关系W d R1 e R2 f R3图2 17域关系演算的例子 R1 xyz R xyz x3 R2 xyz R xyz S xyz y 4 R3 xyz u v R zxu w yv u v 78 2 3 2域关系演算 3 元组表达式到域表达式的转换我们可以很容易地把元组表达式转换成域表达式 转换规则如下 对于k元的元组变量t 可引入k个域变量t1 tk 在公式中t用t1 tk替换 元组分量t i 用ti替换 对于每个量词 u 或 u 若u是m元的元组变量 则引入m个新的域变量u1 um 在量词的辖域内 u用u1 um替换 u i 用ui替换 u 用 u1 um 替换 u 用 u1 um 替换 79 例2 20设关系R和S都是二元关系 1 4 2 3 R S 例2 17转换成的元组表达式是 w u v R u S v u 2 v 1 w 1 u 1 w 2 v 2 再转换成域表达式 w1w2 u1 u2 v1 v2 R u1u2 S v1v2 u2 v1 w1 u1 w2 v2 再进一步简化 可消去域变量u1 v1 v2 得到下式 w1w2 u2 R w1u2 S u2w2 80 例2 21对于例2 6 例2 18的查询 可转换成下列域表达式 检索学习课程号为C2的学生学号与成绩 t1t2 u1 u2 u3 SC u1u2u3 u2 C2 t1 u1 t2 u3 可化简为 t1t2 SC t1 C2 t2 检索学习课程号为C2的学生学号与姓名 t1t2 u1 u2 u3 u4 v1 v2 v3 S u1u2u3u4 SC v1v2v3 v2 C2 u1 v1 t1 u1 t2 u2 可化简为 t1t2 u3 u4 v3 S t1t2u3u4 SC t1 C2 v3 81 2 3 3关系运算的安全约束和等价性 定义2 6在数据库技术中 不产生无限关系和无穷验证的运算称为安全运算 相应的表达式称为安全表达式 所采取的措施称为安全约束 并 差 笛卡儿积 投影和选择是关系代数最基本的操作 并构成了关系代数运算的最小完备集 已经证明 在这个基础上 关系代数 安全的元组关系演算 安全的域关系演算在关系的表达和操作能力上是完全等价的 82 关系运算的安全性 元组表达式 t R t 这是一个无限关系 验证公式 u P1 u 为假时 必须对所有可能的元组u进行验证 当所有的u都使P1 u 为假时 才能断定公式 u P1 u 为假 验证公式 u P1 u 也是这样 当所有可能的u使P1 u 为真时 才能断定公式 u P1 u 为真 这在实际上是行不通的 我们必须采取措施 防止无限关系和无穷验证的出现 83 关系运算的安全性 续 对于元组表达式 t P t 将公式P t 的 域 Domain 定义为出现在公式P t 中的常量和关系的所有属性值组成的集合 记为DOM P t 由于所有关系都是有限的 因此DOM P 也是有限的 例如P t 是t 1 a R t R是二元关系 那么DOM P a 1 R 2 R 84 关系运算的安全性 续 安全的元组表达式 t P t 应满足下列三个条件 表达式的元组t中出现的所有值均来自DOM P 对于P t 中每个形如 u P1 u 的子公式 如果元组u使P1 u 为真 那么u的每个分量必是DOM P1 的元素 换言之 如果u有某个分量不属于DOM P1 那么P1 u 必为假 对于P t 中每个形如 u P1 u 的子公式 如果元组u使P1 u 为假 那么u的每个分量必是DOM P1 的元素 换言之 如果u有某个分量不属于DOM P1 那么P1 u 必为真 85 关系运算的等价性 ISBL InformationSystemBaseLanguage 语言与关系代数非常接近 QUEL语言 QueryLanguage 是一种基于元组演算的数据语言 QBE QueryByExample 按例查询 是一种特殊的屏幕编辑语言 是一种域演算语言 现在 QBE的思想已渗入到许多DBMS中 SQL StructuredQueryLanguage 是介乎于关系代数和元组演算之间的一种关系查询语言 现已成为关系数据库的标准语言 我们将在第3章详细介绍 86 2 4关系代数表达式的优化 2 4 1关系代数表达式的优化问题2 4 2关系代数表达式的等价变换规则2 4 3关系代数表达式的优化算法 87 2 4 1关系代数表达式的优化 1 在关系代数表达式中需要指出若干关系的操作步骤 那么 系统应该以什么样的操作顺序 才能做到既省时间 又省空间 而且效率也比较高呢 这个问题称为查询优化问题 在关系代数运算中 笛卡儿积和连接运算是最费时间的 88 2 4 1关系代数表达式的优化 2 例2 22设关系R和S都是二元关系 属性名分别为A B和C D E1 A B C D 99 R S E2 A B C R D 99 S E3 A R D 99 S 这三个关系代数表达式是等价的 但执行的效率大不一样 显然 求El E2 E3的大部分时间是花在连接操作上的 返回 89 2 4 2等价变换规则 1 连接和笛卡儿积的交换律连接和笛卡儿积的结合律投影的级联选择的级联选择和投影操作的交换选择对笛卡儿积的分配律选择对并的分配律 90 2 4 2等价变换规则 2 选择对集合差的分配律选择对自然连接的分配律投影对笛卡儿积的分配律投影对并的分配律选择与连接操作的结合并和交的交换律并和交的结合律 返回 91 2 4 3启发式优化算法 1 在关系代数表达式中 最花费时间和空间的运算是笛卡儿积和连接操作 为此 引出三条启发式规则 用于对表达式进行转换 以减少中间关系的大小 尽可能早地执行选择操作 尽可能早地执行投影操作 避免直接做笛卡儿积 把笛卡儿积操作之前和之后的一连串选择和投影合并起来一起做 92 2 4 3启发式优化算法 2 算法2 1关系代数表达式的启发式优化算法 输入 一个关系代数表达式的语法树输出 计算表达式的一个优化序列方法 把每个形为 F1 Fn E 的子表达式转换成选择级联形式 F1 Fn E 在语法树中 尽可能把每个选择下推到树的叶端 对每个投影操作 尽可能往下推 移向树的叶端 把选择和投影合并在一起做 将上述步骤得到的语法树的内结点分组 以每个二元运算 结点为中心分组 生成一个序列 每一组结点的计算是序列中的一步 93 2 4 3启发式优化算法 3 例2 23查询语句 检索学习课程名为OS的女学生学号和姓名 该查询语句的关系代数表达式如下 S SNAME CNAME OS SEX F CSCS 上式中 符号用 操作表示 可得下式 S SNAME CNAME OS SEX F L C C SC C SC S S S C SC S 此处L是C SC S中全部属性 94 2 4 3启发式优化算法 4 图2 18关系代数表达式的初始语法树 95 2 4 3启发式优化算法 5 图2 19优化过程中的语法树 选择操作已尽可能移向叶端 96 2 4 3启发式优化算法 6 图2 20优化的语法树及其分组 97 2 5关系逻辑 2 5 1关系运算的成分2 5 2规则的安全性2 5 3从关系代数到关系逻辑的转换2 5 4递归过程2 5 5关系逻辑与关系代数的差异 98 2 5 1关系运算的成分 1 1 谓词 predicates 定义2 7其关系存储在数据库中的谓词称为 外延谓词 extensionalpredica te 而把由逻辑规则定义的谓词称为 内涵谓词 intensionalpredicate 一般 我们用 外延数据库 的缩写EDB来引用外延谓词或相应关系 用 内涵数据库 的缩写IDB来引用内涵谓词或相应关系 99 2 5 1关系运算的成分 2 2 原子 atoms 定义2 8关系逻辑中的原子有两种 关系原子是一个谓词符号 算术原子是算术比较表达式 例如关系R A B C 那么关系原子R 2345 b c 表示了表达式 1 2345 R 如果关系原子是R x b x 则表示了表达式 1 3 R 算术原子用中缀形式表示 例如x y 100 2 5 1关系运算的成分 3 3 规则定义2 9规则是形为W P1 P2 Pn的式子 规则有三部分组成 一个称为头部 head 的关系原子 符号 通常读作 if 包括一个或多个原子的体 body 称为子目标 subgoal 它可能是关系原子 也可能是算术原子 各子目标用 与 运算符 连接 并且子目标前面可以有 非 运算符 也可以没有 101 2 5 1关系运算的成分 4 实际上 规则W P1 P2 Pn 就是逻辑蕴涵式P1 P2 Pn W 即if P1 P2 Pn thenW 或者 P1 P2 Pn W 102 2 5 1关系运算的成分 5 例2 24设关系S S SNAME AGE SEX 现有一个规则W a b S a b c M c 20此处 规则的头部是W a b 规则的体包括两个子目标 第一个子目标有谓词S和4个参数 对应于关系S的4个属性 当S中元组的AGE值大于20时 第2个子目标c 20为真 因此 这个规则等价于关系代数中下列操作 W S SNAME AGE 20 SEX M S 103 2 5 1关系运算的成分 6 4 查询定义2 10关系逻辑中的查询是一个或多个规则的聚集 规则之间的顺序无关紧 104 2 5 2规则的安全性 1 在规则中 应保证头部关系是有限的 如果得到的头部关系是无限的 那么这种规则是无意义的 在规则的子目标中 有四种形式 关系子目标 求反关系子目标 算术子目标和求反算术子目标 关系子目标总是有限的 而另外三种形式则是无限的 因此对于另外三种形式必须保证取值限制在一定的范围之内 为了保证规则的结果有意义 使得带有算术子目标或求反子目标的规则具有直观的意义 我们必须对规则中变量的使用方式加以限制 这种限制条件称为 安全条件 105 2 5 2规则的安全性 2 安全条件的含义是 出现在规则中任何地方的变量必须出现在某个非求反的关系子目标中 也就是 在头部 求反关系子目标或任何算术子目标中出现的变量 必须出现在非求反的关系子目标中 通过把变量限制在取值有限的关系子目标中 使得规则的查询结果是有限的 106 2 5 2规则的安全性 3 例2 25下列规则有三处违反了安全条件 P x y Q x z R w x z x y 变量y出现在头部 但是没有出现在任何非求反的关系子目标中 虽然y出现在算术子目标x y 但仍无法限制y在有限集中 变量w出现在求反的关系子目标中而不在非求反的关系子目标中 变量y出现在算术子目标中 但不在非求反的关系子目标中 因此 这个规则不是安全的规则 107 2 5 2规则的安全性 4 例2 26下列规则是一个安全的规则 P x y Q x z R z y Q x y 假设关系Q包括两个元组 1 2 和 1 3 关系R包括两个元组 2 3 和 3 1 这里有两个非求反的关系子目标 Q x z 和R z y 所以 我们必须考虑分别来自Q和R的元组对这些子目标赋值的所有组合 表2 1考虑了这四种组合 显然P中唯一的元组是 1 1 108 2 5 2规则的安全性 5 表2 1元组对Q x z 和R z y 的赋值组合 109 2 5 3从关系代数到关系逻辑的转换 1 例2 27设有关系R A B C 和S A B C 那么R S可用下列规则计算 W a b c R a b c S a b c 例2 28那么R S可用下列规则计算 W a b c R a b c W a b c S a b c 例2 29那么R S可用下列规则计算 W a b c R a b c S a b c 110 2 5 3从关系代数到关系逻辑的转换 2 例2 30设有关系R A B C 那么 C A R 可用下列规则计算 W c a R a b c 例2 31设有关系R A B C 那么 B 5 C 18 R 可以写成下列规则 W a b c R a b c b 5 c 18 例2 32设有关系R A B C 那么 B 5 C 18 R 可以用两个规则表示 W a b c R a b c b 5 W a b c R a b c c 18 111 2 5 3从关系代数到关系逻辑的转换 3 例2 33设有关系R A B C 和S D E F 那么R S可用下列规则表示 W a b c x y z R a b c S x y z 例2 34设有关系R A B C 和S C D E 那么R S可用下列规则定义 W a b c d e R a b c S c d e 112 2 5 3从关系