第三章 关系运算精选文档.ppt

《第三章 关系运算精选文档.ppt》由会员分享，可在线阅读，更多相关《第三章 关系运算精选文档.ppt（63页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第三章 关系运算本讲稿第一页，共六十三页第三章第三章 关系运算关系运算教学内容：教学内容：教学内容：教学内容：l l基本概念：基本概念：基本概念：基本概念：关系代数：关系代数：关系代数：关系代数：关系演算：关系演算：关系演算：关系演算：l l查询优化：查询优化：查询优化：查询优化：关系模型、关键码、关系的定义和性质、关系模型、关键码、关系的定义和性质、关系模型、关键码、关系的定义和性质、关系模型、关键码、关系的定义和性质、三类完整性规则。三类完整性规则。三类完整性规则。三类完整性规则。基本操作、组合操作、扩充操作。基本操作、组合操作、扩充操作。基本操作、组合操作、扩充操作。基本操作、组合操作、

2、扩充操作。元组演算、域演算、关系演算的安全性和等价性。元组演算、域演算、关系演算的安全性和等价性。元组演算、域演算、关系演算的安全性和等价性。元组演算、域演算、关系演算的安全性和等价性。关系代数表达式的等价转换规则、优化算法。关系代数表达式的等价转换规则、优化算法。关系代数表达式的等价转换规则、优化算法。关系代数表达式的等价转换规则、优化算法。教学重点：教学重点：关系代数运算关系代数运算本讲稿第二页，共六十三页11关系数据模型关系数据模型关系数据模型关系数据模型的基本概念的基本概念的基本概念的基本概念一、基本术语一、基本术语一、基本术语一、基本术语 用用用用二维表格二维表格二维表格二维表格表示

3、实体集，表示实体集，表示实体集，表示实体集，外键外键外键外键表示实体间联系的模型称为关系模型；表示实体间联系的模型称为关系模型；表示实体间联系的模型称为关系模型；表示实体间联系的模型称为关系模型；关系：关系：关系：关系：对应二维表格；对应二维表格；对应二维表格；对应二维表格；元组：元组：元组：元组：表中的行；表中的行；表中的行；表中的行；属性：属性：属性：属性：表中的列；表中的列；表中的列；表中的列；域：域：域：域：属性的取值范围。属性的取值范围。属性的取值范围。属性的取值范围。本讲稿第三页，共六十三页 二、数学定义二、数学定义二、数学定义二、数学定义 定义一：定义一：定义一：定义一：域（域（

4、域（域（DomainDomainDomainDomain）是值的集合。即域是属性的取值范围。）是值的集合。即域是属性的取值范围。）是值的集合。即域是属性的取值范围。）是值的集合。即域是属性的取值范围。定义二：定义二：定义二：定义二：关系的定义关系的定义关系的定义关系的定义 用集合论的观点定义关系：用集合论的观点定义关系：用集合论的观点定义关系：用集合论的观点定义关系：用值域的观点定义关系：用值域的观点定义关系：用值域的观点定义关系：用值域的观点定义关系：关系是一个元数为关系是一个元数为关系是一个元数为关系是一个元数为K K K K的元组的集合。的元组的集合。的元组的集合。的元组的集合。即这个关

5、系中有若干个元组，每个元组有即这个关系中有若干个元组，每个元组有即这个关系中有若干个元组，每个元组有即这个关系中有若干个元组，每个元组有K K K K个属性值。个属性值。个属性值。个属性值。把关系看成一个集合，集把关系看成一个集合，集把关系看成一个集合，集把关系看成一个集合，集合中的元素是元组。合中的元素是元组。合中的元素是元组。合中的元素是元组。关系是属性值域笛卡儿积的一个子集。关系是属性值域笛卡儿积的一个子集。关系是属性值域笛卡儿积的一个子集。关系是属性值域笛卡儿积的一个子集。本讲稿第四页，共六十三页三、关系的性质三、关系的性质三、关系的性质三、关系的性质11、列具有相同的性质，不同的列可

6、有相同的域，、列具有相同的性质，不同的列可有相同的域，、列具有相同的性质，不同的列可有相同的域，、列具有相同的性质，不同的列可有相同的域，22、任意两个元组不能相同，元组的次序可交换；、任意两个元组不能相同，元组的次序可交换；、任意两个元组不能相同，元组的次序可交换；、任意两个元组不能相同，元组的次序可交换；33、每个属性值、每个属性值、每个属性值、每个属性值(分量分量分量分量)都是不可分的数据项都是不可分的数据项都是不可分的数据项都是不可分的数据项(即属性即属性即属性即属性值为最小单位值为最小单位值为最小单位值为最小单位).).本讲稿第五页，共六十三页四、关键码四、关键码超超键：键：侯选键：

