《关模型和关系运算理论.ppt》由会员分享，可在线阅读，更多相关《关模型和关系运算理论.ppt（116页珍藏版）》请在金锄头文库上搜索。
1、第2章关系模型和关系运算理论 数据库系统数据库系统数据库系统数据库系统 20102010年年年年本章重要概念（一）（1）基本概念关系模型，关键码（主键和外键），关系的定义和性质，三类完整性规则，过程性语言与非过程性语言。（2）关系代数五个基本操作，四个组合操作，七个扩充操作。本章重要概念（二）（3）关系演算元组关系演算和域关系演算的原子公式、公式的定义。关系演算的安全性和等价性。（4）关系代数表达式的优化关系代数表达式的等价及等价转换规则，启化式优化算法。（5）关系逻辑谓词、原子、规则和查询，规则的安全性，用规则模拟关系代数表达式。本章概要n本章先介绍关系模型的基本概念；然后介绍关系运算的三种
2、理论：关系代数、关系演算和关系逻辑。2.1 关系模型的基本概念n系统而严格地提出关系模型的是美国IBM公司的E.F.Coddn1970年提出关系数据模型nE.F.Codd, “A Relational Model of Data forLargeSharedDataBanks”,CommunicationoftheACM,1970n之后，提出了关系代数和关系演算的概念n1972年提出了关系的第一、第二、第三范式n1974年提出了关系的BC范式2.1 关系模型的基本概念n关系模型建立在集合代数的基础上n关系数据库应用数学方法来处理数据库中的数据n关系数据库系统n是支持关系模型的数据库系统n80年
3、代后，关系数据库系统成为最重要、最流行的数据库系统2.1 关系模型的基本概念n典型实验系统nSystem RnUniversity INGRESn典型商用系统nORACLEnSYBASEnINFORMIXnDB2nINGRES基本术语(1)n定义2.1用二维表格表示实体集，用关键码表示实体之间联系的数据模型称为关系模型关系模型（relationalModel）。图2.1 职工登记表 基本术语(2)n 在在关关系系模模型型中中，字字段段称称为为属属性性，字字段段值值称称为为属属性性值值，记记录录类类型型称称为为关关系系模模式式。在在图图2.22.2中中，关关系系模模式式名名是是R R。记记录录称
4、称为为元元组组（tupletuple），元元组组的的集集合合称称为为关关系系（relationrelation）或或实实例例（instanceinstance）。一一般般用用大大写写字字母母A A、B B、C C、 表表示示单单个个属属性性，用用大大写写字字母母 、X X、Y Y、Z Z表表示示属属性性集集，用用小小写写字字母母表表示示属属性性值值，有有时时也也习习惯惯称称呼呼关系为表或表格，元组为行关系为表或表格，元组为行(row)(row)，属性为列属性为列(column)(column)。n关系中属性个数称为关系中属性个数称为“元数元数”（arityarity），），元组个数为元组个数为
5、“基数基数”(cardinality)(cardinality)。基本术语(3)n关系元数为关系元数为5 5，基数为，基数为4 4图2.2 关系模型的术语 一般术语一般术语 关系模型术语关系模型术语字段、数据项字段、数据项属性属性记录类型记录类型关系模式关系模式记录记录1 1元组元组1 1记录记录2 2元组元组2 2记录记录3 3元组元组3 3记录记录4 4元组元组4 4字段值字段值属性值属性值基本术语(4)n 关关键键码码(key,(key,简简称称键键) )由由一一个个或或多多个个属属性性组组成成。在在实实际际使用中，有下列几种键。使用中，有下列几种键。 （1 1）超超键键（super s
6、uper KeyKey）：在在关关系系中中能能唯唯一一标标识识元元组组的的属性集称为关系模式的超键。属性集称为关系模式的超键。 （2 2）候候选选键键（candidate candidate KeyKey）：不不含含有有多多余余属属性性的的超超键称为候选键。键称为候选键。在最简单的情况下，候选码只包含一个属性在最简单的情况下，候选码只包含一个属性。 （3 3）主主键键(primary (primary Key)Key)：用用户户选选作作元元组组标标识识的的候候选选键键称为主键。称为主键。 一般如不加说明，键是指主键。一般如不加说明，键是指主键。 基本术语(4)（续）（4 4）全键全键( (Al
7、lkey) )：在最极端的情况下，关在最极端的情况下，关系模式的所有属性组是这个关系模式的候选系模式的所有属性组是这个关系模式的候选键，称为全键（键，称为全键（All-key）例：朋友关系例：朋友关系姓名1姓名2张三李四张三王五赵六李四丁一李四基本术语(4)（续）例例：在在图图2.12.1中中，（工工号号，姓姓名名）是是模模式式的的一一个个超超键键，但但不不是是候候选选键键，而而（工工号号）是是候候选选键键。在在实实际际使使用用中中，如如果果选选择择（工工号号）作作为为删删除除或或查查找找元元组组的的标标志志，那那么么称称（工工号）是主键。号）是主键。（5 5）外外键键（foreign for
8、eign KeyKey）：如如果果模模式式R R中中属属性性K K是其他模式的主键，那么是其他模式的主键，那么K K在在模式模式R R中称为外键。中称为外键。例：例： S S（S#S#，SNAMESNAME，AGEAGE，SEXSEX） SCSC（S#S#，C#C#，GRADEGRADE） 在关系在关系S S中中S#S#为主键，在关系为主键，在关系SCSC中中S#S#为外键。为外键。基本术语(5) 关关系系中中每每一一个个属属性性都都有有一一个个取取值值范范围围，称称为为属属性性的的值值域域。属属性性A A的的取取值值范范围围用用DOMDOM（A A）表示。表示。关系的定义和性质n定义定义2.
9、2 2.2 关系关系是一个具有相同属性的元组的集合。是一个具有相同属性的元组的集合。n 在关系模型中，对关系作了下列规范性限制：在关系模型中，对关系作了下列规范性限制：（1 1）关系中每一个属性值都是不可分解的；）关系中每一个属性值都是不可分解的；（2 2）关关系系中中不不允允许许出出现现重重复复元元组组（即即不不允允许许出出现现相相同同的的元组）；元组）；（3 3）由由于于关关系系是是一一个个集集合合，因因此此不不考考虑虑元元组组间间的的顺顺序序，即没有行序；即没有行序；（4 4）元元组组中中的的属属性性在在理理论论上上也也是是无无序序的的，但但使使用用时时按按习习惯考虑列的顺序。惯考虑列的
10、顺序。关系模型的3类完整性规则(1)n 实体完整性规则（实体完整性规则（entity integrity ruleentity integrity rule）要要求求关关系系中中元元组组在在组组成成主主键键的的属属性性上上不不能能有有空空值值。如如果果出现空值，那么主键值就起不了惟一标织元组的作用。出现空值，那么主键值就起不了惟一标织元组的作用。关系模型的3类完整性规则(2)n参照完整性规则（参照完整性规则（reference integrity rule）n定义定义2.3 参照完整性规则的形式定义如下：参照完整性规则的形式定义如下： 如如果果属属性性集集K是是关关系系模模式式R1的的主主键键
11、，K也也是是关关系系模模式式R2的的外外键键，那那么么在在R2的的关关系系中中，K的的取取值值只只允允许许两两种种可能，或者为空值，或者等于可能，或者为空值，或者等于R1关系中某个主键值。关系中某个主键值。这条规则的实质是这条规则的实质是“不允许引用不存在的实体不允许引用不存在的实体”。 在在上上述述形形式式定定义义中中，关关系系模模式式R1R1的的关关系系称称为为“参参照照关关系系”，关关系系模模式式R2R2的的关关系系称称为为“依依赖赖关关系系”。R1R1和和R2 R2 的的关关系系也也称称为为“主主表表”和和“副副表表”(PowerBuilder)(PowerBuilder)，“父表父表
12、”和和“子表子表”(Visual (Visual FoxproFoxpro) )。关系模型的3类完整性规则(3)n例例2.1 2.1 下下面面各各种种情情况况说说明明了了参参照照完完整整性性规规则则在在关关系系中中如何实现的。如何实现的。 在关系数据库中有下列两个关系模式：在关系数据库中有下列两个关系模式：S S（S#S#，SNAMESNAME，AGEAGE，SEXSEX）SCSC（S#S#，C#C#，GRADEGRADE） 在在关关系系S S中中S#S#为为主主键键，在在关关系系SCSC中中S#S#为为外外键键。据据规规则则要要求求关关系系SCSC中中的的S# S# 值值应应该该在在关关系系
13、S S中中出出现现。如如果果关关系系SCSC中中有有一一个个元元组组（S7,C4,80S7,C4,80），而而学学号号S7S7却却在在关关系系S S中中找找不不到到，那那么么我我们们就就认认为为在在关关系系SCSC中中引引用用了了一一个个不不存存在在的学生实体，这就违反了参照完整性规则。的学生实体，这就违反了参照完整性规则。 另另外外，在在关关系系SCSC中中S# S# 不不仅仅是是外外键键，也也是是主主键键的的一一部部分，因此这里分，因此这里S# S# 值不允许空。值不允许空。关系模型的3类完整性规则(4)设工厂数据库中有两个关系模式：设工厂数据库中有两个关系模式：DEPT(DEPT(D#D
14、#，DNAME)DNAME)EMP(EMP(E#E#，ENAMEENAME，SALARYSALARY，D#D# ) ) 车车间间模模式式DEPTDEPT的的属属性性为为车车间间编编号号、车车间间名名，职职工工模模式式EMPEMP的的属属性性为为工工号号、姓姓名名、工工资资、所所在在车车间间的的编编号号。每每个个模模式式的的主主键键与与外外键键已已标标出出。在在EMPEMP中中，由由于于D# D# 不不在在主键中，因此主键中，因此D# D# 值允许空。值允许空。关系模型的3类完整性规则(5) 设课程之间有先修、后继联系。模式如下：设课程之间有先修、后继联系。模式如下：R(R(C#C# ，CNAM
15、ECNAME，PC#PC# ) ) 其属性表示课程号、课程名、先修课的课程号。如其属性表示课程号、课程名、先修课的课程号。如果规定，每门课程的直接先修课只有一门，那么模式果规定，每门课程的直接先修课只有一门，那么模式R R的主键是的主键是C#C#，外键是外键是PC#.PC#.。这里参照完整性在一个模这里参照完整性在一个模式中实现。即每门课程的直接先修课必须在关系中出式中实现。即每门课程的直接先修课必须在关系中出现。现。关系模型的3类完整性规则(6)n用户定义的完整性规则用户定义的完整性规则 在在建建立立关关系系模模式式时时，对对属属性性定定义义了了数数据据类类型型，即即使使这这样样可可能能还还
16、满满足足不不了了用用户户的的需需求求。此此时时，用用户户可可以以针针对对具具体体的的数数据据约约束束，设设置置完完整整性性规规则则，由由系系统统来来检检验验实实施施，以以使使用用统统一一的的方方法法处处理理它它们们，不不再再由由应应用用程程序序承承担担这这项项工工作作。例例如如学学生生的的年年龄龄定定义义为为两两位位整整数数，范范围围还还太太大大，我我们们可可以以写写如如下下规规则则把把年年龄龄限限制制在在15153030岁之间：岁之间：CHECKCHECK（AGE BETWEEN 15 AND 30AGE BETWEEN 15 AND 30）数据结构图 数据结构图可用来表示关系数据库数据结构
17、图可用来表示关系数据库中表与表之间的联系。中表与表之间的联系。矩形框表示关系模式矩形框表示关系模式框间的连线表示其联系框间的连线表示其联系连连线线端端点点的的“鸡鸡爪爪型型”表表示示“多多”的一端的一端P42图图2.3关系模型的3层体系结构n在关系模型中，记录类型称为关系模式，在关系模型中，记录类型称为关系模式，而关系模式的集合就是数据库的概念模式。在而关系模式的集合就是数据库的概念模式。在系统实现时，关系模式和属性的命名一般都用系统实现时，关系模式和属性的命名一般都用英文单词。如：英文单词。如： 学生关系模式S(S#，SNAME，AGE，SEX) 选课关系模式SC(S#，C#，GRADE)
18、课程关系模式C(C#，CNAME，TEACHER)图2.6 关系模式集关系模型的3层体系结构-子模式n子模式是用户所用到的那部分数据的描述。除此之外，子模式是用户所用到的那部分数据的描述。除此之外，还应指出数据与关系模式中相应数据的联系。例如，还应指出数据与关系模式中相应数据的联系。例如，用户需要用到子模式用户需要用到子模式G G（图（图2.42.4）。）。成绩子模式 G(S#，SNAME，C#，GRADE) 图2.4 子模式关系模型的3层体系结构-存储模式图2.6 关系S和SC的环结构 在有些在有些DBMSDBMS中，关系存储是作为文件看待的，每个元中，关系存储是作为文件看待的，每个元组就是
19、一个记录。由于关系模式有键，因此存储一个关组就是一个记录。由于关系模式有键，因此存储一个关系可用散列方法或索引方法实现。如果关系的元组数目系可用散列方法或索引方法实现。如果关系的元组数目较少（较少（100100个以内），那么也可以用个以内），那么也可以用“堆文件堆文件”方式实现方式实现（即没有特定的次序）。此外，还可对任意的属性集建（即没有特定的次序）。此外，还可对任意的属性集建立辅助索引。立辅助索引。 关系模型的形式定义n 关关系系模模型型有有三三个个重重要要组组成成部部分分：数数据据结结构构，数数据据操操纵纵，数据完整性规则。数据完整性规则。（1 1）数数据据结结构构：数数据据库库中中全全
20、部部数数据据及及其其相相互互联联系系都都被被组组织织成成“关关系系”（二二维维表表格格）的的形形式式。关关系系模模型型基基本本的的数据结构是关系。数据结构是关系。（2 2）数数据据操操纵纵：关关系系模模型型提提供供一一组组完完备备的的高高级级关关系系运运算算，以以支支持持对对数数据据库库的的各各种种操操作作。关关系系运运算算分分成成关关系系代代数数、关系演算和关系逻辑等三类。关系演算和关系逻辑等三类。（3 3）数据完整性规则数据完整性规则：数据库中数据必须满足实体完整：数据库中数据必须满足实体完整性，参照完整性和用户定义的完整性等三类完整性规性，参照完整性和用户定义的完整性等三类完整性规则。则
21、。关系模型的优点n与其它数据模型相比，关系模型突出的优点如下：与其它数据模型相比，关系模型突出的优点如下：（1 1）关关系系模模型型提提供供单单一一的的数数据据结结构构形形式式，具具有有高高度度的的简简明性和精确性。明性和精确性。（2 2）关关系系模模型型的的逻逻辑辑结结构构和和相相应应的的操操作作完完全全独独立立于于数数据据存储方式，具有高度的数据独立性。存储方式，具有高度的数据独立性。（3 3）关关系系模模型型使使数数据据库库的的研研究究建建立立在在比比较较坚坚实实的的数数学学基基础上。础上。（4 4）关关系系数数据据库库语语言言与与一一阶阶谓谓词词逻逻辑辑的的固固有有内内在在联联系系，为
22、为以以关关系系数数据据库库为为基基础础的的推推理理系系统统和和知知识识库库系系统统的的研研究提供了方便。究提供了方便。关系查询语言和关系运算n关关系系数数据据库库的的数数据据操操纵纵语语言言（DML）的的语语句句分分成成查查询询语语句句和和更更新新语语句句两两大大类类。查查询询语语句句用用于于描描述述用用户户的的各各种种检检索索要要求求；更更新新语语句句用用于于描描述述用用户户进进行行插插入入、删删除除、修改等操作。关于查询的理论称为修改等操作。关于查询的理论称为“关系运算理论关系运算理论”。n关系查询语言根据其理论基础的不同分成三类：关系查询语言根据其理论基础的不同分成三类：（1）关系代数语
23、言：查询操作以集合操作为基础的运算）关系代数语言：查询操作以集合操作为基础的运算（2）关系演算语言：查询操作以谓词演算为基础的运算）关系演算语言：查询操作以谓词演算为基础的运算（3）关系逻辑语言：查询操作以）关系逻辑语言：查询操作以if-then逻辑操作为基逻辑操作为基础的运算础的运算2.2 关系代数n关系代数：一组高级运算的集合，运算的对象为关系。关系代数：一组高级运算的集合，运算的对象为关系。n关系代数运算分为：传统的集合运算关系代数运算分为：传统的集合运算并、差、交、广义笛卡尔积并、差、交、广义笛卡尔积专门的关系运算专门的关系运算选择、投影、连接、除选择、投影、连接、除n五个基本运算：并
24、、差、笛卡尔积、选择、投影，其五个基本运算：并、差、笛卡尔积、选择、投影，其他运算可由他们推出。他运算可由他们推出。关系代数的五个基本操作(1)n 并（并（Union）设设关关系系R和和S具具有有相相同同的的关关系系模模式式，R和和S的的并并是是由由属属于于R或或属属于于S的的元元组组构构成成的的集集合合，记记为为RS。形形式式定定义义如如下：下： RSt | tR tS t是元组变量，是元组变量，R和和S的元数相同。的元数相同。n 差（差（Difference）设设关关系系R和和S具具有有相相同同的的关关系系模模式式，R和和S的的差差是是由由属属于于R但但不不属属于于S的的元元组组构构成成的
25、的集集合合，记记为为RS。形形式式定定义义如下：如下： RS t | tR tS R和和S的元数相同。的元数相同。关系代数的五个基本操作（1） RABCa1b1c1a1b2c2a2b2c1SABCa1b2c2a1b3c2a2b2c1RS ABCa1b1c1a1b2c2a1b3c2a2b2c1R-S ABCa1b1c1关系代数的五个基本操作（1）nRnn元关系，元关系，k1个元组个元组nSnm元关系，元关系，k2个元组个元组n笛卡尔积：笛卡尔积：RSn列：（列：（n+m）列的元组的集合列的元组的集合n元组的前元组的前n列是关系列是关系R的一个元组的一个元组n后后m列是关系列是关系S的一个元组的一
26、个元组n行：行：k1k2个元组个元组nRS=tr,ts|tr Rts S关系代数的五个基本操作（1）RABCa1 b1 c1a1 b2 c2a2 b2 c1SABCa1 b2 c2a1 b3 c2a2 b2 c1R S R.AR.BR.Ca1b1c1a1b1c1a1b1c1a1b2c2a1b2c2a1b2c2a2b2c1a2b2c1a2b2c1S.AS.BS.Ca1b2c2a1b3c2a2b2c1a1b2c2a1b3c2a2b2c1a1b2c2a1b3c2a2b2c1关系代数的五个基本操作（2）n投影：投影：n1）投影运算符的含义）投影运算符的含义n从从R中选择出若干属性列组成新的关系中选择出
27、若干属性列组成新的关系A(R)=tA|t RA：R中的属性列中的属性列A=Ai1,Ai2,Ai3,Aikn t R表示表示t是是R的一个元组的一个元组ntA=(tAi1，tAi2，tAik)表示元组表示元组t在属在属性列性列A上诸分量的集合。上诸分量的集合。nA(R)可写为可写为i1，im（R）关系代数的五个基本操作（2）n2）投影操作主要是从列的角度进行运算n但投影之后不仅取消了原关系中的某些列，而且还可能取消某些元组（避免重复行）关系代数的五个基本操作（2）RABCa1 b1 c1a1 b2 c2a2 b2 c1SABCa1 b2 c2a1 b3 c2a2 b2 c1C，A(R)或或3，1
28、(R)CAc1a1c2a1c1a2ACa1c2a2c1A，C(S)或或1，3(S)关系代数的五个基本操作（3）n1)选择选择:又称为限制（又称为限制（Restriction）n2)选择运算符的含义选择运算符的含义n在关系在关系R中选择满足给定条件的诸元组中选择满足给定条件的诸元组F(R)=t|t RF(t)=真真nF：选择条件，是一个逻辑表达式，基本形式为：选择条件，是一个逻辑表达式，基本形式为： (X1Y1) ( X2Y2)n：比较运算符（，比较运算符（，或，或）nX1，Y1等等：属属性性名名、常常量量、简简单单函函数数；属属性性名名也也可可以以用用它它的序号来代替；的序号来代替；n：逻辑运
29、算符（逻辑运算符（或或）n：表示任选项：表示任选项n：表示上述格式可以重复下去：表示上述格式可以重复下去关系代数的五个基本操作（3）例如，23（R）表表示示从从R中中挑挑选选第第2个个分分量量值值大大于于3的的元元组组所所构构成成的的关关系系。书书写写时时，为为了了与与属属性性序序号号区区别别起起见见，常常量量用用引引号号括括起起来来，而而属属性性序序号号或或属属性性名名不不要要用引号括起来。用引号括起来。n3)选择运算是从行的角度进行的运算选择运算是从行的角度进行的运算关系代数的五个基本操作（3）RABCa1 b1 c1a1 b2 c2a2 b2 c1A= a1 (R)或或1= a1(R)A
30、BCa1 b1 c1a1 b2 c2例：例：设设有有一一个个学学生生-课课程程数数据据库库，包包括括学学生生关关系系Student、课程关系课程关系Course和选修关系和选修关系关系代数的五个基本操作（例）学学 号号Sno姓姓 名名Sname性性 别别Ssex年年 龄龄Sage系系 Sdept95001李勇李勇男男20CS95002刘晨刘晨女女19IS95003王敏王敏女女18MA95004张立张立男男19IS Student关系代数的五个基本操作（例）例1查询学生的姓名和所在系即求Student关系上学生姓名和所在系两个属性上的投影Sname，Sdept(Student)或2，5(Stud
31、ent)结果：SnameSdept李勇李勇CS刘晨刘晨IS王敏王敏MA张立张立IS关系代数的五个基本操作（例）例2查询学生关系Student中都有哪些系Sdept(Student)结果：SdeptCSISMA关系代数的五个基本操作（例）例3查询信息系（IS系）全体学生Sdept=IS(Student)或5=IS(Student)结果：SnoSnameSsexSageSdept95002刘晨刘晨女女19IS95004张立张立男男19IS关系代数的五个基本操作（例）例4查询年龄小于20岁的学生Sage20(Student)或420(Student)结果：SnoSnameSsexSageSdept9
32、5002刘晨刘晨女女19IS95003王敏王敏女女18MA95004张立张立男男19IS关系代数的四个组合操作(1)n 交（交（intersection） 关关系系R和和S的的交交是是由由属属于于R又又属属于于S的的元元组组构构成成的的集集合合，记记为为RS，这这里里要要求求R和和S定定义义在在相相同同的的关关系系模模式式上。形式定义如下：上。形式定义如下： RSttR tS R和和S的元数相同。的元数相同。 由由于于RS = R-（R-S），或或RS = S-（S-R），因因此交操作不是一个独立的操作。此交操作不是一个独立的操作。 关系代数的四个组合操作（1）RABCa1b1c1a1b2c2
33、a2b2c1SABCa1b2c2a1b3c2a2b2c1R S ABCa1b2c2a2b2c1关系代数的四个组合操作（2）n连连接接（join）连连接接有有两两种种：连连接接和和F连连接接（这这里里是算术比较符，是算术比较符，F是公式）。是公式）。 连接连接 n从从两两个个关关系系的的笛笛卡卡尔尔积积中中选选取取属属性性间间满满足足一一定定条条件件的元组的元组R S = t|t= tr Rts StrAtsBnA和和B：分别为分别为R和和S上可比的属性上可比的属性n：比较运算符比较运算符 AB关系代数的四个组合操作（2）n连接运算从连接运算从R和和S的广义笛卡尔积的广义笛卡尔积RS中选取（中选
34、取（R关系）在关系）在A属性上的值与属性上的值与（S关系）在关系）在B属性上值满足比较关系的属性上值满足比较关系的元组元组关系代数的四个组合操作（2）ABCa1b15a1b26a2b38a2b412 RBEb13b27b310b32b52Sn举例 例1 CEAR.BCS.BEa1b15b27a1b15b310a1b26b27a1b26b310a2b38b310RS关系代数的四个组合操作（2）n等值连接（等值连接（equijoin）n什么是等值连接什么是等值连接n为为“”的连接运算称为等值连接的连接运算称为等值连接n等值连接的含义等值连接的含义n从从关关系系R与与S的的广广义义笛笛卡卡尔尔积积中
35、中选选取取A、B属性值相等的那些元组，即等值连接为：属性值相等的那些元组，即等值连接为：R S=t|t= tr Rts StrA=tsBA=B关系代数的四个组合操作（2）例2：等值连接R S R.B=S.B AR.BCS.BEa1b15b13a1b26b27a2b38b310a2b38b32 ABCa1b15a1b26a2b38a2b412BEb13b27b310b32b52RS关系代数的四个组合操作（2）n自然连接（自然连接（Naturaljoin）n什么是自然连接什么是自然连接n自然连接是一种特殊的等值连接自然连接是一种特殊的等值连接n两个关系中进行比较的分量必须是相同的属两个关系中进行比
36、较的分量必须是相同的属性组性组n在结果中把重复的属性列去掉在结果中把重复的属性列去掉n自然连接的含义自然连接的含义R和和S具有相同的属性组具有相同的属性组BR S = t|t= tr Rts StrB=tsB关系代数的四个组合操作（2）ABCEa1b153a1b267a2b3810a2b382例3自然连接R S ABCa1b15a1b26a2b38a2b412BEb13b27b310b32b52RS关系代数的四个组合操作（2）n一般的连接操作是从行的角度进行运算。自然连接还需要取消重复列，所以是同时从行和列的角度进行运算。 ABRS关系代数的四个组合操作（2） F连接连接 F连接是从关系连接是
37、从关系R和和S的笛卡儿积中选取属性的笛卡儿积中选取属性间满足某一公式间满足某一公式F的元组的元组, 这里这里F是形为是形为F1F2Fn的公式，每个的公式，每个FP是形为是形为ij的式的式子，而子，而i和和j分别为关系分别为关系R和和S的第的第i、第、第j个分量个分量的序号。的序号。关系代数的四个组合操作（2）例4F连接R S 2=13s0），），那那么么RS是一个（是一个（r-s）元的元组的集合。元的元组的集合。（RS）是满足下列条件的最大关系：其中每是满足下列条件的最大关系：其中每个元组个元组t与与S中每个元组中每个元组u组成的新元组组成的新元组必在关系必在关系R中。中。 nRS 1，2，r
38、-s（R）- 1，2，r-s（ 1，2，r-s（R）S）-R） 2.2.3关系代数运算的应用实例n 在在关关系系代代数数运运算算中中，把把由由五五个个基基本本操操作作经经过过有有限限次次复复合合的的式式子子称称为为关关系系代代数数表表达达式式。这这种种表表达达式式的的运运算算结结果果仍仍是是一一个个关关系系。我我们们可可以以用用关关系系代代数数表表达达式式表表示示各种数据查询操作。各种数据查询操作。 教学数据库系统应用实例例例2.7 设有教学数据库系统的四个关系：设有教学数据库系统的四个关系：教师关系教师关系T(T#,TNAME,TITLE)学生关系学生关系S(S#,SNAME,AGE,SEX
39、)选课关系选课关系SC(S#,C#,GRADE)课程关系课程关系C(C#,CNAME,T#)应用实例（1）n(1)检索学习课程号为检索学习课程号为C2的学生学号与成绩的学生学号与成绩n分析：所求的分析：所求的S#与与GRADE属性均在属性均在SC关系中；关系中；约束条件为约束条件为C#是是C2,C#在在SC中，因此对中，因此对SC关关系操作。系操作。n解：解：s#,GRADE(c#=c2(sc)n注：约束条件成为选择运算的选择条件。注：约束条件成为选择运算的选择条件。应用实例（2）n(2)检索学习课程号为检索学习课程号为C2的的学生学号与姓名学生学号与姓名n分析：所求的分析：所求的S#与与SN
40、AME在在S中，选择条件中，选择条件中中C#在在SC和和C中，因此必须把中，因此必须把S和和SC或或C连接，连接，但但C与与S没有公共属性。没有公共属性。n解：解：s#,SNAME(c#=c2(SSC)应用实例（3）n(3)检索至少选修检索至少选修LIU老师所授课程中一门课程老师所授课程中一门课程的学生学号与姓名。的学生学号与姓名。n分析：所求的分析：所求的S#与与SNAME在在S中，选择条件中中，选择条件中LIU在在T中，但中，但S和和T没有公共属性，因此必须借没有公共属性，因此必须借助助SC和C。n(SSC)C=S(SCC)=SSCCn解：解：ns#,SNAME(TNAME=LIU(SSC
41、CT)应用实例（4）n(4)检索选修课程号为检索选修课程号为C2或或C4的学生学号。的学生学号。n分析：所求的分析：所求的S#与选择条件中与选择条件中C#都在都在SC中，中，选择条件用逻辑或表示，所求的仅有学号。选择条件用逻辑或表示，所求的仅有学号。n解：解：s#(C#=c2C#=c4(SC)n应用实例（5）n(5)检索至少选修课程号为检索至少选修课程号为C2和和C4的学生学号。的学生学号。n分析：所求分析：所求S#和选择条件中的和选择条件中的C#均在均在SC中，因此对中，因此对SC操作，但操作，但SC中元组仅有一个中元组仅有一个C#值，要包括值，要包括C2和和C4必须有一个元组中有两个必须有
42、一个元组中有两个C#值，考虑值，考虑SCSC中同一中同一学生的元组。学生的元组。n解：解：1(1=42=C25=C4(SCSC)n错误解：错误解：1(2=C22=C4(SC)应用实例（6）n(6)检索检索不不学学C2课的学生姓名与年龄。课的学生姓名与年龄。n分析：所有的学生中去除选学分析：所有的学生中去除选学C2课的学生课的学生。n解：解：SNAME,AGE(S)-SNAME,AGE(c#=c2(SSC)注：检索条件中有否定词的用差运算。注：检索条件中有否定词的用差运算。n错误解：错误解：SNAME,AGE(c#c2(SSC)应用实例（7）n(7)检索学习检索学习全部全部课程的学生姓名。课程的
43、学生姓名。n分析：全部课程为：分析：全部课程为：C#(C)n学习了全部课程的学生为学习了全部课程的学生为S#,C#(SC)C#(C)n但但SC中没有中没有SNAME，因此要与因此要与S连接。连接。n解：解：SNAME(S(S#,C#(SC)C#(C)注：检索条件中有全部、所有等全称量词的注：检索条件中有全部、所有等全称量词的用除运算。用除运算。应用实例（8）n(8)检索所学课程检索所学课程包含包含S3所学课程的学生的学号。所学课程的学生的学号。n分析：分析：S3所学的课程可用所学的课程可用C#(S#=S3(SC)。n解：解：S#,C#(SC)C#(S#=S3(SC)关系代数的七个扩充操作（1）
44、n改名改名 ：S(A1,An)(R) 例：例：将将R(B,C,D)改名为改名为S(A,B,C)：S(A,B,C)(R)将将R(B,C,D)改名为改名为R(X,C,D)：R(X,C,D)(R)将将R(B,C,D)改名为改名为S(B,C,D)：S(R)n广义投影广义投影 ： F1,Fn(R)Fi为常量与属性的算术表达式。为常量与属性的算术表达式。例：例：s#,c#,GRADE*1.05(c#=c2(sc)n赋值赋值 ： 例：例：TEMP R S 关系代数的七个扩充操作（2）n外连接（outer join） ABCabcbbfcadRBCDbcdbceadbefgSABCDabcdabcecadbA
45、BCDabcdabcecadbbbfnullnullefgR SABCDabcdabcecadbnullefgABCDabcdabcecadbbbfnull R S左外连接左外连接 R S 外连接外连接 R S右外连接右外连接关系代数的七个扩充操作（3）n外部并（outer union）： ABCDabcnullbbfnullcadnullnullbcdnullbcenulladbnullefg关系代数的七个扩充操作（4）n半连接（semijoin）：nR S=R (R S) S R= S (S R) R S S RABCabcdbcbbfcadBCDbcdbceadbRSABCabcdbcc
46、adBCDbcdbceadb关系代数的七个扩充操作（5）n聚集操作 ：max、min、avg、sum、count例：求男同学的平均年龄avgage(SEX=M(s)求年龄为18岁的人数counts#(AGE=18(s)2.3 关系演算n把数理逻辑的谓词演算引入到关把数理逻辑的谓词演算引入到关系运算中，就可得到以关系演算系运算中，就可得到以关系演算为基础的运算。关系演算又可分为基础的运算。关系演算又可分为元组关系演算和域关系演算，为元组关系演算和域关系演算，前者以元组为变量，后者以属性前者以元组为变量，后者以属性（域）为变量。（域）为变量。2.3.1元组关系演算n 在在元元组组关关系系演演算算（
47、Tuple Relational Calculus）中中，元元组组 关关系系演演算算表表达达式式简简称称为为元元组组表表达达式式，其一般形式为其一般形式为 t | P（t） 其中，其中，t是元组变量，表示一个元数固定的元是元组变量，表示一个元数固定的元组；组；P是公式，在数理逻辑中也称为谓词，也是公式，在数理逻辑中也称为谓词，也就是计算机语言中的条件表达式。就是计算机语言中的条件表达式。 t | P（t）表示满足公式表示满足公式P的所有元组的所有元组t的集合。的集合。 公式（1）n在元组表达式中，公式由原子公式组成。在元组表达式中，公式由原子公式组成。n定义定义2.4 原子公式（原子公式（At
48、oms）有下列三种形式：有下列三种形式： R（s） :表示命题表示命题“s是关系是关系R的一个元组的一个元组” siuj ：表示命题表示命题“元组元组s的第的第i个分量和元组个分量和元组u的第的第j个分量之间满足个分量之间满足关系关系” sia或或auj：a是常量是常量 ，“sia”表示命题表示命题 “元组元组s的第的第i个分量与常量个分量与常量a之间满足之间满足关系关系”n在定义关系演算操作时，要用到在定义关系演算操作时，要用到“自由自由”（FreeFree）和和“约束约束”（BoundBound）变量概念。在一个公式中，如果元变量概念。在一个公式中，如果元组变量未用存在量词组变量未用存在量
49、词 或全称量词或全称量词 符号定义，那么称符号定义，那么称为为自由元组变量自由元组变量，否则称为，否则称为约束元组变量约束元组变量。公式（2）n定义定义2.5 公式（公式（Formulas）的递归定义如下：的递归定义如下： 每个原子是一个公式。其中的元组变量是自由变量。每个原子是一个公式。其中的元组变量是自由变量。 如果如果P1和和P2是公式，那么是公式，那么P1、P1P2、P1P2和和P1P2也都是公式。也都是公式。 如果如果P1是公式，那么（是公式，那么（ s）（）（P1）和（和（ s）（）（P1）也都是公式。也都是公式。 公式中各种运算符的优先级从高到低依次为：公式中各种运算符的优先级从
50、高到低依次为：， 和和 ，和和，。在公式外还可以加括号，以改。在公式外还可以加括号，以改变上述优先顺序。变上述优先顺序。 公式只能由上述四种形式构成，除此之外构成的都公式只能由上述四种形式构成，除此之外构成的都不是公式。不是公式。 元组关系演算实例n例例2.152.15 图图2.202.20的（的（a a）、（）、（b b）是关系是关系R R和和S S，（，（c c）（）（g g）分别是下面分别是下面五个元组表达式的值五个元组表达式的值图2.20 元组关系演算的例子 R1 = t | SR1 = t | S（t t）t12 t12 R2 = t | RR2 = t | R（t t）SS（t t
51、） R3 = t |R3 = t |（ u u）（）（S S（t t）RR（u u）t3u2t3u1t3u1） R5 = t R5 = t | |（ u u）（）（ v v）（）（R R（u) u) S S（v v） u1v2 t1=u2 u1v2 t1=u2 t2=v3t3=u1t2=v3t3=u1） 元组关系演算的等价转换规则n 在在元元组组关关系系演演算算的的公公式式中中，有有下下列列三三个个等等价价的的转转换换规规则：则： P1P2等价于等价于(P1P2)； P1P2等价于等价于（P1P2）。）。 （ s）（）（P1（s）等价于等价于( s)（P1（s）；）； （ s）（）（P1（s）
52、等价于等价于( s）（）（P1（s）。）。 P1P2等价于等价于 P1P2。关系代数表达式到元组表达式的转换例例2.16RS可用可用t|R（t）S（t）表示；表示；R-S可用可用t|R（t）S（t）表示；表示；RS可用可用t|（ u）（）（ v）（）（R（u）S(V)t1=u1t2=u2t3=u3t4=v1t5=v2t6=v3）表示。表示。关系代数表达式到元组表达式的转换设投影操作是设投影操作是2,3（R），），那么元组表达式可写成：那么元组表达式可写成：t|( u)（R（u）tl=u2t2=u3）F（R）可用可用t|R(t)F表示，表示，F是是F的等价表示形式。的等价表示形式。譬如譬如2=d
53、（R）可写成可写成t|（R（t）t2=d）。 2.3.2域关系演算n原子公式有两种形式：原子公式有两种形式： R R（x x1 1xxk k）；）； xyxy。 公公式式中中也也可可使使用用、和和等等逻逻辑辑运运算算符符,(,( x)x)和和（ x x），），但变量但变量x x是域变量，不是元组变量。是域变量，不是元组变量。n自由域变量、约束域变量等概念和元组演算中一样。自由域变量、约束域变量等概念和元组演算中一样。n域演算表达式是形为域演算表达式是形为t t1 1ttk kPP（t t1 1，t tk k） 的的表表达达式式，其其中中P P（t t1 1，t tk k）是是关关于于自自由由域
54、域变变量量t t1 1，t tk k 的公式。的公式。域关系演算实例n例例2.19 2.19 图图2.212.21的的（a a）、（b b）、（c c）是是三三个个关关系系R R、S S、W W，（d d）、（）、（e e）、（）、（f f）分别表示下面三个域表达式的值。分别表示下面三个域表达式的值。（a）关系R （b）关系S（c）关系W （d）R1 （e）R2 （f）R3 图2.21 域关系演算的例子 R1= xyz| RR1= xyz| R（xyzxyz） x3 x3 R2= xyz| RR2= xyz| R（xyzxyz）（S S（xyzxyz） y = 4y = 4） R3= xyz|
55、R3= xyz|（ u u）（）（ v v）（）（R R（zxuzxu） w w（yvyv） uv uv ） ABC123456789ABC123346569DE7548ABC456ABC123456789346BDA574877847元组表达式到域表达式的转换 转换规则如下：转换规则如下： 对对于于k k元元的的元元组组变变量量t t，可可引引入入k k个个域域变变量量t t1 1t tk k，在在公公式式中中t t用用t t1 1t tk k替替换换，元元组组分分量量titi用用t ti i替换。替换。 对于每个量词（对于每个量词（ u）或（或（ u），若），若u是是m元的元组变量，则引入
56、元的元组变量，则引入m个新的域变量个新的域变量u1um。在量词的辖域内，在量词的辖域内，u用用u1um替换替换，ui用用ui替替换，（换，（ u）用（用（ u1）（ um）替换，替换，（ u）用（用（ u1）（ um）替换。替换。关系运算的安全性n无限关系：关系中的元组有无限多个。如：无限关系：关系中的元组有无限多个。如： t|R（t）n无穷验证：验证公式真假时需要进行无限次验证。无穷验证：验证公式真假时需要进行无限次验证。 如验证：如验证：（ u）P1（u）为假）为假 或或 （ u）P1（u）为真）为真n定定义义2.6 2.6 在在数数据据库库技技术术中中，不不产产生生无无限限关关系系和和无
57、无穷穷验验证证的的运运算算称称为为安安全全运运算算，相相应应的的表表达达式式称称为为安安全全表表达达式式，所采取的措施称为安全约束。所采取的措施称为安全约束。n在在关关系系演演算算中中，我我们们约约定定，运运算算只只在在表表达达式式中中公公式式涉涉及及的的关关系系值值范范围围内内进进行行，这这样样就就不不会会产产生生无无限限关关系系和和无无穷穷验证问题，关系演算是安全的。验证问题，关系演算是安全的。关系运算的等价性n并、差、笛尔卡积、投影和选择是关系代数最基本的并、差、笛尔卡积、投影和选择是关系代数最基本的操作，并构成了关系代数运算的最小完备集。已经证操作，并构成了关系代数运算的最小完备集。已
58、经证明，在这个基础上，关系代数、安全的元组关系演算、明，在这个基础上，关系代数、安全的元组关系演算、安全的域关系演算在关系的表达和操作能力上是完全安全的域关系演算在关系的表达和操作能力上是完全等价的。等价的。n相相应应于于关关系系代代数数、元元组组演演算算和和域域演演算算三三种种关关系系运运算算，关关系系查查询询语语言言的的典典型型代代表表是是ISBLISBL语语言言、QUELQUEL语语言言和和QBEQBE语言。语言。关系运算的等价性nISBL(Information ISBL(Information System System Base Base Language)Language)于于1
59、9761976年年由由IBMIBM公公司司英英格格兰兰底底特特律律科科学学中中心心研研制制出出来来，与与关关系系代代数数非非常常接接近近，每每个个查查询询语语句句都都近似于一个关系代数表达式。近似于一个关系代数表达式。nQUEL(Query QUEL(Query Language)Language)是是美美国国伯伯克克利利加加州州大大学学研研制制的的关关系系数数据据库库系系统统INGRESINGRES的的查查询询语语言言，19751975年年投投入入运运行行，是是一一种种基基于于元元组组关关系系演演算算的的数据查询语言数据查询语言。关系运算的等价性nQBE(Query By Example)Q
60、BE(Query By Example)由由M.M.ZloofM.M.Zloof提出，提出，19781978年在年在IBM 370IBM 370上实现，是约克镇上实现，是约克镇IBMIBM高级研高级研究实验室为图形显示终端用户设计的一种域演究实验室为图形显示终端用户设计的一种域演算语言。算语言。nSQL(Structured Query Language)SQL(Structured Query Language)是一种介于是一种介于关系代数和元组演算之间的关系查询语言，现关系代数和元组演算之间的关系查询语言，现已成为关系数据库的标准语言。已成为关系数据库的标准语言。2.4 关系代数表达式的优
61、化n在在关关系系代代数数表表达达式式中中需需要要指指出出若若干干关关系系的的操操作作步步骤骤。那那么么，系系统统应应该该以以什什么么样样的的操操作作顺顺序序，才才能能做做到到既既省省时时间间，又又省省空空间间，而而且且效效率率也也比比较高呢？这个问题称为查询优化问题。较高呢？这个问题称为查询优化问题。n在关系代数运算中，笛卡儿积和连接运算是最在关系代数运算中，笛卡儿积和连接运算是最费时间的。费时间的。n数据库管理系统产品强调：一个查询中涉及的数据库管理系统产品强调：一个查询中涉及的基本表的个数不要超过基本表的个数不要超过7 7个，最多不要超过个，最多不要超过1010个个关系代数表达式的优化(1
62、)n例例2.22 2.22 设设关关系系R R和和S S都都是是二二元元关关系系，属属性性名名分分别别为为A A，B B和和C C，D D。设有一个查询可用关系代数表达式表示：设有一个查询可用关系代数表达式表示： E1= E1= A A（ B=CD=99B=CD=99（R R S S） 也可以把选择条件也可以把选择条件D=D=9999移到笛卡儿积中的关系移到笛卡儿积中的关系S S前面：前面： E2= E2= A A（ B=CB=C（R R D=99D=99（S S） 还可以把选择条件还可以把选择条件B BC C与笛卡儿积结合成等值连接形式：与笛卡儿积结合成等值连接形式： E3= E3= A A
63、（R R B=C B=C D=99D=99（S S）这三个关系代数表达式是等价的，但执行的效率大不一样。这三个关系代数表达式是等价的，但执行的效率大不一样。显然，求显然，求ElEl，E2E2，E3E3的大部分时间是花在连接操作上的。的大部分时间是花在连接操作上的。E3E3（目的：减少内外存交换的信息量目的：减少内外存交换的信息量） 花费的时间：花费的时间：E1E2E3 E1E2E3 查询优化查询优化导致查询低效的原因导致查询低效的原因n冗余计算冗余计算n内外存交换次数太多内外存交换次数太多提高效率的途径（启发式优化的目标）提高效率的途径（启发式优化的目标）n减少中间结果的大小减少中间结果的大小
64、n减少不相关的数据运算减少不相关的数据运算n减少扫描表的次数减少扫描表的次数n减少不相关元组的读取减少不相关元组的读取查询优化查询优化逻辑优化的一般准则逻辑优化的一般准则1）选择操作尽可能先做目的：大大减少中间结果的大小2）执行连接前对关系适当地预处理两种预处理方法：在连接属性上建立索引和对关系排序目的：n减少扫描表的次数n减少不相关元组的读取实例实例例如：例如：SSC.两种预处理方法：两种预处理方法：n索引连接方法：索引连接方法：n(1)在在SC上建立上建立S#的索的索引；引；n(2)对对S中的每一个元组，中的每一个元组，由由S#值通过值通过SC的索引的索引查找相应的查找相应的SC元组；元组
65、；n(3)把这些把这些SC元组和元组和S元元组连接起来；组连接起来；n效率效率：S和和SC表均只要表均只要扫描一遍。处理时间是扫描一遍。处理时间是两个关系大小的线性函两个关系大小的线性函数。数。排序连接方法：排序连接方法：(1)(1)对对S S和和SCSC按按S#S#排序；排序；(2)(2)取取S S表表中中第第一一个个S#S#，依依次次扫扫描描SCSC表表中中具具有有相相同同S#S#的的元组，把它们连接起来；元组，把它们连接起来；(3)(3)当当扫扫描描到到S#S#不不相相同同的的第第一一个个SCSC元元组组时时，返返回回S S表表扫扫描描它它的的下下一一个个元元组组，再再扫扫描描SCSC表
66、表中中具具有有相相同同S#S#的的元元组组，把它们连接起来；把它们连接起来；效效率率：S S和和SCSC表表均均只只要要扫扫描描一一遍遍。处处理理时时间间要要加加上上对对两两个表排序的时间。个表排序的时间。查询优化查询优化逻辑优化的一般准则逻辑优化的一般准则3）投影运算和选择运算同时进行目的：避免重复扫描表4）投影同其前或其后的双目运算结合起来目的：避免重复扫描表查询优化查询优化逻辑优化的一般准则逻辑优化的一般准则5）把某些选择同在它前面要执行的笛卡尔积结合起来成为一个连接运算目的：减少内外存交换的信息量6）找出公共子表达式目的：减少计算量关系代数表达式的优化(2)例：求选修了课程例：求选修了
67、课程2的学生姓名的学生姓名假设假设1：外存：外存：S:1000条条,SC:10000条条,选修选修2号课程号课程:50条条假设假设2：一个内存块：一个内存块装元组装元组:10个个S,或或100个个SC,内存中内存中一次可以存放一次可以存放:5块块S元组元组,1块块SC元组和若干块连接结元组和若干块连接结果元组果元组假设假设3：读写速度：读写速度：20块块/秒秒假设假设4：连接方法：连接方法：基于数据块基于数据块的嵌套循环法的嵌套循环法关系代数表达式的优化（3）1sname(S.S#=SC.S#SC.C#=2(SSC)SSC读取总块数读取总块数=读读S表块数表块数+读读SC表遍数表遍数*每遍块数
68、每遍块数=1000/10+(1000/(105)(10000/100)=100+20100=2100读数据时间读数据时间=2100/20=105秒秒关系代数表达式的优化（4）中间结果大小=1000*10000=107(1千万条元组)写中间结果时间写中间结果时间=10000000/10/20=50000秒读数据时间读数据时间=50000秒总时间总时间=1055000050000秒=100105秒=27.8小时关系代数表达式的优化（5）2.2name(SC.C#=2(SSC)读取总块数读取总块数=2100块块读数据时间读数据时间=2100/20=105秒秒中间结果大小中间结果大小=10000（减少
69、（减少1000倍）倍）写中间结果时间写中间结果时间=10000/10/20=50秒秒读数据时间读数据时间=50秒秒总时间总时间1055050秒秒205秒秒=3.4分分关系代数表达式的优化（6）3.3Sname(SSC.C#=2(SC)读读SC表总块数表总块数=10000/100=100块块读数据时间读数据时间=100/20=5秒秒中间结果大小中间结果大小=50条条不必写入外存不必写入外存读读S表总块数表总块数=1000/10=100块块读数据时间读数据时间=100/20=5秒秒总时间总时间55秒秒10秒秒关系代数表达式的优化（7）4.4name(SSC.C#=2(SC)假设假设SC表在表在C#
70、上有索引，上有索引，S表在表在S#上有索引上有索引 读读SC表索引表索引=读读SC表总块数表总块数=50/1001块块读数据时间读数据时间中间结果大小中间结果大小=50条条不必写入外存不必写入外存关系代数表达式的优化（8） 读读S表索引表索引=读读S表总块数表总块数=50/10=5块块读数据时间读数据时间=5/20总时间总时间10秒秒关系代数表达式的等价变换规则(1)n连接和笛卡儿积的交换律E1E2 E2E1E1E2 E2E1E1E2 E2E1n连接和笛卡儿积的结合律(E1E2)E3E1(E2E3)(E1E2)E3E1(E2E3)(E1E2)E3E1(E2E3)FFF2F2F1F1关系代数表达
71、式的等价变换规则(1)n投影的级联L1(L2(Ln(E)L1(E)n选择的级联F1(F2(E)F1F2(E)F2F1(E)n选择和投影操作的交换L(F(E)L(F(LL1(E)L(F(E)F(L(E)关系代数表达式的等价变换规则(1)n选择对笛卡儿积的分配律 F=F1F2F(E1E2)F(E1)E2F(E1E2)F1(E1)F2(E2)F(E1E2)F2(F1(E1)E2)n选择对并的分配律F(E1E2)F(E1)F(E2)关系代数表达式的等价变换规则(2)n选择对集合差的分配律F(E1E2)F(E1)F(E2)F(E1E2)F(E1)E2n选择对自然连接的分配律F(E1E2)F(E1)F(E
72、2)这里要求这里要求F只涉及只涉及E1和和E2的的公共属性公共属性n投影对笛卡儿积的分配律L1L2(E1E2)L1(E1)L2(E2)关系代数表达式的等价变换规则(2)n投影对并的分配律L(E1E2)L(E1)L(E2)n选择与连接操作的结合F(E1E2)E1E2F1(E1E2)E1E2FF2F1F2关系代数表达式的等价变换规则(2)n并和交的交换律(E1E2)(E2E1)(E1E2)(E2E1)n并和交的结合律(E1E2)E3E1(E2E3)(E1E2)E3E1(E2E3)关系代数表达式的优化算法(1) 在关系代数表达式中，最花费时间和空间在关系代数表达式中，最花费时间和空间的运算是笛卡儿积
73、和连接操作，为此，引出三的运算是笛卡儿积和连接操作，为此，引出三条启发式规则，用于对表达式进行转换，以减条启发式规则，用于对表达式进行转换，以减少中间关系的大小。少中间关系的大小。n 尽可能早地执行选择操作；尽可能早地执行选择操作；n 尽可能早地执行投影操作；尽可能早地执行投影操作；n 避免直接做笛卡儿积，把笛卡儿积操作之前避免直接做笛卡儿积，把笛卡儿积操作之前和之后的一连串选择和投影合并起来一起做。和之后的一连串选择和投影合并起来一起做。关系代数表达式的优化算法(2)n算法算法2.12.1 关关系系代代数数表表达达式式的的启启发发式式优优化化算法。算法。 输入：一个关系代数表达式的语法树输入
74、：一个关系代数表达式的语法树 输出：计算表达式的一个优化序列输出：计算表达式的一个优化序列n例例2.232.232.5 关系逻辑(自学) 关系逻辑和关系代数在表达功能上相关系逻辑和关系代数在表达功能上相差甚大，只有在规则被约束为安全的、非差甚大，只有在规则被约束为安全的、非递归、在带有某些否定的情况下，关系逻递归、在带有某些否定的情况下，关系逻辑才与关系代数等价。由于关系逻辑中引辑才与关系代数等价。由于关系逻辑中引进了基于逻辑的规则概念，使得关系逻辑进了基于逻辑的规则概念，使得关系逻辑比关系代数在模拟现实世界能力方面更强。比关系代数在模拟现实世界能力方面更强。关系逻辑一般用在知识库的知识表达中
75、。关系逻辑一般用在知识库的知识表达中。小结n关系模型的基本术语关系模型的基本术语n关系模型的三类完整性规则关系模型的三类完整性规则n关系模型的三级体系结构关系模型的三级体系结构n关关系系代代数数的的五五个个基基本本操操作作、四四个个组组合合操操作作、七七个个扩扩充充操操作作、用用关关系系代代数数表表达达式式表表示示数数据据查查询询操作（教材中操作（教材中P49P49的例的例2.62.6）。）。重要内容分析（一）（1）一般规则）一般规则对对于于只只涉涉及及到到选选择择、投投影影、连连接接的的查查询询可可用用下下列表达式表示：列表达式表示：（RS） 或者或者（R S）对对于于否否定定的的操操作作，
76、一一般般要要用用差差操操作作表表示示，例例如如“检索不学检索不学C2课的学生姓名课的学生姓名”。对于检索具有对于检索具有“全部全部”特征的操作，一般要用特征的操作，一般要用除法操作表示，例如除法操作表示，例如“检索学习全部课程的学检索学习全部课程的学生姓名生姓名”。重要内容分析（二）（2）“检检索索不不学学C2课课的的学学生生姓姓名名”，决决不不能能用用下下式表示：式表示： SNAME，AGE（C#C2（S SC） 一定要用一定要用“差差”的形式：的形式： SNAME，AGE（S）SNAME，AGE（C#=C2（S SC）（3）“检索学习全部课程的学生学号检索学习全部课程的学生学号”，要用，要用 S#，C#（SC）C#（C）表示，表示， 重要内容分析（三）2非过程性语言与过程性语言的区别非过程性语言与过程性语言的区别编编程程时时必必须须指指出出“干干什什么么”及及“怎怎么么干干”的的语语言言，称称为为过过程程性性语语言言；编编程程时时只只须须指指出出“干干什什么么”，不不必必指指出出“怎怎么么干干”的语言，称为非过程性语言。的语言，称为非过程性语言。
