(1)∏Sname(S∞(∏S#,C#(SC)÷∏C#(σteacher=“程军”(C)))) 说明：根据条件由课程关系得到课程号→由课程号在SC关系中得到学生号→ 由学生号在学生表中查找学生姓名。 1、先在C关系中进行选择运算，选择关系式选出给定条件的元组。这里 选出 2 关系，这里从上面得到的关系当中投影出C#的属性。得到结果如下： 3、对SC C#这两列： 4、将步骤3得到的关系B进行除运算。除运算的 定义在课本上，这里我想简单说明此处是怎么得到的： 关系A和关系B具有相同的属性名，满足除运算的条件→此处除运算的结果时关系A中S#的分量值，也就是说结果肯定是一个在1,2,5当中取值的集合→ 首先我们计算1的象集为{k1}，2的象集为{k1,k5}，5的象集为{k1,k5,k8} → B关系在C#上的投影为{k5,k8}，因此这里只有5的象集{k1,k5,k8}B关系在C#上的投影为{k5,k8}。因此A关系除以B关系的结果为： 5、关系D与S 行比较的分量必须有相同的属性组，并且结果中把重复的属性组去掉。连接结果为： 6
(2)∏C#(C)-∏C#(σSname=“李强”(S)∞SC) 说明：首先在S关系中选出姓名为李强的元组→与SC关系进行连接运算在得到的新关系上进行投影运算得到李强学习的课程号→在课程关系中进行投影运算得到所有课程的课程号–李强学习的课程号得到的就是李强不学习的课程号，最终结果为：{k5，k8}。 (3)∏C#,Cname(C∞(∏S#,C#(SC)÷∏S#(S)) 说明：解题思路：这道题目要检索学生都选修的课程号和课程名，关键就在那个“都”字上，我们知道，除运算所满足的条件：元组X上的分量值x的象集Yx包含S在Y上的投影的集合。抽象不要紧，实例化之后就能看懂了。 1、首先在SC关系上选出S#和C#这两列属性得到一个新的关系我们称为 A，从S关系当中选出S#这列属性得到的关系我们称为B，A和B做除运算的流程： 首先计算k1的象集{1,2,5}{2,5}，k8的象集{5}，关系B在S#上的投影{1,2,5}。由此可看出只有k1的象集{1,2,5}包含B在S#上的投影{1,2,5}。因此除运算的结果为{k1}。关系表示为： 2、将除运算的结果关系D与题目当中的关系C进行连接运算，并选择其 中的C#和Cname
关系代数表达式： 由关系代数运算经有限次复合而成的式子称为关系代数表达式。 这种表达式的运算结果仍然是一个关系。可以用关系代数表达式表示对数据库的查询和更新操作。 关系代数(演算)要求掌握各种语句的应用 1：设教学数据库中有3个关系： 学生关系S(SNO,SNAME,AGE,SEX) 学习关系SC(SNO,CNO,GRADE) 课程关系C(CNO,CNAME,TEACHER) 下面用关系代数表达式表达每个查询语句。 (1) 检索学习课程号为C2的学生学号与成绩。 πSNO，GRADE(σCNO='C2'(SC)) (2) 检索学习课程号为C2的学生学号与姓名 πSNO，SNAME(σCNO='C2'(S SC)) 由于这个查询涉及到两个关系S和SC，因此先对这两个关系进行自然连接，同一位学生的有关的信息，然后再执行选择投影操作。
此查询亦可等价地写成： πSNO，SNAME（S）（πSNO(σCNO='C2'(SC))） 这个表达式中自然连接的右分量为"学了C2课的学生学号的集合"。这个表达式比前一个表达式优化，执行起来要省时间，省空间。 （3）检索选修课程名为MATHS的学生学号与姓名。 πSNO，SANME(σCNAME='MATHS'(S SC C)) （4）检索选修课程号为C2或C4的学生学号。 πSNO(σCNO='C2'∨CNO='C4'(SC)) （5）检索选修课程号为C2和C4的学生学号。 π1(σ1=4∧2='C2'∧5='C4'（SC×SC）) 这里（SC×SC）表示关系SC自身相乘的乘积操作，其中数字1，2，4，5都为它的结果关系中的属性序号。 比较这一题与上一题的差别。 （6）检索不学C2课的学生姓名与年龄。 πSNAME，AGE（S）－πSNAME，AGE(σCNO='C2'（S SC）)
2.5 谓词逻辑推理理论 谓词演算推证的基本思路是将量词消去， 然后用类似命题演算推证法证明。
2.5.1 谓词演算推证 谓词演算推证也是由三个要素组成：推理根据、推理规则和证明方法。 推理根据： 一方面命题演算推证中命题定律和推理定律的代换实例可以作为谓词演算推证的推理依据； 一方面谓词演算的基本逻辑等价式和逻辑蕴涵式： 量词否定逻辑等价式 量词辖域的收缩与扩张逻辑等价式 量词分配逻辑等价式 具有两个量词的逻辑等价式 量词与联结词的逻辑蕴涵式 具有两个量词的逻辑蕴涵式
2.5.1 谓词演算推证 证明方法： 直接证法 间接证明方法 反证法 附加前提证法
2.5.1 谓词演算推证 推理规则： P规则 T规则 CP规则 消去和添加量词的规则
2.5.1 谓词演算推证 1）US 规则（全称指定规则） 这里P 是谓词，而c 是个体域中某个任意的个体。 例如，设个体域为全体偶数的集合，P(x)表示“x 是整数”，则?xP(x)表示“所有的偶数都是整数”，那么根据全称指定规则有P(6)，即“6是整数”。 全称指定规则在使用时要求x 是P(x)中自由出现的个体变元。该规则使用时还可以有以下形式：() () c Ρx x Ρ∴?() () y Ρx Ρ∴?x 这里y 是任意的不在P(x)中约束出现的个体变元。注意：
2.5.1 谓词演算推证 2）UG 规则（全称推广规则） 设E 是指定的个体域，若对于E 中的任意个体a ，都有P(a)成立，才能应用该全称推广规则。例如，设个体域是全体人类，P(x)表示“x 是要死的”。显然，对于任意一个人a ，P(a)都成立，即任何人都是要死的。则应用全称推广规则有?xP(x)成立。 全称推广规则在使用时要求y 不在P(x)中约束出现。注意：) () (y yP x P ?∴
# 关系模型课后习题 名词解释 (1)关系模型：用二维表格结构表示实体集，外键表示实体间联系的数据模型称为关系模型。 (2)关系模式：关系模式实际上就是记录类型。它的定义包括：模式名，属性名，值域名以及模式的主键。关系模式不涉及到物理存储方面的描述，仅仅是对数据特性的描述。 (3)关系实例：元组的集合称为关系和实例，一个关系即一张二维表格。 (4)属性：实体的一个特征。在关系模型中，字段称为属性。 (5)域：在关系中，每一个属性都有一个取值范围，称为属性的值域，简称域。 (6)元组：在关系中，记录称为元组。元组对应表中的一行；表示一个实体。 (7)超键：在关系中能唯一标识元组的属性集称为关系模式的超键。 (8)候选键：不含有多余属性的超键称为候选键。 (9)主键：用户选作元组标识的一个候选键为主键。（单独出现，要先解释“候选键”） (10)外键：某个关系的主键相应的属性在另一关系中出现，此时该主键在就是另一关系的外键，如有两个关系S和SC,其中S#是关系S的主键，相应的属性S#在关系SC中也出现，此时S#就是关系SC的外键。 (11)实体完整性规则：这条规则要求关系中元组在组成主键的属性上不能有空值。如果出现空值，那么主键值就起不了唯一标识元组的作用。 (12)参照完整性规则：这条规则要求“不引用不存在的实体”。其形式定义如下：如果属性集K是关系模式R1的主键，K也是关系模式R2的外键，那么R2的关系中， K的取值只允许有两种可能，或者为空值，或者等于R1关系中某个主键值。这条规则在使用时有三点应注意： 1)外键和相应的主键可以不同名，只要定义在相同值域上即可。 2)R1和R2也可以是同一个关系模式，表示了属性之间的联系。 3)外键值是否允许空应视具体问题而定。 (13)过程性语言：在编程时必须给出获得结果的操作步骤，即“干什么”和“怎么干”。如Pascal和C语言等。 (14)非过程性语言：编程时只须指出需要什么信息，不必给出具体的操作步骤。各种关系查询语言均属于非过程性语言。 (15)无限关系：当一个关系中存在无穷多个元组时，此关系为无限关系。如元组表达式{t|┐R(t)}表示所有不在关系R中的元组的集合，这是一个无限关系。 (16)无穷验证：在验证公式时需对无穷多个元组进行验证就是无穷验证。如验证公式(u)(P(u))的真假时需对所有的元组u进行验证，这是一个无穷验证的问题。 为什么关系中的元组没有先后顺序 因为关系是一个元组的集合，而元组在集合中的顺序无关紧要。因此不考虑元组间的顺序，即没有行序。 为什么关系中不允许有重复元组 因为关系是一个元组的集合，而集合中的元素不允许重复出现，因此在关系模型中对关系作了限制，关系中的元组不能重复，可以用键来标识唯一的元组。 关系与普通的表格、文件有什么区别 关系是一种规范化了的二维表格，在关系模型中，对关系作了下列规范性限制： 1)关系中每一个属性值都是不可分解的。 2)关系中不允许出现相同的元组(没有重复元组)。 3)由于关系是一个集合，因此不考虑元组间的顺序，即没有行序。 4)元组中，属性在理论上也是无序的，但在使用时按习惯考虑列的顺序。 笛卡尔积、等值联接、自然联接三者之间有什么区别 笛卡尔积对两个关系R和S进行乘操作，产生的关系中元组个数为两个关系中元组个数之积。 等值联接则是在笛卡尔积的结果上再进行选择操作，从关系R和S的笛卡儿积中选择对应属性值相等的元组； 自然连接则是在等值联接(以所有公共属性值相等为条件)的基础上再行投影操作，并去掉重复的公共属性列。当两个关系没有公共属性时，自然连接就转化我笛卡尔积。 设有关系R和S（如下：） 计算： 设有关系R和S（如下：） 计算： 如果R是二元关系，那么下列元组表达式的结果是什么 {t|(u)(R(t)∧R(u)∧(t[1]≠u[1]∨t[2]≠u[2]))}
第二章关系代数 教学目的： 本章实际上研究的是关系的运算。 学习目的： 关系运算是设计关系数据库操作语言的基础，因为其中的每一个询问往往表示成一个关系运算表达式，在我们的课程中，数据及联系都是用关系表示的，所以实现数据间的联系也可以用关系运算来完成。 通过本章学习，应重点掌握： (1)关系数据库的基本概念； (2)如何用关系代数表达式来表达实际查询问题； (3)如何用元组演算表达式来表达实际查询问题； (4)如何用域演算表达式来表达实际查询问题； (5)如何将关系代数表达式转换为元组演算表达式或转换为域演算表达式。 了解和掌握关系数据结构中涉及到的域、笛卡儿积、关系模式等有关内容的含义； 掌握关系的实体完整性和参照完整性的定义； 掌握关系代数中的并、交、差、笛卡儿积运算，以及选择、投影和连接运算。 教学重点： 关系的实体完整性和参照完整性的定义； 关系代数中的并、交、差、笛卡儿积运算，以及选择、投影和连接运算。 教学难点：关系代数中的并、交、差、笛卡儿积运算，以及选择、投影和连接运算。 教学方法：实例法 教学内容：如下： 关系模型 关系模型是一种简单的二维表格结构，每个二维表称做一个关系，一个二维表的表头，即所有列的标题称为一个元组，每一列数据称为一个属性，列标题称估属性名。同一个关系中不允许出现重复元组和相同属性名的属性。 1．关系模型组成 关系模型由关系数据结构、关系操作集合和关系完整性约束三部分组成。关系操作分为两大部分如图所示。
2．关系操作的特点 关系操作的特点是操作对象和操作结果都是集合。而非关系数据模型的数据操作方式则为一次一个记录的方式。 关系数据语言分为三类： (1)关系代数语言：如ISBL ； (2)关系演算语言：分为元组关系演算语言(如Alpha ，Quel)、域关系演算语言(如QBE)； (3)具有关系代数和关系演算双重特点的语言：如SQL 。 3．关系数据结构及其形式化定义 （1）域 定义 域是一组具有相同数据类型的值的集合。 （2）笛卡尔积 定义 设D 1，D 2，D 3，…，D n ，为任意集合，定义D l ，D 2，D 3，…，D n 的笛卡尔积为 D 1×D 2×D 3×…×D n ＝{(d1，d2，d3，…dn)[di ∈Di ，i ＝1，2，3…，n] 其中每一个元素(dl ，d2，d3，…，dn ，)叫做一个n 元组(n 一tuple)或简称为元组(Tuple)，每一个值di 叫做一个分量(Component)，若Di(i ＝l ，2，…n)为有限集，其基数(Cardinal number)为mi(i=l ，2，3，…，n)， 则D 1×D 2×D 3×…×D n 的基数M 为 M ＝ ∏=n i 1 mi
习题四 1. 试述关系模型的三个组成部分。 .关系是由（R，U，D,dom,F ）组成，R 为关系名，关系结构、关系操作、关系完整性约束 U 位组成关系的元组属性集合，D 为属性集合U 来自的域，dom 为对象关系的映像集合，F 为属性依赖关系集合。关系操作为关系代数、关系演算、关系映象操作，此语言表达能和功能强大，约束：参照完整性约束，用户自定义约束，实体完整性约束。 2. 试述关系数据语言的特点和分类。 关系操作语言灵活方便、语言表达能力和功能强，其特点：操作一体化，操作方式一次一集合，高度的非过程化的操作，关系操作语言包括：关系代数语言、关系演算语言、基于映像 的语言，关系代数语言是对关系的运算来表达查询的语言，关系演算语言查询元组的应该满足的谓词条件的运算查询语言， 基于映像的语言具有关系代数与关系演算的语言的双重特点 语言查询！
3. 定义并解释下列术语，说明它们之间的联系与区别。 主码、候选码、外码。）1 在一个关系中某个属性（或属性组）能够唯一标识一个元组，则称该属性为候选码，选择其 R 中属性F 不是R 的码，h 为K 关系的主码，如果F 与h 相对应，中一个为主码，在关系 则称 F 为管系R 的外码 笛卡尔积、关系、元组、属性、域。2）给定一组域D1,D2,D3 3）关系、关系模式、关系数据库。 4. 试述关系模型的完整性规则。在参照完整性中，为什么外码属性的值也可以为空？什么 情况下才可以为空？ 5. 试述等值连接与自然连接的区别和联系。 6. 对于学生选课关系，其关系模式为： 学生（学号，姓名，年龄，所在系）； 课程（课程名，课程号，先行课）； 选课（学号，课程号成绩）。 用关系代数完成如下查询。 求学过数据库课程的学生的姓名和学号。1） 求学过数据库和数据结构的学生姓名和学号。2）求没学过数
关系模型课后习题 2.1 名词解释 (1)关系模型：用二维表格结构表示实体集，外键表示实体间联系的数据模型称为关系模型。 (2)关系模式：关系模式实际上就是记录类型。它的定义包括：模式名，属性名，值域名以及模式的主键。关系模式不涉及到物理存储方面的描述，仅仅是对数据特性的描述。 (3)关系实例：元组的集合称为关系和实例，一个关系即一张二维表格。 (4)属性：实体的一个特征。在关系模型中，字段称为属性。 (5)域：在关系中，每一个属性都有一个取值范围，称为属性的值域，简称域。 (6)元组：在关系中，记录称为元组。元组对应表中的一行；表示一个实体。 (7)超键：在关系中能唯一标识元组的属性集称为关系模式的超键。 (8)候选键：不含有多余属性的超键称为候选键。 (9)主键：用户选作元组标识的一个候选键为主键。（单独出现，要先解释“候选键”） (10)外键：某个关系的主键相应的属性在另一关系中出现，此时该主键在就是另一关系的外键，如有两个关系S和SC,其中S#是关系S的主键，相应的属性S#在关系SC中也出现，此时S#就是关系SC的外键。 (11)实体完整性规则：这条规则要求关系中元组在组成主键的属性上不能有空值。如果出现空值，那么主键值就起不了唯一标识元组的作用。 (12)参照完整性规则：这条规则要求“不引用不存在的实体”。其形式定义如下：如果属性集K是关系模式R1的主键，K也是关系模式R2的外键，那么R2的关系中， K的取值只允许有两种可能，或者为空值，或者等于R1关系中某个主键值。这条规则在使用时有三点应注意： 1)外键和相应的主键可以不同名，只要定义在相同值域上即可。 2)R1和R2也可以是同一个关系模式，表示了属性之间的联系。 3)外键值是否允许空应视具体问题而定。 (13)过程性语言：在编程时必须给出获得结果的操作步骤，即“干什么”和“怎么干”。如Pascal和C语言等。 (14)非过程性语言：编程时只须指出需要什么信息，不必给出具体的操作步骤。各种关系查询语言均属于非过程性语言。 (15)无限关系：当一个关系中存在无穷多个元组时，此关系为无限关系。如元组表达式{t|┐R(t)}表示所有不在关系R中的元组的集合，这是一个无限关系。 (16)无穷验证：在验证公式时需对无穷多个元组进行验证就是无穷验证。如验证公式(u)(P(u))的 真假时需对所有的元组u进行验证，这是一个无穷验证的问题。 2.2 为什么关系中的元组没有先后顺序? 因为关系是一个元组的集合，而元组在集合中的顺序无关紧要。因此不考虑元组间的顺序，即没有行序。 2.3 为什么关系中不允许有重复元组? 因为关系是一个元组的集合，而集合中的元素不允许重复出现，因此在关系模型中对关系作了限制，关系中的元组不能重复，可以用键来标识唯一的元组。 2.4 关系与普通的表格、文件有什么区别? 关系是一种规范化了的二维表格，在关系模型中，对关系作了下列规范性限制： 1)关系中每一个属性值都是不可分解的。 2)关系中不允许出现相同的元组(没有重复元组)。 3)由于关系是一个集合，因此不考虑元组间的顺序，即没有行序。 4)元组中，属性在理论上也是无序的，但在使用时按习惯考虑列的顺序。 2.5 笛卡尔积、等值联接、自然联接三者之间有什么区别? 笛卡尔积对两个关系R和S进行乘操作，产生的关系中元组个数为两个关系中元组个数之积。 等值联接则是在笛卡尔积的结果上再进行选择操作，从关系R和S的笛卡儿积中选择对应属性值相等的元组； 自然连接则是在等值联接(以所有公共属性值相等为条件)的基础上再行投影操作，并去掉重复的公共属性列。当两个关系没有公共属性时，自然连接就转化我笛卡尔积。 2.6 设有关系R和S（如下：） 计算： 2.7 设有关系R和S（如下：） 计算： 2.8 如果R是二元关系，那么下列元组表达式的结果是什么? {t|(u)(R(t)∧R(u)∧(t[1]≠u[1]∨t[2]≠u[2]))} 这个表达式的意思是：从关系R中选择元组，该元组满足：第1分量值或第2分量值至少有一个不等于其他某元组。由于R是二元关系，只有两个分量，由于没有重复元组，上述条件显然满足。所以，这个表达式结果就是关系R。 2.9 假设R和S分别是三元和二元关系，试把表达式π 1,5(σ 2=4∨3=4 (R×S))转换成等价的：(1)汉语查 询句子；(2)元组表达式；(3)域表达式。 (1)汉语表达式：
数据库系统原理第四章关系运算课后习题答案 4.1 名词解释 (1)关系模型：用二维表格结构表示实体集，外键表示实体间联系的数据模型称为关系模型。 (2)关系模式：关系模式实际上就是记录类型。它的定义包括：模式名，属性名，值域名以及模式的主键。关系模式不涉及到物理存储方面的描述，仅仅是对数据特性的描述。 (3)关系实例：元组的集合称为关系和实例，一个关系即一张二维表格。 (4)属性：实体的一个特征。在关系模型中，字段称为属性。 (5)域：在关系中，每一个属性都有一个取值范围，称为属性的值域，简称域。 (6)元组：在关系中，记录称为元组。元组对应表中的一行；表示一个实体。 (7)超键：在关系中能唯一标识元组的属性集称为关系模式的超键。 (8)候选键：不含有多余属性的超键称为候选键。 (9)主键：用户选作元组标识的一个候选键为主键。（单独出现，要先解释“候选键”） (10)外键：某个关系的主键相应的属性在另一关系中出现，此时该主键在就是另一关系的外键，如有两个关系S和SC,其中S#是关系S的主键，相应的属性S#在关系SC中也出现，此时S#就是关系SC的外键。 (11)实体完整性规则：这条规则要求关系中元组在组成主键的属性上不能有空值。如果出现空值，那么主键值就起不了唯一标识元组的作用。 (12)参照完整性规则：这条规则要求“不引用不存在的实体”。其形式定义如下：如果属性集K是关系模式R1的主键，K也是关系模式R2的外键，那么R2的关系中， K的取值只允许有两种可能，或者为空值，或者等于R1关系中某个主键值。这条规则在使用时有三点应注意： 1)外键和相应的主键可以不同名，只要定义在相同值域上即可。 2)R1和R2也可以是同一个关系模式，表示了属性之间的联系。 3)外键值是否允许空应视具体问题而定。 (13)过程性语言：在编程时必须给出获得结果的操作步骤，即“干什么”和“怎么干”。如Pascal和C语言等。 (14)非过程性语言：编程时只须指出需要什么信息，不必给出具体的操作步骤。各种关系查询语言均属于非过程性语言。 (15)无限关系：当一个关系中存在无穷多个元组时，此关系为无限关系。如元组表达式{t|┐R(t)}表示所有不在关系R中的元组的集合，这是一个无限关系。 (16)无穷验证：在验证公式时需对无穷多个元组进行验证就是无穷验证。如验证公式(u)(P(u))的真假时需对所有的元组u进行验证，这是一个无穷验证的问题。 4.2 为什么关系中的元组没有先后顺序? 因为关系是一个元组的集合，而元组在集合中的顺序无关紧要。因此不考虑元组间的顺序，即没有行序。 4.3 为什么关系中不允许有重复元组?
数据库系统原理关系运算习题答案 1、笛卡尔积、等值联接、自然联接三者之间有什么区别? 笛卡尔积对两个关系R和S进行乘操作，产生的关系中元组个数为两个关系中元组个数之积。 等值联接则是在笛卡尔积的结果上再进行选择操作，从关系R和S的笛卡儿积中选择对应属性值相等的元组； 自然连接则是在等值联接(以所有公共属性值相等为条件)的基础上再行投影操作，并去掉重复的公共属性列。当两个关系没有公共属性时，自然连接就转化我笛卡尔积。 2、设有关系R和S（如下：） 计算：
3、设有关系R和S（如下：） 计算：
4、如果R是二元关系，那么下列元组表达式的结果是什么? {t|(u)(R(t)∧R(u)∧(t[1]≠u[1]∨t[2]≠u[2]))} 这个表达式的意思是：从关系R中选择元组，该元组满足：第1分量值或第2分量值至少有一个不等于其他某元组。由于R是二元关系，只有两个分量，由于没有重复元组，上述条件显然满足。所以，这个表达式结果就是关系R。 5、假设R和S分别是三元和二元关系，试把表达式π 1,5(σ 2=4∨3=4 (R×S))转换成 等价的：(1)汉语查询句子；(2)元组表达式；(3)域表达式。 (1)汉语表达式： 从R×S关系中选择满足下列条件的元组： 第2分量（R中第2分量）与第4分量（S中第1分量）值相等，或第3分量（R 中第3分量）与第4分量（S中第1分量）值相等；并取第1列与第5列组成的新关系。 (2)元组表达式：{t|(u)( v)(R(u)∧S(v)∧(u[2]=v[1]∨u[3]=v[1])∧t[1]=u[1]∧t[2]=v[2])} (3)域表达式:{xv|(y)(z)(u)(R(xyz)∧S(uv)∧(y=u∨z=u))} 6、假设R和S都是二元关系，试把元组表达式{t|R(t)∧( u)(S(u)∧u[1]≠t[2])}转换成等价的： (1)汉语查询句子；(2)域表达式：(3)关系代数表达式。 (1)汉语表达式：选择R关系中元组第2分量值不等于S关系中某元组第1分量值的元组。
2.4 关系运算(二)——关系演算 关系代数是将整个关系看作变元，并以其作为基本运算单位，同时以集合方法为关系运算的理论基础。如果将组成关系的基本成分例如元组或者属性域看作变量，以其作为基本运算单位，同时以数理逻辑中谓词演算为相应关系演算的理论基础，就得到了另外一种形式的关系数据语言——关系演算。 关系演算基于谓词演算。在谓词演算中，如果谓词中的变元是关系中的元组，则得到所谓元组关系演算；如果谓词中的变元是关系中的属性域，则得到所谓域关系演算。这样，关系演算就分为元组关系演算和域关系演算两类。 在 2.4节和2.5节，均以本章 2.3.4节中的关系数据库{S,C,SC}为背景举例。这里S (S#,Sn,Sex,Sa,Sd)；C (C#,Cn,P#,Tn)；SC (S#,C#,G)，其中各个属性的含义见2.3.4节。 2.4.1 元组关系演算 如果在一阶谓词演算表达式中，变量是以元组为演算单位，就称其为元组关系演算(Tuple Relation Calculus)，其中元组变量表示关系中的元组，变量取值范围是整个关系。 1. 关系的元组演算表示 (1) 关系与谓词的对应 为了得到关系操作的元组关系演算表达式，需要考虑关系与谓词的联系。 z由关系R确定的谓词P 在数理逻辑中我们知道，关系可用谓词表示，n元关系可以由n元谓词表示。 设有关系R，它有元组(r1,r2,…,r m)，定义关系R对应如下一个谓词 P (x1,x2, …,x n)。 当t =(r1,r2, …,r m)属于R时，t为P的成真的真值指派，而其他不在R中的任意元组t则是P 的成假指派。即是说，由关系R定义一个谓词P具有如下性质： P(t) = T (当t在R中)； P(t) = F (当t不在R中)。 z由谓词P表示关系R 由于关系代数中R是元组集合，一般而言，集合是可以用满足它的某种特殊性质来刻画与表示。如果谓词P表述了关系R中元组的本质特性，就可以将关系R写为： R={t | P(t)} 这个公式就建立了关系(元组集合)的谓词表示，称之为关系演算表达式。 (2) 元组关系演算表达式 元组关系演算表达式的严格数学描述是由“归纳定义”方式完成的。按照通常的思路，元组演算表达式是由“关系演算公式”组成；“关系演算公式”是由“原子公式”组成。 ①原子公式 下述三类称为元组演算原子公式，简称原子公式： z谓词R(t)是原子公式。 z u(i)θv(j)是原子公式。 z u(i)θa是原子公式。 其中，t =(r1,r2,…,r m)是P的成真指派；u(i)表示元组u的第i个分量，v(j)表示元组v的第j 个分量；a是常量，u(i)θa表示u的第i个分量与常量a有关系θ。
习题四 1. 试述关系模型的三个组成部分。 关系结构、关系操作、关系完整性约束.关系是由（R，U，D,dom,F ）组成，R 为关系名，U 位组成关系的元组属性集合， D 为属性集合U 来自的域，dom 为对象关系的映像集合， F 为属性依赖关系集合。关系操作为关系代数、关系演算、关系映象操作，此语言表达能和功能强大，约束：参照完整性约束，用户自定义约束，实体完整性约束。 2. 试述关系数据语言的特点和分类。 关系操作语言灵活方便、语言表达能力和功能强，其特点：操作一体化，操作方式一次一集 合，高度的非过程化的操作，关系操作语言包括：关系代数语言、关系演算语言、基于映像 的语言，关系代数语言是对关系的运算来表达查询的语言，关系演算语言查询元组的应该满 足的谓词条件的运算查询语言，基于映像的语言具有关系代数与关系演算的语言的双重特点 语言查询！ 3. 定义并解释下列术语，说明它们之间的联系与区别。 1）主码、候选码、外码。 在一个关系中某个属性（或属性组）能够唯一标识一个元组，则称该属性为候选码，选择其 中一个为主码，在关系R 中属性 F 不是R 的码，h 为K 关系的主码，如果 F 与h 相对应，则称 F 为管系R 的外码 2）笛卡尔积、关系、元组、属性、域。 给定一组域D1,D2,D3 3） 关系、关系模式、关系数据库。 4. 试述关系模型的完整性规则。在参照完整性中，为什么外码属性的值也可以为空？什么 情况下才可以为空？ 5. 试述等值连接与自然连接的区别和联系。 6. 对于学生选课关系，其关系模式为： 学生（学号，姓名，年龄，所在系）； 课程（课程名，课程号，先行课）； 选课（学号，课程号成绩）。 用关系代数完成如下查询。 1）求学过数据库课程的学生的姓名和学号。 2）求学过数据库和数据结构的学生姓名和学号。 3）求没学过数据库课程的学生学号。 4）求学过数据库的先行课的学生学号。
2.5 谓词演算的推理理论 1．推理定律 谓词演算中也存在一些基本的等价与蕴含关系，参见表2-2。我们以此作为推理的基础，即推理定律。 表2-2 序号 等价或蕴含关系 含义 E27 E28 ┐?xA(x)??x┐A(x) ┐?xA(x)??x┐A(x) 量词否定等值式 E29 E30?x(A(x)∧B(x))??xA(x)∧?xB(x) ?x(A(x)∨B(x))??xA(x)∨?xB(x) 量词分配等值式（量词分配律） E31 E32 E33 E34 E35 E36 E37 E38 E39 E40 E41 E42 E43?x(A(x)∨B)??xA(x)∨B ?x(A(x)∧B)??xA(x)∧B ?x(A(x)∨B)??xA(x)∨B ?x(A(x)∧B)??xA(x)∧B ?x(B∨A(x))? B∨?xA(x) ?x(B∧A(x))? B∧?xA(x) ?x(B∨A(x))? B∨?xA(x) ?x(B∧A(x))? B∧?xA(x) ?x(A(x)→B(x))??xA(x)→?xB(x) ?x(A(x)→B)??xA(x)→B ?xA(x)→B??x(A(x)→B) A→?xB(x)??x(A→B(x)) A→?xB(x)??x(A→B(x)) 量词作用域的扩张与收缩 I21 I22?xA(x)∨?xB(x)??x(A(x)∨B(x)) ?x(A(x)∧B(x))??xA(x)∧?xB(x) I23 ?xA(x)→?xB(x)??x(A(x)→B(x)) 表2-2中的I、E序号是接着表1-5和1-8排列的，表明它们都是谓词逻辑的推理定律。E31~E34与E35~E38只是A和B的顺序不同。 2．量词的消除与产生规则 谓词推理可以看作是对命题推理的扩充。除了原来的P规则（前提引入）、T规则（命题等价和蕴含）及反证法、CP规则外，为什么还需引入新的推理规则呢？ 命题逻辑中只有一种命题，但谓词逻辑中有2种，即量词量化的命题和谓词填式命题。如果仅由表2-2的推理定律就可推证，并不需要引入新的规则，但这种情况十分罕见，也失去了谓词逻辑本身的意义。为此，要引入如下4个规则完成量词量化命题与谓词填式之间的转换，其中的A(x)表示任意的谓词。 (1) 全称指定（消去）规则US（Ubiquity Specification，或记为?-）
对下列关系模式分别用关系代数、和SQL 实现下列查询 理解下面几句话： 1. SQL 语言是具有很坚实数学基础的语言 2. SQL 语言是介于关系代数和关系演算之间的结构化查询语言 3. 一个查询只要能用关系代数或关系演算实现，必能用SQL 实现 4. 一个查询即能用关系代数、关系演算、SQL 实现 5. 在SQL 语言中，能用非EXISTS 谓词实现的查询，均能用EXISTS 谓词实现，反之不一定。 1. 查询学生95001的所有信息。 ① 关系代数： )('95001'Student Sno =σ ②SQL 语言： SELECT * FROM Student WHERE Sno='95001' 2. 查询学生95001的姓名和所在系。 ① 关系代数： ))(('95001',Student Sno Sdept Sname =σπ ②SQL 语言： 方法一： SELECT Sname,Sdept FROM Student WHERE Sno='95001' 方法二： SELECT Sname,Sdept FROM Student WHERE EXISTS ( SELECT * FROM Student SX WHERE Student.Sno=SX.Sno AND SX.Sno='95001' ) 方法三： SELECT Sname,Sdept FROM Student WHERE Sno IN ( SELECT Sno FROM Student WHERE Sno='95001' ) 3. 查询选修了1号课的学生的学号。 ① 关系代数： ))(('1'SC Cno Sno =σπ ②SQL 语言： 方法一： SELECT Sno FROM SC
设前提为?x?yF(x, y) ，下面的推证是否正确？ (1) ?x?yF(x, y) P (2) ?yF(y, y) T (1) US 解：推证不正确。 取解释I：个体域为R，在I下前提被解释为?x?y(x>y) ，为真； 而?yF(y, y)被解释为?y(y>y) ，为假。 所以推理不正确。 错误的原因是第(2)步违反了US规则成立的条件y不应在P(x)中约束出现。
设前提为?x?yF(x, y) ，下面的推证是否正确？ (1) ?x?yF(x, y) P (2) ?yF(t, y) T (1) US (3) F(t, c) T (2) ES (4)?xF(x,c) T (3) UG (5)?y?x F(x,y) T (4) EG 解：推证不正确。 取与例2.16相同的解释，则?x?yF(x,y)为真； 而?y?x F(x,y)意为“存在着最小实数”，是假命题， 所以推理不正确。 之所以出现这样的错误，是第(3)步违反了ES规则成立的条件 P(x)中除x外还有其他自由出现的个体变元时，不能用此规则。
试证明 ?x(P(x)→Q(x))∧?x(Q(x)→R(x))??x(P(x)→R(x))证：(1)?x(P(x)→Q(x)) P (2)P(y)→Q(y)T (1) US (3)?x(Q(x)→R(x)) P (4)Q(y)→R(y)T (3) US (5)P(y)→R(y) T (2)(4) I (6)?x(P(x)→R(x)) T (5) UG 证毕。
试证明 ?x(C(x)→W(x)∧R(x))∧?x(C(x)∧Q(x))??x(Q(x)∧R(x))证：(1) ?x(C(x)∧Q(x))P (2) C(a)∧Q(a)T (1) ES (3) ?x(C(x)→W(x)∧R(x))P (4)C(a)→W(a)∧R(a)T (3) US (5)C(a) T (2) I (6)W(a)∧R(a) T (4)(5) I (7)Q(a)T (2) I (8)R(a)T (6) I (9)Q(a)∧R(a)T (7)(8) I (10)?x(Q(x)∧R(x)) T (9) EG 证毕。
第三章关系代数与关系运算 关系数据语言有三类： 1．关系代数语言 2．关系演算语言（元组关系演算语言、域关系演算语言） 3．具有关系代数和关系演算双重特点的语言如SQL 一．关系代数 关系代数：一种抽象的查询语言，是关系数据操纵语言的一种传统表达方式。用对关系的运算来表达查询。 运算：将一定的运算符作用于一定的运算对象上，得到预期的运算结果 运算三要素：运算符、运算对象、运算结果 关系代数的运算对象和结果都是：关系 关系代数运算符（四类）：集合运算符、专门的关系运算符、算术比较符和逻辑运算符 集合运算符：并（U）、差（—）、交（∩） 传统的集合运算符——从关系的“水平“方向即行的角度来进行 专门的关系运算符：广义笛卡尔积（ⅹ）、选择（σ）、投影（π）、连接、除 专门关系运算符不仅涉及行而且涉及列 比较运算符：>、<、=、≥、≤、≠ 逻辑运算符：￢∧∨ 用来辅助专门的关系运算符 二．传统的集合运算符
传统集合运算符是二目运算符 设关系R和S具有相同的目n(即n个属性),且相应的属性取自同一个域 1．并（Union） 记作：RUS={t|t∈R∨t∈S}结果仍是n目关系，由属于R或S的元组组成。 例： （a）（b） （c）（d） (e) 2.差 关系R与S的差记作：R-S={t|t∈R∧t∈S} 结果仍是n目，由属于R而不属于S的所有元组组成。如图E 3.交 关系R与S的交记作：R∩S = { t | t∈R∧t∈S }结果仍是n目，由即属于R又属于S 的所有元组组成。如图D 可以用差来表示R∩S=R-(R-S) 4．广义笛卡尔积 两个分别为n目和m目的关系R和S的广义笛卡尔积是一个（m+n）列的元组的集合。元组的前n列是关系R的一个元组，后m列是关系S的一个元组。若R有k1个元组，S 有k2个元组，那么关系R与S的广义笛卡尔积有k1 x k2个元组，记作 R×S = { t r t s | t r∈R∧t s∈S } 结果是m+n目 如图例
元组关系演算的语义研究 王小兵 西安电子科技大学计算机学院，陕西西安 (710071) E-mail：xbwang@https://www.doczj.com/doc/9317355628.html, 摘要：针对一些文献存在的问题，规范了特性谓词在元组关系演算中的表达形式，研究了完整性约束及空值对元组关系演算语义的影响，并通过实例加以说明。 关键词:元组关系演算，特性谓词，完整性约束，空值 中图分类号: TP311 文献标识码: A 1. 引言 20世纪60年代诞生的数据库技术，经过近半个世纪的发展，形成了坚实的理论基础、成熟的商业产品和广泛的应用领域。E.F Codd 提出的关系数据模型为当今主流的数据库管理系统提供了坚实的数学基础。关系数据模型有三种等价的操作语言：关系代数、SQL、关系演算，它们的非过程化程度依次递增，主要应用领域也不同。对于用户提出的查询要求，需要由专业人员书写SQL语句并执行得到结果。有一些复杂的查询，不易直接写出SQL语句，此时可求助于元组关系演算，大致过程为：先写出查询的元组关系演算表达式；再根据等价转化规则得到不含全称量词?的元组关系演算表达式；最后将元组关系演算表达式转化为SQL语句。不过，元组关系演算的抽象性和非过程性，产生了一些问题[1] [2] [3] 。对于这些问题，笔者进行了深入细致的分析，希望有助于人们对元组关系演算的学习和使用。 2. 元组关系演算 元组关系演算是关系演算的一种，是以数理逻辑中的谓词演算为基础的。文献[2] 分析元组关系演算的运行机制，介绍了一种易于正确理解和设计元组关系演算表达式的方法，并通过实例揭示了它与SQL之间的密切联系。经过仔细分析，笔者发现有一些问题值得商榷。 下面以[2] 中“学生选修课程”这一数据库模式为例。该数据库模式包含三个基本表：S表示学生基本情况，结构为S(s# , sn , age, sex)，各属性分别表示学号、学生姓名、年龄、性别；C表示课程基本情况，结构为C(c#, cn, tn)，各属性分别表示课程编号、课程名称、任课教师姓名；SC表示学生选课情况，结构为SC(s#, c#, g)，各属性分别表示学号、课程编号和成绩。 [2] 提出查询，要求检索Wang同学不学的课程的编号。在分析该查询的语义后，给出了三种不同的方案，分别用元组关系演算表达式(1)、(2)、(3)来表示。由于SQL只有与存在量词?对应的EXISTS谓词，因而使用谓词逻辑中全称量词?和存在量词?之间的等价转化公式，分别得到不包含?的元组演算表达式(4)、(5)、(6)，最后以此为依据写出三种不同形式的SQL语句。 {t[c#]|C(t)∧w(SC(w)∧t[c#]≠w[c#]∨v(S(v)∧w[s#]=v[s#]∧v[sn]≠'Wang'))} (1) {t[c#]|C(t)∧w(SC(w)∧t[c#]≠w[c#]∨v(S(v)∧(v[sn]≠'Wang'∨w[s#]≠v[s#])))} (2) {t[c#]|C(t)∧v(S(v)∧(v[sn]≠'Wang'∨w(SC(w)∧(w[s#]≠v[s#]∨t[c#]≠w[c#]))))} (3) {t[c#]|C(t)∧?w(SC(w)∧t[c#]=w[c#]∧?v(S(v)∧w[s#]=v[s#]∧v[sn]≠'Wang'))} (4)
关系演算 教学目标：让学生掌握元组关系演算和域关系演算； 教学重难点：ALPHA语言、QBE语言 教学工具：多媒体教室 课时安排：2课时 教学方法：讲授法、练习法 教学过程： 导入语：上节课我们已经学习了关系运算，那么今天我们继续学习关系演算。 2.7 关系演算 关系演算是以数理逻辑中的谓词演算为基础的，通过谓词形式来表示查询表达式。 根据谓词变元的不同，可将关系演算分为元组关系演算和域关系演算。 2.7.1 元组关系演算语言 元组关系演算是以元组变量作为谓词变元的基本对象。 元组关系演算语言的典型代表是E.F.Codd提出的ALPHA语言. 2.7.1.1 ALPHA语言 ALPHA语言是以谓词公式来定义查询要求的。在谓词公式中存在客体变元，这里称为元组变量。 元组变量是一个变量，其变化范围为某一个命名的关系。 ALPHA语言的基本格式是： <操作符> <工作空间名> (<目标表>)[:<操作条件>] 操作符有GET，PUT，HOLD，UPDATE，DELETE，DROP等到种。 1. 数据查询 （1）简单查询 例查询所有学生的数据。 GET W (S) 例2.13 查询所有被选修的课程号码。 GET W (https://www.doczj.com/doc/9317355628.html,O) （2）条件查询 例2.14 查询计算机系工资高于1000元的教师的姓名和工资。 GET W (T.TN,T.SAL):T.DEPT=’计算机’∧T.SAL>1000 （3）排序查询 例2.15 查询S3同学所选课程号及成绩，并按成绩降序排列。 GET W (https://www.doczj.com/doc/9317355628.html,O,SC.SCORE):SC.SNO=’S3’DOWN SC.SCORE DOWN表示降序，后面紧跟排序的属性名。 升序排列时使用UP。 （4）定额查询 例2.15 查询一名男教师的教师号和姓名。 GET W (1) (T.TNO,T.TN):T.SEX=’男’ 例2.16 查询一名男教师的教师号和姓名，并使他的年龄最小。 GET W (1) (T.TNO,T.TN):T.SEX=’男’ UP T.AGE （5）带元组变量的查询 例2.17 查询S3同学所选课程号。 RANGE SC X GET W (https://www.doczj.com/doc/9317355628.html,O):X.SNO=’S3’
习题四 1．试述关系模型的三个组成部分。 2．试述关系数据语言的特点和分类。 3．定义并解释下列术语，说明它们之间的联系与区别。 1）主码、候选码、外码。 2）笛卡尔积、关系、元组、属性、域。 3）关系、关系模式、关系数据库。 4. 试述关系模型的完整性规则。在参照完整性中，为什么外码属性的值也可以为空？什么情况下才可以为空？ 5. 试述等值连接与自然连接的区别和联系。 6. 对于学生选课关系，其关系模式为： 学生（学号，姓名，年龄，所在系）； 课程（课程名，课程号，先行课）； 选课（学号，课程号成绩）。 用关系代数完成如下查询。 1）求学过数据库课程的学生的姓名和学号。 2）求学过数据库和数据结构的学生姓名和学号。 3）求没学过数据库课程的学生学号。 4）求学过数据库的先行课的学生学号。 7. 设有一个SPJ数据库，包括S，P，J，SPJ四个关系模式： S（SNO，SNAME，STATUS，CITY）； P（PNO，PNAME，COLOR，WEIGHT）； J（JNO，JNANE，CITY）； SPJ（SNO，PNO，JNO，QTY）。
其中：供应商表S由供应商代码（SNO）、供应商姓名（SNAME）、供应商状态（STATUS）、供应商所在城市（CITY）组成；零件表P由零件代码（PNO）、零件名（PNAME）、颜色（COLOR）、重量（WEIGHT）组成；工程项目表J 由工程项目代码（JNO）、工程项目名（JNAME）、工程项目所在城市（CITY）组成；供应情况表SPJ由供应商代码（SNO）、零件代码（PNO）、工程项目代码（JNO）、供应数量组成（QTY）组成，表示某供应商供应某种零件给某工程项目的数量为QTY。 试用关系代数完成如下查询： 1）求供应工程J1 零件的供应商号码SNO。 2）求供应工程J1 零件P1的供应商号码SNO。 3）求供应工程J1 零件为红色的供应商号码SNO。 4）求没有使用天津供应商生产的红色零件的工程号。 5）求至少用了供应商S1所供应的全部零件的工程号。 8. 设属性A 是关系R 的主属性，则属性A 不能取空值小（NULL），这是_______。 A. 实体完整性规则 B. 参照完整性规则 C. 用户定义完整性规则 D. 域完整性规则 9. 下面对于关系的叙述中，不正确的是_______。 A. 关系中的每个属性是不可分解的 B. 在关系中元组的顺序是无关紧要的 C. 任意的一个二维表都是一个关系 D. 每一个关系只有一种记录类型 10. 设关系R和S的元组个数分别为100和300，关系T是R与S的笛卡尔积则T的元组个数是________。 A. 400 B. 10000 C. 30000 D. 90000 11. 设关系R与关系S具有相同的目（或称度），且相对应的属性的值取自同一个域，则R-（R-S）等于________。 A. R∪S B. R∩S C. R╳S D. R－S 习题四解答 1．答： 关系模型的三个组成部分为关系结构、关系操作和关系完整性约束。 在关系模型中，无论是实体集，还是实体集之间的联系均由单一的关系表示。关系模式可以形式化地表示为：R（U，D，Dom，F），其中R为关系名，U为组成该关系的属性集合，D为属性组U中属性所来自的域，Dom为属性向域的映像的集合，F为属性间数据的依赖关系集合。 关系操作语言包括关系代数、关系演算和基于映像的语言。关系操作语言灵活方便．表达能力和功能都非常强大。其主要特点是：关系操作语言操作一体化；关系操作的方式是一次一集合方式；关系操作语言是高度非过程化的语言。 关系模型中有三类完整性约束：实体完整性、参照完整性和用户定义的完整性。 2 答： 关系操作语言灵活方便，表达能力和功能都非常强大，其主要特点是：关系操作语言操作一体化；关系操作的方式是一次一集合方式；关系操作语言是高度非过程化的语言。关系操作语言包括关系代数、关系演算和基于映像的语言。关系代数语言是用对关系的运算来表达查询要求的语言。关系演算语言是用查询得到的元组应满足的谓词条件来表达查询要求的语言。基于映像的语言是具有关系代数和关系演算双重特点的语言。