关系代数和关系演算重点.ppt

1、第三章关系代数和关系演算,关系模型的形式定义,数据结构关系数据操作关系运算与关系演算完整性规则,关系运算与关系演算,DML分成查询语句（描述用户的各类检索要求）和更新语句（描述用户的增删改等操作）Nonprocedurallanguage关系查询语言根据理论基础的不同分关系代数语言：集合操作,一种抽象的非过程高级查询语言，用对关系的运算来表达查询，非过程性较弱（需指明操作的前后顺序）关系演算语言：谓词演算,非过程性强，操作顺序仅限于量词顺序,3.1关系代数,关系代数运算的三个要素关系代数运算的分类表示记号,关系代数运算的三个要素,运算对象：关系运算结果：关系运算符：四类,关系代数运算的操作符,

2、集合运算符（并、差、交）将关系看成元组的集合运算是从关系的“水平”方向即行的角度来进行专门的关系运算符（笛卡尔积、投影、选择、联接、除）不仅涉及行而且涉及列算术比较符辅助专门的关系运算符进行操作逻辑运算符（与、或、非）辅助专门的关系运算符进行操作,表2.4关系代数运算符,表2.4关系代数运算符（续）,3表示记号,（1）R，tR，tAi设关系模式为R(A1，A2，An)它的一个关系设为R。tR表示t是R的一个元组tAi则表示元组t中相应于属性Ai的一个分量学生（学号，姓名，年龄，政治面貌）R记录（2004A0020306，张晓曦，18，党员）t张晓曦tAi,3表示记号,（2）A，tA，A若A=A

3、i1，Ai2，Aik，其中Ai1，Ai2，Aik是A1，A2，An中的一部分，则A称为属性列或域列。tA=(tAi1，tAi2，tAik)表示元组t在属性列A上诸分量的集合。A则表示A1，A2，An中去掉Ai1，Ai2，Aik后剩余的属性组。,3表示记号,（3）trtsR为n目关系，S为m目关系。trR，tsS，trts称为元组的联接。它是一个n+m列的元组，前n个分量为R中的一个n元组，后m个分量为S中的一个m元组。,3表示记号,4）像集Zx给定一个关系R（X，Z），X和Z为属性组。当tX=x时，x在R中的像集（ImagesSet）为：Zx=tZ|tR，tX=x它表示R中属性组X上值为x的诸

4、元组在Z上分量的集合。,3.1关系代数,概述传统的集合运算专门的关系运算,3.1.1传统的集合运算,并差交,1.并（Union）,R和S具有相同的目n（即两个关系都有n个属性，且次序相同，但属性名可以不同）相应的属性取自同一个域RS仍为n目关系，由属于R或属于S的元组组成RS=t|tRtS,并(续),R,S,RS,2.差（Difference）,R和S具有相同的关系模式，相同的目n相应的属性取自同一个域R-S仍为n目关系，由属于R而不属于S的所有元组组成R-S=t|tRtS,差(续),R,S,R-S,3.交（Intersection）,R和S具有相同的目n相应的属性取自同一个域RS仍为n目关系

5、，由既属于R又属于S的元组组成RS=t|tRtS非基本运算，可由其它运算合成RS=R(R-S）,交(续),R,S,RS,3.1关系代数,概述传统的集合运算专门的关系运算,3.1.2专门的关系运算,广义笛卡尔积选择投影联接除,广义笛卡尔积ExtendedCartesianProduct,Rn目关系，k1个元组Sm目关系，k2个元组RS列：（n+m）列的元组的集合元组的前n列是关系R的一个元组后m列是关系S的一个元组行：k1k2个元组RS=trts|trRtsS,广义笛卡尔积(续),R,S,RS,选择（Selection）,1)选择又称为限制（Restriction）2)选择运算符的含义在关系R中

