第四章 关系运算.ppt

第4章关系运算 关系模型的三个组成部分数据结构 数据库中全部结构及其相互联系被组织成 关系 数据操纵 关系模型提供一组完备的高级关系运算 包括关系代数和关系演算两类 数据完整性规则 三类完整性规则 关系数据库的数据操纵语言 DML 分为查询语句 更新语句两类 查询语句比较复杂 以 关系运算理论 为基础关系查询语言的分类关系代数语言 以集合操作为基础关系演算语言 以谓词演算为基础 主要内容 4 1关系代数4 2关系演算4 3关系代数表达式的优化 4 1关系代数 4 1 1关系代数的五个基本操作4 1 2关系代数的四个组合操作4 1 3关系代数的应用实例4 1 4关系代数的扩充操作 4 1 1关系代数的五个基本操作 关系代数是以关系为运算对象的一组高级运算的集合 传统的集合操作 并 差 交 笛卡儿积 乘法 笛卡儿积的逆运算 除法 扩充的关系操作 投影 选择 连接 自然连接等1 并操作设R和S具有相同的关系模式 则R S t t R t S t为元组变量属于R或属于S 例 假定有如下关系 R S的结果 4 1 1关系代数的五个基本操作 2 差操作设R和S具有相同的关系模式 则R S t t R t S 属于R但不属于S 例 假定有如下关系 4 1 1关系代数的五个基本操作 3 笛卡尔乘积设R与S的元数分别为r s 则R S t t tr R ts S 元数r s 每个元组前r个属性值来自R的一个元组 后s个属性值来自S的一个元组 例 假定有如下关系 4 1 1关系代数的五个基本操作 4 投影操作R为一个k元关系 i1 i2 im是R的m个属性 R在i1 i2 im的投影操作定义为 i1 im R t t R 进行垂直分割 消去某些列 并重新按排列的顺序 例 假定有如下关系 C A R 的结果 4 1 1关系代数的五个基本操作 5 选择操作运算对象 常数 用引号括起来 元组分量运算符 算术比较运算符 也称 符 逻辑运算符 则R关于公式F的选择操作定义为 F R t t R F t true 从R中挑选满足公式F为真的元组所构成的关系根据条件对关系做水平分割 例 假定有如下关系 B b R 的结果 例4 1 有两个关系R和S 求出RS R S R S C A R B 4 R a 关系R b 关系S 4 1 2关系代数的四个组合操作 1 交操作 Intersection 关系R与关系S的交记作 R S t t R t S 其结果仍为n目关系 由既属于R又属于S的元组组成 关系的交可以用差来表示 即R S R R S 2 连接 Join 也称为 连接它是从两个关系的笛卡尔积中选取属性间满足一定条件的元组 记作 R S trts tr R ts S tr A ts B A B其中A和B分别为R和S上度数相等且可比的属性组 是比较运算符 例4 2 有两个关系R和S 关系R 关系S 4 1 2关系代数的四个组合操作 3 自然连接操作 Naturaljoin 自然连接 Naturaljoin 是一种特殊的等值连接 它要求两个关系中进行比较的分量必须是相同的属性组 并且在结果中把重复的属性列去掉 4 1 2关系代数的四个组合操作 3 自然连接操作 Naturaljoin 两个关系R和S的自然连接操作用表示 具体计算过程如下 计算R S 设R和S的公共属性是A1 Ak 挑选R S中满足R A1 S A1 R Ak S Ak的那些元组去掉S A1 S Ak这些列因此可用下式定义 其中为R和S的全部属性 但公共属性只出现一次 例4 3 关系R 关系S 4 1 2关系代数的四个组合操作 4 除操作 Division 设关系R和S的元数分别为r和s 设r s 0 那么R S是一个 r s 元的元组的集合 R S 是满足下列条件的最大关系 其中每个元组t与S中每个元组u组成的新元组必在关系R中 为方便起见 我们假设S的属性为R中后s个属性 4 1 2关系代数的四个组合操作 4 除操作 Division R S的具体计算过程如下 例 假定有如下关系 给定公式B D 则R和S关于此公式连接操作的结果 4 1 3关系代数运算的应用实例 例 设教学数据库中有三个关系 教师关系T T TNAME TITLE 学生关系S S SNAME AGE SEX 选课关系SC S C SCORE 课程关系C C CNAME T 试用相应的关系代数表达式描述查询语句一般格式 R S 1 检索学习课程为C2课程的学生学号与成绩 2 检索学习课程号位C2课程的学生学号与姓名 3 检索至少选修LIU老师所授课程中一门课程的学生学号与姓名 4 检索选修课程号为C2或C4课程的学生学号 5 检索至少选修课程号为C2和C4课程的学生学号 6 检索不学C2课的学生姓名与年龄 7 检索学习全部课程的学生姓名学生选课情况可用操作 表示全部课程可用 学习了全部课程的学生学号可用除法操作表示 从S 求学生姓名SNAME 可用自然连接和投影操作组合而成 8 检索所学课程包含学号为S3学生所学课程的学生学号学生选课情况可用操作 学生S3所学课程可用操作 所学课程包含学生S3所学课程的学生学号 可用除法操作求得 4 1 4关系代数的扩充操作 1 外连接 OuterJoin 为了保存自然连接操作时被舍弃的元组关系模式R和S作自然连接时 将原该舍弃的元组也保留在新关系中 并在其新属性上填上空值 称为 外连接 操作若只把R中该舍弃的元组保留在新关系中 称为 左外连接 若只把S中该舍弃的元组保留在新关系中 称为 左外连接 4 1 4关系代数的扩充操作 4 1 4关系代数的扩充操作 4 1 4关系代数的扩充操作 2 外部并 OuterUnion 关系模式R和S模式不同 构成的新关系的属性由R和S的所有属性组成 公共属性只取一次 新关系的元组由属于R或属于S的元组构成 同时元组在新增加的属性上填空值 称为 外部并 操作 4 1 4关系代数的扩充操作 关系R 关系S 外部并 4 2关系演算 4 2 1元组关系演算4 2 2域关系演算4 2 3关系运算的安全约束和等价性 36 关系演算以数理逻辑中的谓词演算为基础按谓词变元不同进行分类1 元组关系演算 以元组变量作为谓词变元的基本对象2 域关系演算 以域变量作为谓词变元的基本对象 4 2 1元组关系演算 元组关系表达式简称为元组表达式 其一般形式 t P t t是元组变量 表示一个元数固定的元组P是公司 在数理逻辑中也称为谓词 也就是计算机语言中的条件表达式 t P t 表示满足公式P的所有元组t的集合 4 2 1元组关系演算 在元组表达式中 公式由原子公式组成定义4 1原子公式有下列三种形式 R s R为关系名 s为元组变量 R t 表示s是R中的元组这样一个命题函数 s i u j s和u是两个元组 i和j表示元组分量的序号 是算术比较符 所表示的命题函数是元组s第i个分量与元组u第j个分量满足 关系 如s 1 u 2 s i a或a u j 这里a是常量 表示的命题函数是元组第i个分量与常数a满足 关系 如s 4 3 4 2 1元组关系演算 在定义关系演算操作时 要用到自由和约束变量概念 在一个公式中 如果元组变量未用存在量词或全称量词符号定义 那么称其为自由元组变量 否则称为约束元组变量 4 2 1元组关系演算 公式4 2公式的递归定义如下 1 每个原子是一个公式 其中的元组变量是自由变量 2 如果P1和P2是公式 那么 和也都是公式 分别表示以下命题 P1不是真 P1或P2或两者都是真 P1和P2都是真 若P1为真则P2必然为真 3 如果P1是公式 那么也都是公式 其中s是公式P1中的自由元组变量 在中成为约束元组变量 这两个公式分别表示存在一个元组s使得公式P1为真 对于所有元组s都使得公式P1为真 4 2 1元组关系演算 4 公式中各种运算符的优先级从高到低依次为 5 公式只能由上述四种形式构成 除此之外构成的都不是公式 例4 8 关系R 关系S 4 2 1元组关系演算 在元组关系演算的公式中 有下列三个等价的转换规则 44 关系代数表达式到元组表达式的转换例4 9R 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 4 2 1元组关系演算 45 类似于元组运算 只不过公式中的变量用元组各分量对应的域变量来描述 域演算的谓词变元是域变量 域演算表达式的一般形式为 t1 t2 tk t1 t2 tk 其中t1 t2 tk分别是域变量 是域演算公式 4 2 2域关系演算 递归定义域运算公式 1 原子公式 R t1 t2 tn R为n元关系 ti是域变量或常量 表示的谓词含义 以t1 t2 tn为分量的元组在关系R中 ti uj ti为元组t第i个分量 uj为元组u第j个分量 为算术比较符 表示的谓词含义为t的第i个分量与u的第j个分量满足 关系 ti c c为常量 表示的谓司含义是t的第i个分量与常数C满足 关系 4 2 2域关系演算 2 递归定义 原子公式是域运算公式 若 1 2是公式 则 1 2 1 2 1也是公式 有限次使用 也是公式 4 2 2域关系演算 例4 12 关系R 关系S 关系W 例4