关系在计算机中的应用.doc

关系在计算机科学中的应用 1.4.1关系在关系数据库中的应用 数据库是计算机管理数据的一种机构，一般讲它由两部分组成，一部分是供存入数据用的大量存储空间，它们可以是磁盘、磁带、光盘等外存空间；另一部分是管理数据库中数据的一组程序，这组程序叫数据库管理系统，简称DBMS。用户可通过数据管理系统所提供的语言使用数据库中的数据，这种使用包括下列几个方面。(1)数据的检索：从数据库中取出满足一定条件的数据。(2)数据插入：将一些数据存储到数据库中供以后使用。(3)数据的修改：修改数据库中指定的数据。(4)数据的删除：删除数据库中指定的数据。供用户使用数据库的语言有的是从终端装置打入，这种语言一般叫终端查询语言，简称为TQL；有的可附属于某些宿主语言，如可附属于FORTRAN，COBOL等语言作为这些语言的扩充成分。数据库内的数据一般都按一定格式组织与存放，数据库中数据的基本组织模式如下：(1)实体 实体是数据库中数据的基本存放单位，如教师的简历，课程表，课程概貌，合同执行情况，物资代销情况等均是实体，数据库内实体是一个整体，它内部的数据相互间是有逻辑联系的。(2) 属性 实体都有一些性质，这些性质叫此实体的属性，如教师简历这个实体就有姓名、性别、职称等属性，所有实体的属性就组成这个实体，如教师实体实际上就是由姓名、性别、职称等属性组成。(3) 属性域 实体的每个属性的表现形式都是统一的，如姓名是由多个字母所组成的字，性别为M，F中之一(M代表男性，F代表女性)，职称是由多个字母所组成的字，对每个属性它有一个表示范围，如姓名这个属性的表示范围是多个由26个字母所组成的集合中的字母，而性别的表示范围是集合M，F，职称的表示范围是由不同领域的职称枚举类型确定的(如大学中教师职称一般包括助教、讲师、副教授、教授、助理研究员、副研究员、研究员)，这种属性的表示范围就是属性域，每个属性都有一个属性域。(4) 联系 在数据库中实体是基本的数据单位，但是各实体间是有一定联系的，如实体学生与课程之间有联系，这个联系是学生修读课程，教师也是实体，而教师与学生、课程也有联系。在数据库中存储数据时不仅要存放实体的数据，而且还有存放联系的数据，如上例中，不仅要存放有教师、学生、课程的实体，而且还要存放学生修读何种课程的情况及教师教授何种课程的情况，只有这样数据库中的这个数据信息才是完整的。数据库信息操作所需要的时间依赖于这些信息是怎样存储的。插入和删除记录，更新记录，检索记录以及从一些重叠的数据库中组合记录的操作，在一个大型数据库中每天要执行几百万次。由于这些操作的重要性，已经开发了数据库表示的各种方法。我们将讨论其中的一种基于关系概念的方法，叫做关系数据模型。一般来说，数据库由记录组成，这些记录是由字段构成的n元组。这些字段是n元组的数据项。例如，学生记录的数据库可以由包启学生的姓名、学号、专业、平均成绩的字段构成。关系数据模型把一个记录的数据库表示成一个n元关系。我们在这里以目前应用最广泛的关系式数据库为例，来介绍集合的应用。在关系数据库中数据按二维表的形式存放，这种二维表就叫关系，数据库中的实体与联系均按这种二维表的形式存放。二维表的形式如表1.4.1所示，它包括有行和列。一张二维表可有m行n列，二维表的每一行叫元组，它代表一个完整的数据。一个元组有n个分量，因此这个元组又叫n元元组。二维表的每一列表示数据的分量。这种二维表叫n元关系。二维表的形式 表1.4.1名称号码类型价格数量 设一个实体A有n个属性，分别为A1，A2，A3，An，它可表示如下：A(A1，A2，A3，。，An)这个实体可以允许存放m个数据，此时这个实体可用一个关系表示之，亦即可用一张二维表表示之，这张二维表的每一列是一个属性，二维表的每一行可存放实体中的一个数据，这个表示实体的二维表见表1.4.2。表1.4.2实体A的关系A1A2A3An-2An-1An 现在我们举几个例子。例1.4.1 设有实体T表示教师概貌，它有四个属性，编号、姓名、年龄、所属系名，分别可用T#，TN，TA及TD表示，这个实体存放6个教师的概貌，它们可用下列关系(即二维表)表示。表1.4.3实体T的关系T#TNTATD0001AB25CS0002AC31MA0003AD42MA0004AE55CS0005AF40CS0006AG30CS 又设有实体课程的概况C，它有三个属性：课程号、课程名、认课教师编号，它们分别用C#，CN，T#表示之(我们假定每个教师可以教授多门课程)，这个实体存放六门课的概况，它们可用下列关系表示。 表1.4.4实体C的关系C#CNT#01OS000202PL000503DB000604ML000505MC000606DS0004当n元组的某个域的值能够确定这个n元组时，n元关系的这个域就叫做主键码。这就是说当关系中没有两个n元组在这个域有相同的值时这个域就是主键码。由于常常要对数据库增加或删除记录。由于这一点，一个域是主键码的性质是随时间而改变的。所以，一个主键码应该选择那种无论数据库怎样改变都能够继续存在的。用数据库的内涵的主键码就可以做到这一点，它包含了在表示这个数据库的n元关系中所有可能含有的n元组。在表1.4.4中课程号码和课程名是唯一的，因此课程号域和课程名域都可以做主键码，但教师号码不是唯一的，因此该域不能做主键码。在一个n元关系中域的组合也可以唯一地标识n元组。当一组域的值确定了一个关系中的n元组时，这些域的笛卡儿积就叫做复合键码。因为主键码和复合键码用于唯一的标识数据库中的记录，当新的记录加到这个数据库时键码要保持有效性是非常重要的。因此，应该做检测以保证在这个或这些相应的字段中每一个新记录与表中所有其他的记录不同。例如表1.4.3中使用教师的编号作为教师记录的键码是有意义的，因为没有两个教师有相同的编号。实体与实体间的联系也可用关系表示，如教师认课情况可用编号与课程构成一个新关系TC，它刻画了教师认课情况，这个关系可用下面二维表1.4.5表示。有时，在关系所表示的联系中还可以附加一些数据，如关系TC中还可以加入课程的学时CT，这时可在原关系中增加一个属性CT表示之，这个修改后的关系可叫TCT，以后我们常用这种修改后的TCT，这种修改后的关系TCT可用二维表1.4.6表示。表1.4.5 联系TC的关系 表1.4.6 修改后的关系TCT0001000100020002000200030004000400040005000500060007000700080008 01020102030504050601050101020406 T#C#CT0001000100020002000200030004000400040005000500060007000700080008 01020102030504050601050101020406 365072726072363660605450721083654 从上面表示可以看出，数据实体与联系均可用二维表表示，在数据库中，用这种二维表构造数据的模型就叫关系式数据库。现在我们举几个例子。例1.4.1 设有实体T表示教师概貌，它有四个属性，编号、姓名、年龄、所属系名，分别可用T#，TN，TA及TD表示，这个实体存放6个教师的概貌，它们可用下列关系(即二维表)表示。表1.4.3实体T的关系T#TNTATD0001AB25CS0002AC31MA0003AD42MA0004AE55CS0005AF40CS0006AG30CS 又设有实体课程的概况C，它有三个属性：课程号、课程名、认课教师编号，它们分别用C#，CN，T#表示之(我们假定每个教师可以教授多门课程)，这个实体存放六门课的概况，它们可用下列关系表示。 表1.4.4实体C的关系C#CNT#01OS000202PL000503DB000604ML000505MC000606DS0004当n元组的某个域的值能够确定这个n元组时，n元关系的这个域就叫做主键码。这就是说当关系中没有两个n元组在这个域有相同的值时这个域就是主键码。由于常常要对数据库增加或删除记录。由于这一点，一个域是主键码的性质是随时间而改变的。所以，一个主键码应该选择那种无论数据库怎样改变都能够继续存在的。用数据库的内涵的主键码就可以做到这一点，它包含了在表示这个数据库的n元关系中所有可能含有的n元组。在表1.4.4中课程号码和课程名是唯一的，因此课程号域和课程名域都可以做主键码，但教师号码不是唯一的，因此该域不能做主键码。在一个n元关系中域的组合也可以唯一地标识n元组。当一组域的值确定了一个关系中的n元组时，这些域的笛卡儿积就叫做复合键码。因为主键码和复合键码用于唯一的标识数据库中的记录，当新的记录加到这个数据库时键码要保持有效性是非常重要的。因此，应该做检测以保证在这个或这些相应的字段中每一个新记录与表中所有其他的记录不同。例如表1.4.3中使用教师的编号作为教师记录的键码是有意义的，因为没有两个教师有相同的编号。实体与实体间的联系也可用关系表示，如教师认课情况可用编号与课程构成一个新关系TC，它刻画了教师认课情况，这个关系可用下面二维表1.4.5表示。有时，在关系所表示的联系中还可以附加一些数据，如关系TC中还可以加入课程的学时CT，这时可在原关系中增加一个属性CT表示之，这个修改后的关系可叫TCT，以后我们常用这种修改后的TCT，这种修改后的关系TCT可用二维表1.4.6表示。表1.4.5 联系TC的关系 表1.4.6 修改后的关系TCT0001000100020002000200030004000400040005000500060007000700080008 01020102030504050601050101020406 T#C#CT0001000100020002000200030004000400040005000500060007000700080008 01020102030504050601050101020406 365072726072363660605450721083654 从上面表示可以看出，数据实体与联系均可用二维表表示，在数据库中，用这种二维表构造数据的模型就叫关系式数据库。例1.4.8 从数据库取出所有重量大于100克的轴承部件。解 我们可以将此要求写为：RP,其中谓词P表示重量大于100克的轴承部件。3数据子语言与关系代数综上所述我们可以知道，在关系数据库中需要向用户提供使用数据库的数据子语言。这个数据子语言可以允许用户对数据库进行检索、插入、修改及删除操作。这种数据子语言相当于一种代数结构，而这个代数结构的研究对象是n元有限组的集合，对它一共有五种基本操作，其中两个是一元运算三个是二元运算，它们是：投影运算：RA限定运算：RP笛卡尔乘积：RS并运算：RS差运算：RS这些运算都是封闭的。因此它们构成了一个代数，称此代数为关系代数。由此可见，在关系式数据库的运算中自然联接并不出现，这是因为自然联接并不是基本运算符，它可以由其他运算符生成。4数据子语言的优化与关系代数在关系数据库中，用户用数据子语言使用数据库，相同的要求有时可以有多种不同的写法，而不同的写法在计算机内执行时可得到完全不同的效率，我们知道，在计算机内执行一个笛卡尔积是很花时间的，这个时间正比于两个关系的元组数，并且同关系的元素也有关系，因此一般希望对执行笛卡尔乘积的两个关系，尽是让其先作投影与限定运算，这样可使其执行速度大为提高，上述情况对自然联接也适用，另外，为了优化子语言使它具有最高效率，我们也可用关系代数等价公式的转换来实现。由上面所述，我们也可以看出如何将关系数据库的数据子语言抽象成关系代数，又如何用关系代数的方法优化数据子语言的全过程。 1.4.3等价关系在计算机中的应用 前面我们研究了集合和元素，现在来研究结构的一些基本形式，它们是用集合的元素间的关系表示的。关系这一概念对计算机科学的理论和应用都是非常重要的，复合的数据结构，如陈列表列、树等，用来表示数据的集合，这些数据是由元素间的关系联系着的。关系是数学模型的一部分，它常常在数据结构内隐含地体现出来，数值应用、信息检索、网络问题等就是关系的应用领域，这些领域中关系作为描述问题的一部分而解决问题，因而关系的运算和处理是重要的。关系在包括程序结构和算法分析的计算理论方面也有重要的作用。定义1.4.3设p1，p2是A的任意两个划分，则p1p2p和p1p2p都是A的划分，p1p2和p1p2分别叫做划分的“积”与“和”，其中pp1p2，满足：（1）p细分p1和p2。（2）若另有p细分p1和p2，则p细分p。pp1p2满足：（1）p1和p2细分和p。（2）若另有A的划分p，且p1和p2细分p（p为能被p1和p2细分的最细的划分）。例1.4.9：在信息检索系统中，根据一个主码，可以把全体文献划分成两块，如主码是“知识工程”，则文献将根据它来分类。假定可以用十个主码，指定一个主码，则可确定文献集合中十个划分中的一个，然后再进行检索，则能在文献集合二十个划分中确定一个。若允许使用一个连接词AND，则可得到一个积划分p1p2，p2是分别由二主码确定的划分。p1p2中的一块相应于一个文献子集合。若使用一个连接词OR，则不会得到一个和划分p1p2中一块，而只是划分的积中一些块的并集。 1.4.4 序关系在项目管理中的应用 假设一个项目由20个任务构成，某些任务只能在其他任务结束之后完成。怎么能找到关于这些任务的顺序？对这