关系在计算机科学中的应用PPT课件

1、.,1,第一章 集合与关系在计算机科学中的应用,.,1-2,集合论分为两种体系：一种是朴素集合论体系，也称为康托集合论体系；另一种是公理集合论体系。 自从19世纪末著名德国数学家康托（Cantor,18451918）创立集合论，迄今已有100多年的历史，集合的概念已深入到现代科学的各个方面，成为表达各种科学概念的必不可少的“数学语言”，然而有趣的是，集合本身却是一个不能精确定义的基本概念，但这并不妨碍我们对它的理解和使用。,.,1-3,集合论的特点是研究对象的广泛性，人们把研究的对象视作一个集合，本意可以是包罗万象的，但是最早所研究多半是分析数学的“数集”和几何学的“点集”。而集合中的元素真正

2、成为包罗万象的对象，应当说是从“计算机革命”开始：数字、符号、图像、语音以及光、电、热各种信息，它们都可以作为“数据”，这些数据就构成集合。,.,1-4,集合论总结出由各种对象构成的集合的共同性质，并用统一的方法来处理。正因为如此，集合论被广泛应用于各种科学和技术领域。由于集合论的语言适合于描述和研究离散对象及其关系，因此它是计算机科学与工程的理论基础，它在程序设计、形式语言、关系数据库、操作系统等计算机学科中得到广泛地应用。集合论的原理和方法成为名符其实的数学技术。,.,1-5,关系和函数是数学中的最重要的两个概念。在计算机科学的各个分支中，它们也是应用极为广泛的概念。人与人之间有父子、兄弟

3、、同学关系；两数之间有大于、等于、小于关系；元素与集合之间有属于关系；计算机程序间有调用关系。集合论为刻画这种联系提供了一种数学模型关系，它仍然是一个集合，以那种具有联系的对象组合为其成员。例如，在关系数据库模型中，每个数据库都是一个关系。计算机程序的输入和输出构成一个二元关系。在各种计算机程序设计语言中，关系和函数都是必不可少的概念。,.,1-6,如何在计算机上表示有限集合的子集,下面介绍一种二进制编码方法： 我们在表示一个集合时，元素的排列顺序是无关紧要的，但是为了便于在计算机上操作，有时我们给元素排定顺序，这样就可以用二进制数为足码表示任意集合的子集，这种方法称为子集的编码表示法。,.,

4、1-7,设集合Aa1，a2，an，用Bxxx表示A的一个子集，其中B是子集的符号，足码xxx是n位二进制数，n是集合A的基数，对于A，如果子集含有ai，则在足码的第i位上记入1，否则为0。所以P(A)=Bk0k2n-1也可将Bi的二进制数换算成十进制数。,.,1-8,【例1.1.4】 设A=a, b, c， 则各子集的编码表示为 =B 000=B 0 ， a=B 100=B 4 b=B 010=B 2 ， c=B 001=B 1 a, b=B 110=B 6 a, c=B 101=B 5 b, c=B 011=B 3 a, b, c=B 111 =B 7,.,1-9,关系在计算机科学中的应用,

5、一、概念 数据库是计算机管理数据的一种结构，一般讲，它需要两部分组成，一个是供存放数据用的大量存储空间，它们可以是磁盘，磁带等外存空间，另一个是管理数据库中数据的一组程序，这组程序叫数据库管理系统，简称DBMS，用户可以通过数据库管理系统所提供的语言使用数据库中的数据，这种使用包括下列几个方面：,.,1-10,DBMS的一些基本功能,(1)数据的检索：从数据库中取出满足一定条件要求的数据； (2)数据插入：将一些数据存储到数据库中供以后使用； (3)数据的修改：修改数据库中指定的数据； (4)数据的删除：删除数据库内指定的数据。,.,1-11,数据库内数据的基本组织格式如下：,(1)实体：实体

6、是数据库中数据的基本存放单位，如职工的简历、工资单、课程概貌、库存情况等均是实体，数据库内实体是一个整体，它内部的数据相互间是逻辑联系的。 (2)属性：实体都有一些性质，这些性质叫作此实体的属性，如职工简历这个实体就有姓名、性别和年龄等属性，所有实体的属性就组成这个实体，如职工简历这个实体实际上就由上述属性组成。,.,1-12,(3)属性域：实体的每个属性的表现形式都是统一的，如姓名是由n个字母所组成的字符串，性别为M，F中之一(M代表男性，F代表女性)，年龄由两个数字所组成。对于每个属性它都有一个表示范围(即取值范围)。 (4)联系：在数据库中实体是基本数据单位，但是各实体间是有一定联系的，