7、侯选键：主键：主键：外键：外键：能唯一标识元组的属性组合（可能存在多余的属性）。能唯一标识元组的属性组合（可能存在多余的属性）。能唯一标识元组的最小属性组合。能唯一标识元组的最小属性组合。不含有多余属性的超不含有多余属性的超键键若一个关系中有多个侯选键若一个关系中有多个侯选键,则选其中的一个为关系的主键。则选其中的一个为关系的主键。若某个属性组若某个属性组F F是关系是关系R R的主键的主键,F,F又在关系又在关系S S中出现中出现,则则F F是是S S的外键的外键.若一个关系若一个关系R R中包含有另一个关系中包含有另一个关系S S的主键所对应的属性的主键所对应的属性组组F F，则称则称F

8、F为为R R的外键。称关系的外键。称关系S S为参照关系，为参照关系，R R为依赖为依赖关系。关系。本讲稿第六页，共六十三页 五、五、关系模型的三类完整性规则关系模型的三类完整性规则实体完整性规则：实体完整性规则：实体完整性规则：实体完整性规则：参照完整性规则：参照完整性规则：参照完整性规则：参照完整性规则：用户定义的完整性规则：用户定义的完整性规则：用户定义的完整性规则：用户定义的完整性规则：若若某某个个属属性性组组F F是是关关系系R R的的主主键键,F,F又又在在关关系系S S中中出出现现,则则F F是是S S的的外外键键.F.F在在S S中中的的取取值值只只有有两两种种可可能能,一一为

9、为空空,二二为为R R中中的的某个主键值某个主键值通过外键通过外键子句来实现子句来实现(foreign key)(foreign key)。由应用环境决定，反映某一具体应用由应用环境决定，反映某一具体应用 涉及的数据必须满足的约束条件。涉及的数据必须满足的约束条件。关系中元组的主键值不能为空且不能重复。关系中元组的主键值不能为空且不能重复。通过主键子句来实现通过主键子句来实现(primary key)(primary key)本讲稿第七页，共六十三页六、关系模型的形式定义六、关系模型的形式定义(有三个组成部分)数据结构：数据结构：数据操作：数据操作：完整性规则：完整性规则：数数据据库库中中全全

10、部部数数据据及及其其相相互互联联系系都都被被组组织织成成关系（即二维表格）的形式。关系（即二维表格）的形式。提供了一组完备的高级关系运算，以支持提供了一组完备的高级关系运算，以支持对数据库的各种操作。关系运算分为关系对数据库的各种操作。关系运算分为关系代数和关系演算两类。代数和关系演算两类。三类完整性规则三类完整性规则本讲稿第八页，共六十三页2关系代数关系代数一、一、关系数据语言关系数据语言关系数据库语言由查询语句（描述用户的检索操作）和更新关系数据库语言由查询语句（描述用户的检索操作）和更新语句（描述用户的插入、修改和删除等操作）两大类组成。语句（描述用户的插入、修改和删除等操作）两大类组成

11、。关系查询语言分为：关系查询语言分为：关系代数语言：关系代数语言：关系演算语言：关系演算语言：基于关系代数和关系演算语言双重特点的语言：基于关系代数和关系演算语言双重特点的语言：以集合操作为基础；以集合操作为基础；以谓词演算为基础；以谓词演算为基础；元组关系演算语言元组关系演算语言 域关系演算语言域关系演算语言SQLSQL本讲稿第九页，共六十三页二、关系代数的基本运算二、关系代数的基本运算二、关系代数的基本运算二、关系代数的基本运算1.1.1.1.并并并并（unionunionunionunion）：）：）：）：设关系设关系设关系设关系R R R R和关系和关系和关系和关系S S S S具有相

12、同的元数，且相应的具有相同的元数，且相应的具有相同的元数，且相应的具有相同的元数，且相应的 属性列具有相同的特征：属性列具有相同的特征：属性列具有相同的特征：属性列具有相同的特征：RStRSttRtStRtS 其中：其中：其中：其中：t t t t是元组变量，是元组变量，是元组变量，是元组变量，R R R R和和和和S S S S的元数相同。的元数相同。的元数相同。的元数相同。并并并并运运运运算算算算要要要要求求求求两两两两个个个个关关关关系系系系属属属属性性性性的的的的性性性性质质质质必必必必须须须须一一一一致致致致且且且且并并并并运运运运算算算算的的的的结结结结果果果果要要要要消消消消除重

