数据库系统原理-第五章代数和逻辑查询语言.ppt

第5章代数和逻辑查询语言 5 1关系代数操作5 2包上的关系操作5 3关系代数的扩展操作符5 4关系逻辑5 5关系代数与Datalog Page1 5 1关系代数操作 1 关系代数的传统定义一个元组集合 即关系 能用来进行典型的基于关系的查询集合上的五个操作 并 差 笛卡尔积 选择 投影在基本操作上定义的附加操作 各种连接关系代数的操作规则对于集合和包是不一样的简单的说 包是以空间代价换取时间效率所以对一般小例子来说 包的综合效率更高但对实际应用中的数据库来说 用集合更加合理 Page2 5 1关系代数操作 2 关系中的集合操作基本集合操作 并 交 差应用到关系操作时 需要附加约束属性列表和属性类型必须一致属性的排列顺序也要一致原则上属性名也要对应一致 如果不一致 需要利用重命名操作处理 Page3 5 1关系代数操作 3 投影 A1 A2 An R 只保留指定部分列由于属性减少 元组可能会重值 进而合并 因此数目可能减少选择 C R 该操作产生的新关系的元组必须满足条件C结果关系和原关系的模式相同 Page4 5 1关系代数操作 4 笛卡尔积R S一个有序对的集合 有序对的第一个元素来自R 第二个元素来自S一般地 笛卡尔积对应一个关系 其元组维度更大 个数更多如果R和S有重名属性 则在结果中加前缀区分连接操作参与连接操作的一般是两个关系 且连接时相应的元组在某些方面具有一致性 连接分为三类全连接即笛卡尔积自然连接 连接 Page5 5 2包上的关系操作 1 一组元素的一种聚集形式 允许重复元素出现 而集合set中不允许元素重复出现 对一个包去掉其中重复元素 就可得到一个集合 一个集合可认为是一个特殊的包 其中没有重复元组 什么是包bag Page6 关系看作为集合 则不允许有重复元组 如果看作为包 则允许有重复元组 包 集合 5 2包上的关系操作 1 Page7 为何需要包 关系中的元组应该不重复 但经运算得到的新关系中的元组可以重复 数据库系统支持提高投影计算效率对聚合运算有用 汇总值 平均值 计数等 Page8 例子 商业DBMS实现的都是包 为什么呢 包的实现效率较高 包的并操作和投影操作实现简单例如 对下面关系在A B属性上的投影 包 集合 Page9 例子 例如 对下面关系R 要求A属性的平均值 则先对A属性投影 如果允许结果为包 则均值为1 5 否则为2 错 包 集合 Page10 5 2包上的关系操作 2 包上的运算 并 交 差 投影 选择 乘积和连接等都允许运算之前和之后元组重复对两个关系求并 集合方式要先合并再去重 而包方式只合并不去重 所以效率更高投影操作后不去重对后面要出现的聚集操作来说 只能用包方式 用集合方式的话会出现逻辑错误 Page11 包的并 交 差设R和S是包 若元组t在R和S中分别出现n次和m次 这里的m和n可以是0 则 R S的包并操作结果中 元组t出现m n次 R S的包交操作结果中 元组t出现min m n 次 R S的包差操作结果中 元组t出现max 0 n m 次 减后为负数则取0 Page12 包的并 交 差举例 设关系R S如下 R S R S R S R S Page13 5 2包上的关系操作 2 集合上的包操作 文本框内容释义 如果对两个集合R S进行基于包的交和差操作 其结果与集合方式运算一样因为作为被处理对象的两个关系本身没有重复的元组 所以交或差之后结果中仍然没有重值元组但对两个集合R和S 进行基于包的并操作 其操作结果可能不再是集合结论 必须看清 答题 声明 出题 是包方式还是集合方式 Page14 如果在投影操作过程中 产生了多个同样的元组 那些重复的元组将不会被从包投影结果中除去 如对enroll表的cid投影 包 关系 5 2包上的关系操作 3 Page15 举例 RAB125612 Page16 如果在进行选择操作时 要独立地对每个元组应用选择条件 在结果中不去除重复元组 R C 6 R 5 2包上的关系操作 4 Page17 举例 RAB125612 Page18 一个关系中的每个元组与另一个关系中的每个元组配对 而不问这个元组是否重复出现 R R S S 5 2包上的关系操作 5 Page19 举例 RABSBC1234567812 R S AR BS BC123412785634567812341278 Page20 包的连接操作也跟预想的一样 首先对比两个关系中的元组 看是否能组成一对 如果能 则配对起来的元组就是结果关系中的一员 R R S S 5 2包上的关系操作 6 Page21 连接如下 R R R B S BS S 5 2包上的关系操作 6 Page22 举例 RABSBC1234567812 R R B S BS AR BS BC12341278567812341278 Page23 5 3关系代数的扩展操作 1 1 消除重复清除包中的重复元素 只保留一个副本在关系中2 聚集操作应用到关系的属性上 比如求和操作3 分组根据元组在一个或多个属性的值把关系的元组拆分成 组 4 扩展投影以原有的列作为参数来计算 并产生新的列5 排序算子根据一个或多个属性对关系的元组来排序6 外连接算符连接运算的变体 防止了悬挂元组的出现 Page24 消除重复消除关系R中的重复元组 将包转化为集合 R 例5 8 R R Page25 聚集操作符汇总或 聚集 关系中某一列出现的值SUM用来产生一列总和 得到的是一个数字值AVG用来产生一列平均值 结果也是数字值MAX和MIN当用于数字值列的时候 产生的分别是这一列中最大的和最小的值 当应用于字符列的时候产生是字典序的最大者和最小者COUNT产生一列中的 值 的数目 并不一定指不同的值 同样 COUNT应用于一个关系的任何属性时 产生的是这个关系的元组数 包括重复的元组 Page26 例子 考虑关系 1 SUM B 2 4 2 2 102 AVG A 1 3 1 1 4 1 53 MIN A 14 MAX B 45 COUNT A 4 Page27 分组为什么要分组分组是便于各分组中元组的聚集操作 如何分组算符 的下标是一个元素的列表 其中每个元素是下列情况之一 是应用 操作的那个关系的一个属性 这个属性是那些可以把R分组的属性其中之一 这个元素称为分组属性 应用到关系的一个属性上的聚集操作符 为了在结果中对应此聚集 给属性一个名称 一个箭头和一个新的名字附在这个聚集的后面 称为聚集属性 Page28 分组操作符 L R 分组操作符的下标是一个元素的列表L 可以是 应用 操作的关系的一个属性 R使用这个属性分组 称为分组属性 例如 图5 4 studioname Movies 应用到关系的一个属性上的聚集操作符 可以使用箭头给聚集属性列命名 例如 studioname SUM length sumOFLength Movies Page29 表达式 L R 的求解过程根据L中的分组属性 按照该属性上的不同取值进行分组对每一组 产生一个元组 其属性和属性值按照L取L中的分组属性 该组在分组属性上的值L中的属性聚集结果 箭头右侧属性 例5 23对关系StarsIn title year starName 查询至少出演了三部电影的影星 以及他们在电影中出现的最早年份 starname MIN year minYear COUNT title ctTitle StarsIn 先聚集 再选择 最后投影得到结果 Page30 设关系student 学生 course 课程 和sc 成绩 如下 Page31 1 查询各个专业的学生人数及平均年龄2 统计各门课的平均成绩 最高成绩及选修人数3 查询被两个以上同学选修的课程的课程名及平均成绩 分组操作符举例 1 查询各个专业的学生人数及平均年龄2 统计各门课的平均成绩 最高成绩及选修人数3 查询被两个以上同学选修的课程的课程名及平均成绩 sdept count sno snum avg sage avgage student 注意 分组后取出姓名 学号 性别是没意义的 Page32 是 的特殊情况 如果R A1 A2 An 是关系 则 A1 A2 An R 与 R 等价 Page33 举例 参演关系如下 starsin title year starname 找出至少出演了三部电影的影星 以及他们在电影中出现的最早年份 starname minyear cttitle 3 starname MIN year minyear count title cttitle starsin Page34 扩展的投影操作符 L R L R 其中L是R的一些属性序列 L的组成可以做如下扩展 R的属性 形如 x y x是R的属性 y为结果模式中的新属性名 E z E是表达式 z是表达式E计算结果的属性的新名字 如 a b x 表示a和b属性的和并生命名为x Page35 举例 令R关系如下 那么 A B C X R 为 Page36 举例 令R关系如下 那么 B A X C B Y R 为 Page37 举例 令R关系如下 那么 A B C X R 为 Page38 举例 令R关系如下 那么 B A X C B Y R 为 Page39 排序操作符 有时人们希望对关系中的元组按照一个或多个属性值排序 L R L是R中某些属性的列表 对R中的元组按照L列出的属性排序 作为结果返回 如果L是A1 A2 An 那么R的元组就先按属性A1的值排序 对于A1属性相等的元组就按A2的值排序 依此类推 Page40 举例 令R关系如下 那么 B C A R 为 Page41 外连接 连接操作的缺陷连接操作的一个性质是可能产生悬挂元组 而这些元组不能跟另外关系的任何一个元组匹配 所以这种连接操作并不能完全反映原始关系的全部信息 什么是外连接先计算两个关系R和S的自然连接 然后再把来自R或S的悬浮元组加入其中 用null符号补齐结果元组中那些不具有值的属性 我们称之为外连接 用符号表示 Page42 设有关系 U V UV Page43 外连接的不同变体 只是将左变量R的悬浮元组补齐加入到结果中 称之左外连接 用符号RLS表示 只是将右变量S的悬浮元组补齐加入到结果中 称之左外连接 用符号RRS表示 外连接的操作是 先进行 连接 然后将那些不能匹配其他关系的元组 也用补齐 用UCV表示一个带条件C的 外连接 同样 可用L或R来修饰这个算符 使其表示 的左外连接或右外连接 Page44 如果只将左边关系中的悬浮元组加入到结果关系中 就是左外连接 oL S R oLS R 外连接的不同变体 Page45 如果只将右边关系中的悬浮元组加入到结果关系中 就是右外连接 oR R R oRS S 外连接的不同变体 Page46 类似于自然连接 连接也有对应的外连接 R S R A DS 外连接的不同变体 Page47 举例 R S R OA DS Page48 举例 R S R LA DS Page49 举例 R S R RA DS Page50 练习 P130习题5 2 1a c e f g k n已知关系R A B 0 1 2 3 0 1 2 4 3 4 S B C 0 1 2 4 2 5 3 4 0 2 3 4 计算下面的表达式 a Page51 练习 P130习题5 2 1a c e f g k n已知关系R A B 0 1 2 3 0 1 2 4 3 4 S B C 0 1 2 4 2 5 3 4 0 2 3 4 计算下面的表达式 c Page52 练习 P130习题5 2 1a c e g k n已知关系R A B 0 1 2 3 0 1 2 4 3 4 S B C 0 1 2 4 2 5 3 4 0 2 3 4 计算下面的表达式 e Page53 练习 P130习题5 2 1a c e g k n已知关系R A B 0 1 2 3 0 1 2 4 3 4 S B C 0 1 2 4 2 5 3 4 0 2 3 4 计算下面的表达式 g Page54 练习 P130习题5 2 1a c e g k n已知关系R A B 0 1 2 3 0 1 2 4 3 4 S B C 0 1 2 4 2 5 3 4 0 2 3 4 计算下面的表达式 k Page55 练习 P130习题5 2 1a c e g k n已知关系R A B 0 1 2 3 0 1 2 4 3 4 S B C 0 1 2 4 2 5 3 4 0 2 3 4 计算下面的表达式 n Page56 随着数据技术的不断提高 关系代数也暴露出了一些局限性 例如 无法有效地表示递归运算 逻辑表达能力弱等 在这种情况下 Datalog语言应运而生 Datalog语言是一种基于逻辑编程语言Prolog的一种非过程化的语言 同关系演算类似 用户只需要给出所描述的信息 不需要给出获取信息的具体过程 本节介绍Datalog语言的基本结构 规则以及从关系代数到Datalog语言的转换等内容 5 4关系逻辑 1 Page57 基本概念 逻辑也是一种表示关系查询的方法 例如Datalog语言就可以表示相同类型的查询 Datalog语言不是使用过程语言来表示查询 而是使用一种规则来表示出这种想法 即可以通过已知的关系中的某些元组的组合来推测元组是否在关系中 Page58 基本结构 Datalog语言包括两种基本的原子 即关系原子和算术原子 由原子按照一定的规则组成Datalog查询语句 在Datalog语言中 关系通过 谓词 来表示 每一个谓词都有固定数量的参数 关系原子是由符号谓词和其后的参数组成 常简称原子 例如 如果谓词是R 其参数分别是t1 t2 tn 那么R t1 t2 tn 就是一个关系原子 算术原子是两个算术表达式的比较 算术原子的值是布尔值 Page59 例子 Page60 一般规则 规则是Datalog语言中描述原子之间关联的规范 包括下列三个组成部分 1 一个称为头部的关系原子 其后是2 左向箭头符号 读作if 其后是3 主体部分 由一个或多个称为子目标的原子组成 子目标既可以是关系原子 也可以是算术原子 各个子目标之间用逻辑运算符AND连接 且各个子目标前面可以有选择地增加取反逻辑运算符NOT 规则的目标是使规则的头部关系原子为真 例如 LongMovie t y Movies t y l g s p ANDl 100等价于LongMovie title year length 100 Movies Page61 例子 Page62 例子 Page63 例子 Page64 例子 Page65 Page66 安全规则 安全规则 由于关系实例总是有限 所以还需要由规则保证得到的头部关系也都是有限的 每个在规则中任意位置出现的变量都必须出现在主体的某些非否定的关系子目标中 尤其是 任何在规则头部 否定关系子目标或任意算术子目标中出现的变量 也必须出现在主体的非否定的关系子目标中 Page67 例5 19安全规则LongMovie t y Movies t y l g s p ANDl 100例5 20非安全规则 不允许出现在Datalog中P x y Q x z ANDNOTR w x z ANDx y Page68 扩展谓词和内涵谓词 若谓词所指的关系存储在数据库中 称该谓词为扩展谓词 当谓词所指的关系是通过一个或多个Datalog规则计算得到的 称该谓词是内涵谓词 扩展谓词和内涵谓词分别对应关系代数表达式中的操作数和使用关系代数表达式计算得到的关系 在Datalog规则中 可以使用EDB ExternalDatabase 扩展数据库 表示扩展谓词或相应的关系 使用IDB InternalDatabase 内涵数据库 表示内涵谓词或相应的关系 例如 Movies是一个EDB关系 而LongMovie是一个IDB关系 Page69 练习 P136习题5 3 1b c db Page70 练习 P136习题5 3 1b c dc Page71 练习 P136习题5 3 1b c dd Page72 5 5关系代数与Datalog 一般地 可以使用一个或多个Datalog规则来模拟关系代数的运算形式 并且可以模拟非常复杂的运算形式 本节主要研究如何从关系代数的基本运算形式以及连接运算形式转换到Datalog规则 Page73 从集合运算到Datalog规则 交集运算可以使用一个Datalog规则来表示 由于交集运算涉及了两个关系 那么在Datalog规则中 具有与两个关系对应的子目标 在规则中 相应的参数使用相同的变量 假设R和S的关系模式是R A B C 和S A B C 则R S可以使用规则 I a b c R a b c ANDS a b c Page74 并集运算使用两个规则来表示 每个规则对应着一个并集运算中的关系 且两个规则的头部都有相同的IDB谓词 头部的参数与各个子目标中的参数完全相同 假设R和S的关系模式是R A B C 和S A B C 则R S可以使用规则 U x y z R x y z U x y z S x y z 或U a b c S a b c 注意 变量名对于规则是局部的 即每条规则是独立计算的 并且向其头部关系提供元组 与其他规则无关 因此变量名是独立于规则的 Page75 差集运算可以使用具有求反子目标的一个规则来计算 即如果计算两个关系U和V的差集 非求反子目标是谓词U 求反子目标是谓词V 在该规则中 子目标和头部对于相应的参数都有相同的变量 假设R和S的关系模式是R A B C 和S A B C 则R S可以使用规则 D a b c R x y z ANDNOTS x y z Page76 从投影运算到Datalog规则 将关系代数中的投影运算转换成Datalog规则 可以使用一个具有单一子目标的规则 该子目标的参数是不同的变量 每个变量代表关系的一个属性 头部是带有参数的原子 其参数按照期望顺序对应于投影列表的属性 例5 25将关系Movies title year length genre studioName producerC 投影到前三个属性 P t y l Movies t y l g s p Page77 从选择运算到Datalog规则 如果选择条件是一个或多个算术比较表达式的AND运算 可以建立一个具有下列子目标的Datalog规则 一个关系子目标对应于将其进行选择的关系 该关系子目标的每个分量都有不同的变量 且每个分量都对应关系的一个属性 多个算术子目标 每个算术子目标对应选择条件的一个比较运算 虽然在选择条件中使用属性名 但是在算术子目标中却使用相应的变量 并且与关系子目标中建立的变量保持一致 复杂条件可以将逻辑表达式转化成 析取范式 即正负文字的合取的析取 Page78 例5 26 length 100andstudioName Fox Movies S t y l g s p Movies t y l g s p ANDl 100ands Fox 例5 27 length 100orstudioName Fox Movies S t y l g s p Movies t y l g s p ANDl 100S t y l g s p Movies t y l g s p ANDs Fox 例5 28 NOT length 100orstudioName Fox Movies 根据狄摩根定律 等价于 NOT length 100 AND NOT studioName Fox Movies 即 length 100ANDstudioName Fox Movies 再转化为Datalog规则 S t y l g s p Movies t y l g s p ANDl 100ands Fox Page79 从笛卡尔乘积到Datalog规则 R S可以使用单一的Datalog规则来表示 规则包含两个子目标 一个对应R一个对应S 两个子目标有不同的变量分别对应R和S的属性 头部IDB谓词拥有所有在这两个子目标中出现的参数 R子目标中的变量列在S子目标中变量的前面 p a b c x y z R a b c ANDS x y z Page80 从连接运算到Datalog规则 自然连接RS使用一条近似于笛卡尔积的Datalog规则来表示 区别在于R和S的同名属性使用相同的变量 否则使用不同的变量 规则头部是一个IDB谓词 它的每个变量出现一次 假设R和S的关系模式是R A B 和S B C D 则自然连接RS可以用规则J a b c d R a b ANDS b c d Page81 连接先对笛卡尔积进行转化 再对选择条件进行转化 例5 32考虑关系U A B C 和V B C D 其 连接对应的Datalog规则 J a ub uc vb vc d U a ub uc ANDV vb vc d ANDa dANDub vb例5 33J a ub uc vb vc d U a ub uc ANDV vb vc d ANDa dJ a ub uc