第4章 关系运算优秀课件.ppt

第4章 关系运算第1 页，本讲稿共31 页 关系模型有三个重要组成部分：数据结构、数据操纵、数据完整性规则。（1）数据结构：数据库中全部数据及其相互联系都被组织成“关系”（二维表格）的形式。关系模型基本的数据结构是关系。（2）数据操纵：关系模型提供一组完备的高级关系运算，以支持对数据库的各种操作。（3）数据完整性规则：数据库中数据必须满足实体完整性，参照完整性和用户定义的完整性等三类完整性规则。关系数据库的数据操纵语言（DML）的语句分成查询语句和更新语句两大类。查询语句用于描述用户的各种检索要求；更新语句用于描述用户进行插入、删除、修改等操作。关系查询语言根据其理论基础的不同分成两类：（1）关系代数语言：查询操作是以集合操作为基础的运算。（2）关系演算语言：查询操作是以谓词演算为基础的运算。第2 页，本讲稿共31 页4.1 关系代数 4.1.1 关系代数的五个基本操作 关系代数是以关系为运算对象的一组高级运算的集合。由于关系定义为属性个数相同的元组的集合，因此集合代数的操作就可以引入到关系代数中。关系代数中的操作可分为两类：传统的集合操作：并、差、交、笛卡儿积（乘法），笛卡儿积的逆运算（除法）。扩充的关系操作：对关系进行垂直分割（投影）、水平分割（选择）、关系的结合（连接、自然连接）等。1.并（Union）设关系R和S具有相同的关系模式，R和S的并是由属于R或属于S的元组构成的集合，记为R U S。RSttRtS，t是元组变量，R和S的元数相同第3 页，本讲稿共31 页 2.差（Differnece）设关系R和S具有相同的关系模式，R和S的差是由属于R但不属于S的元组构成的集合，记为R S。R-SttR tS 3.笛卡儿积 设关系R和S的元数分别为r和s，定义R和S的笛卡儿积是一个(r+s)元的元组集合，每个元组的前r个分量（属性值）来自R的一个元组，后s个分量来自S的一个元组，记为R S R S t|t=R 4.投影 这个操作是对一个关系进行垂直分割，消去某些列，并重新安排列的顺序。设关系R是k元关系，R在其分量Ai1，Aim上的投影用i1，im（R）表示。它是一个m元的元组的集合 i1,im(R)t|t=R第4 页，本讲稿共31 页 5.选择 选择操作是根据某些条件对关系做水平分割,即选取符合条件的元组.条件可用命题公式F表示。F中有两种成分：运算对象：常数（用引号括起来），元组分量（属性名或列的序号）。运算符：符术比较运算符，逻辑运算符 关系R关于公式F的选择操作用F（R）表示，形式定义如下：F（R）=t|t R F(t)=true 为选择运算符,F（R）表示从R中挑选满足公式F为真的元组所构成的关系。第5 页，本讲稿共31 页4.1.2 关系代数的四个组合操作 1.交(Intersection)关系R和S的交是由属于R又属于S的元组构成的集合，记为RS，要求R和S定义在相同的关系模式上。RSt|tRtS，R和S的元数相同 由于RS=R-（R-S），或RS=S-（S-R），因此交操作不是一个独立的操作。2.连接(Join)连接是从关系R和S的笛卡儿积中选取属性值满足某一操作的元组(P98)3.自然连接(P98)4.除法第6 页，本讲稿共31 页4.1.3 关系代数运算的应用实例 在关系代数运算中，把由五个基本操作经过有限次复合的式子称为关系代数表达式。这种表达式的运算结果仍是一个关系。【例4.5】P100第7 页，本讲稿共31 页4.1.4 关系代数的两个扩充操作 1.外连接 在关系R和S做自然连接时，我们选择两个关系在公共属性上值相等的元组构成新关系的元组。此时，关系R中某些元组有可能在S中不存在公共属性上值相等的元组，造成R中这些元组的值在操作时被舍弃。由于同样的原因，S中某些元组也有可能被舍弃。为了在操作时能保存这些将被舍弃的元组，提出“外连接”操作。如果如果R和S做自然连接时，把原该舍弃的元组也保留在新关系中，那么这种操作称为“左外连接”操作。如果R和S做自然连接时，只把S中原该舍弃的元组放到新关系中，那么这种操作称为“右外连接”操作。第8 页，本讲稿共31 页 2.外部并 如果R和S的关系模式不同，构成的新关系的属性由R和S的所有属性组成，新关系的元组由属于R或属于S的元组构成，同时元组在新增加的属性上填上空值，那么这种操作称为“外部并”操作。第9 页，本讲稿共31 页4.2 关系演算 把数理逻辑的谓词演算引入到关系运算中，就可得到以关系演算为基础的运算。关系演算又可分为元组关系深处和域关系演算，前者以元组为变量，后者以属性（域）为变量分别简称为元组演算和域演算。4.2.1 元组关系演算 在元组关系演算中，元组关系深处表达式简称为元组表达式。其中t是元组变时不时，表示一个元数固定的元组；P是公式，在数理逻辑中也称为谓词，也就是计算机语言中的条件表达式。t|P(t)表示满足公式P的所有元组t的集合。1.原子公式和公式的定义 在元组表达式中，公式由原子公式组成。第10 页，本讲稿共31 页 定义4.1 原子公式有三种形式 P103（1）R（S）。其中R是关系名，S是元组变时不时。它表示了这样一个命题：“S是关系R的一个元组”。（2）Siuj。其中S和U是元组变量，是算术比较去处符，Si和uj分别是S的第i个分量和U的第j个分时不时。Siuj表示命题：“元组S的第i个分量和U的第j个分量之间满足关系”。（3）Sia或auj。a是常量。“Sia”表示命题：“元组S的第i个分量值与常量a之间满足关系”。在定义关系深处操作时，要用到“自由”和“约束”变量概念。在一个公式中，如果元组变量未用存在量词或全称量词符号定义，那么称其为自由元组变量，否则称礤为约束元组变量。约束变量类似于程序设计语言中过程内部定义的局部变量，自由变量类似于过程外部定义的外部变量或全局变量。第1 1 页，本讲稿共31 页 定义4.2 公式的递归定义（1）每个原子是一个公式。其中的元组变量是自由变量。（2）如果P1和P2是公式，那么P1、p1 p2、P1 P2和P1=P2。公式中元组的变量的自由约束性质如同在P1和P2中一样，依然是自由的或约束的。（3）如果P1是公式，那么（S）（P1）和（S）（P1）也都是公式。其中S是公式P1中的自由元组变量；在（S）（P1）和（S）（P1）中称为约束元组变量。（4）公式中各种运算符的优先级从高到低依次为：、=。在公式外还可以加括号，以改变上述优先顺序。（5）公式只能由上述四种形式构成，除此之外构成的都不是公式。第12 页，本讲稿共31 页 在元组关系演算的公式中，有下列三个等价的转换规则：（1）P1P2等价于（P1P2）；P1P2等价于（P1P2）（2）（S）（3）P1=P2等价于P1P2 2.关系代数表达式到元组表达式的转换 P104第13 页，本讲稿共31 页4.2.2 域关系演算 1.域关系演算表达式 域关系演算类似于元组关系演算，不同之处是用域变量代替元组变量的每个分量，域变量的变化范围是某个值域而不是一个关系。原子公式有两种形式：（1）R（X1,Xk),R是一个k元关系，每个Xi是常量或域变量；（2）XY，其中X、Y是常量或域变量，但至少有一个是域变量，是算术比较符。域关系演算的公式中也可使用、=逻辑运算符，也可以用 形成新的公式，但变量X是域变量，不是元组变量。自由域变量、约束域变量等概念和元组演算中一样。域演算表达式是形为：t1tk|P(t1,tk)的表达式，其中P(t1,tk)是关于自由域变量t1tk的公式。第14 页，本讲稿共31 页 2.元组表达式到域表达式的转换（1）对于k元的元组变量t，可引入k个域变量t1tk，在公式中t用t1tk替换，元组分量ti用ti替换。（2）对于每个量词 或，若U是M元的元组变量，则引入M个新的域变量UUm。在量词的辖域内，U用UUm替换，Ui用Ui替换，用 替换。用 替换。第15 页，本讲稿共31 页4.2.3 关系运算的安全约束和等价性 1.关系运算的安全性 在关系代数中基本操作是并、差、笛卡儿积、投影和选择，没有集合的“补”操作。因而关系代数运算总是安全的。关系演算则不然，可能会出现无限关系和无穷验证问题。这些在实际上是行不通的。因为，一方面计算机的存储空间是有限的，不可能存储无限关系。另一方面，在计算机上进行无穷验证是永远得不到结果。所以防止无限关系和无穷验证的出现。定义4.3 在数据库技术中，不产生无限条件和无穷验证的运算称为安全运算，相应的表达式称为安全表达式，所采取的措施称为安全约束。第16 页，本讲稿共31 页 2.关系运算的等价性 并、差、笛卡儿积、投影和选择是关系代数最基本的操作，并构成了关系代数运算的最小完备集。在些基础上，关系代数、安全的元组关系演算、安全的域关系演算在关系的表达和操作能力上是完全等价的。关系运算主要有关系代数、元组演算和域演算三种，相应的关系查询语言也已研制出来，其典型代表为ISBL语言、QUEL语言、QBE语言、SQL语言（介于关系代数和元组演算之间的一种关系查询语言）。第17 页，本讲稿共31 页4.3 关系代数表达式的优化 查询处理的代价通常取决于磁盘访问，磁盘访问比内存访问速度要慢得多。对于一个缎带定的查询，通常会有许多可能的处理策略，也就是可以写出许多等价的关系代数表达式。4.3.1 关系代数表达式的优化问题 在关系代数运算中，笛卡儿积和连接运算是最费时间的，若关系R有m个元组，关系S有n个元组，那么RS就有mn个元组。两个关系代数表达式等价是指用同样的关系实例代替两个表达式中相应关系时所得到的结果是一样的。也不是得到相同的属性集和相同的元组集，但元组中属性的顺序可能不一致。第18 页，本讲稿共31 页4.3.2 关系代数表达式的启发式优化算法 在关系代数表达式中，最花费时间和空间的运算是笛卡儿积和连接操作。为此，引出三条启发式规则，用于对表达式进行转换，以减少中间关系的大小。尽可能早地执行选择操作；尽可能早地执行投影操作；避免直接做笛卡儿积，把笛卡儿积操作之前和之后的一连串选择和投影合并起来一起做。通常选择操作优先于投影操作比较好，因为选择操作可能会大大减少关系，并且选择操作可以利用索引存取元组。关系代数表达式的启发式优化是由DBMS的DML编译器完成的。对一个关系代数表达式进行语法分析，可以得到一棵语法树，树中叶子是关系，非叶子结点是关系代数操作。第19 页，本讲稿共31 页 算法4.1 关系代数表达式的启发式优化算法 输入：一个关系代数表达式的语法树 方法：（1）把每个开式为F1 Fn（E）的子表达式转换成选择级联形式：F1（Fn（E）（2）在语法树中，尽可能把每个选择操作下推到最早可能执行的地方（即移向树的叶端）（3）对每个投影操作，尽可能把投影操作往下推，移向树的叶端。可能使某些投影操作消失，也可以把一个投影分成两个投影操作，其中一个将靠近叶端。如果一个投影是针对被投影的表达式的全部属性，则可消去该投影操作。第20 页，本讲稿共31 页（4）把选择和投影合并成单个选择、单个投影或一个选择后跟一个投影。使多个选择投影能同时执行或在一次扫描中同时完成。（5）每个二元运算结点与其直接祖先（不超过别的二元运算结点）的一元运算结点分为一组。如果它的子孙结点一直到叶都是一元运算符，则也并入该组。但是，如果二元运逄是笛卡儿积，而且后面不是与它组合成等值连接的选择时，则不能将选择与这个二元运算组成同一组。（6）生成一个序列，每一组结点的计算是序列中的一眇，各步的顺序是任意的，只要保证任何一组不会在它的子孙组之前计算即可。第21 页，本讲稿共31 页练习题一、单项选择题1设关系R和S的元组个数分别为100和300，关系T是R与S的笛卡儿积，则T的元组个数是（）A.400 B.10000 C.30000 D.900002设关系R与关系S具有相同的关系模式，则R-（R-S）等于（）A.R S B.RS C.RS D.R-S3在关系代数中，从两个关系的笛卡儿积中，选取它们属性间满足一定条件的元组的操作，称为（）A.投影 B.选择 C.自然连接 D.连接4设关系R和关系S的元数分别是3和4，关系T是R与S的笛卡儿积，即：T=RS，则关系T的元数是（）A.7 B.9 C.12 D.165在关系代数中，自然连接的运算符号为（）A.B.C.D.CBDDA第22 页，本讲稿共31 页6设有关系R，S和T如下。关系T由关系R和S经过（）操作得到。R S TA.R S B.RS C.RS D.RS7查询优化策略中最重要、最基本的一条原则是（）A.投影运算应尽可能先做 B.连接运算应尽可能先做 C.选择运算应尽可能先做 D.把投影运算和选择运算同时进行A B C1 2 34 1 63 2 4A B C4 1 62 7 1A B C1 2 33 2 4BC第23 页，本讲稿共31 页8假定有两个关系R与S，其内容分别为：R关系 S关系则RS的运算结果为（）A B C DA B C1 2 52 5 63 5 4B C D2 5 172 5 95 4 1A B C1 2 51 2 42 5 5A B C D1 2 5 171 2 5 93 5 4 1A B C S.B S.C D1 2 5 2 5 172 5 6 2 5 93 5 4 5 4 1A B C2 5 6A B C1 2 52 5 63 5 4B C D2 5 172 5 95 4 1B第24 页，本讲稿共31 页9.对表进行垂直方向的分割用的运算是（）A.交 B.投影 C.选择 D.连接10当关系R与S做自然连接时，能够把R和S原该舍弃的元组放到结果关系中的操作是（）A.左外连接 B.右外连接 C.外部并 D.外连接11关系笛卡儿积运算记号RS中，（）A.R为关系名，S为属性名 B.R，S均为属性名 C.R为属性名，S为关系名 D.R，S均为关系名12关系模型通常由3部分组成，它们是（）A.数据结构、数据通信、数据操作 B.数据结构、数据操作、完整性规则 C.数据通信、数据操作、完整性规则 D.数据结构、数据通信、完整性规则13如果两个关系没有公共属性，那么其自然连接操作（）A.转化为笛卡儿积操作 B.转化为连接操作 C.转化为外部并操作 D.结果为空关系BDDBA第25 页，本讲稿共31 页二、填空题1关系模型的三个组成部分分别是：、和。2已知关系R，T，试求下列运算结果。R TA R.B T.B Cb c c cA Ba db cf fB Cb bc cb gA B Cb c c数据结构数据操纵数据完整性规则A=C（RT）RT第26 页，本讲稿共31 页3给定两个关系S1，S2 S1 S2求B(C5(S1)S24关系代数中，从两个关系中找出相同元组的运算称为 运算。5关系代数的五个基本操作为：、和。6关系运算分成 和 两类。B C D2 5 73 6 72 5 83 6 9B C2 53 6B C2 53 6B C2 53 6B C2 53 6B C2 53 6B C2 53 6交 并 差 笛卡儿积 投影 选择关系代数 关系演算第27 页，本讲稿共31 页三、计算题1设有关系R和S：R S计算R S、R-S、RS、RS、3，1（S）、C6（R）、RS(2=2)、RS2.设有关系R和S，计算RS、RS(1=1)、3=6（RS）A B C2 4 63 5 74 6 8A C B2 5 74 6 82 5 9A C D2 5 87 4 14 5 83 4 9B C D3 5 84 4 14 1 86 4 1第28 页，本讲稿共31 页四、设计题1设教学数据库中有四个关系：教师关系T（T#，TNAME，TITLE）课程关系C（C#，CNAME，T#）学生关系S（S#，SNAME，AGE，SEX）选课关系SC（S#，C#，SCORE）试用关系代数表达式表示下列查询语句：（1）检索年龄小于17岁的女学生的学号和姓名。（2）检索男学生所学课程的课程号和成绩。（3）检索男学生所学课程的任课教师的工号和姓名。（4）检索至少选修两门课程的学生学号。（5）检索至少有学号为S2和S4学生选修的课程的课程号。（6）检索WANG同学不学的课程的课程号。（7）检索全部学生都选修的课程的课程号和课程名。（8）检索选修课程包含LIU老师所授全部课程的学生学号。第29 页，本讲稿共31 页答案：（1）S#，SNAME（AGE17 SEX=女（S）（2）C#，SCORE（sex=男（SSC）（3）T#，TNAME（sex=男（SSCCT）（4）1（1=4 2 5（SCSC）（5）C#（S#=S2（SC）C#（S#=S4（SC）（6）C#（C）-C#（SNAME=WANG（SSC）（7）c#，CNAME（C（S#，C#（SC）S#（S）（8）S#，C#（SC）C#（TNAME=LIU（CT）第30 页，本讲稿共31 页第4章 结束 谢谢！第31 页，本讲稿共31 页