离散数学课件第7章.ppt

《离散数学课件第7章.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、1离散数学DiscreteMathematics汪荣贵教授合肥工业大学软件学院专用课件2010.05Chapter7Relations学习内容预备知识1集合基础预备知识2序偶与笛卡尔积7.1关系及其性质7.2n元关系及其应用7.3关系的闭包7.4等价关系7.5偏序学习内容预备知识1集合基础预备知识2序偶与笛卡尔积7.1关系及其性质7.2n元关系及其应用7.3关系的闭包7.4等价关系7.5偏序7.1n元关系及其应用在两个以上集合的元素中常会产生某种关系。例如，学生的姓名、学生的专业以及学生的平均学分之间的关系。一个航班的航空公司、航班号、出发地、目的地，起飞时间和到达时间之间的关系，等等。本节

2、我们将研究两个以上集合的元素之间的关系。即n元关系。可以用这种关系表示计算机的数据库。一、n元关系我们从建立关系数据库理论的基本定义开始。定义1：设A1,A2,…,An是集合，在这些集合上的n元关系是A1×A2×…×An的子集。这些集合A1,A2,…An叫做关系的域，n叫做它的阶。【example1】R是由三元组(a,b,c)构成的关系，其中a、b、c是满足a

3、，T是起飞时间。例如，如果Nadir直达航空公司在15：00有从Newark到Bangor的936航班，那么(Nadir，936，Newark，Bangor，15：00)属于R.这个关系的阶是5，并且它的域是所有航空公司的集合、航班号的集合、城市的集合、城市的集合以及时间的集合。二、数据库与关系操作数据库信息所需的时间依赖于这些信息是怎样存储的。一些基本的插入、删除、更新和检索记录以及从一个重叠的数据库中组合记录的操作在一个大型数据库中每天要执行几百万次。由于这些操作的重要性，已经开发了数据库表示的各种方法，这里将讨论其中一种基于关系概念的方法，叫做关系数据模型。数据库由记录组成，这些记录是

4、由字段构成的n元组，这些字段是n元组的数据项。例如，学生记录的数据库可以由包含学生的姓名、学号、平均学分绩点（GPA）的字段构成。关系数据模型把一个记录的数据库表示成一个n元关系。于是，学生记录可以被表示成形如（学生姓名、学号、专业、GPA）的4元组。关系数据模型中的一些性质6个记录的一个数据库样本是：（Achermann，231455，计算机科学，3.88）（Adams，888323，物理学，3.45）（Chou，102147，计算机科学，3.49）（Goodfriend，453876，数学，3.45）（Rao，678543，数学，3.90）（Stevens，786576，哲学，2.99）

5、2.用于表示数据库的关系叫做表，这些关系常用表来给出。这些表的每个列对应于数据库的一个属性。例如，上述的6个学生的数据所形成的数据库可以如表1所示。3.当n元组的某个域的值能够确定这个n元组时，n元关系的这个域就叫做主关键字。因为常常要从数据库中添加或删除记录。所以一个域是主关键字的性质是随时间而改变的。所以一个主关键字应该选择那种无论数据库怎么改变都能继续存在的字段。4.用数据库的内涵的主关键字在任何时候都是不会改变的，它包含了在表示这个数据库的n元关系中可能永远存在的所有的n元组。【example3】假设将来不再增加n元组，对于表1所示的n元关系，哪个域是主关键字？Solution：因为

6、在这个表中对应每个学生的姓名只有一个4元组，学生姓名的域是主关键字。类似地，在这个表中学号是唯一的，学号的域也是主关键字。但是，所学专业的域不是主关键字，因为包含同样的专业的4元组有多个。平均学分绩点的域也不是主关键字，因为有2个4元组包含了同样的GPA.5.在一个n元关系中域的组合也可以唯一地标识n元组。当一组域的值确定了一个关系中的n元组时，这些域的笛卡尔积就叫做复合关键字。【example4】对于表1中的n元关系，假设不增加n元组，所学专业的域与GPA的域的笛卡尔积是复合关键字吗？Solution：这个表中没有两个4元组有同样的专业和同样的GPA，因此这个笛卡尔积是一个复合关键字。6.

7、因为主关键字和复合关键字用于唯一地标识数据库中的记录，当新的记录被追加到这个数据库时关键字要保持有效是非常重要的。因此，应该确保与主关键字或复合关键字相对应的字段中每个新记录与表中所有其他的记录不同。例如，使用学号作为学生记录的主关键字是有意义的，因为没有两个学生有同样的学号。一个大学不应该使用姓名字段为主关键字，因为有可能两个学生有同样的姓名。三、n元关系的运算n元关系存在可以用于构成新的n元关系的不同的运