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

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,1-,*,第一章 集合与关系在计算机科学中的应用,1,集合论分为两种体系：一种是朴素集合论体系，也称为康托集合论体系；另一种是公理集合论体系。,自从,19,世纪末著名德国数学家康托（,Cantor,18451918,）创立集合论，迄今已有,100,多年的历史，集合的概念已深入到现代科学的各个方面，成为表达各种科学概念的必不可少的“数学语言”，然而有趣的是，集合本身却是一个不能精确定义的基本概念，但这并不妨碍我们对它的理解和使用。,2,集合论的特点是研究对象的广泛性，人们把研究的对象视作一个集合，本意可以是包罗万象的，但是最早所研究多半是分析数学的“数集”和几何学的“点集”。而集合中的元素真正成为包罗万象的对象，应当说是从“计算机革命”开始：数字、符号、图像、语音以及光、电、热各种信息，它们都可以作为“数据”，这些数据就构成集合。,3,集合论总结出由各种对象构成的集合的共同性质，并用统一的方法来处理。正因为如此，集合论被广泛应用于各种科学和技术领域。由于集合论的语言适合于描述和研究离散对象及其关系，因此它是计算机科学与工程的理论基础，它在程序设计、形式语言、关系数据库、操作系统等计算机学科中得到广泛地应用。集合论的原理和方法成为名符其实的数学技术。,4,关系和函数是数学中的最重要的两个概念。在计算机科学的各个分支中，它们也是应用极为广泛的概念。人与人之间有父子、兄弟、同学关系；两数之间有大于、等于、小于关系；元素与集合之间有属于关系；计算机程序间有调用关系。集合论为刻画这种联系提供了一种数学模型,关系，它仍然是一个集合，以那种具有联系的对象组合为其成员。例如，在关系数据库模型中，每个数据库都是一个关系。计算机程序的输入和输出构成一个二元关系。在各种计算机程序设计语言中，关系和函数都是必不可少的概念。,5,如何在计算机上表示有限集合的子集,下面介绍一种二进制编码方法：,我们在表示一个集合时，元素的排列顺序是无关紧要的，但是为了便于在计算机上操作，有时我们给元素排定顺序，这样就可以用二进制数为足码表示任意集合的子集，这种方法称为子集的编码表示法。,6,设集合,A,a,1,，,a,2,，,，,a,n,，用,B,xx,x,表示,A,的一个子集，其中,B,是子集的符号，足码,xxx,是,n,位二进制数，,n,是集合,A,的基数，对于,A,，如果子集含有,a,i,，则在足码的第,i,位上记入,1,，否则为,0,。所以,P(A)=,B,k,0,k,2,n,-1,也可将,B,i,的二进制数换算成十进制数。,7,【,例,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,8,关系在计算机科学中的应用,一、概念,数据库是计算机管理数据的一种结构，一般讲，它需要两部分组成，一个是供存放数据用的大量存储空间，它们可以是磁盘，磁带等外存空间，另一个是管理数据库中数据的一组程序，这组程序叫数据库管理系统，简称,DBMS,，用户可以通过数据库管理系统所提供的语言使用数据库中的数据，这种使用包括下列几个方面：,9,DBMS,的一些基本功能,(1),数据的检索：从数据库中取出满足一定条件要求的数据；,(2),数据插入：将一些数据存储到数据库中供以后使用；,(3),数据的修改：修改数据库中指定的数据；,(4),数据的删除：删除数据库内指定的数据。,10,数据库内数据的基本组织格式如下：,(1),实体：实体是数据库中数据的基本存放单位，如职工的简历、工资单、课程概貌、库存情况等均是实体，数据库内实体是一个整体，它内部的数据相互间是逻辑联系的。,(2),属性：实体都有一些性质，这些性质叫作此实体的属性，如职工简历这个实体就有姓名、性别和年龄等属性，所有实体的属性就组成这个实体，如职工简历这个实体实际上就由上述属性组成。,11,(3),属性域：实体的每个属性的表现形式都是统一的，如姓名是由,n,个字母所组成的字符串，性别为,M,，,F,中之一,(M,代表男性，,F,代表女性,),，年龄由两个数字所组成。对于每个属性它都有一个表示范围,(,即取值范围,),。,(4),联系：在数据库中实体是基本数据单位，但是各实体间是有一定联系的，如实体学生与课程之间有联系，这个联系是学生修读课程，教师也是实体，而教师与学生、课程也有联系。,12,在数据库中存储数据时不仅要存放实体的数据，而且要存放联系的数据，如上例中，不仅要存放有关教师、学生、课程的实体，而且还要存放学生修读何种课程的情况及教师教授何种课程的情况，只有这样数据库中的这个数据库中的这个数据信息才是完整的。,数据库目前可以三种结构模型，它们分别叫层次模型、网络模型和关系模型。,13,关系数据库,在关系数据库中数据按二维表的形式存放，这种二维表就叫关系，数据库中的实体与联系按这种二维表的形式存放。,14,二维表的形式如表,1,所示，它包括有行和列。一张二维表可有,m,行,n,列，二维表的每一行叫元组,(,记录,),，它代表一个完整的数据，一个元组有,n,个分量，因此这个元又叫,n,元组。二维表的每一列表示数据的分量。这种二维表叫,n,元关系。,表,1,二维表的形式,n,列,m,列,15,设一个实体,A,有,n,个属性，分别为,A,1,A,2,A,3,A,n,，它可表示如下：,A(A,1,A,2,A,3,A,n,),这个实体可以允许存放,m,个数据，此时这个实体可用一个关系来表示，亦即可用一张二维表来表示，这张二维表的每一列是一个属性，二维表的每一行可存放实体中一个数据，这个表示实体的二维表见表,2,。,表,2,实体,A,的关系,A,1,A,2,A,3,A,n-1,A,n,m,行,16,二、具体例子,例,1.1,设有实体学生概貌，它有四个属性：学号、姓名、年龄和所属系名，这个实体存放,10,学生的概貌，它们可用下列关系,(,即二维表,3),表示。,17,又设有实体课程的概况，它有三个属性：课程编号、课程名和先修课程号，我们假定每门课的先修课只有一门，这个实体存放六门课的概况，它们可用表,4,表示。,表,4,课程概况表,C,课程编号,课程名,先修课程号,01,02,03,04,05,06,OSPL,DB,ML,MC,DS,02,05,06,05,06,04,18,实体与实体间的联系也可用关系表示，如学生修读课程的情况可用学号与课程号构成一个新关系,SC,，它刻划学生修课情况，这个关系可用二维表表,5,表示。,19,20,从上面表示可以看出，数据实体与联系均可用二维表表示，在数据库中，用这种二维表构造数据的模型就是关系数据库。它是由,E.F.Cold,于,1970,年提出的。,用户使用关系数据库就是对一些二维表进行检索、插入、修改和删除等操作，关系数据库的,DBMS,必须向用户提供使用数据库的语言，一般称为数据子语言，这种语言目前是以关系代数或谓词逻辑中方法表示的，更确切说就是这种语言以关系代数或谓词逻辑作为它的数学基础。,21,由于可用数学的方法来表示，使得对数据子语言的研究成为对数与谓词逻辑的化简问题。而引入数学表示方法，使得关系数据库具有比其它几种数据库较为优越的条件，正因为如此，关系数据库近几年发展迅速，成为最有前途最有希望的一种数据库，目前已基本上代替其它类型的数据库。,当今流行的各种大型网络数据库如：,Sybase,、,Oracle,、,Informix,、,Foxpro,等都是属于关系型数据库。关系数据库已成为数据库中最有实用价值和理论价值的数据库。,22,三、关系代数与数据子语言,关系数据库的数据子语言，它的基本操作对象是二维表，它的基本操作有检索、插入、修改与删除，为了用数学的方法表示语言，有必要对其操作对象与基本操作加以研究，并将其抽象成数学符号与运算。,1.,二维表与,n,元有序组集合,二维表是数据子语言的操作对象，一张二维表可看成若干元组的集合，而,n,元元组可视为一个,n,元有序组，因此一张二维表可看成是,n,元有序组的集合，因此我们说，数据子语言的操作对象是,n,元有序组的集合。,23,2.,基本操作与集合运算,数据子语言的操作对象是集合，而对其对象操作可视为对集合的运算。,(1),检索与集合运算,对一张二维表的检索不外乎选择表中满足某些条件和一些行和列。例如对表,3,表示的学生花名册,S,，要求年龄大于,21,岁的学生的学号与姓名，这是一种检索，它要求选择满足“年龄,21”,的那些行，再由这些行中选出属性学号与姓名，这种检索操作的结果还是一张二维表，这张二维表有两个属性以及一些满足“年龄,21”,的行，可用表,6,表示。,24,由此可见，检索是由一张表到另一张表的操作，从数学观点看，检索是一种一元运算，即一个集合通过此运算而得到另一个集合。下面我们就定义两种一元检索运算，一个叫选择,(Select),，另一个叫投影,(Project),。,学号,姓名,0301019,0301010,0305045,陈悦,林丽梅,吴迪,表,6,年龄,21,的学生,25,投影运算,(Projecting Operation),定义,1.1,设有关系,R,，它由,m,个,n,元元组组成，则 也是一个关系，它由,m,个,k,元元组组成，其各元组由属性 组成，这个运算叫做,R,在属性 上的投影运算,(Projecting Operation),。,可见投影运算是从二维表中,选择一些指定列而组成的新表,。见下面两个例子：,26,例,1.2,打印全体学生名单。,解：将这要求写为,姓名,(,学生花名册,S),例,1.3,打印所有课程编号与课程名。,解：将此要求写为,课程编号，课程名,(,课程概况表,C),上述详细内容见表,7,和表,8,27,课程编号,课程名,01,02,03,04,05,06,OSPL,DB,ML,MC,DS,表,7,全体学生名单,表,8,28,选择运算,(Selecting Operation),定义,1.2,设有关系,R,，则,F,(,R,),也是关系，它由,R,中满足条件,F,的元组所组成，,F,为逻辑条件，它是一个命题公式，它按下列方法组成：,它的基本操作数是常量或元组分量,(,即属性,),；,由基本操作数通过比较运算：,，,，,而构成命题；,由命题通过命题联结词,(,与,),，,(,或,),，,(,非,),构成新命题。,这种运算叫做,R,的选择运算,(Selecting Operation),29,所以选择运算是从二维表中选出那些满足条件,F,的元组而组成的新表，即从二维表中选择满足条件,F,的行而组成。,例,1.4,取出年龄大于,21,的数学系学生的概况。,年龄,21,系名,=,数学系,(,学生花名册,S),例,1.5,取出先修课程为,05,的课程概况。,先修课程号,=05,(,课程概况表,C),上述结果见表,9,和表,10,。,30,学号,姓名,年龄,系名,0301019,0301010,陈悦,林丽梅,22,22,数学系,数学系,表,9,年龄大于,21,的数学系学生的概况,课程编号,课程名,先修课程号,02,04,PLML,05,05,表,10,先修课程为,05,的课程概况,31,将运算,和,F,联合应用于关系就可以从关系中检索出所要求的任意行与列的内容。,例如：,例,1.6,取出材料系学生的学号与姓名。,学号，姓名,系名,=,材料系,(,学生花名册,S),见表,11,32,学号,姓名,0309021,0309026,李玉兰,林铁,表,11,材料系学生,33,我们可以用两个二元运算,和,F,检索一张二维表的内容，由于各实体之间是有联系的,(,即各表之间是有联系的,),，因此我们可以检索与几张表有关的内容。,例如我们