《关系在计算机科学中的应用》由会员分享,可在线阅读,更多相关《关系在计算机科学中的应用(49页珍藏版)》请在金锄头文库上搜索。
1、1,第一章 集合与关系在计算机科学中的应用,1-2,集合论分为两种体系:一种是朴素集合论体系,也称为康托集合论体系;另一种是公理集合论体系。 自从19世纪末著名德国数学家康托(Cantor,18451918)创立集合论,迄今已有100多年的历史,集合的概念已深入到现代科学的各个方面,成为表达各种科学概念的必不可少的“数学语言”,然而有趣的是,集合本身却是一个不能精确定义的基本概念,但这并不妨碍我们对它的理解和使用。,1-3,集合论的特点是研究对象的广泛性,人们把研究的对象视作一个集合,本意可以是包罗万象的,但是最早所研究多半是分析数学的“数集”和几何学的“点集”。而集合中的元素真正成为包罗万象
2、的对象,应当说是从“计算机革命”开始:数字、符号、图像、语音以及光、电、热各种信息,它们都可以作为“数据”,这些数据就构成集合。,1-4,集合论总结出由各种对象构成的集合的共同性质,并用统一的方法来处理。正因为如此,集合论被广泛应用于各种科学和技术领域。由于集合论的语言适合于描述和研究离散对象及其关系,因此它是计算机科学与工程的理论基础,它在程序设计、形式语言、关系数据库、操作系统等计算机学科中得到广泛地应用。集合论的原理和方法成为名符其实的数学技术。,1-5,关系和函数是数学中的最重要的两个概念。在计算机科学的各个分支中,它们也是应用极为广泛的概念。人与人之间有父子、兄弟、同学关系;两数之间
3、有大于、等于、小于关系;元素与集合之间有属于关系;计算机程序间有调用关系。集合论为刻画这种联系提供了一种数学模型关系,它仍然是一个集合,以那种具有联系的对象组合为其成员。例如,在关系数据库模型中,每个数据库都是一个关系。计算机程序的输入和输出构成一个二元关系。在各种计算机程序设计语言中,关系和函数都是必不可少的概念。,1-6,如何在计算机上表示有限集合的子集,下面介绍一种二进制编码方法: 我们在表示一个集合时,元素的排列顺序是无关紧要的,但是为了便于在计算机上操作,有时我们给元素排定顺序,这样就可以用二进制数为足码表示任意集合的子集,这种方法称为子集的编码表示法。,1-7,设集合Aa1,a2,
4、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所示,它包括有行和列。一张二维表可有m行n列,二维表的每一行叫元组(记录),它代表一个完
8、整的数据,一个元组有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 设有实体学生概貌,它有四个属性:学号、姓名、年龄和所属系名,这个实体存放10学生的概貌,它们可用下列关系(即二
9、维表3)表示。,1-18,又设有实体课程的概况,它有三个属性:课程编号、课程名和先修课程号,我们假定每门课的先修课只有一门,这个实体存放六门课的概况,它们可用表4表示。 表4 课程概况表C,1-19,实体与实体间的联系也可用关系表示,如学生修读课程的情况可用学号与课程号构成一个新关系SC,它刻划学生修课情况,这个关系可用二维表表5表示。,1-20,1-21,从上面表示可以看出,数据实体与联系均可用二维表表示,在数据库中,用这种二维表构造数据的模型就是关系数据库。它是由E.F.Cold于1970年提出的。 用户使用关系数据库就是对一些二维表进行检索、插入、修改和删除等操作,关系数据库的DBMS必
10、须向用户提供使用数据库的语言,一般称为数据子语言,这种语言目前是以关系代数或谓词逻辑中方法表示的,更确切说就是这种语言以关系代数或谓词逻辑作为它的数学基础。,1-22,由于可用数学的方法来表示,使得对数据子语言的研究成为对数与谓词逻辑的化简问题。而引入数学表示方法,使得关系数据库具有比其它几种数据库较为优越的条件,正因为如此,关系数据库近几年发展迅速,成为最有前途最有希望的一种数据库,目前已基本上代替其它类型的数据库。 当今流行的各种大型网络数据库如:Sybase、Oracle、Informix、Foxpro等都是属于关系型数据库。关系数据库已成为数据库中最有实用价值和理论价值的数据库。,1-
11、23,三、关系代数与数据子语言,关系数据库的数据子语言,它的基本操作对象是二维表,它的基本操作有检索、插入、修改与删除,为了用数学的方法表示语言,有必要对其操作对象与基本操作加以研究,并将其抽象成数学符号与运算。 1.二维表与n元有序组集合 二维表是数据子语言的操作对象,一张二维表可看成若干元组的集合,而n元元组可视为一个n元有序组,因此一张二维表可看成是n元有序组的集合,因此我们说,数据子语言的操作对象是n元有序组的集合。,1-24,2.基本操作与集合运算,数据子语言的操作对象是集合,而对其对象操作可视为对集合的运算。 (1)检索与集合运算 对一张二维表的检索不外乎选择表中满足某些条件和一些
12、行和列。例如对表3表示的学生花名册S,要求年龄大于21岁的学生的学号与姓名,这是一种检索,它要求选择满足“年龄21”的那些行,再由这些行中选出属性学号与姓名,这种检索操作的结果还是一张二维表,这张二维表有两个属性以及一些满足“年龄21”的行,可用表6表示。,1-25,由此可见,检索是由一张表到另一张表的操作,从数学观点看,检索是一种一元运算,即一个集合通过此运算而得到另一个集合。下面我们就定义两种一元检索运算,一个叫选择(Select),另一个叫投影(Project)。,表6 年龄21的学生,1-26,投影运算(Projecting Operation),定义1.1 设有关系R,它由m个n元元
13、组组成,则 也是一个关系,它由m个k元元组组成,其各元组由属性 组成,这个运算叫做R在属性 上的投影运算(Projecting Operation)。 可见投影运算是从二维表中选择一些指定列而组成的新表。见下面两个例子:,1-27,例1.2 打印全体学生名单。 解:将这要求写为 姓名(学生花名册S) 例1.3 打印所有课程编号与课程名。 解:将此要求写为 课程编号,课程名(课程概况表C) 上述详细内容见表7和表8,1-28,表7 全体学生名单,表8,1-29,选择运算(Selecting Operation),定义1.2 设有关系R,则F (R )也是关系,它由R 中满足条件F 的元组所组成,
14、F为逻辑条件,它是一个命题公式,它按下列方法组成: 它的基本操作数是常量或元组分量(即属性); 由基本操作数通过比较运算:,而构成命题; 由命题通过命题联结词(与),(或), (非)构成新命题。 这种运算叫做R的选择运算(Selecting Operation),1-30,所以选择运算是从二维表中选出那些满足条件F的元组而组成的新表,即从二维表中选择满足条件F的行而组成。 例1.4 取出年龄大于21的数学系学生的概况。 年龄21系名=数学系(学生花名册S) 例1.5 取出先修课程为05的课程概况。 先修课程号=05(课程概况表C) 上述结果见表9和表10。,1-31,表9 年龄大于21的数学系
15、学生的概况,表10 先修课程为05的课程概况,1-32,将运算和 F 联合应用于关系就可以从关系中检索出所要求的任意行与列的内容。 例如: 例1.6 取出材料系学生的学号与姓名。 学号,姓名系名=材料系(学生花名册S) 见表11,1-33,表11 材料系学生,1-34,我们可以用两个二元运算和 F 检索一张二维表的内容,由于各实体之间是有联系的(即各表之间是有联系的),因此我们可以检索与几张表有关的内容。 例如我们可以检索学生林丽梅选修的课程编号,这种检索就涉及到两张表,一张是学生花名册S,另一张是选课表SC。对于这种检索,上述一元运算已经无法满足,我们需要引入另外的新的运算,即笛卡儿乘积。,
16、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 , 并定义为: A1A2An =(x1, x2, , xn)|x1A1x2A2, , xnAn 当A1=A2=An=A时, A1A2An简记为A n。,1-37,关系R与S的笛卡儿乘积,例1.7 设有关系R与S,见表12和表13,求R与S的笛卡儿乘积。,