第2章数据库关系模型优秀PPT.ppt
第2章数据库关系模型现在学习的是第1页，共29页2.5 关系演算关系演算元组关系演算 域 关 系 演 算 现在学习的是第2页，共29页元组关系演算元组关系演算表达式元组关系演算表达式t|P(t)其中，其中，t元组变量元组变量P(t)公式（条件表达式）公式（条件表达式）原子公式的形式原子公式的形式R(s)siuj如：如：s1 u1sia a 或或 aasi如：如：s110现在学习的是第3页，共29页公式的递归定义公式的递归定义每个原子公式是一个公式每个原子公式是一个公式如果如果P1和和P2是公式，则是公式，则P1、P1 P2、P1 P2 和和 P1 P2都是公式。都是公式。如果如果P1是公式，则是公式，则(s)(P1)也都是公式。也都是公式。如果如果P1是公式，则是公式，则(s)(P1)也都是公式。也都是公式。在公式中各种运算符的优先级从高到低依次为：在公式中各种运算符的优先级从高到低依次为：；和和 ；和和；。可以在公式中加括号改变优先顺序。可以在公式中加括号改变优先顺序。除此以外构成的都不是公式。除此以外构成的都不是公式。现在学习的是第4页，共29页举例：举例：R1=t|S(t)t 1 2R2=t|R(t)S(t)R3=t|(u)(S(t)R(u)t3u1)R5=t|(u)(v)(R(u)S(v)u1v2 t1=u2 t2=v3 t3=u1)A B C1 2 34 5 67 8 9A B C1 2 33 4 65 6 9RSA B C3 4 65 6 9R1A B C4 5 67 8 9R2A B C1 2 33 4 6R3A B C4 5 67 8 9R4现在学习的是第5页，共29页关系代数表达式到元组表达式的转换关系代数表达式到元组表达式的转换RS 可用 t|R(t)S(t)表示RS可用 t|R(t)S(t)表示RS可用 t|R(t)S(t)表示RS可用 t|(u)(v)(R(u)S(v)t1=u1 t2=u3 t3=v1 t4=v2 表示。(设关系R和S都是二元关系）1,2(R)可用 t|(u)(R(u)t1=u1 t2=u2)表示。F(R)可用 t|R(t)F 表示。现在学习的是第6页，共29页元组表达式举例：S#SNAGESEXDEPS1A20MCSS2B21FCSS3C19MMAS4D19FCIS5E20FMAS6F22MCSSC#CNC1GC2HC3IC4JC5KCS#C#GRADES1C1AS1C2AS1C3AS1C5BS2C1BS2C2CS2C4CS3C2BS3C3CS3C4BS4C3BS4C5DS5C2CS5C3BS5C5BS6C4AS6C5ASC1.求选修课程号为C2课程的学号和成绩2.求选修课程号为C2课程的学号和姓名3.求选修课程名为“数学”的学号和姓名4.求选修课程号为C2或C4的学号5.求至少选修课程号为C2和C4的学号6.求不修C2课程的学号7.求选修了全部课程的学生姓名8.求所学课程包含学号S3所学课程的学号现在学习的是第7页，共29页域关系演算域关系演算域关系演算表达式域关系演算表达式t1 tk|P(t1，tk)其中，其中，t1 tk 域变量域变量P(t1，tk)公式（条件表达式）公式（条件表达式）原子公式的形式原子公式的形式R(t1 tk)xy现在学习的是第8页，共29页举例：举例：R1=xyz|R(xyz)x3R2=xyz|R(xyz)(S(xyz)y=4)R3=xyz|(u)(v)(R(zxu)W(yv)uv)A B C1 2 34 5 67 8 9A B C1 2 33 4 65 6 9RSD E7548WA B C4 5 6R1A B C1 2 34 5 67 8 93 4 6R2A B C5 7 48 8 78 4 7R3现在学习的是第9页，共29页元组表达式到域表达式的转换元组表达式到域表达式的转换对于对于K元的元组变量元的元组变量t，引入，引入K个域变量个域变量t1tk，在，在公式中公式中t用用t1tk替换，元组分量替换，元组分量ti用用ti替换。替换。对于每个量词对于每个量词(u)或或(v)，若，若u是是m元的元组变量，元的元组变量，则引入则引入m个新的域变量个新的域变量u1um。在量词的辖域内，。在量词的辖域内，u用用u1um替换，替换，ui用用ui替换，替换，(u)用用(u1)(um)替换，替换，(v)用用(u1)(um)替换。替换。现在学习的是第10页，共29页举例设关系R和S都是二元关系关系代数：RS元组表达式：t|(u)(v)(R(u)S(v)t1=u1 t2=u3 t3=v1 t4=v2)域表达式：t1 t2 t3t4|(u1)(u2)(v1)(v2)(R(u1 u2)S(v1 v2)t1=u1 t2=u3 t3=v1 t4=v2)进一步简化：进一步简化：t1 t2 t3t4|(R(t1 t2)S(t3t4)现在学习的是第11页，共29页关系运算的安全性关系运算的安全性在数据库技术中，不产生无限关系和无穷验证的运在数据库技术中，不产生无限关系和无穷验证的运算称为安全运算，相应的表达式称为安全表达式，算称为安全运算，相应的表达式称为安全表达式，所采取的措施称为安全约束。所采取的措施称为安全约束。关系代数运算总是安全的。关系代数运算总是安全的。在关系演算中，运算只对表达式中公式在涉及到在关系演算中，运算只对表达式中公式在涉及到的关系的值范围内操作。这样就不会产生无限关的关系的值范围内操作。这样就不会产生无限关系和无穷验证问题，关系演算是安全的。系和无穷验证问题，关系演算是安全的。现在学习的是第12页，共29页关系模型概述关系模型概述关系模型的完整性约束关系模型的完整性约束关系数据库系统的三层模式结构关系数据库系统的三层模式结构关系代数关系代数关系演算关系演算查询优化查询优化第2章 关系模型现在学习的是第13页，共29页一个实例一个实例查询选修C2课程的学生姓名关系表达式可写成：Q1=SN(S.SNO=SC.SNO SC.CNO=C2(S SC)Q2=SN(SC.CNO=C2(S SC)Q3=SN(S SC.CNO=C2(SC)设S关系中有1000个学生；SC有10000条记录；选C2的学生有50个。1个数据块装10个S元组，装100个SC元组。内存：只给6个数据块，5块装S元组，1块装SC元组，内存交换数据数度为20块/s。Q1的情况计算S SC。1000/10+1000/(5*10)*(10000/10)=2100块 -105秒连接103*104=107记录数，每块装10个记录，将中间结果写回外存需要107/10/20=5*104秒读回中间结果，选择，需5*104秒。选择后有50个元组。投影 总需要2*5*104+105秒 约27.7小时。现在学习的是第14页，共29页一个实例一个实例关系表达式可写成：Q1=SN(S.SNO=SC.SNO SC.CNO=C2(S SC)Q2=SN(SC.CNO=C2(S SC)Q3=SN(S SC.CNO=C2(SC)设S关系中有1000个学生；SC有10000条记录；选C2的学生有50个。1个数据块装10个S元组，装100个SC元组。内存：只给6个数据块，5块装S元组，1块装SC元组，内存交换数据数度为20块/s。Q2的情况计算自然连接。1000/10+1000/(5*10)*(10000/10)=2100块 -105秒如果一个学生选10门，则自然连接结果104记录数，每块装10个记录，将中间结果写回外存需要104/10/20=50秒读回中间结果，选择，需50秒。选择后有50个元组。投影 总需要2*50+105秒=205秒 约3.4分钟。现在学习的是第15页，共29页一个实例一个实例关系表达式可写成：Q1=SN(S.SNO=SC.SNO SC.CNO=C2(S SC)Q2=SN(SC.CNO=C2(S SC)Q3=SN(S SC.CNO=C2(SC)设S关系中有1000个学生；SC有10000条记录；选C2的学生有50个。1个数据块装10个S元组，装100个SC元组。内存：只给6个数据块，5块装S元组，1块装SC元组，内存交换数据数度为20块/s。Q3的情况读SC。10000/100/20=5秒读S 1000/10/20=5秒；选择后有50个元组。投影 总需要5+5秒=10秒现在学习的是第16页，共29页优化策略优化策略选择运算尽可能先做，这是最根本的一条。选择运算尽可能先做，这是最根本的一条。在执行连接之前对关系文件适当的预处理，预处理的方法有两在执行连接之前对关系文件适当的预处理，预处理的方法有两种，对关系文件排序和在连接属性上建索引。种，对关系文件排序和在连接属性上建索引。把投影运算和选择运算同时进行，如果有若干个投影和选择运算，把投影运算和选择运算同时进行，如果有若干个投影和选择运算，并且它们并且它们6都是对同一关系操作，则可在扫描此关系时完都是对同一关系操作，则可在扫描此关系时完成所有这些操作，避免重复扫描。成所有这些操作，避免重复扫描。把投影同前或后的双目运算（并、交、差）结合起来，没有必把投影同前或后的双目运算（并、交、差）结合起来，没有必要为了去掉某些列尔再去扫描一遍关系。要为了去掉某些列尔再去扫描一遍关系。把笛卡尔积和随后的选择操作合并成把笛卡尔积和随后的选择操作合并成F连接运算。连接运算。如果在一个表达式中多次出现某个子表达式，应该将该如果在一个表达式中多次出现某个子表达式，应该将该子表达式预先计算出结果保存起来，避免重复计算。子表达式预先计算出结果保存起来，避免重复计算。现在学习的是第17页，共29页关系代数表达式的等价规则关系代数表达式的等价规则（1）连接和笛卡尔积的交换律）连接和笛卡尔积的交换律 E1 E2E2 E1 E1 E2E2 E1 E1E2E2E1（2）连接和笛卡尔积的结合律）连接和笛卡尔积的结合律 (E1 E2)E3 E1 (E2 E3)(E1 E2)E3 E1 (E2 E3)(E1E2)E3 E1(E2E3)FFF1F2F1F2现在学习的是第18页，共29页关系代数表达式的等价规则关系代数表达式的等价规则（3）投影的串接）投影的串接A1An(B1Bm(E)A1An(E)其中其中A1An是是B1Bm的子集。的子集。如：对于如：对于R(A,B,C,D)A,B(A,B,C,D(R)A,B(R)（4）选择的串接）选择的串接F1(F2(E)F1 F2(E)现在学习的是第19页，共29页关系代数表达式的等价规则关系代数表达式的等价规则（5）选择和投影的交换）选择和投影的交换F(A1An(E)A1An(F(E)注意：选择的属性不能投影掉注意：选择的属性不能投影掉更一般的更一般的 若若F中有不属于中有不属于A1An的属性的属性B1Bm时时A1An(F(E)A1An(F(A1An，B1Bm(E)如：如：SN(DEPT=计算机计算机(S)SN(DEPT=计算机计算机(SN，DEPT(S)现在学习的是第20页，共29页关系代数表达式的等价规则关系代数表达式的等价规则（6）选择和笛卡尔积的交换律）选择和笛卡尔积的交换律当当F中涉及的属性都是中涉及的属性都是E1中的中的 属性时：属性时：F(E1E2)F(E1)E2 若若F=F1F2,F1只涉及只涉及E1中的属性，中的属性，F2只涉及只涉及E2中的中的属性属性F(E1E2)F1(E1)F2(E2)现在学习的是第21页，共29页关系代数表达式的等价规则关系代数表达式的等价规则（7）选择并的交换律）选择并的交换律E1和和E2有相同的属性：有相同的属性：F(E1E2)F(E1)F(E2)（8）选择与差的交换律）选择与差的交换律F(E1-E2)F(E1)-F2(E2)现在学习的是第22页，共29页关系代数表达式的等价规则关系代数表达式的等价规则（9）投影与笛卡尔积的交换）投影与笛卡尔积的交换 A1An B1Bm(E1E2)A1An(E1)B1Bm(E2)其中，其中，A1An是是E1的属性，的属性，B1Bm是是E2的属性的属性（10）投影与并的交换投影与并的交换A1An(E1E2)A1An(E1)A1An(E2)现在学习的是第23页，共29页关系代数表达式优化算法关系代数表达式优化算法输入：一个关系表达式的语法树输入：一个关系表达式的语法树输出：计算该表达式的程序输出：计算该表达式的程序方法：方法：1.利用规则（利用规则（4）把形如）把形如F1Fn(E)变换为变换为 F1(Fn(E)2.对每一个选择利用（对每一个选择利用（1）（8）尽可能将它移到树的叶端（靠近）尽可能将它移到树的叶端（靠近关系）关系）3.对每个投影利用（对每个投影利用（3）、（）、（4）、（）、（10）、（）、（5）中的一般形式）中的一般形式尽可能把它到树的叶端。尽可能把它到树的叶端。注意：注意：（3）可能使一些投影消失，（）可能使一些投影消失，（5）的一般形式把一个投影分裂）的一般形式把一个投影分裂成两个，其中一个有可能靠近叶端。成两个，其中一个有可能靠近叶端。现在学习的是第24页，共29页关系代数表达式优化算法关系代数表达式优化算法4.利用规则（利用规则（3）（5）把选择和投影的串接合并成单个选择，）把选择和投影的串接合并成单个选择，单个投影或一个选择跟一个投影，使多个选择或投影能同时执单个投影或一个选择跟一个投影，使多个选择或投影能同时执行，或一次扫描中全部完成。行，或一次扫描中全部完成。5.把上述得到的语法树的内结点分组，每一双目运算（并，连接，把上述得到的语法树的内结点分组，每一双目运算（并，连接，差，笛卡尔）和它所有的连接祖先为一组（投影和选择），如果差，笛卡尔）和它所有的连接祖先为一组（投影和选择），如果它的子结点直到叶结点都是单目运算，则也也并入改组。但当双它的子结点直到叶结点都是单目运算，则也也并入改组。但当双目运算为笛卡尔积，而其后的选择不能与它结合为等值连接时除目运算为笛卡尔积，而其后的选择不能与它结合为等值连接时除外，把这些单目运算独立放在一组。外，把这些单目运算独立放在一组。6.生成一个程序，每组结点的运算是程序中的一步，各部的顺序是任生成一个程序，每组结点的运算是程序中的一步，各部的顺序是任意的，只要保证任何一组的计算不会在它的后代组之前计算就行。意的，只要保证任何一组的计算不会在它的后代组之前计算就行。现在学习的是第25页，共29页举例举例：数据库：数据库：S(S#,SNAME,AGE,SEX)SC(S#,C#,GRADE)C(C#,CNAME,TEACHER)查询语句：检索至少学习查询语句：检索至少学习LIU老师所授一门课程的女学老师所授一门课程的女学生学号和姓名。生学号和姓名。S#,SNAME(TEACHER=LIU SEX=F(L(SC.C#=C.C#SC.S#=S.S#(SC C S)现在学习的是第26页，共29页SCCSSC.C#=C.C#SC.S#=S.S#TEACHER=LIU SEX=FS#,SNAME,AGE,SEX,C#,CNAME,TEACHER,GRADES#,SNAME现在学习的是第27页，共29页SCSC.S#=S.S#S#,SNAMESC.C#=C.C#SCTEACHER=LIUSEX=F现在学习的是第28页，共29页SC.S#=S.S#S#,SNAMESC.C#=C.C#SCSCTEACHER=LIUSEX=FSC.S#,SC.C#SC.S#C.C#S.S#,SNAME现在学习的是第29页，共29页
