关模型和关系运算理论.ppt

第2章关系模型和关系运算理论,数据库系统2010年,本章重要概念（一）,（1）基本概念关系模型，关键码（主键和外键），关系的定义和性质，三类完整性规则，过程性语言与非过程性语言。（2）关系代数五个基本操作，四个组合操作，七个扩充操作。,本章重要概念（二）,（3）关系演算元组关系演算和域关系演算的原子公式、公式的定义。关系演算的安全性和等价性。（4）关系代数表达式的优化关系代数表达式的等价及等价转换规则，启化式优化算法。（5）关系逻辑谓词、原子、规则和查询，规则的安全性，用规则模拟关系代数表达式。,本章概要,本章先介绍关系模型的基本概念；然后介绍关系运算的三种理论：关系代数、关系演算和关系逻辑。,2.1关系模型的基本概念,系统而严格地提出关系模型的是美国IBM公司的E.F.Codd1970年提出关系数据模型E.F.Codd,“ARelationalModelofDataforLargeSharedDataBanks”,CommunicationoftheACM,1970之后，提出了关系代数和关系演算的概念1972年提出了关系的第一、第二、第三范式1974年提出了关系的BC范式,2.1关系模型的基本概念,关系模型建立在集合代数的基础上关系数据库应用数学方法来处理数据库中的数据关系数据库系统是支持关系模型的数据库系统80年代后，关系数据库系统成为最重要、最流行的数据库系统,2.1关系模型的基本概念,典型实验系统SystemRUniversityINGRES典型商用系统ORACLESYBASEINFORMIXDB2INGRES,基本术语(1),定义2.1用二维表格表示实体集，用关键码表示实体之间联系的数据模型称为关系模型（relationalModel）。,图2.1职工登记表,基本术语(2),在关系模型中，字段称为属性，字段值称为属性值，记录类型称为关系模式。在图2.2中，关系模式名是R。记录称为元组（tuple），元组的集合称为关系（relation）或实例（instance）。一般用大写字母A、B、C、表示单个属性，用大写字母、X、Y、Z表示属性集，用小写字母表示属性值，有时也习惯称呼关系为表或表格，元组为行(row)，属性为列(column)。关系中属性个数称为“元数”（arity），元组个数为“基数”(cardinality)。,基本术语(3),关系元数为5，基数为4,图2.2关系模型的术语,一般术语关系模型术语字段、数据项属性记录类型关系模式记录1元组1记录2元组2记录3元组3记录4元组4字段值属性值,基本术语(4),关键码(key,简称键)由一个或多个属性组成。在实际使用中，有下列几种键。（1）超键（superKey）：在关系中能唯一标识元组的属性集称为关系模式的超键。（2）候选键（candidateKey）：不含有多余属性的超键称为候选键。在最简单的情况下，候选码只包含一个属性。（3）主键(primaryKey)：用户选作元组标识的候选键称为主键。一般如不加说明，键是指主键。,基本术语(4)（续）,（4）全键(Allkey)：在最极端的情况下，关系模式的所有属性组是这个关系模式的候选键，称为全键（All-key）例：朋友关系,基本术语(4)（续）,例：在图2.1中，（工号，姓名）是模式的一个超键，但不是候选键，而（工号）是候选键。在实际使用中，如果选择（工号）作为删除或查找元组的标志，那么称（工号）是主键。（5）外键（foreignKey）：如果模式R中属性K是其他模式的主键，那么K在模式R中称为外键。例：S（S#，SNAME，AGE，SEX）SC（S#，C#，GRADE）在关系S中S#为主键，在关系SC中S#为外键。,基本术语(5),关系中每一个属性都有一个取值范围，称为属性的值域。属性A的取值范围用DOM（A）表示。,关系的定义和性质,定义2.2关系是一个具有相同属性的元组的集合。在关系模型中，对关系作了下列规范性限制：（1）关系中每一个属性值都是不可分解的；（2）关系中不允许出现重复元组（即不允许出现相同的元组）；（3）由于关系是一个集合，因此不考虑元组间的顺序，即没有行序；（4）元组中的属性在理论上也是无序的，但使用时按习惯考虑列的顺序。,关系模型的3类完整性规则(1),实体完整性规则（entityintegrityrule）要求关系中元组在组成主键的属性上不能有空值。如果出现空值，那么主键值就起不了惟一标织元组的作用。,关系模型的3类完整性规则(2),参照完整性规则（referenceintegrityrule）定义2.3参照完整性规则的形式定义如下：如果属性集K是关系模式R1的主键，K也是关系模式R2的外键，那么在R2的关系中，K的取值只允许两种可能，或者为空值，或者等于R1关系中某个主键值。这条规则的实质是“不允许引用不存在的实体”。在上述形式定义中，关系模式R1的关系称为“参照关系”，关系模式R2的关系称为“依赖关系”。R1和R2的关系也称为“主表”和“副表”(PowerBuilder)，“父表”和“子表”(VisualFoxpro)。,关系模型的3类完整性规则(3),例2.1下面各种情况说明了参照完整性规则在关系中如何实现的。在关系数据库中有下列两个关系模式：S（S#，SNAME，AGE，SEX）SC（S#，C#，GRADE）在关系S中S#为主键，在关系SC中S#为外键。据规则要求关系SC中的S#值应该在关系S中出现。如果关系SC中有一个元组（S7,C4,80），而学号S7却在关系S中找不到，那么我们就认为在关系SC中引用了一个不存在的学生实体，这就违反了参照完整性规则。另外，在关系SC中S#不仅是外键，也是主键的一部分，因此这里S#值不允许空。,关系模型的3类完整性规则(4),设工厂数据库中有两个关系模式：DEPT(D#，DNAME)EMP(E#，ENAME，SALARY，D#)车间模式DEPT的属性为车间编号、车间名，职工模式EMP的属性为工号、姓名、工资、所在车间的编号。每个模式的主键与外键已标出。在EMP中，由于D#不在主键中，因此D#值允许空。,关系模型的3类完整性规则(5),设课程之间有先修、后继联系。模式如下：R(C#，CNAME，PC#)其属性表示课程号、课程名、先修课的课程号。如果规定，每门课程的直接先修课只有一门，那么模式R的主键是C#，外键是PC#.。这里参照完整性在一个模式中实现。即每门课程的直接先修课必须在关系中出现。,关系模型的3类完整性规则(6),用户定义的完整性规则在建立关系模式时，对属性定义了数据类型，即使这样可能还满足不了用户的需求。此时，用户可以针对具体的数据约束，设置完整性规则，由系统来检验实施，以使用统一的方法处理它们，不再由应用程序承担这项工作。例如学生的年龄定义为两位整数，范围还太大，我们可以写如下规则把年龄限制在1530岁之间：CHECK（AGEBETWEEN15AND30）,数据结构图,数据结构图可用来表示关系数据库中表与表之间的联系。矩形框表示关系模式框间的连线表示其联系连线端点的“鸡爪型”表示“多”的一端P42图2.3,关系模型的3层体系结构,在关系模型中，记录类型称为关系模式，而关系模式的集合就是数据库的概念模式。在系统实现时，关系模式和属性的命名一般都用英文单词。如：,学生关系模式S(S#，SNAME，AGE，SEX)选课关系模式SC(S#，C#，GRADE)课程关系模式C(C#，CNAME，TEACHER),图2.6关系模式集,关系模型的3层体系结构-子模式,子模式是用户所用到的那部分数据的描述。除此之外，还应指出数据与关系模式中相应数据的联系。例如，用户需要用到子模式G（图2.4）。,成绩子模式G(S#，SNAME，C#，GRADE),图2.4子模式,关系模型的3层体系结构-存储模式,图2.6关系S和SC的环结构,在有些DBMS中，关系存储是作为文件看待的，每个元组就是一个记录。由于关系模式有键，因此存储一个关系可用散列方法或索引方法实现。如果关系的元组数目较少（100个以内），那么也可以用“堆文件”方式实现（即没有特定的次序）。此外，还可对任意的属性集建立辅助索引。,关系模型的形式定义,关系模型有三个重要组成部分：数据结构，数据操纵，数据完整性规则。（1）数据结构：数据库中全部数据及其相互联系都被组织成“关系”（二维表格）的形式。关系模型基本的数据结构是关系。（2）数据操纵：关系模型提供一组完备的高级关系运算，以支持对数据库的各种操作。关系运算分成关系代数、关系演算和关系逻辑等三类。（3）数据完整性规则：数据库中数据必须满足实体完整性，参照完整性和用户定义的完整性等三类完整性规则。,关系模型的优点,与其它数据模型相比，关系模型突出的优点如下：（1）关系模型提供单一的数据结构形式，具有高度的简明性和精确性。（2）关系模型的逻辑结构和相应的操作完全独立于数据存储方式，具有高度的数据独立性。（3）关系模型使数据库的研究建立在比较坚实的数学基础上。（4）关系数据库语言与一阶谓词逻辑的固有内在联系，为以关系数据库为基础的推理系统和知识库系统的研究提供了方便。,关系查询语言和关系运算,关系数据库的数据操纵语言（DML）的语句分成查询语句和更新语句两大类。查询语句用于描述用户的各种检索要求；更新语句用于描述用户进行插入、删除、修改等操作。关于查询的理论称为“关系运算理论”。关系查询语言根据其理论基础的不同分成三类：（1）关系代数语言：查询操作以集合操作为基础的运算（2）关系演算语言：查询操作以谓词演算为基础的运算（3）关系逻辑语言：查询操作以if-then逻辑操作为基础的运算,2.2关系代数,关系代数：一组高级运算的集合，运算的对象为关系。关系代数运算分为：传统的集合运算并、差、交、广义笛卡尔积专门的关系运算选择、投影、连接、除五个基本运算：并、差、笛卡尔积、选择、投影，其他运算可由他们推出。,关系代数的五个基本操作(1),并（Union）设关系R和S具有相同的关系模式，R和S的并是由属于R或属于S的元组构成的集合，记为RS。形式定义如下：RSt|tRtSt是元组变量，R和S的元数相同。差（Difference）设关系R和S具有相同的关系模式，R和S的差是由属于R但不属于S的元组构成的集合，记为RS。形式定义如下：RSt|tRtSR和S的元数相同。,关系代数的五个基本操作（1）,R,S,RS,R-S,关系代数的五个基本操作（1）,Rn元关系，k1个元组Sm元关系，k2个元组笛卡尔积：RS列：（n+m）列的元组的集合元组的前n列是关系R的一个元组后m列是关系S的一个元组行：k1k2个元组RS=tr,ts|trRtsS,关系代数的五个基本操作（1）,R,S,RS,关系代数的五个基本操作（2）,投影：1）投影运算符的含义从R中选择出若干属性列组成新的关系A(R)=tA|tRA：R中的属性列A=Ai1,Ai2,Ai3,AiktR表示t是R的一个元组tA=(tAi1，tAi2，tAik)表示元组t在属性列A上诸分量的集合。A(R)可写为i1，im（R）,关系代数的五个基本操作（2）,2）投影操作主要是从列的角度进行运算但投影之后不仅取消了原关系中的某些列，而且还可能取消某些元组（避免重复行）,关系代数的五个基本操作（2）,R,S,C，A(R)或,3，1(R),A，C(S)或,1，3(S),关系代数的五个基本操作（3）,1)选择:又称为限制（Restriction）2)选择运算符的含义在关系R中选择满足给定条件的诸元组F(R)=t|tRF(t)=真F：选择条件，是一个逻辑表达式，基本形式为：(X1Y1)(X2Y2)：比较运算符（，或）X1，Y1等：属性名、常量、简单函数；属性名也可以用它的序号来代替；：逻辑运算符（或）：表示任选项：表示上述格式可以重复下去,关系代数的五个基本操作（3）,例如，23（R）表示从R中挑选第2个分量值大于3的元组所构成的关系。书写时，为了与属性序号区别起见，常量用引号括起来，而属性序号或属性名不要用引号括起来。3)选择运算是从行的角度进行的运算,关系代数的五个基本操作（3）,R,A=a1(R)或,1=a1(R),例：设有一个学生-课程数据库，包括学生关系Student、课程关系Course和选修关系,关系代数的五个基本操作（例）,Student,关系代数的五个基本操作（例）,例1查询学生的姓名和所在系即求Student关系上学生姓名和所在系两个属性上的投影Sname，Sdept(Student)或2，5(Student)结果：,关系代数的五个基本操作（例）,例2查询学生关系Student中都有哪些系Sdept(Student)结果：,关系代数的五个基本操作（例）,例3查询信息系（IS系）全体学生Sdept=IS(Student)或5=IS(Student)结果：,关系代数的五个基本操作（例）,例4查询年龄小于20岁的学生Sage0），那么RS是一个（r-s）元的元组的集合。（RS）是满足下列条件的最大关系：其中每个元组t与S中每个元组u组成的新元组必在关系R中。RS1，2，r-s（R）-1，2，r-s（1，2，r-s（R）S）-R）,2.2.3关系代数运算的应用实例,在关系代数运算中，把由五个基本操作经过有限次复合的式子称为关系代数表达式。这种表达式的运算结果仍是一个关系。我们可以用关系代数表达式表示各种数据查询操作。,教学数据库系统应用实例,例2.7设有教学数据库系统的四个关系：教师关系T(T#,TNAME,TITLE)学生关系S(S#,SNAME,AGE,SEX)选课关系SC(S#,C#,GRADE)课程关系C(C#,CNAME,T#),应用实例（1）,(1)检索学习课程号为C2的学生学号与成绩分析：所求的S#与GRADE属性均在SC关系中；约束条件为C#是C2,C#在SC中，因此对SC关系操作。解：s#,GRADE(c#=c2(sc)注：约束条件成为选择运算的选择条件。,应用实例（2）,(2)检索学习课程号为C2的学生学号与姓名分析：所求的S#与SNAME在S中，选择条件中C#在SC和C中，因此必须把S和SC或C连接，但C与S没有公共属性。解：s#,SNAME(c#=c2(SSC),应用实例（3）,(3)检索至少选修LIU老师所授课程中一门课程的学生学号与姓名。分析：所求的S#与SNAME在S中，选择条件中LIU在T中，但S和T没有公共属性，因此必须借助SC和C。(SSC)C=S(SCC)=SSCC解：s#,SNAME(TNAME=LIU(SSCCT),应用实例（4）,(4)检索选修课程号为C2或C4的学生学号。分析：所求的S#与选择条件中C#都在SC中，选择条件用逻辑或表示，所求的仅有学号。解：s#(C#=c2C#=c4(SC),应用实例（5）,(5)检索至少选修课程号为C2和C4的学生学号。分析：所求S#和选择条件中的C#均在SC中，因此对SC操作，但SC中元组仅有一个C#值，要包括C2和C4必须有一个元组中有两个C#值，考虑SCSC中同一学生的元组。解：1(1=42=C25=C4(SCSC)错误解：1(2=C22=C4(SC),应用实例（6）,(6)检索不学C2课的学生姓名与年龄。分析：所有的学生中去除选学C2课的学生。解：SNAME,AGE(S)-SNAME,AGE(c#=c2(SSC)注：检索条件中有否定词的用差运算。错误解：SNAME,AGE(c#c2(SSC),应用实例（7）,(7)检索学习全部课程的学生姓名。分析：全部课程为：C#(C)学习了全部课程的学生为S#,C#(SC)C#(C)但SC中没有SNAME，因此要与S连接。解：SNAME(S(S#,C#(SC)C#(C)注：检索条件中有全部、所有等全称量词的用除运算。,应用实例（8）,(8)检索所学课程包含S3所学课程的学生的学号。分析：S3所学的课程可用C#(S#=S3(SC)。解：S#,C#(SC)C#(S#=S3(SC),关系代数的七个扩充操作（1）,改名：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)广义投影：F1,Fn(R)Fi为常量与属性的算术表达式。例：s#,c#,GRADE*1.05(c#=c2(sc)赋值：例：TEMPRS,关系代数的七个扩充操作（2）,外连接（outerjoin）,R,S,RS,RS左外连接,RS外连接,RS右外连接,关系代数的七个扩充操作（3）,外部并（outerunion）：,关系代数的七个扩充操作（4）,半连接（semijoin）：RS=R(RS)SR=S(SR)RSSR,R,S,关系代数的七个扩充操作（5）,聚集操作：max、min、avg、sum、count例：求男同学的平均年龄avgage(SEX=M(s)求年龄为18岁的人数counts#(AGE=18(s),2.3关系演算,把数理逻辑的谓词演算引入到关系运算中，就可得到以关系演算为基础的运算。关系演算又可分为元组关系演算和域关系演算，前者以元组为变量，后者以属性（域）为变量。,2.3.1元组关系演算,在元组关系演算（TupleRelationalCalculus）中，元组关系演算表达式简称为元组表达式，其一般形式为t|P（t）其中，t是元组变量，表示一个元数固定的元组；P是公式，在数理逻辑中也称为谓词，也就是计算机语言中的条件表达式。t|P（t）表示满足公式P的所有元组t的集合。,公式（1）,在元组表达式中，公式由原子公式组成。定义2.4原子公式（Atoms）有下列三种形式：R（s）:表示命题“s是关系R的一个元组”siuj：表示命题“元组s的第i个分量和元组u的第j个分量之间满足关系”sia或auj：a是常量，“sia”表示命题“元组s的第i个分量与常量a之间满足关系”在定义关系演算操作时，要用到“自由”（Free）和“约束”（Bound）变量概念。在一个公式中，如果元组变量未用存在量词或全称量词符号定义，那么称为自由元组变量，否则称为约束元组变量。,公式（2）,定义2.5公式（Formulas）的递归定义如下：每个原子是一个公式。其中的元组变量是自由变量。如果P1和P2是公式，那么P1、P1P2、P1P2和P1P2也都是公式。如果P1是公式，那么（s）（P1）和（s）（P1）也都是公式。公式中各种运算符的优先级从高到低依次为：，和，和，。在公式外还可以加括号，以改变上述优先顺序。公式只能由上述四种形式构成，除此之外构成的都不是公式。,元组关系演算实例,例2.15图2.20的（a）、（b）是关系R和S，（c）（g）分别是下面五个元组表达式的值,图2.20元组关系演算的例子,R1=t|S（t）t12R2=t|R（t）S（t）R3=t|（u）（S（t）R（u）t3u1）,R5=t|（u）（v）（R（u)S（v）u1v2t1=u2t2=v3t3=u1）,元组关系演算的等价转换规则,在元组关系演算的公式中，有下列三个等价的转换规则：P1P2等价于(P1P2)；P1P2等价于（P1P2）。（s）（P1（s）等价于(s)（P1（s）；（s）（P1（s）等价于(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（R）可写成t|（R（t）t2=d）。,2.3.2域关系演算,原子公式有两种形式：R（x1xk）；xy。公式中也可使用、和等逻辑运算符,(x)和（x），但变量x是域变量，不是元组变量。自由域变量、约束域变量等概念和元组演算中一样。域演算表达式是形为t1tkP（t1，tk）的表达式，其中P（t1，tk）是关于自由域变量t1，tk的公式。,域关系演算实例,例2.19图2.21的（a）、（b）、（c）是三个关系R、S、W，（d）、（e）、（f）分别表示下面三个域表达式的值。,（a）关系R（b）关系S（c）关系W（d）R1（e）R2（f）R3图2.21域关系演算的例子,R1=xyz|R（xyz）x3R2=xyz|R（xyz）（S（xyz）y=4）R3=xyz|（u）（v）（R（zxu）w（yv）uv）,元组表达式到域表达式的转换,转换规则如下：对于k元的元组变量t，可引入k个域变量t1tk，在公式中t用t1tk替换，元组分量ti用ti替换。对于每个量词（u）或（u），若u是m元的元组变量，则引入m个新的域变量u1um。在量词的辖域内，u用u1um替换，ui用ui替换，（u）用（u1）（um）替换，（u）用（u1）（um）替换。,关系运算的安全性,无限关系：关系中的元组有无限多个。如：t|R（t）无穷验证：验证公式真假时需要进行无限次验证。如验证：（u）P1（u）为假或（u）P1（u）为真定义2.6在数据库技术中，不产生无限关系和无穷验证的运算称为安全运算，相应的表达式称为安全表达式，所采取的措施称为安全约束。在关系演算中，我们约定，运算只在表达式中公式涉及的关系值范围内进行，这样就不会产生无限关系和无穷验证问题，关系演算是安全的。,关系运算的等价性,并、差、笛尔卡积、投影和选择是关系代数最基本的操作，并构成了关系代数运算的最小完备集。已经证明，在这个基础上，关系代数、安全的元组关系演算、安全的域关系演算在关系的表达和操作能力上是完全等价的。相应于关系代数、元组演算和域演算三种关系运算，关系查询语言的典型代表是ISBL语言、QUEL语言和QBE语言。,关系运算的等价性,ISBL(InformationSystemBaseLanguage)于1976年由IBM公司英格兰底特律科学中心研制出来，与关系代数非常接近，每个查询语句都近似于一个关系代数表达式。QUEL(QueryLanguage)是美国伯克利加州大学研制的关系数据库系统INGRES的查询语言，1975年投入运行，是一种基于元组关系演算的数据查询语言。,关系运算的等价性,QBE(QueryByExample)由M.M.Zloof提出，1978年在IBM370上实现，是约克镇IBM高级研究实验室为图形显示终端用户设计的一种域演算语言。SQL(StructuredQueryLanguage)是一种介于关系代数和元组演算之间的关系查询语言，现已成为关系数据库的标准语言。,2.4关系代数表达式的优化,在关系代数表达式中需要指出若干关系的操作步骤。那么，系统应该以什么样的操作顺序，才能做到既省时间，又省空间，而且效率也比较高呢？这个问题称为查询优化问题。在关系代数运算中，笛卡儿积和连接运算是最费时间的。数据库管理系统产品强调：一个查询中涉及的基本表的个数不要超过7个，最多不要超过10个,关系代数表达式的优化(1),例2.22设关系R和S都是二元关系，属性名分别为A，B和C，D。设有一个查询可用关系代数表达式表示：E1=A（B=CD=99（RS）也可以把选择条件D=99移到笛卡儿积中的关系S前面：E2=A（B=C（RD=99（S）还可以把选择条件BC与笛卡儿积结合成等值连接形式：E3=A（RB=CD=99（S）这三个关系代数表达式是等价的，但执行的效率大不一样。显然，求El，E2，E3的大部分时间是花在连接操作上的。E3（目的：减少内外存交换的信息量）花费的时间：E1E2E3,查询优化,导致查询低效的原因冗余计算内外存交换次数太多提高效率的途径（启发式优化的目标）减少中间结果的大小减少不相关的数据运算减少扫描表的次数减少不相关元组的读取,查询优化,逻辑优化的一般准则1）选择操作尽可能先做目的：大大减少中间结果的大小2）执行连接前对关系适当地预处理两种预处理方法：在连接属性上建立索引和对关系排序目的：减少扫描表的次数减少不相关元组的读取,实例例如：SSC.两种预处理方法：,索引连接方法：(1)在SC上建立S#的索引；(2)对S中的每一个元组，由S#值通过SC的索引查找相应的SC元组；(3)把这些SC元组和S元组连接起来；效率：S和SC表均只要扫描一遍。处理时间是两个关系大小的线性函数。,排序连接方法：(1)对S和SC按S#排序；(2)取S表中第一个S#，依次扫描SC表中具有相同S#的元组，把它们连接起来；(3)当扫描到S#不相同的第一个SC元组时，返回S表扫描它的下一个元组，再扫描SC表中具有相同S#的元组，把它们连接起来；效率：S和SC表均只要扫描一遍。处理时间要加上对两个表排序的时间。,查询优化,逻辑优化的一般准则3）投影运算和选择运算同时进行目的：避免重复扫描表4）投影同其前或其后的双目运算结合起来目的：避免重复扫描表,查询优化,逻辑优化的一般准则5）把某些选择同在它前面要执行的笛卡尔积结合起来成为一个连接运算目的：减少内外存交换的信息量6）找出公共子表达式目的：减少计算量,关系代数表达式的优化(2),例：求选修了课程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表遍数*每遍块数=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（减少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#上有索引，S表在S#上有索引读SC表索引=读SC表总块数=50/1001块读数据时间中间结果大小=50条不必写入外存,关系代数表达式的优化（8）,读S表索引=读S表总块数=50/10=5块读数据时间=5/20总时间10秒,关系代数表达式的等价变换规则(1),连接和笛卡儿积的交换律E1E2E2E1E1E2E2E1E1E2E2E1连接和笛卡儿积的结合律(E1E2)E3E1(E2E3)(E1E2)E3E1(E2E3)(E1E2)E3E1(E2E3),F,F,F2,F2,F1,F1,关系代数表达式的等价变换规则(1),投影的级联L1(L2(Ln(E)L1(E)选择的级联F1(F2(E)F1F2(E)F2F1(E)选择和投影操