7、如实体学生与课程之间有联系，这个联系是学生修读课程，教师也是实体，而教师与学生、课程也有联系。,.,1-13,在数据库中存储数据时不仅要存放实体的数据，而且要存放联系的数据，如上例中，不仅要存放有关教师、学生、课程的实体，而且还要存放学生修读何种课程的情况及教师教授何种课程的情况，只有这样数据库中的这个数据库中的这个数据信息才是完整的。 数据库目前可以三种结构模型，它们分别叫层次模型、网络模型和关系模型。,.,1-14,关系数据库,在关系数据库中数据按二维表的形式存放，这种二维表就叫关系，数据库中的实体与联系按这种二维表的形式存放。,.,1-15,二维表的形式如表1所示，它包括有行和列。一张二

8、维表可有m行n列，二维表的每一行叫元组(记录)，它代表一个完整的数据，一个元组有n个分量，因此这个元又叫n元组。二维表的每一列表示数据的分量。这种二维表叫n元关系。 表1 二维表的形式,m列,.,1-16,设一个实体A有n个属性，分别为 A1,A2,A3,An，它可表示如下： A(A1,A2,A3,An) 这个实体可以允许存放m个数据，此时这个实体可用一个关系来表示，亦即可用一张二维表来表示，这张二维表的每一列是一个属性，二维表的每一行可存放实体中一个数据，这个表示实体的二维表见表2。 表2 实体A的关系,m 行,.,1-17,二、具体例子,例1.1 设有实体学生概貌，它有四个属性：学号、姓名

9、、年龄和所属系名，这个实体存放10学生的概貌，它们可用下列关系(即二维表3)表示。,.,1-18,又设有实体课程的概况，它有三个属性：课程编号、课程名和先修课程号，我们假定每门课的先修课只有一门，这个实体存放六门课的概况，它们可用表4表示。 表4 课程概况表C,.,1-19,实体与实体间的联系也可用关系表示，如学生修读课程的情况可用学号与课程号构成一个新关系SC，它刻划学生修课情况，这个关系可用二维表表5表示。,.,1-20,.,1-21,从上面表示可以看出，数据实体与联系均可用二维表表示，在数据库中，用这种二维表构造数据的模型就是关系数据库。它是由E.F.Cold于1970年提出的。 用户使

10、用关系数据库就是对一些二维表进行检索、插入、修改和删除等操作，关系数据库的DBMS必须向用户提供使用数据库的语言，一般称为数据子语言，这种语言目前是以关系代数或谓词逻辑中方法表示的，更确切说就是这种语言以关系代数或谓词逻辑作为它的数学基础。,.,1-22,由于可用数学的方法来表示，使得对数据子语言的研究成为对数与谓词逻辑的化简问题。而引入数学表示方法，使得关系数据库具有比其它几种数据库较为优越的条件，正因为如此，关系数据库近几年发展迅速，成为最有前途最有希望的一种数据库，目前已基本上代替其它类型的数据库。 当今流行的各种大型网络数据库如：Sybase、Oracle、Informix、Foxpr

11、o等都是属于关系型数据库。关系数据库已成为数据库中最有实用价值和理论价值的数据库。,.,1-23,三、关系代数与数据子语言,关系数据库的数据子语言，它的基本操作对象是二维表，它的基本操作有检索、插入、修改与删除，为了用数学的方法表示语言，有必要对其操作对象与基本操作加以研究，并将其抽象成数学符号与运算。 1.二维表与n元有序组集合 二维表是数据子语言的操作对象，一张二维表可看成若干元组的集合，而n元元组可视为一个n元有序组，因此一张二维表可看成是n元有序组的集合，因此我们说，数据子语言的操作对象是n元有序组的集合。,.,1-24,2.基本操作与集合运算,数据子语言的操作对象是集合，而对其对象操

12、作可视为对集合的运算。 (1)检索与集合运算 对一张二维表的检索不外乎选择表中满足某些条件和一些行和列。例如对表3表示的学生花名册S，要求年龄大于21岁的学生的学号与姓名，这是一种检索，它要求选择满足“年龄21”的那些行，再由这些行中选出属性学号与姓名，这种检索操作的结果还是一张二维表，这张二维表有两个属性以及一些满足“年龄21”的行，可用表6表示。,.,1-25,由此可见，检索是由一张表到另一张表的操作，从数学观点看，检索是一种一元运算，即一个集合通过此运算而得到另一个集合。下面我们就定义两种一元检索运算，一个叫选择(Select)，另一个叫投影(Project)。,表6 年龄21的学生,.

13、,1-26,投影运算(Projecting Operation),定义1.1 设有关系R，它由m个n元元组组成，则 也是一个关系，它由m个k元元组组成，其各元组由属性 组成，这个运算叫做R在属性 上的投影运算(Projecting Operation)。 可见投影运算是从二维表中选择一些指定列而组成的新表。见下面两个例子：,.,1-27,例1.2 打印全体学生名单。 解：将这要求写为 姓名(学生花名册S) 例1.3 打印所有课程编号与课程名。 解：将此要求写为 课程编号，课程名(课程概况表C) 上述详细内容见表7和表8,.,1-28,表7 全体学生名单,表8,.,1-29,选择运算(Selec

14、ting Operation),定义1.2 设有关系R，则F (R )也是关系，它由R 中满足条件F 的元组所组成，F为逻辑条件，它是一个命题公式，它按下列方法组成： 它的基本操作数是常量或元组分量(即属性)； 由基本操作数通过比较运算：，而构成命题； 由命题通过命题联结词(与)，(或)， (非)构成新命题。 这种运算叫做R的选择运算(Selecting Operation),.,1-30,所以选择运算是从二维表中选出那些满足条件F的元组而组成的新表，即从二维表中选择满足条件F的行而组成。 例1.4 取出年龄大于21的数学系学生的概况。 年龄21系名=数学系(学生花名册S) 例1.5 取出先修

