第4章 关系运算

第4章关系运算学习目的和要求总体要求：深刻理解关系模型的运算理论，了解查询优化的意义和启发式优化算法。熟练掌握：关系代数的基本理论和应用；掌握：关系演算的定义及简单应用；理解：关系代数表达式的优化学习重点：关系代数运算；学习难点：关系演算；第4章关系运算关系模型的三个重要组成部分：数据结构数据操纵数据完整性规则DML可分为：数据查询语句、数据更新语句；关系运算理论是数据查询的理论基础；关系代数：以集合操作为基础的查询；关系演算：以谓词演算为基础的查询；4.1.1关系代数的5个基本操作传统的集合操作：并、差、交、笛卡儿积、笛卡儿积的逆运算；扩充的关系操作：投影、选择；关系代数的基本操作：并、差、笛卡儿积、投影、选择；4.1.1关系代数的5个基本操作1．并(Union)设R和S具有相同的关系模式，R和S的并是由属于R或属于S的元组构成的集合。2．差（Difference）设R和S具有相同的关系模式，R和S的差是由属于R但不属于S的元组构成的集合。4.1.1关系代数的5个基本操作3．笛卡儿积(CartesianProduct)设R和S的元数（属性个数）分别是r和s，R和S的笛卡儿积是一个(r+s)元的元组集合，每个元组的前r个分量（属性值）来自R的一个元组，后s个分量来自s的一个元组。若R有个元组，S有n元组，则R×S有m*n个元组。4.1.1关系代数的5个基本操作4．投影(Projection)设R为k元关系，R在其分量Ai1,…,Aim（m≦k,i1,…,im为1到k的整数）上的投影用∏i1,…,im(R)表示，它是一个m元的组合：该操作实现对关系的垂直分割，消去某些列，并重新安排列的顺序。121110987654321DCBA∏3,1(R)或∏C,A(R)9115713AC4.1.1关系代数的5个基本操作5．选择(Selection)选择是根据条件对关系作水平分割，即选择符合条件的元组。条件用命题公式F表示，F有２种成分：运算对象：常数、元组分量（属性）运算符：比较运算符、逻辑运算符例4.1（P97）4.1.2关系代数的4个组合操作1．交(Intersection)R和S的交是由属于R又属于S的元组构成的集合。由于R∩S=R-R(R-S)或R∩S=S-(S-R)，故交不是独立操作。4.1.2关系代数的4个组合操作2．连接(Join)连接是从R和S的笛卡儿积中选取属性满足某一比较运算操作的元组。由于故连接是由笛卡儿积和选择操作组合而成。例：4.2(P98)4.1.2关系代数的4个组合操作3．自然连接(NaturalJoin)先计算R×S；设R和S的公共属性为A1,…,Ak,挑选R×S中满足R.A1=S.A1,…,R.Ak=S.Ak的元组；去掉S.A1,…,S.Ak这些列，即得到自然连接。其中i1,…,im为Ｒ和S的全部属性。自然连接是去掉重复属性的等值连接。没有公共属性的自然连接转化为笛卡儿积。例4.3(P98)4.1.2关系代数的4个组合操作4．除法(Division)设R和S的元数分别为r和s(r>s>0)，R÷S是一个r-s元的元组的集合，它满足下列条件的最大关系：该集合中每个元组t与S中每个元组u组成的新元组<t,u>必然在关系R中。例4.4(P99)4.1.3关系代数运算的应用实例在关系代数运算中，把由5个操作经过有限次复合的式子称为关系代数表达。关系代数表达式的结果仍为关系。例：设有如下关系：教师T(T#,Tname,Title)课程C(C#,Cname,T#)学生S(S#,Sname,Age,sex)选课SC(S#,C#,Score)请用关系代数表达式实现P100的查询。4.1.4关系代数的两个扩充操作外连接(OuterJoin)若R和S做自然连接时，把原该丢弃的元组也保留在新关系中，同时在这些元组新增加的属性上填空值(Null)，这种操作称“外连接”。只保留R中的元组的操作称“左连接”只保留S中的元组的操作称“右连接”外部并(OuterUnion)对关系模式不同的R和S，外部并所构成的新关系的属性由R和S的所有属性（公共属性只取一次）组成。例：P1024.2关系演算关系演算：元组演算：以元组为变量域演算：以域为变量4.2.1元组关系演算元且表达式的一般形式：{t|P(t)}.t是元组变量，表示一个元数固定的元组，P是公式，也称谓词，即计算机语言中的条件表达式。表示满足公式P的所有元组t的集合。4.2.1元组关系演算1、原子公式和公式的意义在元组表达式，公式由原子公式构成定义：原子公式有下列3种形式：R(s)：s是R的一个元组。

s[i]θu[j]：元组s的第i个分量和元组u的第j个分量满足θ关系。

s[i]θa或aθs[j]：元组s的第i个分量与常数a之间满足θ关系。元组变量未用存在量词或全称量词定义的变量称自由变量，否则称约束变量。4.2.1元组关系演算公式的递归定义：每个原子是一个公式，其元组变量是自由变量。如果P1和P2是公式，那么┑P1、P1∧P２、P1∨P2和P1=>P2也都是公式。如果P1是公式，那么：公式只能由上述4种形式构成。4.2.1元组关系演算例：P103-104321987654CBA321965643CBARS4.2.1元组关系演算等价转换规则4.2.1元组关系演算2、关系代数表达式到元组表达式的转换设R和S为3元关系，则：例4.10(P105)4.2.1元组关系演算例4.11：(P105、P100)有如下关系：教师T(T#,Tname,Title)、课程C(C#,Cname,T#)、学生S(S#,Sname,Age,sex)、选课SC(S#,C#,Score)4.2.2域关系演算域关系演算类似于元组关系演算，用域变量代替元组变量的第一个分量，其变化范围是某个值域。原子公式：R(x,…,xk)，R为k元关系，xi为常量或域变量；Xθj，x,y至少有一个是域变量；也可用逻辑与、或、非，存在量词和全称量词等形成新公式，但此时x是域变量；域演算表达式的一般形式为：

{t1…tk|P(t1,…,tk)}例：P1064.2.2域关系演算元组表达式到域表达式的转换总体思想：用域变量代替相应元组变量或其分量。详细方法见(P106-107)例4.13例4.144.2.3关系运算的安全约束和等价性关系运算的安全性在关系代数中没有集合的“补”操作，因而关系运算总是安全的。关系演算可能出现无限关系和无穷验证问题而不安全；定义：在数据库技术中，不产生无限关系和无穷验证的运算称为安全运算，相应的表达式称为安全表达式，所采取的措施称为安全约束。4.2.3关系运算的安全约束和等价性关系运算的等价性已经证明，基于系代数运算的最小完备集的关系代数、安全的的元组关系演算、安全的域关系演算在关系的表达和操作能力上完全等价的。基于关系运算的关系查询语言已研制成功并广泛使用：ISBL(InformationSystemBaseLanguage)QUEL(QueryLanguage)QBE(QuerybyExample)SQL(StructuredQueryLanguage)4.3关系代数表达式的优化查询处理的代价通常取决于磁盘访问；同一查询有多个等价的关系代数表达式，而不同的查询策略所需的磁盘访问次数差别可能很大；关系代数表达式中需要指出若干关系的操作步骤；查询优化主要解决如何设计查询策略以实现查询代价的最小化（省时、省空间、高效）4.3.1关系代数表达式的优化问题笛卡儿积和连接运算最费时间；例4.15：有关笛卡儿积的优化问题(P109-110)4.3.2启发式优化算法启发式优化(HeuristicOptimization)主要通过合理操作顺序以查询对系统时间和空间的需求，与关系的存储技术无关，是目前最常用的查询优化技术；启发式规则（3条）尽可能早执行选择操作；尽可能早执行投影操作；避免直接做笛卡儿积，把笛卡儿积操作之前和之后的一连串选择和投影合并操作；关系代数表达式的启发式优化由DML编译器完成；4.3.2启发式优化算法启发式优化算法对一个关系代数表达式进行语法分析可得到语法树，树中叶子是关系，非叶结点是关系操作。输入：关系表达式的语法树输出：表达式的优化序列4.3.2启发式优化算法步骤把每个形为δF1∧…∧Fn(E)的子表达式转换成选择级联形式：δF1(…(δFn(E))…)尽可能将选择操作下推到最早可能执行的