第2章关系模型和关系运算理论.ppt

《第2章关系模型和关系运算理论.ppt》由会员分享，可在线阅读，更多相关《第2章关系模型和关系运算理论.ppt（118页珍藏版）》请在三一文库上搜索。

1、1,第2章 关系模型和 关系运算理论,2,本章重要概念（1）,（1）基本概念 关系模型，关键码（主键和外键），关系的定义和性质，三类完整性规则，过程性语言与非过程性语言。 （2）关系代数 五个基本操作，四个组合操作，七个扩充操作。,3,本章重要概念（2）,（3）关系演算 元组关系演算和域关系演算的原子公式、公式的定义。关系演算的安全性和等价性。 （4）关系代数表达式的优化 关系代数表达式的等价及等价转换规则，启化式优化算法。 （5）关系逻辑 谓词、原子、规则和查询，规则的安全性，用规则模拟关系代数表达式。,4,本章概要,本章先介绍关系模型的基本概念；然后介绍关系运算的三种理论：关系代数、关系演

2、算和关系逻辑。,5,关系模型和关系运算理论,2.1 关系模型的基本概念 2.2 关系代数 2.3 关系演算 2.4 关系代数表达式的优化 2.5 关系逻辑 2.6 小结,6,2.1 关系模型的基本概念,2.1.1 基本术语 2.1.2 关系的定义和性质 2.1.3 关系模型的三类完整性规则 2.1.4 关系模型的三级体系结构 2.1.5 关系模型的形式定义和优点 2.1.6 关系查询语言和关系运算,返回,7,2.1.1 基本术语(1),定义2.1 用二维表格表示实体集，用关键码表示实体之间联系的数据模型称为关系模型（Relational Model）。,图2.1 学生登记表,8,2.1.1 基

3、本术语(2),在关系模型中，字段称为属性，字段值称为属性值，记录类型称为关系模式。在图2.1中，关系模式名是R。记录称为元组（tuple），元组的集合称为关系（relation）或实例（instance）。一般用大写字母A、B、C、 表示单个属性，用大写字母 、X、Y、Z表示属性集，用小写字母表示属性值，有时也习惯称呼关系为表或表格，元组为行(row)，属性为列(column)。 关系中属性个数称为“元数”（arity），元组个数为“基数”(cardinality)。,9,2.1.1 基本术语(3),关系元数为5，基数为4。,10,2.1.1 基本术语(4),关键码(key,简称键)由一个或多

4、个属性组成。在实际使用中，有下列几种键。 （1）超键（Super Key） （2）候选键（Candidate Key） （3）主键(Primary Key) 在图2.1中，（工号，姓名）是模式的一个超键，但不是候选键， 而（工号）是候选键。在实际使用中，如果选择（工号）作为删除或查找元组的标志，那么称（工号）是主键。 （4）外键（Foreign Key）,返回,11,2.1.2 关系的定义和性质,定义2.2 关系是一个属性数目相同的元组的 集合。 在关系模型中，对关系作了下列规范性限制： （1）关系中每一个属性值都是不可分解的； （2）关系中不允许出现重复元组 （即不允许出现相同的元组）； （

5、3）由于关系是一个集合，因此不考虑元组间 的顺序，即没有行序； （4）元组中的属性在理论上也是无序的， 但使用时按习惯考虑列的顺序。,返回,12,2.1.3 关系模型的完整性规则(1),实体完整性规则（entity integrity rule） 要求关系中元组在组成主键的属性上不能有空值。如果出现空值，那么主键值就起不了惟一标识元组的作用。,13,2.1.3 关系模型的完整性规则 (2),参照完整性规则（reference integrity rule） 定义2.3 参照完整性规则的形式定义如下： 如果属性集K是关系模式R1的主键，K也是关系模式R2的外键，那么在R2的关系中，K的取值只允许