15、课程为05的课程概况。 先修课程号=05(课程概况表C) 上述结果见表9和表10。,.,1-31,表9 年龄大于21的数学系学生的概况,表10 先修课程为05的课程概况,.,1-32,将运算和 F 联合应用于关系就可以从关系中检索出所要求的任意行与列的内容。 例如： 例1.6 取出材料系学生的学号与姓名。 学号，姓名系名=材料系(学生花名册S) 见表11,.,1-33,表11 材料系学生,.,1-34,我们可以用两个二元运算和 F 检索一张二维表的内容，由于各实体之间是有联系的(即各表之间是有联系的)，因此我们可以检索与几张表有关的内容。 例如我们可以检索学生林丽梅选修的课程编号，这种检索就涉

16、及到两张表，一张是学生花名册S，另一张是选课表SC。对于这种检索，上述一元运算已经无法满足，我们需要引入另外的新的运算，即笛卡儿乘积。,.,1-35,定义1.3 设, 为集合， 用中元素为第一元素， 中元素为第二元素构成有序对。 所有这样的有序对组成的集合称为集合和的笛卡儿乘积(Descartesian product) ， 又称作直积， 记作。 和 的笛卡儿积的符号化表示为： AB=（x, y）|xAyB,定义1.3 笛卡儿乘积,.,1-36,定义1.4 n阶笛卡儿积 若nN， 且n1， A1, A2, , An是n 个集合， 它们的n 阶笛卡儿积记作A1A2An , 并定义为： A1A2A

17、n =（x1, x2, , xn）|x1A1x2A2, , xnAn 当A1=A2=An=A时， A1A2An简记为A n。,.,1-37,关系R与S的笛卡儿乘积,例1.7 设有关系R与S，见表12和表13，求R与S的笛卡儿乘积。,表12 R,表13 S,.,1-38,表14 RS,解： 两个关系R与S的笛卡儿乘积见表14。,.,1-39,从笛卡儿乘积的定义看出，这种运算是将两张表联成一张表的运算，如果我们所要检索的内容牵涉到两张表，此时只要先用这个运算将两张表统一成一张表，然后再用“投影”和“选择”就可找出所需的检索内容了。 但是，在大多数情况下两张相联表之间均有一定关系，即两张表均有相同的

18、分量(字段)，如表3学生花名册S和表5选课表SC间有相同的分量“学号”，表C与SC间也有相同分量“课程编号”，而我们所需要相联后的表是在公共分量外有相等内容的那些元组构成。因此我们在笛卡儿乘积的基础上再引入一个二元运算叫自然联接(Nature Join)。,.,1-40,自然联接(Nature Join),定义1.5 设有n元关系R和m元关系S，R有属性R1，R2，Rn，S有属性S1，S2，Sm，其中S中的属性S1，S2，Sp分别与R中的属性 Rn-p+1，Rn-P+2，Rn相同，此时可定义R与S的自然联接(Nature Join) R|S如下：,.,1-41,自然联接的例子,例1.8 设R与

19、S均为三元关系，见表15和表16，求R|S。,表15 R,表16 S,.,1-42,表17 R|S,解：关系R与S的自然联接 R|S为五元关系，见表17,.,1-43,例1.9 找出学生的姓名为林丽梅所修读课程的课程编号。 解：这个检索与表3学生花名册S和表5选课表SC的关，所以首先自然联接将S与SC联成一张表，然后再在联接后的表中用投影和选择F 找出所需的内容，故可写成： 课程编号姓名=林丽梅(S|SC),.,1-44,例1.10 打印学生姓名为林丽梅所修读课程的课程名。 解：这个检索涉及到三张表，因此可以用两次自然联接将三张表联成一张表，然后再用投影和选择检索所要求的内容。则 课程名姓名=林丽梅(S|SC|C) 至此，我们介绍有关检索的几个例子，其中两个一元运算，两个二元运算，由于自然联接可以用其它三个运算表示，即自然联接不是基本运算，所以实际上只要三个运算就足够对二维表进行检索。,.,1-45,(2)插入、修改和删除操作与集合运算,所谓插入操作(Insert Operation)就是在关系中增加一些元组，为完成这种操作我们可引入另一个集合运算。这种操作相当于集合的并运算。 例1.11 设某系开设课程之概况由关系C表示之(见表4)，现增设两门课，其概况为表1