6、选择满足给定条件的诸元组F(R)=t|tRF(t)=真F：选择条件，是一个逻辑表达式，基本形式为：(X1Y1)(X2Y2)：比较运算符（，或）X1，Y1等：属性名、常量、简单函数；属性名也可以用它的序号来代替；：逻辑运算符（或）：表示任选项：表示上述格式可以重复下去,选择（续）,3)选择运算是从行的角度进行的运算，根据某些条件对关系作水平分割4)举例设有一个学生-课程数据库，包括学生关系Student、课程关系Course和选修关系SC。,选择（续）,(a),Student,E1,E2,E3,E4,选择（续）,(b),Course,选择（续）,(c),SC,例7,例8,选择（续）,例1查询信息

7、系（IS系）全体学生Sdept=IS(Student)或5=IS(Student)结果：,选择（续）,例2查询年龄小于20岁的学生Sage20(Student)或420(Student)结果：,投影（Projection）,1）投影运算符的含义从R中选择出若干属性列组成新的关系A(R)=tA|tRA：R中的属性列,2.投影（Projection）,2）投影操作主要是从列的角度进行运算但投影之后不仅取消了原关系中的某些列，而且还可能取消某些元组（避免重复行）,投影（续）,3)举例例3查询学生的姓名和所在系即求Student关系上学生姓名和所在系两个属性上的投影Sname，Sdept(Studen

8、t)或2，5(Student)结果：,投影（续）,投影（续）,例4查询学生关系Student中都有哪些系Sdept(Student)结果：,3.联接（Join）,1）联接可将两个关系连在一起，形成一个新关系。是笛卡尔积、选择和投影的组合。分成联接和F联接2）联接运算的含义从两个关系的笛卡尔积中选取属性间满足某一操作的元组RS=tr|trtsRtsStrAtsBA和B：分别为R和S上度数相等且可比的属性组：比较运算符联接运算从R和S的广义笛卡尔积RS中选取（R关系）在A属性组上的值与（S关系）在B属性组上值满足比较关系的元组。,F联接,F联接是从关系R和S的笛卡尔积中选择属性间满足某一公式F的元

9、组F是形如F1F2Fn的公式，每个F是形为ij的式子,联接(续),3）两类常用联接运算等值联接（equi-join）什么是等值联接为“”的联接运算称为等值联接等值联接的含义从关系R与S的广义笛卡尔积中选取A、B属性值相等的那些元组，即等值联接为：RS=|trRtsStrA=tsB,A=B,联接(续),自然联接（Naturaljoin）什么是自然联接自然联接是一种特殊的等值联接两个关系中进行比较的分量必须是相同的属性组在结果中把重复的属性列去掉自然联接的含义R和S具有相同的属性组BRS=|trRtsStrB=tsB,自然联接与等值联接的区别,在进行自然联接的两个关系中，要求值相等的属性名也必须相

10、等，而等值连接中不要求值相等的属性名相等在自然联接中，去掉重复的属性名，而在等值连接中不去掉重复的属性名如果两个关系没有公共属性，那么其自然联接就转化为笛卡尔积操作,联接(续),4）一般的联接操作是从行的角度进行运算。自然联接还需要取消重复列，所以是同时从行和列的角度进行运算。,联接(续),5）举例例5,R,S,联接(续),RS,联接(续),等值联接RS,R.B=S.B,联接(续),自然联接RS,4.除（Division）,给定关系R(X，Y)和S(Y，Z)，其中X，Y，Z为属性组。R中的Y与S中的Y可以有不同的属性名，但必须出自相同的域集。R与S的除运算得到一个新的关系P(X)，P是R中满足

11、下列条件的元组在X属性列上的投影：元组在X上分量值x的象集Yx包含S在Y上投影的集合。RS=trX|trRY(S)YxYx：x在R中的象集，x=trX元组针对X上每个分量值xi（可能为多个）求在Y上的像集，如果某个像集包含S在Y上投影，则X的这个分量值xi是RS结果的一个元素,除(续),2）除操作是同时从行和列角度进行运算,书上的例子,R,S,RS,计算过程,T=1,2,r-s(R)W=(TS)RV=1,2,r-s(W)RS=T-V,T=1,2,r-s(R),2.W=(TS)R,计算TS中不在R的元组,3.V=1,2,r-s(W),4.RS=T-V,T,V,RS,象集Z,给定一个关系R（X，Z