13、复的元组。除重复的元组。除重复的元组。除重复的元组。举例：举例：本讲稿第十页，共六十三页 2.2.2.2.差差差差(differedce)(differedce)(differedce)(differedce)：设关系设关系设关系设关系R R R R和关系和关系和关系和关系S S S S具有相同的元数，具有相同的元数，具有相同的元数，具有相同的元数，且相应的属性列具有相同的特征：且相应的属性列具有相同的特征：且相应的属性列具有相同的特征：且相应的属性列具有相同的特征：RStRSttRttRt SS 其中：其中：其中：其中：t t t t是元组变量，是元组变量，是元组变量，是元组变量，R R R

14、 R和和和和S S S S的元数相同。的元数相同。的元数相同。的元数相同。举例：举例：本讲稿第十一页，共六十三页3.3.3.3.笛卡儿积（笛卡儿积（笛卡儿积（笛卡儿积（cartesian productcartesian productcartesian productcartesian product）设设设设关关关关系系系系R R R R和和和和关关关关系系系系S S S S的的的的元元元元数数数数分分分分别别别别为为为为r r r r和和和和s s s s。定定定定义义义义R R R R和和和和S S S S的的的的笛笛笛笛卡卡卡卡儿儿儿儿积积积积RSRSRSRS是是是是一一一一个个个个

15、（r+sr+sr+sr+s）元元元元的的的的元元元元组组组组集集集集合合合合，每每每每个个个个元元元元组组组组的的的的前前前前r r r r个个个个分分分分量量量量（属属属属性性性性值值值值）来来来来自自自自R R R R的的的的一一一一个元组，后个元组，后个元组，后个元组，后s s s s个分量是个分量是个分量是个分量是S S S S的一个元组，记为的一个元组，记为的一个元组，记为的一个元组，记为RSRSRSRS。形式定义如下：形式定义如下：形式定义如下：形式定义如下：RStRStt=tt=ttr rRtRts sSS 若若若若R R R R有有有有n n n n个元个元个元个元组组组组，S

