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

第2章 关系模型和关系运算理论,数据库系统 2010年,本章重要概念（一）,（1）基本概念 关系模型，关键码（主键和外键），关系的定义和性质，三类完整性规则，过程性语言与非过程性语言。 （2）关系代数 五个基本操作，四个组合操作，七个扩充操作。,本章重要概念（二）,（3）关系演算 元组关系演算和域关系演算的原子公式、公式的定义。关系演算的安全性和等价性。 （4）关系代数表达式的优化 关系代数表达式的等价及等价转换规则，启化式优化算法。 （5）关系逻辑 谓词、原子、规则和查询，规则的安全性，用规则模拟关系代数表达式。,本章概要,本章先介绍关系模型的基本概念；然后介绍关系运算的三种理论：关系代数、关系演算和关系逻辑。,2.1 关系模型的基本概念,系统而严格地提出关系模型的是美国IBM公司的E.F.Codd 1970年提出关系数据模型 E.F.Codd, “A Relational Model of Data for Large Shared Data Banks”, Communication of the ACM,1970 之后，提出了关系代数和关系演算的概念 1972年提出了关系的第一、第二、第三范式 1974年提出了关系的BC范式,2.1 关系模型的基本概念,关系模型建立在集合代数的基础上 关系数据库应用数学方法来处理数据库中的数据 关系数据库系统 是支持关系模型的数据库系统 80年代后，关系数据库系统成为最重要、最流行的数据库系统,2.1 关系模型的基本概念,典型实验系统 System R University INGRES 典型商用系统 ORACLE SYBASE INFORMIX DB2 INGRES,基本术语(1),定义2.1 用二维表格表示实体集，用关键码表示实体之间联系的数据模型称为关系模型（relational Model）。,图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）超键（super Key）：在关系中能唯一标识元组的属性集称为关系模式的超键。 （2）候选键（candidate Key）：不含有多余属性的超键称为候选键。 在最简单的情况下，候选码只包含一个属性。 （3）主键(primary Key)：用户选作元组标识的候选键称为主键。 一般如不加说明，键是指主键。,基本术语(4)（续）,（4）全键(All key)：在最极端的情况下，关系模式的所有属性组是这个关系模式的候选键，称为全键（All-key） 例：朋友关系,基本术语(4)（续）,例：在图2.1中，（工号，姓名）是模式的一个超键，但不是候选键，而（工号）是候选键。在实际使用中，如果选择（工号）作为删除或查找元组的标志，那么称（工号）是主键。 （5）外键（foreign Key）：如果模式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),实体完整性规则（entity integrity rule） 要求关系中元组在组成主键的属性上不能有空值。如果出现空值，那么主键值就起不了惟一标织元组的作用。,关系模型的3类完整性规则 (2),参照完整性规则（reference integrity rule） 定义2.3 参照完整性规则的形式定义如下： 如果属性集K是关系模式R1的主键，K也是关系模式R2的外键，那么在R2的关系中，K的取值只允许两种可能，或者为空值，或者等于R1关系中某个主键值。 这条规则的实质是“不允许引用不存在的实体”。 在上述形式定义中，关系模式R1的关系称为“参照关系”，关系模式R2的关系称为“依赖关系”。R1和R2 的关系也称为“主表”和“副表”(PowerBuilder)，“父表”和“子表”(Visual Foxpro)。,关系模型的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（AGE BETWEEN 15 AND 30）,数据结构图,数据结构图可用来表示关系数据库中表与表之间的联系。 矩形框表示关系模式 框间的连线表示其联系 连线端点的“鸡爪型”表示“多”的一端 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 | tR tS t是元组变量，R和S的元数相同。 差（Difference） 设关系R和S具有相同的关系模式，R和S的差是由属于R但不属于S的元组构成的集合，记为RS。形式定义如下： RS t | tR tS R和S的元数相同。,关系代数的五个基本操作（1）,R,S,RS,R-S,关系代数的五个基本操作（1）,R n元关系，k1个元组 S m元关系，k2个元组 笛卡尔积：RS 列：（n+m）列的元组的集合 元组的前n列是关系R的一个元组 后m列是关系S的一个元组 行：k1k2个元组 RS = tr, ts| tr R ts S ,关系代数的五个基本操作（1）,R,S,R S,关系代数的五个基本操作（2）,投影： 1）投影运算符的含义 从R中选择出若干属性列组成新的关系 A(R) = tA | t R A：R中的属性列 A=Ai1,Ai2,Ai3,Aik t R表示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岁的学生 Sage 20(Student) 或 4 20(Student) 结果：,关系代数的四个组合操作 (1),交（intersection） 关系R和S的交是由属于R又属于S的元组构成的集合，记为RS，这里要求R和S定义在相同的关系模式上。形式定义如下： RSttR tS R和S的元数相同。 由于RS = R-（R-S），或RS = S-（S-R），因此交操作不是一个独立的操作。,关系代数的四个组合操作（1）,R,S,R S,关系代数的四个组合操作（2）,连接（join）连接有两种：连接和F连接（这里是算术比较符，F是公式）。 连接 从两个关系的笛卡尔积中选取属性间满足一定条件的元组 R S = t|t= tr Rts StrAtsB A和B：分别为R和S上可比的属性 ：比较运算符,关系代数的四个组合操作（2）,连接运算从R和S的广义笛卡尔积RS中选取（R关系）在A属性上的值与（S关系）在B属性上值满足比较关系的元组,关系代数的四个组合操作（2）,R,S,举例 例1,R,S,关系代数的四个组合操作（2）,等值连接（equijoin） 什么是等值连接 为“”的连接运算称为等值连接 等值连接的含义 从关系R与S的广义笛卡尔积中选取A、B属性值相等的那些元组，即等值连接为： R S = t|t= tr Rts StrA=tsB ,A=B,关系代数的四个组合操作（2）,例2 ：等值连接 R S,R,S,关系代数的四个组合操作（2）,自然连接（Natural join） 什么是自然连接 自然连接是一种特殊的等值连接 两个关系中进行比较的分量必须是相同的属性组 在结果中把重复的属性列去掉 自然连接的含义 R和S具有相同的属性组B,R S = t|t= tr Rts StrB = tsB ,关系代数的四个组合操作（2）,例3自然连接 R S,R,S,关系代数的四个组合操作（2）,一般的连接操作是从行的角度进行运算。 自然连接还需要取消重复列，所以是同时从行和列的角度进行运算。,关系代数的四个组合操作（2）, F连接 F连接是从关系R和S的笛卡儿积中选取属性间满足某一公式F的元组, 这里F是形为F1F2Fn的公式，每个FP是形为ij的式子，而i和j分别为关系R和S的第i、第j个分量的序号。,关系代数的四个组合操作（2）,例4 F连接 R S,R,S,关系代数的四个组合操作（3）,除操作是同时从行和列角度进行运算,关系代数的四个组合操作（3）,R,S,关系代数的四个组合操作（3）,除法（division） 设关系R和S的元数分别为r和s（设rs0），那么RS是一个（r-s）元的元组的集合。（RS）是满足下列条件的最大关系：其中每个元组t与S中每个元组u组成的新元组必在关系R中。 RS 1，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 (S SC),应用实例（3）,(3)检索至少选修LIU老师所授课程中一门课程的学生学号与姓名。 分析：所求的S#与SNAME在S中，选择条件中LIU在T中，但S和T没有公共属性，因此必须借助SC和C。 (S SC) C= S (SC C)= S SC C 解： s#,SNAME(TNAME=LIU (S SC C T),应用实例（4）,(4)检索选修课程号为C2或C4的学生学号。 分析：所求的S#与选择条件中C#都在SC中，选择条件用逻辑或表示，所求的仅有学号。 解： s#( C#=c2 C#=c4 (SC),应用实例（5）,(5)检索至少选修课程号为C2和C4的学生学号。 分析：所求S#和选择条件中的C#均在SC中，因此对SC操作，但SC中元组仅有一个C#值，要包括C2和C4必须有一个元组中有两个C#值，考虑SC SC中同一学生的元组。 解： 1(1=4 2=C2 5=C4(SC SC) 错误解： 1(2=C2 2=C4(SC),应用实例（6）,(6)检索不学C2课的学生姓名与年龄。 分析：所有的学生中去除选学C2课的学生。 解： SNAME,AGE(S)- SNAME,AGE( c#=c2(S SC) 注：检索条件中有否定词的用差运算。 错误解： SNAME,AGE( c# c2(S SC),应用实例（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) 赋值 ： 例：TEMP R S,关系代数的七个扩充操作（2）,外连接（outer join）,R,S,R S,R S 左外连接,R S 外连接,R S 右外连接,关系代数的七个扩充操作（3）,外部并（outer union）：,关系代数的七个扩充操作（4）,半连接（semijoin）： R S=R (R S) S R= S (S R) R S S R,R,S,关系代数的七个扩充操作（5）,聚集操作 ：max、min、avg、sum、count 例：求男同学的平均年龄 avgage( SEX=M(s) 求年龄为18岁的人数 counts#( AGE=18(s),2.3 关系演算,把数理逻辑的谓词演算引入到关系运算中，就可得到以关系演算为基础的运算。关系演算又可分为元组关系演算和域关系演算，前者以元组为变量，后者以属性（域）为变量。,2.3.1元组关系演算,在元组关系演算（Tuple Relational Calculus）中，元组 关系演算表达式简称为元组表达式，其一般形式为 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）t12 R2 = 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=v3t3=u1）,元组关系演算的等价转换规则,在元组关系演算的公式中，有下列三个等价的转换规则： P1P2等价于(P1P2)； P1P2等价于（P1P2）。 （s）（P1（s）等价于(s)（P1（s）； （s）（P1（s）等价于(s）（P1（s）。 P1P2等价于 P1P2。,关系代数表达式到元组表达式的转换,例2.16 RS可用 t | R（t）S（t）表示； R-S可用 t | R（t）S（t） 表示； RS可用 t |（u）（v）（R（u）S(V) t1=u1 t2=u2t3=u3 t4=v1 t5=v2 t6=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） x3 R2= 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(Information System Base Language)于1976年由IBM公司英格兰底特律科学中心研制出来，与关系代数非常接近，每个查询语句都近似于一个关系代数表达式。 QUEL(Query Language)是美国伯克利加州大学研制的关系数据库系统INGRES的查询语言，1975年投入运行，是一种基于元组关系演算的数据查询语言。,关系运算的等价性,QBE(Query By Example)由M.M.Zloof提出，1978年在IBM 370上实现，是约克镇IBM高级研究实验室为图形显示终端用户设计的一种域演算语言。 SQL(Structured Query Language)是一种介于关系代数和元组演算之间的关系查询语言，现已成为关系数据库的标准语言。,2.4 关系代数表达式的优化,在关系代数表达式中需要指出若干关系的操作步骤。那么，系统应该以什么样的操作顺序，才能做到既省时间，又省空间，而且效率也比较高呢？这个问题称为查询优化问题。 在关系代数运算中，笛卡儿积和连接运算是最费时间的。 数据库管理系统产品强调：一个查询中涉及的基本表的个数不要超过7个，最多不要超过10个,关系代数表达式的优化(1),例2.22 设关系R和S都是二元关系，属性名分别为A，B和C，D。设有一个查询可用关系代数表达式表示： E1= A（ B=CD=99（R S） 也可以把选择条件D=99移到笛卡儿积中的关系S前面： E2= A（ B=C（R D=99（S） 还可以把选择条件BC与笛卡儿积结合成等值连接形式： E3= A（R B=C D=99（S） 这三个关系代数表达式是等价的，但执行的效率大不一样。显然，求El，E2，E3的大部分时间是花在连接操作上的。E3（目的：减少内外存交换的信息量） 花费的时间：E1E2E3,查询优化,导致查询低效的原因 冗余计算 内外存交换次数太多 提高效率的途径（启发式优化的目标） 减少中间结果的大小 减少不相关的数据运算 减少扫描表的次数 减少不相关元组的读取,查询优化,逻辑优化的一般准则 1）选择操作尽可能先做 目的：大大减少中间结果的大小 2）执行连接前对关系适当地预处理 两种预处理方法：在连接属性上建立索引和对关系排序 目的： 减少扫描表的次数 减少不相关元组的读取,实例例如： S SC. 两种预处理方法：,索引连接方法： (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）,1 sname(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. 2 name(SC.C#= 2 (S SC) 读取总块数= 2100块 读数据时间=2100/20=105秒 中间结果大小=10000 （减少1000倍） 写中间结果时间=10000/10/20=50秒 读数据时间=50秒 总时间1055050秒205秒=3.4分,关系代数表达式的优化（6）,3. 3 Sname(S SC.C#= 2 (SC) 读SC表总块数= 10000/100=100块 读数据时间=100/20=5秒 中间结果大小=50条 不必写入外存 读S表总块数= 1000/10=100块 读数据时间=100/20=5秒 总时间55秒10秒,关系代数表达式的优化（7）,4. 4 name(S SC.C#=2 (SC) 假设SC表在C#上有索引，S表在S#上有索引 读SC表索引= 读SC表总块数= 50/1001块 读数据时间 中间结果大小=50条 不必写入外存,关系代数表达式的优化（8）, 读S表索引= 读S表总块数= 50/10=5块 读数据时间 =5/20 总时间10秒,关系代数表达式的等价变换规则 (1),连接和笛卡儿积的交换律 E1 E2 E2 E1 E1 E2 E2 E1 E1 E2 E2 E1 连接和笛卡儿积的结合律 (E1 E2) E3 E1 (E2 E3) (E1 E2) E3 E1 (E2 E3) (E1 E2) E3 E1 (E2 E3),F,F,F2,F2,F1,F1,关系代数表达式的等价变换规则 (1),投影的级联 L1(L2 ( ( Ln(E) L1(E) 选择的级联 F1 (F2(E) F1F2(E) F2F1(E) 选择和投影操作的交换 L(F(E) L(F(LL1 ( E) L(F(E) F(L( E),关系代数表达式的等价变换规则 (1),选择对笛卡儿积的分配律 F=F1F2 F(E1E2) F(E1) E2 F(E1E2) F1(E1) F2( E2 ) F(E1E2) F2(F1 (E1) E2 ) 选择对并的分配律 F(E1E2) F(E1) F( E2 ),关系代数表达式的等价变换规则 (2),选择对集合差的分配律 F(E1E2) F(E1) F( E2 ) F(E1E2) F(E1) E2 选择对自然连接的分配律 F(E1 E2) F(E1) F( E2 ) 这里要求F只涉及E1和E2的公共属性 投影对笛卡儿积的分配律 L1L2 (E1E2) L1(E1) L2 ( E2),关系代数表达式的等价变换规则 (2),投影对并的分配律 L (E1E2) L (E1)L (E2) 选择与连接操作的结合 F(E1E2) E1 E2 F1(E1 E2) E1 E2,F,F2,F1F2,关系代数表达式的等价变换规则 (2),并和交的交换律 (E1E2)(E2E1) (E1E2)(E2E1) 并和交的结合律 (E1E2)E3 E1(E2E3) (E1E2)E3 E1(E2E3),关系代数表达式的优化算法 (1),在关系代数表达式中，最花费时间和空间的运算是笛卡儿积和连接操作，为此，引出三条启发式规则，用于对表达式进行转换，以减少中间关系的大小。 尽可能早地执行选择操作； 尽可能早地执行投影操作； 避免直接做笛卡儿积，把笛卡儿积操作之前和之后的一连串选择和投影合并起来一起做。,关系代数表达式的优化算法 (2),算法2.1 关系代数表达式的启发式优化算法。 输入：一个关系代数表达式的语法树 输出：计算表达式的一个优化序列 例2.23,2.5 关系逻辑 (自学),关系逻辑和关系代数在表达功能上相差甚大，只有在规则被约束为安全的、非递归、在带有某些否定的情况下，关系逻辑才与关系代数等价。由于关系逻辑中引进了基于逻辑的规则概念，使得关系逻辑比关系代数在模拟现实世界能力方面更强。关系逻辑一般用在知识库的知识表达中。,小 结,关系模型的基本术语 关系模型的三类完整性规则 关系模型的三级体系结构 关系代数的五个基本操作、四个组合操作、七个扩充操作、用关系代数表达式表示数据查询操作（教材中P49的例2.6）。,重要内容分析（一）,（1）一般规则 对于只涉及到选择、投影、连接的查询可用下列表达式表示： （RS） 或者（R S） 对于否定的操作，一般要用差操作表示，例如“检索不学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非过程性语言与过程性语言的区别 编程时必须指出“干什么”及“怎么干”的语言，称为过程性语言；编程时只须指出“干什么”，不必指出“怎么干”的语言，称为非过程性语言。,