12、），X和Z为属性组。当tX=x时，x在R中的象集（ImagesSet）为：Zx=tZ|tR，tX=x它表示R中属性组X上值为x的诸元组在Z上分量的集合。,除(续),R,S,分析：,在关系R中，A可以取四个值a1，a2，a3，a4a1的象集为(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)属性组上的投影所以RS=a1,计算RS的操作步骤,将R中的属性分为两个集合X和Y，其中Y就是S中的全部属性的集合；若

13、X的某个值x的像集Yx=tY|tRtX=x包含S表中的所有元组，则将x放入结果集中。,除(续),R,S,RS,分析,在关系R中，A，B可以取三个值(a,b),(b,c),(e,d)(a,b)的象集为(c,d),(e,f),(b,e)(b,c)的象集为(e,f)(e,d)的象集为(c,d),(e,f)S在(C,D)上的投影为(c,d),(e,f)只有(a,b)和(e,d)的象集包含了S在(B，C)属性组上的投影，所以RS=(a,b),(e,d),5综合举例,以学生-课程数据库为例例7查询至少选修1号课程和3号课程的学生号码首先建立一个临时关系K：然后求：Sno.Cno(SC)K,综合举例(续),

14、例7续Sno.Cno(SC)95001象集1，2，395002象集2，3Cno(K)=1，3于是：Sno.Cno(SC)K=95001,综合举例(续),例8查询选修了2号课程的学生的学号。Sno（Cno=2（SC）95001，95002,关系代数运算的应用举例,设教学数据库中的4个基本关系如下：教师关系T(T#,Tname,Title)课程关系C(C#,Cname,T#)学生关系S(S#,Sname,Age,Gender)选课关系SC(S#,C#,Score),运算举例,学习课程号为C2课程的学生学号与成绩学习课程号为C2课程的学生学号与姓名至少选修Liu老师所授课程中一门课程的学生学号与姓名

15、选修课程号为C2或C4的学生学号至少选修课程号为C2和C4的学生学号不学C2课程的学生姓名与年龄学习全部课程的学生姓名所学课程中包含学生S3所学课程的学生学号,Answer,S#.Score(C#=C2(SC)S#.Sname(C#=C2(SSC)S#.Sname(Tname=Liu(SSCCT)S#.(C#=C2C#=C2(SC)1(1=42=C25=C4(SCSC)Sname,age(S)-Sname,age(C#=C2(SSC)Sname(S(S#,C#(SC)C#(C)S#,C#(SC)C#(S#=S3(SC),关系代数的扩充,为了使关系代数运算能真实的模拟用户的查询，对关系代数操作扩

16、充了以下三种操作：OuterJoinOuterUnionSemijoin,OuterJoin,自然联接时，选择两个关系在公共属性上值相等的元组构成新关系的元组。此时，关系R中某些元组可能在S中不存在公共属性上值相等的元组，造成R中这些元组的值在操作时被舍弃。由于同样的原因，S中某些元组也有可能被舍弃。如果在R和S自然联接时，把原该舍弃的元组也保留在新关系中，同时在这些元组新增加的属性上填上空值，这就是外联接,example,OuterUnion,Union需要R和S具有相同的关系模式，如果R和S的关系模式不同，构成新关系的属性由构成R和S的所有属性组成（公共属性只取一次），新关系的元组由属于R

17、或属于S的元组构成，同时在元组新增加的属性上填上空值,example,小结,关系代数运算关系代数运算并、差、交、笛卡尔积、投影、选择、联接、除基本运算并、差、笛卡尔积、投影、选择交、联接、除可以用5种基本运算来表达引进它们并不增加语言的能力，但可以简化表达,小结(续),l关系代数表达式关系代数运算经有限次复合后形成的式子l典型关系代数语言ISBL（InformationSystemBaseLanguage）由IBMUnitedKingdom研究中心研制用于PRTV（PeterleeRelationalTestVehicle）实验系统,第三章关系代数和查询优化,3.1关系代数3.2关系演算元组关

18、系演算域关系演算关系运算的安全性和等价性关系演算语言,3.2关系演算,关系演算把数理逻辑中的谓词演算引入到关系运算中种类：按谓词变元不同分类1.元组关系演算(TupleRelationalCalculus)：以元组变量作为谓词变元的基本对象元组关系演算语言QUEL2.域关系演算(DomainRelationalCalculus)：以域变量作为谓词变元的基本对象域关系演算语言QBE,TupleRelationalCalulus,元组关系演算表达式简称为元组表达式，一般形式为t|P(t),其中t是元组变量，P是公式，在数理逻辑中也称为谓词，也就是计算机语言中的条件表达式。t|P(t)表示满足公式P

19、的所有元组t的集合。原子公式AtomsR(s),s是关系R的一个元组siuj,元组s的第i个分量和u的第j个分量之间满足关系。sia或auj,a是常量如果有量词修饰，变量为约束变量，否则为自由变量,Formulas,公式Formulas的定义每一个原子是一个公式，其中的元组变量是自由变量如果P1和P2是公式，那么P1,P1P2,P1VP2,P1P2也都是公式如果P1是公式，那么(存在s)(P1),(任意s)(P1)也都是公式公式中各种运算符有优先级的规定攻势只能由上述4种形式构成，除此之外构成的都不是公式,example,R,S,R1=t|S(t)t12,R2=t|R(t)S(t),转换,可以

20、把关系代数表达式等价的转换成元组表达式。由于所有关系代数表达式都能用5种基本操作组合而成，因此只要把5个基本操作用元组演算表达就行,域关系演算,类似于元组关系演算，不同之外是用域变量代替元组变量的每一个分量，域变量的变化范围是某个值域而不是一个关系。可以像元组演算一样定义域演算的原子公式和公式域演算表达式是形为t1.tk|P(t1.,.,tk)的表达式,example,R,S,R1=xyz|R(xyz)x3,R2=xyz|R(xyz)v(S(xyz)y=4),3.2.3关系演算语言,关系代数ISBL元组演算QUEL域演算QBE,域关系演算语言QBE,l一种典型的域关系演算语言由M.M.Zloo

21、f提出1978年在IBM370上得以实现QBE也指此关系数据库管理系统lQBE：QueryByExample基于屏幕表格的查询语言查询要求：以填写表格的方式构造查询用示例元素(域变量)来表示查询结果可能的情况查询结果：以表格形式显示,QBE操作框架,关系名,属性名,操作命令,元组属性值或查询条件或操作命令,一、检索操作,（1）用户提出要求；（2）屏幕显示空白表格；（3）用户在最左边一栏输入要查询的关系名，例如Student；,检索操作（续）,（4）系统显示该关系的属性名（5）用户在上面构造查询要求,检索操作（续）,（6）屏幕显示查询结果,构造查询的几个要素,示例元素即域变量一定要加下划线示例元

22、素是这个域中可能的一个值，它不必是查询结果中的元素打印操作符P.指定查询结果所含属性列查询条件不用加下划线可使用比较运算符，和其中可以省略排序要求,1.简单查询,例1查询全体学生的全部数据。,简单查询（续）,显示全部数据也可以简单地把P.操作符作用在关系名上。,2.条件查询,(1)简单条件例2求信息系全体学生的姓名。,条件查询（续）,例3求年龄大于19岁的学生的学号。,条件查询（与条件）,例4求计算机科学系年龄大于19岁的学生的学号。方法（1）：把两个条件写在同一行上,条件查询（续）,方法（2）：把两个条件写在不同行上，但使用相同的示例元素值,条件查询（续）,例6查询计算机科学系或者年龄大于19岁的学生