6、两种可能，或者为空值，或者等于R1关系中某个主键值。 这条规则的实质是“不允许引用不存在的实体”。 在上述形式定义中，关系模式R1的关系称为“参照关系”，关系模式R2的关系称为“依赖关系”。“主表”和“副表”，“父表”和“子表”。,14,2.1.3 关系模型的完整性规则 (3),这条规则在具体使用时，有三点变通： 外键和相应的主键可以不同名， 只要定义在相同值域上即可； R1和R2也可以是同一个关系模式，此时表示了同一个关系中不同元组之间的联系； 外键值是否允许空，应视具体问题而定。,15,2.1.3 关系模型的完整性规则 (4),例 下面各种情况说明了参照完整性规则在关系中如何实现的。 在关

7、系数据库中有下列两个关系模式： S（S#，SNAME，AGE，SEX） SC（S#，C#，SCORE） 这里带 线者为主键，带 线者为外键。据规则要求关系SC中的S#值应该在关系S中出现。如果关系SC中有一个元组（S7,C4,80），而学号S7却在关系S中找不到，那么我们就认为在关系SC中引用了一个不存在的学生实体，这就违反了参照完整性规则。 另外，在关系SC中S# 不仅是外键，也是主键的一部分，因此这里S# 值不允许空。,16,2.1.3 关系模型的完整性规则 (5), 设工厂数据库中有两个关系模式： DEPT(D#，DNAME) EMP(E#，ENAME，SALARY，D# ) 车间模式D

8、EPT的属性为车间编号、车间名，职工模式EMP的属性为工号、姓名、工资、所在车间的编号。每个模式的主键与外键已标出。在EMP中，由于D# 不在主键中，因此D# 值允许空。,17,2.1.3 关系模型的完整性规则 (6), 设课程之间有先修、后继连系。模式如下： R（C#，CNAME，PC#） 其属性表示课程号、课程名、先修课的课程号。如果规定，每门课程的直接先修课只有一门，那么模式R的主键是C#，外键是PC#.。这里参照完整性在一个模式中实现。即每门课程的直接先修课必须在关系中出现。,18,2.1.3 关系模型的完整性规则 (7),例2.1 TEACHER（T#，TNAME，TITLE） CO

9、URSE （C#，CNAME，T#） STUDENT（S#，SNAME，AGE，SEX） SC （S#，C#，SCORE）,图2.3 关系模型的数据结构图（DSD）,19,2.1.3 关系模型的完整性规则 (8),用户定义的完整性规则 在建立关系模式时，对属性定义了数据类型，即使这样可能还满足不了用户的需求。此时，用户可以针对具体的数据约束，设置完整性规则，由系统来检验实施，以使用统一的方法处理它们，不再由应用程序承担这项工作。 例如学生的年龄定义为两位整数，范围还太大，我们可以写如下规则把年龄限制在1530岁之间： CHECK（AGE BETWEEN 15 AND 30）,返回,20,2.1

10、.4 关系模型的三层体系结构 - 关系模式,在关系模型中，记录类型称为关系模式，而关系模式的集合就是数据库的概念模式。在系统实现时，关系模式和属性的命名一般都用英文单词。,TEACHER（T#，TNAME，TITLE） COURSE （C#，CNAME，T#） STUDENT（S#，SNAME，AGE，SEX） SC （S#，C#，SCORE）,21,2.1.4 关系模型的三层体系结构 -子模式（1）,子模式是用户所用到的那部分数据的描述。除此之外，还应指出数据与关系模式中相应数据的连系。例如，用户需要用到子模式G（图2.3）。,成绩子模式 G(S#，SNAME，C#，SCORE),22,2.

11、1.4 关系模型的三层体系结构 -子模式（2）,80,23,2.1.4 关系模型的三层体系结构 -存储模式（1）,图2.6 关系STUDENT和SC的环结构,在有些DBMS中，关系存储是作为文件看待的，每个元组就是一个记录。由于关系模式有键，因此存储一个关系可用散列方法或索引方法实现。如果关系的元组数目较少（100个以内），那么也可以用“堆文件”方式实现（即没有特定的次序）。此外，还可对任意的属性集建立辅助索引。,24,2.1.4 关系模型的三层体系结构 -存储模式（2）,图2.7 两个关系存储在一起,25,2.1.5 关系模型的形式定义,关系模型有三个重要组成部分：数据结构，数据操纵，数据完