16、 S S S有有有有m m m m个元个元个元个元组组组组，则则则则RSRSRSRS有有有有nmnmnmnm个元个元个元个元组组组组。举例：举例：本讲稿第十二页，共六十三页 4.4.投影（投影（projectionprojection）：）：对一个关系进行垂直分割对一个关系进行垂直分割,消去某些列，消去某些列，并重新安排列的顺序并重新安排列的顺序,再删去重复元组。再删去重复元组。i1,imi1,im(R)t|t=t(R)t|t=tRR,1,1 m m k k 设设关关系系R R是是k k元元关关系系，R R在在其其分分量量A Ai1i1,A,Aimim(mk,(mk,i1,i1,im,im为为

17、1 1到到k k之之间间的的整整数数)上上的的投投影影用用i1i1,imim（R R）表表示示，它它是是从从R R中中选选择择若若干干属属性性列组成的一个列组成的一个m m元元组的集合，形式定义如下：元元组的集合，形式定义如下：举例：举例：本讲稿第十三页，共六十三页 5.5.选择选择(selection)(selection)根据某些条件对关系做水平分割根据某些条件对关系做水平分割,选择符合条件的元组。选择符合条件的元组。条件用命题公式条件用命题公式F F（即计算在括号中的条件表达式）（即计算在括号中的条件表达式）表示表示.F F中的运算对象中的运算对象:常量常量(用引号括起来）用引号括起来）

18、,元组分量（属性名或列的序号），元组分量（属性名或列的序号），算术比较运算符算术比较运算符:，,逻辑运算符逻辑运算符:，。关系关系R R关于公式关于公式F F的选择操作用的选择操作用F F（R R）表示，形式定义如下：）表示，形式定义如下：F F（R R）=t|tRF(t)=t|tRF(t)=T T 举例：举例：本讲稿第十四页，共六十三页 三、关系代数的组合操作三、关系代数的组合操作 1 1、交（、交（intersectionintersection）设设关关系系R R和和关关系系S S具具有有相相同同的的元元数数n n（即即两两个个关关系系都都有有n n个个属属性性），而而且且相相应应的的属

19、属性性取取自自同同一一个个域域。关关系系R R和和S S的的交交记记为为RSRS，结结果果仍仍为为n n元元的的关关系系。由由即属于即属于R R又属于又属于S S的元组组成。形式定义如下：的元组组成。形式定义如下：RStRSttRtStRtS t t是元组变量，是元组变量，R R和和S S的元数相同。的元数相同。关系的交可以由关系的差来表示，即：关系的交可以由关系的差来表示，即：RSR-RSR-（R-SR-S）举例举例:本讲稿第十五页，共六十三页 2 2、联接联接(join)(join)联接操作是笛卡儿积、选择和投影操作的组合。联接操作是笛卡儿积、选择和投影操作的组合。联接分成联接分成联接和联

20、接和F F联接两种。联接两种。联接：联接：F F 联接：联接：ijij R S R S i(r+j)i(r+j)(RS)(RS)如果如果为等号为等号“=”，那么这个联结操作称为等值连接。，那么这个联结操作称为等值连接。F F F F联联接接是是从从关关系系R R和和S S的的笛笛卡卡儿儿积积中中选选取取属属性性间间满满足足某一公式某一公式F F的元组的元组,记为记为:R SR S 这里这里F F是形为是形为F1F2F1F2FnFn公式，每个公式，每个FiFi是形为是形为ijij的式子。的式子。而而i i和和j j分别为关系分别为关系R R和和S S的第的第i i个分量和第个分量和第j j个分量

21、的序号。个分量的序号。举例：举例：本讲稿第十六页，共六十三页 3 3、自然联接、自然联接(natural join)-(natural join)-特殊的等值连接特殊的等值连接 将关系将关系R R和和S S中公共属性组满足对应分量相等的元组中公共属性组满足对应分量相等的元组 联接起来，联接起来，并且要在结果中将重复的属性去掉。并且要在结果中将重复的属性去掉。R R SSi1,.imi1,.im(R.A1=S.A1.R.AK=S.AKR.A1=S.A1.R.AK=S.AK(RS)(RS)举例：举例：本讲稿第十七页，共六十三页 4 4、除除(division)(division)设关系设关系R R

22、和和S S的元数分别为的元数分别为:r:r、s s（rs0rs0），），RS:RS:是一个（是一个（r-sr-s）元的元组的集合，）元的元组的集合，是满足下列条件的最大关系：是满足下列条件的最大关系：其中每个元组其中每个元组t t与与S S中每个元组中每个元组u u组成的组成的 新元组新元组必在关系必在关系R R中。中。本讲稿第十八页，共六十三页 RSRS的具体的具体计计算算过过程如下：程如下：T=T=1，2，r-s（R R）W=(TS)-R W=(TS)-R V=V=1，2，r-s（W W）RS=T RS=T V V RS RS1,2,r-s(R)-(R)-1,2,r-s(1,2,r-s(R

23、)S)-R)(R)S)-R)举例：举例：本讲稿第十九页，共六十三页四、关系代数表达式及其应用实例四、关系代数表达式及其应用实例本讲稿第二十页，共六十三页 工程项目零件供应数据库工程项目零件供应数据库PROJECTYPROJECTY有四个关系模式：有四个关系模式：供应商关系：供应商关系：S(S(SNOSNO,SNAME,SADDR),SNAME,SADDR)零件关系：零件关系：P(P(PNO,PNO,PNAME,COLOR,WEIGHT)PNAME,COLOR,WEIGHT)工程项目关系：工程项目关系：J(J(JNOJNO,JNAME,JCITY,BALANCE),JNAME,JCITY,BAL

24、ANCE)供应情况关系：供应情况关系：SPJ(SPJ(SNO,PNO,JNOSNO,PNO,JNO,PRICE,QTY),PRICE,QTY)SN0,PN0SN0,PN0(JNO=JNO=J1J1(SPJ)(SPJ)或或:l,2l,2(3=J13=J1(SPJ)(SPJ)试用关系代数表达式表示每个查询语句。试用关系代数表达式表示每个查询语句。.检索供应零件给工程检索供应零件给工程J1J1的供应商编号的供应商编号SNOSNO与零件编号与零件编号PNOPNO。本讲稿第二十一页，共六十三页SNOSNO（JNO=J1 PNO=P1JNO=J1 PNO=P1（SPJSPJ）3.3.检索使用了编号为检索使

25、用了编号为P3P3零件的工程编号和名称。零件的工程编号和名称。2.2.检索供应零件给工程检索供应零件给工程J1J1，且零件编号为，且零件编号为P1P1的供应商编号的供应商编号SNOSNO。4.4.检索供应零件给工程检索供应零件给工程J1,J1,且零件颜色为红色的供应商名称和地址。且零件颜色为红色的供应商名称和地址。5.5.检索使用了零件编号为检索使用了零件编号为P3P3或或P5P5零件的工程编号零件的工程编号JNOJNO。JNO,JNAMEJNO,JNAME（PNO=P3PNO=P3（J J SPJ)SPJ)SNAME,SADDRSNAME,SADDR(JNO=J1 COLOR=JNO=J1

26、COLOR=红色红色(S(S SPJSPJ P)P)JNOJNO（PNO=P3PNO=P5PNO=P3PNO=P5(SPJSPJ)本讲稿第二十二页，共六十三页6.6.检索至少使用了编号为检索至少使用了编号为P3P3和和P5P5 零件的工程编号零件的工程编号JNOJNO。3 3（3=82=P37=P53=82=P37=P5(SPJSPJSPJSPJ)7.7.检索不使用编号为检索不使用编号为P3P3零件的工程编号零件的工程编号JNOJNO和工程名称和工程名称JNAMEJNAME。JNO,JNAMEJNO,JNAME(J)(J)JNO,JNAMEJNO,JNAME(PNO=PNO=P3P3(J(J

27、SPJ)SPJ)8.8.检索使用了全部零件的工程名称检索使用了全部零件的工程名称JNAMEJNAME。JNAMEJNAME(J(J(JNO,PNOJNO,PNO(SPJ)(SPJ)PNOPNO(P)(P)9.9.检索使用零件包含编号为检索使用零件包含编号为S1S1的供应商所供应的全部零件的工程的供应商所供应的全部零件的工程 编号编号JNOJNO。JNO,PNOJNO,PNO(SPJ)(SPJ)PNOPNO(SNO=S1SNO=S1(SPJ)(SPJ)本讲稿第二十三页，共六十三页举例举例 假设学生数据库中的关系模式如下：假设学生数据库中的关系模式如下：S（SNO,SNAME,AGE,SEX,SD

28、EPT）C（CNO,CNAME,CDEPT,TNAME）SC（SNO,CNO,GRADE）试用关系代数表达式表示每个查询语句。试用关系代数表达式表示每个查询语句。.检索计算机系的全体学生的学号、姓名和性别。检索计算机系的全体学生的学号、姓名和性别。2.2.检索学习课程号为检索学习课程号为C2C2的学生的学号和姓名。的学生的学号和姓名。3.3.检索选修课程名为检索选修课程名为“数据结构数据结构”的学生的学号和姓名。的学生的学号和姓名。4.4.检索选修课程号为检索选修课程号为C2C2或或C4C4的学生的学号。的学生的学号。5.5.检索至少选修课程号为检索至少选修课程号为C2C2和和C4C4的学生的

29、学号。的学生的学号。本讲稿第二十四页，共六十三页7.7.检索选修了全部课程的学生的姓名和所在系。检索选修了全部课程的学生的姓名和所在系。6.6.检索没有选修检索没有选修C2C2课程的学生的姓名和年龄。课程的学生的姓名和年龄。8.8.检索选修课程包含学生检索选修课程包含学生S2S2所选的全部课程的学生的学号。所选的全部课程的学生的学号。9.9.将新课程将新课程 插入到课程表插入到课程表C C中。中。10.10.将学号为将学号为S4S4所选修的所选修的C4C4课程的成绩修改为课程的成绩修改为8585分。分。本讲稿第二十五页，共六十三页五、扩充的关系代数操作五、扩充的关系代数操作 1.1.外外联联接

30、（接（outer joinouter join）R R SSi1,.imi1,.im(R.A1=S.A1.R.AK=S.AKR.A1=S.A1.R.AK=S.AK(RS)(RS)在在R R和和S S做做自自然然联联接接时时，把把原原该该舍舍弃弃的的元元组组也也保保留留在在新新关关系系中中，同同时时在在这这些些元元组组新新增增加加的的属属性性上上填填上上空空值值（nullnull），这这种种操操作作称称为为“外联接外联接”操作操作，用符号，用符号R SR S表示。表示。本讲稿第二十六页，共六十三页i i、如果、如果R R和和S S做自然做自然联联接接时时，把把R R中原中原该该舍弃的元舍弃的元组

31、组放放 到新关系中到新关系中，那么，那么这这种操作称种操作称为为“左外左外联联接接”操作，操作，用符号用符号:R S:R S表示。表示。iiii、如果、如果R R和和S S做自然联接时，做自然联接时，把把S S中原该舍弃的元组中原该舍弃的元组 放到新关系中放到新关系中，那么这种操作称为，那么这种操作称为“右外联接右外联接”操作，操作，用符号用符号:R S:R S表示。表示。本讲稿第二十七页，共六十三页A AB BC Ca ab bc cb bb bf fc ca ad dB BC CD Db bc cd db bc ce ea ad db be ef fg gA AB BC CD Da ab

32、bc cd da ab bc ce ec ca ad db bb bb bf fnullnullnullnulle ef fg g关系关系R R关系关系S SA AB BC CD Da ab bc cd da ab bc ce ec ca ad db bb bb bf fnullnullA AB BC CD Da ab bc cd da ab bc ce ec ca ad db bnullnulle ef fg g本讲稿第二十八页，共六十三页 2.2.外部并（外部并（outer unionouter union）如如果果R R和和S S的的关关系系模模式式不不同同，构构成成的的新新关关系系属属

33、性性有有R R和和S S的的所所有有属属性性组组成成（公公共共属属性性只只取取一一次次），新新关关系系的的元元组组由由属属于于R R或或属属于于S S的的元元组组构构成成，同同时时元元组在新增加的属性上填上空值组在新增加的属性上填上空值(null)(null)。A AB BC CD Da ab bc cnullnullb bb bf fnullnullc ca ad dnullnullnullnullb bc cd dnullnullb bc ce enullnulla ad db bnullnulle ef fg g本讲稿第二十九页，共六十三页 3.3.半联接（半联接（semijoinsem

34、ijoin）关系关系R R和和S S的半联接操作记为的半联接操作记为R R S S:R R和和S S的自然联接在关系的自然联接在关系R R的属性集上的投影的属性集上的投影即：即：R R S S R R（R R S S）本讲稿第三十页，共六十三页关系关系R R关系关系S SR R S SR R S SS S R RA A B B C C D Da a b b c c d da a b b c c e ed d b b c c d dd d b b c c e ec c a a d d b bA A B B C Ca a b b c cd d b b c cc c a a d dB B C C D

35、 Db b c c d db b c c e ea a d d b bB B C C D Db b c c d db b c c e ea a d d b bA A B B C Ca a b b c cd d b b c cb b b b f fc c a a d d本讲稿第三十一页，共六十三页4关系演算关系演算 以数理逻辑中的谓词演算为基础，用公式表示关系演算的条件。以数理逻辑中的谓词演算为基础，用公式表示关系演算的条件。关系演算按所用到的变量不同可分为：关系演算按所用到的变量不同可分为：元组关系演算以元组为变量；元组关系演算以元组为变量；域关系演算域关系演算 以域为变量。以域为变量。一、元

36、组关系演算一、元组关系演算 形式：形式：tt(t)(t)其中其中 t t：元组变量；：元组变量；：公式，公式有原子公式及运算符组成。公式，公式有原子公式及运算符组成。本讲稿第三十二页，共六十三页 1.1.原子公式有下列三种形式：原子公式有下列三种形式：R R（t t）：）：R R 是关系名，是关系名，t t 是元组变量。是元组变量。tiuj:tiuj:t t 和和 u u是元组变量，是元组变量，是算术比较运算符。是算术比较运算符。tiC tiC 或或 Cui Cui：t t 和和 u u 是元组变量，是元组变量，c c 是常量。是常量。2.2.约束变量和自由变量约束变量和自由变量 在在一一个个

37、公公式式中中，如如果果一一个个元元组组变变量量的的前前面面没没有有存存在在量量词词或或全全称称量量词词 的的符号符号定义，称之为定义，称之为自由元组变量自由元组变量，否则称为约束元组变量。，否则称为约束元组变量。本讲稿第三十三页，共六十三页 3 3.运算符及优先次序为：运算符及优先次序为：i.i.括号中运算符优先级最高括号中运算符优先级最高 ii.ii.算术比较运算符最高；算术比较运算符最高；iii.iii.量词量词 ：存在量词：存在量词 全称量词全称量词 iv.iv.逻辑运算符：逻辑运算符：、优先级最高本讲稿第三十四页，共六十三页 4.4.公式中变量的递归定义如下：公式中变量的递归定义如下：

38、每个原子公式是一个公式。其中的元组变量是自由变量每个原子公式是一个公式。其中的元组变量是自由变量;如果如果 1 1和和 2 2是元是元组组关系演算公式，关系演算公式，则则:11 2,2,11 2,2,1 1也是元也是元组组关系演算公式关系演算公式;若若 是是元元组组关关系系演演算算公公式式，则则(t)(t)()也也是是元元组组关关系系演演算算公公式式;若若 是元组关系演算公式，则是元组关系演算公式，则(t)(t)()也是元组关系演算公式也是元组关系演算公式;在元组演算公式中，各种运算符的优先次序为：在元组演算公式中，各种运算符的优先次序为：括号括号,算术比较运算符算术比较运算符,、有限次地使用

39、上述五条规则得到的公式是元组关系演算公式，有限次地使用上述五条规则得到的公式是元组关系演算公式，其他公式不是元组关系演算公式。其他公式不是元组关系演算公式。本讲稿第三十五页，共六十三页5.5.用元用元组组关系演算表达式表示关系运算关系演算表达式表示关系运算并并:RS:RS t|R t|R（t t）S(t)S(t)差差:R-S:R-S t|R t|R（t t）S(t)S(t)笛卡儿积笛卡儿积:RS:RS t|(t|(u)(u)(v)(R(u)S(v)t1=u1v)(R(u)S(v)t1=u1 tr=urtr+1=v1 tr=urtr+1=v1 tr+s=vs)tr+s=vs)投影投影:i1,i2

40、,i1,i2,ikik(R)(R)t|(t|(u)|R(u)tl=uiu)|R(u)tl=ui1 1tiK=uiK tiK=uiK 选择选择:F F（R R）t|R(t)F t|R(t)F F F是是F F在元组演算中的等价表示形式。在元组演算中的等价表示形式。本讲稿第三十六页，共六十三页如果如果P1和和P2是公式，是公式，在元组关系演算的公式中，存在下列等价转换规则：在元组关系演算的公式中，存在下列等价转换规则：P1P2(P1P2)P1P2(P1P2）(s)(P1(s)(s)(P1(s)(s)(P1(s)(s)(P1(s)P1P2 P1P2本讲稿第三十七页，共六十三页6.实例实例:用元组表达

41、式形式表示下列查询用元组表达式形式表示下列查询本讲稿第三十八页，共六十三页例例:用元组表达式形式表示下列查询：用元组表达式形式表示下列查询：1.1.检索供应零件给工程检索供应零件给工程J1J1，且零件编号为，且零件编号为P1P1的供应商编号的供应商编号SNOSNO。t|(t|(u)(SPJ(u)u)(SPJ(u)u2=u2=P1P1u3=u3=J1J1tl=u1)tl=u1)2.2.检索使用了编号为检索使用了编号为P3P3零件的工程编号和名称。零件的工程编号和名称。t|(t|(u)(u)(v)(J(u)v)(J(u)SPJ(v)v2=SPJ(v)v2=P3P3ul=v3ul=v3 tl=u1t

42、2=u2)tl=u1t2=u2)t|(t|(u)(u)(v)(SPJ(u)v)(SPJ(u)SPJ(v)u3=v3u2=SPJ(v)u3=v3u2=P3P3 v2=v2=P5P5tl=u3)tl=u3)3.3.检索至少使用了编号为检索至少使用了编号为P3P3和和P5P5零件的工程编号零件的工程编号JNOJNO。本讲稿第三十九页，共六十三页t|(t|(u)(u)(v)(J(u)v)(J(u)SPJ(v)(ul=v3)SPJ(v)(ul=v3)v2 v2P3)P3)t1=u1t2=u2)t1=u1t2=u2)4.4.检索不使用编号为检索不使用编号为P3P3零件的工程编号零件的工程编号JNOJNO和

43、工程名称和工程名称SNAMESNAME。5.5.检索使用了全部零件的工程名称检索使用了全部零件的工程名称JNAMEJNAME。t|(t|(u)(u)(v)(v)(w)(J(u)w)(J(u)P(v)SPJ(w)ul=w3v1=w2P(v)SPJ(w)ul=w3v1=w2 t1=u2)t1=u2)t|(t|(u)(SPJ(u)u)(SPJ(u)(v)(SPJ(v)v)(SPJ(v)(v1=(v1=S1S1(w)(SPJ(w)w)(SPJ(w)w3=u3w2=v2)tl=u3)w3=u3w2=v2)tl=u3)6.6.检索使用零件包含编号为检索使用零件包含编号为S1S1供应商所供应的全部零件的工程

44、编号。供应商所供应的全部零件的工程编号。本讲稿第四十页，共六十三页 二、域关系演算二、域关系演算 域演算表达式的定域演算表达式的定义义类类似于似于元元组组演算表达式的定演算表达式的定义义，所不同的是所不同的是公式中用域公式中用域变变量代替元量代替元组变组变量的每一个分量，量的每一个分量，域域变变量的量的变变化范化范围围是某个是某个值值域而不是一个关系。域而不是一个关系。1 1、域演算表达式：、域演算表达式：一般形式一般形式:tt1 1 t t2 2ttk k P(tP(t1 1,t,t2 2,t,tk k)其中其中t t1 1、t t2 2、t tk k分别是元组变量分别是元组变量t t的各个

45、分量的域变量，的各个分量的域变量，P P是域演算公式。是域演算公式。本讲稿第四十一页，共六十三页 原子公式有下列两种形式：原子公式有下列两种形式：i iR R（t t1 1t tk k）：）：R R是是K K元关系，每个元关系，每个t ti i是域变量或常量。是域变量或常量。ii iixy,xy,其中其中x,yx,y是域变量或常量，但至少有一个是域变是域变量或常量，但至少有一个是域变 量，量，是算术比较运算符。是算术比较运算符。域关系演算的公式中域关系演算的公式中也可使用也可使用、和和=等逻辑运算符等逻辑运算符 也可用也可用(x)x)和（和（x x）形成新的公式，但变量）形成新的公式，但变量x

46、 x是域变量，是域变量，不是元组变量。不是元组变量。自由域变量、约束域变量等概念和元组演算中一样。自由域变量、约束域变量等概念和元组演算中一样。本讲稿第四十二页，共六十三页2.2.元组表达式到域表达式的转换规则：元组表达式到域表达式的转换规则：对于对于k k元的元组变量元的元组变量t,t,引入引入k k个域变量个域变量t t1 1,t,t2 2,t,tk k,在公式中在公式中t t用用t t1 1,t,t2 2,t,tk k替换，元组分量替换，元组分量titi用用t ti i替换。替换。对于每个量词对于每个量词(u)u)或（或（u u），若），若u u是是m m元的元组变量，元的元组变量，则引

47、入则引入m m个新的域变量个新的域变量u u1 1,u,u2 2,u,um m。在量词的辖域内，在量词的辖域内，u u用用u u1 1u u2 2u um m替换，替换，uiui用用u ui i替换，替换，(u)u)用用(u u1 1)(u um m)替换，替换，(u u）用（）用（u u1 1）(u um m)替换。替换。3.3.举例举例 本讲稿第四十三页，共六十三页 安全运算：安全运算：不不产产生无限关系和无生无限关系和无穷穷次次验证验证的运算称为安全运算，的运算称为安全运算，相应的相应的表达式称表达式称为为是安全表达式。是安全表达式。所采用的措施称为安全约束。所采用的措施称为安全约束。安

48、全约束集安全约束集DOM(DOM():):公式公式 中的常量和中的常量和 中所出现关系的所有中所出现关系的所有 属性值组成的集合。属性值组成的集合。三、关系运算的安全性和等价性三、关系运算的安全性和等价性 1.1.关系运算的安全性关系运算的安全性 t|t|R(t)R(t)无限关系无限关系 验证验证(u)(w(u)u)(w(u)为为T T 或（或（u u）(w(u)(w(u)为为F F 无穷验证无穷验证 本讲稿第四十四页，共六十三页2.2.关系运算的等价性关系运算的等价性 并并、差差、笛笛卡卡儿儿积积、投投影影和和选选择择是是关关系系代代数数最最基基本本的的操操作作，并并构构成成了了关关系系代代

49、数数运运算算的的最最小小完完备备集集。可可以以证证明明，在在这这个个基基本本上上，关关系系代代数数、安安全全的的元元组组关关系系演演算算、安安全全的的域域关关系系演演算算在在关关系系的的表表达达和和操操作作能力上是等价的。能力上是等价的。本讲稿第四十五页，共六十三页5查询优化查询优化 关系代数表达式的优化问题关系代数表达式的优化问题:在关系代数表达式中需要指出若干关系的操作步骤。在关系代数表达式中需要指出若干关系的操作步骤。系统应该以什么样的操作顺序，才能做到系统应该以什么样的操作顺序，才能做到既省时间既省时间，又省空间又省空间，而且，而且效率也比较高效率也比较高呢？呢？如何花费较少的时间和空

50、间，有效地如何花费较少的时间和空间，有效地执行笛卡儿积操作执行笛卡儿积操作.本讲稿第四十六页，共六十三页 一、查询优化的总目标一、查询优化的总目标 选择有效的策略，选择有效的策略，求得给定关系代数表达式的值，求得给定关系代数表达式的值，达到提高达到提高DBMSDBMS系统效率的目标。系统效率的目标。本讲稿第四十七页，共六十三页例例:学生数据库：学生数据库：S(S(SNOSNO,SNAME,SEX,AGE,SDEPT),SNAME,SEX,AGE,SDEPT)C(C(CNOCNO,CNAME,CDEPT,TNAME),CNAME,CDEPT,TNAME)SC(SC(SNO,CNOSNO,CNO,