《关系在计算机科学中的应用》由会员分享，可在线阅读，更多相关《关系在计算机科学中的应用（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的笛卡儿乘积。,