12、整性规则。 （1）数据结构：数据库中全部数据及其相互连系都被组织成“关系”（二维表格）的形式。关系模型基本的数据结构是关系。 （2）数据操纵：关系模型提供一组完备的高级关系运算，以支持对数据库的各种操作。关系运算分成关系代数、关系演算和关系逻辑等三类。 （3）数据完整性规则：数据库中数据必须满足实体完整性，参照完整性和用户定义的完整性等三类完整性规则。,26,2.1.5 关系模型的优点,与其它数据模型相比，关系模型突出的优点如下： （1）关系模型提供单一的数据结构形式，具有高度的简明性和精确性。 （2）关系模型的逻辑结构和相应的操作完全独立于数据存储方式，具有高度的数据独立性。 （3）关系模型

13、使数据库的研究建立在比较坚实的数学基础上。 （4）关系数据库语言与一阶谓词逻辑的固有内在连系，为以关系数据库为基础的推理系统和知识库系统的研究提供了方便。,27,2.1.6 关系查询语言和关系运算,关系数据库的数据操纵语言（DML）的语句分成查询语句和更新语句两大类。查询语句用于描述用户的各种检索要求；更新语句用于描述用户进行插入、删除、修改等操作。关于查询的理论称为“关系运算理论”。 关系查询语言根据其理论基础的不同分成三类： （1）关系代数语言。 （2）关系演算语言。 （3）关系逻辑语言。,28,2.2 关系代数,2.2.1 关系代数的五个基本操作 2.2.2 关系代数的四个组合操作 2.

