关系模型和关系运算理论

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,*,*,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,关系模型和关系运算理论,本章重要概念1,1根本概念,关系模型，关键码主键和外键，关系的定义和性质，三类完整性规那么，过程性语言与非过程性语言。,2关系代数,五个根本操作，四个组合操作，七个扩大操作。,2,本章重要概念2,3关系演算,元组关系演算和域关系演算的原子公式、公式的定义。关系演算的平安性和等价性。,4关系代数表达式的优化,关系代数表达式的等价及等价转换规那么，启化式优化算法。,5关系逻辑,谓词、原子、规那么和查询，规那么的平安性，用规那么模拟关系代数表达式。,3,本章概要,本章先介绍关系模型的根本概念；然后介绍关系运算的三种理论：关系代数、关系演算和关系逻辑。,4,关系模型和关系运算理论,2.1 关系模型的根本概念,2.2 关系代数,2.3 关系演算,2.4 关系代数表达式的优化,2.5 关系逻辑,2.6 小结,5,2.1 关系模型的根本概念,2.1.1 根本术语,2.1.2 关系的定义和性质,2.1.3 关系模型的三类完整性规那么,2.1.4 关系模型的三级体系构造,2.1.5 关系模型的形式定义和优点,2.1.6 关系查询语言和关系运算,返回,6,2.1.1 根本术语(1),定义2.1 用二维表格表示实体集，用关键码表示实体之间联系的数据模型称为关系模型Relational Model。,图2.1 学生登记表,学号,姓名,年龄,性别,籍贯,S1,WANG,20,M,北京,S4,LIU,18,F,山东,S2,HU,17,M,上海,S3,XIA,19,F,四川,7,2.1.1 根本术语(2),在关系模型中，字段称为属性，字段值称为属性值，记录类型称为关系模式。在图2.1中，关系模式名是R。记录称为元组tuple，元组的集合称为关系relation或实例instance。一般用大写字母A、B、C、 表示单个属性，用大写字母 、X、Y、Z表示属性集，用小写字母表示属性值，有时也习惯称呼关系为表或表格，元组为行(row)，属性为列(column)。,关系中属性个数称为“元数arity，元组个数为“基数(cardinality)。,8,2.1.1 根本术语(3),关系元数为5，基数为4。,一般术语,关系模型术语,字段、数据项属性,记录类型关系模式,记录1元组1,记录2元组2,记录3元组3,记录4元组4,字段值属性值,图2.2 关系模型的术语,文,件,关,系,9,2.1.1 根本术语(4),关键码(key,简称键)由一个或多个属性组成。在实际使用中，有以下几种键。,1超键Super Key,2候选键Candidate Key,3主键(Primary Key),在图2.1中，工号，姓名是模式的一个超键，但不是候选键，而工号是候选键。在实际使用中，如果选择工号作为删除或查找元组的标志，那么称工号是主键。,4外键Foreign Key,返回,10,2.1.2 关系的定义和性质,定义2.2 关系是一个属性数目一样的元组的 集合。,在关系模型中，对关系作了以下标准性限制：,1关系中每一个属性值都是不可分解的；,2关系中不允许出现重复元组,即不允许出现一样的元组；,3由于关系是一个集合，因此不考虑元组间的顺序，即没有行序；,4元组中的属性在理论上也是无序的，,但使用时按习惯考虑列的顺序。,返回,11,2.1.3 关系模型的完整性规那么(1),实体完整性规那么entity integrity rule,要求关系中元组在组成主键的属性上不能有空值。如果出现空值，那么主键值就起不了惟一标识元组的作用。,12,2.1.3 关系模型的完整性规那么 (2),参照完整性规那么reference integrity rule,定义2.3 参照完整性规那么的形式定义如下：,如果属性集K是关系模式R1的主键，K也是关系模式R2的外键，那么在R2的关系中，K的取值只允许两种可能，或者为空值，或者等于R1关系中某个主键值。,这条规那么的实质是“不允许引用不存在的实体。,在上述形式定义中，关系模式R1的关系称为“参照关系，关系模式R2的关系称为“依赖关系。“主表和“副表，“父表和“子表。,13,2.1.3 关系模型的完整性规那么 (3),这条规那么在具体使用时，有三点变通：, 外键和相应的主键可以不同名，,只要定义在一样值域上即可；, R1和R2也可以是同一个关系模式，此时表示了同一个关系中不同元组之间的联系；, 外键值是否允许空，应视具体问题而定。,14,2.1.3 关系模型的完整性规那么 (4),例 下面各种情况说明了参照完整性规那么在关系中如何实现的。, 在关系数据库中有以下两个关系模式：,SS#，SNAME，AGE，SEX,SCS#，C#，SCORE,这里带 线者为主键，带 线者为外键。据规那么要求关系SC中的S#值应该在关系S中出现。如果关系SC中有一个元组S7,C4,80，而学号S7却在关系S中找不到，那么我们就认为在关系SC中引用了一个不存在的学生实体，这就违反了参照完整性规那么。,另外，在关系SC中S# 不仅是外键，也是主键的一局部，因此这里S# 值不允许空。,15,2.1.3 关系模型的完整性规那么 (5), 设工厂数据库中有两个关系模式：,DEPT(D#，DNAME),EMP(E#，ENAME，SALARY，D# ),车间模式DEPT的属性为车间编号、车间名，职工模式EMP的属性为工号、姓名、工资、所在车间的编号。每个模式的主键与外键已标出。在EMP中，由于D# 不在主键中，因此D# 值允许空。,16,2.1.3 关系模型的完整性规那么 (6), 设课程之间有先修、后继连系。模式如下：,RC#，CNAME，PC#,其属性表示课程号、课程名、先修课的课程号。如果规定，每门课程的直接先修课只有一门，那么模式R的主键是C#，外键是PC#.。这里参照完整性在一个模式中实现。即每门课程的直接先修课必须在关系中出现。,17,2.1.3 关系模型的完整性规那么 (7),例2.1 TEACHERT#，TNAME，TITLE,COURSE C#，CNAME，T#,STUDENTS#，SNAME，AGE，SEX,SC S#，C#，SCORE,TEACHER(T#,TNAME,TITLE),COURSE(C#,CNAME,T#),STUDENT(S#,SNAME,AGE,SEX),SC(S#,C#,SCORE),图2.3 关系模型的数据构造图DSD,18,2.1.3 关系模型的完整性规那么 (8),用户定义的完整性规那么,在建立关系模式时，对属性定义了数据类型，即使这样可能还满足不了用户的需求。此时，用户可以针对具体的数据约束，设置完整性规那么，由系统来检验实施，以使用统一的方法处理它们，不再由应用程序承担这项工作。,例如学生的年龄定义为两位整数，范围还太大，我们可以写如下规那么把年龄限制在1530岁之间：,CHECKAGE BETWEEN 15 AND 30,返回,19,2.1.4 关系模型的三层体系构造 - 关系模式,在关系模型中，记录类型称为关系模式，而关系模式的集合就是数据库的概念模式。在系统实现时，关系模式和属性的命名一般都用英文单词。,TEACHERT#，TNAME，TITLE,COURSE C#，CNAME，T#,STUDENTS#，SNAME，AGE，SEX,SC S#，C#，SCORE,20,2.1.4 关系模型的三层体系构造 -子模式1,子模式是用户所用到的那局部数据的描述。除此之外，还应指出数据与关系模式中相应数据的连系。例如，用户需要用到子模式G图2.3。,成绩子模式 G(S#，SNAME，C#，SCORE),21,2.1.4 关系模型的三层体系构造 -子模式2,80,G,S#,SNAME,C#,SCORE,S256,Wang,C5,80,S,S#,SNAME,AGE,SEX,S256,Wang,21,F,SC,S#,C#,SCORE,S256,C5,80,22,2.1.4 关系模型的三层体系构造 -存储模式1,图2.6 关系STUDENT和SC的环构造,在有些DBMS中，关系存储是作为文件对待的，每个元组就是一个记录。由于关系模式有键，因此存储一个关系可用散列方法或索引方法实现。如果关系的元组数目较少100个以内，那么也可以用“堆文件方式实现即没有特定的次序。此外，还可对任意的属性集建立辅助索引。,关系STUDENT,S#,SNAME,AGE,SEX,PTR,S1,WANG,20,M,S2,HU,17,M,S3,XIA,19,F,S4,LIU,18,F,关系SC,PTR,S#,C#,SCORE,S1,C1,80,S2,C1,85,S1,C2,60,S2,C2,75,S1,C3,70,S4,C4,90,23,2.1.4 关系模型的三层体系构造 -存储模式2,图2.7,两个关系存储在一起,S1,WANG,20,M,S1,C1,80,S1,C2,60,S1,C3,70,S2,HU,17,M,S2,C1,85,S2,C2,75,S3,XIA,19,F,S4,LIU,20,F,S4,C4,90,24,2.1.5 关系模型的形式定义,关系模型有三个重要组成局部：数据构造，数据操纵，数据完整性规那么。,1数据构造：数据库中全部数据及其相互连系都被组织成“关系二维表格的形式。关系模型根本的数据构造是关系。,2数据操纵：关系模型提供一组完备的高级关系运算，以支持对数据库的各种操作。关系运算分成关系代数、关系演算和关系逻辑等三类。,3数据完整性规那么：数据库中数据必须满足实体完整性，参照完整性和用户定义的完整性等三类完整性规那么。,25,2.1.5 关系模型的优点,与其它数据模型相比，关系模型突出的优点如下：,1关系模型提供单一的数据构造形式，具有高度的简明性和准确性。,2关系模型的逻辑构造和相应的操作完全独立于数据存储方式，具有高度的数据独立性。,3关系模型使数据库的研究建立在比较坚实的数学根底上。,4关系数据库语言与一阶谓词逻辑的固有内在连系，为以关系数据库为根底的推理系统和知识库系统的研究提供了方便。,26,2.1.6 关系查询语言和关系运算,关系数据库的数据操纵语言DML的语句分成查询语句和更新语句两大类。查询语句用于描述用户的各种检索要求；更新语句用于描述用户进展插入、删除、修改等操作。关于查询的理论称为“关系运算理论。,关系查询语言根据其理论根底的不同分成三类：,1关系代数语言。,2关系演算语言。,3关系逻辑语言。,27,2.2 关系代数,2.2.1 关系代数的五个根本操作,2.2.2 关系代数的四个组合操作,2.2.3 关系代数运算的应用实例,2.2.4 关系代数的七个扩大操作,返回,28,2.2.1 关系代数的五个根本操作 (1),并Union,设关系R和S具有一样的关系模式，R和S的并是由,属于R或属于S的元组构成的集合，记为RS。,形式定义如下：,RSt | tR tS，,t是元组变量，R和S的元数一样。,差Difference,设关系R和S具有一样的关系模式，R和S的差是由,属于R但不属于S的元组构成的集合，记为RS。形式定义如下：,RS t | tR tS，R和S的元数一样。,29,2.2.1 关系代数的五个根本操作 (2),笛卡尔积Cartesian Product,形式定义如下：,RSt|ttrRtsS,此处tr、ts中r，s为上标。假设R有m个元组，S有n个元组，那么RS有mn个元组。,30,2.2.1 关系代数的五个根本操作 (3),投影Projection对关系进展垂直分割,形式定义如下：,i1，imR,t|tti1，timt1，tkR,例如，3，1R表示新关系中第1列为R的第3列，新关系的第2列为R的第1列。如果R的每列标上属性名，那么操作符的下标处也可以用属性名表示。例如，关系RA，B，C，,那么C，AR与3，1R是等价的。,31,2.2.1 关系代数的五个根本操作 (4),选择Selection据条件对关系做水平分割,形式定义如下：,FR t | tR Ft= true ,例如，23R表示从R中挑选第2个分量值大于3的元组所构成的关系。书写时，为了与属性序号区别起见，常量用引号括起来，而属性序号或属性名不要用引号括起来。,32,(例),例2.2 有两个关系R和S：,（a）关系R,（b）关系S,A,B,C,A,B,C,1,2,3,2,4,6,4,5,6,4,5,6,7,8,9,33,(例),A,B,C,A,B,C,R.A,R.B,R.C,S.A,S.B,S.C,C,A,A,B,C,1,2,3,1,2,3,1,2,3,2,4,6,3,1,4,5,6,4,5,6,7,8,9,1,2,3,4,5,6,6,4,7,8,9,7,8,9,4,5,6,2,4,6,9,7,2,4,6,4,5,6,4,5,6,7,8,9,2,4,6,7,8,9,4,5,6,a b c d e,RS RS RS C，AR B4R,34,2.2.2 关系代数的四个组合操作,(1),交intersection,关系R和S的交是由属于R又属于S的元组构成的集合，记为RS，这里要求R和S定义在一样的关系模式上。形式定义如下：,RSttR tS，R和S的元数一样。,由于RS = R-R-S，或RS = S-S-R，因此交操作不是一个独立的操作。,在表2.3中，RS的结果是只有一个元组,4，5，6。,35,2.2.2 关系代数的四个组合操作,(2),连接join连接 ,R Stt=trRtsStritsj,定义等价于下式：,R Si(r+j)(RS),该式表示连接是在关系R和S的笛卡儿积中挑选第i个分量和第r+j个分量满足操作的元组。,ij,ij,36,2.2.2 关系代数的四个组合操作,(3),A,B,C,D,E,A,B,C,D,E,1,2,3,2,4,1,2,3,2,4,4,5,6,5,6,4,5,6,5,6,7,2,9,7,8,7,2,9,2,4,(a)关系R (b)关系S (c) R,S,2=1,图2.10 连接的例子,R S,2=4,(RS),2=1,37,2.2.2 关系代数的四个组合操作,(4),自然连接natural join,关系R和S的自然连接操作计算过程如下：,R S 去掉S中的公共属性(公共属性上值相等(RS),A,B,C,B,C,D,A,B,C,D,2,4,6,5,7,3,2,4,6,2,3,5,7,4,6,2,3,5,7,3,7,4,6,5,7,9,3,5,7,9,7,4,6,2,a关系R b关系ScR S,R,S,A,R.B,R.C,D,(RS),38,2.2.2 关系代数的四个组合操作,(5),除法division,设关系R和S的元数分别为r和s设rs0，那么RS是一个r-s元的元组的集合。RS是满足以下条件的最大关系：其中每个元组t与S中每个元组u组成的新元组必在关系R中。,RS1，2，r-s(R),1，2，r-s(1，2，r-s(R)S)-R),39,R,S#,SNAME,C#,CNAME,COURSE1,C#,CNAME,RCOURSE1,S#,SNAME,S1,BAO,C1,DB,C2,OS,S1,BAO,S1,BAO,C2,OS,S2,GU,S1,BAO,C3,DS,COURSE2,C#,CNAME,S3,AN,S1,BAO,C4,MIS,C2,OS,S4,LI,S2,GU,C1,DB,C4,MIS,S2,GU,C2,OS,RCOURSE2,S#,SNAME,S3,AN,C2,OS,COURSE3,C#,CNAME,S1,BAO,S4,LI,C2,OS,C1,DB,S4,LI,S4,LI,C4,MIS,C2,OS,C4,MIS,RCOURSE 3,S#,SNAME,S1,BAO,表2.7 除法操作的例子,40,象集Z,给定一个关系RX，Z，X和Z为属性组。当tX=x时，x在R中的象集Images Set为：,Zx=tZ|t R，tX=x,它表示R中属性组X上值为x的诸元组在Z上分量的集合。,41,除Division,给定关系R (X，Y) 和S (Y，Z)，其中X，Y，Z为属性组。,R中的Y与S中的Y可以有不同的属性名，但必须出自一样,的域集。R与S的除运算得到一个新的关系P(X)，P是R中,满足以下条件的元组在X属性列上的投影：元组在X上分,量值x的象集Yx包含S在Y上投影的集合。,RS = tr X | tr RY (S) Yx ,Yx：x在R中的象集，x = trX,42,除(续),A,B,C,a,1,b,1,c,2,a,2,b,3,c,7,a,3,b,4,c,6,a,1,b,2,c,3,a,4,b,6,c,6,a,2,b,2,c,3,a,1,b,2,c,1,B,C,D,b,1,c,2,d,1,b,2,c,1,d,1,b,2,c,3,d,2,R,S,A,a,1,R,S,43,除法举例,在关系R中，A可以取四个值a1，a2，a3，a4,a,1,的象集为 (,b,1,，,c,2,)，(,b,2,，,c,3,)，(,b,2,，,c,1,),a,2,的象集为 (,b,3,，,c,7,)，(,b,2,，,c,3,),a,3,的象集为 ,(b,4,，,c,6,),a,4,的象集为 (,b,6,，,c,6,),S,在(,B,，,C,)上的投影为,(b1，c2)，(b2，c1)，(b2，c3) ,只有,a,1,的象集包含了,S,在(,B,，,C,)属性组上的投影,所以,R,S,=,a,1,44,2.2.3 关系代数运算的应用实例,在关系代数运算中，把由五个根本操作经过有限次复合的式子称为关系代数表达式。这种表达式的运算结果仍是一个关系。我们可以用关系代数表达式表示各种数据查询操作。,例2.6 设教学数据库中有四个关系：,教师关系 TT#，TNAME，TITLE,课程关系CC#，CNAME，T#,学生关系SS#，SNAME，AGE，SEX,选课关系SCS#，C#，SCORE,45,SS#，SNAME，AGE，SEX SCS#，C#，SCORE,检索学习课程号为C2课程的学生学号与成绩。,S#，SCOREC#=C2SC,表达式中也可以不写属性名，而写上属性的序号：1，32=C2SC, 检索学习课程号为C2的学生学号与姓名。,S#，SNAMEC#=C2S SC,由于这个查询涉及到两个关系S与SC，因此先要对这两个关系进展自然连接操作，然后再执行选择和投影操作。,46,T(T#,TNAME,TITLE) S(S#,SNAME,AGE,SEX),C(C#,CNAME,T#) SC(S#,C#,SCORE),检索至少选修LIU教师所授课程中一门课程的学生学号与姓名。,S#，SNAMETNAME=LIUS SC C T, 检索选修课程号为C2或C4的学生学号。,S#C#=C2C#=C4SC, 检索至少选修课程号为C2和C4的学生学号。,11=42=C25=C4SCSC,这里SCSC表示关系SC自身相乘的笛卡尔积操作。,47,SS#，SNAME，AGE，SEX SCS#，C#，SCORE, 检索不学C2课的学生姓名与年龄。,SNAME，AGE,(S),SNAME，AGE,(,C#=C2,(S SC),这里要用到集合差操作。先求出全体学生的,姓名和年龄，再求出学了C2课的学生的姓名,和年龄，最后执行两个集合的差操作。,SNAME，AGE,(,C#C2,(S,SC),48,SS#，SNAME，AGE，SEXSCS#，C#，SCORECC#，CNAME，TEACHER, 检索学习全部课程的学生姓名。,编写这个查询语句的关系代数表达式过程如下：,学生选课情况可用操作,S#，C#,(SC)表示；,全部课程可用操作,C#,(C) 表示；,学了全部课程的学生学号可用除法操作表示，操作结果是学号S#集：,S#，C#,(SC),C#,(C),从S#求学生姓名SNAME，可以用自然联接和投影操作组合而成：,SNAME,(S (,S#，C#,(SC),C#,(C),49,SCS#，C#，SCORE, 检索所学课程包含学生S3所学课程的学生学号。,学生选课情况可用操作,S#，C#,(SC)表示；,学生S3所学课程可用操作,C#,(,S#=S3,(SC) 表示；,所学课程包含学生S3所学课程的学生学号，可以用除法操作求得：,S#，C#,(SC),C#,(,S#=S3,(SC),50,2.2.3 关系代数运算的应用实例,查询语句的关系代数表达式的一般形式是：,RS,或者 R S,但是当查询涉及到否认或全部值时，上述形式就不能表达了，就要用到差操作或除法操作，在例2.6中的、说明了这点。,51,2.2.4 七个扩大操作1,改名,广义投影,赋值,外连接outer join,外部并outer union,半连接semijoin,聚集操作,52,2.2.4 七个扩大操作2,1改名：可改变关系的命名和属性的命名。,例2.7 设关系RA，B和SB，C，D，那么RS的属性应写成A、R.B、S.B、C、D。使用改名操作后，RS可写成RS(X，C，D)S，那么其属性为A、B、X、C、D，更为清晰。, 设关系RA，B和SC，D，那么R和S在B、C上自然连接要写成A，B，DR S,或A，B，DB=CRS。,使用改名操作后，可写成R S(B，D)S形式。,B=C,53,2.2.4 七个扩大操作3,2广义投影：允许在投影列表中使用算术函数来对投影进展扩展，,其形式是F1, F2,FnR，,这里R是任意的关系模式，F1、 F2、Fn是涉及R模式中常量和属性的算术表达式。,例2.8 在选课关系SCS#，C#，SCORE中，课程号为C4的成绩应增加5%，那么可用下式表示：,C#=C4SC,54,2.2.4 七个扩大操作4,3赋值：通过给临时变量赋值，可以把关系代数表达式分开书写，以便把复杂的表达式化整为零，成为简单的表达式。,赋值运算符是“，类似于计算机语言中的赋值运算符。,例2.9 关系R和S的除法操作，可用下面的一串操作表示出来：,TEMP1 1，2，r-sR,TEMP2 TEMP1SR,TEMP3 1，2，r-sTEMP2,RS TEMP1TEMP3,55,2.2.4 七个扩大操作5,4外连接Outer Join,如果R和S做自然连接时，把原该舍弃的元组也保存在新关系中，同时在这些元组新增加的属性上填上空值null，这种操作称为“外连接操作，用符号R S表示。,如果R和S做自然连接时，只把R中原该舍弃的元组放到新关系中，那么这种操作称为“左外连接操作，用符号R S表示。,如果R和S做自然连接时，只把S中原该舍弃的元组放到新关系中，那么这种操作称为“右外连接操作，用符号R S表示。,56,2.2.4 七个扩大操作6,A,B,C,B,C,D,A,B,C,D,A,B,C,D,a,b,c,b,c,d,a,b,c,d,a,b,c,d,b,b,f,b,c,e,a,b,c,e,a,b,c,e,c,a,d,a,d,b,c,a,d,b,c,a,d,b,e,f,g,b,b,f,null,null,e,f,g,A,B,C,D,A,B,C,D,a,b,c,d,a,b,c,d,a,b,c,e,a,b,c,e,c,a,d,b,c,a,d,b,b,b,f,null,null,e,f,g,(a)关系R (b)关系S (c)R,S (d)R S,（e）R S,（f）R S,57,2.2.4 七个扩大操作7,5外部并Outer Union,前面定义两个关系的并操作时，要求R和S具有一样的关系模式。如果R和S的关系模式不同，构成的新关系的属性由R和S的所有属性组成公共属性只取一次，新关系的元组由属于R或属于S的元组构成，同时元组在新增加的属性上填上空值，那么这种操作称为“外部并操作。,58,2.2.4 七个扩大操作8,A,B,C,B,C,D,A,B,C,D,a,b,c,b,c,d,a,b,c,null,b,b,f,b,c,e,b,b,f,null,c,a,d,a,d,b,c,a,d,null,e,f,g,null,b,c,d,null,b,c,e,null,a,d,b,null,e,f,g,(a)关系R(b)关系S (c) R和S的,外部并,59,2.2.4 七个扩大操作9,6 半连接semijoin,R S RR S,或R S R RSS。,显然，半连接的交换律是不成立的，,即 R S S R。,半连接操作主要用于分布式数据库中。,60,2.2.4 七个扩大操作10,R S RR S,A,B,C,B,C,D,A,B,C,D,A,B,C,B,C,D,a,b,c,b,c,d,a,b,c,d,a,b,c,b,c,d,d,b,c,b,c,e,a,b,c,e,d,b,c,b,c,e,b,b,f,a,d,b,d,b,c,d,c,a,d,a,d,b,c,a,d,d,b,c,e,c,a,d,b,(a)关系R (b)关系S (c) R S (d)R S (e)R S,61,2.2.4 七个扩大操作11,7聚集操作：聚集操作是指输入一个值的集合，然后根据该值集合得到一个单一的值作为结果。 聚集函数有max、min、avg、sum和count等。,例2.14 在SS#，SNAME，AGE，SEX中，,求男同学的平均年龄，可以用式子,avgagesex=MS,表示，求年龄为18岁的人数可用式子,countS#age=18S,表示。,62,关系代数习题,1. 设有如下关系：,学生学号，姓名，性别，专业，出生日期,教师教师编号，姓名，所在部门，职称,授课教师编号，学号，课程编号，课程名称，教材，学分，成绩,1查找学习“数据库原理课程且成绩不及格的学生学号和任课教师编号；,2查找学习“英语课程的“计算机应用专业学生的学号、姓名和成绩。,2. 设有如下关系：,SS#,SNAME,AGE,SEX/*学生学号，姓名，年龄，性别*/,CC#,CNAME,TEACHER/*课程课程号，课程名，任课教师*/,SCS#,C#,GRADE/*成绩学号，课程号，成绩*/,查询：,教师“程军所授课程的课程号和课程名；,“李强同学不学课程的课程号；,至少选修了课程号为k1和k5的学生学号；,选修课程包含学号为2的学生所修课程的学生学号。,63,2.3 关系演算,把数理逻辑的谓词演算引入到关系运算中，就可得到以关系演算为根底的运算。关系演算又可分为元组关系演算和域关系演算，前者以元组为变量，后者以属性域为变量。,2.3.1 元组关系演算,2.3.2 域关系演算,2.3.3 关系运算的平安约束和等价性,64,2.3.1 元组关系演算,(1),在元组关系演算Tuple Relational Calculus中，元组关系演算表达式简称为元组表达式，其一般形式为, t | Pt,其中，t是元组变量，表示一个元数固定的元组；P是公式，在数理逻辑中也称为谓词，也就是计算机语言中的条件表达式。 t | Pt表示满足公式P的所有元组t的集合。,65,2.3.1 元组关系演算,(2),在元组表达式中，公式由原子公式组成。,定义2.4 原子公式Atoms有以下三种形式：, Rs, siuj, sia或auj。,在定义关系演算操作时，要用到“自由Free和“约束Bound变量概念。在一个公式中，如果元组变量未用存在量词或全称量词符号定义，那么称为自由元组变量，否那么称为约束元组变量。,66,2.3.1 元组关系演算,(3),定义2.5 公式Formulas的递归定义如下：,每个原子是一个公式。其中的元组变量是自由变量。, 如果P1和P2是公式，那么P1、P1P2、P1P2和P1P2也都是公式。, 如果P1是公式，那么sP1和sP1也都是公式。, 公式中各种运算符的优先级从高到低依次为：，和，和，。在公式外还可以加括号，以改变上述优先顺序。, 公式只能由上述四种形式构成，除此之外构成的都不是公式。,67,2.3.1 元组关系演算,(4),例2.15 图2.16的a、b是关系R和S，cg分别是下面五个元组表达式的值：,图2.20 元组关系演算的例子,R1=t|S(t)t12,R2=t|R(t)S(t),R3=t|(,u)(S(t)R(u)t3u1),R5=t|(,u)(,v)(R(u)S(v),u1v2t1=u2,t2=v3t3=u1),68,2.3.1 元组关系演算,(5),在元组关系演算的公式中，有以下三个等价的转换规那么：, P1P2 等价于 (P1P2)；,P1P2 等价于 (P1P2)。, (s)(P1(s) 等价于 (s)(P1(s)；,(s)(P1(s) 等价于 (s)(P1(s)。, P1P2 等价于 P1P2。,69,2.3.1 元组关系演算,(6),关系代数表达式到元组表达式的转换,例2.16,RS可用 t | RtSt表示；,R-S可用 t | RtSt 表示；,RS可用 t |uvRuS(V) t1=u1 t2=u2t3=u3t4=v1 t5=v2 t6=v3 表示。,设投影操作是2,3R，那么元组表达式可写成：, t |(u)Rutl=u2t2=u3,FR可用 t |R(t)F表示，F是F的等价表示形式。譬如2=dR可写成 t |Rtt2=d。,70,例2.17 设关系R和S都是二元关系，1,42=3RS, RS：,t|(u)(v)(R(u)S(v)t1=u1t2=u2 t3=v1t4=v2), 2=3RS:,在上述表达式的公式中加上“t2=t3即可。, 1,42=3RS:,w|(t)(u)(v)(R(u)S(v)t1=u1t2=u2 t3=v1t4=v2t2=t3,w1=t1w2=t4), 再对上式化简，去掉元组变量t，可得下式：,w|(u)(v)(R(u)S(v),u2=v1w1=u1w2=v2),71,例2.18 对于例2.6中查询语句的关系代数表达式形式也可以用元组表达式形式表示：, 检索学习课程号为C2的学生学号与成绩。,S#，GRADEC#=C2SC,t|(u)(SC(u)u2=C2tl=u1,t2=u3), 检索学习课程号为C2的学生学号与姓名。,S#，SNAMEC#=C2S SC,t|(u)(v)(S(u)SC(v)v2=C2,ul=v1tl=u1t2=u2),72,例2.18 对于例2.6中查询语句的关系代数表达式形式也可以用元组表达式形式表示：, 检索至少选修LIU教师所授课程中一门课程的学生学号与姓名。,S#，SNAMECNAME=MATHSS SC C T,t|(u)(v)(w)(x)S(u)SC(v)C(w)T(x),ul=v1v2=w1w3=x1,x2=LIUtl=u1t2=u2, 检索选修课程号为C2或C4的学生学号。,S#C#=C2C#=C4SC,t|(u)(SC(u)(u2=C2u2=C4),tl=u1),73,例2.18 对于例2.6中查询语句的关系代数表达式形式也可以用元组表达式形式表示：, 检索至少选修课程号为C2和C4的学生学号。,11=42=C25=C4SCSC,t|(u)(v)(SC(u)SC(v)u2=C2,v2=C4ul=v1tl=u1), 检索不学C2课的学生姓名与年龄。,SNAME，AGESSNAME，AGEC#=C2S SC,t|(u)(v)(S(u)SC(v),(ul=v1v2C2),t1=u2t2=u3),74,例2.18 对于例2.6中查询语句的关系代数表达式形式也可以用元组表达式形式表示：, 检索学习全部课程的学生姓名。,SNAMES S#，C#SCC#C,t|(u)(v)(w)(S(u)C(v)SC(w),ul=w1v1=w2t1=u2), 检索所学课程包含学号S3所学课程的学生。,S#，C#SCC#S#=S3SC,t|(u)(SC(u)(v)(SC(v),(v1=S3 (w)(SC(w)w1=u1w2=v2),tl=u1),75,2.3.2 域关系演算,(1),原子公式有两种形式：, Rx1xk；, xy。,公式中也可使用、和等逻辑运算符,(x)和x，但变量x是域变量，不是元组变量。,自由域变量、约束域变量等概念和元组演算中一样。,域演算表达式是形为,t1tkPt1，tk,的表达式，其中Pt1，tk是关于自由域变量t1，tk 的公式。,76,2.3.2 域关系演算,(2),例2.19 图2.17的a、b、c是三个关系R、S、W，d、e、f分别表示下面三个域表达式的值。,(a)关系R (b)关系S (c)关系W (d)R1 (e)R2 (f)R3,图,2.17,域关系演算的例子,R1=xyz|R(xyz)x3,R2=xyz|R(xyz)(S(xyz)y=4),R3=xyz|(,u)(,v)(R(zxu)w(yv)uv),77,2.3.2 域关系演算,(3),元组表达式到域表达式的转换,我们可以很容易地把元组表达式转换成域表达式，转换规那么如下：, 对于k元的元组变量t，可引入k个域变量t1tk，在公式中t用t1tk替换，元组分量ti用ti替换。, 对于每个量词u或u，假设u是m元的元组变量，那么引入m个新的域变量u1um。,在量词的辖域内，u用u1um替换，ui用ui替换，u用u1um替换，u用u1um替换。,78,例2.20 设关系R和S都是二元关系，1,42=3RS,例2.17 转换成的元组表达式是：,w|(,u)(,v)(R(u)S(v)u2=v1,w1=u1w2=v2),再转换成域表达式：,w,1,w,2,|(,u,1,)(,u,2,)(,v,1,)(,v,2,)(R(u,1,u,2,)S(v,1,v,2,),u,2,=v,1,w,1,=u,1,w,2,=v,2,),再进一步简化，可消去域变量u,1,、v,1,、v,2,，得到下式：,w,1,w,2,|(,u,2,)(R(w,1,u,2,)S(u,2,w,2,),79,例2.21 对于例2.6、例2.18的查询，可转换成以下域表达式：, 检索学习课程号为C2的学生学号与成绩。,t,1,t,2,|(,u,1,)(,u,2,)(,u,3,)(SC(u,1,u,2,u,3,)u,2,=C2,t,1,=u,1,t,2,=u,3,),可化简为：t,1,t,2,|SC(t,1,C2t,2,), 检索学习课程号为C2的学生学号与姓名。,t,1,t,2,|(,u,1,)(,u,2,)(,u,3,)(,u,4,)(,v,1,)(,v,2,)(,v,3,),(S(u,1,u,2,u,3,u,4,)SC(v,1,v,2,v,3,)v,2,=C2,u,1,=v,1,t,1,=u,1,t,2,=u,2,),可化简为：,t,1,t,2,|(,u,3,)(,u,4,)(,v,3,),(S(t,1,t,2,u,3,u,4,)SC(t,1,C2v,3,),80,定义2.6 在数据库技术中，不产生无限关系和无穷验证的运算称为平安运算，相应的表达式称为平安表达式，所采取的措施称为平安约束。,并、差、笛卡儿积、投影和选择是关系代数最根本的操作，并构成了关系代数运算的最小完备集。已经证明，在这个根底上，关系代数、平安的元组关系演算、平安的域关系演算在关系的表达和操作能力上是完全等价的。,81,关系运算的平安性,元组表达式t|Rt，这是一个无限关系。,验证公式(u)(P1(u)为假时，必须对所有可能的元组u进展验证，当所有的u都使P1(u)为假时，才能断定公式(u)(P1(u)为假。,验证公式(u)(P1(u)也是这样，当所有可能的u使P1(u)为真时，才能断定公式(u)(P1(u)为真。这在实际上是行不通的。,我们必须采取措施，防止无限关系和无穷验证的出现。,82,关系运算的平安性续,对于元组表达式t|Pt，将公式P(t)的“域Domain定义为出现在公式P(t)中的常量和关系的所有属性值组成的集合，记为DOM(P(t)。,由于所有关系都是有限的，因此DOM(P)也是有限的。,例如P(t)是t1=aRt，R是二元关系，那么DOM(P)=a1R2R。,83,关系运算的平安性续,平安的元组表达式t|P(t)应满足以下三个条件：,表达式的元组t中出现的所有值均来自DOM(P)。,对于P(t)中每个形如(u)(P1(u)的子公式，如果元组u使P1(u)为真，那么u的每个分量必是DOM(P1)的元素。换言之，如果u有某个分量不属于DOM(P1)，那么P1(u)必为假。,对于P(t)中每个形如(u)(P1(u)的子公式，如果元组u使P1(u)为假，那么u的每个分量必是DOM(P1)的元素。换言之，如果u有某个分量不属于DOM(P1),那么P1(u)必为真。,84,关系运算的等价性,ISBLInformation System Base Language语言与关系代数非常接近。,QUEL语言Query Language是一种基于元组演算的数据语言。,QBEQuery By Example,按例查询是一种特殊的屏幕编辑语言。是一种域演算语言，现在，QBE的思想已渗入到许多DBMS中。,SQLStructured Query Language是介乎于关系代数和元组演算之间的一种关系查询语言，现已成为关系数据库的标准语言，我们将在第3章详细介绍。,85,2.4 关系代数表达式的优化,2.4.1 关系代数表达式的优化问题,2.4.2 关系代数表达式的等价变换规那么,2.4.3 关系代数表达式的优化算法,86,2.4.1 关系代数表达式的优化(1),在关系代数表达式中需要指出假设干关系的操作步骤。那么，系统应该以什么样的操作顺序，才能做到既省时间，又省空间，而且效率也比较高呢？这个问题称为查询优化问题。,在关系代数运算中，,笛卡儿积和连接运算,是最费时间的。,87,2.4.1 关系代数表达式的优化(2),例2.22 设关系R和S都是二元关系，属性名分别为A，B和C，D。,E1 = AB=CD=99RS,E2 = AB=CRD=99S,E3 = AR D=99S,这三个关系代数表达式是等价的，但执行的效率大不一样。显然，求El，E2，E3的大局部时间是花在连接操作上的。,返回,B=C,88,2.4.2 等价变换规那么 (1),连接和笛卡儿积的交换律,连接和笛卡儿积的结合律,投影的级联,选择的级联,选择和投影操作的交换,选择对笛卡儿积的分配律,选择对并的分配律,89,2.4.2 等价变换规那么 (2),选择对集合差的分配律,选择对自然连接的分配律,投影对笛卡儿积的分配律,投影对并的分配律,选择与连接操作的结合,并和交的交换律,并和交的结合律,返回,90,2.4.3 启发式优化算法,(1),在关系代数表达式中，最花费时间和空间的运算是笛卡儿积和连接操作，为此，引出三条启发式规那么，用于对表达式进展转换，以减少中间关系的大小。,尽可能早地执行选择操作；,尽可能早地执行投影操作；,防止直接做笛卡儿积，把笛卡儿积操作 之前和之后的一连串选择和投影合并起 来一起做。,91,2.4.3 启发式优化算法,(2),算法2.1 关系代数表达式的启发式优化算法。,输入：一个关系代数表达式的语法树,输出：计算表达式的一个优化序列,方法： 把每个形为F1 FnE的子表达式转,换成选择级联形式：F1FnE, 在语法树中，尽可能把每个选择下推到树的叶端。, 对每个投影操作，尽可能往下推，移向树的叶端。, 把选择和投影合并在一起做。, 将上述步骤得到的语法树的内结点分组。以每个二元运算、结点为中心分组。, 生成一个序列，每一组结点的计算是序列中的一步。,92,2.4.3 启发式优化算法,(3),例2.23 查询语句：检索学习课程名为OS的女学生学号和姓名。,该查询语句的关系代数表达式如下：,S#，SNAME,(,CNAME=OSSEX=F,(C SC S),上式中， 符号用、操作表示，可得下式：,S#，SNAME,(,CNAME=OSSEX=F,(,L,(,C.C# = SC.C#SC.S# = S.S#,(CSCS),此处L是C、SC、S中全部属性。,93,2.4.3 启发式优化算法,(4),S.S#，SNAME,C.C#，CNAME，T#， SCORE，,S.S#，SNAME，AGE，SEX,CNAME=,OS,SEX=,F,C.C#=SC.C#SC.S#=S.S#,S,SC,C,图2.18 关系代数表达式,的初始语法树,94,2.4.3 启发式优化算法,(5),图2.19 优化过程中的语法树,选择操作已尽可能移向叶端,S.S#，SNAME,SC.S#=S.S#,S,SC,C,SEX=,F,C.C#=SC.C#,CNAME=,OS,95,2.4.3 启发式优化算法,(6),图2.20 优化的语法树,及其分组,S.S#，SNAME,S.S#，SNAME,SC.S#=S.S#,S,SC,C,SEX=,F,C.C#=SC.C#,CNAME=,OS,SC.S#,SC.S#，S