第三章-关系运算2(实例讲解)课件

数据库实用教程（第三版）数据库实用教程（第三版）第三章第三章 关系运算关系运算习题及实例讲解习题及实例讲解各各种运算总结：种运算总结：关系代数运算有五个基本操作，另三个非关系代数运算有五个基本操作，另三个非基本运算可以由这基本运算可以由这5 5个基本运算组合而成。个基本运算组合而成。由和 组合而成由、-和组合而成四、关系代数表达式及其应用实例四、关系代数表达式及其应用实例 工程项目零件供应数据库工程项目零件供应数据库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,BALANCE)供应情况关系：供应情况关系：SPJ(SPJ(SNO,PNO,JNOSNO,PNO,JNO,PRICE,QTY),PRICE,QTY)SNOSNAMESADDRS1喜多上海浦东S2多乐士北京房山S3天奴广州汕头PNOPNAMECOLORWEIGHTP1螺丝银色0.5P2门扣红色5P3门锁红色20P4开关白色2P5水龙头蓝色50JNOJNAMEJCITYBALANCEJ1办公室工程青岛50000J2居家装修山东50000SNOPNOJNOPRICEQTYS1P3J155S1P5J2102S3P4J1151lJSPJSNOSNAMESADDRS1喜多上海浦东S2多乐士北京房山S3天奴广州汕头PNOPNAMECOLORWEIGHTP1螺丝银色0.5P2门扣红色5P3门锁红色20P4开关白色2P5水龙头蓝色50JNOJNAMEJCITYBALANCEJ1办公室工程青岛50000J2居家装修山东50000SNOPNOJNOPRICEQTYS1P3J155S1P5J2102S3P4J1151工程项目使用零件的情况工程项目使用零件的情况SNOPNOJNOPRICEQTYJNAMEJCITYBALANCES1P3J155办公室工程青岛50000S3P4J1151办公室工程青岛50000S1P5J2102居家装修山东50000lSSPJ PSNOSNAMESADDRS1喜多上海浦东S2多乐士北京房山S3天奴广州汕头PNOPNAMECOLORWEIGHTP1螺丝银色0.5P2门扣红色5P3门锁红色20P4开关白色2P5水龙头蓝色50JNOJNAMEJCITYBALANCEJ1办公室工程青岛50000J2居家装修山东50000SNOPNOJNOPRICEQTYS1P3J155S1P5J2102S3P4J1151lSSPJ PSNOSNAMESADDRPNOJNOPRICEQTYPNAMECOLORWEIGHTS1喜多上海浦东P3J155门锁红色20S3天奴广州汕头P4J1151开关白色2S1喜多上海浦东P5J2102水龙头蓝色50试用关系代数表达式表示每个查询语句。试用关系代数表达式表示每个查询语句。.检索工程检索工程J1J1的供应记录。的供应记录。JNOJNAMEJCITYBALANCEJ1办公室工程青岛50000J2居家装修山东50000SNOPNOJNOPRICEQTYS1P3J155S1P5J2102S3P4J1151SNOPNOJNOPRICEQTYS1P3J155S3P4J1151JNO=JNO=J1J1(SPJ)(SPJ)2.2.检索供应零件给工程检索供应零件给工程J1J1的供应商编号的供应商编号SNOSNO与零件编号与零件编号PNOPNO。SN0,PN0SN0,PN0(JNO=JNO=J1J1(SPJ)(SPJ)JNO=J1 PNO=P1JNO=J1 PNO=P1（SPJSPJ）3.3.检索供应零件给工程检索供应零件给工程J1J1，且零件编号为，且零件编号为P1P1的供应商记录。的供应商记录。4.4.检索供应零件给工程检索供应零件给工程J1J1，且零件编号为，且零件编号为P1P1的供应商编号的供应商编号SNOSNO。SNOSNO（JNO=J1 PNO=P1JNO=J1 PNO=P1（SPJSPJ）SNOPNOJNOPRICEQTYS1P3J155S1P5J2102S3P4J11515.5.检索供应零件给工程检索供应零件给工程J1,J1,且零件颜色为红色的供应情况。且零件颜色为红色的供应情况。SNAME,SADDRSNAME,SADDR(JNO=J1 COLOR=JNO=J1 COLOR=红色红色(S(S SPJSPJ P)P)6.6.检索供应零件给工程检索供应零件给工程J1,J1,且零件颜色为红色的供应商名称和地址。且零件颜色为红色的供应商名称和地址。JNO=J1 COLOR=JNO=J1 COLOR=红色红色(S(S SPJSPJ P)P)7.7.检索使用了零件编号为检索使用了零件编号为P3P3或或P5P5零件的工程情况。零件的工程情况。PNO=P3PNO=P5PNO=P3PNO=P5(SPJSPJ)8.8.检索使用了零件编号为检索使用了零件编号为P3P3或或P5P5零件的工程编号零件的工程编号JNOJNO。JNOJNO（PNO=P3PNO=P5PNO=P3PNO=P5(SPJSPJ)9.9.检索至少使用了编号为检索至少使用了编号为P3P3和和P5P5 零件的工程编号零件的工程编号JNOJNO。3 3（3=82=P37=P53=82=P37=P5(SPJSPJSPJSPJ)10.10.检索不使用编号为检索不使用编号为P3P3零件的工程编号零件的工程编号JNOJNO和工程名称和工程名称JNAMEJNAME。JNO,JNAMEJNO,JNAME(J)(J)JNO,JNAMEJNO,JNAME(PNO=PNO=P3P3(S(S SPJSPJ P)P)11.11.检索使用了全部零件的工程名称检索使用了全部零件的工程名称JNAMEJNAME。JNAMEJNAME(J(J(JNO,PNOJNO,PNO(SPJ)(SPJ)PNOPNO(P)(P)12.12.检索使用零件包含编号为检索使用零件包含编号为S1S1的供应商所供应的全部零件的工程的供应商所供应的全部零件的工程 编号编号JNOJNO。JNO,PNOJNO,PNO(SNO=S1(SNO=S1(SPJ)SPJ)PNOPNO(SNO=S1SNO=S1(SPJ)(SPJ)课后3.12检索LIU老师所授课程的课程号、课程名。检索年龄大于23岁的男学生的学号与姓名。检索学号为S3学生所学课程的课程名与任课教师名。检索至少选修LIU老师所授课程中一门课程的女学生的姓名。检索WANG同学不学的课程号。检索至少选修两门课程的学生学号。检索全部学生都选修的课程的课程号与学生学号。检索选修课程包含LIU老师所授课程的学生学号。五、扩充的关系代数操作五、扩充的关系代数操作 1.1.外外联联接接（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表示。表示。空字符串空字符串0 i i、如果、如果R R和和S S做自然做自然联接接时，把，把R R中原中原该舍弃的元舍弃的元组放放 到新关系中，那么到新关系中，那么这种操作称种操作称为“左外左外联接接”操作，操作，用符号用符号: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 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的的关关系系模模式式不不同同，构构成成的的新新关关系系属属性性有有R R和和S S的的所所有有属属性性组组成成（公公共共属属性性只只取取一一次次），新新关关系系的的元元组组由由属属于于R R或或属属于于S S的的元组构成，同时元组在新增加的属性上填上空值。元组构成，同时元组在新增加的属性上填上空值。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.半联接（半联接（semijoinsemijoin）关系关系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 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 d4关系演算关系演算 以数理逻辑中的谓词演算为基础，用公式表示关系演算的条件。以数理逻辑中的谓词演算为基础，用公式表示关系演算的条件。关系演算按所用到的变量不同可分为：关系演算按所用到的变量不同可分为：元组关系演算以元组为变量；元组关系演算以元组为变量；域关系演算域关系演算 以域为变量。以域为变量。一、元组关系演算一、元组关系演算 形式：形式：tt(t)(t)其中其中 t t：元组变量；：元组变量；：公式，公式有原子公式及运算符组成。公式，公式有原子公式及运算符组成。1.1.原子公式有下列三种形式：原子公式有下列三种形式：R R（t t）：）：R R 是关系名，是关系名，t t 是元组变量。是元组变量。tiuj:tiuj:t t 和和 u u是元组变量，是元组变量，是算术比较运算符。是算术比较运算符。tiC tiC 或或 CuiCui：t t 和和 u u 是元组变量，是元组变量，c c 是常量。是常量。2.2.约束变量和自由变量约束变量和自由变量 在在一一个个公公式式中中，如如果果一一个个元元组组变变量量的的前前面面没没有有存存在在量量词词或或全全称称量量词词 的的符符号号定定义义，称称之之为为自自由由元元组组变变量量，否否则则称称为为约约束束元组变量。元组变量。3 3.运算符及优先次序为：运算符及优先次序为：i.i.括号中运算符优先级最高括号中运算符优先级最高 ii.ii.算术比较运算符最高；算术比较运算符最高；iii.iii.量词量词 ：存在量词：存在量词 全称量词全称量词 iv.iv.逻辑运算符：逻辑运算符：、优先级最高4.4.用元用元组关系演算表达式表示关系运算关系演算表达式表示关系运算并并: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,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)Ft|R(t)F F F是是F F在元组演算中的等价表示形式。在元组演算中的等价表示形式。6.实例实例:用元组表达式形式表示下列查询用元组表达式形式表示下列查询例例:用元组表达式形式表示下列查询：用元组表达式形式表示下列查询：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=v3tlul=v3tl=u1=u1 t2=u2)t2=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和工程名称和工程名称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)(SPJw)(SPJ(w)(w)w3=u3w2=v2)tl=u3)w3=u3w2=v2)tl=u3)6.6.检索使用零件包含编号为检索使用零件包含编号为S1S1供应商所供应的全部零件的工程编号。供应商所供应的全部零件的工程编号。如果如果P1和和P2是公式，是公式，在元组关系演算的公式中，存在下列等价转换规则：在元组关系演算的公式中，存在下列等价转换规则：P1P2(P1P2)P1P2(P1P2）(s)(P1(s)(s)(P1(s)(s)(P1(s)(s)(P1(s)P1P2 P1P2 二、域关系演算二、域关系演算 域演算表达式的定域演算表达式的定义类似于似于元元组演算表达式的定演算表达式的定义，所不同的是所不同的是公式中用域公式中用域变量代替元量代替元组变量的每一个分量，量的每一个分量，域域变量的量的变化范化范围是某个是某个值域而不是一个关系。域而不是一个关系。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的各个分量的域变量，的各个分量的域变量，P P是域演算公式。是域演算公式。原子公式有下列两种形式：原子公式有下列两种形式：i iR R（t1t1tktk）：）：R R是是K K元关系，每个元关系，每个titi是域变量或常量。是域变量或常量。iiiixy,xy,其中其中x,yx,y是域变量或常量，但至少有一个是域变是域变量或常量，但至少有一个是域变 量，量，是算术比较运算符。是算术比较运算符。域关系演算的公式中域关系演算的公式中也可使用也可使用、和和=等逻辑运算符等逻辑运算符 也可用也可用(x)x)和（和（x x）形成新的公式，但变量）形成新的公式，但变量x 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元的元组变量，元的元组变量，则引入则引入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.举例举例 安全运算：安全运算：不不产生无限关系和无生无限关系和无穷次次验证的运算称为安全运算，的运算称为安全运算，相应的相应的表达式称表达式称为是安全表达式。是安全表达式。所采用的措施称为安全约束。所采用的措施称为安全约束。安全约束集安全约束集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.关系运算的等价性关系运算的等价性 并并、差差、笛笛卡卡儿儿积积、投投影影和和选选择择是是关关系系代代数数最最基基本本的的操操作作，并并构构成成了了关关系系代代数数运运算算的的最最小小完完备备集集。可可以以证证明明，在在这这个个基基本本上上，关关系系代代数数、安安全全的的元元组组关关系系演演算算、安安全全的的域域关关系系演演算算在关系的表达和操作能力上是等价的。在关系的表达和操作能力上是等价的。5查询优化查询优化 关系代数表达式的优化问题关系代数表达式的优化问题:在关系代数表达式中需要指出若干关系的操作步骤。在关系代数表达式中需要指出若干关系的操作步骤。系统应该以什么样的操作顺序，才能做到既省时间，系统应该以什么样的操作顺序，才能做到既省时间，又省空间，而且效率也比较高呢？又省空间，而且效率也比较高呢？如何花费较少的时间和空间，有效地如何花费较少的时间和空间，有效地执行笛卡儿积操作执行笛卡儿积操作.一、查询优化的总目标一、查询优化的总目标 选择有效的策略，选择有效的策略，求得给定关系代数表达式的值，求得给定关系代数表达式的值，达到提高达到提高DBMSDBMS系统效率的目标。系统效率的目标。例例:学生数据库：学生数据库：S(SNO,SNAME,SEX,SDEPT)S(SNO,SNAME,SEX,SDEPT)C(CNO,CNAME,TEACHER,CDEPT)C(CNO,CNAME,TEACHER,CDEPT)SC(SNO,CNO,GRADE)SC(SNO,CNO,GRADE)检索选修检索选修C2C2课程的学生的学号和姓名课程的学生的学号和姓名,用关系代数表达式表示：用关系代数表达式表示：E1=E1=SNAMESNAME（S.SNO=SC.SNOSC.CNO=C2S.SNO=SC.SNOSC.CNO=C2（SSCSSC）E2=E2=SNAME SNAME（SC.CNO=C2SC.CNO=C2（S S SC SC）E3=SNAMESNAME（S S SC.CNO=C2SC.CNO=C2（SC）这这三三个个关关系系代代数数表表达达式式是是等等价价的的，但但执执行行的的效效率率大大不不一一样样。显显然，求然，求ElEl，E2E2，E3E3的大部分时间是花在联接操作上的。的大部分时间是花在联接操作上的。二、代数表达式的等价变换规则二、代数表达式的等价变换规则 1、联接和笛卡儿积的交换律联接和笛卡儿积的交换律 E1 E1 E2 E2 E1 E2 E2 E1 E1 E2 E2 E1 E1 E2 E2 E1 E1 E2 E2 E1 E1 E2 E2 E1 F F 2 2联接和笛卡儿积的结合律联接和笛卡儿积的结合律 （E1 E2 E1 E2）E3 E1 E3 E1 （E2 E3E2 E3）（E1 E2E1 E2）E3 E1 E3 E1 （E2 E3E2 E3）（E1 E2E1 E2）E3 E1 E3 E1（E2 E3E2 E3）F1 F1 F2 F2 3.3.投影的串接投影的串接 设设L1L1，L2L2，LnLn为属性集，并且为属性集，并且L1L1 L2L2 LnLn，成立：成立：L1L1（L2L2（LnLn（E E）L1L1（E E）4 4选择的串接选择的串接 F1F1（F2F2（E E）F1 F2F1 F2（E E）由于由于F1 F2=F2 F1F1 F2=F2 F1，选择的交换律也成立：，选择的交换律也成立：F1F1（F2F2（E E）F2F2（F1F1（E E）5 5选择和投影操作的交换选择和投影操作的交换 L L（F F（E E）F F（L L（E E）要求条件要求条件F F只涉及到只涉及到L L中的属性中的属性,如果如果F F还涉及到不在还涉及到不在L L中的属性集中的属性集L1L1：L L（F F（E E）L L（F F（LL1LL1（E E）6 6选择对笛卡儿积的分配律选择对笛卡儿积的分配律 F F（E1E2E1E2）F F（E1E1）E2E2 F F（E1E2E1E2）F1F1（E1E1）F2F2（E2E2）F F（E1E2E1E2）F2F2（F1F1（E1E1）E2E2）7.7.选择对并的分配律选择对并的分配律 F F（E1E2E1E2）F1F1（E1E1）F2F2（E2E2）8 8 选择对集合差的分配律选择对集合差的分配律 F F（E1E1E2E2）F F（E1E1）F F（E2E2）9 9选择对自然联接的分配律选择对自然联接的分配律 F F（E1 E1 E2 E2）F F（E1E1）F F（E2E2）1010 投影对笛卡儿积的分配律投影对笛卡儿积的分配律L1L2L1L2（E1E2E1E2）L1L1（E1E1）L2L2（E2E2）1111 投影对并的分配律投影对并的分配律 L L（E1E2E1E2）L L（E1E1）L L（E2E2）1212 选择与联接操作的结合选择与联接操作的结合 F1F1（E1 E2E1 E2）E1 E1 E2E21313 并和交的交换律并和交的交换律 E1E2 E2E1 E1E2 E2E1 E1E2 E2E1 E1E2 E2E11414 并和交的结合律并和交的结合律 （E1E2E1E2）E3 E1E3 E1（E2E3E2E3）（E1E2E1E2）E3 E1E3 E1（E2E3E2E3）F2F2F2 三、三、优化的一般策略化的一般策略 (1-6)(1-6)(1)(1)在关系代数表达式中尽可能早地在关系代数表达式中尽可能早地执行行选择操作。操作。(2)(2)把笛卡儿把笛卡儿积和其后的和其后的选择操作合并成操作合并成F F联接运算。接运算。(3)(3)同时计算一连串的选择和投影操作，以免分开运算造成多次同时计算一连串的选择和投影操作，以免分开运算造成多次 扫描文件，节省操作时间。扫描文件，节省操作时间。(4)(4)如在一个表达式中多次出如在一个表达式中多次出现某个子表达式，某个子表达式，可先对可先对该子子 表达式表达式进行进行计算算并并保存保存结果，以免重复果，以免重复计算。算。(5)(5)适当地适当地对关系文件关系文件进行行预处理。理。(6)(6)在在计算表达式前算表达式前应先估先估计一下怎么一下怎么计算合算。算合算。三、关系代数表达式的优化算法三、关系代数表达式的优化算法 输入：输入：一个关系代数表达式的语法树。一个关系代数表达式的语法树。输出：输出：计算表达式的一个优化序列。计算表达式的一个优化序列。方法方法:依次执行下面每一步。依次执行下面每一步。使用等价变换使用等价变换规则规则把每个形为把每个形为F1F1 Fn Fn（E E）的子表达式转）的子表达式转 换成选择串接形式：换成选择串接形式：F1F1（FnFn（E E）对每个选择操作，使用对每个选择操作，使用规则规则，尽可能把，尽可能把选择操作移近树选择操作移近树 的叶端的叶端（即尽可能早地执行选择操作）。（即尽可能早地执行选择操作）。对每个投影操作，使用对每个投影操作，使用规则规则(3)(3)，(5)(5)，(10)(10)和和(11)(11)，尽可能把，尽可能把 投影操作移近树的叶端。投影操作移近树的叶端。使使用用规规则则，把把选选择择和和投投影影合合并并成成单单个个选选择择、单单个个投投影影或或一个选择后跟一个投影。一个选择后跟一个投影。将上述步骤得到的语法树的内结点分组。分组原则：将上述步骤得到的语法树的内结点分组。分组原则：a a、每个二元运算每个二元运算(、)结点结点与其直接祖先与其直接祖先(不超过别的二不超过别的二 元运算结点）的元运算结点）的一元运算结点一元运算结点(或或)分为一组。分为一组。如果它的子如果它的子 孙结点一直到叶都是一元运算符孙结点一直到叶都是一元运算符(或或),则也并入该组。则也并入该组。b b、如果二元运算是笛卡儿积，而且后面不是与它组合成等值联接、如果二元运算是笛卡儿积，而且后面不是与它组合成等值联接 的选择时，则不能将选择与这个二元运算组成同一组。的选择时，则不能将选择与这个二元运算组成同一组。生成一个程序，每一组结点的计算是程序中的一步，各步的顺生成一个程序，每一组结点的计算是程序中的一步，各步的顺 序是任意的只要保证任何一组不会在它的子孙组之前计算。序是任意的只要保证任何一组不会在它的子孙组之前计算。举例举例:学生数据库：学生数据库：S(SNO,SNAME,SEX,SDEPT)S(SNO,SNAME,SEX,SDEPT)C(CNO,CNAME,TEACHER,CDEPT)C(CNO,CNAME,TEACHER,CDEPT)SC(SNO,CNO,GRADE)SC(SNO,CNO,GRADE)“检索选修检索选修LIULIU老师所教课程的女学生的学号和姓名老师所教课程的女学生的学号和姓名”。用关系代数表达式表示：用关系代数表达式表示：SNO,SNAMESNO,SNAME(TEACHER=LIUSEX=FTEACHER=LIUSEX=F(S(S SCSC C)C)该表达式构成的语法树该表达式构成的语法树:S.S.SNO,SNAMESNO,SNAME TEACHER=LIUSEX=FTEACHER=LIUSEX=F SNO,SNAME,SEX,SDEPT,CNO,CNAME,SNO,SNAME,SEX,SDEPT,CNO,CNAME,TEACHER,CDEPT,GRADE TEACHER,CDEPT,GRADES.SNO=SC.SNOSC.CNO=C.CNOS.SNO=SC.SNOSC.CNO=C.CNOSCSC语法树语法树:SC.SNO=S.SNOSC.SNO=S.SNO SSCSCTEACHER=TEACHER=LIULIU C CSEX=SEX=F F SC.CNO=C.CNOSC.CNO=C.CNO S.SNO,SNAMES.SNO,SNAME S.SNO,SNAME,SC.SNOS.SNO,SNAME,SC.SNOTEACHER=TEACHER=LIULIUS.SNOS.SNO，SNAMESNAMESC.SNO=S.SNOSC.SNO=S.SNOSEX=SEX=F FSC.CNO=C.CNOSC.CNO=C.CNO C CSCSC S S S.SNO,SNAMESNO,SNAMESEX=SEX=F FSC.SNO SC.SNO SC.CNO=C.CNOSC.CNO=C.CNOSC.SNO,SC.CNO,C.CNOSC.SNO,SC.CNO,C.CNO 把把S.SNO,SNAME,SC.SNO S.SNO,SNAME,SC.SNO 分成分成:SC.SNOSC.SNO 和和 SNO,SNAMESNO,SNAME 使它们分别对使它们分别对SC.CNO=C.CNOSC.CNO=C.CNO()和和SEX=SEX=F F(S)(S)做投影操作。做投影操作。再据规则再据规则，将投影，将投影SC.SNOSC.SNO和和SNO,SNAMESNO,SNAME分别与前面的选择运算形分别与前面的选择运算形成两个串接运算：成两个串接运算：S.SNO,SNAMES.SNO,SNAMESC.SNO=S.SNOSC.SNO=S.SNO SEX=SEX=F FSS.SNO,SNAMESNO,SNAMESC.CNO=C.CNOSC.CNO=C.CNOSC.SNOSC.SNOSC TEACHER=TEACHER=LIULIUC C C.CNOC.CNOSC.CNOSC.CNO，SC.SNOSC.SNO精精 读读:教材教材 P.37 P.37 P.P.6464习习 题：题：P.65 3.6 3.12P.65 3.6 3.12 3.7 3.7 3.113.11 3.13 3.13 3.153.15精读和习题要求精读和习题要求