14、2.3 关系代数运算的应用实例 2.2.4 关系代数的七个扩充操作,返回,29,2.2.1 关系代数的五个基本操作 (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的元数相同。,30,2.2.1 关系代数的五个基本操作 (2),笛卡尔积（Cartesian Product） 形式定义如

15、下： RSt|ttrRtsS 此处tr、ts中r，s为上标。若R有m个元组，S有n个元组，则RS有mn个元组。,31,2.2.1 关系代数的五个基本操作 (3),投影（Projection）（对关系进行垂直分割） 形式定义如下： i1，im（R） t|tti1，timt1，tkR 例如，3，1（R）表示新关系中第1列为R的第3列，新关系的第2列为R的第1列。如果R的每列标上属性名，那么操作符的下标处也可以用属性名表示。例如，关系R（A，B，C）， 那么C，A（R）与3，1（R）是等价的。,32,2.2.1 关系代数的五个基本操作 (4),选择（Selection）（据条件对关系做水平分割） 形

16、式定义如下： F（R） t | tR F（t）= true 例如，23（R）表示从R中挑选第2个分量值大于3的元组所构成的关系。书写时，为了与属性序号区别起见，常量用引号括起来，而属性序号或属性名不要用引号括起来。,33,2.2.1关系代数的五个基本操作 (例),例2.2 有两个关系R和S：,34,2.2.1关系代数的五个基本操作 (例),（a） （b） （c） （d） （e） RS RS RS C，A（R） B4（R）,35,2.2.2 关系代数的四个组合操作 (1),交（intersection） 关系R和S的交是由属于R又属于S的元组构成的集合，记为RS，这里要求R和S定义在相同的关系模

17、式上。形式定义如下： RSttR tS，R和S的元数相同。 由于RS = R-（R-S），或RS = S-（S-R），因此交操作不是一个独立的操作。 在表2.3中，RS的结果是只有一个元组 （4，5，6）。,36,2.2.2 关系代数的四个组合操作 (2),连接（join）（连接 ） R Stt=trRtsStritsj 定义等价于下式： R Si(r+j)(RS) 该式表示连接是在关系R和S的笛卡儿积中挑选第i个分量和第（r+j）个分量满足操作的元组。,37,2.2.2 关系代数的四个组合操作 (3),38,2.2.2 关系代数的四个组合操作 (4),自然连接（natural join） 关

18、系R和S的自然连接操作计算过程如下： R S 去掉S中的公共属性(公共属性上值相等(RS),（a）关系R （b）关系S （c）R S,R SA,R.B,R.C,D (R.B=S.BR.C=S.C(RS),39,2.2.2 关系代数的四个组合操作 (5),除法（division） 设关系R和S的元数分别为r和s（设rs0），那么RS是一个（r-s）元的元组的集合。（RS）是满足下列条件的最大关系：其中每个元组t与S中每个元组u组成的新元组必在关系R中。 RS1，2，r-s(R) 1，2，r-s(1，2，r-s(R)S)-R),40,表2.7 除法操作的例子,41,2.2.3 关系代数运算的应用实

19、例,在关系代数运算中，把由五个基本操作经过有限次复合的式子称为关系代数表达式。这种表达式的运算结果仍是一个关系。我们可以用关系代数表达式表示各种数据查询操作。 例2.6 设教学数据库中有四个关系： 教师关系 T（T#，TNAME，TITLE） 课程关系 C（C#，CNAME，T#） 学生关系 S（S#，SNAME，AGE，SEX） 选课关系 SC（S#，C#，SCORE）,42,S（S#，SNAME，AGE，SEX） SC（S#，C#，SCORE）,检索学习课程号为C2课程的学生学号与成绩。 S#，SCORE（C#=C2（SC） 表达式中也可以不写属性名，而写上属性的序号： 1，3（2=C2（

20、SC） 检索学习课程号为C2的学生学号与姓名。 S#，SNAME（C#=C2（S SC） 由于这个查询涉及到两个关系S与SC，因此先要对这两个关系进行自然连接操作，然后再执行选择和投影操作。,43,T(T#,TNAME,TITLE) S(S#,SNAME,AGE,SEX) C(C#,CNAME,T#) SC(S#,C#,SCORE),检索至少选修LIU老师所授课程中一门课程的学生学号与姓名。 S#，SNAME（TNAME=LIU（S SC C T） 检索选修课程号为C2或C4的学生学号。 S#（C#=C2C#=C4（SC） 检索至少选修课程号为C2和C4的学生学号。 1（1=42=C25=C4

21、（SCSC） 这里（SCSC）表示关系SC自身相乘的笛卡尔积操作。,44,S（S#，SNAME，AGE，SEX） SC（S#，C#，SCORE）, 检索不学C2课的学生姓名与年龄。 SNAME，AGE(S)SNAME，AGE(C#=C2(S SC) 这里要用到集合差操作。先求出全体学生的 姓名和年龄，再求出学了C2课的学生的姓名 和年龄，最后执行两个集合的差操作。 SNAME，AGE(C#C2(S SC),45,S（S#，SNAME，AGE，SEX） SC（S#，C#，SCORE） C（C#，CNAME，TEACHER）, 检索学习全部课程的学生姓名。 编写这个查询语句的关系代数表达式过程如下

22、： 学生选课情况可用操作S#，C#(SC)表示； 全部课程可用操作 C#(C) 表示； 学了全部课程的学生学号可用除法操作表示，操作结果是学号S#集： S#，C#(SC)C#(C) 从S#求学生姓名SNAME，可以用自然联接和投影操作组合而成： SNAME(S (S#，C#(SC)C#(C),46,SC（S#，C#，SCORE）, 检索所学课程包含学生S3所学课程的学生学号。 学生选课情况可用操作S#，C#(SC)表示； 学生S3所学课程可用操作C#(S#=S3(SC) 表示； 所学课程包含学生S3所学课程的学生学号，可以用除法操作求得： S#，C#(SC)C#(S#=S3(SC),47,2.

23、2.3 关系代数运算的应用实例,查询语句的关系代数表达式的一般形式是： （RS） 或者 （R S） 但是当查询涉及到否定或全部值时，上述形式就不能表达了，就要用到差操作或除法操作，在例2.6中的、说明了这点。,48,2.2.4 七个扩充操作（1）,改名 广义投影 赋值 外连接（outer join） 外部并（outer union） 半连接（semijoin） 聚集操作,49,2.2.4 七个扩充操作（2）,1改名：可改变关系的命名和属性的命名。 例2.7 设关系R（A，B）和S（B，C，D），则RS的属性应写成A、R.B、S.B、C、D。使用改名操作后，RS可写成RS(X，C，D)（S），则

24、其属性为A、B、X、C、D，更为清晰。 设关系R（A，B）和S（C，D），则R和S在B、C上自然连接要写成A，B，D（R S） 或A，B，D（B=C（RS）。 使用改名操作后，可写成R S(B，D)（S）形式。,B=C,50,2.2.4 七个扩充操作（3）,2广义投影：允许在投影列表中使用算术函数来对投影进行扩展， 其形式是F1, F2,Fn（R）， 这里R是任意的关系模式，F1、 F2、Fn是涉及R模式中常量和属性的算术表达式。 例2.8 在选课关系SC（S#，C#，SCORE）中，课程号为C4的成绩应增加5%，则可用下式表示： S#，C#，SCORE*1.05（C#=C4（SC）,51,2

25、.2.4 七个扩充操作（4）,3赋值：通过给临时变量赋值，可以把关系代数表达式分开书写，以便把复杂的表达式化整为零，成为简单的表达式。 赋值运算符是“”，类似于计算机语言中的赋值运算符。 例2.9 关系R和S的除法操作，可用下面的一串操作表示出来： TEMP1 1，2，r-s（R） TEMP2 （TEMP1S）R TEMP3 1，2，r-s（TEMP2） RS TEMP1TEMP3,52,2.2.4 七个扩充操作（5）,4外连接（Outer Join） 如果R和S做自然连接时，把原该舍弃的元组也保留在新关系中，同时在这些元组新增加的属性上填上空值（null），这种操作称为“外连接”操作，用符号

26、R S表示。 如果R和S做自然连接时，只把R中原该舍弃的元组放到新关系中，那么这种操作称为“左外连接”操作，用符号R S表示。 如果R和S做自然连接时，只把S中原该舍弃的元组放到新关系中，那么这种操作称为“右外连接”操作，用符号R S表示。,53,2.2.4 七个扩充操作（6）,54,2.2.4 七个扩充操作（7）,5外部并（Outer Union） 前面定义两个关系的并操作时，要求R和S具有相同的关系模式。如果R和S的关系模式不同，构成的新关系的属性由R和S的所有属性组成（公共属性只取一次），新关系的元组由属于R或属于S的元组构成，同时元组在新增加的属性上填上空值，那么这种操作称为“外部并”

27、操作。,55,2.2.4 七个扩充操作（8）,(a)关系R (b)关系S (c) R和S的外部并,56,2.2.4 七个扩充操作（9）,6 半连接（semijoin） R S R（R S） 或 R S R RS（S）。 显然，半连接的交换律是不成立的， 即 R S S R。 半连接操作主要用于分布式数据库中。,57,2.2.4 七个扩充操作（10）,R S R（R S）,58,2.2.4 七个扩充操作（11）,7聚集操作：聚集操作是指输入一个值的集合，然后根据该值集合得到一个单一的值作为结果。 聚集函数有max、min、avg、sum和count等。 例2.14 在S（S#，SNAME，AGE

28、，SEX）中， 求男同学的平均年龄，可以用式子 avgage（sex=M（S） 表示，求年龄为18岁的人数可用式子 countS#（age=18（S） 表示。,59,2.3 关系演算,把数理逻辑的谓词演算引入到关系运算中，就可得到以关系演算为基础的运算。关系演算又可分为元组关系演算和域关系演算，前者以元组为变量，后者以属性（域）为变量。 2.3.1 元组关系演算 2.3.2 域关系演算 2.3.3 关系运算的安全约束和等价性,60,2.3.1 元组关系演算 (1),在元组关系演算（Tuple Relational Calculus）中，元组关系演算表达式简称为元组表达式，其一般形式为 t |

29、P（t） 其中，t是元组变量，表示一个元数固定的元组；P是公式，在数理逻辑中也称为谓词，也就是计算机语言中的条件表达式。 t | P（t）表示满足公式P的所有元组t的集合。,61,2.3.1 元组关系演算 (2),在元组表达式中，公式由原子公式组成。 定义2.4 原子公式（Atoms）有下列三种形式： R（s） siuj sia或auj。 在定义关系演算操作时，要用到“自由”（Free）和“约束”（Bound）变量概念。在一个公式中，如果元组变量未用存在量词或全称量词符号定义，那么称为自由元组变量，否则称为约束元组变量。,62,2.3.1 元组关系演算 (3),定义2.5 公式（Formula

30、s）的递归定义如下： 每个原子是一个公式。其中的元组变量是自由变量。 如果P1和P2是公式，那么P1、P1P2、P1P2和P1P2也都是公式。 如果P1是公式，那么（s）（P1）和（s）（P1）也都是公式。 公式中各种运算符的优先级从高到低依次为：，和，和，。在公式外还可以加括号，以改变上述优先顺序。 公式只能由上述四种形式构成，除此之外构成的都不是公式。,63,2.3.1 元组关系演算 (4),例2.15 图2.16的（a）、（b）是关系R和S，（c）（g）分别是下面五个元组表达式的值：,图2.20 元组关系演算的例子,R1=t|S(t)t12 R2=t|R(t)S(t) R3=t|(u)(

31、S(t)R(u)t3u1),R5=t|(u)(v)(R(u)S(v) u1v2t1=u2 t2=v3t3=u1),64,2.3.1 元组关系演算 (5),在元组关系演算的公式中，有下列三个等价的转换规则： P1P2 等价于 (P1P2)； P1P2 等价于 (P1P2)。 (s)(P1(s) 等价于 (s)(P1(s)； (s)(P1(s) 等价于 (s)(P1(s)。 P1P2 等价于 P1P2。,65,2.3.1 元组关系演算 (6),关系代数表达式到元组表达式的转换 例2.16 RS可用 t | R（t）S（t）表示； R-S可用 t | R（t）S（t） 表示； RS可用 t |（u）

32、（v）（R（u）S(V) t1=u1 t2=u2t3=u3t4=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）。,66,例2.17 设关系R和S都是二元关系， 1,4（2=3（RS）, RS： t|(u)(v)(R(u)S(v)t1=u1t2=u2 t3=v1t4=v2) 2=3（RS）: 在上述表达式的公式中加上“t2=t3”即可。 1,4（2=3（RS）: w|(t)(u)(v)(R(u)S(v

33、)t1=u1t2=u2 t3=v1t4=v2t2=t3 w1=t1w2=t4) 再对上式化简，去掉元组变量t，可得下式： w|(u)(v)(R(u)S(v) u2=v1w1=u1w2=v2),67,例2.18 对于例2.6中查询语句的关系代数表达式形式也可以用元组表达式形式表示：, 检索学习课程号为C2的学生学号与成绩。 S#，GRADE（C#=C2（SC） t|(u)(SC(u)u2=C2tl=u1 t2=u3) 检索学习课程号为C2的学生学号与姓名。 S#，SNAME（C#=C2（S SC） t|(u)(v)(S(u)SC(v)v2=C2 ul=v1tl=u1t2=u2),68,例2.18

34、 对于例2.6中查询语句的关系代数表达式形式也可以用元组表达式形式表示：, 检索至少选修LIU老师所授课程中一门课程的学生学号与姓名。 S#，SNAME（CNAME=MATHS（S SC C T） t|(u)(v)(w)(x)（S(u)SC(v)C(w)T(x) ul=v1v2=w1w3=x1 x2=LIUtl=u1t2=u2） 检索选修课程号为C2或C4的学生学号。 S#（C#=C2C#=C4（SC） t|(u)(SC(u)(u2=C2u2=C4) tl=u1),69,例2.18 对于例2.6中查询语句的关系代数表达式形式也可以用元组表达式形式表示：, 检索至少选修课程号为C2和C4的学生学

35、号。 1（1=42=C25=C4（SCSC） t|(u)(v)(SC(u)SC(v)u2=C2 v2=C4ul=v1tl=u1) 检索不学C2课的学生姓名与年龄。 SNAME，AGE（S）SNAME，AGE（C#=C2（S SC） t|(u)(v)(S(u)SC(v) (ul=v1v2C2) t1=u2t2=u3),70,例2.18 对于例2.6中查询语句的关系代数表达式形式也可以用元组表达式形式表示：, 检索学习全部课程的学生姓名。 SNAME（S （S#，C#（SC）C#（C） t|(u)(v)(w)(S(u)C(v)SC(w) ul=w1v1=w2t1=u2) 检索所学课程包含学号S3所

36、学课程的学生。 S#，C#（SC）C#（S#=S3（SC） t|(u)(SC(u)(v)(SC(v) (v1=S3 (w)(SC(w)w1=u1w2=v2) tl=u1),71,2.3.2 域关系演算 (1),原子公式有两种形式： R（x1xk）； xy。 公式中也可使用、和等逻辑运算符,(x)和（x），但变量x是域变量，不是元组变量。 自由域变量、约束域变量等概念和元组演算中一样。 域演算表达式是形为 t1tkP（t1，tk） 的表达式，其中P（t1，tk）是关于自由域变量t1，tk 的公式。,72,2.3.2 域关系演算 (2),例2.19 图2.17的（a）、（b）、（c）是三个关系R、

37、S、W，（d）、（e）、（f）分别表示下面三个域表达式的值。,(a)关系R (b)关系S (c)关系W (d)R1 (e)R2 (f)R3 图2.17 域关系演算的例子,R1=xyz|R(xyz)x3 R2=xyz|R(xyz)(S(xyz)y=4) R3=xyz|(u)(v)(R(zxu)w(yv)uv),73,2.3.2 域关系演算 (3),元组表达式到域表达式的转换 我们可以很容易地把元组表达式转换成域表达式，转换规则如下： 对于k元的元组变量t，可引入k个域变量t1tk，在公式中t用t1tk替换，元组分量ti用ti替换。 对于每个量词（u）或（u），若u是m元的元组变量，则引入m个新的

38、域变量u1um。 在量词的辖域内，u用u1um替换，ui用ui替换，（u）用（u1）（um）替换，（u）用（u1）（um）替换。,74,例2.20 设关系R和S都是二元关系， 1,4（2=3（RS）,例2.17 转换成的元组表达式是： w|(u)(v)(R(u)S(v)u2=v1 w1=u1w2=v2) 再转换成域表达式： w1w2|(u1)(u2)(v1)(v2)(R(u1u2)S(v1v2) u2=v1 w1=u1 w2=v2) 再进一步简化，可消去域变量u1、v1、v2，得到下式： w1w2|(u2)(R(w1u2)S(u2w2),75,例2.21 对于例2.6、例2.18的查询，可转换

39、成下列域表达式：, 检索学习课程号为C2的学生学号与成绩。 t1t2|(u1)(u2)(u3)(SC(u1u2u3)u2=C2 t1=u1t2=u3) 可化简为：t1t2|SC(t1C2t2) 检索学习课程号为C2的学生学号与姓名。 t1t2|(u1)(u2)(u3)(u4)(v1)(v2)(v3) (S(u1u2u3u4)SC(v1v2v3)v2=C2 u1=v1t1=u1t2=u2) 可化简为： t1t2|(u3)(u4)(v3) (S(t1t2u3u4)SC(t1C2v3),76,2.3.3关系运算的安全约束和等价性,定义2.6 在数据库技术中，不产生无限关系和无穷验证的运算称为安全运算

40、，相应的表达式称为安全表达式，所采取的措施称为安全约束。 并、差、笛卡儿积、投影和选择是关系代数最基本的操作，并构成了关系代数运算的最小完备集。已经证明，在这个基础上，关系代数、安全的元组关系演算、安全的域关系演算在关系的表达和操作能力上是完全等价的。,77,关系运算的安全性,元组表达式t|R（t），这是一个无限关系。 验证公式(u)(P1(u)为假时，必须对所有可能的元组u进行验证，当所有的u都使P1(u)为假时，才能断定公式(u)(P1(u)为假。 验证公式(u)(P1(u)也是这样，当所有可能的u使P1(u)为真时，才能断定公式(u)(P1(u)为真。这在实际上是行不通的。 我们必须采取

41、措施，防止无限关系和无穷验证的出现。,78,关系运算的安全性（续）,对于元组表达式t|P（t），将公式P(t)的“域”（Domain）定义为出现在公式P(t)中的常量和关系的所有属性值组成的集合，记为DOM(P(t)。 由于所有关系都是有限的，因此DOM(P)也是有限的。 例如P(t)是t1=aR（t），R是二元关系，那么DOM(P)=a1（R）2（R）。,79,关系运算的安全性（续）,安全的元组表达式t|P(t)应满足下列三个条件： 表达式的元组t中出现的所有值均来自DOM(P)。 对于P(t)中每个形如(u)(P1(u)的子公式，如果元组u使P1(u)为真，那么u的每个分量必是DOM(P1

42、)的元素。换言之，如果u有某个分量不属于DOM(P1)，那么P1(u)必为假。 对于P(t)中每个形如(u)(P1(u)的子公式，如果元组u使P1(u)为假，那么u的每个分量必是DOM(P1)的元素。换言之，如果u有某个分量不属于DOM(P1),那么P1(u)必为真。,80,关系运算的等价性,ISBL（Information System Base Language）语言与关系代数非常接近。 QUEL语言（Query Language）是一种基于元组演算的数据语言。 QBE（Query By Example,按例查询）是一种特殊的屏幕编辑语言。是一种域演算语言，现在，QBE的思想已渗入到许多D

43、BMS中。 SQL（Structured Query Language）是介乎于关系代数和元组演算之间的一种关系查询语言，现已成为关系数据库的标准语言，我们将在第3章详细介绍。,81,2.4 关系代数表达式的优化,2.4.1 关系代数表达式的优化问题 2.4.2 关系代数表达式的等价变换规则 2.4.3 关系代数表达式的优化算法,82,2.4.1 关系代数表达式的优化(1),在关系代数表达式中需要指出若干关系的操作步骤。那么，系统应该以什么样的操作顺序，才能做到既省时间，又省空间，而且效率也比较高呢？这个问题称为查询优化问题。 在关系代数运算中， 笛卡儿积和连接运算 是最费时间的。,83,2.

44、4.1 关系代数表达式的优化(2),例2.22 设关系R和S都是二元关系，属性名分别为A，B和C，D。 E1 = A（B=CD=99（RS） E2 = A（B=C（RD=99（S） E3 = A（R D=99（S） 这三个关系代数表达式是等价的，但执行的效率大不一样。显然，求El，E2，E3的大部分时间是花在连接操作上的。,返回,84,2.4.2 等价变换规则 (1),连接和笛卡儿积的交换律 连接和笛卡儿积的结合律 投影的级联 选择的级联 选择和投影操作的交换 选择对笛卡儿积的分配律 选择对并的分配律,85,2.4.2 等价变换规则 (2),选择对集合差的分配律 选择对自然连接的分配律 投影对

45、笛卡儿积的分配律 投影对并的分配律 选择与连接操作的结合 并和交的交换律 并和交的结合律,返回,86,2.4.3 启发式优化算法 (1),在关系代数表达式中，最花费时间和空间的运算是笛卡儿积和连接操作，为此，引出三条启发式规则，用于对表达式进行转换，以减少中间关系的大小。 尽可能早地执行选择操作； 尽可能早地执行投影操作； 避免直接做笛卡儿积，把笛卡儿积操作 之前和之后的一连串选择和投影合并起 来一起做。,87,2.4.3 启发式优化算法 (2),算法2.1 关系代数表达式的启发式优化算法。 输入：一个关系代数表达式的语法树 输出：计算表达式的一个优化序列 方法： 把每个形为F1 Fn（E）的子表达式转 换成选择级联形式：F1（Fn（E） 在语法树中，尽可能把每个选择下推到树的叶端。 对每个投影操作，尽可能往下推，移向树的叶端。 把选择和投影合并在一起做。 将上述步骤得到的语法树的内结点分组。以每个二元运算（、）结点为中心分组。 生成一个序列，每一组结点的计算是序列中的一步。,88,2.4.3 启发式优化算法 (3),例2.23 查询语句：检索学习课程名为OS的女学生学号和姓名。 该查询语句的关系代数表达式如